## Transcribed Text

1. We have started doing the semantics of FOL. We can now say what it is for any
sentence of FOL to be true or false in an interpretation, unless that sentence of FOL has a
quantier in it.
On the left below are eight FOL sentences without quantiers, and on the right is an interpretation that I provided. Please say whether these FOL sentences are true or false in the
interpretation provided.
(a) (F(b) ∧ G(b))
(b) a = c
(c) b = c
(d) (S(a, b) ∨ S(d, c))
(e) (G(d) → G(c))
(f) ((R(b, a) ∧ R(b, b)) → F(d))
(g) (a = b ↔ ¬c = d)
(h) (a = a ∧ (F(a) ∧ ¬G(a)))
Domain: All the numbers.
a: 2
b: 3
c: 2
d: 5
F(x): x is even.
G(x): 3, 5, 7, 10
R(x, y): x is greater than y.
S(x, y): < 2, 3 >, < 3, 2 >
2. Pretty soon, we will talk about validity for argumentsin FOL. It is going to be exactly what you
would expect: since we have said that interpretations will be our “cases” in FOL, an FOL
argument will be valid if and only if there is no interpretation in which the premises are true
and the conclusion is false.
And so: below are four arguments in FOL. For each one, there is an interpretation in which
the premise(s) are true and the conclusion is false: as we will say, the argument is not valid in
FOL. For each argument, please provide such an interpretation: one in which the premise(s)
are true and the conclusion is false.
(a) F (a) ∴ G(a)
(b) a = a ∴ ¬b = a
(c) (F (a) → G(a)), G(a) ∴ (F (a) ↔ G(a))
(d) (R(a, b) ∧ R(b, c)) ∴ R(a, c)
3. More proof practice! This is the same as on Assignment 7: please just prove these things in
our deduction system for FOL, using the rules that were also in our system for TFL: both the
basic and the derived rules are allowed.
(a) (S(a, b) ∨ P ), (P ∨ S(b, a)), ¬P ` (S(a, b) ∧ S(b, a))
(b) (a = b ∨ (b = c → a = b)) ` (¬a = b → ¬b = c)
(c) (G(b) ∧ (G(a) ∨ G(c))) ` ((G(b) ∧ G(a)) ∨ (G(b) ∧ G(c)))
(d) (R(a, b) → R(b, c)), (R(a, b) ∧ R(b, a)) ` (R(a, b) → (R(b, c) ∧ R(b, a)))

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

1.

a. False

b. True

c. False

d. True

e. False

f. True

g. False

h. True

2.

a.

Domain: All the numbers.

a: 2

F(x): _____x is even.

G(x): 3, 5, 7, 10...