Logic and Proofs - Comprehensive Study Guide

🎯 Introduction to Logic

What is Logic?

Logic is the study of consequence. Given a few mathematical statements or facts, logic helps us determine which conclusions validly follow from those premises.

Logic aims to determine in which cases a conclusion is, or is not, a consequence of a set of premises.

Simple Example

Premise #1: If Sara eats her vegetables, then she can have a cookie.
Premise #2: Sara eats her vegetables.
Conclusion: Sara gets a cookie. ✓

Historical Context

Propositional logic was first developed systematically by the Greek philosopher Aristotle more than 2,300 years ago.

💭 Propositions

Definition

A proposition is a declarative sentence that is either true or false (but not both).

Examples of Propositions

The Moon is made of green cheese. (False, but still a proposition)
Cairo is the capital of Egypt. (True)
Toronto is the capital of Canada. (False)
1 + 0 = 1 (True)
0 + 0 = 2 (False)

Examples that are NOT Propositions

Sit down! (Command - not declarative)
What time is it? (Question - not declarative)
x + 1 = 2 (Variable - truth value depends on x)
x + y = z (Multiple variables - not a statement)

Propositional Variables

We use variables to represent propositions:

p, q, r, s, ... represent individual propositions
T represents a proposition that is always true
F represents a proposition that is always false

🔗 Logical Connectives

Compound propositions are constructed from simpler propositions using logical connectives.

Negation (¬)

The negation of proposition p is denoted by ¬p (read as "not p") and represents the opposite truth value of p.

p	¬p
T	F
F	T

Example

p: "The earth is round."

¬p: "The earth is not round."

Conjunction (∧)

The conjunction of propositions p and q is denoted by p ∧ q (read as "p and q") and is true only when both p and q are true.

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

Example

p: "I am at home."

q: "It is raining."

p ∧ q: "I am at home and it is raining."

Disjunction (∨)

The disjunction of propositions p and q is denoted by p ∨ q (read as "p or q") and is true when at least one of p or q is true.

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

Example

p: "I am at home."

q: "It is raining."

p ∨ q: "I am at home or it is raining."

⚠️ Two Meanings of "OR" in English

Inclusive Or (∨): "Students who have taken CS202 or Math120 may take this class" - can take one or both prerequisites
Exclusive Or (⊕): "Soup or salad comes with this entrée" - can have one but not both

Exclusive Or (⊕)

The exclusive or (XOR) of propositions p and q is denoted by p ⊕ q and is true when exactly one of p or q is true (but not both).

p	q	p ⊕ q
T	T	F
T	F	T
F	T	T
F	F	F

Implication (→)

The conditional statement or implication p → q is read as "if p, then q" where:

p is the hypothesis (antecedent or premise)
q is the conclusion (or consequence)

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

🔑 Understanding Implication

Think of an implication as an obligation or contract:

"If I am elected, then I will lower taxes."
"If you get 100% on the final, then you will get an A."

Key Point: The implication is false only when the hypothesis is true but the conclusion is false. If the hypothesis is false, the implication is automatically true (vacuously true).

Ways to Express p → q

• if p, then q
• p implies q
• if p, q
• p only if q
• q unless ¬p
• q when p
• q if p
• p is sufficient for q
• q is necessary for p
• q whenever p
• q follows from p
• a necessary condition for p is q
• a sufficient condition for q is p

Related Conditional Statements

From p → q, we can form three related statements:

Converse

q → p

Interchange hypothesis and conclusion

Inverse

¬p → ¬q

Negate both hypothesis and conclusion

Contrapositive

¬q → ¬p

Negate both and interchange

Example

Original: "If it is raining, then I will not go to town."

Converse: If I do not go to town, then it is raining.
Inverse: If it is not raining, then I will go to town.
Contrapositive: If I go to town, then it is not raining.

Biconditional (↔)

The biconditional p ↔ q is read as "p if and only if q" (abbreviated as "p iff q") and is true when p and q have the same truth value.

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

Key Insight

Note that the biconditional truth table is the exact opposite of exclusive or (⊕).

p ↔ q ≡ ¬(p ⊕ q)

Ways to Express p ↔ q

p if and only if q
p iff q
p is necessary and sufficient for q
if p then q, and conversely

⚖️ Logical Equivalences

Two compound propositions are logically equivalent if they have the same truth value in all possible cases. We write p ≡ q to denote that p and q are logically equivalent.

Important Logical Equivalences

Identity Laws

p ∧ T ≡ p
p ∨ F ≡ p

Domination Laws

p ∨ T ≡ T
p ∧ F ≡ F

Idempotent Laws

p ∨ p ≡ p
p ∧ p ≡ p

Double Negation

¬(¬p) ≡ p

Commutative Laws

p ∨ q ≡ q ∨ p
p ∧ q ≡ q ∧ p

Associative Laws

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

Distributive Laws

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

De Morgan's Laws

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

Absorption Laws

p ∨ (p ∧ q) ≡ p
p ∧ (p ∨ q) ≡ p

Negation Laws

p ∨ ¬p ≡ T
p ∧ ¬p ≡ F

Conditional Statement Equivalences

p → q ≡ ¬p ∨ q
p → q ≡ ¬q → ¬p (contrapositive)
p ↔ q ≡ (p → q) ∧ (q → p)

🔍 Predicate Logic

Predicate logic extends propositional logic by allowing us to reason about objects and their properties. It introduces variables, predicates, and quantifiers.

What are Predicates?

Examples

P(x): "x is greater than 5" - P is a predicate, x is a variable
Q(x, y): "x + y = 10" - Q is a two-variable predicate
R(x): "x is a prime number"

These statements become propositions when we assign specific values to the variables or use quantifiers.

Domain of Discourse

The domain of discourse (or universe of discourse) is the set of all possible values that variables can take.

∀∃ Quantifiers

Universal Quantifier (∀)

The universal quantifier ∀x P(x) means "for all x, P(x) is true" or "P(x) is true for every x in the domain."

Examples

∀x (x + 0 = x) - "For all numbers x, x + 0 = x"
∀x (x² ≥ 0) - "For all real numbers x, x squared is non-negative"

Existential Quantifier (∃)

The existential quantifier ∃x P(x) means "there exists an x such that P(x) is true" or "P(x) is true for at least one x in the domain."

Examples

∃x (x² = 4) - "There exists a number x such that x² = 4" (e.g., x = 2)
∃x (x + 5 = 0) - "There exists an x such that x + 5 = 0" (x = -5)

Negating Quantifiers

De Morgan's Laws for Quantifiers

¬∀x P(x) ≡ ∃x ¬P(x)
¬∃x P(x) ≡ ∀x ¬P(x)

In words:

"Not all x satisfy P" is equivalent to "There exists an x that doesn't satisfy P"
"There doesn't exist an x satisfying P" is equivalent to "All x don't satisfy P"

Multiple Quantifiers

Order Matters!

∀x ∃y (x + y = 0) - "For every x, there exists a y such that x + y = 0" (TRUE for real numbers)
∃y ∀x (x + y = 0) - "There exists a y such that for all x, x + y = 0" (FALSE for real numbers)

The order of quantifiers can completely change the meaning!

✓ Proofs

A proof is a valid argument that establishes the truth of a mathematical statement. Proofs use axioms, definitions, and previously proven statements along with rules of inference.

Types of Proofs

1. Direct Proof

Assume the hypothesis is true and use logical steps to show the conclusion must be true.

Example: Prove that if n is even, then n² is even

Proof:

Assume n is even
Then n = 2k for some integer k (definition of even)
n² = (2k)² = 4k² = 2(2k²)
Since 2k² is an integer, n² is even ✓

2. Proof by Contrapositive

To prove p → q, instead prove ¬q → ¬p (which is logically equivalent).

Example: If n² is odd, then n is odd

Proof by Contrapositive: If n is even, then n² is even (proven above)

3. Proof by Contradiction

Assume the statement is false and derive a contradiction.

Example: Prove √2 is irrational

Proof:

Assume √2 is rational (contradiction assumption)
Then √2 = a/b where a,b are integers with no common factors
2 = a²/b², so 2b² = a²
Therefore a² is even, so a is even
Let a = 2k, then 2b² = 4k², so b² = 2k²
Therefore b² is even, so b is even
But this contradicts our assumption that a and b have no common factors!
Therefore √2 must be irrational ✓

📜 Rules of Inference

Rules of inference are patterns of reasoning that allow us to derive conclusions from premises. An argument is valid if the conclusion logically follows from the premises.

⚠️ Important Note

A valid argument can lead to an incorrect conclusion if one of its premises is false! Validity refers to the logical structure, not the truth of the premises.

The Nine Rules of Inference

1. Modus Ponens (Law of Detachment)

p → q
p

∴ q

Tautology: [p ∧ (p → q)] → q

Example:

If it is snowing, then I will study discrete math.

It is snowing.

Therefore, I will study discrete math.

2. Modus Tollens

p → q
¬q

∴ ¬p

Tautology: [¬q ∧ (p → q)] → ¬p

Example:

If it is snowing, then I will study discrete math.

I will not study discrete math.

Therefore, it is not snowing.

3. Hypothetical Syllogism

p → q
q → r

∴ p → r

Tautology: [(p → q) ∧ (q → r)] → (p → r)

Example:

If it snows, then I will study discrete math.

If I study discrete math, I will get an A.

Therefore, if it snows, I will get an A.

4. Disjunctive Syllogism

p ∨ q
¬p

∴ q

Tautology: [¬p ∧ (p ∨ q)] → q

Example:

I will study discrete math or I will study English literature.

I will not study discrete math.

Therefore, I will study English literature.

5. Addition

∴ p ∨ q

Tautology: p → (p ∨ q)

Example:

I will study discrete math.

Therefore, I will study discrete math or I will visit Las Vegas.

6. Simplification

p ∧ q

∴ p

Tautology: (p ∧ q) → p

Example:

I will study discrete math and English literature.

Therefore, I will study discrete math.

7. Conjunction

p
q

∴ p ∧ q

Tautology: [(p) ∧ (q)] → (p ∧ q)

Example:

I will study discrete math.

I will study English literature.

Therefore, I will study discrete math and English literature.

8. Resolution

p ∨ q
¬p ∨ r

∴ q ∨ r

Tautology: [(p ∨ q) ∧ (¬p ∨ r)] → (q ∨ r)

Note: Resolution plays an important role in AI and is used in Prolog.

Example:

I will study discrete math or I will study databases.

I will not study discrete math or I will study English literature.

Therefore, I will study databases or English literature.

Building Arguments with Rules of Inference

Example: Canoe Trip Argument

Premises:

It is not sunny this afternoon and it is colder than yesterday.
If we go swimming, then it is sunny this afternoon.
If we do not go swimming, then we will take a canoe trip.
If we take a canoe trip, then we will be home by sunset.

Conclusion: We will be home by sunset.

Translation to propositions:

p: It is sunny this afternoon
q: It is colder than yesterday
r: We go swimming
s: We will take a canoe trip
t: We will be home by sunset

Premises in symbolic form:

1. ¬p ∧ q
2. r → p
3. ¬r → s
4. s → t

Proof:

¬p ∧ q (Premise 1)
¬p (Simplification from step 1)
r → p (Premise 2)
¬r (Modus Tollens from steps 2 and 3)
¬r → s (Premise 3)
s (Modus Ponens from steps 4 and 5)
s → t (Premise 4)
t (Modus Ponens from steps 6 and 7) ✓

💡 Strategy for Building Arguments

Translate the English statements into propositional logic
Identify the premises and the desired conclusion
Apply rules of inference step by step
Each step should reference previous steps or premises
Continue until you reach the desired conclusion

📝 Quick Reference Summary

Logical Connectives

Name	Symbol	Example	True When
Negation	¬	¬p	p is false
Conjunction	∧	p ∧ q	Both p and q are true
Disjunction	∨	p ∨ q	At least one of p or q is true
Exclusive Or	⊕	p ⊕ q	Exactly one of p or q is true
Implication	→	p → q	If p is true, then q is true
Biconditional	↔	p ↔ q	p and q have the same truth value

Key Equivalences to Remember

• De Morgan's Laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q
• Implication: p → q ≡ ¬p ∨ q
• Contrapositive: p → q ≡ ¬q → ¬p
• Biconditional: p ↔ q ≡ (p → q) ∧ (q → p)

Quantifiers

∀x P(x): "For all x, P(x) is true"
∃x P(x): "There exists an x such that P(x) is true"
¬∀x P(x) ≡ ∃x ¬P(x)
¬∃x P(x) ≡ ∀x ¬P(x)