Note
Studied by 5 people
Midterm Review Notes
REVIEW FOR MIDTERM
ITEMS TO MEMORIZE
Truth Table for the Negation of a Proposition
P | ¬P |
|---|---|
T | F |
F | T |
Truth Table for the Conjunction of Two Propositions
P | Q | P ∧ Q |
|---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | F |
Truth Table for the Disjunction of Two Propositions
P | Q | P ∨ Q |
|---|---|---|
T | T | T |
T | F | T |
F | T | T |
F | F | F |
Truth Table for the Exclusive Or of Two Propositions
P | Q | P ⊕ Q |
|---|---|---|
T | T | F |
T | F | T |
F | T | T |
F | F | F |
Truth Table for the Conditional Statement (P → Q)
P | Q | P → Q |
|---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
Truth Table for the Biconditional (P ↔ Q)
P | Q | P ↔ Q |
|---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | T |
Constructing Truth Tables
Logical Equivalence Proofs
Example: Prove that P ∨ (Q ∧ R) and (P ∨ Q) ∧ (P ∨ R) are logically equivalent.
P | Q | R | Q ∧ R | P ∨ (Q ∧ R) | P ∨ Q | P ∨ R | (P ∨ Q) ∧ (P ∨ R) |
|---|---|---|---|---|---|---|---|
T | T | T | T | T | T | T | T |
T | T | F | F | T | T | T | T |
T | F | T | F | T | T | T | T |
T | F | F | F | T | T | T | T |
F | T | T | T | T | T | T | T |
F | T | F | F | F | T | F | F |
F | F | T | F | F | F | T | F |
F | F | F | F | F | F | F | F |
Logical Equivalences
Laws of Logics
Equivalence | Name |
|---|---|
P ↔ P | Identity laws |
P ∨ F ↔ P | Domination laws |
P ∨ T ↔ T | Domination laws |
P ∧ F ↔ F | Domination laws |
P ∧ T ↔ P | Identity laws |
P ∨ P ↔ P | Idempotent laws |
P ∧ P ↔ P | Idempotent laws |
¬(¬P) ↔ P | Double negation law |
P ∨ Q ↔ Q ∨ P | Commutative laws |
(P ∨ Q) ∨ R ↔ P ∨ (Q ∨ R) | Associative laws |
P ∧ (Q ∨ R) ↔ (P ∧ Q) ∨ (P ∧ R) | Distributive laws |
¬(P ∧ Q) ↔ ¬P ∨ ¬Q | De Morgan's laws |
P ∧ Q ↔ P ∧ (Q ∨ R) | Absorption laws |
P ∨ Q ↔ P ∨ (P ∧ Q) | Absorption laws |
Quantifiers
Types of Quantifiers
Statement | When True | When False |
|---|---|---|
∀x P(x) | P(x) is true for every x | There is an x for which P(x) is false. |
∃x P(x) | There is an x for which P(x) is true. | P(x) is false for every x. |
De Morgan's Laws for Quantifiers
Negation | Equivalent Statement |
|---|---|
¬∀x P(x) | ∃x ¬P(x) |
¬∃x P(x) | ∀x ¬P(x) |
Rules of Inference
Basic Rules of Inference
Rule of Inference | Name |
|---|---|
P, P → Q | Modus ponens |
P, ¬Q | ¬(P → Q) |
P ∧ Q, P | Simplification |
P ∨ Q, ¬P | Q |
P & Q | Conjunction |
(P ∨ Q) ∧ ¬R | Q |
Rules for Quantified Statements
Rule of Inference | Name |
|---|---|
∀x P(x) | Universal Instantiation |
P(c) for arbitrary c | Universal Generalization |
∃x P(x) | Existential Instantiation |
P(c) for some element c | Existential Generalization |
Proof Techniques
Proof by Contradiction
Example: Proof that √2 is irrational.
If we assume √2 is rational, it can be expressed as a fraction p/q (where p and q are integers and q ≠ 0). Squaring both sides results in a contradiction…
Proof by Contraposition
Example: Prove that if n is an integer and 3n + 2 is odd, then n is odd.
Assume that n is even, then n can be expressed as 2k. Therefore, 3(2k) + 2 = 6k + 2, which is even. This contradicts the odd result.