Discrete Mathematics — Lecture

Summary
Lecture 1 & 2

Propositional Logic — Predicates & Quantifiers

All definitions + every example and exercise from the lecture, gathered in one
place

1
Quick Index

Part 1: Propositional Logic — definitions, tables, and examples

Part 2: Logical Equivalences, Tautology/Contradiction, Boolean Circuits

Part 3: Predicates & Quantifiers

Part 4: Formalizing English Sentences, Google Boolean Search, and Knights &
Knaves Puzzles

🟧 Yellow box = a question/exercise that appeared in the lecture 🟩 Green box =

the answer as given in the lecture 🟦 Blue box = definition/rule

2
 Part 1: Propositional Logic

1. Objectives

• Decide if a sentence is a proposition, and evaluate its truth value.

• Construct the truth table of a compound proposition.
• Translate compound propositions (negations, conjunctions, disjunctions,
implications, biconditionals) back and forth between English and logical symbols.
• Write formal expressions of English statements (including system specifications),
and check if they are consistent.

2. Propositions

Definition: A proposition (or statement) is a descriptive sentence that is either true

or false (depending on the world it describes).

Question Which of the following are statements (propositions)?

a) 1 + 1 = 3
b) x + 1 = 2
c) What time is it?
d) It's 9:00 am.
e) Read this carefully.

Answer Sentences (a) and (d) are propositions. Sentences (c) and (e) are not

propositions because they are not descriptive sentences. Sentence (b) is not a
proposition because its truth value depends on the variable x.

3. Compound Propositions and Basic Logical Connectives

Definition: A logical connective is a word (or more) connecting one or more

propositions, forming a compound proposition. The truth value of the compound
proposition depends only on the truth values of the primitive propositions.

Connective Symbol Reading

Negation ¬p "not p"

3
 Conjunction p∧q "p and q"

Inclusive Disjunction p∨q "p or q (or both)"

Exclusive Disjunction p⊕q "either p or q, but not both"

Question Express the compound proposition: "I am smart but you are not."

using p: I am smart, q: You are smart.

Answer p ∧ ¬q

Truth Table of the Basic Connectives

p q ¬p p∧q p∨q p⊕q

0 0 1 0 0 0

0 1 1 0 1 1

1 0 0 0 1 1

1 1 0 1 1 0

4. Conditional Statements

Definition: p → q is read "p implies q" or "If p, then q", and is called an implication
or conditional statement. p is the hypothesis, q is the conclusion. p → q is false
exactly when p is true and q is false.

p q p→q

0 0 1

0 1 1

1 0 0

1 1 1

Question p: "I will get 95% in BSC 225", q: "I will get an A in BSC 225".

Determine the truth value of p → q for all possible truth values of p and q.
(Solved by the truth table above, applied with this p and q)

4
English Phrasings for p → q
• "if p, then q" / "p implies q"
• "if p, q" / "p only if q"
• "p is sufficient for q" / "a sufficient condition for q is p"
• "q if p" / "q whenever p"
• "q when p" / "q is necessary for p"
• "a necessary condition for p is q" / "q follows from p"
• "q unless ¬p"

Question S: "It's sunny", G: "I'm going out". Express in symbols:

1) "I go out, whenever it's sunny."

2) "I'm not going out, unless it's sunny."

Answer 1) S → G

2) Means: if I'm going out, then it must be sunny → G → S (the contrapositive of

S → G)

5. The Biconditional

Definition: p ↔ q is shorthand for (p→q) ∧ (q→p), read "p if and only if q" or "p is
necessary and sufficient for q".

p q p→q q→p p↔q

0 0 1 1 1

0 1 1 0 0

1 0 0 1 0

1 1 1 1 1

6. Truth Tables of Compound Propositions

Question (worked example) Construct the truth table of (p ∨ q) → (p ∧ q).

Answer

5
 p q ¬q p∨q p∧q (p∨q)→(p∧q)

0 0 1 0 0 1

0 1 0 1 0 0

1 0 1 1 0 0

1 1 0 1 1 1

Exercise Construct the truth tables for:

(a) p → (q ∨ r)
(b) (p ∨ q) ⊕ r
(c) p ∧ q → r

Answer (a)

p q r q∨r p→(q∨r)

0 0 0 0 1

0 0 1 1 1

0 1 0 1 1

0 1 1 1 1

1 0 0 0 0

1 0 1 1 1

1 1 0 1 1

1 1 1 1 1

Answer (b)

p q r p∨q (p∨q)⊕r

0 0 0 0 0

0 0 1 0 1

0 1 0 1 1

0 1 1 1 0

1 0 0 1 1

6
 1 0 1 1 0

1 1 0 1 1

1 1 1 1 0

Answer (c) Note: → and ↔ have lower precedence than ∧ and ∨, so p ∧ q → r is

read as (p ∧ q) → r.

p q r p∧q (p∧q)→r

0 0 0 0 1

0 0 1 0 1

0 1 0 0 1

0 1 1 0 1

1 0 0 0 1

1 0 1 0 1

1 1 0 1 0

1 1 1 1 1

7. Specification Consistency

Question Are the following system specifications consistent (can they all be

true at the same time)?

- Whenever the system software is being upgraded, users cannot access the file
system.
- If users can access the file system, then they can save new files.
- If users cannot save new files, then the system software is not being upgraded.

Answer Let p = "the system software is being upgraded", q = "users can

access the file system", r = "users can save new files". The sentences translate
to: p→q, q→r, r→p. Building the full truth table shows at least one assignment
(e.g. all false) makes all three true simultaneously, so the system is
consistent.

7
 Part 2: Logical Equivalences and Boolean
Circuits

1. Objectives

• Decide (with proof) if a proposition is a tautology, a contradiction, or a

contingency.
• Find the converse, contrapositive, and inverse of a conditional proposition.
• Decide (with proof) if two propositions are logically equivalent using truth tables,
known equivalences, or a logical argument.
• Construct a compound proposition realizing a given truth table.

2. Famous Equivalences 1

Idempotency: p∧p ≡ p and p∨p ≡ p

Commutativity: p∧q ≡ q∧p, p∨q ≡ q∨p
Associativity: p∨(q∨r) ≡ (p∨q)∨r, p∧(q∧r) ≡ (p∧q)∧r
Distributivity: p∧(q∨r) ≡ (p∧q)∨(p∧r), p∨(q∧r) ≡ (p∨q)∧(p∨r)

Question Construct the truth table of (p→q) ↔ (¬p∨q).

Answer The value is always "True" — hence it is a tautology.

3. Tautology, Contradiction, and Equivalence

Definition: Tautology = always true. Contradiction = always false. Contingency =

sometimes true, sometimes false. p ≡ q means p↔q is a tautology.

Question Classify the following as a tautology, contradiction, or contingency:

1) (p→q) ↔ (¬p∨q)
2) Y ≡ ((p→q)∨(q∨r)) ∧ (¬(p→q)∧¬(q∨r))
3) (p→q) → (q→p)

8
 Answer 1) Tautology (always True).

2) Contradiction (always False) — can also be shown directly via the Negation
Law H∧¬H ≡ F.
3) Contingency (neither a tautology nor a contradiction).

Exercise Which of the following are valid equivalences?

1) (p→q) ≡ (¬p∨q)
2) (p→q) ≡ (¬q→¬p)
3) (p→p) ≡ ¬p

4. Converse, Inverse, and Contrapositive

Converse of p→q is q→p

Inverse of p→q is ¬p→¬q
Contrapositive of p→q is ¬q→¬p

Exercise Which of the following are equivalent? p→q , q→p , ¬q→¬p , ¬p→¬q

(Expected answer: p→q is equivalent to ¬q→¬p; q→p is equivalent to ¬p→¬q)

5. Famous Equivalences 2

Negation: ¬(¬p) ≡ p, p∧¬p ≡ F, p∨¬p ≡ T

De Morgan's Laws: ¬(p∧q) ≡ ¬p∨¬q , ¬(p∨q) ≡ ¬p∧¬q
Conditional Law: p→q ≡ ¬p∨q
Truth: p∨T ≡ T, p∧T ≡ p
Falsity: p∧F ≡ F, p∨F ≡ p

Question Show De Morgan's Law: ¬(p∧q) ≡ ¬p∨¬q.

Answer By truth table, both sides have the same values in every case, so they

are equivalent.

Question Using a logical argument (not a truth table), show that: p∧(q∨r) ≡

(p∧q)∨(p∧r).

9
 Hint: consider the two cases p is true and p is false.

Question Construct a compound proposition s realizing the following truth

table:

p q r s

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 1

Answer s = (¬p∧¬q∧r) ∨ (¬p∧q∧¬r) ∨ (p∧¬q∧¬r) ∨ (p∧q∧r)

Rule: for every row where s = 1, AND the variables (negated where 0), then OR all these
terms together.

6. Boolean Circuits

Question 1 Construct a Boolean circuit (using NOT, OR, and AND gates) that

produces the output (p∨q)∧¬r from input bits p, q, and r.

Question 2 Build a digital circuit that produces the output (p∧r) ∨ (¬p∧(q∨r))

from input bits p, q, and r.

Question 3 Determine the output for the given combinatorial circuit, then

construct the truth table of the output Y.

Answer (Question 3) The output Y = ¬(A∧B) ∨ (¬A∧C)

A B C Y

10
0 0 0 1

0 0 1 1

0 1 0 1

0 1 1 1

1 0 0 1

1 0 1 1

1 1 0 1

1 1 1 0

11
 Part 3: Predicates & Quantifiers

1. Motivation for Predicate Calculus

Argument 1 i) Socrates is a man. ii) All men are mortal. iii) Therefore, Socrates

is mortal.

Idea This is "Universal Instantiation": from the general rule "all men are

mortal" we move to a specific case (Socrates is a man ⇒ Socrates is mortal). It's

classically known as the syllogism "Barbara" in Aristotelian logic.

Argument 2 3 is a factor of 21. Therefore, 21 has at least one factor.

Idea This is "Existential Generalization": from a specific witness (3) we

conclude ∃x. Propositional logic alone cannot express properties or relations of

individuals, nor existence claims — hence the need for predicate logic
(predicates + quantifiers).

2. Predicates

Definition: A predicate (or propositional function) is a descriptive sentence that

may contain variables, and becomes a statement (true/false) once all free variables
are replaced by particular values.

Question For the predicates P(x): x²-3x+7=0, M(x): "x is a man", Q(x,y): x≤y —

evaluate P(1), M(Socrates), Q(2,2).

Compound Predicates

Question Using L(x,y): "x < y" (x, y range over real numbers), express as

compound predicates: |x| < 2 and |x| > 2.

12
 Answer |x|<2 ≡ L(-2,x) ∧ L(x,2)

|x|>2 ≡ L(x,-2) ∨ L(2,x)

3. Quantifiers

Universal: ∀x P(x) means "For all x in U, P(x)"

Existential: ∃x P(x) means "There exists an x in U such that P(x)"

Question Let U = {1,2,3,...}, P(x): "x is prime", D(x): "x is odd", L(x,y): "x<y".

Express in English and determine the truth values of:

1) ∃x L(x,1)
2) ∀x [P(x) ∧ D(x)]
3) ∀x [P(x) ∨ ¬D(x)]

Answer 1) False — there is no natural number less than 1.

2) False — 2 is prime but not odd, and 4 is neither prime nor odd
(counterexamples).
3) False — non-prime even numbers (4, 6, 8...) are counterexamples.

Question Express "All men are mortal" using Man(x) and Mortal(x).

Answer ∀x [Man(x) → Mortal(x)]

Question Express "Some man is immortal" using the same predicates.

Answer ∃x [Man(x) ∧ ¬Mortal(x)]

4. Predicate Equivalences

De Morgan (quantifiers): ¬(∀x P(x)) ≡ ∃x ¬P(x) , ¬(∃x P(x)) ≡ ∀x ¬P(x)

Associativity: ∀x(P(x)∧Q(x)) ≡ (∀xP(x))∧(∀xQ(x))

13
 Question Show the equivalence: ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x))

Answer (step by step) ¬∀x(P(x)→Q(x))

≡ ∃x ¬(P(x)→Q(x)) (De Morgan)

≡ ∃x ¬(¬P(x)∨Q(x)) (Conditional Law)
≡ ∃x (¬¬P(x) ∧ ¬Q(x)) (De Morgan)
≡ ∃x (P(x) ∧ ¬Q(x)) (Negation)

Question S1: "Nothing is impossible." S2: "Some student in BSC 225 will get an

A."
1) Express S1 and S2 using predicates and quantifiers.
2) Negate S1 and S2, and simplify using De Morgan's laws.

Answer S1: ∀x ¬I(x) — "Everything is possible".

S2: ∃x [S(x)∧A(x)]
¬S1 ≡ ∃x I(x) — "Something is impossible".
¬S2 ≡ ∀x [¬S(x)∨¬A(x)] — "No student in BSC 225 will get an A".

Question Let U = {1,2,3,...}, P(x): "x is prime", L(x,y): "x<y". Express in English

and determine the truth values of:

1) ∀x ∃y L(x,y)
2) ∃y ∀x L(x,y)
3) ∀x ∃y [P(y) ∧ L(x,y)]

Answer 1) True — every natural number has a larger one (take y=x+1).

2) False — there is no largest natural number.

3) True — by Euclid's theorem, there are infinitely many primes, so for every x
there's a larger prime.

Question Let U be the set of all people, L(x,y): "x loves y". S1: "Everyone loves

someone", S2: "Someone loves everyone".

1) Express S1 and S2.
2) Negate S1 and S2 and simplify so no quantifier is in the scope of a negation.

14
 Answer S1: ∀x∃y L(x,y) , S2: ∃x∀y L(x,y)

¬S1 ≡ ∃x∀y ¬L(x,y) — "Someone loves no one".

¬S2 ≡ ∀x∃y ¬L(x,y) — "Everyone fails to love someone".

Question Let U be the real numbers, P(x,y): "x+y=0". Determine the truth

values of:
1) ∀x∃y P(x,y)
2) ∃y∀x P(x,y)
3) ∀x∀y [P(x,y)→P(y,x)]
4) ∃x∃y [P(x,y)∧¬P(y,x)]

Answer 1) True — for every x, take y = -x.

2) False — no single y works for every x.

4) False — the expression inside the quantifiers becomes a contradiction
(Q∧¬Q).

Question Let U be the real numbers, Q(x,y,z): "xy=z". Find the truth values of:

∀x∀y∃z Q(x,y,z) , ∀x∃z∀y Q(x,y,z) , ∃z∀x Q(x,x,z) , ∀x∃z Q(x,z,z)

5. Nested Quantifiers

Commutativity: ∀x∀y P(x,y) ≡ ∀y∀x P(x,y) , ∃x∃y P(x,y) ≡ ∃y∃x P(x,y)

Mixed: ∃y∀x P(x,y) and ∀x∃y P(x,y) are not equivalent, but ∃y∀x P(x,y) → ∀x∃y
P(x,y) is always a valid statement.

Question Let F(x,y): "x and y are friends" (U = all people).

1) Express in English: ∃x∀y F(x,y) and ∀x∃y F(x,y).

2) Write a predicate statement expressing: "Every person has exactly one
friend."

Question (sorted variables) Let x range over CIC students and y over CIC courses,

T(x,y): "x is registered in y". Express in English:

∀x∃y T(x,y) , ∃y∀x T(x,y) , ∀x∀y T(x,y)

15
 Part 4: Formalizing Sentences, Google
Search, and Logic Puzzles

1. Formalizing an English Statement in Propositional Logic

Question Using propositional logic, express: "To use the wireless network in the

airport you must pay the daily fee unless you are a subscriber to the service."

Answer Let p: "you can use the wireless network", q: "you paid the daily fee", r:

"you are a subscriber". The sentence translates to: p → (q ∨ r)

2. Boolean Logic in Google Searches

Example To find pages about universities in New Mexico: NEW AND MEXICO

AND UNIVERSITIES. To find pages about universities in New Mexico or Arizona:

(NEW AND MEXICO OR ARIZONA) AND UNIVERSITIES (AND has precedence over
OR). To find pages about universities in Mexico (not New Mexico): (MEXICO AND
UNIVERSITIES) NOT NEW — in Google, NOT is replaced by the "-" symbol.

3. Knights & Knaves Puzzles

Logic Puzzle 1 An island has knights (who always tell the truth) and knaves (who

always lie). A says: "The two of us (A and B) are knaves." Find out who is the
knight and who is the knave.

Answer If A is a knight ⇒ A's statement is true ⇒ A is a knave (contradiction).

So A is a knave ⇒ A's statement is false ⇒ not both are knaves ⇒ therefore B is

a knight and A is a knave.

Logic Puzzle 2 A says: "B is a knight." B says: "The two of us are opposite types."

Who are A and B?

16
 Answer If A is a knight ⇒ B is a knight (since A tells the truth) ⇒ B's statement

must then be true, but B claimed they are opposite types while they're the same
type (contradiction). So A is a knave ⇒ A's statement is false ⇒ B is also a knave.
Result: both A and B are knaves.

Logic Puzzle 3 An island has A, B, and C: exactly one knight, one knave, and one

spy (who may or may not lie). A: "B is a knight." B: "C is a knave." C: "A is a spy."
Find out who is the knight, knave, and spy.
(The lecture poses this question without walking through the full solution.)

A Logical Paradox A says: "B is a knave." B says: "A is a knight." Can this

situation actually occur?

Answer If A is a knight ⇒ B is a knave ⇒ B's statement ("A is a knight") should

then be false, but it's actually true (contradiction).

If A is a knave ⇒ B is a knight ⇒ B's statement ("A is a knight") should then be
true, but A is a knave (contradiction).
Conclusion: both possibilities are impossible — the statements are logically
inconsistent and cannot occur on this island.

17