Recursive definitions and proof stratergies Flashcards
1
Q
What are the three parts of a recursive definition?
A
- A basic clause - for the “starting” elements
- An inductive clause - to build other elements
- An extremal clause - to eliminate unwanted elements
2
Q
How do you define a recursively defined function?
A
- Specify the value of the function at zero
- Give a rule for finding its value at any integer from its values at smaller integers
3
Q
What are two common features of a proof strategy?
A
- A proof starts with an assumptions (called premises, conditions or pre-conditions)
- A proof has a goal
4
Q
What are elimination stratergies?
A
Eliminating a logical element in order to reduce the distance to the goal.
5
Q
What are introduction strategies?
A
Introducing logical elements in order in to get closer to the goal.
6
Q
What is modus ponens?
A
If P implies Q and P is true then Q is true
7
Q
What is modus tollens?
A
If P implies Q and not Q then not P follows