Discrete Math Chapter 1 (CSCI 2610 @ UGA)

Conjunction The conjunction "p and q" is denoted by p∧q. The conjunction p∧q is true when both p and q are true and is false otherwise. Disjunction The disjunction "p or q" is denoted by p∨q. The disjunction p∨q is false when both p and q are false and is true otherwise. Exclusive Or (XOR) The exclusive or "p xor q" is denoted by p⊕q. The exclusive or p⊕q is true when exactly one of p or q is true and is false otherwise. Conditional Statement (Implication) The implication "if p then q" is denoted by p→q. The implication p→q is false when p is true and q is false. It is true otherwise. Negation Operator The negation operator "not" is denoted by the symbol ¬. ∴¬p represents "not p" Converse q → p Inverse ¬p → ¬q Contrapositive (*) ¬q → ¬p Biconditional Statement The Biconditional Statement "p if and only if q" or "p iff q" is denoted by p ↔ q. The biconditional statement p ↔ q is true when p and q have the same truth values and is false otherwise. p↔q = p→q ∧ q→p What order is the precedence of logic operators? 1) ¬ 2) ∧ 3) ∨, ⊕ 4) → 5) ↔ Tautology Needless repetition of an idea by using different but equivalent words; a redundancy. Contradiction A compound proposition that is always FALSE, no matter the truth values of the propositional variables. (ie. p ∧ ¬p ≡ F) Contingency A compound proposition that is neither tautology or a contradiction. Logically Equivalent The compound propositions p and q are called Logically Equivalent if p ↔ q is a tautology the notation p ≡ q denotes that p and q are equivalent. Identity Laws p ∧ T ≡ p p ∨ F ≡ p Domination Laws p ∨ T ≡ T p ∧ F ≡ F Idempotent Laws p ∨ p ≡ p p ∧ p ≡ p Double Negation Law ¬(¬p) ≡ p Commutative Laws p ∨ q ≡ q ∨ p p ∧ q ≡ q ∧ p Associative Laws (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) Distributive Laws p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) De Morgan's Laws ¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q Absorption Laws p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p Negation Laws p ∨ ¬p ≡ T p ∧ ¬p ≡ F How many truth table rows are there per number of variables? 2ⁿ (note: n = # of vars)