Introduction to Logic

Lessons

Senior 4 · Mathematics

Introduction to Logic

5 lessons

Lesson 5 of 5

Applications of logic: valid arguments, sets and switching circuits

25 min

Logic at work

A staircase light can be switched on at the bottom and off at the top, or the other way round. Whether the lamp is lit is a logical function of the two switch positions, and the wiring inside the wall is a piece of logic made of copper. This lesson puts the unit to work in three places: deciding whether an argument is valid, proving facts about sets, and designing switching circuits.

Definition

Valid argument: an argument with premises $p_1, p_2, \ldots, p_n$ and conclusion $q$ is valid if the conclusion is true in every case in which all the premises are true; that is, if

(p_1 \wedge p_2 \wedge \cdots \wedge p_n) \Rightarrow q

is a tautology. Otherwise it is invalid (a fallacy). Validity depends only on the form of the argument, not on whether the premises are actually true.

Rules of inference and two famous fallacies

Name	Form	Valid?
Modus ponens	$p \Rightarrow q$ , $p$ ; therefore $q$	Yes
Modus tollens	$p \Rightarrow q$ , $\neg q$ ; therefore $\neg p$	Yes
Hypothetical syllogism	$p \Rightarrow q$ , $q \Rightarrow r$ ; therefore $p \Rightarrow r$	Yes
Disjunctive syllogism	$p \vee q$ , $\neg p$ ; therefore $q$	Yes
Affirming the consequent	$p \Rightarrow q$ , $q$ ; therefore $p$	No
Denying the antecedent	$p \Rightarrow q$ , $\neg p$ ; therefore $\neg q$	No

Worked example 1: exposing a fallacy

"If Mugisha trains every day, he wins the race. Mugisha won the race. Therefore Mugisha trained every day." Is the argument valid?

Solution Let $p$ : "Mugisha trains every day", $q$ : "Mugisha wins". The form is $p \Rightarrow q$ , $q$ ; therefore $p$ .

$p$	$q$	$p \Rightarrow q$	$q$	conclusion $p$
T	T	T	T	T
T	F	F	F	T
F	T	T	T	F
F	F	T	F	F

In row 3 both premises are true but the conclusion is false (he may have won for another reason). The argument is invalid: it affirms the consequent.

Worked example 2: a chain of valid steps

"If it rains, the road is slippery. If the road is slippery, the bus is late. The bus is not late. Therefore it did not rain." Show that the argument is valid.

Solution With $r$ : "it rains", $s$ : "the road is slippery", $b$ : "the bus is late", the premises are $r \Rightarrow s$ , $s \Rightarrow b$ , $\neg b$ .

From $r \Rightarrow s$ and $s \Rightarrow b$ : $r \Rightarrow b$ (hypothetical syllogism).
From $r \Rightarrow b$ and $\neg b$ : $\neg r$ (modus tollens).

Each step uses a valid rule, so the argument is valid. (A truth table would need 8 rows; the rules need two lines.)

Logic and sets

If $A$ and $B$ are the truth sets of $P (x)$ and $Q (x)$ in a universal set $U$ , every connective matches a set operation:

Logic	Sets
$P(x) \wedge Q(x)$	$A \cap B$
$P(x) \vee Q(x)$	$A \cup B$
$\neg P(x)$	$A^{'}$ (complement)
$\forall x,\ P(x) \Rightarrow Q(x)$	$A \subseteq B$
logical equivalence $\equiv$	equality of sets $=$
tautology $\mathbf{T}$ , contradiction $\mathbf{F}$	$U$ , $\varnothing$

So every law of logic gives a law of sets. For example, De Morgan's law for sets follows line by line from De Morgan's law for statements:

x \in (A \cup B)' \iff \neg(x \in A \vee x \in B) \iff (x \notin A) \wedge (x \notin B) \iff x \in A' \cap B' .

Switching circuits

Let a statement $p$ mean "switch $p$ is closed" (current can pass). A lamp is on when there is a closed path through it. Switches one after another (in series) need both closed; switches on separate branches (in parallel) need at least one. A switch written $p^{'}$ is linked to $p$ so that it is always in the opposite state, giving $\neg p$ .

Every compound statement therefore describes a circuit, and every law of logic tells you how to build an equivalent circuit, often with fewer switches.

Worked example 3: simplifying a circuit

A circuit has two parallel branches: switches $p$ and $q$ in series on one, and $p$ and $r$ in series on the other. Write its logic expression and design a simpler equivalent circuit.

Solution The circuit is $(p \wedge q) \vee (p \wedge r)$ . By the distributive law this is $p \wedge (q \vee r)$ : one switch $p$ in series with $q$ and $r$ in parallel. The new circuit does the same job with three switches instead of four.

Worked example 4: the staircase light

A lamp must be on when switches $p$ (bottom of the stairs) and $q$ (top) are both closed or both open, so that flicking either one always changes the lamp. Find a logic expression and a circuit.

Solution "Both closed or both open" is $(p \wedge q) \vee (\neg p \wedge \neg q)$ , which is equivalent to $p \Leftrightarrow q$ . Changing either switch changes exactly one of $p, q$ , and so changes the truth value of $p \Leftrightarrow q$ : the lamp toggles. The circuit uses two branches:

In a real house each end uses a single two-way switch that does the job of $p$ and $p^{'}$ at once; the logic is the same.

Warning

Valid does not mean true. "All prime numbers are odd; 2 is prime; therefore 2 is odd" has a valid form, yet its conclusion is false, because the first premise is false. And an invalid argument can happen to have a true conclusion. Validity says only this: if all the premises are true, the conclusion must be true.

Tip

To test an argument with a truth table, you need only the rows in which every premise is true. If the conclusion is true in all of those rows, the argument is valid; one such row with a false conclusion makes it invalid.

Ganitya: Application of Boolean algebra to switching theory, series and parallel circuits. Watch for how a series connection behaves like 'and' and a parallel connection like 'or'.

✦

Practice

Justify each answer with a rule, a truth table or a law.

Use a truth table to test: $p \Rightarrow q$ , $\neg p$ ; therefore $\neg q$ .
Valid or invalid? Name the form. (a) If $n$ is divisible by 4, then $n$ is even. 36 is divisible by 4. So 36 is even. (b) If the shop is open, the lights are on. The lights are on. So the shop is open. (c) Either the pump is broken or the tank is empty. The tank is not empty. So the pump is broken.
Use the laws of logic to show that $(A \cap B)' = A' \cup B'$ .
$A$ and $B$ are the truth sets of $P (x)$ and $Q (x)$ . Which set is the truth set of $P(x) \wedge \neg Q(x)$ ?
Describe a circuit for $(p \vee q) \wedge r$ .
A lamp is controlled by $p$ in series with $q$ and $r$ in parallel. Is the lamp on when $p$ is closed, $q$ is open and $r$ is closed?
Simplify the circuit $(p \wedge q) \vee (p \wedge \neg q)$ .
A committee of three (votes $p, q, r$ ) passes a motion when at least two vote yes. Write a logic expression and simplify it so that $p$ appears only once.

Show answersHide answers

Invalid (denying the antecedent): with $p$ false and $q$ true, both premises are true but $\neg q$ is false.
(a) Valid, modus ponens. (b) Invalid, affirming the consequent. (c) Valid, disjunctive syllogism.
$x \in (A \cap B)' \iff \neg(x \in A \wedge x \in B) \iff x \notin A \vee x \notin B \iff x \in A' \cup B'$ (De Morgan).
$A \cap B'$ , which is $A \setminus B$ .
$p$ and $q$ in parallel, and that pair in series with $r$ .
$p \wedge (q \vee r)$ is T $\wedge$ (F $\vee$ T), which is T: the lamp is on.
$p \wedge (q \vee \neg q) \equiv p \wedge \mathbf{T} \equiv p$ : a single switch $p$ .
$(p \wedge q) \vee (p \wedge r) \vee (q \wedge r) \equiv \big(p \wedge (q \vee r)\big) \vee (q \wedge r)$ .

Quick check

Which of these argument forms is NOT valid?

Key points

An argument is valid when (premises) $\Rightarrow$ conclusion is a tautology.
Modus ponens, modus tollens and the syllogisms are valid; affirming the consequent and denying the antecedent are fallacies.
$\wedge, \vee, \neg$ correspond to $\cap, \cup$ and complement, so every law of logic is a law of sets.
Series switches give $\wedge$ , parallel switches give $\vee$ ; the laws of logic simplify circuits.

1Logic at work

2Rules of inference and two famous fallacies

3Logic and sets

4Switching circuits

Logic at work

Rules of inference and two famous fallacies

Logic and sets

Switching circuits