WGU C959 - Discrete Math exam questions and answers

What is the notation for subset? ⊆ A collection of objects is known as a set What is the notation for integers? ℤ What is the notation for element? ∈ What is the notation for set-roster? { } Write the set-builder notation for, "Numbers whose square roots are an integer" { x | √x ∈ ℤ} Write the set-builder notation for "the set of all x's, such that x is greater than 0" { x | x > 0} T/F: Order matters in ordered pairs? True In a Cartesian Product of two sets, every element of the CROSS PRODUCT is an ordered pair What is the Cartesian Product for: {a,b} x {0,1} A x B = { {a,1} , {a,0} , {b,1} , {b,0} } Ordered pairs are _____ of the Cartesian Product elements A ______ is a subset between two different sets relation Give the general equation for Relations (a,b) ∈ A x B (i.e. (a,b) is the ordered pair and A x B are two different sets) Describe in words what this formula means: (a,b) ∈ A x B Ordered pair (a,b) are in the two sets A x B True ∧ True = True True ∧ False = False False ∧ False = False True ∨ False = True True ∨ True = True False ∨ False = False A compound proposition is a tautology if the proposition is always _____ True A compound proposition is a contradiction if the proposition is always _____ False If p is False and q is True, solve this equation. p → q True If an equation is show as this "p → q" and the hypothesis is false, then the answer to the question is _____ True Give the truth table for ¬(p ↔ q) F T T F What is the logical equivalence of ¬(p ∧ q) ≡ ? (¬p ∨ ¬q) What is the logical equivalence of ¬(p ∨ q) ≡ ? (¬p ∧ ¬q) What is the logical equivalence of p→q ≡ ? (¬p ∨ q) In Boolean Algebra the addition symbol is the same as what? OR The XOR operation outputs 1 when what? Both inputs are different (1 XOR 0 = 1) (1 XOR 1 = 0) Boolean multiplication is the same as what? AND The minterm must evaluate to what 1 0 NAND 1 = 1 1 NAND 1 = 0 0 NAND 0 = 1 The NAND gate computes the NAND operation: x↑y The NOR gate computes the NOR operation: x↓y The NAND gate outputs 0 if all inputs are _____ 1 The NOR gate outputs 1 if all inputs are _____ 0 The gate outputs 1 if all inputs are 0 and outputs _____ 0 1 NOR 1 = 0 1 NOR 0 = 0 0 NOR 0 = 1 A two-input XOR gate (for "exclusive OR") outputs 1 if the input values differ. True or False True 1 XOR 0 = 1 1 XOR 1 = 0 0 XOR 0 = 0 A two-input XNOR gate (for "exclusive NOR") outputs 1 if the input values are the same. True or False True 1 XNOR 0 = 0 1 XNOR 1 = 1 0 XNOR 0 = 1 Which gate follows the same rules as Boolean multiplication? AND Which gate follows the same rules as Boolean addition? OR What is the maximum length of a cycle in a graph? The amount of Vertices that connect. The proposition p ⊕ q is true if... Exactly one of the propositions p and q is true but not both Give DeMorgans Law for QUANTIFIED STATEMENTS (there are 2 laws) ¬∀xP(x) ≡ ∃x¬P(x) ¬∃xP(x) ≡ ∀x¬P(x) Use DeMorgans Law to solve: ¬∃x P(x) ∀x ¬P(x) Use DeMorgans Law to solve: ¬∃x (P(x) ∨ Q(x)) ∀x (¬P(x) ∧ ¬Q(x)) Use DeMorgans Law to solve: ¬∀x (P(x) ∧ Q(x)) ∃x (¬P(x) ∨ ¬Q(x)) Is the variable y bound in the expression ∀xQ(x,y)? No Is the following logical expression a proposition: ∀z∃yQ(x,y,z)? Why? No. X is not bound If the domain of a universal statement is small, it may be easiest to prove the statement by checking each element individually. A proof of this kind is called a _____ proof by exhaustion A _____ is an assignment of values to variables that shows that a universal statement is false counterexample When are XNOR gates equal to 0? When both inputs = 0 When both inputs = 1 The NAND operation outputs 1 for all combinations except for _____ 1 NAND 1 contrapositive of a conditional statement If not q, then not p In a _______ conditional statement we assume the question is false, and then use the falsity to prove that the statement is possibly true contradiction Contradiction, Contrapositive or Direct Proof: p→q = p→-q Contrapositive Because the empty set has no elements, for any element a, a ∉ ∅ is _____ true The set with no elements is called the empty set and is denoted by the symbol: ∅