Discrete #7: Discrete Mathematics and Its Applications 1.2A

Section 1.2: Propositional Equivalences

Okay, now things start to get a little more interesting. In this section, we get the idea of propositional equivalence, which is pretty straightforward, and De Morgan’s Laws, which are a little trickier but very important.

Let’s dig in.

You may remember in the last section I solved a logic puzzle by proceeding from an assumption to a contradiction, thereby proving the assumption wrong. Well, a contradiction is actually a super important concept, usually denoted “F.”

The simple version is p∧¬p, or “p and not p.” Or, more contradictorialy (not a real word), “P is true and not p is true” In other words, a contradiction is a statement that is always false no matter what has because it implies that a proposition is both false and true. Regardless of whether p is true or p is false, the above statement is always false.

The explicit assumption is that a proposition cannot be both true and false. This is why politicians are lousy at logic.

The opposite of a contradiction is a tautology. A tautology is a statement that is always true, no matter what. This is always true because bachelors are by definition unmarried. Tautology is usually denoted “T.” The simple version could be written p∧p. Note that no matter what truth value you assign p, the conditional p∧p is still true.

Unfortunately, this can get a little confusing because truth tables use the T and F symbols. So, to be clear: if a statement (say, p∧q) is listed as false somewhere on your table, that doesn’t mean it’s a contradiction at that point. The false on your table refers to one possible truth value in relation to other information. It is distinct from a contradiction.

So, for example, the statement “Zach Weiner is lousy in bed” is false, but it is not self-contradicting. It could be true, in some crazy universe with different and stupid standards, because although empirically it seems false, it doesn’t self-contradict. To be a contradiction, you’d have to say “Zach Weiner is lousy in bed and not lousy in bed.” Similarly, “Zach Weiner is great in bed” is true, but not a tautology. A tautology would be something like “Zach has red hair or Zach is a ginger.”

If something is NOT a contradiction or a tautology, it is a contingency. Most things you encounter in your life will be contingencies.

Unfortunately, it’s not always obvious when two statements form a contradiction or a tautology. To do that, you have to write out a truth table. If you have two statements with the same truth table, you can say that “p↔q is a tautology.” Or, in layman’s terms “p and q mean the same fucking thing.”

The way you denote this is the “logical equivalence” symbol, which is an equal’s sign with fifty percent more parallel lines than usual: p≡q.

De Morgan’s Laws

Now that you get the idea behind logical equivalence, you get a really powerful tool. De Morgan’s Laws. Here they are:

1) ¬(p∧q)≡¬p∨¬q

2) ¬(p∨q)≡¬p∧¬q

That may seem a little tricky at first. The visual mnemonic I used to use was this: Imagine the “not” sign is a battering ram that bashes through the parentheses. In its wake, all the statements are negated and the operator is flipped upside down.

Let’s do an example to prove it makes some sense. Note, I’m just going to make up two statements – I didn’t think hard about these because I don’t have to – the logic does the work for me.

p: Puppies are cute.

q: Revenge is a dish best served cold.

So, in (1) from above, the left side says “It is not the case that puppies are cute AND revenge is a dish best served cold.” Think about what you can infer from that. Because it’s “AND” it’s only true when both p and q are true. So, all you know is that at least one statement is false. That leaves 3 possibilities: p is false, q is false, or both are false.

Well, how would you state that idea logically? Simple: ¬p∨¬q. In an English sentence: “puppies aren’t cute OR revenge is not a dish best served cold OR puppies aren’t cute and revenge is not a dish best served cold.” The left and right hand statements are logically equivalent.

Let’s try it out on (2): ¬(p∨q)≡¬p∧¬q

The left side says “It is not the case that p or q are true.” That is, the following possibilities are false: only p is true, only q is true, both p and q are true. Immediately, you’re going to see that’s very restrictive. In fact, it leaves only one possibility: that both statements are false. How would you say that? Simple:¬p∧¬q

Got it? If you’re still not convinced, check out the provided truth tables in the book.

Next stop, distribution laws!



This entry was posted in Autodidaction. Bookmark the permalink.

6 Responses to Discrete #7: Discrete Mathematics and Its Applications 1.2A

  1. Juby says:

    p→¬p isn’t really a contradiction, though. In the logical system that we’re using, an implication is false only if the antecedent is true and the conclusion is false (hence why we say that p→q is equivalent to ¬p∧q). If p is false, then the implication is true, as we evaluate F→T to be true.

    A contradiction is a logical expression where all possible truth value assignments result in the expression being evaluated as false, which is not true with p→¬p, as shown above. The best example of a contradiction I know of is p∧¬p — a proposition cannot be both true and false at the same time. If p is false, then we have F∧T, which is false. If p is true, then we have T∧F, which is also false.

    The above definition of implication sometimes seems counterintuitive, and in fact is an issue of some debate in philosophical circles. Modal logic is one logical system I know of that attempts to address this problem, though it has problems of its own. For mathematical purposes, though, the given definition of implication works; we refer to implications where the antecedent is false as trivially true.

  2. Hypothetical non ginger Zach says:

    Zach has red hair and Zach is a ginger is not a tautology, for example in a world (or a comment) where there is a Zach that is not is none of those.
    Zach has red or Zach is not a ginger is a tautology.

  3. Ian says:

    This statement is unfortunately not correct either:
    >The simple version could be written p∧p. Note that no matter
    >what truth value you assign p, the conditional p∧p is still true.

    If p is false, then p∧p is also false. I think you meant p∨¬p or something like that. But a tautology doesn’t necessarily have that form – it just is a logical statement that is always true.

    Oh, by the way, I’m enjoying reading the blog.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>