Introduction to Logic and Proofs

Introduction to Logic and Proofs

Logic is the foundation of reasoning, and in discrete mathematics, it's essential for forming valid arguments and solving problems systematically. Proofs are the methods we use to verify the truth of statements or propositions.

1. Basic Logic Concepts

• Propositions: A proposition is a statement that is either true or false, but not both. Examples include:

  • "5 is an odd number" (True)
  • "2 + 2 = 5" (False)

• Logical Connectives: These are used to combine propositions into more complex statements. The most common logical connectives are:

  • Negation (¬): The negation of a proposition $p$ is written as $\neg p$ and means "not $p$". If $p$ is true, $\neg p$ is false, and vice versa.
  • Conjunction (∧): The conjunction of two propositions $p$ and $q$, written as $p \land q$, is true only when both $p$ and $q$ are true.
  • Disjunction (∨): The disjunction of two propositions $p$ and $q$, written as $p \lor q$, is true when at least one of $p$ or $q$ is true.
  • Implication (→): The implication $p \rightarrow q$ means "if $p$, then $q$". It is false only when $p$ is true and $q$ is false; otherwise, it's true.
  • Biconditional (↔): The biconditional $p \leftrightarrow q$ means "$p$ if and only if $q$". It is true when $p$ and $q$ are both true or both false.

• Truth Tables: A truth table is a systematic way of showing all possible truth values of a logical expression based on the truth values of its components. Here's an example for conjunction (AND):

This shows that $p \land q$ is only true when both $p$ and $q$ are true.

2. Propositional Equivalences

Two logical expressions are equivalent if they have the same truth table. Some common equivalences include:

• De Morgan’s Laws:
  • $\neg (p \land q) \equiv (\neg p \lor \neg q)$
  • $\neg (p \lor q) \equiv (\neg p \land \neg q)$
• Implication equivalence:
  • $p \rightarrow q \equiv \neg p \lor q$
• Double Negation:
  • $\neg (\neg p) \equiv p$

These equivalences are useful for simplifying logical expressions and making proofs easier.

3. Quantifiers in Logic

• Universal Quantifier (∀): This means "for all". For example, $\forall x \, P(x)$ means "P(x) is true for all x".
• Existential Quantifier (∃): This means "there exists". For example, $\exists x \, P(x)$ means "there exists an x such that P(x) is true".

Quantifiers allow us to make statements about entire sets of objects.

4. Types of Proofs

In mathematics, we use various methods to prove statements:

• Direct Proof: A direct proof starts from known facts or axioms and uses logical steps to arrive at the conclusion.

  • Example: To prove $2 + 2 = 4$, we simply use basic arithmetic and properties of numbers.

• Proof by Contradiction (Indirect Proof): In a proof by contradiction, we assume the opposite of what we want to prove and show that this assumption leads to a contradiction.

  • Example: To prove that $\sqrt{2}$ is irrational, assume the opposite (that $\sqrt{2}$ is rational), and show that this leads to a contradiction.

• Proof by Contrapositive: The contrapositive of an implication $p \rightarrow q$ is $\neg q \rightarrow \neg p$, and a proof by contrapositive involves proving this equivalent statement.

  • Example: To prove $p \rightarrow q$, you prove $\neg q \rightarrow \neg p$.

• Proof by Induction: This is used to prove statements about integers or other countable sets. There are two main steps:

  1. Base case: Show the statement is true for the first element (usually $n = 1$).
  2. Inductive step: Assume the statement is true for some $k$, and then prove it is true for $k + 1$.

• Proof by Counterexample: To disprove a statement, you can provide a counterexample, which is a specific case where the statement doesn't hold.

5. Logical Fallacies

A fallacy is a flaw in reasoning that undermines the validity of an argument. Some common logical fallacies are:

• Affirming the consequent: Assuming that $p \rightarrow q$ and $q$ are true, so $p$ must be true. (Incorrect reasoning)
• Denying the antecedent: Assuming that $p \rightarrow q$ and $\neg p$ are true, so $\neg q$ must be true. (Incorrect reasoning)
• Circular reasoning: The argument assumes the conclusion is true in the premises.

6. Formal Logic and Proof Systems

In discrete mathematics, logic is formalized into systems with rules for manipulating symbols. These systems are used to ensure rigorous reasoning. Examples include:

• Propositional Logic: Deals with propositions and their connectives (AND, OR, NOT, etc.).
• Predicate Logic: Extends propositional logic to include quantifiers and predicates (statements about objects).
• Formal Systems: These include axiomatic systems like Zermelo-Fraenkel set theory, which form the basis of mathematical logic.

Summary

• Logic involves understanding propositions, logical connectives, and truth values.
• Proofs are structured arguments used to verify statements, with several types like direct proof, contradiction, contrapositive, induction, and counterexamples.
• Quantifiers (universal and existential) allow us to reason about collections of objects.
• Logical equivalences and fallacies help refine arguments and identify errors in reasoning.

This foundational knowledge of logic and proofs is crucial for solving problems in discrete mathematics, computer science, and beyond!