Logic and Proofs

Please read Sections 2.5 through 2.7 of your textbook. That is where you will find complete explanations of the following ideas. Here I will summarize our class discussion.

In logic we work with statements that are either true or false. We use variables to represent such statements and logical operators to modify and/or connect them.

One such operator is negation, not. The symbol for not is ¬. If S is a true statement then "¬S" is false. If S is false, then "¬S" is true. Note that there is never a reason to say "¬ ¬S" because two nots cancel each other out.

Another operator is conjunction, and. The symbol for and is . If A and B are both true, then "A B" is true. If either or both are false, then "A B" is false

Disjunction is another operator, also known as or. The symbol for or is . If either A or B is true, then "A B" is true. If both are false, then "A B" is false.

Another operator is implication, if-then. The symbol used for if-then is . If A is true and B is false, then "A B" is false. Otherwise, it is true.


Snot S
T
F		F
T

ABA B A BA B
T
T
F
F		T
F
T
F 		T
F
F
F		T
T
T
F 		T
F
T
T

DeMorgan's Laws/Negation

We can combine negation with either conjunction or disjunction to obtain alternative ways to say the same thing. The following are known as DeMorgan's Laws:
¬(A  B) = ¬A  ¬B
¬(A  B) = ¬A  ¬B

For example, the negation of "John is a doctor AND Mary is not a lawyer." is "John is not a doctor OR Mary is a lawyer."

More on if/then statements

Many statements are written in the form "if A then B." Such statements can be written in several equivalent ways. All of the following are logically equivalent to "if A then B":
  1. A is sufficient for B.
  2. B is necessary for A.
  3. A implies B.
  4. B if A.
  5. A only if B.
  6. if not B then not A.

The contrapositive

The last statement in the above list is called the contrapositive of "if A then B".

The contrapositive. of "If A then B", is "If not B then not A". In mathematics, sometimes you will hear the phrase, "proof by the contrapositive." Proving the contrapositive is the same as proving the original statement, because they have the same truth value.
Two truth expressions are equal if and only if their truth table values are equal.

The converse and inverse

Other similar statements to "if A then B." do not mean the same thing. People are often misquoted by having their if statements turned around. You can see from the truth table that these statements are not the same.
  1. if B then A (called the converse of if A then B)
  2. if not B then not A (called the inverse of if A then B)

Tautologies and Contradictions

In a truth table, we look at the value of a compound truth statement under all possible combinations of values of the logic variables. Sometimes a compound truth statement is TRUE no matter what value the logic variables have. That type of statement is called a tautology. Section 2.7 of your text gives many examples of tautologies. In a truth table, all the values result in True.

Here are some tautologies:

  1. p or not p
  2. if p, then p
  3. if not p, then not p
  4. p is equivalent to p
  5. not (not a or not b) is equivalent to (a or b)

On the other hand, sometimes a compound truth statement is FALSE no matter what value the logic variables have. That type of statement is called a contradiction. Section 2.7 of your text gives many examples of contradictions. In a truth table, all the table values in the column of a contradiction result in false.

Here are some contradictions:

  1. p and not p
  2. p is equivalent to not p
  3. not (p or not p)