Exercise 1.3

We've claimed that when evaluating sentences, it doesn't matter which variable assignment we start with. Formally, this means that given any sentence and any model (of the same vocabulary), and any variable assignments and in , then iff Now, we would like you to do two things:

First, show that the above claim is false if is not a sentence but a formula containing free variables.

Secondly, show that the claim is true if is a sentence.

Exercise 1.4

This exercise shows that free variables and constants are very similar. In particular, if a free variable x and a constant c denote the same individual, we can even replace the free variable by the constant without affecting satisfiability.

Formally, let be a model, let be an assignment in , and suppose that . Let be any formula, and let denote the formula obtained by replacing all free occurrences of x in by c. Then iff , where is any x-variant of .

It follows that when working with exact models, every formula is equivalent to a sentence. Explain why.

Exercise 1.5

This exercise shows that the validity of arbitrary formulae is equivalent to the validity of certain sentences. As a first step, we would like the reader to prove that if is a formula containing x as a free variable, then is valid iff is valid.

It follows that the validity of formulae is reducible to the validity of sentences. Explain why. [Hint: we've just found a way of reducing the number of free variables by one while maintaining validity. Iterate this process.]

Exercise 1.6

The Deduction Theorem for first-order logic states that if and only if (That is, there is a close link between validities and valid arguments.) Prove the Deduction Theorem.

Exercise 1.7

Show that the validity of arguments whose premises or conclusions contain free variables is reducible to the validity of arguments whose premises and conclusions are sentences. [Hint: think about Exercise 1.6.]