➕Logic and Formal Reasoning Unit 6 – Predicate Logic: Reasoning & Proofs

Key Concepts and Definitions

• Predicate logic extends propositional logic by introducing predicates, variables, and quantifiers to represent and reason about properties of objects and relationships between them
• Predicates are symbols that represent properties or relations, taking one or more arguments (variables or constants) and producing a truth value when evaluated
• Variables are symbols that represent arbitrary objects within a given domain, serving as placeholders in predicates and formulas
• Constants are specific objects or entities within the domain of discourse, represented by unique symbols
• Quantifiers, such as the universal quantifier (∀) and the existential quantifier (∃), express the scope and quantity of variables in a formula
  • The universal quantifier (∀) asserts that a property holds for all objects in the domain
  • The existential quantifier (∃) asserts that a property holds for at least one object in the domain
• Domain of discourse refers to the set of objects or entities under consideration in a particular context or discussion
• Formulas in predicate logic are well-formed combinations of predicates, variables, constants, logical connectives, and quantifiers, representing statements or assertions

Syntax and Symbols

• Predicate symbols are typically denoted by uppercase letters (P, Q, R) and represent properties or relations
• Variable symbols are typically denoted by lowercase letters (x, y, z) and serve as placeholders for objects
• Constant symbols are typically denoted by lowercase letters (a, b, c) and represent specific objects or entities
• Logical connectives used in predicate logic include:
  • Conjunction (∧): "and"
  • Disjunction (∨): "or"
  • Implication (→): "if...then"
  • Biconditional (↔): "if and only if"
  • Negation (¬): "not"
• Quantifier symbols:
  • Universal quantifier (∀): "for all"
  • Existential quantifier (∃): "there exists"
• Parentheses and brackets are used to indicate the scope and precedence of logical connectives and quantifiers

Logical Operators and Connectives

• Conjunction (∧) combines two formulas, yielding true only when both formulas are true
• Disjunction (∨) combines two formulas, yielding true when at least one formula is true
• Implication (→) represents a conditional statement, yielding false only when the antecedent is true and the consequent is false
• Biconditional (↔) represents an "if and only if" relationship, yielding true when both formulas have the same truth value
• Negation (¬) reverses the truth value of a formula
• The order of precedence for logical connectives, from highest to lowest, is: ¬, ∧, ∨, →, ↔
• Logical equivalence (≡) denotes that two formulas have the same truth value for all possible interpretations
  • Logical equivalences can be used to simplify and transform formulas while preserving their meaning

Truth Tables and Validity

• Truth tables are used to evaluate the truth values of formulas for all possible combinations of truth values assigned to their component propositions or predicates
• Each row in a truth table represents a unique combination of truth values for the component propositions or predicates
• The number of rows in a truth table is determined by $2^n$, where $n$ is the number of unique propositions or predicates in the formula
• A formula is considered logically valid (a tautology) if its truth table yields true for all possible combinations of truth values
• A formula is considered logically invalid (a contradiction) if its truth table yields false for all possible combinations of truth values
• A formula is considered contingent if its truth table yields a mixture of true and false values, depending on the specific truth value assignments

Rules of Inference

• Rules of inference are principles that allow the derivation of new, logically valid formulas from existing formulas
• Modus Ponens (MP): If $P$ and $P \to Q$ are true, then $Q$ is true
• Modus Tollens (MT): If $\neg Q$ and $P \to Q$ are true, then $\neg P$ is true
• Hypothetical Syllogism (HS): If $P \to Q$ and $Q \to R$ are true, then $P \to R$ is true
• Disjunctive Syllogism (DS): If $P \lor Q$ and $\neg P$ are true, then $Q$ is true
• Constructive Dilemma (CD): If $(P \to Q) \land (R \to S)$ and $P \lor R$ are true, then $Q \lor S$ is true
• Universal Instantiation (UI): If $\forall x P(x)$ is true, then $P(c)$ is true for any constant $c$ in the domain
• Existential Generalization (EG): If $P(c)$ is true for some constant $c$, then $\exists x P(x)$ is true

Proof Techniques

• Direct proof: Assumes the premises are true and uses logical steps to derive the conclusion
• Proof by contradiction: Assumes the negation of the conclusion and shows that it leads to a logical contradiction with the premises or known facts
• Proof by cases: Divides the proof into distinct cases and proves the conclusion for each case separately
• Proof by induction: Proves a statement for a base case and then shows that if the statement holds for a particular case, it also holds for the next case
  • Mathematical induction is commonly used to prove statements involving natural numbers
• Proof by counterexample: Disproves a universal statement by providing a specific example that contradicts it
• Proof by contraposition: Proves a conditional statement $P \to Q$ by proving its contrapositive $\neg Q \to \neg P$
• Proof by equivalence: Proves a biconditional statement $P \leftrightarrow Q$ by proving both $P \to Q$ and $Q \to P$

Common Fallacies

• Fallacies are flawed arguments that may appear convincing but are logically invalid
• Affirming the consequent: Concluding $P$ from $Q$ and $P \to Q$
• Denying the antecedent: Concluding $\neg Q$ from $\neg P$ and $P \to Q$
• Begging the question (circular reasoning): Using the conclusion as a premise in the argument
• Equivocation: Using a term with multiple meanings in different parts of the argument, leading to ambiguity and flawed reasoning
• False dilemma (false dichotomy): Presenting a limited set of options as if they were the only possibilities, disregarding other viable alternatives
• Straw man: Misrepresenting or oversimplifying an opponent's argument to make it easier to refute
• Appeal to authority: Relying on the opinion of an authority figure to support a claim, rather than presenting valid arguments or evidence

Practical Applications

• Predicate logic is used in various fields, including mathematics, computer science, linguistics, and philosophy, to analyze and reason about complex statements and arguments
• In mathematics, predicate logic is employed to formalize theories, define concepts, and prove theorems
  • Set theory, which forms the foundation of modern mathematics, is formalized using predicate logic
• Computer science utilizes predicate logic in areas such as artificial intelligence, knowledge representation, and automated theorem proving
  • Programming languages and databases often incorporate elements of predicate logic to express queries, constraints, and assertions
• Linguistics applies predicate logic to study the formal structure of natural language and analyze the meaning of sentences
  • Predicate logic can be used to represent the logical form of sentences and capture the relationships between words and phrases
• Philosophy employs predicate logic to analyze and evaluate arguments, theories, and concepts
  • Philosophical discussions often involve complex statements and arguments that can be clarified and assessed using the tools of predicate logic
• Predicate logic provides a framework for precise communication, rigorous reasoning, and the identification and resolution of ambiguities and inconsistencies in various domains