CS208 Logic & Algorithms

Semester 1: Logic

Natural Deduction: Implication

Video

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

Theorem:
 ⊢ A → A
Proof
goal: A → A
Proof incomplete (1 subgoal open).

Exercise 2

Theorem:
 ⊢ (A ∧ B) → (B ∧ A)
Proof
goal: (A ∧ B) → (B ∧ A)
Proof incomplete (1 subgoal open).

Exercise 3

Theorem:
 ⊢ ((A ∧ B) → C) → A → B → C
Proof
goal: ((A ∧ B) → C) → A → B → C
Proof incomplete (1 subgoal open).

Exercise 4

Theorem:
 ⊢ (A → B → C) → (A ∧ B) → C
Proof
goal: (A → B → C) → (A ∧ B) → C
Proof incomplete (1 subgoal open).

Exercise 5

Theorem:
 ⊢ (A → B) → (B → C) → A → C
Proof
goal: (A → B) → (B → C) → A → C
Proof incomplete (1 subgoal open).

Exercise 6

Theorem:
 ⊢ (A ∧ B ∧ C) → ((A ∧ B) ∧ C)
Proof
goal: (A ∧ B ∧ C) → ((A ∧ B) ∧ C)
Proof incomplete (1 subgoal open).

Exercise 7

Theorem:
 ⊢ (A ∧ B) → (B → C) → (A ∧ C)
Proof
goal: (A ∧ B) → (B → C) → (A ∧ C)
Proof incomplete (1 subgoal open).