Mathematical Reasoning: Propositional and Predicate Logic

Mathematical Reasoning: Propositional and Predicate Logic

Mathematical reasoning is fundamental to discrete mathematics and involves logical thinking to prove statements. The two major types of logic used in mathematical reasoning are Propositional Logic and Predicate Logic.

1. Propositional Logic (Sentential Logic)

Propositional logic deals with statements that can be either true or false. These statements are referred to as propositions. In propositional logic, we combine simple propositions using logical connectives to form complex expressions.

Key Components:

• Proposition: A declarative statement that is either true or false, but not both. For example:

  • "The sky is blue" (True or False).
  • "2 + 2 = 5" (False).

• Logical Connectives: Used to combine or modify propositions. The common ones include:

  1. Negation (¬): Negates a proposition.

     • Example: If $p$ is "The sky is blue," then $\neg p$ means "The sky is not blue."

  2. Conjunction ( ∧ ): Represents logical AND.

     • Example: $p \land q$ is true only if both $p$ and $q$ are true.
     • "It is raining and the temperature is cold."

  3. Disjunction ( ∨ ): Represents logical OR.

     • Example: $p \lor q$ is true if at least one of $p$ or $q$ is true.
     • "It is raining or it is snowing."

  4. Implication ( → ): Represents logical IF-THEN.

     • Example: $p \to q$ means "If $p$ is true, then $q$ is true."
     • "If it rains, then I will carry an umbrella."
     • An implication is false only when the first part is true, and the second part is false.

  5. Biconditional ( ↔ ): Represents logical IF AND ONLY IF.

     • Example: $p \leftrightarrow q$ means $p$ and $q$ are either both true or both false.
     • "You will pass the exam if and only if you study."

Truth Tables:

Truth tables are used to systematically explore the truth values of logical expressions. For example, for the implication $p \to q$, the truth table looks like this:

Tautology and Contradiction:

• Tautology: A formula that is always true, regardless of the truth values of its components (e.g., $p \lor \neg p$).
• Contradiction: A formula that is always false (e.g., $p \land \neg p$).

2. Predicate Logic (First-Order Logic)

Predicate logic extends propositional logic by introducing quantifiers and predicates, which allows us to express more complex statements about variables and their relationships.

Key Components:

• Predicate: A function or relation that returns a true or false value. A predicate takes one or more arguments.

  • Example: $P(x)$ could represent the predicate "x is a prime number."
  • Example: $R(x, y)$ could represent "x is greater than y."

• Variables: A predicate can have variables that represent elements of a domain. For example, $P(x)$ means "x is prime" where $x$ is a variable from some domain (e.g., integers).

Quantifiers:

Quantifiers are used to express the extent to which a predicate applies to a set of values. There are two main types of quantifiers:

1. Universal Quantifier ( ∀ ): Expresses that a predicate is true for all elements in the domain.

   • Example: $\forall x \, P(x)$ means "For all $x$, $x$ is a prime number."

2. Existential Quantifier ( ∃ ): Expresses that there exists at least one element in the domain for which the predicate is true.

   • Example: $\exists x \, P(x)$ means "There exists an $x$ such that $x$ is a prime number."

Quantified Statements:

• Universal Statement: "All humans are mortal" can be written as $\forall x \, (H(x) \to M(x))$, where $H(x)$ means "x is human" and $M(x)$ means "x is mortal."
• Existential Statement: "There exists a person who is a teacher" can be written as $\exists x \, T(x)$, where $T(x)$ means "x is a teacher."

Predicates with Multiple Variables:

Predicates can also involve more than one variable. For example:

• $R(x, y)$ could represent the relationship "x is taller than y."
• $\forall x \forall y \, R(x, y)$ means "Everyone is taller than everyone else" (a universally quantified statement over two variables).

Negation of Quantifiers:

• Negating a universal quantifier: $\neg \forall x \, P(x)$ is equivalent to $\exists x \, \neg P(x)$ (there exists an $x$ such that $P(x)$ is false).
• Negating an existential quantifier: $\neg \exists x \, P(x)$ is equivalent to $\forall x \, \neg P(x)$ (for all $x$, $P(x)$ is false).

Logical Equivalences:

• Quantifier Distribution: The logical equivalences involving quantifiers are important. For example:
  • $\forall x \, \exists y \, P(x, y)$ means "For all $x$, there exists a $y$ such that $P(x, y)$ is true."
  • $\exists y \, \forall x \, P(x, y)$ means "There exists a $y$ such that for all $x$, $P(x, y)$ is true."

Comparison Between Propositional and Predicate Logic:

1. Propositional Logic:

   • Deals with simple true/false propositions.
   • Limited to handling whole propositions and their combinations.
   • Examples: "It is raining," "2 + 2 = 4."

2. Predicate Logic:

   • Deals with predicates that describe properties of objects and their relationships.
   • Uses variables and quantifiers to express more complex statements.
   • Examples: "All humans are mortal," "There exists a person who is a teacher."

Applications:

• Propositional Logic: Commonly used in circuit design, computer programming, and boolean algebra.
• Predicate Logic: Used in formal proofs, database queries (SQL), and artificial intelligence (AI), where relationships between objects are essential.

Conclusion:

• Propositional Logic is useful for simple reasoning about statements, and its logical connectives combine propositions to form more complex expressions.
• Predicate Logic allows more sophisticated reasoning, as it involves quantifiers and predicates, enabling the expression of statements involving variables and relationships between them.

Understanding both logics is crucial in fields like computer science, mathematics, and logic, as they form the foundation for reasoning and proofs in various applications.