OPTIMIZED LOGIC STUDY GUIDE (CH 2.2-3.4)

LOGIC STUDY GUIDE (CH 2.2-3.4)

CONDITIONAL STATEMENTS (CH 2.2)

Truth Values and Forms:

• p→q (Conditional): False ONLY when p=true and q=false

  • Truth table: T→T=T, T→F=F, F→T=T, F→F=T

  • Vacuously true: When hypothesis p is false

  • Equivalent to: ~p∨q ("not p or q")

  • Negation: ~(p→q) ≡ p∧~q ("p and not q")

• Related Statements:

  • Contrapositive: ~q→~p (EQUIVALENT to original)

  • Converse: q→p (NOT equivalent)

  • Inverse: ~p→~q (NOT equivalent, but equivalent to converse)

• Special Forms:

  • "p only if q" means p→q (q is necessary for p)

  • p↔q (Biconditional): (p→q)∧(q→p) ("if and only if")

  • Necessary condition: "q necessary for p" means p→q

    • If p happens, q must happen; can't have p without q

    • Example: "Oxygen is necessary for fire" means "If fire, then oxygen"

  • Sufficient condition: "q sufficient for p" means q→p

    • If q happens, p must follow; q guarantees p

    • Example: "100% on final is sufficient for passing" means "If 100%, then pass"

VALID ARGUMENTS (CH 2.3)

Valid Argument Forms:

• Modus Ponens: p→q, p, therefore q

• Modus Tollens: p→q, ~q, therefore ~p

• Transitivity: p→q, q→r, therefore p→r

• Elimination: p∨q, ~p, therefore q

• Division into Cases: p∨q, p→r, q→r, therefore r

• Contradiction Rule: ~p→contradiction, therefore p

Invalid Argument Forms (Fallacies):

• Converse Error: p→q, q, therefore p (INVALID!)

  • Example: "If it rains, streets get wet. Streets are wet. Therefore, it's raining."

• Inverse Error: p→q, ~p, therefore ~q (INVALID!)

  • Example: "If it rains, streets get wet. It's not raining. Therefore, streets aren't wet."

PREDICATES & QUANTIFIERS (CH 3.1-3.2)

Basic Concepts:

• Predicate P(x): Statement with variable(s)

  • Truth set: Values making P(x) true

  • Example: P(x) = "x is prime" is true for x=2, false for x=4

• Quantifiers:

  • Universal ∀x: "For all x" (must be true for EVERY value)

  • Existential ∃x: "There exists at least one x" (must be true for AT LEAST ONE value)

• Universal Statement Forms:

  • ∀x, P(x) - "All x have property P"

  • ∀x, if P(x) then Q(x) - "All things with property P also have property Q"

  • ∀x∈D, Q(x) ≡ ∀x, (x∈D→Q(x)) - Two equivalent ways to restrict domain

• Negating Quantified Statements:

  • ~(∀x, P(x)) ≡ ∃x, ~P(x) - "Not all" equals "Some are not"

  • ~(∃x, P(x)) ≡ ∀x, ~P(x) - "None are" equals "All are not"

  • ~(∀x, P(x)→Q(x)) ≡ ∃x, P(x)∧~Q(x) - "Not all P are Q" equals "Some P are not Q"

MULTIPLE QUANTIFIERS (CH 3.3)

Order and Negation:

• Order Matters with Different Quantifiers:

  • ∀x, ∃y, P(x,y) ≠ ∃y, ∀x, P(x,y)

  • ∀x, ∃y: "For each x, we can find at least one y" (may be different y for each x)

  • ∃y, ∀x: "There is one y that works for all x" (same y works for every x)

• Order Doesn't Matter with Same Quantifiers:

  • ∀x, ∀y, P(x,y) ≡ ∀y, ∀x, P(x,y)

  • ∃x, ∃y, P(x,y) ≡ ∃y, ∃x, P(x,y)

• Negating Multiple Quantifiers:

  • ~(∀x, ∃y, P(x,y)) ≡ ∃x, ∀y, ~P(x,y)

  • ~(∃x, ∀y, P(x,y)) ≡ ∀x, ∃y, ~P(x,y)

QUANTIFIED ARGUMENTS (CH 3.4)

Key Inference Rules:

• Universal Instantiation:

  • If ∀x, P(x) is true, then P(a) is true for any specific a

  • Example: "All humans are mortal. Socrates is human." → "Socrates is mortal."

• Universal Modus Ponens:

  • ∀x, P(x)→Q(x); P(a); therefore Q(a)

  • Example: "All even numbers are divisible by 2. 8 is even. Therefore, 8 is divisible by 2."

• Universal Modus Tollens:

  • ∀x, P(x)→Q(x); ~Q(a); therefore ~P(a)

  • Example: "All dogs bark. This animal doesn't bark. Therefore, this animal isn't a dog."

• Testing Validity with Venn Diagrams:

  • "All A are B": A circle inside B circle

  • "No A are B": Non-overlapping circles

SYMBOLS & ORDER OF OPERATIONS

Symbols:

• →: Conditional (if-then)

• ↔: Biconditional (if and only if)

• ∧: Conjunction (and)

• ∨: Disjunction (or)

• ~: Negation (not)

• ∀: Universal quantifier (for all)

• ∃: Existential quantifier (there exists)

• ∈: Element of (belongs to set)

• ∴: Therefore (concludes argument)

Operation Order (Highest to Lowest):

1. Negation (~)

2. Conjunction (∧) and Disjunction (∨)

3. Conditional (→) and Biconditional (↔)