Lecture 2

Lecture 2
Logic
Def 1: The equivalence of two statements A and B, often denoted A if and only
if B, A iff B, A ⇐⇒ B, informally as A = B, A and B are equivalent statements if
they have precisely the same truth values.
Prop: A =⇒ B and ¬A∨B are equivalent statements. I.e. (A =⇒ B) ⇐⇒ (¬A∨B).
Proof. The proof follows from the truth table below.
A B ¬A ¬ A ∨ B
T T F T
T F F F
F T T T
F F T T
By comparing the truth values, we see that the statements are equivalent.
This can come in handy, in many proofs is it easier to work with ¬A ∨ B instead of
A =⇒ B.
Note: The implication P =⇒ Q is often in the following equivalent phrases.
• Q if P
• Q whenever P
• Q provided that P
• P only if Q (this is easier to see through the contrapositive that willl be
described later)
• P is a sufficient condition for Q.
For an implication A =⇒ B, the converse of this implication is the reverse implica-

tion B =⇒ A.
A B A =⇒ B B =⇒ A
T T T T
T F F T
F T T F
F F T T
2
Thus we can see in general that an implication and its converse do not share the same
truth values, i.e. generally an implication and it’s converse are not logically equivalent.
Ex: Consider the statement,
If an animal is a cat, then it has at most four legs.
and it’s converse
If an animal has at most four legs, then it is a cat.
Pretty clear one of these is true, right?
Def 2: The equivalence/biconditional of two statements A and B, often denoted
A if and only if B, A iff B, A ⇐⇒ B, informally as A = B, is given by (A =⇒
B) ∧ (B =⇒ A). It’s truth table is given by
A B A =⇒ B B =⇒ A (A =⇒ B) ∧ (B =⇒ A)
T T T T T
T F F T F
F T T F F
F F T T T
Notice that this lines up with our prior definition of equivalence as the truth table
shows that A ⇐⇒ B precisely when A and B have identical truth values.
Similar to implication, there are many ways to state logical equivalence
• P if and only if Q.
• P is a necessary and sufficient condition for Q.
• If P , then Q and conversely.
Remark For any statement B, the compound statement B ∧ ¬B

B ¬B B∧¬B
T F F
F T F
is always false. A statement that is always false is called a contradiction.
3
Remark The statement (A ∧ ¬B) ⇐⇒ ¬(A =⇒ B). Via truth table, we see
A B ¬ B A ∧ ¬ B A =⇒ B ¬ (A =⇒ B) ⇐⇒
T T F F T F T
T F T T F T T
F T F F T F T
F F T F T F T
A statement that is always true is called a tautology. (Note: In this case, this is a
tautology because these two statements are equivalent)
All right, let’s be honest. Truth tables can be very boring to work out sometimes.
Luckily, once we have shown certain statements are tautologies via truth tables, we
can use the algebra of logcial connectives to prove two statements are equal.
So, we begin by seeing how certain logical connectives interplay.
Distribution of Negation
Prop: ¬(A ∧ B) ⇐⇒ ¬A ∨ ¬B.
Proof. We check by truth table.
A B A ∧ B ¬ (A ∧ B) ¬ A ¬ B ¬ A ∨ ¬ B
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T
And so the result holds.
Similarly one can check that ¬(A ∨ B) ⇐⇒ ¬A ∧ ¬B.
Distribution Laws
Prop: A ∧ (B ∨ C) ⇐⇒ (A ∧ B) ∨ (A ∧ C)
Proof. We check by truth table

4
A B C B ∨ C A ∧ (B ∨ C) A ∧ B A ∧ C (A ∧ B) ∨ (A ∧ C)
T T T T T T T T
T T F T T T F T
T F T T T F T T
T F F F F F F F
F T T T F F F F
F T F T F F F F
F F T T F F F F
F F F F F F F F
Similarly one can show A ∨ (B ∧ C) ⇐⇒ (A ∨ B) ∧ (A ∨ C).
Associativity
Prop: A ∧ (B ∧ C) ⇐⇒ A ∧ B ∧ C.
Proof. We check by truth table
A B C B ∧ C A ∧ (B ∧ C) A ∧ B ∧ C
T T T T T T
T T F F F F
T F T F F F
T F F F F F
F T T T F F
F T F F F F
F F T F F F
F F F F F F
Similarly, one can check that A ∨ (B ∨ C) ⇐⇒ A ∨ B ∨ C.

Now that we have these rules, we can check the equivalence of statements algebraically.
Ex: Prove that A =⇒ (B ∨ C) is equivalent to (A ∧ ¬B) =⇒ C.
Proof.
A =⇒ (B ∨ C) ⇐⇒ ¬A ∨ (B ∨ C) As P =⇒ Q ⇐⇒ ¬P ∨ Q.
⇐⇒ ¬A ∨ B ∨ C Associativity
5
⇐⇒ (¬A ∨ B) ∨ C Associativity
⇐⇒ ¬(A ∧ ¬B) ∨ C Rules of negation
⇐⇒ (A ∧ ¬B) =⇒ C As P =⇒ Q = ¬P ∨ Q.

Def: Given two statements P, Q, given the implication statement P =⇒ Q, the

associated contrapositive statement is ¬Q =⇒ ¬P .
Looking at the following truth table we can see
P Q ¬P ¬Q P =⇒ Q ¬Q =⇒ ¬P
T T F F T T
T F F T F F
F T T F T T
F F T T T T
that (P =⇒ Q) ⇐⇒ [(¬Q) =⇒ (¬P )], i.e. the contrapositive is logically equiavalent
to the original implication.
Def: There are two important quantifiers that are often used in mathematics.
• The universal quantifier ,∀, which means for all elements.

• The existential quantifier, ∃, which means there exists an element.
These quantifiers just give a more compact way of writing statements, for example,
1
∃x ∈ N, s.t. ∈ N.
x
is a more compact way to say the statement “There exists an element of the natural
numbers, x, such that its reciprocal, x1 , is also a natural number.” Similarly,
∀x ∈ R, x2 > 0.
says, “For every element x of the real numbers, x2 > 0.”
Ex: Determine the truth values of the above statements. (True and False respec-
tively)

Lecture 2

Uploaded by

Copyright:

Available Formats

Lecture 2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture 2

Uploaded by

Copyright:

Available Formats

Lecture 2

Proof. The proof follows from the truth table below.

For an implication A =⇒ B, the converse of this implication is the reverse implica-

Remark For any statement B, the compound statement B ∧ ¬B

Prop: ¬(A ∧ B) ⇐⇒ ¬A ∨ ¬B.

Proof. We check by truth table.

And so the result holds.

Similarly one can check that ¬(A ∨ B) ⇐⇒ ¬A ∧ ¬B.

Proof. We check by truth table

Similarly one can show A ∨ (B ∧ C) ⇐⇒ (A ∨ B) ∧ (A ∨ C).

Proof. We check by truth table

Similarly, one can check that A ∨ (B ∨ C) ⇐⇒ A ∨ B ∨ C.

Def: Given two statements P, Q, given the implication statement P =⇒ Q, the

• The universal quantifier ,∀, which means for all elements.

You might also like