Discrete Math for Computer Science, unit: Proof Techniques. Core concepts, terminology, and worked-example cues a college student meets for this unit, building on prior units without repeating them. Front: a term, concept, or short problem cue. Back: the definition, explanation, or answer.
16 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a mathematical proof?
- A logical argument establishing that a statement is necessarily true
- What is direct proof?
- A proof technique that assumes the hypothesis and logically derives the conclusion
- What is proof by contraposition?
- Proving a conditional statement by proving its logically equivalent contrapositive
- What is proof by contradiction?
- Assuming the negation of a statement and showing it leads to a logical contradiction
- What is mathematical induction used to prove?
- Statements that hold true for all natural numbers or an infinite sequence
- What is the base case in a proof by induction?
- Verifying the statement holds true for the smallest (initial) value
- What is the inductive step in a proof by induction?
- Showing that if the statement holds for some value k, it also holds for k+1
- What is strong induction?
- An induction variant assuming the statement holds for all values up to k, not just k itself
- What is a counterexample?
- A single case that disproves a universally quantified statement
- What is proof by cases?
- Dividing a proof into distinct scenarios and proving the statement holds in each one
- What is an existence proof?
- A proof showing that at least one object with a given property exists
- What is a constructive proof?
- A proof that explicitly builds or identifies the object it claims exists
- What is a non-constructive proof?
- A proof showing something exists without explicitly constructing an example
- What is vacuous truth, in logic?
- A conditional statement that is true simply because its hypothesis is always false
- What does it mean for a proof to be valid?
- Each step follows logically from the previous ones according to accepted rules of inference
FlashKeepers