Elementary Logic: Kinds of Reasoning, Logical Statements, and Proof Techniques

Kinds of Reasoning

• Inductive Reasoning

  • Definition: Inductive reasoning is the process of reaching a general conclusion by examining specific examples, patterns, or observations. The conclusion reached through this method is referred to as a conjecture.

  • Nature of Conclusion: A conjecture may or may not be true; it is based on evidence seen so far. It moves from the specific to the general.

  • Example: Observing the sequence $2, 4, 6, 8, \text{...}$ and concluding that the next term is $10$ because the previous terms followed the pattern of adding $2$.

  • Counterexamples: To prove a conjecture is false, one only needs to find a single case where it does not hold, known as a counterexample.

• Deductive Reasoning

  • Definition: Deductive reasoning is the process of reaching a specific, logical conclusion by applying general assumptions, procedures, principles, or rules. It moves from the general to the specific.

  • Nature of Conclusion: If the premises and the logic used are true and valid, the conclusion is guaranteed to be true.

  • Example: All mammals have lungs (general premise). A dolphin is a mammal (specific case). Therefore, a dolphin has lungs (deductive conclusion).

Conditional, Converse, Inverse, Contrapositive, and Biconditional Statements

• Conditional Statements

  • Form: An "If-then" statement, symbolically represented as $P \rightarrow Q$.

  • Components:

    • Antecedent (Hypothesis): The part following "if" (represented by $P$).

    • Consequent (Conclusion): The part following "then" (represented by $Q$).

  • Truth Value: A conditional statement is only considered false when the antecedent ($P$) is true and the consequent ($Q$) is false.

• Converse Statement

  • Form: Formed by switching the hypothesis and the conclusion of the original conditional statement.

  • Symbolic Form: $Q \rightarrow P$

• Inverse Statement

  • Form: Formed by negating both the hypothesis and the conclusion of the original conditional statement.

  • Symbolic Form: $\neg P \rightarrow \neg Q$

• Contrapositive Statement

  • Form: Formed by both switching and negating the hypothesis and the conclusion.

  • Symbolic Form: $\neg Q \rightarrow \neg P$

  • Logical Equivalence: The contrapositive is always logically equivalent to the original conditional statement. If $P \rightarrow Q$ is true, then $\neg Q \rightarrow \neg P$ is also true.

• Biconditional Statements

  • Form: An "if and only if" statement, symbolically represented as $P \rightleftharpoons Q$ or $P \text{ iff } Q$.

  • Definition: It represents the conjunction of a conditional and its converse: $(P \rightarrow Q) \text{ and } (Q \rightarrow P)$.

  • Truth Value: A biconditional is true only when both $P$ and $Q$ have the same truth value (both true or both false).

Mathematical Induction and Indirect Proof

• Mathematical Induction

  • Purpose: A method of mathematical proof typically used to establish that a given statement is true for all natural numbers ($n = 1, 2, 3, \text{...}$).

  • The Principle of Mathematical Induction (PMI): Consists of two essential steps:

    1. Basis Step (Base Case): Prove that the statement $P(n)$ is true for the first natural number, usually $n = 1$. Showing $P(1)$ is true.

    2. Inductive Step: Prove that if the statement is true for some arbitrary integer $k$, then it must also be true for the next integer $k+1$.

       • Inductive Hypothesis: Assume $P(k)$ is true for some $k$.

       • Goal: Show that $P(k) \rightarrow P(k+1)$.

  • Analogy: Often compared to falling dominoes; if the first domino falls (Base Case), and every domino that falls causes the next one to fall (Inductive Step), then all dominoes will eventually fall.

• Indirect Proof (Proof by Contradiction)

  • Logic: Based on the law of non-contradiction, which states that a proposition cannot be both true and false at the same time ($\neg (R \text{ and } \neg R)$).

  • Procedure:

    1. Assume the negation of the conclusion you are trying to prove. If you want to prove $P$, assume $\neg P$ (not $P$).

    2. Use logical reasoning and rules of inference to show that this assumption leads to a contradiction (e.g., $1 = 0$ or a statement that contradicts a known axiom/given information).

    3. Since the assumption ($\neg P$) leads to an impossible result, the assumption must be false. Therefore, the original statement ($P$) must be true.