Chapter 2 notes

Conditional Statements

• Form: $p\rightarrow q$ = "If p, then q"

• Truth rule: Only false when $p$ = True and $q$ = False

• If $p$ is false, the statement is true by default (vacuously true)

Example:

• “If 0 = 1, then 1 = 2”

→ True (because 0 = 1 is false)

Order of Operations

• $\neg$ (NOT) first

• $\land$ (AND), $\lor$ (OR)

• $\rightarrow$ (if–then) last

Logical Equivalences

• $p\rightarrow q\equiv\neg p\lor q$

  ("If p then q" = "Not p or q")

Example:

• “Either you get to work on time or you are fired.”

→ If you do not get to work on time, then you are fired.

Negation of a Conditional

• Negation of $p\rightarrow q$:

  $p\land\neg q$

• Reads: “p is true AND q is false”

Examples:

• If it is raining, then the ground is wet.

→ Negation: It is raining AND the ground is not wet.

• If I study, then I pass.

→ Negation: I study AND I do not pass.

Contrapositive

• Contrapositive: $\neg q\rightarrow\neg p$

• Logically equivalent to original conditional

Examples:

• If Howard can swim across the lake, then he can swim to the island.

→ Contrapositive: If Howard cannot swim to the island, then he cannot swim across the lake.

• If today is Easter, then tomorrow is Monday.

→ Contrapositive: If tomorrow is not Monday, then today is not Easter.

Converse and Inverse

• Converse: $q\rightarrow p$

• Inverse: $\neg p\rightarrow\neg q$

• Not equivalent to original (but converse & inverse are equivalent to each other)

Examples:

• If today is Easter, then tomorrow is Monday.

  • Converse: If tomorrow is Monday, then today is Easter.

  • Inverse: If today is not Easter, then tomorrow is not Monday.

“Only If”

• “p only if q” means $p\rightarrow q$

• Equivalent contrapositive: $\neg q\rightarrow\neg p$

Example:

• John will break the record only if he runs under 4 minutes.

  • Version 1: If John does not run under 4 minutes, then he will not break the record.

  • Version 2: If John breaks the record, then he ran under 4 minutes.

Biconditional ($\leftrightarrow$)

• $p\leftrightarrow q$ = “p if and only if q”

• Equivalent to: $(p\rightarrow q)\land(q\rightarrow p)$

Example:

• “This program is correct if and only if it produces correct answers for all inputs.”

→ If program is correct, then it produces correct answers.

→ If it produces correct answers, then it is correct.

Necessary & Sufficient Conditions

• Sufficient condition (If A then B):

  A guarantees B

  • Example: Pia born on U.S. soil

→ She is a U.S. citizen

<!-- -->

• Necessary condition (If not B then not A):

  B must be true for A to be true

  • Example: Being 35 is necessary to be U.S. president

    • If not 35, then not president

Quick Flashcard Rules:

1. Conditional false only when p = T, q = F

2. Rewrite conditionals: $p\rightarrow q\equiv\neg p\lor q$

3. Negation: $p\land\neg q$

4. Contrapositive = always equivalent

5. Converse/Inverse = equivalent to each other, not original

6. Biconditional = both directions true

7. Sufficient = If A then B

8. Necessary = If not B then not A