Logic and Proofs

Introduction

Logic is the foundation of mathematical reasoning and computer science. Every algorithm, every program, and every circuit relies on logical operations. Understanding logic enables you to write correct programs, design digital circuits, and construct valid arguments.

Learning Objectives

By the end of this reading, you will be able to:

• Identify and construct propositions
• Apply logical connectives (AND, OR, NOT, etc.)
• Build and evaluate truth tables
• Understand logical equivalence and implications
• Construct basic mathematical proofs

1. Propositions

A proposition is a declarative statement that is either true or false, but not both.

Examples of Propositions

• "2 + 2 = 4" (True)
• "Paris is the capital of Germany" (False)
• "All prime numbers greater than 2 are odd" (True)

Non-Propositions

• "What time is it?" (Question)
• "Close the door" (Command)
• "x + 1 = 5" (Variable - truth depends on x)

We typically denote propositions with lowercase letters: p, q, r, s...

2. Logical Connectives

Logical connectives combine propositions to form compound propositions.

2.1 Negation (NOT)

The negation of p, written ¬p (or ~p, or NOT p), is true when p is false, and false when p is true.

Example: If p = "It is raining", then ¬p = "It is not raining"

2.2 Conjunction (AND)

The conjunction of p and q, written p ∧ q, is true only when both p and q are true.

Example: "It is raining AND it is cold" is true only if both conditions hold.

2.3 Disjunction (OR)

The disjunction of p and q, written p ∨ q, is true when at least one of p or q is true.

Note: This is inclusive OR. "Soup or salad" in everyday speech often means exclusive OR (one or the other, but not both).

2.4 Exclusive OR (XOR)

The exclusive or of p and q, written p ⊕ q, is true when exactly one of p or q is true.

2.5 Implication (IF-THEN)

The conditional p → q reads "if p, then q" where p is the hypothesis and q is the conclusion.

Key insight: An implication is only false when the hypothesis is true and the conclusion is false.

Example: "If it rains, the ground is wet"

• Rain + Wet ground = True (as expected)
• Rain + Dry ground = False (contradiction!)
• No rain + Wet ground = True (sprinklers could work)
• No rain + Dry ground = True (perfectly normal)

2.6 Biconditional (IF AND ONLY IF)

The biconditional p ↔ q is true when p and q have the same truth value.

Example: "You pass if and only if you score above 60%" - passing and scoring above 60% must both be true or both be false.

3. Truth Tables

Truth tables systematically list all possible combinations of truth values for a compound proposition.

Building a Truth Table

For a proposition with n variables, there are 2^n rows.

Example: Construct a truth table for (p ∧ q) → ¬r

4. Logical Equivalence

Two propositions are logically equivalent if they have the same truth value in all cases. We write p ≡ q.

Important Equivalences

De Morgan's Laws:

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

Double Negation:

• ¬(¬p) ≡ p

Contrapositive:

• (p → q) ≡ (¬q → ¬p)

Distributive Laws:

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

Identity Laws:

• p ∧ T ≡ p
• p ∨ F ≡ p

Domination Laws:

• p ∨ T ≡ T
• p ∧ F ≡ F

5. Predicates and Quantifiers

Predicates

A predicate is a statement containing variables that becomes a proposition when variables are assigned values.

Example: P(x) = "x > 5"

• P(3) is false
• P(10) is true

Quantifiers

Universal Quantifier (∀): "For all"

• ∀x P(x) means P(x) is true for every x in the domain

Existential Quantifier (∃): "There exists"

• ∃x P(x) means P(x) is true for at least one x in the domain

Negating Quantifiers:

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

Example: "Not all birds can fly" ≡ "There exists a bird that cannot fly"

6. Proof Techniques

6.1 Direct Proof

To prove p → q directly, assume p is true and show q must be true.

Example: Prove "If n is even, then n² is even"

Proof: Assume n is even. Then n = 2k for some integer k. n² = (2k)² = 4k² = 2(2k²) Since 2k² is an integer, n² is even. ∎

6.2 Proof by Contrapositive

To prove p → q, prove ¬q → ¬p instead.

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

Proof: We prove the contrapositive: "If n is even, then n² is even" If n is even, n = 2k, so n² = 4k² = 2(2k²), which is even. ∎

6.3 Proof by Contradiction

To prove p, assume ¬p and derive a contradiction.

Example: Prove √2 is irrational.

Proof: Assume √2 is rational. Then √2 = a/b where a, b are integers with no common factors. Squaring: 2 = a²/b², so a² = 2b². Thus a² is even, so a is even. Let a = 2c. Then 4c² = 2b², so b² = 2c². Thus b² is even, so b is even. But if both a and b are even, they share factor 2. Contradiction! ∎

6.4 Proof by Cases

Divide into exhaustive cases and prove each separately.

Example: Prove |xy| = |x||y|

Proof: Case 1: x ≥ 0 and y ≥ 0. Then |xy| = xy = |x||y|. Case 2: x < 0 and y < 0. Then |xy| = xy = (-x)(-y) = |x||y|. Case 3: One positive, one negative. Then |xy| = -xy = |x||y|. ∎

6.5 Mathematical Induction

To prove P(n) for all n ≥ base case:

1. Base case: Prove P(base) is true
2. Inductive step: Prove P(k) → P(k+1)

Example: Prove 1 + 2 + ... + n = n(n+1)/2

Base case: n = 1: 1 = 1(2)/2 = 1 ✓

Inductive step: Assume true for k: 1 + 2 + ... + k = k(k+1)/2

For k+1: 1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2 ✓ ∎

7. Application to Computer Science

Boolean Logic in Programming

# Logical operators in Python
a = True
b = False

print(a and b)    # False (conjunction)
print(a or b)     # True (disjunction)
print(not a)      # False (negation)

# Short-circuit evaluation
# Python stops evaluating when result is determined
x = 5
if x > 0 and x < 10:  # Both conditions checked
    print("In range")

# If first condition is False, second isn't evaluated
if False and some_expensive_function():
    pass  # some_expensive_function() never called

Conditional Logic

# Implication in code: p → q
# "If user is admin, grant access"
if is_admin:
    grant_access()

# Common pattern: validating preconditions
def divide(a, b):
    # Precondition: b != 0 → return a/b
    if b == 0:
        raise ValueError("Cannot divide by zero")
    return a / b

De Morgan's Laws in Practice

# These are equivalent:
not (a and b)  ≡  (not a) or (not b)
not (a or b)   ≡  (not a) and (not b)

# Practical example: "not logged in AND not guest"
if not (logged_in or guest):
    redirect_to_login()

# Equivalent to:
if not logged_in and not guest:
    redirect_to_login()

Exercises

Basic

1. Construct truth tables for:

   • p → (q ∨ r)
   • (p ∧ q) ↔ (q ∧ p)
   • ¬(p → q)

2. Determine if these are propositions:

   • "The sky is blue"
   • "x² = 4"
   • "Is it raining?"
   • "7 + 5 = 12"

Intermediate

3. Prove or disprove: (p → q) ≡ (¬p ∨ q)

4. Using proof by contradiction, prove there is no largest prime number.

5. Use mathematical induction to prove: 1² + 2² + ... + n² = n(n+1)(2n+1)/6

Advanced

6. Prove: If 3n + 2 is odd, then n is odd.

7. Write the negation of: ∀x ∃y (x + y = 0)

8. A logic puzzle: You meet two people. One always tells the truth, one always lies. You can ask one yes/no question to determine who is who. What question do you ask?

Summary

• Propositions are statements with definite truth values
• Logical connectives (∧, ∨, ¬, →, ↔) combine propositions
• Truth tables enumerate all possible truth values
• Logical equivalences allow simplification
• Quantifiers (∀, ∃) extend logic to predicates
• Proof techniques: direct, contrapositive, contradiction, cases, induction

Next Reading

Set Theory →