CS208 Logic & Algorithms

Semester 1: Logic

Natural Deduction: Implication

Video

Enter any notes to yourself here.

Slides

Exercises

Proof Commands...

The blue boxes represent parts of the proof that are unfinished. The comments (in green) tells you what the current goal is. Either the goal is unfocused:

{ goal: <some formula> }

or there is a formula is focus:

{ focus: <formula1>; goal: <formula2> }

The commands that you can use differ according to which mode youare in. The commands correspond directly to the proof rules given in the videos.

Unfocused mode

These rules can be used when there is no formula in the focus. These rules either act on the conclusion directly to break it down into simpler sub-goals, or switch to focused mode (the use command).

Focused mode

These rules apply when there is a formula in focus. These rules either act upon the formula in focus, or finish the proof when the focused formula is the same as the goal.

Exercise 1

(config (goal "A -> A") (solution (Rule(Introduce a)((Rule(Use a)((Rule Close())))))))

Exercise 2

(config (goal "(A /\ B) -> (B /\ A)") (solution (Rule(Introduce a-and-b)((Rule Split((Rule(Use a-and-b)((Rule Conj_elim2((Rule Close())))))(Rule(Use a-and-b)((Rule Conj_elim1((Rule Close())))))))))))

Exercise 3

(config (goal "((A /\ B) -> C) -> A -> B -> C") (solution (Rule(Introduce ab-implies-c)((Rule(Introduce a)((Rule(Introduce b)((Rule(Use ab-implies-c)((Rule Implies_elim((Rule Split((Rule(Use a)((Rule Close())))(Rule(Use b)((Rule Close())))))(Rule Close())))))))))))))

Exercise 4

(config (goal "(A -> B -> C) -> (A /\ B) -> C") (solution (Rule(Introduce a-implies-b-implies-c)((Rule(Introduce a-and-b)((Rule(Use a-implies-b-implies-c)((Rule Implies_elim((Rule(Use a-and-b)((Rule Conj_elim1((Rule Close())))))(Rule Implies_elim((Rule(Use a-and-b)((Rule Conj_elim2((Rule Close())))))(Rule Close())))))))))))))

Exercise 5

(config (goal "(A -> B) -> (B -> C) -> (A -> C)") (solution (Rule(Introduce a-implies-b)((Rule(Introduce b-implies-c)((Rule(Introduce a)((Rule(Use b-implies-c)((Rule Implies_elim((Rule(Use a-implies-b)((Rule Implies_elim((Rule(Use a)((Rule Close())))(Rule Close())))))(Rule Close())))))))))))))

Exercise 6

(config (goal "(A /\ B /\ C) -> ((A /\ B) /\ C)") (solution (Rule(Introduce a-and-b-and-c)((Rule Split((Rule Split((Rule(Use a-and-b-and-c)((Rule Conj_elim1((Rule Close())))))(Rule(Use a-and-b-and-c)((Rule Conj_elim2((Rule Conj_elim1((Rule Close())))))))))(Rule(Use a-and-b-and-c)((Rule Conj_elim2((Rule Conj_elim2((Rule Close())))))))))))))

Exercise 7

(config (goal "(A /\ B) -> (B -> C) -> (A /\ C)") (solution (Rule(Introduce a-and-b)((Rule(Introduce b-implies-c)((Rule Split((Rule(Use a-and-b)((Rule Conj_elim1((Rule Close())))))(Rule(Use b-implies-c)((Rule Implies_elim((Rule(Use a-and-b)((Rule Conj_elim2((Rule Close())))))(Rule Close())))))))))))))