Introduction
Propositional logic: branch of logic dealing with propositions and their connectives. Focus: formal manipulation of declarative statements with truth values true (T) or false (F). Foundation for mathematical logic, computer science, and automated reasoning. Objective: determine truth value of complex statements from components.
"Logic is the anatomy of thought." -- John Locke
Syntax of Propositional Logic
Propositions
Atomic propositions: indivisible declarative statements, e.g., P, Q, R. Compound propositions: formed by combining atomic propositions with connectives.
Alphabet
Symbols include: propositional variables (P, Q, R...), logical connectives (¬, ∧, ∨, →, ↔), parentheses "(" and ")".
Well-formed Formulas (WFF)
Rules: 1) Atomic propositions are WFF. 2) If φ is WFF, then ¬φ is WFF. 3) If φ and ψ are WFF, then (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), (φ ↔ ψ) are WFF. 4) No other strings are WFF.
Formal Grammar
Defined recursively or via context-free grammar specifying production rules for WFF construction.
Formula ::= Atom | ¬ Formula | (Formula Connective Formula)Connective ::= ∧ | ∨ | → | ↔Atom ::= P | Q | R | ...Semantics and Truth Assignments
Truth Values
Domain: {T, F}. Each proposition assigned one truth value.
Interpretation
Function mapping propositional variables to truth values.
Evaluation
Truth value of complex formulas computed from atomic assignments and connective semantics.
Model
An interpretation under which a formula evaluates to true.
Logical Connectives
Negation (¬)
Unary operator; inverts truth value: ¬T = F, ¬F = T.
Conjunction (∧)
Binary operator; true if both operands true.
Disjunction (∨)
Binary operator; true if at least one operand true.
Implication (→)
Binary; false only if antecedent true and consequent false.
Biconditional (↔)
Binary; true if operands share same truth value.
| Connective | Meaning |
|---|---|
| ¬P | Not P |
| P ∧ Q | P and Q |
| P ∨ Q | P or Q |
| P → Q | If P then Q |
| P ↔ Q | P if and only if Q |
Truth Tables
Definition
Tabular method listing all truth value combinations of atomic propositions and resulting formula value.
Construction
Enumerate 2^n rows for n propositions; compute formula column by applying connectives.
Use Cases
Verify tautologies, contradictions, equivalence, satisfiability.
Example: P → QP | Q | P → QT | T | TT | F | FF | T | TF | F | TTautologies and Contradictions
Tautology
Formula true under every interpretation; e.g., P ∨ ¬P.
Contradiction
Formula false under every interpretation; e.g., P ∧ ¬P.
Contingency
Formula true under some interpretations, false under others.
Logical Equivalence
Definition
Two formulas equivalent if they have identical truth values for all interpretations.
Notation
φ ≡ ψ denotes equivalence.
Properties
Reflexive, symmetric, transitive.
Common Equivalences
De Morgan’s laws, double negation, implication elimination.
¬(P ∧ Q) ≡ ¬P ∨ ¬QP → Q ≡ ¬P ∨ QRules of Inference
Modus Ponens
From P and P → Q infer Q.
Modus Tollens
From ¬Q and P → Q infer ¬P.
Disjunctive Syllogism
From P ∨ Q and ¬P infer Q.
Hypothetical Syllogism
From P → Q and Q → R infer P → R.
Constructive Dilemma
From (P → Q) ∧ (R → S) and P ∨ R infer Q ∨ S.
Proof Systems
Hilbert-style Systems
Axioms plus inference rules; minimal and abstract.
Natural Deduction
Derivations constructed via introduction and elimination rules for connectives.
Sequent Calculus
Focus on sequents; structural rules and cut elimination.
Soundness and Completeness
Soundness: all derivable formulas are valid. Completeness: all valid formulas are derivable.
| Proof System | Characteristics |
|---|---|
| Hilbert-style | Axioms + few inference rules |
| Natural Deduction | Introduction/elimination rules |
| Sequent Calculus | Sequents and structural rules |
Applications of Propositional Logic
Mathematics
Foundation for proof theory, set theory, automated theorem proving.
Computer Science
Design of digital circuits, programming languages semantics, verification.
Artificial Intelligence
Knowledge representation, automated reasoning, logic programming.
Philosophy
Formal analysis of arguments, modal and epistemic logic extensions.
Boolean Algebra and Propositional Logic
Correspondence
Propositions correspond to Boolean variables; connectives map to Boolean operations.
Algebraic Laws
Commutativity, associativity, distributivity, identity, complements.
Simplification
Use Boolean identities to minimize propositional formulas.
Applications
Digital logic design, circuit optimization, switching theory.
Examples:P ∨ F ≡ PP ∧ T ≡ PP ∨ ¬P ≡ TLimitations of Propositional Logic
Expressive Power
Cannot express internal structure of propositions or quantification.
First-Order Logic
Extends propositional logic by adding quantifiers and predicates.
Decidability
Propositional logic is decidable; first-order logic is semi-decidable.
Computational Complexity
Satisfiability problem (SAT) is NP-complete.
References
- Enderton, H. B., "A Mathematical Introduction to Logic," Academic Press, vol. 2, 2001, pp. 45-120.
- Boolos, G. S., Burgess, J. P., & Jeffrey, R. C., "Computability and Logic," Cambridge University Press, vol. 5, 2007, pp. 30-95.
- Huth, M., & Ryan, M., "Logic in Computer Science: Modelling and Reasoning about Systems," Cambridge University Press, vol. 2, 2004, pp. 10-60.
- Smullyan, R. M., "First-Order Logic," Dover Publications, vol. 1, 1995, pp. 3-50.
- Mendelson, E., "Introduction to Mathematical Logic," Chapman & Hall, vol. 4, 1997, pp. 100-180.