Logic and Propositional Calculus
Mathematical logic formalises reasoning. Propositional logic deals with statements that are true or false. It is the basis of digital circuits, programming conditions, and formal verification.
Propositions
A proposition is a declarative statement that is either true (T) or false (F). "5 is prime" is a proposition; "Close the door" is not. Propositions are denoted by variables p, q, r.
Logical Connectives
Negation (¬p): reverses truth value. Conjunction (p ∧ q): true when both true. Disjunction (p ∨ q): true when at least one true. Implication (p → q): false only when p true and q false. Biconditional (p ↔ q): true when both have the same value.
Truth Tables
A truth table lists all possible truth value combinations and the resulting compound proposition value. For n variables, there are 2^n rows. Truth tables verify logical equivalences, tautologies (always true), contradictions (always false), and contingencies.
Logical Equivalence
Two propositions are logically equivalent (≡) if they have the same truth table. Important equivalences: De Morgan's laws, double negation, contrapositive (p → q ≡ ¬q → ¬p), distributive, absorption, and exportation laws.
Predicate Logic
Predicate logic extends propositional logic with variables and quantifiers. A predicate P(x) becomes a proposition when x is assigned a value. The universal quantifier (∀x) means "for all"; the existential quantifier (∃x) means "there exists". Negation: ¬(∀x P(x)) ≡ ∃x ¬P(x).
Proof Methods
Direct proof assumes premises and derives the conclusion. Proof by contradiction assumes the negation and derives a contradiction. Proof by contrapositive proves ¬q → ¬p. Mathematical induction proves a base case and an inductive step. Each method suits different types of theorems.
Normal Forms
Conjunctive Normal Form (CNF) is a conjunction of disjunctions (product of sums). Disjunctive Normal Form (DNF) is a disjunction of conjunctions (sum of products). Any proposition can be converted to CNF or DNF. These forms are used in circuit design and SAT solvers.
Summary
Propositional and predicate logic provide the formal foundation for reasoning, programming, and system verification. Mastery of connectives, truth tables, equivalences, and proof methods is essential for computer science.