Conditional Statement: An "if-then" statement of the form "If p, then q" (p → q). Converse: q → p; Inverse: ¬p → ¬q; Contrapositive: ¬q → ¬p.
- Identify the hypothesis (p) and conclusion (q)
- Form the converse by switching p and q
- Form the inverse by negating both p and q
- Form the contrapositive by negating both and switching
- Determine truth values using logical principles
Hypothesis (p): A number is divisible by 6
Conclusion (q): It is divisible by 2 and 3
Original statement: p → q
Converse: If a number is divisible by 2 and 3, then it is divisible by 6
Symbolically: q → p
Truth value: TRUE (If n is divisible by both 2 and 3, then n is divisible by lcm(2,3)=6)
Inverse: If a number is not divisible by 6, then it is not divisible by 2 and 3
Symbolically: ¬p → ¬q
Truth value: FALSE (Counterexample: 10 is not divisible by 6, but is divisible by 2)
Contrapositive: If a number is not divisible by 2 and 3, then it is not divisible by 6
Symbolically: ¬q → ¬p
Truth value: TRUE (Logically equivalent to original statement)
Original ↔ Contrapositive: Logically equivalent
Converse ↔ Inverse: Logically equivalent
Original and Converse: Not necessarily equivalent
Original: True; Converse: True; Inverse: False; Contrapositive: True
• Conditional Logic: p → q is equivalent to ¬q → ¬p
• Converse vs Original: Not logically equivalent
• Counterexamples: Disprove universal statements
Proof by Contradiction: A method of proof where we assume the opposite of what we want to prove and show that this leads to a logical contradiction.
Assume √2 is rational, meaning √2 = a/b where a and b are integers with no common factors (gcd(a,b) = 1) and b ≠ 0.
(√2)² = (a/b)²
2 = a²/b²
2b² = a²
Since a² = 2b², a² is even
If a² is even, then a must be even (since odd² = odd)
So a = 2k for some integer k
a² = (2k)² = 4k²
From 2b² = a²: 2b² = 4k²
Therefore: b² = 2k²
Since b² = 2k², b² is even
Therefore b is even
But if both a and b are even, then gcd(a,b) ≥ 2
This contradicts our assumption that gcd(a,b) = 1
Since assuming √2 is rational leads to a contradiction, √2 must be irrational
Proof by contradiction is effective for proving non-existence because:
• It allows us to assume existence and derive impossibility
• It creates a logical framework to explore consequences
• It leverages the principle that contradictory premises lead to absurd conclusions
√2 is irrational. Proof by contradiction is effective because assuming the opposite leads to a logical impossibility, confirming the original statement.
• Proof by Contradiction: Assume ¬P, derive contradiction, conclude P
• Even/Odd Properties: Even² = even, Odd² = odd
• Rational Numbers: Can be expressed as a/b in lowest terms
Logical Equivalence: Two statements are logically equivalent if they have the same truth values under all possible interpretations.
Let p = "It rains"
Let q = "The ground gets wet"
Statement 1: p → q (If it rains, then the ground gets wet)
Statement 2: ¬p ∨ q (Either it doesn't rain or the ground gets wet)
| p (rains) | q (wet) | ¬p | p → q | ¬p ∨ q |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Columns for (p → q) and (¬p ∨ q) are identical in all rows
Therefore: p → q ≡ ¬p ∨ q
The equivalence p → q ≡ ¬p ∨ q is based on the fact that:
A conditional statement is false only when the antecedent is true and the consequent is false
In all other cases, the conditional is true
This matches the disjunction ¬p ∨ q: true when p is false OR q is true
"If it rains, then the ground gets wet" is equivalent to saying "Either it doesn't rain or the ground gets wet"
Both statements are false only when it rains but the ground doesn't get wet
This equivalence allows us to convert conditional statements to disjunctions
Useful in formal logic, computer science, and mathematical proofs
The statements are logically equivalent. The principle is that a conditional statement is equivalent to the disjunction of the negation of the antecedent with the consequent.
• Conditional Equivalence: p → q ≡ ¬p ∨ q
• Truth Tables: Systematic method for proving logical equivalence
• Logical Implication: Only false when true → false
Proposition: A declarative sentence that is either true or false, but not both.
Logical Connective: Words or symbols that connect propositions (and, or, not, if-then, if and only if).
Valid Argument: An argument where if the premises are true, the conclusion must be true.
Sound Argument: A valid argument with true premises.
- Identify Propositions: Determine the basic statements
- Recognize Connectives: Identify logical operators
- Form Structure: Express in symbolic form
- Apply Rules: Use logical equivalences and inference rules
- Derive Conclusion: Reach logical conclusion
- Verify Validity: Check reasoning process
¬(p ∨ q) ≡ ¬p ∧ ¬q
p → q ≡ ¬q → ¬p
• Modus Ponens: If p → q and p, then q
• Modus Tollens: If p → q and ¬q, then ¬p
• Law of Detachment: Valid inference rule for conditionals
• Principle of Contradiction: A statement cannot be both true and false
Deductive Reasoning: A logical process where conclusions are drawn from general principles or premises. If premises are true, the conclusion must be true.
Let S(x) = "x is a square"
Let R(x) = "x is a rectangle"
Let F(x) = "x has four sides"
Premise 1: ∀x(S(x) → R(x)) [All squares are rectangles]
Premise 2: ∀x(R(x) → F(x)) [All rectangles have four sides]
Premise 3: S(X) [Figure X is a square]
From Premise 1 and S(X): S(X) → R(X)
Since S(X) is true and S(X) → R(X), by Modus Ponens: R(X) is true
Conclusion: Figure X is a rectangle
From Premise 2: R(X) → F(X)
Since R(X) is true and R(X) → F(X), by Modus Ponens: F(X) is true
Conclusion: Figure X has four sides
From S(x) → R(x) and R(x) → F(x), we can deduce: S(x) → F(x)
This means: All squares have four sides
Since S(X) is true, F(X) must be true
The argument follows valid logical forms:
Universal Instantiation + Modus Ponens + Hypothetical Syllogism
If all premises are true, the conclusion must be true
Yes, Figure X has four sides.
Justification: Figure X is a square → Figure X is a rectangle → Figure X has four sides
Yes, Figure X has four sides. This follows deductively from the premises using valid logical rules: Universal Instantiation, Modus Ponens, and Hypothetical Syllogism.
• Universal Instantiation: From ∀x P(x), infer P(c) for any c
• Modus Ponens: From p → q and p, infer q
• Hypothetical Syllogism: From p → q and q → r, infer p → r
Mathematical Induction: A proof technique for statements about all positive integers, consisting of a base case and an inductive step.
P(n): 1 + 2 + 3 + ... + n = n(n+1)/2 for all positive integers n
Left side: 1
Right side: 1(1+1)/2 = 1(2)/2 = 1
Since both sides equal 1, P(1) is true
Assume P(k) is true for some arbitrary positive integer k:
1 + 2 + 3 + ... + k = k(k+1)/2
We must show that P(k+1) is true:
1 + 2 + 3 + ... + k + (k+1) = (k+1)((k+1)+1)/2
Starting with the left side of P(k+1):
1 + 2 + 3 + ... + k + (k+1) = [1 + 2 + 3 + ... + k] + (k+1)
By inductive hypothesis: = k(k+1)/2 + (k+1)
k(k+1)/2 + (k+1) = k(k+1)/2 + 2(k+1)/2
= [k(k+1) + 2(k+1)]/2
= [(k+1)(k + 2)]/2
= (k+1)(k+2)/2
We've shown that if P(k) is true, then P(k+1) is true
Since P(1) is true and P(k) → P(k+1), by mathematical induction,
P(n) is true for all positive integers n
Mathematical induction is valid because:
• The base case establishes the statement for n=1
• The inductive step shows that truth propagates from any n=k to n=k+1
• Together, they establish truth for n=1, 2, 3, ..., covering all positive integers
The formula 1 + 2 + 3 + ... + n = n(n+1)/2 is proven true for all positive integers n by mathematical induction. This method works because it establishes a domino effect of truth across all positive integers.
• Mathematical Induction: Base case + inductive step proves universal statement
• Algebraic Manipulation: Factoring and simplification techniques
• Logical Structure: If P(1) and P(k)→P(k+1), then P(n) for all n≥1
Logical Reasoning: The process of using a rational, systematic series of steps based on sound mathematical procedures and given statements to arrive at a conclusion.
Deductive Reasoning: Drawing specific conclusions from general principles; if premises are true, conclusion must be true.
Inductive Reasoning: Drawing general conclusions from specific observations; conclusion is probable but not certain.
Mathematical Induction: A proof technique establishing truth for all positive integers through base case and inductive step.
- Proposition Identification: Recognize and symbolize the basic statements
- Structure Analysis: Determine the logical form and relationships
- Rule Selection: Choose appropriate logical rules and equivalences
- Argument Construction: Build a step-by-step logical progression
- Validity Verification: Check each step follows logically
- Conclusion Drawing: Reach the final logical result
- Soundness Check: Ensure premises are true for practical application
• Law of Identity: A = A; every statement is identical to itself
• Law of Non-Contradiction: A and ¬A cannot both be true
• Law of Excluded Middle: Either A or ¬A must be true
• Transitivity: If A implies B and B implies C, then A implies C
Deductive reasoning: Draws specific conclusions from general principles
Inductive reasoning: Derives general principles from specific instances
Proof by contradiction: Assumes negation to reach contradiction
Mathematical induction: Proves statements for all positive integers
Analysis: This chart illustrates the applicability and certainty of different logical reasoning approaches.
- Deductive reasoning provides certainty when premises are true
- Inductive reasoning offers probability based on evidence
- Proof by contradiction is effective for negative claims
- Mathematical induction handles infinite sets systematically