C959 Discrete Math I| 305 questions and answers.

Form When an argument has been translated from English using symbols Invalid Describes an argument when the conclusion is false in a situation with all the hypotheses are are true Valid Describes an argument when the conclusion is true whenever the hypotheses are all true Conclusion The final proposition Hypothesis Each of the propositions within an argument Argument Sequence of propositions Two Player Game In reasoning whether a quantified statement is true or false, it is a useful way to think of the statement in which universal and existential compete to set the statement's truth value. Nested Quantifier A logical expression with more than one quantifier that binds different variables in the same predicate Predicate A logical statement whose truth value is a function of one or more variables Domain of a variable The set of all possible values for the variable universal quantifier ∀ "for all" universally quantified statement ∀x P(x) Counterexample For a universally quantified statement, it is an element in the domain for which the predicate is false. existential quantifier ∃ "there exists" Existentially quantified statement ∃x P(x) Quantifier Two types are universal and existential Quantified Statement Logical statement including universal or existential quantifier Logical proof A sequence of steps, each of which consists of a proposition and a justification for an argument Arbitrary element Has no special properties other than those shared by all elements of the domain Particular element May have properties that are not shared by all the elements of the domain Theorem Statement that can be proven true Proof Series of steps, each of which follows logically from assumptions, or from previously proven statements, whose final step should result in the statement of the theorem being proven Axiom Statements assumed to be true Generic object We don't assume anything about it besides assumptions given in the statement of the theorem Proof by exhaustion If the domain is small, might be easiest to prove by checking each element individually Counterexample An assignment of values to variables that shows that a universal statement is false Direct proof The hypothesis p is assumed to be true and the conclusion c is proven to be a direct result of the assumption; for proving a conditional statement Rational number A number that can be expressed as the ratio of two integers in which the denominator is non-zero Proof by contrapositve Proves a conditional theorem of the form p->c by showing that the contrapositive -c->-p is true Even integer 2k for some integer k Odd integer 2k+1 for some integer k Irrational number Real number that cannot be written as a fraction Proof by contradiction Starts by assuming that the theorem is false and then shows that some logical inconsistency arises as a result of this assumption Indirect proof Another name for a proof by contradiction Proof by cases For a universal statement, it breaks the domain into different classes and gives a different proof for each class. All of the domain must be covered. Parity Whether a number is odd or even Absolute value Of a real number x, is defined as |x| = -x if x ≤ 0, and |x| = x if x ≥ 0. Set A collection of objects Elements Objects in a set Roster notation Definition of a set by listing elements enclosed in curly braces with elements separated by commas Empty set Set with no elements, denoted Ø Finite set Set with finite number of elements Infinite set Set with infinite number of elements Cardinality Number of elements in set A, denoted |A| Set N Set of natural numbers Set Z Set of all integers Set Q Set of rational numbers