Logic and Propositional Calculus
Logic is the foundation of mathematical reasoning and plays a crucial role in discrete
mathematics.
1. Propositions and Logical Operators
A proposition is a declarative statement that is either true or false.
Basic logical operators:
- Negation (¬): "not"
- Conjunction (∧): "and"
- Disjunction (∨): "or"
- Implication (→): "if...then"
- Biconditional (↔): "if and only if"
2. Truth Tables
Truth tables display all possible combinations of truth values for compound propositions.
Example:
p | q | p ∧ q
T | T | T
T | F | F
F | T | F
F | F | F
3. Logical Equivalences
Two propositions are logically equivalent if they have the same truth value for all possible
inputs.
Important equivalences:
- De Morgan's Laws:
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
4. Conditional Statements
- Converse: If q → p is the converse of p → q
- Inverse: If ¬p → ¬q is the inverse of p → q
- Contrapositive: If ¬q → ¬p is the contrapositive of p → q
5. Arguments and Validity
An argument is valid if the conclusion logically follows from the premises.
Common valid argument forms:
- Modus Ponens: If p → q and p, then q
- Modus Tollens: If p → q and ¬q, then ¬p
6. Predicate Logic
Predicate logic extends propositional logic by including variables and quantifiers.
Quantifiers:
- Universal quantifier (∀): "for all"
- Existential quantifier (∃): "there exists"
Understanding logic is essential for constructing valid mathematical proofs and analyzing
complex systems in computer science.
