Discrete Structures Help Sheet
→ p ⋁ q ≡ q ⋁ p, → A ⋃ B = B ⋃ A,
Laws Propositional Set Theory & Law’s → & ↔ Equivalences
→p⋀q≡q⋀p →A⋂B=B⋂A
Communicative Logical Equivalences; Logical Equivalences;
→ (p ⋀ q) ⋀ r ≡ p ⋀ (q ⋁ → A ⋃ (B ⋃ C) = (A ⋃ B) p → q ≡ ¬p ⋁ q p ↔ q ≡ (p → q) ⋀ (q
Conditional Statements Biconditional Statements
⋃ C,
Associative
→ (p ⋁ q) ⋁ r ≡ p ⋁ (q ⋁ → A ⋂ (B ⋂ C) = (A ⋂ B) p ⋁ q ≡ ¬p → q
r), p → q ≡ ¬q → ¬p → p)
⋂C p ⋀ q ≡ ¬(p → ¬q) p ↔ q ≡ (p ⋀ q) ⋁
p ↔ q ≡ ¬p ↔ ¬q
¬(p → q) ≡ p ⋀ ¬q (¬p ⋀ ¬q)
→ (p ⋁ (q ⋀ r) ≡ (p ⋁ q) → A ⋂ (B ⋃ C) = (A ⋂ B)
r)
⋀ (p ⋁ r), ⋃ (A ⋂ C) (p → q) ⋀ (p → r) ≡ p
Distributive
→ (q ⋀ r)
¬(p ↔ q) ≡ p ↔ ¬q
→ (p ⋀ (q ⋁ r) ≡ (p ⋀ q) → A ⋃ (B ⋂ C) = (A ⋃ B)⋂
⋁ (p ⋀ r) (A ⋃ C) (p → r) ⋀ (q → r) ≡ (p
⋁ q) → r
→ p ⋁ (p ⋀ q) ≡ p → A ⋃ (A ⋂ B) = A,
→ p ⋀ (p ⋁ q) ≡ p → A ⋂ (A ⋃ B) = B (p → q) ⋁ (p → r) ≡ p
Absorption
→ (q ⋁ r)
→ p ⋀ T ≡ p, → A ⋃ ∅ = A,
→p⋁F≡p →A⋂U=A (p → r) ⋁ (q → r) ≡ (p
Identity
⋀ q) → r
→ ¬ (p ⋀ q) ≡ ¬p ⋁ ¬q → ( A ⋃ B ) = A ⋂ B,
→ ¬ (p ⋁ q) ≡ ¬p ⋀ ¬q
DeMorgan
→ ( A ⋂ B) = A⋃ B
p ⋁ T ≡ T, ⋃
p⋀F≡F ⋂ ∅=∅
Domination → → A U = U,
p ⋁ p ≡ p, ⋃
→ → A
p⋀p≡p ⋂
Idempotent → → A A = A,
→ → A A=A
Double Negation → ¬(¬p) ≡ p
p ⋀ ¬p ≡ F
Negation → p V ¬p ≡ T,
→
Complementation → ( A ) = A,
Logic & Set Theory Relations & Mathematical Counting, Discrete Recurrence Graphs,
Equivalences & Ops, Equivalence Induction & Permutation, & Probability Relation Trees, and
Functions & Relations Recursive Combination Boolean
Matrices Definitions Algebra
Proposition is
declarative
sentence
that is either
true or false.
Logical
¬, ⋁, ⋀, →,
Connectives:
↔