Formal Logic II Unit 12 ReviewLogical Foundations of Math & Computing

Key Concepts and Definitions

• Logic studies the principles of valid reasoning and inference
• Propositions are declarative sentences that are either true or false
• Arguments are sequences of propositions where one (the conclusion) is claimed to follow from the others (the premises)
• Logical connectives include negation ($\neg$), conjunction ($\wedge$), disjunction ($\vee$), implication ($\rightarrow$), and equivalence ($\leftrightarrow$)
  • Negation ($\neg P$) reverses the truth value of a proposition $P$
  • Conjunction ($P \wedge Q$) is true when both $P$ and $Q$ are true
  • Disjunction ($P \vee Q$) is true when at least one of $P$ or $Q$ is true
  • Implication ($P \rightarrow Q$) is false only when $P$ is true and $Q$ is false
  • Equivalence ($P \leftrightarrow Q$) is true when $P$ and $Q$ have the same truth value
• Tautologies are propositions that are always true, while contradictions are always false
• Logical equivalence means two propositions have the same truth value for all possible truth assignments of their variables

Propositional Logic Review

• Propositional logic deals with propositions and their relationships using logical connectives
• Truth tables are used to evaluate the truth values of compound propositions
• Logical identities include De Morgan's laws, distributive laws, and absorption laws
  • De Morgan's laws: $\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q)$ and $\neg(P \vee Q) \equiv (\neg P) \wedge (\neg Q)$
  • Distributive laws: $P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)$ and $P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)$
  • Absorption laws: $P \wedge (P \vee Q) \equiv P$ and $P \vee (P \wedge Q) \equiv P$
• Propositional satisfiability (SAT) determines if there exists a truth assignment that makes a propositional formula true
• Inference rules allow deriving new propositions from existing ones (modus ponens, modus tollens, hypothetical syllogism)
• Propositional resolution is a proof technique that uses the resolution inference rule to prove theorems

First-Order Logic Fundamentals

• First-order logic extends propositional logic by introducing predicates, quantifiers, and variables
• Predicates are functions that map objects to truth values (e.g., $P(x)$: "$x$ is prime")
• Quantifiers express the extent to which a predicate holds:
  • Universal quantifier ($\forall$) states that a predicate holds for all objects in a domain (e.g., $\forall x P(x)$: "For all $x$, $P(x)$ is true")
  • Existential quantifier ($\exists$) states that a predicate holds for at least one object in a domain (e.g., $\exists x P(x)$: "There exists an $x$ such that $P(x)$ is true")
• Variables are symbols that represent objects in a domain (e.g., $x$, $y$, $z$)
• Terms are variables, constants, or functions applied to terms (e.g., $f(x)$, $g(x, y)$)
• Formulas are built using predicates, logical connectives, and quantifiers
• Interpretations assign meanings to the symbols in a first-order language, specifying a domain and mappings for constants, functions, and predicates

Proof Techniques and Strategies

• Direct proof: Assume the premises are true and use logical reasoning to derive the conclusion
• Proof by contradiction: Assume the negation of the conclusion and show that it leads to a contradiction with the premises or known facts
• Proof by contraposition: Prove the contrapositive statement ($\neg Q \rightarrow \neg P$) instead of the original statement ($P \rightarrow Q$)
• Proof by cases: Divide the problem into exhaustive cases and prove the statement for each case
• Proof by induction: Prove a statement for a base case and then show that if it holds for an arbitrary case, it also holds for the next case
  • Mathematical induction proves statements involving natural numbers
  • Structural induction proves statements involving recursive data structures
• Proof by construction: Provide an explicit example or algorithm that demonstrates the existence of an object or solution
• Proof by counterexample: Disprove a universal statement by providing a counterexample that satisfies the premises but not the conclusion

Set Theory and Relations

• Sets are collections of distinct objects, denoted using curly braces (e.g., $\{1, 2, 3\}$)
• Set operations include union ($\cup$), intersection ($\cap$), difference ($\setminus$), and complement ($^c$)
  • Union ($A \cup B$): elements that belong to either set $A$ or set $B$ (or both)
  • Intersection ($A \cap B$): elements that belong to both set $A$ and set $B$
  • Difference ($A \setminus B$): elements that belong to set $A$ but not set $B$
  • Complement ($A^c$): elements in the universal set that do not belong to set $A$
• Venn diagrams visually represent sets and their relationships using overlapping circles
• Cartesian product ($A \times B$) is the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$
• Relations are subsets of the Cartesian product, representing relationships between elements of sets
  • Reflexive relation: $\forall x \in A, (x, x) \in R$
  • Symmetric relation: $\forall x, y \in A, (x, y) \in R \rightarrow (y, x) \in R$
  • Transitive relation: $\forall x, y, z \in A, (x, y) \in R \wedge (y, z) \in R \rightarrow (x, z) \in R$
• Equivalence relations are reflexive, symmetric, and transitive, and they partition a set into disjoint equivalence classes
• Partial orders are reflexive, antisymmetric, and transitive, and they define a ordering on a set (e.g., subset relation $\subseteq$)

Formal Languages and Automata

• Alphabets are finite, non-empty sets of symbols (e.g., $\Sigma = \{0, 1\}$)
• Strings are finite sequences of symbols from an alphabet (e.g., $010$, $\varepsilon$ (empty string))
• Languages are sets of strings over an alphabet (e.g., $L = \{0^n1^n \mid n \geq 0\}$)
• Regular expressions define languages using union, concatenation, and Kleene star operations
  • Union ($L_1 \cup L_2$): strings that belong to either language $L_1$ or $L_2$ (or both)
  • Concatenation ($L_1L_2$): strings formed by concatenating a string from $L_1$ with a string from $L_2$
  • Kleene star ($L^*$): strings formed by concatenating zero or more strings from language $L$
• Finite automata are mathematical models for recognizing regular languages
  • Deterministic finite automata (DFAs) have unique transitions for each state-symbol pair
  • Nondeterministic finite automata (NFAs) allow multiple transitions for a state-symbol pair and $\varepsilon$-transitions
• Context-free grammars generate languages using production rules and nonterminal symbols (e.g., $S \rightarrow aSb \mid \varepsilon$)
• Pushdown automata recognize context-free languages by using a stack memory in addition to states and transitions

Applications in Computer Science

• Propositional logic is used in digital circuit design and verification (e.g., logic gates, Boolean algebra)
• First-order logic is used in artificial intelligence for knowledge representation and reasoning (e.g., expert systems, theorem provers)
• Set theory is fundamental to database design and query languages (e.g., relational algebra, SQL)
• Graph theory, built on set theory and relations, is used in network analysis, optimization, and algorithm design (e.g., shortest path, maximum flow)
• Formal languages and automata are essential for compiler design, parsing, and syntax analysis (e.g., regular expressions, context-free grammars)
• Computability theory uses formal logic to study the limits of computation and decidability (e.g., Turing machines, undecidable problems)
• Cryptography relies on logic and number theory to design secure communication protocols (e.g., RSA, zero-knowledge proofs)

Advanced Topics and Extensions

• Higher-order logic allows quantification over predicates and functions, enabling more expressive reasoning (e.g., $\forall P \exists x P(x)$)
• Modal logic introduces operators for necessity ($\square$) and possibility ($\diamond$) to reason about different modes of truth (e.g., epistemic logic, temporal logic)
• Fuzzy logic assigns degrees of truth to propositions, enabling reasoning with uncertainty and vagueness (e.g., fuzzy sets, membership functions)
• Paraconsistent logic tolerates inconsistencies by avoiding the principle of explosion ($P \wedge \neg P \rightarrow Q$) (e.g., relevance logic, dialethism)
• Category theory provides a general framework for studying structures and their relationships, unifying concepts across mathematics and computer science (e.g., functors, natural transformations)
• Homotopy type theory is a foundational approach that combines type theory, category theory, and homotopy theory, offering a new perspective on the nature of mathematical objects and proofs (e.g., univalence axiom, higher inductive types)
• Quantum logic investigates the logical structure of quantum mechanics, challenging classical assumptions such as the distributive law (e.g., orthomodular lattices, quantum probability)