The five basic operations in propositional logic are and, or, implies, equivalent, and not. Not converts a proposition to its negation, while the others combine two propositions to form a new one. They are defined as follows, where we write "T" for "True", "F" for "False", and "iff" for "if and only if", another way of expressing equivalence.
| P | Q | Not(P) | Not(Q) | P and Q | P or Q | P implies Q | P iff Q |
| F | F | T | T | F | F | T | T |
| F | T | T | F | F | T | T | F |
| T | F | F | T | F | T | F | F |
| T | T | F | F | T | T | T | T |
These can be verified by constructing the truth tables for the compound propositions as follows.
| P | Q | P and Q | Not(P and Q) | Not(P) | Not(Q) | Not(P) or Not(Q) | Not(P and Q) iff (Not(P) or Not(Q)) |
| F | F | F | T | T | T | T | T |
| F | T | F | T | T | F | T | T |
| T | F | F | T | F | T | T | T |
| T | T | T | F | F | F | F | T |
The compound statement in the right hand column is always true, no matter what the truth values of P and Q are. This means that the two propositions on either side of the "iff", namely "Not(P and Q)" and "Not(P) or Not(Q)" always have the same truth value. (Compare the columns labelled with these two propositions.) The value of this is that we can replace one of these by the other while preserving the information we are given. This is analogous to applying the algebraic distributive law to change -(x+1) into -x-1 in the process of analyzing an algebraic expression.
Some comments about these definitions are in order.
First, the or defined here is often called the inclusive or because it is true if either one or both its propositions are true. This is the kind of or which we use when we say, for example, that we can buy milk at Farmer Jack or at Kroger. There is also an exclusive or which requires that exactly one of the two propositions be true, so its truth values are F, T, T, F, in order from top to bottom of the table above. The exclusive or is the one we mean when we say, for example, that we will travel from Philadelphia to Detroit for the Christmas holiday by airplane or by car.
Ordinary English does not carefully distinguish between these two, relying instead on context and our common sense to sort them out. This sort of ambiguity is not tolerable in mathematical work, so we have to decide which we mean when we say "or", if we choose to use the word "or". It turns out that the inclusive or is far more commonly needed, so this is the one mathematicians have chosen to mean when they say "or" without qualification. If the exclusive or is needed, it must be stated explicitly as in "P or Q but not both" or "P exclusive or Q".
The definition of implies bothers many people. Why should "P implies Q" be true when P is false? Here is a simple common sense example. Suppose I say "If I get home before dark, I will shovel the sidewalk" but do not manage to get home before dark and do not shovel the sidewalk. You would not consider that I had lied. So my statement "If I get home before dark, I will shovel the sidewalk" would have to be considered the truth. If I decided to shovel the sidewalk even though it was dark, I would also be considered to have told the truth. So, if the hypothesis "If I get home before dark" is false, the statement must be considered true independent of whether the conclusion "I will shovel the sidewalk" is true or not. In fact, the only situation in which the statement would be false would be if I did get home before dark, but did not shovel the sidewalk. This is exactly what "P implies Q" does: it is true unless P is true but Q is nonetheless false.
Most of the theorems we will study can be written in the form of an implication: P implies Q. This means that if the condition (P) holds, then the conclusion (Q) must also and that is all. If the condition (P) does not hold in some situation, then the theorem is still true, but does not tell us anything about that situation.
The fact that "P implies Q"" is equivalent to "Not(P) or Q" gives us several ways to approach proving it. Since we are assuming the law of the excluded middle "Q or Not(Q)" (check the truth table!) we could show that "Not(Q) implies Not(P)". Then we would know that "Q or Not(Q)" is true, so "Q or Not(P)" is true, so "Not(P) or Q" is true, and thus "P implies Q" is true. In other words
The statement "Not(Q) implies Not(P)" is called the contrapositive of "P implies Q" and has exactly the same meaning.
Exercise 1: Write "P exclusive or Q" in terms of the operations above.
Let us abbreviate "x is an element of A" by "x in A". Then we can translate the set theoretic definitions into logic as follows: