1. (2 points) We have started working with FOL. FOL is dierent from TFL in its syntax, even
though (as someone pointed out in class) all the sentences of TFL are also sentences of FOL.
The dierence is that there are many new sentences in FOL. Handout 2.2 (which summarizes
Magnus’ Chapter 26) tells us, ocially, what is and what is not a sentence of FOL.
Please say whether or not each of the following is an FOL sentence.
(Note: I’m asking about whether it’s a sentence, not a formula!)
(a) (F(a) ∧ G(a))
(d) (P → Q)
(e) (P → (a = b ↔ ∀xF(x)))
(g) P(x, b, a, q, z)
(h) a = b = c
2. (2 points) We have started to talk about interpretations, and soon we will use them to provide
semantics for FOL, dening entailment, validity, and more in FOL. This will enable us to symbolize English sentences in FOL. We can’t do those things yet.
But what counts as a proof in a natural deduction system is just about which symbols the rules
allow us to write where. We don’t need to think about truth and validity to do proofs.
The natural deduction system we will use for FOL is much like the system for TFL: all the Basic Rules of TFL (as well as the Derived Rules discussed in Assignment 6 and summarized on
Magnus’ p380) are rules of the natural deduction system for FOL. This means we can already
start practicing proofs in the natural deduction system for FOL. Here are two examples.
3 ⊥ ¬E, 1, 2
4 ∀xF(x) IP, 2–3
2 F(a, b)
3 P R, 1
4 P ∧ P ∧I, 1, 3
5 (F(a, b) → (P ∧ P)) →I, 2–4
Below are four FOL arguments. For each, a formal proof of the conclusion of each argument
from the premises is possible, using only rules (Basic or Derived) that also appeared in the
deduction system for TFL. Please give such a proof. (There is space on the next page.)
(a) ∀xF(x),(∀xF(x) → (Q ∨ a = b)), ¬a = b, ` Q
(b) ¬∃x(F(x) ∧ G(x)) ` (∃x(F(x) ∧ G(x)) → ∀xH(x))
(c) (¬P(a) → ¬G(b)) ` (G(b) → P(a))
(d) ((R(a, b) ∧ R(b, c)) ∨ (R(b, a) ∧ R(b, c))) ` R(b, c)
3. (1 Point) We have been talking about arguments like this one:
(a) Willard is a logician.
(b) All logicians wear hats.
(c) Therefore: Willard wears a hat.
We said: it looks like it doesn’t matter who (or what) Willard is; it doesn’t even matter what
most of the words here mean at all. So long as Willard is some thing, and wearing hats is
something that a thing might do, and being a logician is also something that something might
do, the truth of the premises will guarantee the truth of the conclusion: as long as the premises
are true, the conclusion will be true too.
But at the end of class on Wednesday, somebody asked: but what if “wear hats” meant: DOES
NOT wear hats? In that case, the second sentence would really be saying that all logicians
don’t wear hats. And then, the truth of the premises looks like it will not guarantee the truth
of the conclusion!
This is a very good question! I think, however, that even if “wears hats” meant that, the truth
of the premises really would still guarantee the truth of the conclusion!
Please explain why that is.
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.
(a) (F(a)∧G(a)) - Yes
(b) ∀xF(x) - Yes
(c) ∀x(F(G(H(a)))) - No
(d) (P→Q) - Yes
(e) (P→(a=b↔∀xF(x))) - Yes
(f) ∃x(a) - No...