Discrete Mathematics Exam 1with 100- correct answers

p v q This is a disjunction: p or q, or p and q. This is an inclusive or. p ^ q This is a conjunction: p and q p ⊕ q This is an exclusive or: either p or q p → q This is an implication. If p, then q Converse conditional statements q → p Contrapositive conditional statements ¬q → ¬p (has the same truth values as p → q) Inverse conditional statement ¬p → ¬q p ↔ q This is a biconditional statement, also known as bi-implications. It means p if and only if q. True if both p and q have the same truth values. Also written as "p is necessary and sufficient for q", "if p then q, and conversely", and "p iff q". Precedence of logical operators in 1st to 5th 1. ¬ 2. ^ 3. v 4. → 5. ↔ Bit This is a symbol with two possible values, specifically 0 (zero) and 1 (one). 1 represents the True value and 0 represents a False value. De Morgan's law When you distribute a "¬", then you flip the conjunction or disjunction sign that you are distributing to. p ∧ T ≡ p p ∨ F ≡ p Identity laws p ∨ T ≡ T p ∧ F ≡ F Domination laws p ∨ p ≡ p p ∧ p ≡ p Idempotent laws ¬(¬p) ≡ p Double negation law p ∨ q ≡ q ∨ p p ∧ q ≡ q ∧ p Commutative laws (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) Associative laws p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) Distributive laws ¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q De Morgan's laws (1st and 2nd) p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p Absorption laws p ∨ ¬p ≡ T p ∧ ¬p ≡ F Negation laws Predicate refers to a property that the subject of the statement can have (e.g. is greater than 3) Propositional function P at x or P(x); the function Functionally Complete Every compound proposition is logically equivalent to a compound proposition composed of only these logical operators Satisfiability Occurs when there is an assignment of truth values to its variables that makes it true Set N natural numbers = {0,1,2,3...} Set Z integers = {....-3,-2,-1,0,1,2,3....} Set Z+ positive integers = {1,2,3.....} Set R real numbers set R+ positive real numbers set C complex numbers Q set of rational numbers Injection Every single input into A (the domain) has a single output in B (the codomain). However, all of the codomain values do not have to be matched up. "One-to-one" Surjection Every element of the codomain is matched up with a value from the domain. Bijection It is both injective and surjective. In other words, every one of the domain has a single single output and every one of the codomain values is matched up with a value of the domain. א The Hebrew symbol aleph. |S| is equal to the cardinality "aleph null" Join of matrices A v B The meet of matrices A ^ B Boolean Product ^ between terms and then v between the two deciding terms Boolean Powers of zero-one matrices for all positive integers n with n >=5, the matrix becomes all ones