Introduction to Logic

What is Logic?

Logic: Study of reasoning and valid arguments

Mathematical logic: Using precise rules to determine truth

Applications:

• Computer programming
• Mathematics proofs
• Philosophy
• Circuit design
• Artificial intelligence

Propositions

Proposition: Statement that is either true or false (not both)

Examples of propositions:

• "2 + 2 = 4" (True)
• "5 > 10" (False)
• "Today is Monday" (True or False, depends on day)

NOT propositions:

• "What time is it?" (question)
• "Do your homework!" (command)
• "x + 3 = 7" (depends on x, not definite)

Notation: Use letters p, q, r for propositions

Truth Values

Every proposition has truth value:

• T (True) or 1
• F (False) or 0

Example: Assign Truth Values

p: "10 is even" → T

q: "5 + 3 = 7" → F

r: "A square has 4 sides" → T

Logical Operators

Connect propositions to form compound statements

Basic operators:

1. NOT (negation): ¬
2. AND (conjunction): ∧
3. OR (disjunction): ∨
4. IF-THEN (conditional): →
5. IF AND ONLY IF (biconditional): ↔

NOT (Negation)

Symbol: ¬p or ~p

Meaning: Opposite of p

Truth table:

p    ¬p
T    F
F    T

Example: Negation

p: "It is raining"

¬p: "It is NOT raining"

If p is true, ¬p is false If p is false, ¬p is true

AND (Conjunction)

Symbol: p ∧ q

Meaning: Both p AND q are true

Truth table:

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

Only true when BOTH are true

Example: AND

p: "I have $10" q: "Store is open" p ∧ q: "I have $10 AND store is open"

Only true if I have money AND store is open

OR (Disjunction)

Symbol: p ∨ q

Meaning: At least one of p OR q is true

Truth table:

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

True when AT LEAST ONE is true

Note: "Inclusive OR" (both can be true)

Example: OR

p: "I will walk to school" q: "I will bike to school" p ∨ q: "I will walk OR bike to school"

True if I do either or both

Exclusive OR (XOR)

Symbol: p ⊕ q

Meaning: Exactly one is true (not both)

Truth table:

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

Example: XOR

p: "Soup" q: "Salad" p ⊕ q: "Soup XOR Salad" (one or the other, not both)

Conditional (If-Then)

Symbol: p → q

Read: "If p, then q"

Truth table:

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

Only false when p is true and q is false

Key insight: False premise (p = F) makes statement vacuously true

Example: Conditional

p: "It rains" q: "I bring umbrella" p → q: "If it rains, then I bring umbrella"

False only if: It rains but I don't bring umbrella

Example: Vacuous Truth

Statement: "If 2 + 2 = 5, then I am president"

p: "2 + 2 = 5" (False) q: "I am president" (likely False)

p → q: True! (Because p is false)

Vacuously true: False premise makes conditional true regardless of q

Converse, Inverse, Contrapositive

Original: p → q

Converse: q → p (switch p and q)

Inverse: ¬p → ¬q (negate both)

Contrapositive: ¬q → ¬p (switch and negate both)

Important: Original and contrapositive are logically equivalent

Example: Related Conditionals

Original: "If it rains, then ground is wet"

• p → q

Converse: "If ground is wet, then it rains"

• q → p (NOT necessarily true! Could be sprinkler)

Inverse: "If it doesn't rain, then ground isn't wet"

• ¬p → ¬q (NOT necessarily true!)

Contrapositive: "If ground isn't wet, then it didn't rain"

• ¬q → ¬p (TRUE! Logically equivalent to original)

Biconditional (If and Only If)

Symbol: p ↔ q

Read: "p if and only if q" or "p iff q"

Meaning: p and q have same truth value

Truth table:

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

Equivalent to: (p → q) ∧ (q → p)

Example: Biconditional

p: "Triangle is equilateral" q: "Triangle has three equal sides" p ↔ q: True (definitions are equivalent)

p: "x = 2" q: "x² = 4" p ↔ q: False (x = -2 also gives x² = 4)

Compound Statements

Combine multiple operators

Order of operations:

1. Negation (¬)
2. AND (∧)
3. OR (∨)
4. Conditional (→)
5. Biconditional (↔)

Use parentheses for clarity

Example: Compound Statement

p ∧ (q ∨ r)

Truth table:

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

Tautologies and Contradictions

Tautology: Always true, regardless of truth values

Contradiction: Always false, regardless of truth values

Contingency: Sometimes true, sometimes false

Example: Tautology

p ∨ ¬p (Law of Excluded Middle)

p   ¬p   p∨¬p
T   F     T
F   T     T

Always true (either p or not p must be true)

Example: Contradiction

p ∧ ¬p

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

Always false (p and not p cannot both be true)

Logical Equivalence

Two statements logically equivalent if same truth values always

Notation: p ≡ q or 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)

Example: De Morgan's Law

p: "I have homework" q: "I have a test"

¬(p ∧ q): "It's not true that I have homework AND a test"

Equivalent: "I don't have homework OR I don't have a test"

• ¬p ∨ ¬q

Arguments and Validity

Argument: Premises leading to conclusion

Valid argument: If premises true, conclusion must be true

Sound argument: Valid AND premises actually true

Example: Modus Ponens (Valid)

Premise 1: p → q Premise 2: p Conclusion: Therefore q

Example:

• "If it rains, ground is wet" (p → q)
• "It is raining" (p)
• "Therefore, ground is wet" (q) ✓

Example: Affirming Consequent (INVALID)

Premise 1: p → q Premise 2: q Conclusion: Therefore p (WRONG!)

Example:

• "If it rains, ground is wet" (p → q)
• "Ground is wet" (q)
• "Therefore, it rained" (p) ✗ (Could be sprinkler!)

Applications in Programming

Boolean logic: Used in programming conditions

if (p AND q): Execute only if both true

if (p OR q): Execute if at least one true

if (NOT p): Execute if p is false

Example: Login Check

username_correct = True
password_correct = False

can_login = username_correct AND password_correct
→ False (need both)

Practice