CM20019---Computation III:
Formal Logic and Semantics
2007
Exercise sheet 5---Solutions
Problem 1
=========
For example, take F as (X * 0) /= X; I is the interpretation (N, `*', `/='), where N is the set of natural numbers, `*' is the multiplication function and `/=' is the `not equal' relation.
The only valuation that falsifies F is [X := `0'] (where `0', of course, is the semantic zero).
Problem 2
=========
(1) Yes.
(2) For example, f(x) = x, or f(x) = a, or f(x) = b. There are other possibilities as well.
Problem 3
=========
(1) F1 and F3 are valid, but F2 is not: in fact, consider a valuation where X := 0, what could Y be?
(2) F1 is not valid for any valuation, while F2 and F3 are always valid.
Problem 4
=========
For example, F can be
(EX Y)((r(0,0) ^
r(s(0),s(0)) ^
(FA X)(FA Y)(FA Z)(FA W)((r(Y,Z) ^ r(s(Y),W) ^ (Z + W) = X
) -> r(s(s(Y)),X)
)
) -> r(Y,X)
) .
We interpret the formula in the domain of natural numbers, where s stands for `successor' and + stands for `addition'. The predicate r is defined by the formula F and corresponds to a relation such that r(y,x) is true if x is the y.th Fibonacci number.