Recursive definitions and proof stratergies

Question 1

What are the three parts of a recursive definition?

Answer 1

1. A basic clause - for the “starting” elements
2. An inductive clause - to build other elements
3. An extremal clause - to eliminate unwanted elements

Question 2

How do you define a recursively defined function?

Answer 2

1. Specify the value of the function at zero
2. Give a rule for finding its value at any integer from its values at smaller integers

Question 3

What are two common features of a proof strategy?

Answer 3

• A proof starts with an assumptions (called premises, conditions or pre-conditions)
• A proof has a goal

Question 4

What are elimination stratergies?

Answer 4

Eliminating a logical element in order to reduce the distance to the goal.

Question 5

What are introduction strategies?

Answer 5

Introducing logical elements in order in to get closer to the goal.

Question 6

What is modus ponens?

Answer 6

If P implies Q and P is true then Q is true

Question 7

What is modus tollens?

Answer 7

If P implies Q and not Q then not P follows