1. Prove this valuation theorem in detail by induction on Form.
"X:Form. " v0:VarX®B. $y: B. Value(X,v0,y).
Base case: X is a
propositional variable. The value of X is either true or false,
so for y:B Value(X, v0, y) since either Value(X,
v0, true) or Value(X, v0, false)
Inductive case:
(a) X is ~F, for F a Form.
By IH, we have that Value(F, v0, y). Hence, we can see that Value(~F, v0, ~y) will also hold.
(b) X is F op G, for F, G Forms, op a binary operator.
By IH, we know that Value(F, v0, f) and Value(G, v0, g) also hold. One sees that the combined formula can evaluate F op G using f op g, so we can see that Value(F op G, v0, f op g) will hold. □