Formal Logic II Unit 1 ReviewPropositional Logic: Review and Extensions

Key Concepts and Definitions

• Propositions are declarative sentences that can be either true or false but not both simultaneously
• Logical connectives include negation ($\neg$), conjunction ($\wedge$), disjunction ($\vee$), implication ($\rightarrow$), and biconditional ($\leftrightarrow$)
• Truth tables display all possible truth value assignments for a given formula or set of formulas
• Tautologies are formulas that are always true regardless of the truth values assigned to their constituent propositions
• Contradictions are formulas that are always false regardless of the truth values assigned to their constituent propositions
• Logical equivalence occurs when two formulas have the same truth value for all possible truth value assignments
• Validity refers to an argument where the conclusion necessarily follows from the premises
• Soundness refers to a valid argument with true premises

Propositional Logic Basics Recap

• Propositional variables are symbols (usually letters like $p$, $q$, $r$) representing propositions
• Negation ($\neg$) flips the truth value of a proposition from true to false or vice versa
• Conjunction ($\wedge$) is true only when both propositions are true and false otherwise
• Disjunction ($\vee$) is false only when both propositions are false and true otherwise
• Implication ($\rightarrow$) is false only when the antecedent is true and the consequent is false
  • Implication can be thought of as "if...then" statements (if $p$ then $q$)
• Biconditional ($\leftrightarrow$) is true when both propositions have the same truth value and false otherwise
  • Biconditional can be thought of as "if and only if" statements ($p$ if and only if $q$)
• Order of operations: negation, conjunction, disjunction, implication, biconditional

Advanced Propositional Operators

• Exclusive or (XOR) is true when exactly one of the propositions is true and false otherwise
  • Can be expressed using basic connectives: $p \oplus q \equiv (p \vee q) \wedge \neg(p \wedge q)$
• Nand (not-and) is false when both propositions are true and true otherwise
  • Can be expressed using basic connectives: $p \uparrow q \equiv \neg(p \wedge q)$
• Nor (not-or) is true when both propositions are false and false otherwise
  • Can be expressed using basic connectives: $p \downarrow q \equiv \neg(p \vee q)$
• Sheffer stroke (alternative denial) is equivalent to nand
• Peirce's arrow (joint denial) is equivalent to nor
• Advanced operators can simplify complex expressions and are used in digital logic circuits

Truth Tables and Validity

• Truth tables exhaustively list all possible truth value assignments for a given set of propositions
• To construct a truth table, list all combinations of truth values for the propositions and evaluate the formula for each combination
• Tautologies have a truth value of true for every row in their truth table
• Contradictions have a truth value of false for every row in their truth table
• Contingencies have at least one true and one false value in their truth table
• An argument is valid if and only if there is no row in the truth table where the premises are true and the conclusion is false
  • In other words, the conjunction of the premises implies the conclusion
• Checking for validity using truth tables becomes impractical for large numbers of propositions

Formal Proof Techniques

• Formal proofs demonstrate the validity of arguments using a sequence of inference rules
• Modus ponens: if $p$ and $p \rightarrow q$ are true, then $q$ must be true
• Modus tollens: if $\neg q$ and $p \rightarrow q$ are true, then $\neg p$ must be true
• Hypothetical syllogism: if $p \rightarrow q$ and $q \rightarrow r$ are true, then $p \rightarrow r$ must be true
• Disjunctive syllogism: if $p \vee q$ and $\neg p$ are true, then $q$ must be true
• Constructive dilemma: if $p \rightarrow q$, $r \rightarrow s$, and $p \vee r$ are true, then $q \vee s$ must be true
• Proof by contradiction assumes the negation of the conclusion and derives a contradiction, thereby proving the original conclusion
• Proof by cases considers each possible case and shows that the conclusion holds in all cases

Applications in Computer Science

• Propositional logic is the foundation for digital logic circuits and computer architecture
  • Logical gates (AND, OR, NOT, XOR, NAND, NOR) implement logical connectives
• Propositional satisfiability (SAT) is the problem of determining if a propositional formula can be made true by some assignment of truth values
  • SAT solvers have applications in hardware and software verification, planning, and scheduling
• Propositional logic is used in artificial intelligence for knowledge representation and reasoning
  • Rule-based systems and expert systems often use propositional logic to encode domain knowledge
• Programming languages use propositional logic for conditional statements and Boolean expressions
• Database query languages (SQL) use propositional logic for filtering and combining data

Common Fallacies and Pitfalls

• Affirming the consequent: concluding $p$ from $q$ and $p \rightarrow q$ is invalid
  • Example: "If it rains, the grass is wet. The grass is wet, therefore it rained." (The grass could be wet for other reasons)
• Denying the antecedent: concluding $\neg q$ from $\neg p$ and $p \rightarrow q$ is invalid
  • Example: "If you study hard, you will pass the exam. You didn't study hard, therefore you won't pass the exam." (You might pass even without studying hard)
• Begging the question (circular reasoning): using the conclusion as a premise in the argument
  • Example: "God exists because the Bible says so, and the Bible is true because it is the word of God."
• Equivocation: using a term with multiple meanings in different parts of the argument
  • Example: "Feathers are light. What is light cannot be dark. Therefore, feathers cannot be dark."
• False dichotomy: presenting two options as if they were the only possibilities when other alternatives exist
  • Example: "You're either with us or against us." (One can be neutral or partially agree)

Extensions and Related Logical Systems

• First-order logic extends propositional logic by introducing predicates, quantifiers, and variables
  • Allows reasoning about objects and their properties, not just propositions
• Modal logic introduces operators for necessity, possibility, and other modalities
  • Used for reasoning about knowledge, belief, time, and ethics
• Fuzzy logic allows propositions to have truth values between 0 and 1, not just true or false
  • Useful for dealing with vagueness and uncertainty in natural language and decision-making
• Paraconsistent logic allows for inconsistencies without leading to explosion (deriving any proposition from a contradiction)
  • Addresses limitations of classical logic in handling contradictory information
• Relevance logic requires premises to be relevant to the conclusion for an argument to be valid
  • Avoids paradoxes of material implication where irrelevant premises can imply anything
• Intuitionistic logic rejects the law of excluded middle and double negation elimination
  • Corresponds to constructive reasoning in mathematics and computer science