CS208 Logic & Algorithms

Semester 1: Logic

Proof Rules for Or and Not

So far, we have seen the basic natural deduction system and the proof rules for and and the rules for implication. We now add the rules for the remaining two connectives of Propositional Logic: "or" and "not".

Videos

These videos describe the rules for "or":

and for "not":

Enter any notes to yourself here.

Slides

The Interactive Editor

The rules for "or" and "not" are also available in the proof editor. This video explains how to use them for some examples.

Enter any notes to yourself here.

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

If we have A or B, and both imply C, then we have C.

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

Exercise 2

If we have A or B, and A implies C and B implies D, then we have C or D.

(config (goal "(A \/ B) -> (A -> C) -> (B -> D) -> (C \/ D)") (solution (Rule(Introduce a-or-b)((Rule(Introduce a-implies-c)((Rule(Introduce b-implies-d)((Rule(Use a-or-b)((Rule(Cases a b)((Rule Left((Rule(Use a-implies-c)((Rule Implies_elim((Rule(Use a)((Rule Close())))(Rule Close())))))))(Rule Right((Rule(Use b-implies-d)((Rule Implies_elim((Rule(Use b)((Rule Close())))(Rule Close())))))))))))))))))))

Exercise 3

If A or B implies C, then we know that both A implies C and B implies C.

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

Exercise 4

A or (B and C) implies (A or B) and (A or C). This is one direction of the distributivity law we used in Converting to CNF.

(config (assumptions (H "A \/ (B /\ C)")) (goal "(A \/ B) /\ (A \/ C)") (solution (Rule Split((Rule(Use H)((Rule(Cases a b-and-c)((Rule Left((Rule(Use a)((Rule Close())))))(Rule Right((Rule(Use b-and-c)((Rule Conj_elim1((Rule Close())))))))))))(Rule(Use H)((Rule(Cases a b-and-c)((Rule Left((Rule(Use a)((Rule Close())))))(Rule Right((Rule(Use b-and-c)((Rule Conj_elim2((Rule Close())))))))))))))))

Exercise 5

(A or B) and (A or C) imply A or (B and C). This is other direction of distributivity.

(config (assumptions (H "(A \/ B) /\ (A \/ C)")) (goal "A \/ (B /\ C)") (solution (Rule(Use H)((Rule Conj_elim1((Rule(Cases a b)((Rule Left((Rule(Use a)((Rule Close())))))(Rule(Use H)((Rule Conj_elim2((Rule(Cases a c)((Rule Left((Rule(Use a)((Rule Close())))))(Rule Right((Rule Split((Rule(Use b)((Rule Close())))(Rule(Use c)((Rule Close())))))))))))))))))))))

Exercise 6

A implies ¬¬A:

(config (goal "A -> ¬ ¬ A") (solution (Rule(Introduce not-not-a)((Rule(Use excluded-middle)((Rule(Cases a not-a)((Rule(Use a)((Rule Close())))(Rule(Use not-not-a)((Rule NotElim((Rule(Use not-a)((Rule Close())))))))))))))))

Exercise 7

If we assume A or ¬A, then ¬¬A implies A. (We can't prove ¬¬A → A without this assumption, see Soundness, Completeness, and Some Philosophy.

(config (assumptions ("excluded-middle" "A \/ ¬A")) (goal "¬¬A -> A") (solution (Rule(Introduce not-not-a)((Rule(Use excluded-middle)((Rule(Cases a not-a)((Rule(Use a)((Rule Close())))(Rule(Use not-not-a)((Rule NotElim((Rule(Use not-a)((Rule Close())))))))))))))))

Exercise 8

A → F implies ¬A, which demonstrates one direction of the equivalence between them.

(config (goal "(A -> F) -> ¬A") (solution (Rule(Introduce a-implies-F)((Rule(NotIntro H)((Rule(Use a-implies-F)((Rule Implies_elim((Rule(Use H)((Rule Close())))(Rule Close())))))))))))

and ¬A implies A → F, which demonstrates the other direction.

(config (goal "¬A -> (A -> F)") (solution (Rule(Introduce not-a)((Rule(Introduce a)((Rule(Use not-a)((Rule NotElim((Rule(Use a)((Rule Close())))))))))))))