Discrete! #8: Discrete Mathematics and Its Applications 1.2B

Truth Tables, Compound Propositions, and the Use of De Morgan’s Laws

Here, on page 23, for the first time we see a truth table for NOT 1, NOT 2, but 3 propositions: p, q, and r. Let your eyes glide over it a bit and look for patterns. Let’s see what we can see.

First off, note that everything is really determined in the first box on the left, which shows values for p, q, and r. Furthermore, note that we could have infinitely many boxes to the right, as long as we were willing to get infinitely more complex. Note also we could achieve any pattern of T and F we wanted by having the right combination.

Second, note the way the Ts and Fs are stacked in the right box. If you’ve had any interaction with probability math, it should look familiar. With 3 propositions, each of which can occupy 2 values (T or F), you have $2^3$ possible arrangements. For simplicity, the easy way to do this is to use a sort of fractal: For the first proposition, split it so the top half is true then the top half is false. For the second proposition, split each section (the true section and the false section) in like manner. Repeat this until you’re just alternating between T and F, and you’ll have a nice clean arrangement.

Third, notice that this configuration gives you a sort of inverted pyramid, where everything is true at the tip and everything is false at the bottom, with gradations in between. This makes things easier down the line so you can say “okay, THIS is only true when everything is false, and THAT is true when there is at least one false thing.”

The reason it’s similar to probability is that in both cases, you’re essentially doing the same thing – you’re trying to consider every possible outcome at the same time.

Logical Equivalences

This might look a little intimidating. But, when you go through it, you’ll realize a lot of it is common sense. Let’s check’em out.

Identity Laws

p∧T≡p

Makes sense, right? A tautology is always true, so why should it affect the truth value when conjoined to some other proposition. Consider the following:

p: Hedgehogs are cute

T: The opposite of down is up and the opposite of up is down.

Imagine you were arguing that small animals are sometimes cute and you brought the above two points of evidence. p is as good as p∧T, since T brings nothing to the table.

p∨F≡p

Remember that OR gives you three ways to have a true statement: The first proposition is true, the second is true, or both are true.

Well, we know both aren’t true, since one is by definition false. We know the second isn’t true since… it’s by definition false. That leaves only one possible way for the above statment to get a truth value – the first proposition. Let’s think about an example:

p: Zach is sexy.

F: Joe is a bachelor and he is married.

If you say “p OR F,” you’re really saying “at least one of p or F is true.” Clearly that leaves only one possibility: The sexiness of Zach.

Domination Laws

These aren’t as sexy as you might hope.

p∨T≡T

Think about it like this: An or statement is true if at least one of its parts are true. Since, in this case, one of the parts is true by definition, we know the whole statement is true. That is, whenever you want to know whether an OR statement is true, you ask “is at least one part of it true.” In this case, the answer is automatically yes.

p∧F≡F

This is along similar lines. For a whole compound proposition to be true, all of its parts must be true. Here, we know a priori that at least one part is false. So, it can’t be the case that the whole proposition is true.

Idempotent Laws

So, this one took me to the dictionary.

Idempotence refers to something which, when applied to itself, produces itself. So, if the something is the number 1, and the application is multiplication, 1 is idempotent.

In logic, we get these two:

p∧p≡p

p∨p≡p

The first is pretty obvious. If p means “Zach is awesome,” then saying it twice doesn’t make it more true or more false.

The second is similar. If at least one part of the compound proposition is true, then both are true, since both parts are the same. If at least one is false, then both are false.

Double Negation Law

¬¬p≡p

I don’t think I need to explain this one. Anyone who’s ever been corrected for using double negatives knows there ain’t nothing difficult about this.

Commutative Laws

p∨q = q∨p

p∧q = q∧p

These should be pretty obvious by now. Here’s how I like to think about it: Since these aren’t conditionals, there’s no “direction” to their truth or falsehood. One proposition doesn’t depend on another – rather, you look at the whole statement to determine if it’s true. So, order shouldn’t matter.

Associative Laws

(p∨q)∨r≡p∨(q∨r)

(p∧q)∧r≡p∧(q∧r)

That is, for these operators, you can put the parenthesis wherever you like. This makes sense using similar reasoning to the commutative laws: with ANDs, ORs, and similar compound propositions, the statements of which they are made don’t depend on one another. The truth of the overall statement depends on the truth in a vacuum of its constituents.

Distributive Laws

Now we’re getting a little fancier. I’m going to flip the way the book does these, since the second one is more intuitive.

p∧(q∨r)≡(p∧q)∨(p∧r)

That first AND makes this a lot easier. So, we’re saying that, for the left side to be true, p and at least one of the other two propositions must be true. You’ll note the same is true, though perhaps less clear, on the right. Let’s do it as an example.

p: Panthers are cats.

q: Quails are birds.

r: Rats are rodents.

According to the above law’s left side, p is true, and one or both of p and r are true. So, it’s definitely the case that panthers are cats. AND, either quails are birds or rats are rodents, or both of things things are true.

According to the right side, either “panthers are cats and quails or birds” OR “panthers are cats and rats are rodents” OR both of those are true. You see that in any of the three possible cases “Panthers are cats” is true. You also see that the other possibilities may or may not be true, just as in the left side.

p∨(q∧r)≡(p∨q)∧(p∨r)

This operates along the same lines. The left side says “either panthers are cats OR quails are birds and cats are rodents OR panthers are cats and quails are birds and cats are rodents.” So, it’s possible that only p is true, or that q AND r are true, or that all three are true.

On the right, we see the same thing. For the whole proposition on the right to be true, both of these things must be true:

1) at least one of p and q are true.

2) at least one of p and r are true.

This means that most of the possible options are true. However, you can’t have it be the case that just r or just q is true and everything else is false. If you did so, at least one clause of the right hand side would be false, thereby making the whole thing false.

I know this can feel a little Byzantine at times, but the beauty of it is that it can’t be otherwise. So, the more you think about it correctly, the easier it all gets.

De Morgan’s Laws

We’ve already gone over these previously, so I won’t linger here.

Absorption Laws

p∨(p∧q)≡p

p∧(p∨q)≡p

These might feel a little tricky at first glance. Let’s look at the first one first.

Here’s how I like to think of it: Imagine you’re taking a test with two questions. One question is question p, and one is question q.

Now, imagine your teacher says “You pass if you get p right OR you get both right. Well then, your passing is ENTIRELY dependent on how you answer p. You might get q right or wrong, but either way, you only pass if you get p right.

Now, imagine “right” means “true” and “wrong” means “false” and when I say “passing,” I’m referring to the whole compound proposition being considered true. You see how the truth value of the overall statement depends entirely on p.

Let’s look at the second statement and imagine the exam again. This time, your teacher says “In order to pass, you must get p correct AND p or q correct.” Once again, you’re only going to bother with p, since q has no effect on your outcome. That is, the truth or falsity of the compound proposition depends online on p.

Make sense?

Negation Laws

p∨¬p≡T

p∧¬p≡F

This is basically a restatement of the idea of tautology and contradiction. Moreover, it’s a statement of a basic assumption we’re making: That a statement can ONLY be true or false.

With that in mind, we see the top statement merely says “This statement is either true or false,” which is true no matter what the statement is. The bottom statement says “This statement is true AND this statement is false.” That is clearly false no matter what the statement is.

OOF. Hope that didn’t seem too complicated. I find that simple things in math are often the hardest to wrap your head around, since you expect to lean on your intuition, and your intuition is based on your experience. That way of thinking is only useful if you’re setting up your thought process properly.

Since I am only partially versed in discrete, at this point, I’m going to start going over the problems myself before I wrote more sections. Hopefully that won’t slow things down too much. On the plus side, I should be able to help by working some of the more interesting problems.

Next stop: More logical equivalences.

This entry was posted in Autodidaction, Discrete Math. Bookmark the permalink.

3 Responses to Discrete! #8: Discrete Mathematics and Its Applications 1.2B

1. david says:

when explaining p∨(p∧q)≡p with the test analogy you confused q with p a couple of times (or you shuld have said ‘INDEPENDNT’ instead of DEPENDENT, etc)

• ZachWeiner says:

Fixed!

2. j says:

where do i find numbers 1-7, also, what text are you following?