Formal Proof Methods Flashcard

Front

Which of the following is a valid method of formal proof? Intuition, Guess and check, Simulation

Back

Proof by contradiction

Front

In a direct proof, the approach is to:

Back

Start from the hypothesis and derive the conclusion.

Front

Which of these is an example of an additional form of proof? Proof by Contrapositive, Proof by Drawing, Proof by Discussion, Proof by Multiplication

Back

Proof by Contrapositive

Front

The contrapositive of the implication “If P, then Q” is:

Back

If not Q, then not P

Front

A proof by contradiction involves:

Back

Proving that the conclusion is false

Front

Inductive proofs are most commonly used to prove statements about: Real numbers, Turing machines, Regular languages, Natural numbers

Back

Natural numbers

Front

The base case in an inductive proof:

Back

Establishes the statement for the initial value.

Front

In mathematical induction, the inductive step proves that:

Back

If the statement holds for n, it holds for n+1

Front

Which of the following is NOT a type of finite automaton? DFA, NFA, PDA

Back

PDA

Front

A DFA is defined as a 5-tuple. Which of the following is NOT a component of this tuple? Set of states, Input alphabet, Stack, Transition function

Back

Stack