Discreet Math - Chapter 2.2 - " Conditional Statements " NOTES

Foundations of Conditional Statements

• Epigraph Context: As Jean Piaget stated in $1972$, "… hypothetical reasoning implies the subordination of the real to the realm of the possible …"

• Logical Inference and Deduction: When making a logical inference or deduction, reasoning moves from a hypothesis to a conclusion with the goal of stating: "If such and such is known, then something or other must be the case."

• Definition of Conditional Statement:

  • Let $p$ and $q$ be statement variables.

  • A sentence of the form "If $p$ then $q$" or "$p$ implies $q$" is called a conditional statement and is denoted symbolically by $p \rightarrow q$.

  • The statement variable $p$ is called the hypothesis (or antecedent).

  • The statement variable $q$ is called the conclusion (or consequent).

  • The truth of statement $q$ is conditioned on the truth of statement $p$.

• Connective Symbol:

  • The arrow symbol $\rightarrow$ functions as a logical connective (similar to $\land$ or $\lor$) used to join two statements into a single compound statement.

  • To define $p \rightarrow q$ formally, truth values must be specified for all truth combinations of $p$ and $q$.

• Visual Structure of Conditional Statements:     

  

  • Example statement: "If $4,686$ is divisible by $6$, then $4,686$ is divisible by $3$".

  • Hypothesis ($p$): "$4,686$ is divisible by $6$".

  • Conclusion ($q$): "$4,686$ is divisible by $3$".

Truth Values and Truth Tables of Conditional Statements

• Everyday Intuitive Rationale (Job Offer Scenario):

  • Consider the promise: "If you show up for work Monday morning, then you will get the job."

  • A promise is broken (the conditional statement is false) only if you show up for work Monday morning ($p$ is True) and you do not get the job ($q$ is False).

  • If you do not show up for work Monday morning ($p$ is False), the promise made no commitment about what would happen. Therefore, you cannot claim the promise was false regardless of whether you get the job or not.

• Formal Truth Definition:

  • A conditional statement $p \rightarrow q$ is false when $p$ is true and $q$ is false; otherwise, it is true.

• Truth Table for $p \rightarrow q$:

  • Row 1: $p = \text{T}$, $q = \text{T} \implies p \rightarrow q = \text{T}$

  • Row 2: $p = \text{T}$, $q = \text{F} \implies p \rightarrow q = \text{F}$

  • Row 3: $p = \text{F}$, $q = \text{T} \implies p \rightarrow q = \text{T}$

  • Row 4: $p = \text{F}$, $q = \text{F} \implies p \rightarrow q = \text{T}$

• Vacuous Truth (True by Default):

  • A conditional statement that is true simply because its hypothesis is false is called vacuously true or true by default.

  • When the "if" part of an if-then statement is false, the statement as a whole is automatically true, regardless of whether the conclusion is true or false.

  • Example 2.2.1 (A Conditional Statement with a False Hypothesis):

    • Statement: "If $0 = 1$ then $1 = 2$".

    • Analysis: Since the hypothesis $0 = 1$ is false, the statement as a whole is true.

    • Mathematical Context: If one hypothesizes that $0 = 1$, adding $1$ to both sides allows one to logically deduce that $1 = 2$.

• Terminology Note on "Implies":

  • The philosopher Willard Van Orman Quine advised against using the verbal phrase "$p$ implies $q$" to mean $p \rightarrow q$ because the word implies suggests that $q$ can be logically deduced from $p$, which is not always required in pure truth-functional logic.

  • Despite this warning, the phrase remains widely used as a convenient shorthand for the $\rightarrow$ connective.

Order of Operations and Truth Tables for Complex Expressions

• Hierarchy of Operations:

  1. Negation ($\sim$): Performed first.

  2. Conjunction ($\land$) and Disjunction ($\lor$): Performed second. Parentheses are used if both are present.

  3. Conditional ($\rightarrow$) and Biconditional ($\leftrightarrow$): Performed last.

• Constructing Truth Tables for Compound Statements:

  • Example 2.2.2 (Truth Table for $p \lor \sim q \rightarrow \sim p$):

    • By the order of operations, $p \lor \sim q \rightarrow \sim p$ is equivalent to $(p \lor (\sim q)) \rightarrow (\sim p)$.

    • Step 1: Fill in all combinations of truth values for $p$ and $q$ ($4$ rows).

    • Step 2: Compute $\sim p$ and $\sim q$ using the definition of negation.

    • Step 3: Compute the hypothesis column $p \lor \sim q$ using the definition of disjunction ($\lor$).

    • Step 4: Compute the final column $(p \lor \sim q) \rightarrow \sim p$ using the definition of the conditional ($\rightarrow$).

    • Evaluation: The hypothesis $p \lor \sim q$ is true and the conclusion $\sim p$ is false in Row 1 ($\text{T}, \text{T}$) and Row 2 ($\text{T}, \text{F}$), giving $\text{F}$ in those rows and $\text{T}$ in Rows 3 and 4.     

      

Logical Equivalences Involving Conditional Statements

• Division into Cases:

  • Method Analysis: When analyzing three statements $p$, $q$, and $r$, if the truth of $r$ follows from $p$ ($p \rightarrow r$) and also follows from $q$ ($q \rightarrow r$), then regardless of whether $p$ or $q$ is true, $r$ must follow ($p \lor q \rightarrow r$).

  • Example 2.2.3 (Division into Cases: Showing That $p \lor q \rightarrow r \equiv (p \rightarrow r) \land (q \rightarrow r)$):

    • List all $8$ possible truth value combinations for $p$, $q$, and $r$

    • Compute $p \lor q$, $p \rightarrow r$, and $q \rightarrow r$.

    • Compute $p \lor q \rightarrow r$: It is false only in rows where $p \lor q$ is true and $r$ is false (Rows 2, 4, and 6).

    • Compute $(p \rightarrow r) \land (q \rightarrow r)$: It is false whenever either $p \rightarrow r$ or $q \rightarrow r$ is false (Rows 2, 4, and 6).

    • Since both expressions yield identical truth values across all $8$ rows, $p \lor q \rightarrow r \equiv (p \rightarrow r) \land (q \rightarrow r)$.     

      

• Representation of If-Then as Or:

  • Fundamental Equivalence: $p \rightarrow q \equiv \sim p \lor q$

  • Example 2.2.4 (Application of the Equivalence between $\sim p \lor q$ and $p \rightarrow q$):

    • Given statement: "Either you get to work on time or you are fired."

    • Let $\sim p$ = "You get to work on time."

    • Let $q$ = "You are fired."

    • The given statement has the form $\sim p \lor q$

    • The negation of $\sim p$ gives $p$ = "You do not get to work on time."

    • The equivalent if-then statement ($p \rightarrow q$) is: "If you do not get to work on time, then you are fired."

Negation of Conditional Statements

• Negation Rule:

  • By definition, $p \rightarrow q$ is false if and only if $p$ is true and $q$ is false.

  • Therefore, the negation of "if $p$ then $q$" is logically equivalent to "$p$ and not $q$".

  • Symbolic Form: $\sim(p \rightarrow q) \equiv p \land \sim q$

• Algebraic Derivation of the Negation:

  • Starting with $\sim(p \rightarrow q)$, substitute $p \rightarrow q \equiv \sim p \lor q$:         $\sim(p \rightarrow q) \equiv \sim(\sim p \lor q)$

  • Apply De Morgan's laws:         $\equiv \sim(\sim p) \land (\sim q)$

  • Apply the double negative law:         $\equiv p \land \sim q$     

    

• Critical Caution regarding Negations:

  • The negation of an if-then statement does not start with the word if.

  • Resist the temptation to write the negation of a conditional statement as another conditional statement.

• Examples of Negation (Example 2.2.5):

  • Statement a: "If my car is in the repair shop, then I cannot get to class."

    • Negation: "My car is in the repair shop and I can get to class."

  • Statement b: "If Sara lives in Athens, then she lives in Greece."

    • Negation: "Sara lives in Athens and she does not live in Greece."

    • Note: Sara might live in Athens, Georgia; Athens, Ohio; or Athens, Wisconsin.

Contrapositive, Converse, and Inverse Statements

• The Contrapositive:

  • Definition: The contrapositive of a conditional statement "If $p$ then $q$" is "If $\sim q$ then $\sim p$".

  • Symbolic Representation: The contrapositive of $p \rightarrow q$ is $\sim q \rightarrow \sim p$

  • Fundamental Law of Logic: A conditional statement is always logically equivalent to its contrapositive ($p \rightarrow q \equiv \sim q \rightarrow \sim p$).

  • Example 2.2.6 (Writing the Contrapositive):

    • Statement a: "If Howard can swim across the lake, then Howard can swim to the island."

      • Contrapositive: "If Howard cannot swim to the island, then Howard cannot swim across the lake."

    • Statement b: "If today is Easter, then tomorrow is Monday."

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

• The Converse and the Inverse:

  • Definitions for a conditional statement "If $p$ then $q$":

    1. Converse: "If $q$ then $p$" (Symbolically: $q \rightarrow p$).

    2. Inverse: "If $\sim p$ then $\sim q$" (Symbolically: $\sim p \rightarrow \sim q$).

  • Example 2.2.7 (Writing the Converse and Inverse):

    • Statement a: "If Howard can swim across the lake, then Howard can swim to the island."

      • Converse: "If Howard can swim to the island, then Howard can swim across the lake."

      • Inverse: "If Howard cannot swim across the lake, then Howard cannot swim to the island."

    • Statement b: "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."

      • Truth Evaluation: The original statement is true, but its converse and inverse are false on every Sunday of the year except Easter.

• Summary of Non-Equivalences:

  • A conditional statement and its converse are not logically equivalent ($p \rightarrow q \not\equiv q \rightarrow p$).

  • A conditional statement and its inverse are not logically equivalent ($p \rightarrow q \not\equiv \sim p \rightarrow \sim q$).

  • The converse and inverse of a conditional statement are logically equivalent to each other ($q \rightarrow p \equiv \sim p \rightarrow \sim q$), as the inverse is the contrapositive of the converse.

Only If and Biconditional Statements

• The Phrase "Only If":

  • Definition: "$p$ only if $q$" means that $p$ can take place only if $q$ takes place also. If $q$ does not take place, then $p$ cannot take place ($\sim q \rightarrow \sim p$).

  • If-Then Equivalent: By contrapositive equivalence, "$p$ only if $q$" is equivalent to "If $p$ then $q$" ($p \rightarrow q$).

  • Caution: "$p$ only if $q$" does not mean "$p$ if $q$" (which is $q \rightarrow p$).

  • Example 2.2.8 (Converting Only If to If-Then):

    • Statement: "John will break the world's record for the mile run only if he runs the mile in under four minutes."

    • Version 1 (Contrapositive): "If John does not run the mile in under four minutes, then he will not break the world's record."

    • Version 2 (If-Then): "If John breaks the world's record, then he will have run the mile in under four minutes."

• The Biconditional Statement:

  • Definition: Given statement variables $p$ and $q$, the biconditional of $p$ and $q$ is "$p$ if, and only if, $q$", denoted as $p \leftrightarrow q$

  • Abbreviation: The phrase if and only if is frequently abbreviated as iff.

  • Truth Value Rule: $p \leftrightarrow q$ is true if both $p$ and $q$ have the same truth values; it is false if $p$ and $q$ have opposite truth values.

  • Truth Table for $p \leftrightarrow q$:

    • $\text{T}, \text{T} \implies \text{T}$

    • $\text{T}, \text{F} \implies \text{F}$

    • $\text{F}, \text{T} \implies \text{F}$

    • $\text{F}, \text{F} \implies \text{T}$

• Logical Equivalence of Biconditional:

  • Saying "$p$ if, and only if, $q$" is logically equivalent to the conjunction of "$p$ if $q$" ($q \rightarrow p$) and "$p$ only if $q$" ($p \rightarrow q$).

  • Symbolic Equivalence: $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$

  • Example 2.2.9 (If and Only If):

    • Statement: "This computer program is correct if, and only if, it produces correct answers for all possible sets of input data."

    • Conjunction rewrite: "If this program is correct, then it produces the correct answers for all possible sets of input data; and if this program produces the correct answers for all possible sets of input data, then it is correct."

Necessary and Sufficient Conditions

• Sufficient Condition:

  • Definition: "$r$ is a sufficient condition for $s$" means "If $r$ then $s$" ($r \rightarrow s$).

  • Meaning: The occurrence of $r$ is sufficient to guarantee the occurrence of $s$

  • Example 2.2.11: "Pia's birth on U.S. soil is a sufficient condition for her to be a U.S. citizen" converts to "If Pia was born on U.S. soil, then she is a U.S. citizen."

• Necessary Condition:

  • Definition: "$r$ is a necessary condition for $s$" means "If not $r$ then not $s$" ($\sim r \rightarrow \sim s$).

  • Meaning: If $r$ does not occur, then $s$ cannot occur either.

  • Contrapositive Equivalent: By contrapositive equivalence ($\sim r \rightarrow \sim s \equiv s \rightarrow r$), "$r$ is a necessary condition for $s$" also means "If $s$ then $r$".

  • Example 2.2.12: "George's attaining age $35$ is a necessary condition for his being president of the United States."

    • Version 1: "If George has not attained the age of $35$, then he cannot be president of the United States."

    • Version 2: "If George can be president of the United States, then he has attained the age of $35$".

• Necessary and Sufficient Condition:

  • Definition: "$r$ is a necessary and sufficient condition for $s$" means "$r$ if, and only if, $s$" ($r \leftrightarrow s$).

• Example Analysis (Example 2.2.10):

  • Statement: "If John is eligible to vote, then he is at least $18$ years old."

  • Sufficient: John being eligible to vote is a sufficient condition for him being at least $18$ years old.

  • Necessary: John being at least $18$ years old is a necessary condition for him to be eligible to vote.

Practical and Philosophical Implications in Formal Logic

• Subject Matter Independence in Formal Logic:

  • In ordinary speech, conditional statements require a natural connection of content between hypothesis and conclusion.

  • In formal logic, no relationship of content is required between hypothesis and conclusion.

  • Example 1: "If computers are machines, then Babe Ruth was a baseball player" is valid and evaluated as true because both hypothesis and conclusion are true.

  • Example 2: "If $1 = 2$, then Mickey Mouse is president of the United States" is valid and evaluated as true because its hypothesis is false.

  • Practical Reason: Requiring content connections would require an impractical central arbiter to evaluate subjective relationships between clauses for every statement.

• Informal vs. Formal Interpretations of Conditionals:

  • In everyday conversation, simple conditionals are often loosely used when biconditionals are actually intended.

  • Example (Parental Promising): A parent saying "If you eat your dinner, you will get dessert" (emphasizing reward) or "You will get dessert only if you eat your dinner" (emphasizing punishment) almost always intends the full biconditional: "You will get dessert if, and only if, you eat your dinner."

  • Mathematical Precision Requirement: Because people routinely treat simple conditionals as biconditionals in conversation, they often mistakenly confuse conditional statements with their converses or inverses. In mathematics, science, and technical fields, statements must be strictly interpreted according to formal logic without ambiguous assumptions.