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.
38 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a mathematical proof?
Show answer
A logical argument establishing that a statement is necessarily true- What is direct proof?
Show answer
A proof technique that assumes the hypothesis and logically derives the conclusion- What is proof by contraposition?
Show answer
Proving a conditional statement by proving its logically equivalent contrapositive- What is proof by contradiction?
Show answer
Assuming the negation of a statement and showing it leads to a logical contradiction- What is mathematical induction used to prove?
Show answer
Statements that hold true for all natural numbers or an infinite sequence- What is the base case in a proof by induction?
Show answer
Verifying the statement holds true for the smallest (initial) value- What is the inductive step in a proof by induction?
Show answer
Showing that if the statement holds for some value k, it also holds for k+1- What is strong induction?
Show answer
An induction variant assuming the statement holds for all values up to k, not just k itself- What is a counterexample?
Show answer
A single case that disproves a universally quantified statement- What is proof by cases?
Show answer
Dividing a proof into distinct scenarios and proving the statement holds in each one- What is an existence proof?
Show answer
A proof showing that at least one object with a given property exists- What is a constructive proof?
Show answer
A proof that explicitly builds or identifies the object it claims exists- What is a non-constructive proof?
Show answer
A proof showing something exists without explicitly constructing an example- What is vacuous truth, in logic?
Show answer
A conditional statement that is true simply because its hypothesis is always false- What does it mean for a proof to be valid?
Show answer
Each step follows logically from the previous ones according to accepted rules of inference
FlashKeepers