Reading material

Pages 17-21.

Additional material

A (proof)system is sound if only valid formulae are provable. A (proof)system is complete if all valid formulae are provable.

tautology is a system to check if a boolean expression is a tautology. Here the formulae are boolean expressions and a formula is valid if it is a tautology and it is provable if tautology return Valid for it.

Therefore, tautology is sound if whenever tautology returns Valid its input was a tautology. tautology is complete if tautology returns Valid for all boolean expressions which are tautologies.

Question

Give a (trivial) system to check if a boolean expression is a tautology which is sound (but not complete). Give a (trivial) system to check if a boolean expression is a tautology which is complete (but not sound).

Exercise 2.11 of the text

Questions 1, 2, 7, 8, 9 from Chapter 1 of