COMP233 · Chapter 2 Interactive Companion

The Logic of Compound Statements

Propositional logic, truth tables, equivalence, and argument validity.
Back to COMP233

About this chapter

Propositional logic is the grammar of mathematical reasoning. It gives precise rules for combining true/false statements with ∼ ∧ ∨ → ↔, deciding when two compound statements have the same truth value, and testing whether an argument's form forces its conclusion to follow from its premises.

Where it is used. These rules are the foundation for every later chapter: predicates and quantifiers (Ch 3), proofs (Ch 4), set theory (Ch 6), and induction (Ch 5) all stand on the logic you build here. They also map directly onto programming (if/else, boolean expressions), digital circuits (AND/OR/NOT gates), and database queries (WHERE clauses).

Section 2.1Logical form and logical equivalence

A statement (or proposition) is a sentence that is either true or false, but not both. Statements built from simple statements joined by connectives (∼ ∧ ∨ → ↔) are compound statements, the focus of this chapter.

Statements:

  • "2 + 2 = 4" → true
  • "It is raining in Nablus right now" → either true or false
  • "The number 17 is prime" → true

Not statements:

  • "What time is it?" (a question)
  • "Close the door." (a command)
  • "x + 1 = 5" (depends on x; this is a predicate, treated in Chapter 3)

In propositional logic we label statements with letters like p, q, r and combine them with the connectives below.

2.1.1 The basic connectives

Toggle the variables and watch each connective evaluate. Symbols come from the slides. Hover any term for the Arabic name.
  • ∼p Negation, flips a single value.
  • p ∧ q Conjunction, true only when both inputs are true.
  • p ∨ q Disjunction, true when at least one is true (inclusive or).
  • p ⊕ q Exclusive or in slides · optional, true when exactly one of p, q is true. Equivalent to (p ∨ q) ∧ ∼(p ∧ q).

2.1.2 Truth tables

A truth table lists every possible combination of truth values for the inputs and shows the result for each row. With n variables there are 2n rows. Enter any formula below, the table builds each sub-expression as its own column, so you can read the construction step by step.
click to insert
Quick presets:

Try this. Build the tables for p ∧ (q ∨ r) and (p ∧ q) ∨ (p ∧ r). Identical columns: that is the distributive law, and it is the first example of logical equivalence, the topic of the next widget.

2.1.3 Logical equivalence (التكافؤ المنطقي)

Two statement forms are logically equivalent if they have the same truth value in every row of the truth table. We write P ≡ Q. Enter two formulas. The companion builds both truth tables side by side, marks any differing row, and reports the verdict.
Left:
Right:
Equivalence pairs to try:

2.1.4 De Morgan's laws (قوانين دي مورغان)

Two of the most useful equivalences in this course. They appear constantly in proofs, set theory, programming, and circuit design.
$$\sim(p \wedge q) \;\equiv\; \sim p \vee \sim q$$ $$\sim(p \vee q) \;\equiv\; \sim p \wedge \sim q$$

Memory aid. "Break the bar, change the sign." When ∼ moves inside the parentheses, ∧ flips to ∨ (and vice versa), and each part gets negated.

Verify by typing ∼(p ∧ q) and ∼p ∨ ∼q into the equivalence checker above.

Application: filtering student records

A student qualifies when their grade reaches the pass threshold and their attendance reaches the minimum. Drag the sliders. The qualifies column applies the rule directly; the ∼ qualifies (DM) column applies its De Morgan negation. The two should always agree (one is the negation of the other).

Name Grade Attend. passes att_ok qualifies ∼ qualifies (DM)
The qualifies column and the negation of the ∼ qualifies (DM) column always agree, in every row, for every threshold setting.

2.1.5 Tautology and contradiction

  • A tautology is a statement form that is true in every row of its truth table. Example: p ∨ ∼p.
  • A contradiction is false in every row. Example: p ∧ ∼p.
  • Anything else is a contingency, sometimes true, sometimes false.
Try:

Practice exercises · Section 2.1

Adapted from Epp Section 2.1, suggested questions: 15, 24, 33.
Exercise 2.1.A
Use the equivalence checker (or build the truth table by hand) to determine whether the following pair is logically equivalent: $p \wedge (q \vee r) \;\;\text{ and }\;\; (p \wedge q) \vee r$.

They are not equivalent. Build both truth tables side by side and look at the row where they disagree:

The row p = F, q = F, r = T makes the left side F and the right side T. That single mismatch is enough to fail equivalence.

Lesson. ∧ does not distribute the way you might guess. The correct distributive law is p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r), note the second ∧ on the right. Check it below; every row matches:

Exercise 2.1.B
Write the negation of: "It is hot and humid." Then write the negation of: "It is hot or humid." Which De Morgan law did you use for each?

Let h = "it is hot" and m = "it is humid".

(i) Negation of h ∧ m:
∼(h ∧ m) ≡ ∼h ∨ ∼m   (first De Morgan law)
In words: "It is not hot, or it is not humid."

(ii) Negation of h ∨ m:
∼(h ∨ m) ≡ ∼h ∧ ∼m   (second De Morgan law)
In words: "It is not hot, and it is not humid."

Watch the connective flip: ∧ becomes ∨ in (i), and ∨ becomes ∧ in (ii).

Exercise 2.1.C
Classify each of the following as a tautology, contradiction, or contingency. Use the classifier above or work by hand.
  1. (p ∧ q) ∨ (∼p ∨ ∼q)
  2. p ∧ (∼p ∨ q)
  3. ∼(p ∧ ∼p)

(1) (p ∧ q) ∨ (∼p ∨ ∼q). By De Morgan, ∼p ∨ ∼q ≡ ∼(p ∧ q), so the form is X ∨ ∼X, always true. The truth table confirms:

(2) p ∧ (∼p ∨ q). Sometimes T, sometimes F:

(3) ∼(p ∧ ∼p). p ∧ ∼p is a contradiction (always false), so its negation is always true:

Exercise 2.1.D
Use the equivalence laws (Theorem 2.1.1) to simplify ∼(∼p ∧ q) ∧ (p ∨ q). The expected end result is p.

Each step replaces a sub-expression with an equivalent one from Theorem 2.1.1:

∼(∼p ∧ q) ∧ (p ∨ q)
≡ (∼(∼p) ∨ ∼q) ∧ (p ∨ q)    by De Morgan's law
≡ (p ∨ ∼q) ∧ (p ∨ q)         by double negative
≡ p ∨ (∼q ∧ q)               by the distributive law
≡ p ∨ (q ∧ ∼q)               by commutativity for ∧
≡ p ∨ c                       by the negation law (q ∧ ∼q is a contradiction)
≡ p                           by the identity law (p ∨ c ≡ p)

Verify the start/end equivalence with the checker:

Exercise 2.1.E in slides · optional
Build the truth table for (p ∧ ∼q) ∨ (∼p ∧ q). What standard connective does it equal?

This form is true precisely when exactly one of p, q is true. That is the exclusive or p ⊕ q:

In other words: p ⊕ q ≡ (p ∧ ∼q) ∨ (∼p ∧ q). This is one of the standard equivalent forms for XOR (the slides give the other: (p ∨ q) ∧ ∼(p ∧ q)).

Section 2.2Conditional statements

The conditional (→) p → q (read "if p then q") is the workhorse of mathematical reasoning. The only way p → q is false is when p is true but q is false. The rows where p is false make the conditional vacuously true, a topic revisited in 3.2.

Conditional sandbox

Toggle the inputs. Notice when the conditional is vacuously true.

2.2.1 Contrapositive, converse, inverse

Given the conditional p → q, three related forms come up constantly:
  • Contrapositive: ∼q → ∼p. Equivalent to the original.
  • Converse: q → p. Not equivalent.
  • Inverse: ∼p → ∼q. Not equivalent.
The biggest student trap is mixing up contrapositive with converse. The truth table below settles it.

What the columns show.

  • p → q vs ∼q → ∼p  →  identical in every row  →  equivalent (the contrapositive).
  • p → q vs q → p  →  differ in row F | T  →  not equivalent (converse).
  • p → q vs ∼p → ∼q  →  differ in row F | T  →  not equivalent (inverse).
  • Also: q → p ≡ ∼p → ∼q, converse and inverse are equivalent to each other.

Worked example (Epp Section 2.2)

"If it is raining, then the ground is wet."

  • Original: rain → wet
  • Contrapositive: ∼wet → ∼rain,"If the ground is not wet, then it is not raining." ✓ logically the same.
  • Converse: wet → rain,"If the ground is wet, then it is raining." ✗ could be wet from a sprinkler.
  • Inverse: ∼rain → ∼wet,"If it is not raining, then the ground is not wet." ✗ same flaw as converse.

2.2.2 Biconditional

The biconditional (↔) p ↔ q (read "p if and only if q", abbreviated iff) is true exactly when p and q have the same truth value.
$$p \leftrightarrow q \;\equiv\; (p \to q) \wedge (q \to p)$$

Identical columns → equivalent. The biconditional is exactly the conjunction of the two one-way conditionals.

2.2.3 Necessary and sufficient conditions

These two phrases are crucial and easy to swap by mistake.
  • "p is sufficient for q" means p → q. (Having p is enough to guarantee q.)
  • "p is necessary for q" means q → p. (Without p, q cannot happen.)
  • "p only if q" means p → q. slide 15 of Ch 2.2 · optional
  • "p if q" means q → p. slide 15 of Ch 2.2 · optional

Pick a statement to see its symbolic translation:

Practice exercises · Section 2.2

Adapted from Epp Section 2.2, suggested questions: 14(a), 17, 25.
Exercise 2.2.A
Write the contrapositive, converse, and inverse of the statement: "If today is Friday, then I have an exam."

Let p = "today is Friday", q = "I have an exam".

Original (p → q): If today is Friday, then I have an exam.

Contrapositive (∼q → ∼p): "If I do not have an exam, then today is not Friday."  ✓ logically equivalent.

Converse (q → p): "If I have an exam, then today is Friday."  ✗ not equivalent; exams happen on other days too.

Inverse (∼p → ∼q): "If today is not Friday, then I do not have an exam."  ✗ not equivalent; same flaw as converse.

Exercise 2.2.B
Rewrite each statement in the form if p then q:
  1. "Being divisible by 6 is sufficient for being divisible by 2."
  2. "A polygon is a triangle only if it has exactly 3 sides."
  3. "Compiling is necessary for running the program."

(1) "p sufficient for q" translates to p → q:
"If a number is divisible by 6, then it is divisible by 2."

(2) "p only if q" translates to p → q:
"If a polygon is a triangle, then it has exactly 3 sides."

(3) "p necessary for q" translates to q → p:
"If the program runs, then it has been compiled."

Exercise 2.2.C
Use the equivalence checker (in section 2.1.3) or a hand truth table to verify: $p \to q \;\equiv\; \sim p \vee q$. Why is this useful?

Build both truth tables. Identical columns confirm equivalence:

How we use it. This is the bridge from conditional reasoning to the basic connectives. It lets us apply De Morgan to negate conditionals:
∼(p → q) ≡ ∼(∼p ∨ q) ≡ p ∧ ∼q

So the negation of "if p then q" is "p and not q", used constantly in proofs.

Exercise 2.2.D
Write the negation of: "If Sara studies hard, then she passes the exam." (Hint: use ∼(p → q) ≡ p ∧ ∼q.)

Let p = "Sara studies hard", q = "Sara passes the exam".

Original: p → q. Negation: ∼(p → q) ≡ p ∧ ∼q.

In words: "Sara studies hard and she does not pass the exam."

Confirm with the equivalence checker:

Caution. A common mistake is to negate as "If Sara studies hard, then she does not pass". That has the wrong logical shape, it is still an "if … then" statement, not its negation.

Exercise 2.2.E
Let p = "you get a diploma" and q = "you pass all exams". Translate each into symbolic form:
  1. "You get a diploma if you pass all exams."
  2. "You get a diploma only if you pass all exams."
  3. "You get a diploma if and only if you pass all exams."

(1) "p if q",if introduces the hypothesis, so q is the hypothesis: q → p. (Passing is sufficient for the diploma.)

(2) "p only if q", p cannot happen without q, so p → q. (Passing is necessary for the diploma.) Equivalently ∼q → ∼p, no passing means no diploma.

(3) "p if and only if q", both directions: p ↔ q ≡ (q → p) ∧ (p → q).

Notice the arrows in (1) and (2) point in opposite directions. That is the most common confusion in Section 2.2.

Section 2.3Valid arguments and rules of inference

An argument is a sequence of statements: some premises followed by a conclusion.

An argument form is valid when, in every row of the truth table where all premises are true, the conclusion is also true. If there is even one row where every premise is true but the conclusion is false, the argument form is invalid.

Important. Validity is about form, not about whether the premises happen to be true. An argument can be valid with false premises and an absurd conclusion. What we check is whether the form preserves truth.

2.3.1 The argument validity checker

Pick an argument form. The checker builds the truth table, highlights the critical rows (those where every premise is true), and reports the verdict. Sub-expression columns are shown so you can see how the premises and conclusion get built.

Argument:

2.3.2 Standard valid forms (rules of inference)

The nine rules of inference from the lecture slides. Each has been proven valid once and is then used as a building block in larger arguments (a chain of rules replaces a truth table that doubles in size with every variable). c denotes any contradiction. Two classic fallacies follow.

1. Modus Ponens

$p \to q,\;\; p \;\therefore\; q$
"If p then q. p. Therefore q."

2. Modus Tollens

$p \to q,\;\; \sim\!q \;\therefore\; \sim\!p$
"If p then q. Not q. Therefore not p."

3. Generalization

$p \;\therefore\; p \vee q$
Any truth implies a disjunction that contains it.

4. Specialization

$p \wedge q \;\therefore\; p$
From a conjunction, extract either conjunct.

5. Conjunction

$p,\;\; q \;\therefore\; p \wedge q$
From two truths, conclude their combination.

6. Elimination

$p \vee q,\;\; \sim\!p \;\therefore\; q$
"p or q. Not p. Therefore q."

7. Transitivity

$p \to q,\;\; q \to r \;\therefore\; p \to r$
"If p then q. If q then r. Therefore if p then r."

8. Division into cases

$p \vee q,\;\; p \to r,\;\; q \to r \;\therefore\; r$
If r follows from either branch of a disjunction, conclude r.

9. Contradiction rule

$\sim\!p \to c \;\therefore\; p$
If assuming ∼p leads to a contradiction c, conclude p. (Proof by contradiction.)

Converse Error (INVALID)

$p \to q,\;\; q \;\therefore\; p$
Affirming the consequent. Confuses p → q with its converse.

Inverse Error (INVALID)

$p \to q,\;\; \sim\!p \;\therefore\; \sim\!q$
Denying the antecedent. Confuses p → q with its inverse.

Both fallacies are invalid, verify each in the checker above.

Practice exercises · Section 2.3

Adapted from Epp Section 2.3, suggested questions: 9, 11, 13.
Exercise 2.3.A
Determine whether the following argument is valid, and identify it by name.
If today is a holiday, the library is closed.
Today is not a holiday.
∴ The library is not closed.

Let p = "today is a holiday", q = "the library is closed".

Form: p → q,  ∼p  ∴ ∼q. This is the inverse error,invalid. The truth table shows the breakage:

Read the red row: p = F, q = T. Both premises are true (p → q is vacuously true; ∼p is true) but the conclusion ∼q is false. The library could be closed for other reasons (Sunday, renovation),the form does not rule that out.

Verify by selecting "Inverse error" in the checker above.

Exercise 2.3.B
Is the following argument valid?
If 2 + 2 = 5, then 1 = 0.
2 + 2 ≠ 5.
∴ 1 ≠ 0.

Let p = "2 + 2 = 5", q = "1 = 0". Form: p → q,  ∼p  ∴ ∼q, the inverse error again. Invalid.

Even though the conclusion happens to be true in the real world (1 ≠ 0 is correct), validity is about form, not content. The form does not force the conclusion.

Key lesson. An argument can have a true conclusion and still be invalid. Validity asks: does the form guarantee the conclusion is true whenever the premises are?

Exercise 2.3.C
Use a chain of valid argument forms to justify the following:
If Ahmad is in COMP233, then he studies discrete math.
If Ahmad studies discrete math, then he learns about proofs.
Ahmad is in COMP233.
∴ Ahmad learns about proofs.

Let c = "Ahmad is in COMP233", d = "Ahmad studies discrete math", p = "Ahmad learns about proofs".

Premises:
(1) c → d
(2) d → p
(3) c

Step 1. Apply Transitivity to (1) and (2):
c → d,  d → p  ∴ c → p

Step 2. Apply Modus Ponens to the result and (3):
c → p,  c  ∴ p

Therefore p,"Ahmad learns about proofs". ✓ Valid.

Exercise 2.3.D
Determine whether the following argument is valid, and identify it by name.
If today is Friday, then today is a holiday.
Today is not a holiday.
∴ Today is not Friday.

Let p = "today is Friday", q = "today is a holiday". Form: p → q,  ∼q  ∴ ∼p. This is Modus Tollens (Rule 2), valid.

Read the yellow row: the single critical row (both premises T) also makes the conclusion T. The form preserves truth.

Exercise 2.3.E (worked chain)
From the slides (Epp example 2.3.8). Where are the glasses?
(a) If I was reading in the kitchen, then my glasses are on the kitchen table. RK → GK
(b) If my glasses are on the kitchen table, then I saw them at breakfast. GK → SB
(c) I did not see my glasses at breakfast. ∼SB
(d) I was reading in the living room or in the kitchen. RL ∨ RK
(e) If I was reading in the living room, then my glasses are on the coffee table. RL → GC
Chain the rules of inference to find where the glasses are.
  1. Transitivity on (a) and (b):   RK → GK,  GK → SB  ∴ RK → SB
  2. Modus Tollens on the step-1 result and (c):   RK → SB,  ∼SB  ∴ ∼RK
  3. Elimination on (d) and the step-2 result:   RL ∨ RK,  ∼RK  ∴ RL
  4. Modus Ponens on (e) and the step-3 result:   RL → GC,  RL  ∴ GC

Conclusion. The glasses are on the coffee table. Four short rules replace a 32-row truth table (five variables). That is the value of inference rules once you leave Chapter 2.

Recap: Chapter 2

  • Build a truth table for any compound statement.
  • Test whether two statement forms are logically equivalent.
  • Apply the De Morgan laws to negate conjunctions and disjunctions.
  • Classify a statement as tautology, contradiction, or contingency.
  • Distinguish the conditional, its contrapositive (equivalent), converse, and inverse (not equivalent).
  • Translate necessary and sufficient conditions into symbolic form.
  • Check the validity of an argument by inspecting its critical rows.
  • Recognise the nine rules of inference (Modus Ponens, Modus Tollens, Generalization, Specialization, Conjunction, Elimination, Transitivity, Division into cases, Contradiction rule) and the two classic fallacies (converse error, inverse error).
What's next. Chapter 3: The Logic of Quantified Statements. Predicates, plus the universal and existential quantifiers ∀ and ∃, which let us reason about all or some objects at once instead of one statement at a time.