84 Propositional Logic Exercises

This document contains 84 Propositional Logic Exercises designed to strengthen and solidify your understanding of this fundamental area of mathematics and philosophy

These exercises complement the following theoretical reference materials:

#	Theoretical Document	Main Content
1	Logical Propositions	Definition of proposition, logical principles, propositional variables
2	Logical Connectives	The 6 connectives, truth tables, operator hierarchy
3	Truth Tables	Table construction, tautologies, contradictions, contingencies
4	Logical Equivalences	Equivalence laws, expression simplification
5	Rules of Inference	Modus Ponens, Modus Tollens, syllogisms, reductio ad absurdum
6	Logic Circuits	Logic gates, circuit design and simplification
7	Mathematical Proof	Proof methods: direct, contraposition, contradiction, induction

Learning Goals

This collection provides hands-on practice in:

• Identifying propositions and determining their truth values
• Converting verbal statements into symbolic expressions
• Translating symbolic expressions back into natural language
• Evaluating compound propositions with truth tables
• Proving logical equivalences
• Applying rules of inference to arguments
• Designing and simplifying logic circuits

How This Document Is Organized

The exercises are grouped by topic, with each section beginning with a quick reference summary of the key concepts you’ll need.

Section I: Propositions and Logical Connectives

This section covers propositions and logical connectives, including how to identify propositions, symbolize statements, use connectives, and determine truth values.

Quick Reference Guide

What is a proposition?

A proposition is a declarative sentence that can be true (T) or false (F), but never both.

Propositions ✓	Not Propositions ✗
“Washington D.C. is the capital of the USA” (T)	“What time is it?” (question)
“2 + 3 = 7” (F)	“Close the door!” (command)
“Water boils at 100°C” (T)	“x + 5 = 10” (contains undefined variable)

What doesn’t count as a proposition: Questions, commands, exclamations, wishes, open sentences (containing undefined variables), and paradoxes.

Fundamental Logical Principles

Principle	Formula	Meaning
Identity	p ≡ p	Every proposition is identical to itself
Non-Contradiction	\( \mathrm{ ¬(p ∧ ¬p) } \)	A proposition cannot be T and F at the same time
Excluded Middle	p ∨ ¬p	Every proposition is T or F; there is no third option

Propositional Variables

Propositional variables are lowercase letters (p, q, r, s…) that represent complete propositions.

Variable	Proposition	Value
p	“5 is an even number”	F
q	“Brazil is in South America”	T
r	“Water boils at 100°C”	T

Classification of Propositions

Type	Description	Example
Simple (Atomic)	Contains no logical connectives	“Mary studies medicine”
Compound (Molecular)	Contains one or more connectives	“It rains and it’s cold”

The 6 Logical Connectives

Connective	Symbol	Example	When is T
Negation	¬	¬p	Inverts the value of p
Conjunction	∧	p ∧ q	Only when both are T
Disjunction	∨	p ∨ q	When at least one is T
Conditional	→	p → q	Always, except T→F
Biconditional	↔	p ↔ q	When both have the same value
Exclusive Disjunction	⊻	p ⊻ q	When exactly one is T

Ways to Express Connectives

Connective	Indicator Words/Phrases
Negation (¬)	not, it is not true that, it is false that, it is not the case that
Conjunction (∧)	and, but, moreover, however, although, while, despite
Disjunction (∨)	or, either…or
Conditional (→)	if…then, whenever, when, only if, implies, is sufficient for, is necessary for
Biconditional (↔)	if and only if, when and only when, is equivalent to, is necessary and sufficient
Exclusive Disjunction (⊻)	either…or (but not both), exclusively

Propositions Derived from the Conditional

From a conditional p → q, the following can be formed:

Name	Form	Example: “If it rains, then the street gets wet”
Direct	p → q	If it rains, then the street gets wet
Converse	q → p	If the street gets wet, then it rains
Inverse	\( \mathrm{ ¬p → ¬q } \)	If it doesn’t rain, then the street doesn’t get wet
Contrapositive	¬q → ¬p	If the street doesn’t get wet, then it doesn’t rain

Important: The direct and contrapositive always have the same truth value. The converse and inverse also have the same value as each other.

Operator Hierarchy (Order of Precedence)

Priority	Operator	Symbol
1 (highest)	Parentheses	( )
2	Negation	¬
3	Conjunction	∧
4	Disjunction	∨
5	Conditional	→
6 (lowest)	Biconditional	↔

Example: p ∨ q ∧ r is equivalent to p ∨ (q ∧ r), because ∧ has higher precedence than ∨.

Summary Truth Tables

Negation (¬p)

p	¬p
T	F
F	T

Conjunction (p ∧ q) → Only T when both are T

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

Disjunction (p ∨ q) → Only F when both are F

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

Conditional (p → q) → Only F when T→F

p	q	p → q
T	T	T
T	F	F
F	T	T
F	F	T

Biconditional (p ↔ q) → T when both have the same value

p	q	p ↔ q
T	T	T
T	F	F
F	T	F
F	F	T

Exclusive Disjunction (p ⊻ q) → T when exactly one is T

p	q	p ⊻ q
T	T	F
T	F	T
F	T	T
F	F	F

Finding Truth Values: Step by Step

1. Identify the simple propositions (p, q, r…)
2. Assign truth values to each one
3. Look up the result in the appropriate truth table
4. Work from the inside out, respecting parentheses and operator precedence

Worked Examples

Exercise 1

Express each statement in symbolic form:

a) “If it’s cold, then it rains”

Let p: “It’s cold” and q: “It rains”

Solution

• The key words “If… then” signal a Conditional (→)
• Symbolic form: p → q

Note: Symbolic form captures the logical structure, not whether the statement is actually true.

b) “If I study, then I pass the exam, and if I pass the exam, then I go to the party”

Let p: “I study”, q: “I pass the exam” and r: “I go to the party”

Solution

• Breaking it down:
  • “If I study, then I pass” → p → q
  • “If I pass, then I go to the party” → q → r
  • These are connected by “and” → Conjunction (∧)
• Symbolic form: (p → q) ∧ (q → r)

Note: This is the hypothetical syllogism pattern, which lets us conclude p → r.

c) “It is not true that I saw the movie and read the novel”

Let p: “I saw the movie” and q: “I read the novel”

Solution

• Breaking down the structure:
  • “It is not true that…” → Negation (¬) applies to everything after
  • “saw the movie and read the novel” → Conjunction (p ∧ q)
• Symbolic form: ¬(p ∧ q)

Note: By De Morgan’s Law, this is equivalent to: ¬p ∨ ¬q

d) “If you weren’t crazy, you wouldn’t have come here”

Let p: “You are crazy” and q: “You came here”

Solution

• Looking at the structure:
  • “If you were not crazy” → Antecedent: ¬p
  • “you would not have come here” → Consequent: ¬q
• Symbolic form: ¬p → ¬q

Note: This is the inverse of a conditional. The inverse is NOT logically equivalent to the original, but it IS equivalent to the converse (q → p).

e) “It rains and either it snows or the wind blows”

Let p: “It rains”, q: “It snows” and r: “The wind blows”

Solution

• We identify the structure:
  • “It rains” → p
  • “either it snows or the wind blows” → Disjunction: q ∨ r
  • “It rains and (either…)” → Conjunction
• Formalization: p ∧ (q ∨ r)

Note: Parentheses matter here. Without them, operator precedence would give us (p ∧ q) ∨ r instead.

f) “Either it’s raining and snowing or the wind is blowing”

Let p: “It’s raining”, q: “It’s snowing” and r: “The wind is blowing”

Solution

• We identify the structure:
  • “it’s raining and snowing” → Conjunction: p ∧ q
  • “Either (the above) or the wind is blowing” → Disjunction with r
• Formalization: (p ∧ q) ∨ r

Note: Compare this with part (e): p ∧ (q ∨ r) ≠ (p ∧ q) ∨ r. Grouping changes the meaning completely.

g) “If there is true democracy, then there are no arbitrary detentions nor violations of civil rights”

Let p: “There is true democracy”, q: “There are arbitrary detentions” and r: “There are violations of civil rights”

Solution

• We identify the structure:
  • “If there is true democracy” → Antecedent: p
  • “no detentions nor … violations” → “neither…nor” = Conjunction of negations: ¬q ∧ ¬r
• Formalization: p → (¬q ∧ ¬r)

Note: By De Morgan, ¬q ∧ ¬r = ¬(q ∨ r). Equivalent form: p → ¬(q ∨ r)

Exercise 2

Find the truth value of each proposition:

a) If 5 + 4 = 11, then 6 + 6 = 12

Solution

• The connective is a conditional (→), signaled by “If… then”
• p: “5 + 4 = 11” → Actually 5 + 4 = 9, so p is F
• q: “6 + 6 = 12” → This is correct, so q is T
• From the truth table: F → T = T

Answer: True (T)

b) It is not true that 3 + 3 = 7 if and only if 5 + 5 = 12

Solution

• Structure: negation (¬) of a biconditional (↔)
• p: “3 + 3 = 7” → 3 + 3 = 6, so p is F
• q: “5 + 5 = 12” → 5 + 5 = 10, so q is F
• First we evaluate the biconditional: F ↔ F = T (both have the same value)
• Then we apply negation: ¬T = F

Answer: False (F)

c) Paris is in England or Tokyo is in China.

Solution

• The connective is a disjunction (∨), signaled by “or”
• p: “Paris is in England” → Paris is in France, so p is F
• q: “Tokyo is in China” → Tokyo is in Japan, so q is F
• From the truth table: F ∨ F = F (a disjunction is only false when both parts are false)

Answer: False (F)

d) It is not true that 2 + 2 = 5 or that 3 + 1 = 4

Solution

• Structure: negation (¬) of a disjunction (∨)
• p: “2 + 2 = 5” → 2 + 2 = 4, so p is F
• q: “3 + 1 = 4” → 3 + 1 = 4, so q is T
• First we evaluate the disjunction: F ∨ T = T (at least one is T)
• Then we apply negation: ¬T = F

Answer: False (F)

Exercise 3

Find the truth value of each proposition:

a) 4 + 8 = 12 and 9 – 4 = 5

Solution

• We identify the connective: conjunction (∧) by the word “and”
• p: “4 + 8 = 12” → 4 + 8 = 12, so p is T
• q: “9 – 4 = 5” → 9 – 4 = 5, so q is T
• We apply the conjunction table: T ∧ T = T (conjunction is only T when both are T)

Answer: True (T)

b) 8 + 4 = 12 and 8 – 3 = 2

Solution

• We identify the connective: conjunction (∧) by the word “and”
• p: “8 + 4 = 12” → 8 + 4 = 12, so p is T
• q: “8 – 3 = 2” → 8 – 3 = 5, so q is F
• We apply the conjunction table: T ∧ F = F (if one is F, the conjunction is F)

Answer: False (F)

c) 8 + 4 = 12 or 7 – 2 = 3

Solution

• We identify the connective: disjunction (∨) by the word “or”
• p: “8 + 4 = 12” → 8 + 4 = 12, so p is T
• q: “7 – 2 = 3” → 7 – 2 = 5, so q is F
• We apply the disjunction table: T ∨ F = T (if one is T, the disjunction is T)

Answer: True (T)

d) MIT is in California or is in Massachusetts.

Solution

• The connective is a disjunction (∨), signaled by “or”
• p: “MIT is in California” → MIT is in Massachusetts, so p is F
• q: “MIT is in Massachusetts” → Correct, so q is T
• From the truth table: F ∨ T = T

Answer: True (T)

e) Harvard is in Massachusetts or is in New York.

Solution

• The connective is a disjunction (∨), signaled by “or”
• p: “Harvard is in Massachusetts” → Correct, so p is T
• q: “Harvard is in New York” → so q is F
• From the truth table: T ∨ F = T

Answer: True (T)

f) If 5 + 2 = 7, then 3 + 6 = 9

Solution

• We identify the connective: conditional (→) by “If… then”
• p: “5 + 2 = 7” → 5 + 2 = 7, so p is T
• q: “3 + 6 = 9” → 3 + 6 = 9, so q is T
• We apply the conditional table: T → T = T

Answer: True (T)

g) If 4 + 3 = 2, then 5 + 5 = 10

Solution

• We identify the connective: conditional (→) by “If… then”
• p: “4 + 3 = 2” → 4 + 3 = 7, so p is F
• q: “5 + 5 = 10” → 5 + 5 = 10, so q is T
• We apply the conditional table: F → T = T (conditional is only F when T → F)

Answer: True (T)

h) If 4 + 5 = 9, then 3 + 1 = 2

Solution

• We identify the connective: conditional (→) by “If… then”
• p: “4 + 5 = 9” → 4 + 5 = 9, so p is T
• q: “3 + 1 = 2” → 3 + 1 = 4, so q is F
• We apply the conditional table: T → F = F (this is the only case where the conditional is F)

Answer: False (F)

i) If 7 + 3 = 4, then 11 – 7 = 9

Solution

• We identify the connective: conditional (→) by “If… then”
• p: “7 + 3 = 4” → 7 + 3 = 10, so p is F
• q: “11 – 7 = 9” → 11 – 7 = 4, so q is F
• We apply the conditional table: F → F = T (when the antecedent is F, the conditional is always T)

Answer: True (T)

Exercise 4

For the following statements:

1. Pick up that pencil
2. 2+5 < 6
3. x-y=5
4. It’s very cold

Which of the following alternatives is correct?

a) Two are propositions b) Two are open sentences c) Two are neither propositions nor open sentences d) Three are propositions

Solution

Let’s analyze each statement:

#	Statement	Analysis	Classification
1	“Pick up that pencil”	It’s a command/order, has no truth value	❌ Not a proposition
2	“2+5 < 6”	It’s a statement: 2+5=7 and 7 < 6 is F	✅ Proposition (F)
3	“x-y=5”	Contains undefined variables	⚠️ Open sentence
4	“It’s very cold”	It’s subjective/ambiguous, has no defined truth value	❌ Not a proposition

Answer: c) Two are neither propositions nor open sentences

(Statements 1 and 4 are neither propositions nor open sentences)

Exercise 5

Given the propositions: p = Mark is a merchant, q = Mark is a prosperous industrialist and r = Mark is an engineer.

Symbolize the statement: “If it is not the case that Mark is a merchant and prosperous industrialist, then he is an engineer or he is not a merchant.”

Solution

Step 1: We identify the simple propositions:

• p: “Mark is a merchant”
• q: “Mark is a prosperous industrialist”
• r: “Mark is an engineer”

Step 2: We decompose the statement into parts:

Part of the statement	Symbolization
“It is not the case that Mark is a merchant and prosperous industrialist”	¬(p ∧ q)
“He is an engineer or he is not a merchant”	r ∨ ¬p
“If… then…”	→

Step 3: We join with the conditional:

\( \neg(p \land q) \rightarrow (r \lor \neg p) \)

Exercise 6

Let p: “It’s cold” and q: “It’s raining”. Write out each symbolic expression in plain English:

#	Symbolic expression
(1)	¬p
(2)	p ∧ q
(3)	p ∨ q
(4)	q ↔ p
(5)	p → ¬q
(6)	q ∨ ¬p
(7)	¬p ∧ ¬q
(8)	p ↔ ¬q
(9)	¬¬q
(10)	(p ∧ ¬q) → p

Solution

Strategy: Here’s how each symbol translates to English:

Symbol	Verbal translation
¬	“not”, “it is not true that”, “it is false that”
∧	“and”
∨	“or”
→	“if… then”
↔	“if and only if”

(1) ¬p

• Structure: Negation of p
• Translation: “It’s not cold”

(2) p ∧ q

• Structure: Conjunction of p and q
• Translation: “It’s cold and it’s raining”

(3) p ∨ q

• Structure: Disjunction of p and q
• Translation: “It’s cold or it’s raining”

(4) q ↔ p

• Structure: Biconditional between q and p
• Translation: “It’s raining if and only if it’s cold”

(5) p → ¬q

• Structure: Conditional with negated consequent
• Translation: “If it’s cold, then it’s not raining”

(6) q ∨ ¬p

• Structure: Disjunction of q and the negation of p
• Translation: “It’s raining or it’s not cold”

(7) ¬p ∧ ¬q

• Structure: Conjunction of two negations
• Translation: “It’s not cold and it’s not raining”

Note: By De Morgan’s Law, this is equivalent to ¬(p ∨ q): “It is not true that it’s cold or it’s raining”

(8) p ↔ ¬q

• Structure: Biconditional between p and the negation of q
• Translation: “It’s cold if and only if it’s not raining”

(9) ¬¬q

• Structure: Double negation of q
• Literal translation: “It is not true that it’s not raining”
• Simplified translation (by double negation): “It’s raining”

Note: By the law of double negation, ¬¬q ≡ q

(10) (p ∧ ¬q) → p

• Structure: Conditional where the antecedent is a conjunction
• Translation: “If it’s cold and it’s not raining, then it’s cold”

Note: This proposition is a tautology (always true), since if “it’s cold” appears in the antecedent, it necessarily holds in the consequent. It’s a case of the Simplification rule: (p ∧ q) → p.

Exercise 7

Let p = “He is tall” and q = “He is handsome”. Express each statement symbolically:

#	Verbal statement
(1)	He is tall and handsome
(2)	He is tall but not handsome
(3)	It is false that he is short or handsome
(4)	He is neither tall nor handsome
(5)	He is tall, or he is short and handsome
(6)	It is not true that he is short or not handsome

Solution

Important note: “He is short” is the opposite of “He is tall”, therefore:

• “short” = ¬p (negation of p)

(1) He is tall and handsome

• Key word: “and” → Conjunction (∧)
• Symbolic form: p ∧ q

(2) He is tall but not handsome

• Key word: “but” → Conjunction (∧)
• “not handsome” = ¬q
• Symbolic form: p ∧ ¬q

Note: In logic, “but” functions identically to “and” (conjunction), even though in everyday English it suggests contrast.

(3) It is false that he is short or handsome

• Structure: Negation of a disjunction
• “short” = ¬p, “handsome” = q
• “short or handsome” = ¬p ∨ q
• “It is false that…” = Negation of everything
• Formalization: ¬(¬p ∨ q)

Note: By De Morgan, this is equivalent to: p ∧ ¬q (“He is tall and not handsome”)

(4) He is neither tall nor handsome

• Structure: “neither… nor…” = Conjunction of negations
• “not tall” = ¬p
• “not handsome” = ¬q
• Formalization: ¬p ∧ ¬q

Note: By De Morgan, this is equivalent to: ¬(p ∨ q) (“It is not true that he is tall or handsome”)

(5) He is tall, or he is short and handsome

• Structure: Disjunction where one part is a conjunction
• “tall” = p
• “short and handsome” = ¬p ∧ q
• Formalization: p ∨ (¬p ∧ q)

Note: By absorption, this simplifies to: p ∨ q

(6) It is not true that he is short or not handsome

• Structure: Negation of a disjunction
• “short” = ¬p
• “not handsome” = ¬q
• “short or not handsome” = ¬p ∨ ¬q
• Formalization: ¬(¬p ∨ ¬q)

Note: By De Morgan, this is equivalent to: p ∧ q (“He is tall and handsome”)

Answer summary:

#	Formalization
(1)	p ∧ q
(2)	p ∧ ¬q
(3)	¬(¬p ∨ q)
(4)	¬p ∧ ¬q
(5)	p ∨ (¬p ∧ q)
(6)	¬(¬p ∨ ¬q)

Exercise 8

Find the truth value of each compound statement:

#	Statement
(1)	If 3 + 2 = 7, then 4 + 4 = 8
(2)	It is not true that 2 + 2 = 5 if and only if 4 + 4 = 10
(3)	Paris is in England or London is in France
(4)	It is not true that 1 + 1 = 3 or that 2 + 1 = 3
(5)	It is false that if Paris is in England, then London is in France

Solution

(1) If 3 + 2 = 7, then 4 + 4 = 8

Step 1: Identify the component propositions:

• p: “3 + 2 = 7” → 3 + 2 = 5, so p is F
• q: “4 + 4 = 8” → 4 + 4 = 8, so q is T

Step 2: We identify the structure: Conditional (p → q)

Step 3: We evaluate using the conditional table:

• F → T = T (conditional is only F when T → F)

Answer: True (T)

(2) It is not true that 2 + 2 = 5 if and only if 4 + 4 = 10

Step 1: Identify the component propositions:

• p: “2 + 2 = 5” → 2 + 2 = 4, so p is F
• q: “4 + 4 = 10” → 4 + 4 = 8, so q is F

Step 2: We identify the structure: Negation of a biconditional ¬(p ↔ q)

Step 3: We evaluate the biconditional first:

• F ↔ F = T (biconditional is T when both have the same value)

Step 4: We apply negation:

• ¬T = F

Answer: False (F)

(3) Paris is in England or London is in France

Step 1: Identify the component propositions:

• p: “Paris is in England” → Paris is in France, so p is F
• q: “London is in France” → London is in England, so q is F

Step 2: We identify the structure: Disjunction (p ∨ q)

Step 3: We evaluate using the disjunction table:

• F ∨ F = F (disjunction is only F when both are F)

Answer: False (F)

(4) It is not true that 1 + 1 = 3 or that 2 + 1 = 3

Step 1: Identify the component propositions:

• p: “1 + 1 = 3” → 1 + 1 = 2, so p is F
• q: “2 + 1 = 3” → 2 + 1 = 3, so q is T

Step 2: We identify the structure: Negation of a disjunction ¬(p ∨ q)

Step 3: We evaluate the disjunction first:

• F ∨ T = T (at least one is T)

Step 4: We apply negation:

• ¬T = F

Answer: False (F)

(5) It is false that if Paris is in England, then London is in France

Step 1: Identify the component propositions:

• p: “Paris is in England” → p is F
• q: “London is in France” → q is F

Step 2: We identify the structure: Negation of a conditional ¬(p → q)

Step 3: We evaluate the conditional first:

• F → F = T (when the antecedent is F, the conditional is always T)

Step 4: We apply negation:

• ¬T = F

Answer: False (F)

Answer summary:

#	Structure	Values	Result
(1)	p → q	F → T	T
(2)	¬(p ↔ q)	¬(F ↔ F) = ¬T	F
(3)	p ∨ q	F ∨ F	F
(4)	¬(p ∨ q)	¬(F ∨ T) = ¬T	F
(5)	¬(p → q)	¬(F → F) = ¬T	F

Exercise 9

Define a custom operator p#q that is true when p is false and q is true, and false otherwise.

Given r: “John is a doctor” and s: “John is an athlete”, find what (¬r)#s means in plain English.

Solution

Step 1: Build the truth table for the # operator

The # operator is defined as:

• p#q = T only when p = F and q = T
• p#q = F in all other cases

p	q	p#q
T	T	F
T	F	F
F	T	T
F	F	F

Note: This custom operator returns true in exactly one case: (F, T).

Step 2: Build the truth table for (¬r)#s

We apply the definition of the # operator to the expression (¬r)#s:

r	s	¬r	(¬r)#s
T	T	F	T
T	F	F	F
F	T	T	F
F	F	T	F

Step 3: Analyze the pattern

The column (¬r)#s has value T only when:

• ¬r = F (that is, r = T)
• s = T

This is exactly the pattern of the conjunction r ∧ s:

r	s	r ∧ s	(¬r)#s
T	T	T	T
T	F	F	F
F	T	F	F
F	F	F	F

The columns match perfectly!

Step 4: Translate to English

Since (¬r)#s ≡ r ∧ s, the translation is:

“John is a doctor and an athlete”

Takeaway: Custom operators can sometimes be expressed using standard connectives. Here, applying # to (¬r) and s gives us the same result as the conjunction r ∧ s.

Exercise 10

For which of the following can we determine the truth value with the information given?

\( A = (p \lor q) \rightarrow (\neg p \land \neg q) \); \( V(q) = \mathrm{T} \)

\( B = (p \land q) \rightarrow (p \lor r) \); \( V(p) = \mathrm{T} \) and \( V(r) = \mathrm{F} \)

\( C = [p \land (q \rightarrow r)] \); \( V(p \rightarrow r) = \mathrm{T} \)

\( D = (p \rightarrow q) \rightarrow r \); \( V(r) = \mathrm{T} \)

Note: \( V(p) \) means the truth value of \( p \)

Solution

For each case, let’s see if we can pin down the truth value regardless of the unknowns:

In A: \( (p \lor q) \rightarrow (\neg p \land \neg q) \) with \( V(q) = \mathrm{T} \)

• We substitute q = T: \( (p \lor \mathrm{T} ) \rightarrow (\neg p \land \mathrm{F} ) \)
• \( p \lor \mathrm{T} = \mathrm{T} \) (anything OR T is T)
• \( \neg p \land \mathrm{F} = \mathrm{F} \) (anything AND F is F)
• Result: \( T \rightarrow \mathrm{F} = \mathrm{F} \)
• ✅ Sufficient (always gives F)

In B: \( (p \land q) \rightarrow (p \lor r) \) with \( V(p) = \mathrm{T} \), \( V(r) = \mathrm{F} \)

• We substitute: \( ( \mathrm{T} \land q) \rightarrow ( \mathrm{T} \lor \mathrm{F} ) \)
• \( \mathrm{T} \lor \mathrm{F} = \mathrm{T} \) (consequent always T)
• Anything → T = T (conditional with T consequent is always T)
• ✅ Sufficient (always gives T)

In C: \( p \land (q \rightarrow r) \) with \( V(p \rightarrow r) = \mathrm{T} \)

• We know that \( p \rightarrow r = T \), but this has 3 possibilities: (T,T), (F,T), (F,F)
• We cannot determine the individual values of p, q, r
• There are multiple combinations that give different results
• ❌ Not sufficient

In D: \( (p \rightarrow q) \rightarrow r \) with \( V(r) = \mathrm{T} \)

• We substitute: \( (p \rightarrow q) \rightarrow \mathrm{T} \)
• Any “thing” → T = T (conditional with T consequent is always T)
• ✅ Sufficient (always gives T)

Answer: A, B and D have sufficient information; C does not have sufficient information

Exercise 11

Given the propositions q: “4 is an odd number”, p and r any such that \( \neg[(r \lor q) \rightarrow (r \rightarrow p)] \) is true; find the truth value of the following molecular systems:

\( A = r \rightarrow (\neg p \lor \neg q) \) ; \( B = [r \leftrightarrow (p \land q)] \leftrightarrow (q \land \neg p) \) ; \( C = (r \lor \neg p) \land (q \lor p) \)

Solution

Step 1: We determine the value of q:

• q: “4 is an odd number” → 4 is even, so V(q) = F

Step 2: We analyze the main proposition:

• If \( \neg[(r \lor q) \rightarrow (r \rightarrow p)] \) is T
• Then \( (r \lor q) \rightarrow (r \rightarrow p) \) is F (by negation)

Step 3: The conditional is F only when T → F:

• \( (r \lor q) \) is T (antecedent)
• \( (r \rightarrow p) \) is F (consequent)

Step 4: If \( r \rightarrow p \) is F, then: V(r) = T and V(p) = F

Step 5: We verify: \( r \lor q = \mathrm{T} \lor \mathrm{F} = \mathrm{T} \) ✔

Summary of values: p = F, q = F, r = T

Step 6: We evaluate each schema:

Solving	Result
\( \mathrm{A} = r → (¬p ∨ ¬q) \) \( = \mathrm{T} → (\mathrm{T} ∨ \mathrm{T}) \) \( = \mathrm{T} → \mathrm{T} = \mathrm{T} \)	A = T
\( \mathrm{B} = [r ↔ (p ∧ q)] ↔ (q ∧ ¬p) \) \( = [\mathrm{T} ↔ \mathrm{F}] ↔ \mathrm{F} \) \( = \mathrm{F} ↔ \mathrm{F} = \mathrm{T} \)	B = T
\( \mathrm{C} = (r ∨ ¬p) ∧ (q ∨ p) \) \( = (\mathrm{T} ∨ \mathrm{T}) ∧ (\mathrm{F} ∨ \mathrm{F}) \) \( = \mathrm{T} ∧ \mathrm{F} = \mathrm{F} \)	C = F

Answer: V(A) = T, V(B) = T, V(C) = F

Exercise 12

From the falsity of the proposition: \( (p \rightarrow \neg q) \lor (\neg r \rightarrow s) \) it is deduced that the truth value of the molecular schemas:

\( A = (\neg p \land \neg q) \lor (\neg q) \) ; \( B = [(\neg r \lor q)] \leftrightarrow [(\neg q \lor r)] \) ; \( C = (p \rightarrow q) \rightarrow [(p \lor q) \land \neg q] \)

are respectively: a) TFT b) FFF c) TTT d) FFT

Solution

Step 1: We analyze the main proposition:

• If \( (p \rightarrow \neg q) \lor (\neg r \rightarrow s) \) is F
• The disjunction is only F when both parts are F

Step 2: We determine the values:

Proposition	Condition to be F	Values obtained
p → ¬q = F	T → F	p = T, q = T
¬r → s = F	T → F	r = F, s = F

Summary: p = T, q = T, r = F, s = F

Step 3: We evaluate each schema:

Solving	Result
\( \mathrm{A} = (¬p ∧ ¬q) ∨ ¬q \) \( = (\mathrm{F} ∧ \mathrm{F}) ∨ \mathrm{F} \) \( = \mathrm{F} ∨ \mathrm{F} \)	A = F
\( \mathrm{B} = (¬r ∨ q) ↔ (¬q ∨ r) \) \( = (\mathrm{T} ∨ \mathrm{T}) ↔ (\mathrm{F} ∨ \mathrm{F}) \) \( = \mathrm{T} ↔ \mathrm{F} \)	B = F
\( \mathrm{C} = (p → q) → [(p ∨ q) ∧ ¬q] \) \( = \mathrm{T} → [\mathrm{T} ∧ \mathrm{F}] \) \( = \mathrm{T} → \mathrm{F} \)	C = F

Answer: b) FFF

Exercise 13

If the following expression is true, find the truth values of p, q and r:

\( \neg[(\neg p \lor q) \lor (r \rightarrow q)] \land [(\neg p \lor q) \rightarrow (q \land \neg p)] \)

Solution

Strategy: For a conjunction (∧) to be T, both parts must be T.

Step 1: We separate the expression into two parts

• Left part: ¬[(¬p ∨ q) ∨ (r → q)] = T
• Right part: [(¬p ∨ q) → (q ∧ ¬p)] = T

Step 2: We analyze the left part

If ¬[(¬p ∨ q) ∨ (r → q)] = T, then:

• (¬p ∨ q) ∨ (r → q) = F (by negation)

For a disjunction to be F, both parts must be F:

• ¬p ∨ q = F
• r → q = F

Step 3: From ¬p ∨ q = F

The disjunction is only F when both are F:

• ¬p = F → p = T
• q = F

Step 4: From r → q = F

The conditional is only F when T → F:

• r = T
• q = F (confirmed)

Step 5: We verify with the right part

[(¬p ∨ q) → (q ∧ ¬p)] with p = T, q = F

• ¬p ∨ q = F ∨ F = F
• q ∧ ¬p = F ∧ F = F
• F → F = T ✓

Answer:

Variable	Value
p	T
q	F
r	T

Conclusion: This type of exercise requires working “backwards” from the known truth value of the complete expression, using the properties of the connectives to deduce the values of the variables.

Exercise 14

From the falsity of (p → ¬q) ∨ (¬r → ¬s), it is deduced that the truth value of the schemas:

• A = ¬(¬q ∨ ¬s) → ¬p
• B = ¬(¬r ∧ s) ↔ (¬p → ¬q)
• C = p → ¬[q → ¬(s → r)]

are respectively:

a) FFT b) FFF c) FTF d) FTT

Solution

Step 1: We deduce the values of p, q, r, s

If (p → ¬q) ∨ (¬r → ¬s) = F, both parts must be F:

Expression	Condition to be F	Values obtained
\( p → \neg q = F \)	T → F	p = T q = T
\( \neg r → \neg s = F \)	T → F	r = F s = T

Summary: p = T, q = T, r = F, s = T

Step 2: We evaluate A = ¬(¬q ∨ ¬s) → ¬p

Subexpression	Evaluation
¬q, ¬s	F, F
¬q ∨ ¬s	F
¬(¬q ∨ ¬s)	T
¬p	F
T → F	F

Step 3: We evaluate B = ¬(¬r ∧ s) ↔ (¬p → ¬q)

Subexpression	Evaluation
¬r ∧ s	T ∧ T = T
¬(¬r ∧ s)	F
¬p → ¬q	F → F = T
F ↔ T	F

Step 4: We evaluate C = p → ¬[q → ¬(s → r)]

Subexpression	Evaluation
s → r	T → F = F
¬(s → r)	T
q → T	T
¬[q → ¬(s → r)]	F
p → F	T → F = F

Answer:

A	B	C
F	F	F

Correct answer: b) FFF

Exercise 15

(p ∨ q) ↔ (r ∧ s) is a true proposition, with r and s having opposite truth values. Of the following statements, which are true?

• A = [(¬p ∧ ¬q) ∨ (r ∧ s)] ∧ p, is true
• B = [¬(p ∨ q) ∧ (r ∨ s)] ∨ (¬p ∧ q), is false
• C = [(¬r ∧ ¬s) → (p ∨ r)] ∧ ¬(r ∧ s), is true

Solution

Step 1: We deduce the values of the variables

From “r and s are opposite”:

• If r = T, s = F → r ∧ s = F
• If r = F, s = T → r ∧ s = F
• In both cases: r ∧ s = F

From the biconditional (p ∨ q) ↔ (r ∧ s) = T:

• (p ∨ q) ↔ F = T
• For it to be T, both sides must be equal
• Therefore: p ∨ q = F → p = F, q = F

Summary: p = F, q = F, r ∧ s = F (with r ≠ s)

Step 2: We evaluate each statement (using r = T, s = F)

A = [(¬p ∧ ¬q) ∨ (r ∧ s)] ∧ p

Subexpression	Evaluation
¬p ∧ ¬q	T ∧ T = T
r ∧ s	F
T ∨ F	T
T ∧ p	T ∧ F = F

A = F. The statement says T → INCORRECT ❌

B = [¬(p ∨ q) ∧ (r ∨ s)] ∨ (¬p ∧ q)

Subexpression	Evaluation
¬(p ∨ q)	¬F = T
r ∨ s	T
T ∧ T	T
¬p ∧ q	T ∧ F = F
T ∨ F	T

B = T. The statement says F → INCORRECT ❌

C = [(¬r ∧ ¬s) → (p ∨ r)] ∧ ¬(r ∧ s)

Subexpression	Evaluation
¬r ∧ ¬s	F ∧ T = F
p ∨ r	F ∨ T = T
F → T	T
¬(r ∧ s)	T
T ∧ T	T

C = T. The statement says T → CORRECT ✅

Answer:

Statement	Says	Actual value	Result
A	T	F	❌ False
B	F	T	❌ False
C	T	T	✅ True

Conclusion: Two statements are false (A and B) and only one is true (C).

Exercise 16

Given the following information:

• V(r → q) = T
• V(n ∧ r) = F
• V(m ∨ n) = T
• V(p ∨ m) = F

Determine the truth value of the molecular schema:

A = [(m ∨ ¬n) → (p ∧ ¬r)] ↔ (m ∧ q)

Solution

Step 1: We deduce the values of the variables

Condition	Analysis	Values obtained
\( V(p ∨ m) = \mathrm{F} \)	Disjunction F → both F	p = F, m = F
\( V(m ∨ n) = \mathrm{T} \)	F ∨ n = T	n = T
\( V(n ∧ r) = \mathrm{F} \)	T ∧ r = F	r = F
\( V(r → q) = \mathrm{T} \)	F → q = T	q = ?(unknown)

Summary: p = F, m = F, n = T, r = F

Step 2: We evaluate the left side: (m ∨ ¬n) → (p ∧ ¬r)

Subexpression	Evaluation
m ∨ ¬n	F ∨ F = F
p ∧ ¬r	F ∧ T = F
F → F	T

Step 3: We evaluate the right side: m ∧ q

Subexpression	Evaluation
m ∧ q	F ∧ q = F

Note: Regardless of the value of q, when m = F the conjunction is always F.

Step 4: We evaluate the biconditional

T ↔ F = F

Answer:

V(A) = F

Observation: This exercise demonstrates that sometimes it is not necessary to know all variables to determine the final value. The value of q remains undetermined, but it does not affect the result.

Exercise 17

If V[(q → p) → (r ∨ p)] = F, find the truth value of each of the following propositions:

• A = (p ∧ x) → (m ↔ y)
• B = (q → n) ∨ (x ∧ y)
• C = (r ↔ p) → (s ∧ q)
• D = [(s → p) ∨ (n → r)] → (x ∨ ¬x)

Solution

Step 1: We deduce the values of p, q, r

If (q → p) → (r ∨ p) = F, we need T → F:

Expression	Condition	Values
r ∨ p = F	Disjunction F	r = F, p = F
q → p = T	q → F = T	q = F

Summary: p = F, q = F, r = F

Step 2: We evaluate A = (p ∧ x) → (m ↔ y)

Subexpression	Evaluation
p ∧ x	F ∧ x = F
F → (m ↔ y)	T

Antecedent F → conditional always T

A = T ✓

Step 3: We evaluate B = (q → n) ∨ (x ∧ y)

Subexpression	Evaluation
q → n	F → n = T
T ∨ (x ∧ y)	T

B = T ✓

Step 4: We evaluate C = (r ↔ p) → (s ∧ q)

Subexpression	Evaluation
r ↔ p	F ↔ F = T
s ∧ q	s ∧ F = F
T → F	F

C = F ✗

Step 5: We evaluate D = [(s → p) ∨ (n → r)] → (x ∨ ¬x)

Subexpression	Evaluation
x ∨ ¬x	T (tautology)
Anything → T	T

x ∨ ¬x is the Law of Excluded Middle (always true)

D = T ✓

Answer:

Proposition	Value
A	T
B	T
C	F
D	T

Observation: The variables x, y, m, n, s remain undetermined, but they do not affect the final result due to the properties of the connectives.

Section II: Truth Tables

This section covers truth tables, including how to evaluate compound propositions and identify tautologies, contradictions, and contingencies.

Quick Reference Guide

What is a truth table?

A truth table shows every possible truth value of a logical expression based on all combinations of its component propositions.

Molecular Schemas and Main Connectives

A molecular schema combines propositional variables (p, q, r…) with logical connectives. We name the schema after its main connective—the one evaluated last:

Schema	Main Connective	Name
p ∧ q	∧	Conjunction
p ∨ q	∨	Disjunction
p → q	→	Conditional
(p ∧ q) → r	→	Conditional
¬(p ∨ q)	¬	Negation

Components of a Truth Table

Component	Description
Input columns	The first columns containing the atomic propositions (p, q, r…)
Helper columns	Intermediate columns for subexpressions
Main column	The final column showing the result of the complete expression

Number of Rows

\( \text{Rows} = 2^n \) where n = number of distinct propositions

Variables	Rows
1 (p)	2
2 (p, q)	4
3 (p, q, r)	8
4 (p, q, r, s)	16

How to Fill Variable Columns

With n variables, each column follows a specific alternating pattern:

Column	Pattern
1st (leftmost)	Upper half T, lower half F
2nd	Alternates in blocks of n/2
Last (rightmost)	Alternates T, F, T, F… one by one

Example with 3 variables (p, q, r):

Row	p	q	r
1	T	T	T
2	T	T	F
3	T	F	T
4	T	F	F
5	F	T	T
6	F	T	F
7	F	F	T
8	F	F	F

Classification of Propositions

Type	Main Column	Example
Tautology	All T (always true)	p ∨ ¬p
Contradiction	All F (always false)	p ∧ ¬p
Contingency	Mix of T and F	p → q

Order of Evaluation (Operator Precedence)

Priority	Operator	Name
1 (highest)	( )	Parentheses
2	¬	Negation
3	∧	Conjunction
4	∨	Disjunction
5	→	Conditional
6 (lowest)	↔	Biconditional

Truth Tables for Basic Connectives

Negation (¬p)

p	¬p
T	F
F	T

Conjunction (p ∧ q) → Only T when both are T

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

Disjunction (p ∨ q) → Only F when both are F

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

Conditional (p → q) → Only F when T → F

p	q	p → q
T	T	T
T	F	F
F	T	T
F	F	T

Biconditional (p ↔ q) → T when both have the same value

p	q	p ↔ q
T	T	T
T	F	F
F	T	F
F	F	T

How to Build a Truth Table

1. Identify all distinct propositions (p, q, r…) and the main connective
2. Calculate the number of rows needed (2ⁿ)
3. Set up columns for variables, subexpressions, and the final result
4. Fill in variable columns with all possible T/F combinations
5. Evaluate subexpressions from innermost to outermost, following precedence
6. Compute the main column (main connective)
7. Classify the result: Tautology, Contradiction, or Contingency

Truth Value Notation: V(p) and #V(p)

Notation	Meaning
\( V(p) = \mathrm{T} \)	The truth value of p is True
\( V(p) = \mathrm{F} \)	The truth value of p is False
\( \# V(p) = 1 \)	Binary representation of True
\( \# V(p) = 0 \)	Binary representation of False

Arithmetic formulas for connectives:

Connective	Formula
Negation	\( \# V(\neg p) = 1 – \# V(p) \)
Conjunction	\( \# V(p \land q) = \# V(p) \cdot \# V(q) \)
Disjunction	\( \# V(p \lor q) = \# V(p) + \# V(q) – \# V(p) \cdot \# V(q) \)

Worked Examples

Exercise 1

Build the truth table and classify:

\( \neg p \land q \)

Solution

Step 1: Count variables and determine row count

• Variables: p, q → n = 2
• Rows needed: 2² = 4

Step 2: Find the main connective

• Main connective: Conjunction (∧)
• Structure: (¬p) ∧ (q)

Step 3: List subexpressions to evaluate

1. ¬p (negate p first)
2. ¬p ∧ q (then apply conjunction)

Step 4: Build the truth table

p	q	¬p	¬p ∧ q
T	T	F	F
T	F	F	F
F	T	T	T
F	F	T	F

Step 5: Classify the result

The main column shows both T and F values → CONTINGENCY

Takeaway: This proposition is true only when p is false AND q is true (row 3).

Exercise 2

Build the truth table and classify:

\( \neg(p \rightarrow \neg q) \)

Solution

Step 1: Count variables and determine row count

• Variables: p, q → n = 2
• Rows needed: 2² = 4

Step 2: Find the main connective

• Main connective: Negation (¬)
• Structure: ¬(p → ¬q)

Step 3: List subexpressions (work from inside out)

1. ¬q (negate q)
2. p → ¬q (apply conditional)
3. ¬(p → ¬q) (negate the whole thing)

Step 4: Build the truth table

p	q	¬q	p → ¬q	¬(p → ¬q)
T	T	F	F	T
T	F	T	T	F
F	T	F	T	F
F	F	T	T	F

Step 5: Classify the result

The main column shows both T and F values → CONTINGENCY

Fun fact: By the negation of conditional law: ¬(p → ¬q) ≡ p ∧ q

Exercise 3

Prove that the given proposition is a tautology:

\( [(p \lor \neg q) \land q] \rightarrow p \)

Solution

Step 1: Identify the variables and calculate the number of rows

• Variables: p, q → n = 2
• Number of rows: 2² = 4

Step 2: Identify the main connective

• Main connective: Conditional (→)
• Antecedent: (p ∨ ¬q) ∧ q
• Consequent: p

Step 3: Identify the subexpressions to evaluate

1. ¬q
2. A = p ∨ ¬q, first evaluation
3. (p ∨ ¬q) ∧ q (antecedent), second evaluation
4. [(p ∨ ¬q) ∧ q] → p (final conditional), third and final evaluation

Step 4: Build the truth table

p	q	¬q	A = p ∨ ¬q	A ∧ q	[A ∧ q] → p
T	T	F	T	T	T → T = T
T	F	T	T	F	F → T = T
F	T	F	F	F	F → F = T
F	F	T	T	F	F → F = T

Step 5: Classification

All values in the main column are T → TAUTOLOGY ✓

Analysis: The antecedent is only T when p=T and q=T. In that case, the consequent p is also T.

Exercise 4

Prove that the proposition \( [(\neg p \lor q) \land \neg q] \rightarrow \neg p \) is a tautology.

Solution

Step 1: Identify the variables and calculate the number of rows

• Variables: p, q → n = 2
• Number of rows: 2² = 4

Step 2: Identify the main connective

• Main connective: Conditional (→)
• Antecedent: (¬p ∨ q) ∧ ¬q
• Consequent: ¬p

Step 3: Identify the subexpressions to evaluate

1. ¬p, ¬q, first evaluation (negations)
2. ¬p ∨ q, second evaluation (disjunction)
3. (¬p ∨ q) ∧ ¬q (antecedent), third evaluation (conjunction)
4. [(¬p ∨ q) ∧ ¬q] → ¬p, final result, fourth and final evaluation (conditional)

Step 4: Build the truth table

\begin{array}{|c|c|c|c|l|} \hline
p & q & \neg{p} & \neg q & [ ( \neg p \color{blue}{∨} q ) \color{green}{∧} \neg q ] \color{red}{ \rightarrow } \neg p \\ \hline
\mathrm{T} & \mathrm{T} & \mathrm{F} & \mathrm{F} & \hspace{20pt} \color{blue}{ \mathrm{T} } \hspace{13pt} \color{green}{ \mathrm{ F } } \hspace{20pt} \color{red}{ \mathrm{ T } } \\ \hline
\mathrm{T} & \mathrm{F} & \mathrm{F} & \mathrm{T} & \hspace{20pt} \color{blue}{ \mathrm{F} } \hspace{13pt} \color{green}{ \mathrm{ F } } \hspace{20pt} \color{red}{ \mathrm{ T } } \\ \hline
\mathrm{F} & \mathrm{T} & \mathrm{F} & \mathrm{F} & \hspace{20pt} \color{blue}{ \mathrm{T} } \hspace{13pt} \color{green}{ \mathrm{F } } \hspace{20pt} \color{red}{ \mathrm{ T } } \\ \hline
\mathrm{F} & \mathrm{F} & \mathrm{F} & \mathrm{T} & \hspace{20pt} \color{blue}{ \mathrm{T} } \hspace{13pt} \color{green}{ \mathrm{F } } \hspace{20pt} \color{red}{ \mathrm{ T } } \\ \hline
\end{array}

Step 5: Classification

All values in the main column are T → TAUTOLOGY ✓

Note: When the antecedent is F, the conditional is always T (vacuous truth).

Exercise 5

Build the truth table and classify:

\( (p \land q) \rightarrow (p \lor q) \)

Solution

Step 1: Identify the variables and calculate the number of rows

• Variables: p, q → n = 2
• Number of rows: 2² = 4

Step 2: Identify the main connective

• Main connective: Conditional (→)
• Antecedent: p ∧ q
• Consequent: p ∨ q

Step 3: Build the truth table

p	q	p ∧ q	p ∨ q	(p ∧ q) → (p ∨ q)
T	T	T	T	T
T	F	F	T	T
F	T	F	T	T
F	F	F	F	T

Step 4: Classification

All values in the main column are T → TAUTOLOGY

Why it works: If both p and q are true (conjunction), then at least one of them is true (disjunction). Conjunction is stricter than disjunction.

Exercise 6

Build the truth table and classify:

\( \neg(p \land q) \lor \neg(q \leftrightarrow p) \)

Solution

Step 1: Identify the variables and calculate the number of rows

• Variables: p, q → n = 2
• Number of rows: 2² = 4

Step 2: Identify the main connective

• Main connective: Disjunction (∨)
• Structure: ¬(p ∧ q) ∨ ¬(q ↔ p)

Step 3: Identify the subexpressions to evaluate

1. A = p ∧ q and its negation
2. B = q ↔ p and its negation
3. ¬(p ∧ q) ∨ ¬(q ↔ p) = ¬A ∨ ¬B final disjunction

Step 4: Build the truth table

p	q	A = p ∧ q	¬A	B = q ↔ p	¬B	¬A ∨ ¬B
T	T	T	F	T	F	F
T	F	F	T	F	T	T
F	T	F	T	F	T	T
F	F	F	T	T	F	T

Step 5: Classification

The main column has a mix of T and F → CONTINGENCY

Analysis: Only F when p = T and q = T.

Exercise 7

Evaluate the truth table of the compound proposition (First De Morgan’s Law):

\( \neg(p \land q) \leftrightarrow (\neg p \lor \neg q) \)

Solution

Step 1: Identify the variables and calculate the number of rows

• Variables: p, q → n = 2
• Number of rows: 2² = 4

Step 2: Identify the main connective

• Main connective: Biconditional (↔)
• Left side: ¬(p ∧ q) = ¬A
• Right side: (¬p ∨ ¬q) = B

Step 3: Build the truth table

\begin{array}{|c|c|l|c|c|c|l|l|} \hline
p & q & A & \color{blue}{ \neg \mathrm{A} } & \neg p & \neg q & \color{green}{ \mathrm{B} } & \neg A \color{red}{ \leftrightarrow } B \\ \hline
T & T & T & F & F & F & F & \hspace{17pt} T \\ \hline
T & F & F & T & F & T & T & \hspace{17pt} T \\ \hline
F & T & F & T & T & F & T & \hspace{17pt} T \\ \hline
F & F & F & T & T & T & T & \hspace{17pt} T \\ \hline
\end{array}

Step 4: Classification

All values are T → TAUTOLOGY

Note: This is De Morgan’s First Law: ¬(p ∧ q) ≡ ¬p ∨ ¬q

Exercise 8

Verify that the following propositions are contradictions:

a) \( (p \land q) \land \neg(p \lor q) \)

b) \( \neg[p \lor (\neg p \lor \neg q)] \)

Solution

Part a) \( (p \land q) \land \neg(p \lor q) \)

Quick analysis: This expression says “p and q are both true” AND “neither p nor q is true.” That’s clearly self-contradictory! Let’s verify with a truth table:

p	q	p ∧ q	p ∨ q	¬(p ∨ q)	(p ∧ q) ∧ ¬(p ∨ q)
T	T	T	T	F	T ∧ F = F
T	F	F	T	F	F ∧ F = F
F	T	F	T	F	F ∧ F = F
F	F	F	F	T	F ∧ T = F

Classification: All F → CONTRADICTION ✓

Part b) \( \neg[p \lor (\neg p \lor \neg q)] \)

We could prove this algebraically, but let’s use a truth table. Setting A = ¬p ∨ ¬q, the expression becomes ¬(p ∨ A):

p	q	¬p	¬q	A = ¬p ∨ ¬q	p ∨ A	¬(p ∨ A)
T	T	F	F	F	T	F
T	F	F	T	T	T	F
F	T	T	F	T	T	F
F	F	T	T	T	T	F

Classification: All F → CONTRADICTION ✓

Why this happens: The inner expression simplifies to p ∨ ¬p (a tautology). Negating a tautology always yields a contradiction.

Exercise 9

Verify this is a contingency (3 variables):

\( [\neg p \land (q \lor r)] \longleftrightarrow [(p \lor r) \land q] \)

Solution

Step 1: Identify the variables and calculate the number of rows

• Variables: p, q, r → n = 3
• Number of rows: 2³ = 8 rows

Step 2: Identify the main connective

• Main connective: Biconditional (↔)
• Left side: ¬p ∧ (q ∨ r)
• Right side: (p ∨ r) ∧ q

Step 3: Build the truth table

• Left side

p	q	r	¬p	q∨r	¬p∧(q∨r)
T	T	T	F	T	F
T	T	F	F	T	F
T	F	T	F	T	F
T	F	F	F	F	F
F	T	T	T	T	T
F	T	F	T	T	T
F	F	T	T	T	T
F	F	F	T	F	F

• Right side

p	q	r	p∨r	(p∨r)∧q
T	T	T	T	T
T	T	F	T	T
T	F	T	T	F
T	F	F	T	F
F	T	T	T	T
F	T	F	F	F
F	F	T	T	F
F	F	F	F	F

• Main connective

¬p∧(q∨r)	(p∨r)∧q	¬p∧(q∨r) ↔ (p∨r)∧q
F	T	F
F	T	F
F	F	T
F	F	T
T	T	T
T	F	F
T	F	F
F	F	T

Step 4: Classification

Mix of T and F values → CONTINGENCY ✓

Note: With 3 variables, things get more complex. The outcome depends heavily on specific value combinations.

Exercise 10

Check if these two propositions are logically equivalent (3 variables):

\( [p \rightarrow (r \lor \neg q)] \) and \( [(q \rightarrow \neg p) \lor (\neg r \rightarrow \neg p)] \)

Solution

Step 1: Variables: p, q, r → 8 rows needed

Step 2: To check for equivalence, we’ll build both tables and compare their main columns.

Step 3: Build the table

Starting with p→(r∨¬q)

p	q	r	¬p	¬q	¬r	r∨¬q	p→(r∨¬q)
T	T	T	F	F	F	T	T
T	T	F	F	F	T	F	F
T	F	T	F	T	F	T	T
T	F	F	F	T	T	T	T
F	T	T	T	F	F	T	T
F	T	F	T	F	T	F	T
F	F	T	T	T	F	T	T
F	F	F	T	T	T	T	T

Now with (q→¬p)∨(¬r→¬p)

p	q	r	¬p	¬q	¬r	q→¬p	¬r→¬p	(q→¬p)∨(¬r→¬p)
T	T	T	F	F	F	F	T	T
T	T	F	F	F	T	F	F	F
T	F	T	F	T	F	T	T	T
T	F	F	F	T	T	T	F	T
F	T	T	T	F	F	T	T	T
F	T	F	T	F	T	T	T	T
F	F	T	T	T	F	T	T	T
F	F	F	T	T	T	T	T	T

Step 4: Compare the main columns

Row	p→(r∨¬q)	(q→¬p)∨(¬r→¬p)
1	T	T
2	F	F
3	T	T
4	T	T
5	T	T
6	T	T
7	T	T
8	T	T

Conclusion: The columns match exactly → Yes, these propositions are equivalent ✓

Exercise 11

Build the truth table for the following proposition (complex nesting):

\( \neg{[\neg p \lor (\neg q \rightarrow p)] \lor [(p \leftrightarrow \neg q) \rightarrow (q \land \neg p)]} \)

Solution

Step 1: Identify the variables: p, q → n = 2 → 4 rows

Step 2: This is a negation of a disjunction of two parts:

• A = ¬p ∨ (¬q → p)
• B = (p ↔ ¬q) → (q ∧ ¬p)
• Complete expression: ¬(A ∨ B)

Step 3: Evaluate step by step

Starting with schema A

p	q	¬p	¬q	¬q→p	A=¬p∨(¬q→p)
T	T	F	F	T	T
T	F	F	T	T	T
F	T	T	F	F	T
F	F	T	T	F	T

Now with B

p	q	¬p	¬q	p↔¬q	q∧¬p	\( \mathrm{ B=(p↔¬q)→(q∧¬p) } \)
T	T	F	F	F	F	T
T	F	F	T	T	F	F
F	T	T	F	F	T	T
F	F	T	T	T	F	F

Now we evaluate ¬(A ∨ B)

A	B	A∨B	¬(A∨B)
T	T	T	F
T	F	T	F
T	T	T	F
T	F	T	F

Step 4: Classification

All values are F → CONTRADICTION

Note: Even with just 2 variables, the 5 levels of nesting make this a challenging problem.

Exercise 12

We define the following operators:

Operator	Definition
p # q	¬p ∨ ¬q
p θ q	¬(p → q)

Evaluate the truth table of (p → q) # (p θ q) and classify it.

Solution

Step 1: First, we build the tables for the custom operators.

Table for the # operator (p # q ≡ ¬p ∨ ¬q):

p	q	¬p	¬q	p # q
T	T	F	F	F
T	F	F	T	T
F	T	T	F	T
F	F	T	T	T

Note: Only F when both propositions are T.

Table for the θ operator (p θ q ≡ ¬(p → q)):

p	q	p → q	p θ q
T	T	T	F
T	F	F	T
F	T	T	F
F	F	T	F

Note: Only T when p is T and q is F (it’s the negation of the conditional).

Step 2: Now we evaluate (p → q) # (p θ q)

p	q	p → q	p θ q	(p → q) # (p θ q)
T	T	T	F	¬T ∨ ¬F = F ∨ T = T
T	F	F	T	¬F ∨ ¬T = T ∨ F = T
F	T	T	F	¬T ∨ ¬F = F ∨ T = T
F	F	T	F	¬T ∨ ¬F = F ∨ T = T

Step 3: Classification

All values in the main column are T → Tautology ✓

Section III: Logical Equivalences

This section covers logical equivalences, including how to simplify propositions, apply algebraic transformations, and use logical laws.

Quick Reference Guide

What is a logical equivalence?

Two propositions are logically equivalent (p ≡ q) when they share exactly the same truth values across all possible variable combinations.

We say p ≡ q if and only if p ↔ q is a tautology.

Why do equivalences matter?

1. Simplify complex logical expressions
2. Prove two expressions are equal without truth tables
3. Transform expressions into more useful forms
4. Validate logical arguments

Summary Table of the 18 Equivalence Laws

1. Identity:
   p ∧ T ≡ p
   p ∨ F ≡ p
2. Domination:
   p ∨ T ≡ T
   p ∧ F ≡ F
3. Idempotence:
   p ∧ p ≡ p
   p ∨ p ≡ p
4. Double Negation:
   ¬(¬p) ≡ p
5. Complement:
   p ∨ ¬p ≡ T
   p ∧ ¬p ≡ F
6. Commutativity:
   p ∧ q ≡ q ∧ p
   p ∨ q ≡ q ∨ p
7. Associativity:
   (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
8. Distributivity:
   p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
9. Absorption:
   p ∧ (p ∨ q) ≡ p
   p ∨ (p ∧ q) ≡ p
10. De Morgan
    ¬(p ∧ q) ≡ ¬p ∨ ¬q
    ¬(p ∨ q) ≡ ¬p ∧ ¬q
11. Material Implication
    p → q ≡ ¬p ∨ q
12. Contraposition
    p → q ≡ ¬q → ¬p
13. Negation of Conditional
    ¬(p → q) ≡ p ∧ ¬q
14. Biconditional
    p ↔ q ≡ (p → q) ∧ (q → p)
15. Biconditional (alt)
    p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
16. Negation of Biconditional
    ¬(p ↔ q) ≡ p ⊻ q
17. Equivalence of Negations
    p ↔ q ≡ ¬p ↔ ¬q
18. Exportation
    (p ∧ q) → r ≡ p → (q → r)

De Morgan’s Laws (essential!)

Quick tip: To negate an expression, flip ∧ to ∨ (and vice versa) and negate each part.

Formula	In words
\( \mathrm{ ¬(p ∧ q) ≡ ¬p ∨ ¬q } \)	“Not (p AND q)” equals “Not p OR Not q”
¬(p ∨ q) ≡ ¬p ∧ ¬q	“Not (p OR q)” equals “Not p AND Not q”

Extending to more propositions:

• ¬(p ∧ q ∧ r) ≡ ¬p ∨ ¬q ∨ ¬r
• ¬(p ∨ q ∨ r) ≡ ¬p ∧ ¬q ∧ ¬r

Conditional Equivalences

Law	Formula	Interpretation
Material Implication	p → q ≡ ¬p ∨ q	“If p then q” = “Not p, OR q”
Contraposition	p → q ≡ ¬q → ¬p	The contrapositive has the same truth value
Negation of Conditional	¬(p → q) ≡ p ∧ ¬q	Assert the antecedent and negate the consequent
Using negation	\( \mathrm{ p → q ≡ ¬(p ∧ ¬q) } \)	Alternative form

Biconditional Equivalences

Law	Formula	Interpretation
Double Conditional	p ↔ q ≡ (p → q) ∧ (q → p)	“p if and only if q”
Alternative Form	\( \mathrm{ p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q) } \)	True when both are T or both are F
Negation	¬(p ↔ q) ≡ p ⊻ q	The negation is exclusive disjunction (XOR)
Equivalent Negations	p ↔ q ≡ ¬p ↔ ¬q	Negating both sides doesn’t change result

Exportation Law

Law	Formula
Exportation	(p ∧ q) → r ≡ p → (q → r)

Example: “If (you study AND practice), you pass” ≡ “If you study, then (if you practice, you pass)”

How to Simplify Expressions

1. Find the main connective
2. Convert conditionals and biconditionals via material implication
3. Apply De Morgan to push negations in or pull them out
4. Use distributive, absorption, or complement laws as needed
5. Reduce step by step until you reach the simplest form
6. Check with a truth table if you’re unsure

Worked Examples

Exercise 1

Simplify:

\( [\neg(p \lor q) \land r] \lor [(p \lor q) \land r] \)

Solution

Step	Expression	Law Applied
1	\( [\neg(p \lor q) \land r] \lor [(p \lor q) \land r] \)	Original expression
2	\( [\neg(p \lor q) \lor (p \lor q)] \land r \)	Distributive (factor out r)
3	\( T \land r \)	Complement: A ∨ ¬A ≡ T
4	\( r \)	Identity

Result: \( [\neg(p \lor q) \land r] \lor [(p \lor q) \land r] \equiv r \)

Takeaway: Variables p and q are irrelevant here—the expression depends only on r.

Exercise 2

Find a simpler equivalent form of the following schemas:

a) \( \neg[p \lor (p \land q)] \)

b) \( [(p \lor q) \land (q \lor r)] \land \neg q \)

c) \( \neg[\neg p \rightarrow (p \land q)] \)

Solution

Part a) \( \neg[p \lor (p \land q)] \)

Step	Expression	Law Applied
1	\( \neg[p \lor (p \land q)] \)	Original expression
2	\( \neg p \)	Absorption: p ∨ (p ∧ q) ≡ p

Result: \( \neg[p \lor (p \land q)] \equiv \neg p \)

Why? Absorption tells us p ∨ (p ∧ q) ≡ p. Negating that gives ¬p.

Part b) \( [(p \lor q) \land (q \lor r)] \land \neg q \)

Step	Expression	Law Applied
1	\( [(p \lor q) \land (q \lor r)] \land \neg q \)	Original expression
2	\( (p \lor q) \land \neg q \land (q \lor r) \land \neg q \)	Associativity

Simplifying (p ∨ q) ∧ ¬q:

• = (p ∧ ¬q) ∨ (q ∧ ¬q) — Distributive
• = (p ∧ ¬q) ∨ F — Complement
• = p ∧ ¬q — Identity

Simplifying (q ∨ r) ∧ ¬q:

• = (q ∧ ¬q) ∨ (r ∧ ¬q) — Distributive
• = F ∨ (r ∧ ¬q) — Complement
• = r ∧ ¬q — Identity

Step	Expression	Law Applied
3	\( (p \land \neg q) \land (r \land \neg q) \)	Result of simplifications
4	\( p \land r \land \neg q \)	Associativity and Idempotence: ¬q ∧ ¬q ≡ ¬q

Result: \( [(p \lor q) \land (q \lor r)] \land \neg q \equiv p \land r \land \neg q \)

Part c) \( \neg[\neg p \rightarrow (p \land q)] \)

Step	Expression	Law Applied
1	\( \neg[\neg p \rightarrow (p \land q)] \)	Original expression
2	\( \neg[p \lor (p \land q)] \)	Material Implication: ¬p → B ≡ ¬(¬p) ∨ B ≡ p ∨ B
3	\( \neg p \)	Absorption: p ∨ (p ∧ q) ≡ p

Result: \( \neg[\neg p \rightarrow (p \land q)] \equiv \neg p \)

Exercise 3

Find the simplest schema for the proposition:

\( [(p \land q) \lor (p \land \neg q)] \lor (\neg p \land \neg q) \)

Solution

Game plan: The first two terms share variable p, so we’ll:

1. Factor out p using reverse distributive
2. Simplify with complement
3. Apply distributive for the final result

Step 1: Apply Reverse Distributive to the first two terms

Recall: (A ∧ B) ∨ (A ∧ C) ≡ A ∧ (B ∨ C)

\( [(p \land q) \lor (p \land \neg q)] \lor (\neg p \land \neg q) \)

\( = [p \land (q \lor \neg q)] \lor (\neg p \land \neg q) \)

Step 2: Apply Complement and Identity

Recall: q ∨ ¬q ≡ T (Law of Excluded Middle)

\( = [p \land T] \lor (\neg p \land \neg q) \)

\( = p \lor (\neg p \land \neg q) \) — by Identity: A ∧ T ≡ A

Step 3: Apply Distributive

Recall: A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)

\( = (p \lor \neg p) \land (p \lor \neg q) \)

Step 4: Apply Complement and Identity again

\( = T \land (p \lor \neg q) \) — by Complement: p ∨ ¬p ≡ T

\( = p \lor \neg q \) — by Identity: T ∧ A ≡ A

Result: \( [(p \land q) \lor (p \land \neg q)] \lor (\neg p \land \neg q) \equiv p \lor \neg q \)

Takeaway: Factoring out p from the first two terms gave us q ∨ ¬q (always true), which collapsed nicely.

Exercise 4

Find an equivalent proposition to:

\( P = [(\neg p \land q) \rightarrow (r \land \neg r)] \land (\neg q) \)

Solution

Game plan: Notice the consequent is r ∧ ¬r—a contradiction (always F). We’ll:

1. Eliminate the conditional via material implication
2. Simplify the contradiction with complement
3. Apply De Morgan and absorption to finish

Step 1: Apply Material Implication

Recall: A → B ≡ ¬A ∨ B

\( = [\neg(\neg p \land q) \lor (r \land \neg r)] \land (\neg q) \)

Step 2: Apply Complement to the contradiction

Recall: r ∧ ¬r ≡ F (Law of Contradiction)

\( = [\neg(\neg p \land q) \lor F] \land (\neg q) \)

\( = \neg(\neg p \land q) \land (\neg q) \) — by Identity: A ∨ F ≡ A

Step 3: Apply De Morgan

Recall: ¬(A ∧ B) ≡ ¬A ∨ ¬B

\( = (p \lor \neg q) \land (\neg q) \)

Step 4: Apply Absorption

Recall: (A ∨ B) ∧ A ≡ A (term A “absorbs” the disjunction)

With A = ¬q and B = p:

\( = \neg q \)

Result: \( [(\neg p \land q) \rightarrow (r \land \neg r)] \land (\neg q) \equiv \neg q \)

Key insight: When a conditional has a contradiction as its consequent, we’re saying “if the antecedent is true, something impossible happens”—which means the antecedent must be false. This is the heart of proof by contradiction.

Exercise 5

Find the simplest schema for the proposition:

\( \neg[\neg(p \land q) \rightarrow \neg q] \lor p \)

Solution

Game plan: This has the form ¬[A → B] ∨ p. We’ll:

1. Apply negation of conditional: ¬(A → B) ≡ A ∧ ¬B
2. Use De Morgan to handle negations
3. Reduce with distributive and complement

Step 1: Apply Negation of Conditional to the main bracket

Recall: ¬(A → B) ≡ A ∧ ¬B (assert the antecedent and negate the consequent)

The antecedent is ¬(p ∧ q) and the consequent is ¬q:

\( \neg[\neg(p \land q) \rightarrow \neg q] \lor p \)

\( = [\neg(p \land q) \land \neg(\neg q)] \lor p \)

\( = [\neg(p \land q) \land q] \lor p \) — by Double Negation

Step 2: Apply De Morgan to ¬(p ∧ q)

Recall: ¬(p ∧ q) ≡ ¬p ∨ ¬q

\( = [(¬p \lor ¬q) \land q] \lor p \)

Step 3: Apply Distributive inside the bracket

Recall: (A ∨ B) ∧ C ≡ (A ∧ C) ∨ (B ∧ C)

\( = [(¬p \land q) \lor (¬q \land q)] \lor p \)

\( = [(¬p \land q) \lor F] \lor p \) — by Complement: ¬q ∧ q ≡ F

\( = (¬p \land q) \lor p \) — by Identity: A ∨ F ≡ A

Step 4: Apply Distributive again

Recall: A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)

\( = (p \lor ¬p) \land (p \lor q) \) — reordering by Commutativity

\( = T \land (p \lor q) \) — by Complement: p ∨ ¬p ≡ T

\( = p \lor q \) — by Identity: T ∧ A ≡ A

Result: \( \neg[\neg(p \land q) \rightarrow \neg q] \lor p \equiv p \lor q \)

Takeaway: We went from 5 connectives down to just one disjunction. Starting with negation of conditional was the key—it simplifies faster than converting with material implication first.

Exercise 6

Check if these propositions are equivalent: \( [(\neg p \lor q) \lor (\neg r \land \neg p)] \) and \( \neg q \rightarrow \neg p \)

Solution

Step 1: Variables: p, q, r → 8 rows needed

Step 2: Key observation: The second expression \( \neg q \rightarrow \neg p \) doesn’t involve r, so its value depends only on p and q.

Step 3: Let’s simplify the first expression algebraically:

• \( (\neg p \lor q) \lor (\neg r \land \neg p) \)
• By absorption: \( \neg p \lor q \lor (\neg r \land \neg p) = \neg p \lor q \) (\( \neg p \) absorbs \( \neg r \land \neg p \))
• By contraposition: \( \neg p \lor q \equiv p \rightarrow q \equiv \neg q \rightarrow \neg p \)

Step 4: We verify with a truth table:

p	q	r	¬p	¬q	¬r	¬p∨q	¬r∧¬p	(¬p∨q)∨(¬r∧¬p)	¬q→¬p
T	T	T	F	F	F	T	F	T	T
T	T	F	F	F	T	T	F	T	T
T	F	T	F	T	F	F	F	F	F
T	F	F	F	T	T	F	F	F	F
F	T	T	T	F	F	T	F	T	T
F	T	F	T	F	T	T	T	T	T
F	F	T	T	T	F	T	F	T	T
F	F	F	T	T	T	T	T	T	T

Conclusion: The columns match exactly → Yes, they’re equivalent ✓

\( (\neg p \lor q) \lor (\neg r \land \neg p) \equiv \neg q \rightarrow \neg p \)

Takeaway: Variable r is irrelevant in the first expression—it simplifies right out.

Exercise 7

Simplify:

\( \{[(p \rightarrow q) \land p] \rightarrow q\} \land \{[(p \rightarrow q) \land \neg q] \rightarrow \neg p\} \)

Solution

The setup: This expression combines two classic tautologies:

• Modus Ponens: [(p → q) ∧ p] → q
• Modus Tollens: [(p → q) ∧ ¬q] → ¬p
• Step: 1
  • Expression: \( {[(p \rightarrow q) \land p] \rightarrow q} \land {[(p \rightarrow q) \land \neg q] \rightarrow \neg p} \)
  • Law Applied: Original expression
• Step: 2
  • Expression: \( {[(\neg p \lor q) \land p] \rightarrow q} \land {[(\neg p \lor q) \land \neg q] \rightarrow \neg p} \)
  • Law Applied: Material Implication: p→q ≡ ¬p∨q

Let’s simplify each part:

Left part: (¬p ∨ q) ∧ p

• = (¬p ∧ p) ∨ (q ∧ p) — Distributive
• = F ∨ (q ∧ p) — Complement
• = q ∧ p — Identity

Right part: (¬p ∨ q) ∧ ¬q

• = (¬p ∧ ¬q) ∨ (q ∧ ¬q) — Distributive
• = (¬p ∧ ¬q) ∨ F — Complement
• = ¬p ∧ ¬q — Identity
• Step: 3
  • Expression: \( {[q \land p] \rightarrow q} \land {[\neg p \land \neg q] \rightarrow \neg p} \)
  • Law Applied: Result of simplifications
• Step: 4
  • Expression: \( {\neg(q \land p) \lor q} \land {\neg(\neg p \land \neg q) \lor \neg p} \)
  • Law Applied: Material Implication
• Step: 5
  • Expression: \( {(\neg q \lor \neg p) \lor q} \land {(p \lor q) \lor \neg p} \)
  • Law Applied: De Morgan
• Step: 6
  • Expression: \( {T \lor \neg p} \land {T \lor q} \)
  • Law Applied: Complement: (¬q∨q)=T, (p∨¬p)=T
• Step: 7
  • Expression: \( T \land T \)
  • Law Applied: Domination: T∨A ≡ T
• Step: 8
  • Expression: \( T \)
  • Law Applied: Identity

Result: \( \equiv T \) (Tautology)

Why this matters: This confirms that both Modus Ponens and Modus Tollens are rock-solid inference rules.

Exercise 8

Using logical laws, simplify the following compound proposition:

\( A = [\neg(p \rightarrow q) \rightarrow \neg(q \rightarrow p)] \land [p \lor q] \)

Solution

Game plan:

1. Handle ¬(p → q) and ¬(q → p) with negation of conditional
2. Convert the main conditional via material implication
3. Reduce using absorption and distributive

Step 1: Apply Negation of Conditional

Recall: ¬(A → B) ≡ A ∧ ¬B

Expression	Transformation
¬(p → q)	= p ∧ ¬q
¬(q → p)	= q ∧ ¬p

\( A = [(p \land \neg q) \rightarrow (q \land \neg p)] \land [p \lor q] \)

Step 2: Apply Material Implication to the conditional

Recall: A → B ≡ ¬A ∨ B

\( = [\neg(p \land \neg q) \lor (q \land \neg p)] \land [p \lor q] \)

Step 3: Apply De Morgan to ¬(p ∧ ¬q)

Recall: ¬(A ∧ B) ≡ ¬A ∨ ¬B

\( \neg(p \land \neg q) = \neg p \lor q \) — also applying Double Negation

\( = [(\neg p \lor q) \lor (q \land \neg p)] \land [p \lor q] \)

Step 4: Apply Absorption to the first part

Recall: A ∨ (A ∧ B) ≡ A

Reordering: (¬p ∨ q) ∨ (q ∧ ¬p) = (q ∨ ¬p) ∨ (q ∧ ¬p)

Since (q ∧ ¬p) is “absorbed” by (q ∨ ¬p), by absorption:

\( = (q \lor \neg p) \land (p \lor q) \)

Step 5: Apply Reverse Distributive

Recall: (A ∨ B) ∧ (A ∨ C) ≡ A ∨ (B ∧ C)

Reordering: (q ∨ ¬p) ∧ (q ∨ p) = q ∨ (¬p ∧ p)

\( = q \lor (\neg p \land p) \)

Step 6: Apply Complement and Identity

\( = q \lor F \) — by Complement: ¬p ∧ p ≡ F

\( = q \) — by Identity: A ∨ F ≡ A

Result: \( [\neg(p \rightarrow q) \rightarrow \neg(q \rightarrow p)] \land [p \lor q] \equiv q \)

Takeaway: A complex expression with nested conditionals collapsed to a single variable. The winning move? Hit it with negation of conditional first, then use absorption.

Exercise 9

Transform the following compound proposition to its simplest conditional equivalent:

\( P = (\neg p \leftrightarrow q) \veebar (p \rightarrow q) \)

Solution

Key insight: ¬p ↔ q ≡ p ⊕ q (negating one side of a biconditional gives you XOR)

Step	Expression	Law applied
1	\( (\neg p \leftrightarrow q) \veebar (p \rightarrow q) \)	Original expression
2	\( (p \veebar q) \veebar (\neg p \lor q) \)	Equivalence ¬p↔q ≡ p⊻q and Material Implication
3	\( [(p \veebar q) \land (p \land \neg q)] \lor [(p \leftrightarrow q) \land (\neg p \lor q)] \)	XOR Definition: A⊻B ≡ (A∧¬B)∨(¬A∧B)
4	\( (p \land \neg q) \lor (p \land q) \lor (\neg p \land \neg q) \)	Absorption and simplification
5	\( p \lor (\neg p \land \neg q) \)	Inverse Distributive: p∧(¬q∨q) ≡ p
6	\( p \lor \neg q \)	Distributive and Complement
7	\( q \rightarrow p \)	Inverse Material Implication

Result: \( (\neg p \leftrightarrow q) \veebar (p \rightarrow q) \equiv q \rightarrow p \)

Takeaway: Recognizing that ¬p ↔ q ≡ p ⊻ q was the key that unlocked everything.

Exercise 10

Simplify the compound proposition:

\( [\neg(p \leftrightarrow q) \lor [(p \land \neg q) \lor \neg[(r \rightarrow s) \lor (q \rightarrow p)]]] \veebar [q \land (p \rightarrow q)] \)

Solution

Game plan: Simplify each side of the XOR separately, then combine.

Step 1: Simplify the left side of XOR

We observe that ¬(p ↔ q) = p ⊻ q = (p ∧ ¬q) ∨ (¬p ∧ q)

Since (p ∧ ¬q) is already contained in p ⊻ q:

• ¬(p ↔ q) ∨ (p ∧ ¬q) = p ⊻ q — by Absorption

Step 2: Simplify ¬[(r → s) ∨ (q → p)]

Expression	Transformation
(r → s) ∨ (q → p)	= (¬r ∨ s) ∨ (¬q ∨ p) — Material Implication
\( \mathrm{ ¬[(¬r ∨ s) ∨ (¬q ∨ p)] } \)	= (r ∧ ¬s) ∧ (q ∧ ¬p) — De Morgan

This term (r ∧ ¬s ∧ q ∧ ¬p) is “absorbed” by (¬p ∧ q), which is already part of p ⊻ q.

By Absorption: (p ⊻ q) ∨ (r ∧ ¬s ∧ q ∧ ¬p) = p ⊻ q

Left side = p ⊻ q

Step 3: Simplify the right side of XOR

\( q \land (p \rightarrow q) = q \land (\neg p \lor q) \)

By Absorption: A ∧ (B ∨ A) ≡ A

\( = q \)

Right side = q

Step 4: Apply XOR property

\( (p \veebar q) \veebar q \)

Property: (A ⊻ B) ⊻ B = A (XOR is its own inverse)

\( (p \veebar q) \veebar q = p \)

Result: \( [\neg(p \leftrightarrow q) \lor [(p \land \neg q) \lor \neg[(r \rightarrow s) \lor (q \rightarrow p)]]] \veebar [q \land (p \rightarrow q)] \equiv p \)

Takeaway: Four variables (p, q, r, s) collapsed to just one! Variables r and s got absorbed away, and XOR-ing with q cancelled out the q from p ⊻ q.

Exercise 11

Reasoning problem:

If Diana performs activities A or B, then she performs C or D, but if she does not perform B then she performs C; however, she does not perform C. Which activities does Diana necessarily perform?

a) A b) B c) D d) B and D e) A; B and D

Solution

Step 1: We translate to propositional language

Statement	Formalization
“If she performs A or B, then she performs C or D”	\( \mathrm{ (A ∨ B) → (C ∨ D) } \)
“If she does not perform B, then she performs C”	¬B → C
“She does not perform C”	¬C

Complete expression: \( [(A \lor B) \rightarrow (C \lor D)] \land (\neg B \rightarrow C) \land \neg C \)

Step 2: We apply Material Implication to the conditionals

\( [\neg(A \lor B) \lor (C \lor D)] \land (B \lor C) \land \neg C \)

Step 3: We apply De Morgan and Absorption

• ¬(A ∨ B) = ¬A ∧ ¬B
• (B ∨ C) ∧ ¬C
  =(B ∧ ¬C) ∨ (C ∧ ¬C) by Distributivity
  =(B ∧ ¬C) ∨ F, by Complement
  = B ∧ ¬C — by Identity

Resulting in:

\( [(\neg A \land \neg B) \lor C \lor D] \land B \land \neg C \)

Rearranging:

\( [(\neg A \land \neg B) \lor D \lor C] \land \neg C \land B \)

Step 4: We apply Distributive, Complement and Identity again with respect to ¬C:

\( [(\neg A \land \neg B) \lor D] \land \neg C \land B \)

Step 5: We apply Distributive and rearranging:

\( (\neg A \lor D) \land ( \neg B \lor D ) \land B \land \neg C \equiv (\neg A \lor D) \land ( D \lor \neg B ) \land \neg ( \neg B) \land \neg C \)

Step 6: We apply distributive, complement and identity with respect to \( \neg ( \neg B) \):

\( ( \neg A \lor D ) \land D \land \neg ( \neg B ) \land \neg C \equiv ( \neg A \lor D ) \land D \land B \land \neg C \)

Step 7: We apply Absorption to \( (¬A ∨ D) \) when we have \( D \)

• \( (¬A ∨ D) ∧ D = D \)

Then \( D \land B \land \neg C \)

Result: \( B \land D \land \neg C \)

Diana necessarily performs B and D (and does not perform C).

Answer: d) B and D

Note: This exercise shows how propositional logic can solve reasoning problems. The premise ¬C is crucial because, combined with ¬B → C (contrapositive: ¬C → B), it tells us that B is necessarily true.

Section IV: Inference Rules

This section covers inference rules, including how to check argument validity, derive conclusions, and use the shortcut method.

Quick Reference Guide

What is Logical Inference?

Logical inference is the process of drawing valid conclusions from premises using rules that guarantee sound reasoning.

An inference rule is a valid argument pattern that lets you derive a conclusion from premises. If the premises are true, the conclusion must be true.

Notation

Symbol	Meaning
⊢	“Derives” or “entails”
p, q ⊢ r	From p and q, we derive r

Equivalence vs Inference

Concept	Symbol	Meaning
Equivalence	≡	Expressions have the SAME truth value
Inference	⊢	The conclusion FOLLOWS from the premises

Conditional vs Implication

Concept	Symbol	Type	Description
Conditional	→	Logical connective	Can be T or F (depends on p, q)
Implication	⇒	Tautology	Always T

Note: We say p implies q (p ⇒ q) when the conditional p → q is a tautology. Inference rules are implications: for example, Modus Ponens [(p → q) ∧ p] ⇒ q is always true.

Summary of Inference Rules

1. Modus Ponens (M.P.):
   p → q, p ⊢ q
2. Modus Tollens (M.T.):
   p → q, ¬q ⊢ ¬p
3. Hypothetical Syllogism (H.S.):
   p → q, q → r ⊢ p → r
4. Disjunctive Syllogism (D.S.):
   p ∨ q, ¬p ⊢ q
5. Simplification (Simp.):
   p ∧ q ⊢ p
6. Addition (Add.):
   p ⊢ p ∨ q
7. Conjunction (Conj.):
   p, q ⊢ p ∧ q
8. Simple Constructive Dilemma (S.C.D.):
   (p → q), (r → q), p ∨ r ⊢ q
9. Complex Constructive Dilemma (C.C.D.):
   (p → q), (r → s), p ∨ r ⊢ q ∨ s
10. Simple Destructive Dilemma (S.D.D.):
    (p → q), (p → r), ¬q ∨ ¬r ⊢ ¬p
11. Complex Destructive Dilemma (C.D.D.):
    (p → q), (r → s), ¬q ∨ ¬s ⊢ ¬p ∨ ¬r
12. Absorption (Abs.):
    p → q ⊢ p → (p ∧ q)
13. Resolution (Res.):
    p ∨ q, ¬p ∨ r ⊢ q ∨ r

The 4 Core Rules

1. Modus Ponens (M.P.)

If we have a conditional and affirm the antecedent, we can conclude the consequent.

p → q    (If p, then q)
p        (p is true)
─────
∴ q      (Therefore, q)

Example: If it rains → I get wet. It rains. ∴ I get wet. ✓

2. Modus Tollens (M.T.)

If we have a conditional and deny the consequent, we conclude the negation of the antecedent.

p → q    (If p, then q)
¬q       (q is false)
─────
∴ ¬p     (Therefore, NOT p)

Example: If it rains → street is wet. Street is NOT wet. ∴ It’s NOT raining. ✓

3. Hypothetical Syllogism (H.S.)

If p implies q, and q implies r, then p implies r (transitivity).

p → q
q → r
─────
∴ p → r

Example: If I study → I pass. If I pass → I celebrate. ∴ If I study → I celebrate. ✓

4. Disjunctive Syllogism (D.S.)

If we have a disjunction and deny one alternative, we conclude the other.

p ∨ q
¬p
─────
∴ q

Example: I go to the movies ∨ I stay home. I do NOT go to the movies. ∴ I stay home. ✓

Building Rules

Rule	Form	Use
Simplification	p ∧ q ⊢ p	Extract one component from a conjunction
Addition	p ⊢ p ∨ q	Form a disjunction from any proposition
Conjunction	\( \mathrm{ p, q ⊢ p ∧ q } \)	Combine two true propositions

The Shortcut Method (Proof by Contradiction)

The shortcut method lets you check argument validity without building the full truth table.

Steps:

1. Assume the conclusion is FALSE
2. Assume all premises are TRUE
3. Push values through to subexpressions
4. Hunt for contradictions:
   • Contradiction found → The argument is VALID
   • No contradiction → The argument is INVALID

Example:

Verify: [(p → q) ∧ p] → q (Modus Ponens)

1. Assume the main conditional is F, so the antecedent is T and consequent is F
2. Then: (p → q) ∧ p = T, and q = F
3. From the conjunction: p = T and (p → q) = T
4. But p = T and q = F makes p → q = F (contradicts step 3)

CONTRADICTION! → The argument is VALID ✓

⚠️ Common Fallacies (NOT valid)

Fallacy	INCORRECT Form	Error
Affirming the Consequent	p → q, q ⊢ p	❌ Affirming q doesn’t guarantee p
Denying the Antecedent	\( \mathrm{ p → q, ¬p ⊢ ¬q } \)	❌ Denying p doesn’t guarantee ¬q

Worked Examples

Exercise 1

Derive the conclusion Q → P from the premises:

• P1: P ∨ Q → P
• P2: Q ∨ P

Solution

Proof:

Step	Proposition	Justification
1	P∨Q → P	Premise 1
2	¬(P∨Q) ∨ P	Material Implication (1)
3	(¬P ∧ ¬Q) ∨ P	De Morgan (2)
4	P ∨ (¬P ∧ ¬Q)	Commutativity (3)
5	\( ( \mathrm{P} ∨ ¬ \mathrm{P} ) ∧ ( \mathrm{P} ∨ ¬ \mathrm{Q} ) \)	Distributive (4)
6	T ∧ (P ∨ ¬Q)	Complement (5)
7	P ∨ ¬Q	Identity (6)
8	¬Q ∨ P	Commutativity (7)
9	Q → P	Material Implication (8) ✓

Result: \( Q \rightarrow P \) is derivable from the premises.

Takeaway: Premise 1 (P ∨ Q → P) is logically equivalent to the conclusion (Q → P). Premise 2 (Q ∨ P) wasn’t needed here, but it reinforces that at least one proposition is true.

Exercise 2

Prove the conclusion R → ¬Q from the premises:

• P1: ¬(R ∧ S)
• P2: Q → S

Solution

Proof:

Step	Proposition	Justification
1	¬(R ∧ S)	Premise 1
2	¬R ∨ ¬S	De Morgan (1)
3	R → ¬S	Material Implication (2)
4	Q → S	Premise 2
5	¬S → ¬Q	Contraposition (4)
6	R → ¬Q	Hypothetical Syllogism (3, 5) ✓

Result: \( \mathrm{R} \rightarrow \neg \mathrm{Q} \) is derivable from the premises.

Takeaway: The trick was converting P1 into a conditional (R → ¬S) and taking the contrapositive of P2 (¬S → ¬Q). Hypothetical Syllogism then chains them together.

Exercise 3

Is this implication valid?

\( (\neg \mathrm{P} \leftrightarrow \mathrm{Q} ) \land ( \mathrm{Q} \rightarrow \neg \mathrm{R} ) \land \mathrm{R} \Rightarrow \mathrm{P} \land \neg \mathrm{Q} \)

Solution

Splitting into premises:

1. ¬P ↔ Q
2. Q → ¬R
3. R

Conclusion to verify: P ∧ ¬Q

Proof:

Step	Proposition	Justification
1	¬P ↔ Q	Premise 1
2	Q → ¬R	Premise 2
3	R	Premise 3
4	¬Q	Modus Tollens (2, 3)
5	¬P → Q	Biconditional Definition (1)
6	¬Q → P	Contraposition (5)
7	P	Modus Ponens (6, 4)
8	P ∧ ¬Q	Conjunction (7, 4) ✓

Result: The implication is VALID ✓

Takeaway: First, use Modus Tollens on premises 2 and 3 to get ¬Q. Then extract an implication from the biconditional and derive P via Contraposition and Modus Ponens.

Exercise 4

From the following premises:

• P1: 8 is divisible by 2 if and only if it’s even
• P2: Since 12 is a multiple of 3, we conclude that 8 is divisible by 2
• P3: 8 is not even unless 7 > 3

We conclude:

a) 2 is even
b) If 12 is a multiple of 3 then 7 > 3
c) 2 is even or 7 ≤ 3
d) 7 ≤ 3 and 2 is even
e) 8 is not divisible by 2

Solution

Step 1: Define propositional variables

Variable	Proposition
p	8 is divisible by 2
q	8 is even
r	12 is a multiple of 3
s	7 > 3

Step 2: Formalize the premises

Premise	Formalization
P1	p ↔ q
P2	r → p
P3	q → s

Note: “A unless B” formalizes as ¬B → ¬A, which is equivalent to A → B.

Step 3: Proof

Step	Proposition	Justification
1	p ↔ q	Premise 1
2	r → p	Premise 2
3	q → s	Premise 3
4	p → q	Biconditional Definition (1)
5	r → q	Hypothetical Syllogism (2, 4)
6	r → s	Hypothetical Syllogism (5, 3) ✓

Result: r → s is derivable from the premises.

Analyzing the options:

Option	Proposition	Derivable?
a)	2 is even	❌ Not related
b)	If 12 is a multiple of 3 then 7 > 3	✅ Yes
c)	2 is even or 7 ≤ 3	❌ Not derivable
d)	7 ≤ 3 and 2 is even	❌ Not derivable
e)	8 is not divisible by 2	❌ Contradicts

Answer: b) If 12 is a multiple of 3 then 7 > 3

Takeaway: The chain r → p → q → s emerges from applying Hypothetical Syllogism twice.

Exercise 5

Given the following scenario:

“Cultivating values is both necessary and sufficient for living in peace, just as living in peace depends entirely on having a clear conscience. But your conscience is troubled and your morale is low.”

What can we infer?

a) Your morale is not low
b) You cultivate values
c) You do not cultivate values
d) You live in peace
e) You do not live in peace

Solution

Step 1: Define variables

Variable	Proposition
p	You cultivate values
q	You live in peace
r	Your conscience is at ease
s	Your morale is low

Step 2: Formalize the premises

Premise	Formalization
“A is necessary and sufficient for B”	p ↔ q
“just as” (same relationship)	q ↔ r
“conscience troubled and morale low”	¬r ∧ s

Step 3: Derive the conclusion

Step	Proposition	Justification
1	p ↔ q	Premise 1
2	q ↔ r	Premise 2
3	¬r ∧ s	Premise 3
4	¬r	Simplification (3)
5	q → r	Biconditional Definition (2)
6	¬q	Modus Tollens (5, 4)
7	p → q	Biconditional Definition (1)
8	¬p	Modus Tollens (7, 6) ✓

Derivation chain: ¬r → ¬q → ¬p

Analyzing options:

Option	Proposition	Derivable?
a)	Your morale is not low (¬s)	❌ We have s
b)	You cultivate values (p)	❌ We have ¬p
c)	You do not cultivate values (¬p)	✅ Yes
d)	You live in peace (q)	❌ We have ¬q
e)	You do not live in peace (¬q)	✅ Also

Answer: c) You do not cultivate values

Takeaway: Both c) and e) are derivable, but c) is the “end of the line” in the chain ¬r → ¬q → ¬p.

Exercise 6

Check whether these arguments are valid:

a)

• Premise 1: p ∧ q
• Premise 2: ¬p → q
• Conclusion: ∴ ¬q

b)

• Premise 1: (p ∧ q) → (r ∧ s)
• Premise 2: (¬q) ∨ (¬s)
• Conclusion: ∴ (¬p) ∨ (¬q)

c)

• Premise 1: p ∧ (p ∨ q)
• Premise 2: (p ∨ q) → r
• Premise 3: r → s
• Conclusion: ∴ s

d)

• Premise 1: r → ¬q
• Premise 2: p → q
• Premise 3: ¬r → s
• Conclusion: ∴ p → s

Solution

Part a) Premises:

1. p ∧ q
2. ¬p → q

Conclusion: ∴ ¬q

Analysis:

Step	Proposition	Justification
1	p ∧ q	Premise
2	p	Simplification (1)
3	q	Simplification (1)

From premise 1, by Simplification, we get \( V(q) = \mathrm{T} \).

But the proposed conclusion is ¬q, which would require \( V(q) = \mathrm{F} \).

Why is it INVALID?

An argument is valid if: when ALL premises are T, the conclusion MUST be T.

Here:

• Both premises can be T (when p=T, q=T)
• But with those values, the conclusion ¬q = F

Since there’s a situation where premises are T but conclusion is F, the argument is INVALID.

Note: Premise 2 (¬p → q) is irrelevant—premise 1 already gives us q = T, which directly contradicts the conclusion ¬q.

Result: ❌ INVALID

Part b) Premises:

1. (p ∧ q) → (r ∧ s)
2. (¬q) ∨ (¬s)

Conclusion: ∴ (¬p) ∨ (¬q)

Analysis via Proof by Contradiction:

Assume \( V[(¬p) ∨ (¬q)] = \mathrm{F} \):

• For the disjunction to be F: \( V(¬p) = \mathrm{F} \) and \( V(¬q) = \mathrm{F} \)
• Therefore: \( V(p) = \mathrm{T} \) and \( V(q) = \mathrm{T} \)

With these values:

• \( V(p ∧ q) = \mathrm{T} \)
• From premise 1: \( V[(p ∧ q) → (r ∧ s)] = \mathrm{T} \) requires \( V(r ∧ s) = \mathrm{T} \)
• Therefore: \( V(r) = \mathrm{T} \) and \( V(s) = \mathrm{T} \)

Checking premise 2:

• \( V[(¬q) ∨ (¬s)] = V(\mathrm{F} ∨ \mathrm{F}) = \mathrm{F} \)

CONTRADICTION! Premise 2 comes out F.

Result: ✅ VALID

Part c) Premises:

1. p ∧ (p ∨ q)
2. (p ∨ q) → r
3. r → s

Conclusion: ∴ s

Proof:

Step	Proposition	Justification
1	p ∧ (p ∨ q)	Premise
2	(p ∨ q) → r	Premise
3	r → s	Premise
4	p	Simplification (1)
5	p ∨ q	Addition (4)
6	r	Modus Ponens (2, 5)
7	s	Modus Ponens (3, 6) ✓

Result: ✅ VALID

Part d) Premises:

1. r → ¬q
2. p → q
3. ¬r → s

Conclusion: ∴ p → s

Proof:

Step	Proposition	Justification
1	r → ¬q	Premise
2	p → q	Premise
3	¬r → s	Premise
4	q → ¬r	Contraposition (1)
5	p → ¬r	Hypothetical Syllogism (2, 4)
6	p → s	Hypothetical Syllogism (5, 3) ✓

Result: ✅ VALID

Summary

Argument	Valid	Rules Applied
a)	❌ No	Simplification (contradicts conclusion)
b)	✅ Yes	Reductio ad absurdum
c)	✅ Yes	Simplification, Addition, Modus Ponens
d)	✅ Yes	Contraposition, Hypothetical Syllogism

Exercise 7

From the premises:

1. P ∨ ¬Q → R ∨ M
2. R → T ∨ S
3. N → S
4. M ∧ ¬R → N

Prove that: ¬P → (¬(Q ∨ R) → T ∨ S)

Solution

Proof:

Step	Proposition	Justification
1	P ∨ ¬Q → R ∨ M	Premise 1
2	R → T ∨ S	Premise 2
3	N → S	Premise 3
4	M ∧ ¬R → N	Premise 4
5	¬P	Assumption (for →)
6	¬(Q ∨ R)	Assumption (nested conditional)
7	¬Q ∧ ¬R	De Morgan (6)
8	¬Q	Simplification (7)
9	¬R	Simplification (7)
10	P ∨ ¬Q	Addition (8)
11	R ∨ M	Modus Ponens (1, 10)
12	M	Disjunctive Syllogism (11, 9)
13	M ∧ ¬R	Conjunction (12, 9)
14	N	Modus Ponens (4, 13)
15	S	Modus Ponens (3, 14)
16	T ∨ S	Addition (15)
17	\( ¬( \mathrm{Q} ∨ \mathrm{R} ) → \mathrm{T} ∨ \mathrm{S} \)	Introduction → (6-16)
18	\( ¬ \mathrm{P} → (¬( \mathrm{Q} ∨ \mathrm{R} ) → \mathrm{T} ∨ \mathrm{S} ) \)	Introduction → (5-17) ✓

Result: ✅ VALID

Takeaway: This uses conditional proof—assume the antecedent and derive the consequent. The proof chains Modus Ponens, Disjunctive Syllogism, and Addition together.

Exercise 8

Given the premises in binary representation:

• P1: 00111111
• P2: 11101110
• P3: 01010101

The conclusion is:

a) 10101010
b) 01010101
c) 10110011
d) 11110000
e) 00001111

Solution

Step 1: Interpret the binary representation

Each 8-bit number represents a truth table column for 3 variables (2³ = 8 rows).

Row	p	q	r	P1	P2	P3
0	F	F	F	0	1	0
1	F	F	T	0	1	1
2	F	T	F	1	1	0
3	F	T	T	1	0	1
4	T	F	F	1	1	0
5	T	F	T	1	1	1
6	T	T	F	1	1	0
7	T	T	T	1	0	1

Step 2: Identify the formulas

Premise	Pattern	Formula
P1 = 00111111	0 when: p=F and q=F	p ∨ q
P2 = 11101110	0 when: q=T and r=T	¬(q ∧ r) = ¬q ∨ ¬r
P3 = 01010101	1 when: r=T	r

Step 3: Derive the conclusion

Step	Proposition	Justification
1	r	Premise P3
2	¬q ∨ ¬r	Premise P2
3	¬q	Disjunctive Syllogism (2, 1)
4	p ∨ q	Premise P1
5	p	Disjunctive Syllogism (4, 3) ✓

Step 4: Check the options

Option	Binary	Represents	Conclusion?
a)	10101010	¬r	❌
b)	01010101	r	❌ (is P3)
c)	10110011	¬q	❌
d)	11110000	¬r	❌
e)	00001111	p	✅ Yes

Answer: e) 00001111

Takeaway: This mixes binary truth tables with inference rules. Here’s the logic: From P3, r is T. Since P2 says ¬q ∨ ¬r and ¬r is F (because r is T), Disjunctive Syllogism gives us ¬q. Then, since P1 says p ∨ q and q is F (because ¬q is T), Disjunctive Syllogism gives us p.

Section V: Logic Circuits

This section covers exercises on logic circuits, including how to build circuits from expressions, derive expressions from circuits, and simplify using Boolean algebra.

Quick Reference Guide

What are Logic Circuits?

Logic circuits are physical or abstract representations of propositional logic operations. While in logic we work with true (T) or false (F) propositions, in circuits we work with on (1) or off (0) states.

This connection between mathematical logic and electrical circuits was discovered by Claude Shannon in 1938, who showed that Boolean algebra could be applied to switching circuit design.

Logic-Circuit Correspondence

Propositional Logic	Electrical Circuit
True Proposition (T)	Closed Switch (1)
False Proposition (F)	Open Switch (0)
Conjunction (∧)	Series Circuit
Disjunction (∨)	Parallel Circuit
Negation (¬)	Inverter Switch

Basic Elements

1. Switch: Device that allows or blocks current flow
   • Open (0): No current flows
   • Closed (1): Current flows
2. Lamp/Bulb: Indicates circuit output
   • Off (0): Open circuit
   • On (1): Closed circuit
3. Power source: Provides current to the circuit

Basic Circuits

1. AND Circuit (Conjunction) – Series

The AND circuit corresponds to logical conjunction (p ∧ q). It’s built by connecting switches in series.

    
──── p ───── q ────💡
    

How it works: The lamp lights only if both switches are closed.

Circuit states:

State	Diagram	Result
p=0,q=0	─── ○ ─── ○ ───○	Off
p=0,q=1	─── ○ ─── ● ───○	Off
p=1,q=0	─── ● ─── ○ ───○	Off
p=1,q=1	─── ● ─── ● ───💡	On

○ = open, ● = closed

p	q	p ∧ q	Lamp
0	0	0	Off
0	1	0	Off
1	0	0	Off
1	1	1	On

Boolean Notation: \( S = p \cdot q \)

2. OR Circuit (Disjunction) – Parallel

The OR circuit corresponds to logical disjunction (p ∨ q). It’s built by connecting switches in parallel.

       ┌─── p ───┐
       │         │
    ───┼         ┼───💡
       │         │
       └─── q ───┘

How it works: The lamp lights if at least one switch is closed.

Circuit states:

State	Result
p=0, q=0 (both open)	Off
p=0, q=1 (q closed)	On
p=1, q=0 (p closed)	On
p=1, q=1 (both closed)	On

p	q	p ∨ q	Lamp
0	0	0	Off
0	1	1	On
1	0	1	On
1	1	1	On

Boolean Notation: \( S = p + q \)

3. NOT Circuit (Negation) – Inverter

The NOT circuit corresponds to logical negation (¬p). It uses a single switch representing a negated variable.

───── ¬p ─────💡

How it works: The lamp is on when the switch ¬p is closed (meaning p is false). When p is true, ¬p opens and the lamp turns off.

Circuit states:

State	Diagram	Result
p=0	─── ● ───💡(closed)	On
p=1	─── ○ ───○(open)	Off

p	¬p	Lamp
0	1	On
1	0	Off

Boolean Notation: \( S = \overline{p} \) or \( S = p’ \)

Logic Gates Summary

Gate	Symbol	Expression	Description
AND	∧	p · q	Output 1 if both inputs are 1
OR	∨	p + q	Output 1 if at least one input is 1
NOT	¬	p̄	Inverts the input
NAND	⊼	¬(p · q)	Negation of AND
NOR	⊽	¬(p + q)	Negation of OR
XOR	⊕	p ⊕ q	Output 1 if inputs are different
XNOR	⊙	¬(p ⊕ q)	Output 1 if inputs are equal
IMPLY*	→	¬p + q	Conditional: false only if p=1, q=0

Note: The IMPLY gate (*) does not exist as a dedicated integrated circuit. It’s built by combining NOT + OR.

Building Circuits from Expressions

Method:

1. Identify the variables (propositions) involved
2. Analyze the logical expression from inside out
3. Connect switches according to operations:
   • AND → Series
   • OR → Parallel
   • NOT → Inverter switch
4. Verify with truth table

Example: Circuit for (p ∧ q) ∨ r

       ┌──── p ─────── q ───┐
       │                    │
       │                    │───💡
       │                    │
       └──────── r ─────────┘

Circuit Simplification (Boolean Algebra)

Law	Form
Identity	p ∧ 1 ≡ p p ∨ 0 ≡ p
Domination	p ∧ 0 ≡ 0 p ∨ 1 ≡ 1
Idempotence	p ∧ p ≡ p p ∨ p ≡ p
Complement	p ∧ ¬p ≡ 0 p ∨ ¬p ≡ 1
Double Neg.	¬(¬p) ≡ p
De Morgan	¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
Distributive	p ∧ (q ∨ r) ≡ (p∧q) ∨ (p∧r) p ∨ (q ∧ r) ≡ (p∨q) ∧ (p∨r)
Absorption	p ∧ (p ∨ q) ≡ p p ∨ (p ∧ q) ≡ p

Worked Exercises

Exercise 1

Find the equivalent circuit:

       ┌── ¬p ── ¬q ──┐         ┌───── p ─────┐       
       │              │         │             │
●──────┼───── p ──────┼─────────┼        ┌ ¬r ┼────●
       │              │         │        │    │
       └───── q ──────┘         └── q ───└ ¬p ┘
           BLOCK A                BLOCK B

Solution

Step 1: Identify the circuit structure

The circuit consists of two main blocks connected in series (one feeding into the other):

• Block A (left): Three branches in parallel
• Block B (right): Mixed structure with parallel branches

Key rule: Blocks in SERIES equal conjunction (∧)

Step 2: Translate each block to logical expression

Block A:

• Upper branch: ¬p ── ¬q (series) is (¬p ∧ ¬q)
• Middle branch: p
• Lower branch: q

The three branches are in parallel: \( \mathrm{A} = (¬ \mathrm{p} ∧ ¬ \mathrm{q} ) ∨ \mathrm{p} ∨ \mathrm{q} \)

Block B:

• Upper branch: p
• Lower branch: q in series with (¬r ∥ ¬p)

Structure: B = p ∨ [q ∧ (¬r ∨ ¬p)]

Total expression (series between blocks):

\( \begin{align} \mathrm{S} & = \mathrm{A} ∧ \mathrm{B} \\ & = [(¬ \mathrm{p} ∧ ¬ \mathrm{q} ) ∨ \mathrm{p} ∨ \mathrm{q} ] ∧ \{ \mathrm{p} ∨ [ \mathrm{q} ∧ (¬ \mathrm{r} ∨ ¬ \mathrm{p} )] \} \end{align} \)

Step 3: Simplify Block A

Step	Expression	Law Applied
1	(¬p ∧ ¬q) ∨ p ∨ q	Original expression
2	\( \mathrm{ (¬p ∧ ¬q) ∨ (p ∨ q) } \)	Grouping
3	¬(p ∨ q) ∨ (p ∨ q)	De Morgan: ¬p ∧ ¬q ≡ ¬(p ∨ q)
4	T (Tautology)	Complement: ssX ∨ ¬X ≡ T

✅ Block A = T

Step 4: Simplify Block B

Step	Expression	Law Applied
1	p ∨ [q ∧ (¬r ∨ ¬p)]	Original expression
2	p ∨ [(q ∧ ¬r) ∨ (q ∧ ¬p)]	Distributive
3	p ∨ (q ∧ ¬r) ∨ (q ∧ ¬p)	Associative
4	\( [ \mathrm{p} ∨ ( \mathrm{q} ∧ ¬ \mathrm{p} )] ∨ ( \mathrm{q} ∧ ¬ \mathrm{r} ) \)	Regrouping
5	(p ∨ q) ∨ (q ∧ ¬r)	Absorption: p ∨ (q ∧ ¬p) ≡ p ∨ q
6	p ∨ q	Absorption: \( ( \mathrm{p} ∨ \mathrm{q} ) ∨ ( \mathrm{q} ∧ \mathrm{X} ) ≡ \mathrm{p} ∨ \mathrm{q} \)

✅ Block B = p ∨ q

Step 5: Calculate the final expression

Step	Expression	Law Applied
1	A ∧ B	Series between blocks
2	T ∧ (p ∨ q)	Substitution
3	p ∨ q	Identity: T ∧ X ≡ X

Result: The equivalent circuit is:

     ┌─── p ───┐
●────┤         ├────●
     └─── q ───┘

Logical expression: p ∨ q

Takeaway: What looks like a complex circuit with 7 switches and 2 blocks simplifies to just 2 switches in parallel. This shows the real power of Boolean algebra for circuit optimization.

Exercise 2

Build the equivalent logic circuit for the schema:

\( [(p \rightarrow q) \lor p] \land [(p \rightarrow q) \lor \neg p] \)

Solution

Step 1: Identify the structure

The expression has the form:
 [A ∨ p] ∧ [A ∨ ¬p] where A = (p → q)

Step 2: Convert the conditional

We apply Material Implication: p → q ≡ ¬p ∨ q

Substituting:

\( [(\neg p \lor q) \lor p] \land [(\neg p \lor q) \lor \neg p] \)

Step 3: Simplify each bracket separately

Left bracket: (¬p ∨ q) ∨ p

Step	Expression	Law Applied
1	(¬p ∨ q) ∨ p	Original
2	\( \mathrm{ (¬p ∨ p) ∨ q } \)	Associative and Commutative
3	T ∨ q	Complement: ¬p ∨ p ≡ T
4	T	Domination: T ∨ X ≡ T

✅ Left bracket = T

Right bracket: (¬p ∨ q) ∨ ¬p

Step	Expression	Law Applied
1	\( (¬ \mathrm{p} ∨ \mathrm{q} ) ∨ ¬ \mathrm{p} \)	Original
2	(¬p ∨ ¬p) ∨ q	Associative and Commutative
3	¬p ∨ q	Idempotence: ¬p ∨ ¬p ≡ ¬p

✅ Right bracket = ¬p ∨ q

Step 4: Combine the results

Step	Expression	Law Applied
1	[T] ∧ [¬p ∨ q]	Substitution
2	¬p ∨ q	Identity: T ∧ X ≡ X

Result: The equivalent logic circuit is:

     ┌── ¬p ───┐
●────┤         ├────●
     └─── q ───┘

Logical expression: ¬p ∨ q

Takeaway: The expression ¬p ∨ q is equivalent to p → q (material implication). So the complex original circuit simplifies to a basic parallel circuit representing the conditional.

Exercise 3

Build the simplest equivalent logic circuit for:

                    Block A

                 ┌── p ── ¬q ──┐        
                 │             │        
      ┌──── ¬p ──┼───── ¬p ────┼───────────────────┐
      │          │             │                   │
      │          └───── q ─────┘                   │    Block C
      │                                            │
M ●───┤                                            │───── ¬p ───● N
      │   ├──────────  Block B ────────────────│   │       
      │                                            │    
      │   ┌─ r ─ s ─ t ─┐        ┌──── r ──────┐   │      
      │   │             │        │             │   │    
      └───┼──── r ──────┼────────┼─── s ───────┼───┘
          │             │        │             │       
          ├──── s ──────┤        ├─── t ───────┤       
          │             │        │             │       
          └──── t ──────┘        └─ r ─ s ─ t ─┘ 

Solution

Step 1: Identify the general structure

The circuit has the form: (A ∨ B) ∧ C

Where:

• Block A = ¬p in series with [(p ∧ ¬q) ∨ ¬p ∨ q]
• Block B = Left sub-block in series with Right sub-block
• Block C = ¬p
• A and B are in parallel with each other
• The set (A ∨ B) is in series with C

Step 2: Translate each block to logical expression

Block	Expression
A	¬p ∧ [(p ∧ ¬q) ∨ (¬p ∨ q)]
B	\( [( \mathrm{r} ∧ \mathrm{s} ∧ \mathrm{t} ) ∨ ( \mathrm{r} ∨ \mathrm{s} ∨ \mathrm{t} )] ∧ [( \mathrm{r} ∨ \mathrm{s} ∨ \mathrm{t} ) ∨ ( \mathrm{r} ∧ \mathrm{s} ∧ \mathrm{t} )] \)
C	¬p

Step 3: Simplify Block A

Step	Expression	Law Applied
1	¬p ∧ [(p ∧ ¬q) ∨ (¬p ∨ q)]	Original
2	\( ¬ \mathrm{p} ∧ [( \mathrm{p} ∧ ¬ \mathrm{q} ) ∨ ¬( \mathrm{p} ∧ ¬ \mathrm{q} )] \)	De Morgan: \( ¬ \mathrm{p} ∨ \mathrm{q} ≡ ¬( \mathrm{p} ∧ ¬ \mathrm{q} ) \)
3	¬p ∧ T	Complement: X ∨ ¬X ≡ T
4	¬p	Identity: X ∧ T ≡ X

✅ Block A = ¬p

Step 4: Simplify Block B

Notice that B has the form: \( [ \mathrm{X} ∨ \mathrm{Y} ] ∧ [ \mathrm{Y} ∨ \mathrm{X} ] \) where:

• X = (r ∧ s ∧ t) — series
• Y = (r ∨ s ∨ t) — parallel

Step	Expression	Law Applied
1	\( [( \mathrm{r} ∧ \mathrm{s} ∧ \mathrm{t} ) ∨ ( \mathrm{r} ∨ \mathrm{s} ∨ \mathrm{t} )] ∧ [( \mathrm{r} ∨ \mathrm{s} ∨ \mathrm{t} ) ∨ ( \mathrm{r} ∧ \mathrm{s} ∧ \mathrm{t} )] \)	Original
2	[r ∨ s ∨ t] ∧ [r ∨ s ∨ t]	Absorption: \( ( \mathrm{X} ∧ \mathrm{Y} ∧ \mathrm{Z} ) ∨ ( \mathrm{X} ∨ \mathrm{Y} ∨ \mathrm{Z} ) ≡ \mathrm{X} ∨ \mathrm{Y} ∨ \mathrm{Z} \)
3	r ∨ s ∨ t	Idempotence: X ∧ X ≡ X

✅ Block B = r ∨ s ∨ t

Step 5: Calculate (A ∨ B) ∧ C

Step	Expression	Law Applied
1	(A ∨ B) ∧ C	Original structure
2	\( [¬ \mathrm{p} ∨ ( \mathrm{r} ∨ \mathrm{s} ∨ \mathrm{t} )] ∧ ¬ \mathrm{p} \)	Substitution
3	¬p	Absorption: (X ∨ Y) ∧ X ≡ X

Result: The equivalent circuit is:

M ●─── ¬p ───● N

Logical expression: ¬p

Takeaway: A seemingly complex circuit with multiple blocks and over 10 switches simplifies down to just one inverter switch (¬p). This powerfully demonstrates how Boolean algebra can optimize circuits.

Exercise 4

Describe the circuit symbolically:

                        ┌──── r ────┐
       ┌──── p ─────────┤           │
       │                └─── ¬q ────┤
●──────┤                            ├──────●
       │                            │
       └──── q ──────────── ¬r ─────┘

Solution

Step 1: Identify the general structure

The circuit has two main branches in parallel:

• Upper branch: p in series with a sub-block
• Lower branch: q in series with ¬r

Step 2: Analyze each branch

Upper branch:

       ┌──── r ────┐
─ p ───┤           ├───
       └─── ¬q ────┘

• p is in series with a parallel block of (r ∥ ¬q)
• Expression: p ∧ (r ∨ ¬q)

Lower branch:

─── q ─── ¬r ───

• q is in series with ¬r
• Expression: q ∧ ¬r

Step 3: Combine the branches

The two branches are in parallel (disjunction):

Structure	Expression
Upper branch	p ∧ (r ∨ ¬q)
Lower branch	q ∧ ¬r
Complete circuit	[p ∧ (r ∨ ¬q)] ∨ (q ∧ ¬r)

Result:

Symbolic expression of the circuit:
[p ∧ (r ∨ ¬q)] ∨ (q ∧ ¬r)

Exercise 5

Find the smallest expression that represents the given circuit:

    ┌─────── p ────────┐
    │                  │
●───┼─────── q ────────┼── ¬p ───●
    │                  │
    └── ¬q ───── ¬p ───┘

Solution

Step 1: Translate the circuit to logical expression

The circuit has:

• Parallel block: p ∥ q ∥ (¬q — ¬p)
• This block is in series with ¬p

Initial expression: [p ∨ q ∨ (¬q ∧ ¬p)] ∧ ¬p

Step 2: Simplify the internal parallel block

First we simplify: q ∨ (¬q ∧ ¬p)

Step	Expression	Law Applied
1	q ∨ (¬q ∧ ¬p)	Original
2	(q ∨ ¬q) ∧ (q ∨ ¬p)	Distributive
3	T ∧ (q ∨ ¬p)	Complement
4	q ∨ ¬p	Identity

Step 3: Substitute and continue simplifying

Step	Expression	Law Applied
1	[p ∨ (q ∨ ¬p)] ∧ ¬p	Substitution
2	\( [( \mathrm{p} ∨ ¬ \mathrm{p} ) ∨ \mathrm{q} ] ∧ ¬ \mathrm{p} \)	Associative and Commutative
3	[T ∨ q] ∧ ¬p	Complement
4	T ∧ ¬p	Domination
5	¬p	Identity

Result:

The smallest expression is: ¬p

Equivalent circuit:

●─── ¬p ───●

Takeaway: A circuit with 3 parallel branches and 4 switches simplifies down to just one inverter switch.

Exercise 6

Determine the logic circuit that represents the molecular schema:

¬[p → ¬(q ∨ r)]

Solution

Step 1: Convert the conditional using Material Implication

p → X ≡ ¬p ∨ X

Step	Expression	Law Applied
1	¬[p → ¬(q ∨ r)]	Original
2	¬[¬p ∨ ¬(q ∨ r)]	Material Implication

Step 2: Apply De Morgan to the outer negation

Step	Expression	Law Applied
3	\( ¬(¬ \mathrm{p} ) ∧ ¬[¬( \mathrm{q} ∨ \mathrm{r} ) ] \)	De Morgan: ¬(A ∨ B) ≡ ¬A ∧ ¬B
4	p ∧ (q ∨ r)	Double Negation (×2)

Result:

Simplified expression: p ∧ (q ∨ r)

Equivalent logic circuit:

           ┌── q ──┐
           │       │
●─── p ────┤       ├────●
           │       │
           └── r ──┘

Takeaway: An expression with nested negations and a conditional simplifies to a very basic circuit: p in series with (q ∨ r).

Exercise 7

Find the simplest equivalent proposition for the following logic circuit:

     ┌──── p ─────┐   ┌──── ¬p ───┐
     │            │   │           │
●────┼──── q ─────┼───┼           ┼─── p ───●
     │            │   │           │
     └─ ¬p ── ¬q ─┘   └──── q ────┘   
       Block A         Block B     Series

Solution

Step 1: Translate the circuit to logical expression

• Block A: p ∨ q ∨ (¬p ∧ ¬q)
• Block B: ¬p ∨ q
• Final series: p
• Complete expression:
  [p ∨ q ∨ (¬p ∧ ¬q)] ∧ [(¬p ∨ q) ∧ p]

Step 2: Simplify Block A

Step	Expression	Law Applied
1	\( \mathrm{p} ∨ \mathrm{q} ∨ (¬ \mathrm{p} ∧ ¬ \mathrm{q} ) \)	Original
2	(p ∨ q) ∨ ¬(p ∨ q)	De Morgan: ¬p ∧ ¬q ≡ ¬(p ∨ q)
3	T	Complement: X ∨ ¬X ≡ T

✅ Block A = T

Step 3: Simplify (Block B ∧ p)

Step	Expression	Law Applied
1	(¬p ∨ q) ∧ p	Original
2	\( (¬ \mathrm{p} ∧ \mathrm{p} ) ∨ ( \mathrm{q} ∧ \mathrm{p} ) \)	Distributive
3	F ∨ (p ∧ q)	Complement: ¬p ∧ p ≡ F
4	p ∧ q	Identity: F ∨ X ≡ X

✅ Block B ∧ p = p ∧ q

Step 4: Combine

Step	Expression	Law Applied
1	T ∧ (p ∧ q)	Substitution
2	p ∧ q	Identity: T ∧ X ≡ X

Result:

Simplified expression: p ∧ q

Equivalent circuit:

●────── p ────── q ──────●

Takeaway: A circuit with 2 complex blocks (7 switches) simplifies to just 2 switches in series.

Exercise 8

Find the smallest expression that represents the given circuit:

       ┌──── ¬p ──────────── ¬q ───┐
       │                           │
●──────┤                           ├──────●
       │       ┌──── ¬p ───┐       │
       │       │           │       │
       └── p ──┤           ├───────┘
               │           │
               └──── q ────┘

Solution

Step 1: Translate the circuit to logical expression

The circuit has two main branches in parallel:

• Upper branch: ¬p in series with ¬q then \( \mathrm{ (¬p ∧ ¬q) } \)
• Lower branch: p in series with (¬p ∥ q) then \( \mathrm{ p ∧ (¬p ∨ q) } \)

Initial expression: (¬p ∧ ¬q) ∨ [p ∧ (¬p ∨ q)]

Step 2: Simplify the lower branch

Step	Expression	Law Applied
1	p ∧ (¬p ∨ q)	Original
2	\( ( \mathrm{p} ∧ ¬ \mathrm{p} ) ∨ ( \mathrm{p} ∧ \mathrm{q} ) \)	Distributive
3	F ∨ (p ∧ q)	Complement: p ∧ ¬p ≡ F
4	p ∧ q	Identity: F ∨ X ≡ X

Step 3: Substitute and recognize the pattern

Step	Expression	Observation
1	\( (¬ \mathrm{p} ∧ ¬ \mathrm{q} ) ∨ ( \mathrm{p} ∧ \mathrm{q} ) \)	Substitution
2	p ↔ q	This is the definition of the biconditional

Note: p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q) — the biconditional is true when both have the same value

Result:

The smallest expression is: p ↔ q

Equivalent circuit (conceptual):

●────── p ↔ q ──────●

Takeaway: This circuit implements the XNOR operation (logical equivalence): the output is 1 when both inputs have the same value.

Exercise 9

Find the smallest expression that represents the given circuit:

                               ┌──── r ────┐
                ┌──── ¬q ──────┤           │
       ┌─ p ─┐  │              └─── ¬q ────┤
       │     │  │                          │
●──────┤     ├──┤                          ├───── r ─────●
       │     │  │                          │
       └─ q ─┘  └───────── p ────── q ─────┘

Solution

Step 1: Translate the circuit to logical expression

• Block 1 (parallel): p ∨ q
• Block 2 (parallel): [¬q ∧ (r ∨ ¬q)] ∨ (p ∧ q)
• Final series: r

Initial expression: \( ( \mathrm{p} ∨ \mathrm{q} ) ∧ [(¬ \mathrm{q} ∧ ( \mathrm{r} ∨ ¬ \mathrm{q} )) ∨ ( \mathrm{p} ∧ \mathrm{q} )] ∧ \mathrm{r} \)

Step 2: Simplify ¬q ∧ (r ∨ ¬q)

Step	Expression	Law Applied
1	¬q ∧ (r ∨ ¬q)	Original
2	¬q	Absorption: X ∧ (Y ∨ X) ≡ X

Step 3: Simplify [¬q ∨ (p ∧ q)]

Step	Expression	Law Applied
1	¬q ∨ (p ∧ q)	Substitution
2	(¬q ∨ p) ∧ (¬q ∨ q)	Distributive
3	(¬q ∨ p) ∧ T	Complement
4	p ∨ ¬q	Identity

Step 4: Simplify (p ∨ q) ∧ (p ∨ ¬q)

Step	Expression	Law Applied
1	(p ∨ q) ∧ (p ∨ ¬q)	Substitution
2	p ∨ (q ∧ ¬q)	Inverse Distributive
3	p ∨ F	Complement
4	p	Identity

Step 5: Final result

Step	Expression	Law Applied
1	p ∧ r	Substitution

Result:

The smallest expression is: p ∧ r

Equivalent circuit:

●────── p ────── r ──────●

Takeaway: A complex circuit with 8 switches simplifies to just 2 switches in series.

Exercise 10

Find the equivalent circuit:

       ┌─ ¬p ── ¬q ─┐       ┌───── p ─────┐
       │            │       │             │
●──────┼──── p ─────┼───────┼             ├──────●
       │            │       │   ┌─ ¬r ─┐  │
       └──── q ─────┘       └─q─┤      ├──┘
                                └─ ¬p ─┘
         Block A               Block B

Solution

Step 1: Translate the circuit to logical expression

• Block A: (¬p ∧ ¬q) ∨ p ∨ q
• Block B: p ∨ [q ∧ (¬r ∨ ¬p)]

Initial expression: \( [(¬ \mathrm{p} ∧ ¬ \mathrm{q} ) ∨ \mathrm{p} ∨ \mathrm{q} ] ∧ \{ \mathrm{p} ∨ [ \mathrm{q} ∧ (¬ \mathrm{r} ∨ ¬ \mathrm{p} )] \} \)

Step 2: Simplify Block A

Step	Expression	Law Applied
1	(¬p ∧ ¬q) ∨ p ∨ q	Original
2	\( (¬ \mathrm{p} ∧ ¬ \mathrm{q} ) ∨ ( \mathrm{p} ∨ \mathrm{q} ) \)	Regroup
3	¬(p ∨ q) ∨ (p ∨ q)	De Morgan
4	T	Complement: X ∨ ¬X ≡ T

✅ Block A = T

Step 3: Simplify Block B

Step	Expression	Law Applied
1	p ∨ [q ∧ (¬r ∨ ¬p)]	Original
2	\( \mathrm{p} ∨ [( \mathrm{q} ∧ ¬ \mathrm{r} ) ∨ ( \mathrm{q} ∧ ¬ \mathrm{p} )] \)	Distributive
3	p ∨ (q ∧ ¬r) ∨ (q ∧ ¬p)	Regroup
4	[p ∨ (q ∧ ¬p)] ∨ (q ∧ ¬r)	Regroup
5	(p ∨ q) ∨ (q ∧ ¬r)	Absorption: p ∨ (q ∧ ¬p) ≡ p ∨ q
6	p ∨ q	Absorption: \( ( \mathrm{p} ∨ \mathrm{q} ) ∨ ( \mathrm{q} ∧ \mathrm{X} ) ≡ \mathrm{p} ∨ \mathrm{q} \)

✅ Block B = p ∨ q

Step 4: Combine

Step	Expression	Law Applied
1	T ∧ (p ∨ q)	Substitution
2	p ∨ q	Identity: T ∧ X ≡ X

Result:

Simplified expression: p ∨ q

Equivalent circuit:

       ┌──── p ────┐
       │           │
●──────┤           ├──────●
       │           │
       └──── q ────┘

Takeaway: A circuit with 2 complex blocks (9 switches) reduces to just 2 switches in parallel.

Exercise 11

Find the proposition x such that the simplified circuit is a tautology:

       ┌─ ¬p ── ¬q ─┐   ┌──────── p ──────┐ 
    ┌──┤            ├───┤     ┌── ¬p ──┐  ├── ¬q ──┐ ← Q 
    │  └─ p ─── q ──┘   └─ q ─┤        ├──┘        │  (upper)
●───┤                         └── x ───┘           │ 
    │        ┌─ p ─── q ──┐                        │
    │  ┌─────┤   ┌─ p ──┐ ├────────────────┐       │    
    └──┤     └───┤      ├─┘                ├───────┘
       │         └─ ¬q ─┘                  │         ← R 
       │                                   │          (lower)
       │     ┌───── r ──────┐              │
       └─────┤              ├───── x ──────┘
             └─ ¬p ──── ¬r ─┘

Solution

Step 1: Identify the general structure

The circuit has two main blocks in parallel:

• P = Q ∨ R

Where:

• Q = Upper circuit (top branch)
• R = Lower circuit (bottom branch)

For P to be a tautology (always T), we need to find the value of x.

Step 2: Translate each block to logical expression

Block	Expression
Q	\( { (¬ \mathrm{p} ∧ ¬ \mathrm{q} ) ∨ ( \mathrm{p} ∧ \mathrm{q} ) } ∧ { \mathrm{p} ∨ [ \mathrm{q} ∧ (¬ \mathrm{p} ∨ \mathrm{x} )] } ∧ (¬ \mathrm{q} ) \)
R	[(p ∧ q) ∨ (p ∧ ¬q)] ∨ {[r ∨ (¬p ∧ ¬r)] ∧ x}

Step 3: Simplify Q (testing our hypothesis: x = ¬p)

Let’s try x = ¬p and see if it makes the circuit a tautology:

3.1: Simplify {p ∨ [q ∧ (¬p ∨ ¬p)]}

Step	Expression	Law Applied
1	p ∨ [q ∧ (¬p ∨ ¬p)]	Substitution: x = ¬p
2	p ∨ [q ∧ ¬p]	Idempotence: ¬p ∨ ¬p ≡ ¬p
3	(p ∨ q) ∧ (p ∨ ¬p)	Distributive
4	(p ∨ q) ∧ T	Complement
5	p ∨ q	Identity

3.2: Now Q = {(¬p ∧ ¬q) ∨ (p ∧ q)} ∧ (p ∨ q) ∧ (¬q)

Step	Expression	Law Applied
1	\( { (¬ \mathrm{p} ∧ ¬ \mathrm{q} ) ∨ ( \mathrm{p} ∧ \mathrm{q} ) } ∧ ( \mathrm{p} ∨ \mathrm{q} ) \)	Simplifying these first
2	(p ∧ q)	Absorption: the term \( (¬ \mathrm{p} ∧ ¬ \mathrm{q} ) \) is absorbed
3	(p ∧ q) ∧ (¬q)	Add the last term
4	p ∧ (q ∧ ¬q)	Associative
5	p ∧ F	Complement: q ∧ ¬q ≡ F
6	F	Domination

✅ Q = F (Contradiction)

Step 4: Since Q = F, then P = F ∨ R = R

Now we only need R = T for P to be a tautology.

Step 5: Simplify R (with x = ¬p)

5.1: Simplify [(p ∧ q) ∨ (p ∧ ¬q)]

Step	Expression	Law Applied
1	(p ∧ q) ∨ (p ∧ ¬q)	Original
2	p ∧ (q ∨ ¬q)	Inverse Distributive
3	p ∧ T	Complement
4	p	Identity

5.2: Simplify [r ∨ (¬p ∧ ¬r)] ∧ ¬p

Step	Expression	Law Applied
1	[r ∨ (¬p ∧ ¬r)] ∧ ¬p	Substitution: \( \mathrm{x} = ¬ \mathrm{p} \)
2	\( [( \mathrm{r} ∨ ¬ \mathrm{p} ) ∧ ( \mathrm{r} ∨ ¬ \mathrm{r} )] ∧ ¬ \mathrm{p} \)	Distributive
3	[(r ∨ ¬p) ∧ T] ∧ ¬p	Complement
4	(r ∨ ¬p) ∧ ¬p	Identity
5	¬p	Absorption: ss(X ∨ Y) ∧ Y ≡ Y

5.3: Now R = p ∨ ¬p

Step	Expression	Law Applied
1	p ∨ ¬p	Combination
2	T	Complement

✅ R = T (Tautology)

Step 6: Final verification

Expression	Value
Q	F
R	T
P = Q ∨ R	F ∨ T = T ✅

Result

For the circuit to be a tautology: x = ¬p

Takeaway: This exercise showcases an advanced technique: finding unknown variable values that make a complex circuit become a tautology. The key was hypothesizing x = ¬p and systematically verifying that the result is always true.

Exercise 12

Build the simplest equivalent logic circuit for:

                  ┌─ p ── ¬q ─┐                         
       ┌─── ¬p ───┤           ┼─────────────────────┐  
       │          ├── ¬p ─────┤      ┌── r ───┐     │
       │          │           │      │        │     │
P ●────┤          └── q ──────┘   ┌──┼── s ───┼──┐  ┼── ¬p ───● Q
       │                          │  │        │  │  │
       │  ┌─ r ─ s ─ t ─┐         │  └── t ───┘  │  │
       │  │             │         │              │  │
       └──┼─── r ───────┼─────────┼              ├──┘
          │             │         │              │
          ├─── s ───────┤         └─ r ─ s ─ t ──┘
          │             │        
          └─── t ───────┘       

Solution

Step 1: Identify the general structure

The circuit has the form: (A ∨ B) ∧ C

Where:

• A = Upper block (with ¬p, p, q)
• B = Lower blocks (with r, s, t)
• C = ¬p (at the end)

Step 2: Translate each block to logical expression

Block	Expression
A	¬p ∧ [(p ∧ ¬q) ∨ ¬p ∨ q]
B	\( [( \mathrm{r} ∧ \mathrm{s} ∧ \mathrm{t} ) ∨ \mathrm{r} ∨ \mathrm{s} ∨ \mathrm{t} ] ∧ [( \mathrm{r} ∨ \mathrm{s} ∨ \mathrm{t} ) ∨ ( \mathrm{r} ∧ \mathrm{s} ∧ \mathrm{t} )] \)
C	¬p

Step 3: Simplify Block A

Step	Expression	Law Applied
1	¬p ∧ [(p ∧ ¬q) ∨ ¬p ∨ q]	Original
2	¬p ∧ [(p ∧ ¬q) ∨ (¬p ∨ q)]	Regroup
3	\( ¬ \mathrm{p} ∧ [( \mathrm{p} ∧ ¬ \mathrm{q} ) ∨ ¬( \mathrm{p} ∧ ¬ \mathrm{q} )] \)	De Morgan: \( ¬ \mathrm{p} ∨ \mathrm{q} ≡ ¬( \mathrm{p} ∧ ¬ \mathrm{q} ) \)
4	¬p ∧ T	Complement: X ∨ ¬X ≡ T
5	¬p	Identity: X ∧ T ≡ X

✅ Block A = ¬p

Step 4: Simplify Block B

4.1: Each sub-block of B:

Sub-block	Expression	Simplification
Left	\( ( \mathrm{r} ∧ \mathrm{s} ∧ \mathrm{t} ) ∨ \mathrm{r} ∨ \mathrm{s} ∨ \mathrm{t} \)	= r ∨ s ∨ t (by Absorption)
Right	(r ∨ s ∨ t) ∨ (r ∧ s ∧ t)	= r ∨ s ∨ t (by Absorption)

4.2: Combine sub-blocks:

Step	Expression	Law Applied
1	\( ( \mathrm{r} ∨ \mathrm{s} ∨ \mathrm{t} ) ∧ ( \mathrm{r} ∨ \mathrm{s} ∨ \mathrm{t} ) \)	Substitution
2	r ∨ s ∨ t	Idempotence: X ∧ X ≡ X

✅ Block B = r ∨ s ∨ t

Step 5: Calculate (A ∨ B) ∧ C

Step	Expression	Law Applied
1	(A ∨ B) ∧ C	Original structure
2	\( [¬ \mathrm{p} ∨ ( \mathrm{r} ∨ \mathrm{s} ∨ \mathrm{t} )] ∧ ¬ \mathrm{p} \)	Substitution
3	¬p	Absorption: (X ∨ Y) ∧ X ≡ X

Result

The simplest equivalent circuit is: ¬p

Equivalent circuit:

A ●──── ¬p ────● B

Takeaway: A massively complex circuit with multiple blocks and over 12 switches simplifies down to just one inverter switch (¬p).

Section VI: Mathematical Proofs

This section covers exercises on mathematical proof methods, including direct proof, contraposition, contradiction, mathematical induction, and proof by cases.

Quick Reference Guide

What is a Mathematical Proof?

A mathematical proof is a rigorous logical argument that establishes the truth of a proposition, starting from axioms, definitions, and previously proven theorems.

A proof is a finite sequence of propositions where each one is:

• An axiom (a truth accepted without proof)
• A definition (an agreed-upon meaning of a term)
• A hypothesis (an initial assumption of the theorem)
• A proposition derived from previous ones using inference rules

Structure of a Theorem

Every theorem has the form: “If P, then Q” (P → Q)

Component	Name	Role
P	Hypothesis	What we assume to be true
Q	Thesis (or Conclusion)	What we want to prove
P → Q	Theorem	The complete implication

Note: When we prove that a theorem is true, we’re showing that P → Q is a tautology. A proven theorem is really an implication (P ⇒ Q).

Table of Proof Methods

#	Method	Core Idea	When to Use
1	Direct	Assume P, deduce Q	General case, first attempt
2	Contraposition	Prove ¬Q → ¬P	When Q is easier to negate
3	Contradiction	Assume ¬(P→Q), reach absurdity	Existence, uniqueness, irrationality
4	Induction	Base case + inductive step	Properties of natural numbers
5	By Cases	Divide into subcases	When there are distinct scenarios
6	Counterexample	A single refuting case	To prove falsity

1. Direct Proof

The idea is simple: start from the hypothesis and work your way to the conclusion through logical steps.

Steps:

1. Assume P is true (hypothesis)
2. Apply definitions, axioms, and known theorems
3. Through logical steps, deduce that Q is true
4. Conclude: P → Q is proven ✓

Example: If n is even, then n² is even.

Step	Statement	Justification
1	Let n be an even number	Hypothesis
2	n = 2k, for some integer k	Definition of even
3	\( \mathrm{n²} = \mathrm{(2k)²} = \mathrm{4k²} = \mathrm{2(2k²)} \)	Algebraic expansion
4	n² = 2m, where m = 2k²	Substitution
5	n² is even	By definition ∎

2. Proof by Contraposition

This method exploits the logical equivalence: P → Q ≡ ¬Q → ¬P

Structure:

1. We want to prove: P → Q
2. Instead, we prove: ¬Q → ¬P
3. Assume ¬Q (the negation of the conclusion)
4. Through logical steps, deduce ¬P
5. Since ¬Q → ¬P is true, P → Q is also true ✓

Example: If n² is even, then n is even.

Contrapositive: If n is odd, then n² is odd.

Step	Statement	Justification
1	Suppose n is odd	Assume ¬Q
2	n = 2k + 1	Definition of odd
3	\( \mathrm{n² = (2k + 1)² = 4k² + 4k + 1} \)	Expansion
4	n² = 2(2k² + 2k) + 1	Factoring
5	n² is odd	Has the form 2m + 1 ∎

3. Proof by Contradiction

Based on: If assuming something is false leads to a contradiction, then it must be true.

Structure:

1. We want to prove: P
2. Assume the opposite: ¬P (assumption for contradiction)
3. Derive logical consequences from ¬P
4. Reach a CONTRADICTION (something impossible)
5. Conclude: ¬P is false, therefore P is true ✓

Classic Example: √2 is irrational.

Step	Statement	Justification
1	Assume that √2 is rational	Assumption (¬P)
2	√2 = a/b, with a,b having no common factors	Irreducible form
3	\( \mathrm{2 = a²/b²} \), then \( \mathrm{2b² = a²} \)	Algebra
4	a² is even, then a is even	Previous theorem
5	\( \mathrm{a = 2c} \), then \( \mathrm{ 2b² = 4c²} \), \( \mathrm{b² = 2c²} \)	Substitution
6	b² is even, then b is even	Same argument
7	CONTRADICTION: \( \mathrm{a} \) and \( \mathrm{b} \) are both even	We said no common factors
8	√2 is irrational	∎

4. Proof by Mathematical Induction

The go-to method for proving properties that hold for all natural numbers.

Structure:

• Step 1: BASE CASE
  • Prove that P(n₀) is true
• Step 2: INDUCTIVE HYPOTHESIS
  • Assume P(k) is true for some k ≥ n₀
• Step 3: INDUCTIVE STEP
  • Prove that P(k) → P(k+1)
• CONCLUSION: P(n) is true for all n ≥ n₀

Example: 1 + 2 + 3 + … + n = n(n+1)/2

Phase	Development
Base Case (n=1)	1 = 1(2)/2 = 1 ✓
Hypothesis	1 + 2 + … + k = k(k+1)/2
Inductive Step	1 + 2 + … + k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2 ✓

5. Proof by Cases

Divides the problem into subcases that cover all possibilities.

Structure:

• 1. Identify all possible cases (exhaustive)
• 2. Prove the conclusion for each case
• 3. Conclude that the theorem is true in all cases

Example: For any integer n, n(n+1) is even.

Case	Development	Result
n is even	\( n = 2k \)\( \begin{align} → n(n+1) & = 2k(n+1) \ & = 2[k(n+1)] \end{align} \)	Even ✓
n is odd	\( n+1 \) is even\( \begin{align} → n(n+1) & = n(2m) \ & = 2(nm) \end{align} \)	Even ✓

6. Proof by Counterexample

To disprove “For all x, P(x)”, you only need to find one x where P(x) is false.

Examples:

False Statement	Counterexample
“All primes are odd”	2 is prime and even ✗
“n² > n for all n ≥ 1”	n = 1: 1² = 1, not greater ✗
“The sum of irrationals is irrational”	√2 + (-√2) = 0 (rational) ✗

Connection with Propositional Logic

Method	Logical Basis
Direct	P → Q (affirm antecedent, derive consequent)
Contraposition	P → Q ≡ ¬Q → ¬P
Contradiction	¬P → Contradiction, therefore P
By cases	(P₁ → Q) ∧ (P₂ → Q) ∧ … ⊢ Q

End of Proof Symbol

The symbol ∎ (or Q.E.D.) indicates that the proof has been completed.

Q.E.D. = “Quod Erat Demonstrandum” = “what was to be demonstrated”

Worked Exercises

Exercise 1

Prove that the cube of an odd number is also odd.

Type: Direct Proof

Solution

Step 1: Establish the hypothesis

Let n be an odd number.

By definition of odd number: n = 2k + 1, where k is an integer.

Step 2: Calculate n³

Step	Expression	Justification
1	n³ = (2k + 1)³	Substitution
2	= (2k + 1)(2k + 1)(2k + 1)	Expansion
3	= (2k + 1)(4k² + 4k + 1)	Square of a binomial
4	\( \mathrm{ = 8k³ + 8k² + 2k + 4k² + 4k + 1 } \)	Distributive property
5	= 8k³ + 12k² + 6k + 1	Simplification

Step 3: Factor to show the form 2m + 1

Step	Expression	Justification
6	\( \mathrm{ n³ = 2(4k³ + 6k² + 3k) + 1 } \)	Factor out 2
7	Let \( \mathrm{ m = 4k³ + 6k² + 3k } \)	m is an integer (sum and product of integers)
8	n³ = 2m + 1	Substitution

Step 4: Conclusion

Since n³ has the form 2m + 1 (where m is an integer), n³ is odd by definition.

∎

Takeaway: This proof uses the direct method: we start from the hypothesis (n is odd) and through algebraic steps arrive at the conclusion (n³ is odd). The key pattern is showing that the result has the form 2m + 1.

Exercise 2

In the set of integers, prove that if m and n are multiples of p, then m + n and m − n are also multiples of p.

Type: Direct Proof

Solution

Step 1: Establish the hypotheses

Let m and n be multiples of p.

By definition of multiple:

• m = p · a, where a is an integer
• n = p · b, where b is an integer

Step 2: Prove that m + n is a multiple of p

Step	Expression	Justification
1	\( \mathrm{ m + n = p·a + p·b } \)	Substitution
2	= p(a + b)	Factor out p
3	Let c = a + b	c is an integer (sum of integers)
4	m + n = p · c	Substitution

Since m + n = p · c, where c is an integer, m + n is a multiple of p. ✓

Step 3: Prove that m − n is a multiple of p

Step	Expression	Justification
1	\( \mathrm{ m − n = p·a − p·b } \)	Substitution
2	= p(a − b)	Factor out p
3	Let d = a − b	d is an integer (difference of integers)
4	m − n = p · d	Substitution

Since m − n = p · d, where d is an integer, m − n is a multiple of p. ✓

Conclusion

If m and n are multiples of p, then both m + n and m − n are multiples of p.

∎

Takeaway: This proof illustrates that the set of multiples of p is closed under addition and subtraction. In algebra, this means that multiples of p form a subgroup of the integers under addition.

Exercise 3

Prove that when two lines intersect, the vertically opposite angles are equal.

Type: Direct Proof (Geometry)

Solution

Step 1: Establish the situation

Let L₁ and L₂ be two lines that intersect at point O.

When they intersect, four angles are formed: α, β, α’, β’

                     
                     ╱
                    ╱
               α   ╱ β
     ─────────────O─────────────  L₂
                 ╱
            β'  ╱   α'
               ╱
              L₁

Where:

• α and α’ are vertically opposite angles
• β and β’ are vertically opposite angles

Step 2: Use the supplementary angles property

Adjacent angles formed by two intersecting lines are supplementary (sum to 180°).

Relationship	Equation
α and β are adjacent	α + β = 180° … (1)
β and α’ are adjacent	β + α’ = 180° … (2)

Step 3: Equate the equations

From (1) and (2):

Step	Expression	Justification
1	α + β = 180°	Equation (1)
2	β + α’ = 180°	Equation (2)
3	α + β = β + α’	Transitive (both = 180°)
4	α = α’	Cancel β from both sides

✅ The vertically opposite angles α and α’ are equal

Step 4: Prove for β and β’ (analogously)

Relationship	Equation
α and β are adjacent	α + β = 180° … (1)
α and β’ are adjacent	α + β’ = 180° … (3)

From (1) and (3):

Step	Expression	Justification
1	α + β = α + β’	Transitive
2	β = β’	Cancel α

✅ The vertically opposite angles β and β’ are equal

Conclusion

When two lines intersect, the vertically opposite angles are equal:

• α = α’
• β = β’

∎

Takeaway: This is a fundamental theorem in Euclidean geometry. It relies on the property that angles formed on a straight line sum to 180°.

Exercise 4

Prove that the product of two even numbers is even.

Type: Direct Proof

Solution

Step 1: Establish the hypotheses

Let a and b be even numbers.

By definition of even number:

• a = 2m, where m is an integer
• b = 2n, where n is an integer

Step 2: Calculate the product

Step	Expression	Justification
1	a · b = (2m)(2n)	Substitution
2	= 4mn	Multiplication
3	= 2(2mn)	Factor out 2
4	Let k = 2mn	k is an integer
5	a · b = 2k	Substitution

Conclusion

Since a · b = 2k (where k is an integer), the product is even by definition.

∎

Takeaway: In fact, the product of an even number with any integer is even, since even × integer = 2m × n = 2(mn).

Exercise 5

Prove that: (m → n) ⇔ (¬n → ¬m)

Type: Direct Proof (by equivalences)

Solution

We’ll prove that both expressions are logically equivalent by transforming them to a common form.

Step 1: Transform (m → n)

Step	Expression	Justification
1	m → n	Original expression
2	≡ ¬m ∨ n	Definition of implication: p → q ≡ ¬p ∨ q

Step 2: Transform (¬n → ¬m)

Step	Expression	Justification
1	¬n → ¬m	Original expression
2	\( \mathrm{ ≡ ¬(¬n) ∨ ¬m } \)	Definition of implication
3	≡ n ∨ ¬m	Double negation: ¬(¬p) ≡ p
4	≡ ¬m ∨ n	Commutativity of disjunction

Step 3: Compare results

Original Expression	Equivalent Form
m → n	¬m ∨ n
¬n → ¬m	¬m ∨ n

Both expressions are equivalent to ¬m ∨ n, therefore: (m → n) ⇔ (¬n → ¬m) ∎

Verification with Truth Table:

m	n	m → n	¬n → ¬m
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

The columns are identical, confirming the equivalence. ✓

Takeaway: This is the Law of Contraposition, fundamental in logic and mathematics. It says that “If P then Q” is logically equivalent to “If not Q then not P”.

Exercise 6

Prove that the product of two rational numbers is rational.

Type: Direct Proof

Solution

Step 1: Establish the hypothesis

Let a and b be rational numbers.

By definition of rational number:

• \( \mathrm{ a = \frac{p}{q} } \), where p, q ∈ ℤ and q ≠ 0
• \( \mathrm{ b = \frac{r}{s} } \), where r, s ∈ ℤ and s ≠ 0

Step 2: Calculate the product

Step	Expression	Justification
1	\( \mathrm{ a \cdot b = \frac{p}{q} \cdot \frac{r}{s} } \)	Substitution
2	\( = \mathrm{ \frac{p \cdot r}{q \cdot s} } \)	Fraction multiplication
3	\( = \mathrm{ \frac{ pr }{ qs} } \)	Simplified notation

Step 3: Verify that the result is rational

Condition	Verification
Is pr an integer?	Yes, product of integers is an integer ✓
Is qs an integer?	Yes, product of integers is an integer ✓
Is qs ≠ 0?	Yes, because q ≠ 0 and s ≠ 0 ✓

Conclusion:

Since \( \mathrm{ a \cdot b = \frac{pr}{qs} } \) is the quotient of two integers with non-zero denominator, the product is rational.

\[ \mathrm{ a, b \in \mathbb{Q} \Rightarrow a \cdot b \in \mathbb{Q} } \]

Takeaway: This result shows that ℚ is closed under multiplication. Together with closure under addition (Exercise 7), this means that ℚ forms a field.

Exercise 7

Prove that the sum of two rational numbers is rational.

Type: Direct Proof

Solution

Step 1: Establish the hypothesis

Let a and b be rational numbers.

By definition:

• \( \mathrm{ a = \frac{p}{q} } \) where p, q ∈ ℤ and q ≠ 0
• \( \mathrm{ b = \frac{r}{s} } \) where r, s ∈ ℤ and s ≠ 0

Step 2: Calculate the sum

Step	Expression	Justification
1	\( \mathrm{ a+b= \frac{p}{q} + \frac{r}{s} } \)	Substitution
2	\( = \frac{ ps +qr }{qs} \)	Addition of fractions (common denominator)

Step 3: Verify that the result is rational

Condition	Verification
Is ps + qr an integer?	Yes (sums and products of integers) ✓
Is qs an integer?	Yes (product of integers) ✓
Is qs ≠ 0?	Yes, because q ≠ 0 and s ≠ 0 ✓

Conclusion

Since \( a+b = \frac{ps + qr}{qs} \) satisfies the definition of a rational number, the sum is rational.

\[ \mathrm{ a,b \in \mathbb{Q} \Rightarrow a+b \in \mathbb{Q} } ∎ \]

Takeaway: ℚ is closed under addition, subtraction, multiplication, and division (except by zero). This makes ℚ an ordered field.

Exercise 8

For all x ∈ ℝ, x² ≥ 0.

Type: Proof by Cases

Solution

Key insight: Every real number x falls into exactly one category: positive, negative, or zero.

Let’s analyze each case:

Case 1: x = 0

Step	Statement	Justification
1	x = 0	Case hypothesis
2	x² = 0² = 0	Calculation
3	0 ≥ 0	True ✓

Case 2: x > 0

Step	Statement	Justification
1	x > 0	Case hypothesis
2	x² = x · x	Definition of square
3	x · x > 0	Product of positives is positive
4	x² ≥ 0	If x² > 0, then x² ≥ 0 ✓

Case 3: x < 0

Step	Statement	Justification
1	x < 0	Case hypothesis
2	x² = x · x	Definition of square
3	x · x > 0	Product of negatives is positive
4	x² ≥ 0	If x² > 0, then x² ≥ 0 ✓

Conclusion

In all three possible (exhaustive) cases, we have proven that x² ≥ 0.

\[ \mathrm{ \forall x \in \mathbb{R}: x^2 \geq 0 } ∎ \]

Takeaway: This fundamental property tells us that x² = 0 if and only if x = 0. It’s also why negative numbers have no real square roots.

Exercise 9

For all n ∈ ℕ, n² + n is even.

Type: Direct Proof

Solution

Step 1: Factor the expression

\[ \mathrm{ n^2+n=n(n+1) } \]

Step 2: Analyze the product n(n+1)

The numbers n and n+1 are consecutive integers.

Key property: In any pair of consecutive integers, one is even and one is odd.

Pair of consecutives	One even, one odd
1, 2	2 is even
2, 3	2 is even
7, 8	8 is even
n, n+1	One of them is even

Step 3: Conclude

Step	Statement	Justification
1	n or (n+1) is even	Property of consecutives
2	The product n(n+1) has an even factor	The even one is 2k for some k
3	n(n+1) = 2m for some integer m	The product contains factor 2
4	n² + n is even	Definition of even number

\[ \mathrm{ ∀n∈ℕ: 2∣(n^2+n) } ∎ \]

Takeaway: This result was used in Exercise 7 (intermediate level) to prove by contradiction that certain quadratic equations have no integer solutions. The property that the product of consecutives is even is a very useful tool in number theory.

Exercise 10

For all x ∈ ℝ, |x| ≥ 0.

Type: Proof by Cases

Solution

Definition of absolute value:

\[ \mathrm{ |x| = \begin{cases} x, & \text{if } x \ge 0 \\ -x, & \text{if } x<0 \end{cases} } \]

Every real number x belongs to exactly one of these two cases.

Case 1: x ≥ 0

Step	Statement	Justification
1	x ≥ 0	Case hypothesis
2	|x| = x	Definition of absolute value for x ≥ 0
3	|x| ≥ 0	From steps 1 and 2 ✓

Case 2: x < 0

Step	Statement	Justification
1	x < 0	Case hypothesis
2	|x| = −x	Definition of absolute value for x < 0
3	x < 0 implies −x > 0	Multiplying by −1 reverses the inequality
4	|x| = −x > 0	From steps 2 and 3
5	|x| ≥ 0	If |x| > 0, then |x| ≥ 0 ✓

Conclusion

In both possible cases, we have proven that |x| ≥ 0.

\[ \forall \mathrm{ x \in \mathbb{R}: |x| \ge 0 } ∎ \]

Takeaway: This is one of the fundamental properties of absolute value. In fact, |x| = 0 if and only if x = 0. Also, this proof is analogous to Exercise 8 (x² ≥ 0), since |x| = √(x²).

Exercise 11

“For all real x, y, \( \mathrm{ (x+y)^2=x^2+y^2 } \).”

Type: Refutation by Counterexample

Solution

Step 1: Analyze the proposition

The statement says that for all real numbers x and y, \( \mathrm{ (x+y)^2 = x^2 + y^2 } \) holds.

This is a universal proposition: \( \mathrm{ \forall x,y \in \mathbb{R}: (x+y)^2 = x^2 + y^2 } \).

Step 2: Verify the correct binomial formula

Recall the square of a binomial:

\[ \mathrm{ (x+y)^2 = x^2+2xy+y^2 } \]

For \( \mathrm{ (x+y)^2 = x^2 + y^2 } \) to hold, we would need:

\[ \begin{align} \mathrm{ x^2 + 2xy + y^2 } & = \mathrm{ x^2 + y^2 } \\ \mathrm{ 2xy } & = 0 \\ \mathrm{ xy } & = 0 \end{align} \]

This only happens when x = 0 or y = 0.

Step 3: Find a counterexample

To disprove a universal proposition, we just need one case where it fails.

x	y	\( (x+y)^2 \)	\( x^2 + y^2 \)	Equal?
1	1	\( (1+1)^2=4 \)	\( 1^2 + 1^2 = 2 \)	❌ NO

Verification:

• Left side: \((1+1)^2=2^2=4 \)
• Right side: \( 1^2 + 1^2= 1+1=2 \)
• \( 4 \neq 2 \)

Step 4: Conclusion

We have found a counterexample: x = 1, y = 1.

Therefore, the proposition “For all real x, y, \( \mathrm{ (x+y)^2=x^2+y^2 } \)” is FALSE. ∎

Takeaway: To refute a universal proposition (∀), we only need one counterexample. The correct formula is \( \mathrm{ (x+y)^2=x^2+2xy+y^2 } \). This is a very common algebraic error known as “forgetting the middle term”.

Exercise 12

“The sum of two irrational numbers is always an irrational number.”

Type: Refutation by Counterexample

Solution

Step 1: Analyze the proposition

The statement says that for all irrational numbers a and b, their sum a + b is irrational.

Formally: \( \mathrm{ \forall a,b \in \mathbb{R} ∖ \mathbb{Q}: (a+b) \in \mathbb{R} ∖ \mathbb{Q} } \) (note: \( \mathbb{R} ∖ \mathbb{Q} \) means the reals minus the rationals, leaving the irrationals)

Step 2: Find a counterexample

We need two irrational numbers whose sum is rational.

Counterexample 1: Using opposites

Number	Value	Irrational?
a	\( \sqrt{2} \)	✓ Yes
b	\( – \sqrt{2} \)	✓ Yes
a + b	\( \sqrt{2}+( -\sqrt{2} ) \)	❌ Is rational

Verification:

• \( \sqrt{2} \) is irrational (classically proven)
• \( – \sqrt{2} \) is irrational (if it were rational, \( \sqrt{2} = -(- \sqrt{2} ) \) would be rational)
• \( \sqrt{2} + ( – \sqrt{2} ) = 0 \), and \( 0 \) is rational ( \( 0 = \frac{0}{1} \) )

Counterexample 2: More elaborate

Number	Value	Irrational?
a	\( 1 + \sqrt{2} \)	✓ Yes
b	\( 1 – \sqrt{2} \)	✓ Yes
a + b	\( ( 1 + \sqrt{2} ) + ( 1 – \sqrt{2} ) = 2 \)	❌ Is rational

Step 3: Conclusion

We have found counterexamples where the sum of two irrationals is rational.

Therefore, the proposition “The sum of two irrationals is always irrational” is FALSE. ∎

Takeaway: Compare with Exercises 6 and 7 where we proved that ℚ is closed under sum and product. The irrationals are NOT closed under addition or multiplication. Another counterexample for the product: \( \sqrt{2} \cdot \sqrt{2} = 2 \) (rational).

Exercise 13

If n² is even, then n is even.

Type: Proof by Contraposition

Solution

Step 1: Identify the structure

Proposition	Definition
p	n² is even
q	n is even
Statement	p → q
Contrapositive	¬q → ¬p

Contrapositive: If n is odd, then n² is odd.

Step 2: Prove the contrapositive

Hypothesis: n is odd.

By definition: n = 2k + 1 for some k ∈ ℤ.

Step	Expression	Justification
1	n² = (2k + 1)²	Substitution
2	= 4k² + 4k + 1	Expansion
3	= 2(2k² + 2k) + 1	Factor out 2
4	Let m = 2k² + 2k	m is an integer
5	n² = 2m + 1	Form of odd

Conclusion: n² is odd. ✓

Step 3: Apply the equivalence

Since we proved ¬q → ¬p, and this is equivalent to p → q:

If \( \mathrm{ n^2 } \) is even, then \( \mathrm{ n } \) is even ∎

Takeaway: This property is used in the classic proof that √2 is irrational. It’s a perfect example of when contraposition simplifies the proof.

Exercise 14

Prove that for all x, y ∈ ℝ: |xy| = |x| · |y|

Type: Proof by Cases

Solution

We need to consider all possible cases based on the signs of x and y.

Case 1: x ≥ 0 and y ≥ 0

Step	Statement	Justification
1	xy ≥ 0	Product of non-negatives
2	|xy| = xy	Definition of absolute value
3	|x| = x, |y| = y	Definition (x, y ≥ 0)
4	|x| · |y| = xy	Substitution
5	|xy| = |x| · |y|	From steps 2 and 4 ✓

Case 2: x ≥ 0 and y < 0

Step	Statement	Justification
1	xy ≤ 0	Product of opposite signs
2	|xy| = −xy	Definition of absolute value
3	|x| = x, |y| = −y	Definitions
4	\( \mathrm{ |x| · |y| = x · (−y) = −xy } \)	Substitution
5	|xy| = |x| · |y|	From steps 2 and 4 ✓

Case 3: x < 0 and y ≥ 0

Step	Statement	Justification
1	xy ≤ 0	Product of opposite signs
2	|xy| = −xy	Definition
3	|x| = −x, |y| = y	Definitions
4	\( \mathrm{ |x| · |y| = (−x) · y = −xy } \)	Substitution
5	|xy| = |x| · |y|	From steps 2 and 4 ✓

Case 4: x < 0 and y < 0

Step	Statement	Justification
1	xy > 0	Product of negatives
2	|xy| = xy	Definition
3	|x| = −x, |y| = −y	Definitions
4	\( \mathrm{ |x| · |y| = (−x)(−y) = xy } \)	Substitution
5	|xy| = |x| · |y|	From steps 2 and 4 ✓

Conclusion

In all possible cases: |xy| = |x| · |y| ∎

Takeaway: This property is fundamental in mathematical analysis. Proof by cases is necessary because the definition of absolute value has two branches depending on the sign.

Exercise 15

If n > 2, then there is no integer m such that n + m = nm.

Type: Direct Proof

Solution

Step 1: Solve for m from the equation

Step	Expression	Justification
1	n + m = nm	Given equation
2	n = nm − m	Subtract m from both sides
3	n = m(n − 1)	Factor out m
4	m = n/(n − 1)	Solve for m (valid if n ≠ 1)

Step 2: Analyze when m is an integer

For m = n/(n − 1) to be an integer, (n − 1) must divide n.

We rewrite:

\[ m = \frac{n}{n-1} = \frac{(n-1)+1}{n-1} = 1 + \frac{1}{n-1} \]

Step 3: Determine when 1/(n−1) is an integer

Condition	Value of n−1	Value of n	Does n > 2 hold?
1/(n−1) = 1	n − 1 = 1	n = 2	❌ No
1/(n−1) = −1	n − 1 = −1	n = 0	❌ No

For n > 2: n − 1 > 1, so 0 < 1/(n−1) < 1.

Since 1/(n−1) is not an integer for n > 2, then m is not an integer either.

Conclusion

If \( n > 2 \), there is no \( m \in \mathbb{Z} \) such that \( \mathrm{n+m=nm} \) ∎

Takeaway: The only cases where an integer solution exists are n = 2 (with m = 2) and n = 0 (with m = 0). But these are excluded by the condition n > 2.

Exercise 16

Let x and y be positive reals. If xy < 5, then x < √5 or y < √5.

Type: Proof by Contraposition

Solution

Step 1: Identify the structure

Proposition	Definition
p	xy < 5
q	x < √5 ∨ y < √5
Contrapositive	¬q → ¬p

Contrapositive: If x ≥ √5 and y ≥ √5, then xy ≥ 5.

Step 2: Prove the contrapositive

Hypothesis: x ≥ √5 and y ≥ √5

Step	Statement	Justification
1	x ≥ √5	Hypothesis
2	y ≥ √5	Hypothesis
3	xy ≥ √5 · √5	Multiply inequalities (x, y > 0)
4	xy ≥ 5	√5 · √5 = 5

Contrapositive conclusion: xy ≥ 5, that is, ¬(xy < 5). ✓

Step 3: Apply the equivalence

Since ¬q → ¬p is equivalent to p → q:

If xy < 5, then x < √5 or y < √5

∎

Takeaway: Note how the negation of “x < √5 ∨ y < √5” is “x ≥ √5 ∧ y ≥ √5” (De Morgan’s Law). Contraposition converts a disjunction in the conclusion into a conjunction in the hypothesis.

Exercise 17

Let m and n be integers. If mn is even, then m is even or n is even.

Type: Proof by Contraposition

Solution

Step 1: Identify the structure

Proposition	Definition
p	mn is even
q	m is even ∨ n is even
Contrapositive	¬q → ¬p

Contrapositive: If m is odd and n is odd, then mn is odd.

Step 2: Prove the contrapositive

Hypothesis: m is odd and n is odd.

By definition:

• m = 2a + 1 for some a ∈ ℤ
• n = 2b + 1 for some b ∈ ℤ

Step	Expression	Justification
1	mn = (2a + 1)(2b + 1)	Substitution
2	= 4ab + 2a + 2b + 1	Expansion
3	= 2(2ab + a + b) + 1	Factor out 2
4	Let k = 2ab + a + b	k is an integer
5	mn = 2k + 1	Form of odd

Conclusion: mn is odd. ✓

Step 3: Apply the equivalence, we get:

If mn is even, then m is even or n is even. ∎

Takeaway: This result is the “converse” of the fact that even × any integer = even. Here we prove: if the product is even, at least one of the factors must be even.

Exercise 18

If a is rational, \( a ≠ 0 \), and \( b \) is irrational, then ab is irrational.

Type: Proof by Contradiction

Solution

Step 1: Assume the opposite

Suppose that ab is rational.

Step 2: Establish the hypotheses

• \( \mathrm{a} \) is rational with \( \mathrm{a} ≠ 0 \): \( \mathrm{ a = \frac{p}{q} } \) where \( \mathrm{ p, q } ∈ ℤ \), \( \mathrm{q} ≠ 0 \), \( \mathrm{p} ≠ 0 \)
• \( b \) is irrational
• Assumption: \( \mathrm{ab} \) is rational, i.e., \( \mathrm{ ab = \frac{r}{s} } \) where \( \mathrm{ r, s } ∈ ℤ \), \( \mathrm{s} ≠ 0 \)

Step 3: Derive a contradiction

Step	Expression	Justification
1	ab = r/s	Assumption
2	b = (r/s) / a	Solve for b (valid since a ≠ 0)
3	\( \mathrm{ b = (r/s) / (p/q) } \)	Substitution
4	b = (r/s) · (q/p)	Division of fractions
5	b = rq / sp	Multiplication of fractions

Analysis:

• rq is an integer (product of integers)
• sp is an integer (product of integers)
• sp ≠ 0 (because s ≠ 0 and p ≠ 0)

Therefore, b = rq/sp is rational.

Step 4: Contradiction

This contradicts the hypothesis that b is irrational.

Conclusion

Our assumption (ab is rational) is false.

If \( \mathrm{a} \in \mathbb{Q}, a \neq 0, \mathrm{b} \notin \mathbb{Q} \), then \( \mathrm{ab} \notin \mathbb{Q} ∎ \)

Takeaway: The condition a ≠ 0 is essential. If a = 0, then ab = 0 which is rational, regardless of whether b is irrational.

Exercise 19

Prove that for all n ≥ 1:

\[ \mathrm{ 1+2+3+…+n= \frac{n(n+1)}{2}​ } \]

Type: Proof by Induction

Solution

Structure of the induction method:

Step	Description
Base case	Verify that the formula is true for n = 1
Inductive hypothesis	Assume the formula is true for n = k
Inductive step	Prove that the formula is true for n = k + 1

Step 1: Base Case (n = 1)

Left side	Right side	Equal?
1	\( \frac{ 1(1+1) }{2} = \frac{ 1 \cdot 2 }{2} = \frac{2}{2} = 1 \)	✓

The base case holds.

Step 2: Inductive Hypothesis

Assume the formula is true for some n = k, that is:

\( \mathrm{ 1+2+3+…+k= \frac{ k(k+1) }{2}​ } \)

Step 3: Inductive Step (prove for n = k + 1)

We want to prove that:

\[ \mathrm{ 1+2+3+ \dotsb + k + (k+1)= \frac{ (k+1)(k+2) }{2} } \]

Step	Expression	Justification
1	\( \mathrm{ 1 + 2 + \ldots + k + (k+1) } \)	Left side for n = k+1
2	\( \mathrm{ = \frac{k(k+1)}{2} + (k+1) } \)	Applying inductive hypothesis
3	\( \mathrm{ = \frac{k(k+1)}{2} + \frac{2(k+1)}{2} } \)	Common denominator
4	\( \mathrm{ = \frac{k(k+1) + 2(k+1)}{2} } \)	Addition of fractions
5	\( \mathrm{ = \frac{(k+1)(k + 2)}{2} } \)	Factor out (k+1)
6	\( \mathrm{ = \frac{(k+1)((k+1)+1)}{2} } \)	Rewrite k+2 as (k+1)+1

This is exactly the formula for n = k + 1. ✓

Conclusion

By the Principle of Mathematical Induction:

\[ \mathrm{ \boxed{1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}} ∎ } \]

Takeaway: This formula is known as Gauss’s formula. Legend has it that Gauss discovered it at age 7 when his teacher asked him to sum the numbers from 1 to 100.

Exercise 20

“For every integer \( n \), \( \mathrm{ n^2 + n + 41 } \) is a prime number.”

Type: Refutation by Counterexample

Solution

Step 1: Analyze the proposition

The statement says that for every integer n, the value of \( \mathrm{ n^2 + n + 41 } \) is prime.

This is a universal proposition: \( \mathrm{ \forall n \in \mathbb{Z}: n^2 + n + 41 } \) is prime

Step 2: Verify some cases (it appears to work)

n	\( n^2 + n + 41 \)	Prime?
0	\( 0 + 0 + 41 = 41 \)	✓ Yes
1	\( 1 + 1 + 41 = 43 \)	✓ Yes
2	\( 4 + 2 + 41 = 47 \)	✓ Yes
3	\( 9 + 3 + 41 = 53 \)	✓ Yes
5	\( 25 + 5 + 41 = 71 \)	✓ Yes
10	\( 100 + 10 + 41 = 151 \)	✓ Yes
39	\( 1521 + 39 + 41 = 1601 \)	✓ Yes

It seems to always work! But wait…

Step 3: Find the counterexample

Let’s try n = 40:

Step	Calculation	Result
1	\( n^2 = 40^2 \)	1600
2	\( n = 40 \)	40
3	\( n^2 + n + 41 \)	\( 1600 + 40 + 41 = 1681 \)
4	\( \sqrt{1681} \)	41
5	\( 1681 = 41 \times 41 = 41^2 \)	Not prime!

Verification:

\[ 40^2 + 40 + 41 = 1600 + 40 + 41 = 1681 = 41^2 \]

Since \( 1681 = 41 \times 41 \), the number is not prime.

Step 4: Conclusion

We have found a counterexample: n = 40.

The proposition is FALSE ∎

Takeaway: This is the famous Euler polynomial (1772). It generates prime numbers for n = 0, 1, 2, …, 39 (40 consecutive values!), but fails at n = 40 and n = 41. This historic example shows why we can’t rely on “many cases” to prove universal propositions.

Exercise 21

For all n ≥ 1, \( n^3 – n \) is divisible by 3.

Type: Proof by Induction

Solution

Step 1: Base Case (n = 1)

Calculation	Result
\( n^3 – n = 1^3 – 1 \)	\( 1 – 1 = 0 \)
Is 0 divisible by 3?	Yes, \( 0 = 3 \times 0 \) ✓

The base case holds.

Step 2: Inductive Hypothesis

Suppose that for some k ≥ 1:

\( k^3-k = 3m \) for some \( m \in \mathbb{Z} \)

Step 3: Inductive Step (prove for n = k + 1)

Step	Expression	Justification
1	\( (k+1)^3 – (k+1) \)	Expression to prove
2	\( = k^3 + 3k^2 + 3k + 1 – k – 1 \)	Expansion of cube
3	\( = k^3 + 3k^2 + 3k – k \)	Simplification
4	\( = (k^3 – k) + 3k^2 + 3k \)	Regrouping
5	\( = (k^3 – k) + 3(k^2 + k) \)	Factor out 3

Divisibility analysis:

Term	Divisible by 3?	Justification
\( k^3 – k \)	✓ Yes	Inductive hypothesis
\( 3(k^2 + k) \)	✓ Yes	Has factor 3
Total sum	✓ Yes	Sum of multiples of 3

Conclusion

\[ \boxed{\forall n \geq 1: 3 \mid (n^3 – n) ∎ } \]

Takeaway: Alternatively, \( n^3 – n = n(n^2-1) = (n-1)n(n+1) \), which is the product of three consecutive integers. Among three consecutive integers, there’s always a multiple of 3.

Exercise 22

Prove that for all n ≥ 1:

\( 1 + 2 + 4 + \ldots + 2^{n-1} = 2^n – 1 \)

Type: Proof by Induction

Solution

This is the sum of a geometric series with first term 1 and ratio 2.

Step 1: Base Case (n = 1)

Left side	Right side	Equal?
\( 2^{1-1} = 2^0 = 1 \)	\( 2^1 – 1 = 2 – 1 = 1 \)	✓

Step 2: Inductive Hypothesis

Suppose that for some k ≥ 1:

\[ 1 + 2 + 4 + \ldots + 2^{k-1} = 2^k – 1 \]

Step 3: Inductive Step

Step	Expression	Justification
1	\( 1 + 2 + \ldots + 2^{k-1} + 2^k \)	For n = k+1
2	\( = (2^k – 1) + 2^k \)	Inductive hypothesis
3	\( = 2 \cdot 2^k – 1 \)	Addition
4	\( = 2^{k+1} – 1 \)	Property of exponents

Conclusion

\[ \boxed{1 + 2 + 4 + \ldots + 2^{n-1} = 2^n – 1 ∎} \]

Takeaway: This formula has a practical application in computer science: it represents the maximum value storable in n bits (e.g., 8 bits → 255).

Exercise 23

If c is an odd number, then the equation \( n² + n − c = 0 \) has no integer solutions.

Type: Proof by Contradiction

Solution

Step 1: Assume the opposite

Suppose that there exists an integer \( n \) such that \( n² + n − c = 0 \).

Step 2: Derive consequences

From the equation:

\[ n^2 + n = c \]

We factor the left side:

\[ n(n + 1) = c \]

Step 3: Analyze the parity of \( n(n+1) \)

The numbers \( n \) and \( n+1 \) are consecutive integers.

Property	Explanation
\( n \) and \( n+1 \) consecutive	One is even, one is odd
\( n(n+1) \)	Product of even × odd = even

Therefore, \( n(n+1) \) is always even.

Step 4: Reach the contradiction

Statement	Justification
\( n(n+1) = c \)	From the equation
\( n(n+1) \) is even	Product of consecutives
\( c \) is even	Equality

But the hypothesis says that c is odd. ⚡ CONTRADICTION ⚡

Conclusion

Our assumption is false. Therefore:

If \( c \) is odd, \( n^2+n-c=0 \) has no integer solutions

∎

Takeaway: This exercise uses the result from Exercise 9 (basic level): the product of two consecutive integers is always even. The contradiction structure is clear: we assume a solution exists and conclude that an odd number is even.

Exercise 24

Prove that every natural number greater than or equal to 7 is the sum of a multiple of 3 and a multiple of 4.

Type: Proof by Induction

Solution

We want to prove: For all \( n ≥ 7 \), there exist non-negative integers a and b such that \( n = 3a + 4b \).

Structure of strong induction:

Step	Description
Base cases	Verify for n = 7, 8, 9
Inductive hypothesis	Assume true for all k with 7 ≤ k < n
Inductive step	Prove for n (using some previous k)

Step 1: Base Cases

n	Decomposition	Verification
7	3(1) + 4(1)	3 + 4 = 7 ✓
8	3(0) + 4(2)	0 + 8 = 8 ✓
9	3(3) + 4(0)	9 + 0 = 9 ✓

Step 2: Inductive Hypothesis (Strong Induction)

Suppose that for all k with \( 7 ≤ k < n \), \( k = 3a + 4b \) holds.

Step 3: Inductive Step (\( n ≥ 10\))

Let \(n ≥ 10\). Consider \(n − 3\):

Step	Statement	Justification
1	n ≥ 10	Hypothesis
2	n − 3 ≥ 7	Arithmetic
3	n − 3 = 3a + 4b	Inductive hypothesis
4	n = (n − 3) + 3	Arithmetic
5	n = (3a + 4b) + 3	Substitution
6	n = 3(a + 1) + 4b	Factor out

Conclusion

By the Principle of Strong Induction:

\( \forall n \geq 7: n=3a+4b \) for some \( a,b \geq 0 \) ∎

Takeaway: This problem uses strong induction because we need to refer to n − 3 (not n − 1). The base cases 7, 8, 9 cover the three possible residues modulo 3, which guarantees that the inductive step always works.

Document Summary

Throughout this document, we have developed a total of 84 solved exercises in propositional logic, distributed across the following sections:

Section	Topic	Exercises
I	Propositions and Logical Connectives	17
II	Truth Tables	12
III	Logical Equivalences	11
IV	Rules of Inference	8
V	Logic Circuits	12
VI	Mathematical Proofs	24
	TOTAL	84

Each exercise includes a detailed step-by-step solution with clear justifications and key takeaways that reinforce the underlying concepts.

What’s Next?

In the next chapter, we’ll tackle Quantifier Logic (a topic within Predicate Logic or First-Order Logic), where we’ll explore:

• ✅ Universal Quantifier (∀): “For all…”
• ✅ Existential Quantifier (∃): “There exists at least one…”
• ✅ Predicates and propositional functions
• ✅ Negation of quantified propositions
• ✅ Rules of inference for quantifiers

This extension of propositional logic will allow us to express and prove propositions about complete sets of objects, not just individual propositions.