MAT2033 · Week 1 · propositional logic, predicates and quantifiers

Propositional logic, predicates and quantifiers

Connectives, truth tables, laws of logical equivalence, and translating and negating statements with ∀/∃. The first midterm question almost always comes from here.

propositionconnectiveconditionalbiconditionalexclusive ortruth tabletautologycontradictioncontingencylogical equivalenceDe Morgan's lawsconverseinversecontrapositivepredicatedomain of discourseuniversal quantifierexistential quantifiercounterexample

The language of discrete mathematics is logic. The symbols you learn this week will show up in every proof, every set question and every algorithm for the rest of the semester. The midterm questions on this topic are mechanical: build a truth table, show two statements are equivalent using the laws, translate an English sentence into symbols, negate a statement with quantifiers. There are few rules, but they have to be fully memorized.

Golden rules:

$p \to q$ is false only when $p$ is true and $q$ is false. All three other rows are true.
Never change the table order. With 3 variables, $p$ : TTTTFFFF, $q$ : TTFFTTFF, $r$ : TFTFTFTF.
Use a single law in each step and write its name. The instructor gives marks for the names.
“All” takes an arrow, “some” takes an and. $\forall x\,(A \to B)$ , $\exists x\,(A \land B)$ .
When negating, the quantifier flips: $\forall \leftrightarrow \exists$ , then negate the inside.

Propositions and connectives

Proposition: a declarative sentence that is either true (T) or false (F). “7 is prime” is a proposition (true). " $2 + 2 = 5$ " is a proposition (false). “Close the door” and " $x + 1 = 3$ " are not propositions: the first is a command, and in the second you cannot say true or false until $x$ is known.

You combine propositions with connectives:

Symbol	Name	When is it true?
$\lnot p$	negation (not)	when $p$ is false
$p \land q$	conjunction (and)	when both are true
$p \lor q$	disjunction (or, inclusive)	when at least one is true
$p \oplus q$	exclusive or (either … or …)	when exactly one is true
$p \to q$	conditional (if … then)	always, except $p = T, q = F$
$p \leftrightarrow q$	biconditional (if and only if)	when both have the same value

$p$	$q$	$p \to q$	$p \leftrightarrow q$	$p \oplus q$
T	T	T	T	F
T	F	F	F	T
F	T	T	F	T
F	F	T	T	F

Why is the conditional defined this way?

$p \to q$ works like a promise. The instructor says “If you hand in the homework, I will give you 10 points.” The instructor has lied in only one case: you handed it in ( $p = T$ ) and did not get the points ( $q = F$ ). If you did not hand it in ( $p = F$ ), the instructor has not broken the promise whatever they do, so the statement stays true. This is called “vacuously true”.

PITFALL · If $p$ is false, $p \to q$ is true. “From a false hypothesis anything follows.” The rows of the table where $p = F$ are automatically T. Knowing this cuts the work in half.

Translation patterns

These are the patterns the exam likes; all of them are expressed with $p \to q$ :

English	Symbol
if $p$ , then $q$ / $q$ if $p$ / $q$ whenever $p$	$p \to q$
$p$ only if $q$	$p \to q$
$p$ is sufficient for $q$ / $q$ is necessary for $p$	$p \to q$
$q$ unless $p$	$\lnot p \to q$ (that is, $p \lor q$ )
$p$ if and only if $q$ / $p$ iff $q$	$p \leftrightarrow q$

“Only if” is the most confused pattern. “You can enter the exam only if you have an ID” = if you entered the exam, you definitely have an ID: “entered” $\to$ “has ID”. Having an ID does not guarantee entering.

Converse, inverse, contrapositive

For $p \to q$ there are three relatives:

converse: $q \to p$
inverse: $\lnot p \to \lnot q$
contrapositive: $\lnot q \to \lnot p$

Only the contrapositive is equivalent to the original. The converse and the inverse are equivalent to each other, but not to the original. “If it rains, the ground gets wet” is true. The converse “if the ground is wet, it has rained” can be false (someone spilled water). The contrapositive “if the ground is dry, it has not rained” carries the same information as the original.

Building a truth table

Template:

Count the variables: with $n$ variables there are $2^n$ rows.
Fill the columns in the standard order (golden rule 2 above).
Break the expression down from the inside out, with a helper column for each part.
Look at the last column: all T means tautology, all F means contradiction, mixed means contingency.

Example. $(p \land \lnot r) \to (q \lor r)$

$p$	$q$	$r$	$\lnot r$	$p \land \lnot r$	$q \lor r$	result
T	T	T	F	F	T	T
T	T	F	T	T	T	T
T	F	T	F	F	T	T
T	F	F	T	T	F	F
F	T	T	F	F	T	T
F	T	F	T	F	T	T
F	F	T	F	F	T	T
F	F	F	T	F	F	T

The last column has one F and the rest T: contingency. Quick check: the arrow is F only when “left T, right F”. The rows where the left side is T ( $p=T, r=F$ ) are only rows 2 and 4; among them, only row 4 has the right side F.

Logical equivalence

$A$ and $B$ are equivalent if they take the same value in every row: $A \equiv B$ . In other words, $A \leftrightarrow B$ is a tautology. You can show it in two ways: a truth table or a chain of laws.

Law	Formula
Conditional	$p \to q \equiv \lnot p \lor q$
De Morgan	$\lnot(p \land q) \equiv \lnot p \lor \lnot q$ , $\lnot(p \lor q) \equiv \lnot p \land \lnot q$
Double negation	$\lnot\lnot p \equiv p$
Distributive	$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ , $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$
Negation	$p \lor \lnot p \equiv T$ , $p \land \lnot p \equiv F$
Identity	$p \land T \equiv p$ , $p \lor F \equiv p$
Domination	$p \lor T \equiv T$ , $p \land F \equiv F$
Idempotent	$p \lor p \equiv p$ , $p \land p \equiv p$
Commutative, associative	$p \lor q \equiv q \lor p$ , $(p \lor q) \lor r \equiv p \lor (q \lor r)$
Absorption	$p \lor (p \land q) \equiv p$ , $p \land (p \lor q) \equiv p$
Biconditional	$p \leftrightarrow q \equiv (p \to q) \land (q \to p)$

Chain strategy: first turn the arrows into $\lor$ with the conditional law, then push the $\lnot$ in front of parentheses inward with De Morgan, delete the $\lnot\lnot$ , and finally distribute and simplify.

Example 1. Show that $(p \to q) \lor (p \to r) \equiv p \to (q \lor r)$ .

(p → q) ∨ (p → r)
≡ (¬p ∨ q) ∨ (¬p ∨ r)        conditional law (twice)
≡ (¬p ∨ ¬p) ∨ (q ∨ r)        commutative and associative laws
≡ ¬p ∨ (q ∨ r)               idempotent law
≡ p → (q ∨ r)                conditional law   ∎

Example 2. Show that $\lnot(p \lor \lnot q) \lor (\lnot p \land \lnot q) \equiv \lnot p$ .

¬(p ∨ ¬q) ∨ (¬p ∧ ¬q)
≡ (¬p ∧ ¬¬q) ∨ (¬p ∧ ¬q)     De Morgan's law
≡ (¬p ∧ q) ∨ (¬p ∧ ¬q)       double negation law
≡ ¬p ∧ (q ∨ ¬q)              distributive law (common ¬p factored out)
≡ ¬p ∧ T                     negation law
≡ ¬p                         identity law   ∎

TIP · Don’t build a table to show NOT equivalent. Find a single row where the two sides differ. The sentence “For $p = F, q = T$ the left side is T and the right side is F” earns full marks.

Predicates and quantifiers

" $x > 3$ " is not a proposition, because $x$ is not known. This is called a predicate: $P(x)$ . Once you give $x$ a value it becomes a proposition: $P(5)$ is true, $P(1)$ is false. The set of values $x$ can take is called the domain (domain of discourse). Without a domain, the truth of a quantified statement cannot be determined.

Statement	Meaning	When is it true?	When is it false?
$\forall x\, P(x)$	$P(x)$ for every $x$	if every element of the domain satisfies it	if there is a single counterexample
$\exists x\, P(x)$	$P(x)$ for at least one $x$	if there is a single example	if no element satisfies it

Over a finite domain, quantifiers are big “and”s and “or”s. If the domain is $\{1, 2, 3\}$ , then $\forall x\,P(x) \equiv P(1) \land P(2) \land P(3)$ and $\exists x\,P(x) \equiv P(1) \lor P(2) \lor P(3)$ . That is why negating a quantifier is exactly De Morgan:

$\lnot \forall x\, P(x) \equiv \exists x\, \lnot P(x) \qquad \lnot \exists x\, P(x) \equiv \forall x\, \lnot P(x)$

If “Everyone passed” is false, it means “there is someone who did not pass”. It does not mean “nobody passed”.

Effect of the domain: $\exists x\,(2x = 1)$ is true over the reals ( $x = \tfrac12$ ) and false over the integers. Quantifiers bind before all connectives except $\lnot$ : $\forall x\, P(x) \land Q(x)$ means $(\forall x\, P(x)) \land Q(x)$ .

Translation: arrow or and?

The domain is all people, $A(x)$ : ” $x$ is an athlete”, $S(x)$ : ” $x$ is a student”.

Sentence	Correct	Wrong (why)
All athletes are students.	$\forall x\,(A(x) \to S(x))$	$\forall x\,(A(x) \land S(x))$ : says “everyone is an athlete and a student”
Some athletes are students.	$\exists x\,(A(x) \land S(x))$	$\exists x\,(A(x) \to S(x))$ : becomes automatically true because of someone who is not an athlete
No athlete is a student.	$\forall x\,(A(x) \to \lnot S(x))$
Not all athletes are students.	$\exists x\,(A(x) \land \lnot S(x))$

The trap in the second row comes from the vacuous truth of the conditional: a single person in the domain who is not an athlete makes $A(x) \to S(x)$ true, and the sentence says nothing.

Worked example: negation

“Every student who studies passes.” $S(x)$ : studies, $P(x)$ : passes.

∀x (S(x) → P(x))                    original
¬∀x (S(x) → P(x))                   negate
≡ ∃x ¬(S(x) → P(x))                 the quantifier flips
≡ ∃x (S(x) ∧ ¬P(x))                 ¬(a → b) ≡ a ∧ ¬b

In English: “There is a student who studies but does not pass.” Don’t leave the negation as “Not every student who studies passes”; the question usually asks for “no negation in front of a quantifier”.

Common mistakes

Wrong idea	The truth
If $p$ is false, $p \to q$ is false	It is true. The arrow is false only for $T \to F$
” $p$ only if $q$ ” = $q \to p$	$p \to q$
” $q$ unless $p$ ” = $p \to q$	$\lnot p \to q$
The converse is equivalent to the original	Only the contrapositive is equivalent
$\lnot(p \land q) \equiv \lnot p \land \lnot q$	$\lnot p \lor \lnot q$ ; $\land$ and $\lor$ swap
$\lnot \forall x\,P(x) \equiv \forall x\,\lnot P(x)$	$\exists x\,\lnot P(x)$ ; the quantifier flips too
“Some A are B” = $\exists x\,(A \to B)$	$\exists x\,(A \land B)$
“All A are B” = $\forall x\,(A \land B)$	$\forall x\,(A \to B)$
I tried a few examples, so $\forall$ is true	$\forall$ cannot be proved by examples; but a single counterexample breaks it
Answering without looking at the domain	The same statement can be true in $\mathbb{R}$ and false in $\mathbb{Z}$

Test yourself

Exam-style questions. Solve them on paper first, then reveal the answer.

Question 1easy

Let $p$ be true, $q$ be false and $r$ be true. Find the truth value of $(p \lor q) \to (\lnot r \land q)$ .

Show answer

False

Left side: $p \lor q = T \lor F = T$ . Right side: $\lnot r \land q = F \land F = F$ . The arrow is false only for $T \to F$ : $T \to F = F$ .

Question 2easy

Let $g$ : "you can use the gym", $s$ : "you are a student", $t$ : "you are staff". Write in symbols: "You can use the gym only if you are a student or staff."

Show answer

g \to (s \lor t)

The pattern "p only if q" means $p \to q$ : if you use the gym, you are definitely a student or staff. The conclusion is $s \lor t$ . Writing the reverse direction ( $(s \lor t) \to g$ ) is the classic mistake.

Question 3easy

Write the converse and the contrapositive of: "If $n$ is divisible by 6, then $n$ is even." Which of the two is always equivalent to the original?

Show answer

Converse: if n is even, then n is divisible by 6. Contrapositive: if n is not even, then n is not divisible by 6. The contrapositive.

$p$ : "6 divides n", $q$ : "n is even". The converse is $q \to p$ (the direction flips). The contrapositive is $\lnot q \to \lnot p$ (the direction flips and both parts are negated). Only the contrapositive is equivalent to the original. Here the converse is even false: $n = 4$ is even but not divisible by 6.

Question 4medium

Construct the truth table of $(p \to q) \to (q \to p)$ . Is it a tautology, a contradiction or a contingency?

Show answer

Contingency (false only when p = F, q = T)

The rows are TT, TF, FT, FF. $p \to q$ : T, F, T, T. $q \to p$ : T, T, F, T. Outer arrow: $T\to T = T$ , $F \to T = T$ , $T \to F = F$ , $T \to T = T$ . The last column is TTFT: it has both T and F, so it is a contingency.

Question 5medium

In how many rows of its truth table is $(p \oplus q) \land (q \lor r)$ true?

Show answer

There are 8 rows. $p \oplus q$ is T only when $p$ and $q$ differ: the rows TF* and FT* (4 rows). Among these, the ones where $q \lor r$ is also T are TFT ( $r=T$ ), FTT, FTF ( $q=T$ ). In row TFF, $q \lor r = F$ . Total: 3 rows.

Question 6medium

Using the laws of logic (name each law), show that $\lnot(p \to q) \to p$ is a tautology.

Show answer

It is equivalent to T, so it is a tautology.

$\lnot(p\to q) \to p \equiv \lnot\lnot(p \to q) \lor p$ (conditional law) $\equiv (p \to q) \lor p$ (double negation) $\equiv (\lnot p \lor q) \lor p$ (conditional law) $\equiv (p \lor \lnot p) \lor q$ (commutative + associative) $\equiv T \lor q$ (negation law) $\equiv T$ (domination law). One law per step, with its name.

Question 7hard

Are $p \to (q \to r)$ and $(p \to q) \to r$ logically equivalent? Justify.

Show answer

No. For p = F, q = F, r = F the first is T and the second is F.

A single row is enough to show they are not equivalent. When $p = F$ , $p \to (q \to r)$ is automatically T. On the other side $p \to q = T$ ; if we choose $r = F$ then $(p\to q) \to r = T \to F = F$ . The values differ, so they are not equivalent. (Check: the rows where they differ are FTF and FFF.)

Question 8easy

Let $Q(x)$ be " $x^2 - 5x + 6 = 0$ ", the domain being all integers. Find the truth values of $\exists x\, Q(x)$ and $\forall x\, Q(x)$ .

Show answer

∃x Q(x) is true, ∀x Q(x) is false

$x^2 - 5x + 6 = (x-2)(x-3)$ . $x = 2$ satisfies it, so $\exists x\,Q(x)$ is true (one example is enough). For $\forall$ a single counterexample is enough: for $x = 0$ , $6 \ne 0$ , so it is false.

Question 9medium

The domain is $\{1, 2, 3, 4\}$ . Determine the truth values of (a) $\forall x\,(x \text{ is odd} \to x^2 < 10)$ and (b) $\exists x\,(x \text{ is even} \land x^2 > 15)$ .

Show answer

(a) true, (b) true

(a) It is enough to look at the odd values (for even values the arrow is automatically T): $1^2 = 1 < 10$ , $3^2 = 9 < 10$ . All hold, so it is true.
(b) We need one even number whose square is greater than 15: $x = 4$ , $16 > 15$ . True.

Question 10medium

Let $M(x)$ : " $x$ misses practice" and $B(x)$ : " $x$ is benched", the domain being the players of a team. Express "Every player who misses practice is benched" in logic, then write its negation with no negation sign in front of a quantifier, and say it in English.

Show answer

∀x (M(x) → B(x)); negation: ∃x (M(x) ∧ ¬B(x)), "Some player misses practice but is not benched."

The pattern "Every ... who ..." needs $\forall$ and an arrow: $\forall x\,(M(x) \to B(x))$ . Negation: $\lnot\forall x\,(\dots) \equiv \exists x\,\lnot(M(x)\to B(x))$ , then $\lnot(a \to b) \equiv a \land \lnot b$ . The result is $\exists x\,(M(x) \land \lnot B(x))$ .

Question 11hard

Let $S(x)$ : " $x$ is a student" and $L(x)$ : " $x$ is lazy", the domain being all people. Express "No student is lazy" in two equivalent ways, one using $\forall$ and one using $\exists$ .

Show answer

∀x (S(x) → ¬L(x)) and ¬∃x (S(x) ∧ L(x))

"No student is lazy" = "there is no lazy student": $\lnot\exists x\,(S(x) \land L(x))$ . Pushing the negation inside gives $\forall x\,\lnot(S(x)\land L(x)) \equiv \forall x\,(\lnot S(x) \lor \lnot L(x)) \equiv \forall x\,(S(x) \to \lnot L(x))$ . Both say the same thing.

Question 12hard

Determine the truth value of $\forall x\,(x^2 \ge x)$ when the domain is (a) all real numbers, (b) all integers.

Show answer

(a) false, (b) true

(a) Counterexample $x = \tfrac12$ : $\tfrac14 \ge \tfrac12$ is false. One example breaks $\forall$ .
(b) $x^2 - x = x(x-1)$ . Over the integers, if $x \le 0$ both factors are $\le 0$ , and if $x \ge 1$ both are $\ge 0$ ; the product is always $\ge 0$ . True. Same sentence, different domain, different answer.

Verification: All truth tables, equivalences and quantifier truth values were checked by brute force with node (all rows / finite domain and a scan over -1000..1000) (verify/MAT2033/01.mjs).

Review card

p→q is F only for T→F. p↔q is T if they are the same. p⊕q is T if they differ. p→q ≡ ¬p∨q ¬(p→q) ≡ p∧¬q p↔q ≡ (p→q)∧(q→p) De Morgan: ¬(p∧q) ≡ ¬p∨¬q ¬(p∨q) ≡ ¬p∧¬q "p only if q" = p→q "q if p" = p→q "q unless p" = ¬p→q "p sufficient for q" = p→q "q necessary for p" = p→q converse q→p, inverse ¬p→¬q, contrapositive ¬q→¬p (only this one is equivalent) n variables → 2^n rows; p: TTTTFFFF, q: TTFFTTFF, r: TFTFTFTF all T tautology, all F contradiction, mixed contingency To show not equivalent: ONE row with different values is enough ∀: one counterexample makes it false. ∃: one example makes it true. ¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x) "All A are B" = ∀x (A(x)→B(x)) "Some A are B" = ∃x (A(x)∧B(x)) Change the domain, change the answer: ∃x(2x=1) is T in R, F in Z