Logic and Proof

February 2, 2023
ii
Contents

1 Logic 1
1.1 Propositions and Connectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Logical operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Conditionals and Biconditionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Other logical operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Tautologies and contradictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Logical equivalences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Predicate Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.2 Universal Conditiona statements . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.3 Multiple quantifiers and negating sentences . . . . . . . . . . . . . . . . . . . . . 7

iii
iv
Chapter 1

Logic

1.1 Propositions and Connectives

Definition 1.1 A proposition (or statement) is a sentence that has exactly one truth value, that is,
either true or false. We will denote true as T and false as F.

Example 1.2

1. 3 + 4 = 6, F (proposition)

2. She lives in Marawi. (not a proposition because it could be true or false depending upon the person
to whom ”she” refers)

3. x + 3 = 7 (not a proposition)

4. This sentence is false (not a proposition)

Variables are used to represent propositions. The most common variables used are p, q, and r (called
propositional variables).

1.1.1 Logical operators

Propositions can be combined using logical operators to create more complex propositions.

Definition 1.3 The negation of a proposition p, denoted by ¬p, is the proposition “not p”. The propo-
sition ¬p is true exacly when p is false.

Example 1.4 p : 5 is divisible by 3 (F )

¬p : 5 is not divisible by 3 (T )

Definition 1.5 Let p and q be propositions. Then the conjuction of p and q, denoted by p ∧ q, is the
proposition “p and q”. p ∧ q is true exactly when both p and q are true.
The disjunction of p and q, denoted by p ∨ q, is the proposition ”p or q”. p ∨ q is true exactly when
at least one of p or q is true.

Example 1.6 Let p : 19 is composite; q : 45 is multiple of 3. Then

1. 19 is composite and 45 is multiple of 3: p ∧ q (F - is a false proposition)

2. 19 is composite or 45 is multiple of 3: p ∨ q (T - is a true proposition)

3. Either 19 is not composite or 45 is not a multiple of 3 (¬p ∨ ¬q - is a true proposition)

TRUTH TABLE:

p q p∧q p q p∨q
T T T T T T
F T F F T T
T F F T F T
F F F F F F

p ¬p
T F
F T

1
1.1.2 Conditionals and Biconditionals
Definition 1.7 Let p and q be propositions. Then the conditional, p ⇒ q is the proposition ”If p,
then q”. Proposition p is called the antecedent (or premise, hypothesis) and q is the consequent (or
conclusion). The conditional sentence p ⇒ q is true if and only if p is false or q is true.
TRUTH TABLE:
p q p⇒q
T T T
F T T
T F F
F F T

Example 1.8

1. If sin π = 1, then 6 is prime.(T) p is F; q is F

2. If 13 > 7, then 2 + 3 = 5.(T) p is T; q is T

3. If π = 3, then Paris is the capital of France.(T) p is F; q is T

4. If 4π > 10, then 6 is a prime number.(F) p is T; q is F

Definition 1.9 Let p and q be propositions.

Conditional: p ⇒ q
Converse: q ⇒ p
Inverse: ¬p ⇒ ¬q
Contrapositive: ¬q ⇒ ¬p

Example 1.10

1. Conditional: If π is an integer then 24 is even.(T)

Converse: If 24 is even, then π is an integer.(F)
Inverse: If π is not an integer then 24 is not even.(F)
Contrapositive: If 24 is not even, then π is not an integer.(T)
p : π is an integer (F); q : 24 is even (T)
√
2. Conditional: If 2 + 2 = 4 then 12 > 3.(T)
√
Converse: If 12 > 3 , then 2 + 2 = 4.(T)
√
Inverse: If 2 + 2 6= 4 then 12 ≤ 3.(T)
√
Contrapositive: If 12 ≤ 3 , then 2 + 2 6= 4.(T)
√
p : 2 + 2 = 4 (T); q : 12 > 3 (T)

TRUTH TABLE:

p q ¬p ¬q p⇒q q⇒p ¬p ⇒ ¬q ¬q ⇒ ¬p

T T F F T T T T
F T T F T F F T
T F F T F T T F
F F T T T T T T

From the above table, it shows that p =⇒ q is equivalent to its contrapositive ¬q =⇒ ¬p.

Definition 1.11 Let p and q be propositions. The biconditional p ⇐⇒ q is a proposition that p and q
have the same truth values. In other words, either p and q are both true or p and q are both false. In
words, the biconditional is stated as “p if and only if q”.
TRUTH TABLE:
p q p ⇐⇒ q
T T T
F T F
T F F
F F T

Example 1.12

1. 33 = 27 if and only if 16 is a perfect square.(T)

p : 33 = 27 (T); q : 16 is a perfect square (T)

2
 2. 3 + 2 = 5 if and only if Lanao Lake is in Iligan.(F)
p : 3 + 2 = 5 (T); q : Lanao Lake is in Iligan. (F)

Below are some phrases in English that are ordinarily transalted by using the connectives =⇒ or ⇐⇒.

Definition 1.13 A logical connective is an operation used to combine propositions into more compli-
cated propositions.

Definition 1.14 A compound proposition is a proposition that has been built by applying at least one
logical connective to one or more propositions.

1.1.3 Other logical operator

Definition 1.15 The exclusive or is the logical operator which, when applied to two propositions p and
q yields the proposition “p xor q”, denoted p ⊕ q, which is true if exactly one of p or q is true, but not
both. It is false if both are true or if both are false.

1.2 Tautologies and contradictions

Definition 1.16 A tautology is a propositional form that is true for every assignment of truth values
to its components.
A contradiction is a propositional form that is false for every assignment of truth values to its
components.

Definition 1.17 A contingency is a proposition that is neither a tautology nor a contradiction.

Example 1.18

1. The proposition p ∨ ¬(p ∧ q) is a tautology.

2. The proposition (p ⇐⇒ q) ∧ (¬p ∧ q) is a contradiction.

3. The proposition p ∨ q ⇒ ¬r is a contingency.

1.2.1 Logical equivalences

Definition 1.19 Two compound propositions are logically equivalent if they have the same truth value
regardless of the truth values of the components. If r and s are compound propositions that are logically
equivalent, we write r ≡ s.

Example 1.20 Let p and q be propositions. The compound propositions

r : ¬(p ∧ q) and s : ¬p ∨ ¬q

are logically equivalent.

SolutionWe make a truth table that indicates the truth values of these two compound propositions

3
 TRUTH TABLE:

p q p∧q ¬(p ∧ q) ¬p ¬q ¬p ∨ ¬q
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

Thus, r and s are logically equivalent, or in symbol, r ≡ s.

Solution 2:
Let p and q be propositions.

case 1. Suppose ¬(p ∧ q) is true and ¬p ∨ ¬q is false.

¬(p ∧ q) is true if p ∧ q is false. This implies that p is false or q is false. But in each case, ¬p ∨ ¬q
will be true. Hence, this case is not possible.

cse 2. Suppose ¬(p ∧ q) is false and ¬p ∨ ¬q is true.

¬(p ∧ q) is false if p ∧ q is true. This means that both p and q are true. Hence, ¬p ∨ ¬q will be
false. So, this case is not possible.

Since it is not possible for the two propositions to have different truth values, they must be equivalent.

Theorem 1.21 Let p, q, and r be propositions.

1. p ∧ T ≡ p; p ∨ F ≡ p (Identity Laws)

2. p ∨ T ≡ T ; p ∧ F ≡ F (Domination Laws)

3. p ∨ p ≡ p; p ∧ p ≡ p (Idempotent Laws)

4. ¬(¬p) ≡ p (Double Negation Law)

5. ¬(p ∧ q) ≡ ¬p ∨ ¬q (De Morgan’s law)

6. ¬(p ∨ q) ≡ ¬p ∧ ¬q (De Morgan’s law)

7. p ⇒ q ≡ ¬q ⇒ ¬p (Contrapositive)

8. p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) (Distributive Law)

9. p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) (Distributivite Law)

10. p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r (Associative Law)

11. p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r (Associative Law)

12. p ∧ q ≡ q ∧ p (Commutative Law)

13. p ∨ q ≡ q ∨ p (Commutative Law)

14. p ∧ (p ∨ q) ≡ p; p ∨ (p ∧ q) ≡ p (Absorption Laws)

15. p ⇒ q ≡ ¬p ∨ q (Implication Law)

16. p ∨ ¬p ≡ T (Tautology)

17. p ∧ ¬p ≡ F (Contradiction)

18. (p ⇒ q) ∧ (q ⇒ p) ≡ p ⇐⇒ q (Equivalence)

Example 1.22 Use the logical equivalences to show that ¬(p ∨ ¬(p ∧ q)) is a contradiction.
Solution

¬(p ∨ ¬(p ∧ q)) ≡ ¬p ∧ ¬(¬(p ∧ q)) (De Morgan’s Law)

≡ ¬p ∧ (p ∧ q) Double Negation Law
≡ (¬p ∧ p) ∧ p (Associative Law)
≡ F ∧ p (Contradiction)
≡ F (Domination Law and Commutative Law)

4
1.3 Predicate Logic
Recall from the first section that the sentence “x + 3 = 7” is not a proposition, but if we assign a value
for x then it becomes a proposition. A sentence like this with a variable is called an open sentence or
a predicate. It can only be true or false after x is assigned a particular value.
When we have an open sentence with a variable x, it is generally written as P (x). So, P (4) is true
while P (2) is false.
Similarly, when we have more variables, like the open sentence “x+y = 5” we might write as Q(x, y).
So here, Q(2, 3) is true and Q(4, 1) is true, but Q(3, 1) is false.
When we have an open sentence, the collection of objects that can be substituted in for the variable
is called the universe, or universe of discourse, denoted as U .
The elements of the universe that can be substituted in to make the sentence true is called the truth
set.

Definition 1.23 An open sentence or predicate is a declarative sentence containing one or more vari-
ables such that when all of the variables are assigned values in their respective domains, the resulting
sentence has a truth value.

Example 1.24 Let x and y be variables, both with the same domain Q. We may define the open
sentence
P (x, y) : x − 1 = y
With this definition we see that P (5, 4) is true (since 5 − 1 = 4),P (3, 1) is false (since 3 − 1 6= 1).

Example 1.25 Let U be the set of triangles and let x be a variable with domain U . Suppose P (x)
is the sentence “one of the angles of x is a right angle". Then P (x) is a true statement if x is a right
triangle.

1.3.1 Quantifiers
A quantifier turns an open sentence into a proposition without assigning specific values for the variable.

Definition 1.26 Let x be a variable with domain S and let P (x) be an open sentence. The expression

∀x ∈ S, P (x)

is then a proposition. This proposition is true, if the open sentence P (x) is true for all values of x ∈ S.
We read the proposition ∀x ∈ S, P (x) as “for all x in S, P (x),” “for every x in S, P (x),” “for each x
in S, P (x).”
We call the symbol “ ∀ 00 the universal quantifier.

Definition 1.27 Let x be a variable with domain S and let P (x) be an open sentence. The expression

∃x ∈ S, P (x)

is then a proposition. The proposition is true, if there exists an element x ∈ S such that P (x) is true.
We read the proposition ∃x ∈ S, P (x) as “there exists some x in S, such that P (x),” “there is at least
one x in S such that P (x).”
We call the symbol “ ∃ 00 the existential quantifier.

Definition 1.28 Let x be a variable with domain S and let P (x) be an open sentence. The expression

∃!x ∈ S, P (x)

is then a proposition. The proposition is true, if there exists a unique element x ∈ S such that P (x) is
true.
We read the proposition ∃!x ∈ S, P (x) as “there exists unique x x in S, such that P (x),” “there is
exactly one x in S such that P (x).”
We call the symbol “ ∃! 00 the unique existential quantifier.

Example 1.29 Let x be a variable with S = {0, 1, 2} and the open sentence

P (x) : x2 = x,

and
Q(x) : x − 1 > 0,
then the proposition ∀x ∈ {0, 1, 2}, P (x) is a false proposition while ∃x ∈ {0, 1, 2}, P (x) is a true
proposition; and ∃!x ∈ {0, 1, 2}, Q(x) is a true proposition.

5
Example 1.30 Let x and y be an integers and let R(x, y) : xy > 0 be an open sentence. Then

i. R(−2, −5) is a true proposition.

ii. ∀x ∈ Z, R(x, 0) is a false proposition.

iii. ∃y ∈ Z, R(−3, y) is a true proposition.

Example 1.31 Translate the following English sentences into symbolic logic containing one quantifier.
Indicate the truth value of each proposition.

1. For every natural number x, x + 2 > 0.

Solution. ∀x ∈ N, x + 2 > 0. This proposition is true.

2. For each integer x, x + 2 > 0.

Solution. ∃x ∈ Z, x + 2 > 0. This proposition is false.

3. There exists an integer y such that 2y 2 + 3y = 2.

Solution. ∃y ∈ Z, 2y 2 + 3y = 2. This proposition is true.

1.3.2 Universal Conditiona statements

Definition 1.32 The universal conditional statement has the form

∀x, if P (x), then Q(x),

where P (x) and Q(x) are open sentences.

The proposition ∀x, P (x) ⇒ Q(x) means that every element in the truth set of P (x) is in the truth
set of Q(x).
The above quantified statement is false when there is one or more values of x for which P (x) is true
and Q(x) is false. Thus, in order it to be true, it must be the case that for each x ∈ S either P (x) is
false or Q(x) is true. And f we know that P (x) is true, then Q(x)must be true.

The quantified statements ∀x ∈ U, if P (x), then Q(x) can always be written as

∀x ∈ S, Q(x)

where S is the truth set of P (x).

Conversely, the statement of the form

∀x ∈ S, Q(x)

can be written as
∀x, if x is in S, then Q(x).

Example 1.33 Rewrite the following statements formally and indicate the truth value.

1. All nonzero real numbers have positive squares.

Solution. ∀x ∈ R, If x is nonzero, then x2 is positive.(True)

2. If a polygon has 3 sides, it must be a triangle.

Solution. ∀ polygon p, If p has three sides, then p is a triangle. (True)

3. If p is prime then p is odd.

Solution. ∀ prime p, p is odd.(False)

Let P (x) and Q(x) be two quantified statements with nonempty universe of discourse U . Two
statements P (x) and Q(x) are equivalent in U if and only if P (x) and Q(x) have the same truth value
for all x ∈ U. That is, P (x) and Q(x) are equivalent in U if and only if ∀x ∈ U, P (x) ⇐⇒ Q(x). The two
quantified statements P(x) and Q(x) are equivalent if and only if they are equivalent in every universe
of discourse U .

6
1.3.3 Multiple quantifiers and negating sentences
Example 1.34 Let P (x, y) be the open sentence xy = 1 with the domain of x being the set of positive
integers and y the set of real numbers. We examine the following statements
1. ∀x, ∀y, P (x, y)
This statement means: For each positive integer x and for each real number y, xy = 1. (False)

2. ∀x, ∃y, P (x, y)

This statement means: For each positive integer x, there is a real number y such that xy = 1.(True)

3. ∃y, ∀x, P (x, y)

This statement means: There exists a real number y such that, for every positive integer x, xy =
1.(False)

Remark 1.35 Let P (x, y) be an open sentence. Then

∀x, ∀y, P (x, y) ≡ ∀y, ∀y, P (x, y)

∃x, ∃y, P (x, y) ≡ ∃y, ∃y, P (x, y)

∀x, ∃y, P (x, y) 6≡ ∃x, ∀y, P (x, y)

Proposition 1.36 Let P (x) be an open sentence, where x has domain S. Then
i. ¬(∀x ∈ S, P (x)) ≡ ∃x ∈ S, ¬P (x)

ii. ¬(∃x ∈ S, P (x)) ≡ ∀x ∈ S, ¬P (x)

Example 1.37 Negate the following proposition.

1. The square of every real number is nonnegative.
Statement/Proposition: ∀x ∈ R, x2 ≥ 0.
Negation: ¬(∀x ∈ R, x2 ≥ 0) ≡ ∃x ∈ R, ¬(x2 ≥ 0) ≡ ∃x ∈ R, x2 < 0
In words, there exists a real number whose square is negative.

2. For each real number x, there is a real number y for which y 4 = x.

Let S(x, y) be the sentence “y 4 = x”.
Quantified Statement: ∀x ∈ R, ∃y ∈ R, y 4 = x.
Negation:

¬(∀x ∈ R, ∃y ∈ R, y 4 = x) ≡ ∃x ∈ R, ¬(∃y ∈ R, y 4 = x)
≡ ∃x ∈ R, ∀y ∈ R, ¬(y 4 = x)
≡ ∃x ∈ R, ∀y ∈ R, y 4 6= x.

In words, there is a real number x for which y 4 = x for all real numbers y.

3. All rational numbers are positive.

Let Q(x) be the sentence “rational numbers are positive.”
Quantified Statement: ∀x ∈ Q, x > 0.
Negation: ∃x ∈ Q, x ≤ 0.
In words, there exists a rational number that is not positive.

4. All men have at least one friend.

Let S be the set of men and let R(x, y) be the sentence “y is a friend of x.”
Quantified statement: ∀x ∈ S, ∃y ∈ S, P (x, y).
Negation: ∃x ∈ S, ∀y ∈ S, ¬P (x, y)
In words, there is a man who has no friends.

Negating Universal Conditional statement

Recall: p ⇒ q ≡ ¬p ∨ q
So, ¬(p ⇒ q) ≡ p ∧ ¬q.
The negation of the universal conditional statement is logically equivalent to an existential statement.

¬(∀x, P (x) ⇒ Q(x)) ≡ ∃x such that ¬(P (x) ⇒ Q(x)) ≡ ∃x such that P (x) ∧ ¬Q(x)

7
Example 1.38 If a person is blond, then they have blue eyes.
Universal of discourse/Domain: All people
Statement: ∀ people p, if p is blond, then p has blue eyes.(F)
Negation: ∃ person p such that p is blond and p does not have blue eyes.(T)
In words, Some people are blond and do not have blue eyes.

Example 1.39 Consider the statement, ∀x ∈ R, if x > 3, then x2 > 9.

Negation: ∃x ∈ R such that x > 3 and x2 ≤ 9.

Definition 1.40 Consider a statement of the form: ∀x, P (x) ⇒ Q(x)

Contrapositive: ∀x, ¬Q(x) ⇒ ¬P (x)

Converse: ∀x, Q(x) ⇒ P (x)

Inverse: ∀x, ¬P (x) ⇒ ¬Q(x)

Example 1.41 From the previous example, ∀x ∈ R, if x > 3, then x2 > 9.

Contrapositive: ∀x ∈ R,if x2 ≤ 9, then x ≤ 3.

Converse: ∀x ∈ R, if x2 > 9, then x > 3.

Inverse: ∀x ∈ R, if x ≤ 3, then x2 ≤ 9.