FORMAL LOGIC

Computer Science School of Computing

3.1 Prove that the following formula is satisfiable by means of a semantic argument, i.e. by arguing directly from the definitions of the truth values of formulas, and the semantics of quantifiers. x(p(x)q(x))(xp(x)xq(x)) 3.2 Consider the following first-order interpretation: \[ \mathscr{I}=\left(\mathscr{N}^{+},\{\text {prime, less_than }\},\{1\} ight) \] where N+is the set of positive natural numbers, and prime and less_than are unary and binary relations respectively, as in number theory. For each of the following formulas, state whether it is satisfied by I or not. Explain your answer in terms of the interpretations of the predicates under I. (i) x(p(x)y(p(y)q(x,y))) (ii) xy(q(x,y)z(p(z)q(x,z)q(z,y))) 3.3 Prove the validity of the following formula by means of a semantic tableau. (xp(x)xq(x))x(p(x)q(x)) 3.4 Prove that the formula in Question 3.3 is a theorem of the Gentzen system G. Annotate each line of your proof with the rule used