## Discrete Math 5: Logic

Logic is probably the most difficult thing to teach somebody because most people already think that they are logical. As humans we make a bunch of logical decisions everyday, but we never think about why. To understand the following it is best to think less and just try to accept it at first. Once you’ve read about it enough and played around with the topics it starts to make more sense.

In math we tend to enjoy using an “if then statement.” These statements are the foundation of proving something to be true since in order to prove something we have to assume something first. The “if” part of the statement is usually called the hypothesis and in a proof, we assume that to be true, while trying to show the “then” part, which is called the conclusion.

Consider the statement, “if it is raining, then it is wet.” We would want to prove that when it rains, it must be wet by using some sort of reasoning. I will come back to “if then statements” after some other stuff.

A proposition is a statement that is either true or false, but never both and without ambiguity. “My name is Brandon,” would be a true proposition. Just like numbers can be joined together by certain operations, so can propositions. We can “add” propositions to get new propositions.

The two first and most important operations between propositions are, “and” and “or.” In English, these two words can be ambiguous, but for logic they are strictly defined.

Remember they are operators between propositions, so their definitions are formed by using them to combine propositions. An “and” statement is only true if the two propositions that it combines into one, are true. For example, “It is raining, AND it is 2014” is only a true proposition when it is raining and it is also 2014, and it is false any other time. An “or” statement is true if either proposition is true, so for the statement “It is raining, OR it is 2014” to be true we only need it to be raining, or it to be 2014, or both things to be happening.

To make things more mathematical and annoying we can use symbols to represent propositions as well as these operations. Usually we use letters, P,Q, and R for propositions, while the symbols $\wedge$ and $\vee$ mean and and or respectively. So for the proposition P and Q we write, $P\wedge Q$

Lastly, we can use tables to represent these operations. Because a proposition has two possibilities either true or false, when we combine it with another proposition we have 4 total possible cases. The table will make it more clear:

 P Q $P \wedge Q$ $P \vee Q$ True True True True True False False True False True False True False False False False

You can see that each proposition, P and Q, is written 4 times, true and false twice each. This is because I need to do all possible cases for the and and or operations. You can also think of the operations as being defined specifically by these tables. This way of thinking will come in handy when I introduce more operations which will feel counter intuitive to your usual thoughts. So from here on we will consider operations defined by truth tables.

The next operations is “not.” It is also called negation, and it is just the opposite of the proposition. That is, when P is true, not P is false, and when P is false, not P is true. It is denoted by $\lnot P$

 P $\lnot P$ True False False True

This one is also pretty intuitive and exactly what you would expect. The next one is not so much that and confuses n00bs tremendously. It is called “implies” and is an operator between two propositions, P and Q, defined by the following truth table:

 P Q $P \rightarrow Q$ True True True True False False False True True False False True

“Implies” is only false when the first proposition is true and the second is false. The word “implies” is now confusing you highly, because one might suspect that the last two cases should also be false. When P is false, the statement “P implies Q” is called vacuously true. It is true regardless of Q being true or false because the first proposition P is false. The best explanation that I can offer is that because the condition P is not met, it doesn’t matter what Q is so that we can’t say Q is false. It is very hard to explain why these two cases are true, so for now just accept it as a definition of this new operator and move on. You can even call it something else so that the word “implies” doesn’t confuse it, call it “smackledorf.”

Just like with addition and multiplication for numbers, we can put operations together and define them how we would like them to be defined. I present a grand table:

 P Q $P \wedge Q$ $P \vee Q$ $P \rightarrow Q$ $\lnot (P \wedge Q)$ $\lnot (P \vee Q)$ True True True True True False False True False False True False True False False True False True True True False False False False False True True True

Here I’ve inserted the “not (P and Q)” and the “not (P or Q).” Notice that there would be a huge difference if the not was only attached to one thing. I’ll add two more columns here and notice that they are the same as two previous columns.

 P Q $P \wedge Q$ $P \vee Q$ $\lnot (P \wedge Q)$ $\lnot (P \vee Q)$ $\lnot P \vee \lnot Q$ $\lnot P \wedge \lnot Q$ True True True True False False False False True False False True True False True False False True False True True False True False False False False False True True True True

When two operations give the same truth table, we consider them to be logically equivalent. So from this table we can see that;

$\lnot (P \wedge Q) = \lnot P \vee \lnot Q$ and $\lnot (P \vee Q) = \lnot P \wedge \lnot Q$

So distributing the negation through an “and” or an “or” sends the negation to both propositions, while also changing the operation given into the other one. Truth tables are very useful for figuring out when two propositions are logically equivalent. These same rules apply to more propositions than two.

Another nice rule that we have is the distributive property. This requires three propositions, P, Q and R which means that our truth table needs 8 rows in order to fit all possible combinations.

 P Q R $P \vee (Q \wedge R)$ $P \wedge (Q \vee R)$ True True True True True True False True True True True True False True True True False False True False False True True True False False True False False False False False True False False False False False False False

You can use this truth table and then construct another to show that
$P \vee (Q \wedge R) = (P \vee Q) \wedge (P \vee R)$ and
$P \wedge (Q \vee R) = (P \wedge Q ) \vee (P \wedge R)$

So unlike with numbers both operations can distribute through each other (whereas multiplication distributes through addition but not vice versa). That is all for now.