Back to the on-screen lesson ·
Looking inside a simple sentence: predicates and names, the two quantifiers, the shapes that symbolise claims about a kind, and how a small structure settles them.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to read and write first-order formulas with predicates, names, variables and quantifiers, symbolise claims about a kind with the conditional and conjunction shapes, say which strings the formation rules build, read atomic sentences off a small structure, and say what a universal claim is worth when nothing satisfies its antecedent.
You can symbolise a compound sentence with connectives and test it with a table. Propositional logic cannot look inside a simple sentence, so it cannot see why all dogs bark and Rex is a dog give Rex barks. This unit looks inside.
A predicate letter $F$, $G$, $R$ says something of one or more objects; its arity is how many. A name $a$, $b$ picks out an object. A variable $x$, $y$ stands in a quantifier's place. $\forall x$ is the universal quantifier, $\exists x$ the existential. A quantifier's scope is the formula it was applied to. A structure's domain is the objects there are.
The language gains predicate letters with an arity, names, variables and two quantifiers. An atomic formula is a predicate letter followed by that many terms: $Fa$, $Rab$, $Fx$. The connectives work as before, and $\forall x$ or $\exists x$ in front of a formula makes another formula. An interpretation fixes a non-empty domain, an object for each name, and for each predicate the objects it holds of. $\forall x\, \phi$ is true when every object satisfies $\phi$, $\exists x\, \phi$ when at least one does. Two shapes carry most symbolisation, and they are not interchangeable: every $F$ is $G$ is $\forall x\,(Fx \to Gx)$, restricting with a conditional, while some $F$ is $G$ is $\exists x\,(Fx \wedge Gx)$, asserting with a conjunction. First-order logic quantifies objects and never predicates — that restriction is what the name records.
Another way: steps
Another way: example
No bird sings: $\neg \exists x\,(Bx \wedge Sx)$, and equivalently $\forall x\,(Bx \to \neg Sx)$. Both say the set of singing birds is empty.
The first and worst error is $\forall x\,(Fx \wedge Gx)$ for every $F$ is $G$: that formula says everything whatever is both an $F$ and a $G$, and it is false in almost every structure. Its mirror image is $\exists x\,(Fx \to Gx)$ for some $F$ is $G$, which is true as soon as anything at all fails to be $F$. The third error is expecting a universal claim to guarantee that its subject matter exists; it does not, and a structure where nothing is $F$ makes it vacuously true.
Every dog barks: restrict to dogs, then claim barking. $\forall x\,(Dx \to Bx)$.
Restrict with a conditional.
Some dog barks: name an object and claim both. $\exists x\,(Dx \wedge Bx)$.
Assert with a conjunction.
Swapping the connectives gives two formulas that are almost never what was meant.
The connective is not a detail.
Domain $\{a, b\}$; $F$ holds of $a$ only; $G$ holds of $a$ and $b$.
The interpretation is a list.
$\forall x\,(Fx \to Gx)$: the instance for $a$ is $T \to T$, for $b$ it is $F \to T$. Both true, so the universal is true.
Instance by instance.
$\forall x\,(Fx \wedge Gx)$: the instance for $b$ has $Fb$ false, so the universal is false. Different formula, different answer.
The connective decides.
Only birds sing says that anything that sings is a bird, so the restriction runs the other way.
$\forall x\,(Sx \to Bx)$ — a conditional inside a universal again, with the two predicates exchanged.
Match each English form to the formula that symbolises it.
| $\forall x\, Fx$ | $\exists x\, Fx$ | $\forall x\,(Fx \to Gx)$ | $\exists x\,(Fx \wedge Gx)$ | $\forall x\,(Fx \to \neg Gx)$ | |
|---|---|---|---|---|---|
| Everything is $F$ | |||||
| Something is $F$ | |||||
| Every $F$ is $G$ | |||||
| Some $F$ is $G$ | |||||
| No $F$ is $G$ |
Mark every string below that is a formula of first-order logic.
This task has no paper form; do it on a device.
Let $F$ mean “is a bird” and $G$ mean “sings”. Which formula symbolises “nothing is both a bird and a singer”?
Here are four stages in the construction of $\neg \forall x\, \exists y\, Rxy$. Put them in the order the formation rules produce them.
Number the steps in order (write the number in the box):
A structure has a domain of $2$ objects, each with a name. Complete the sentence about $\forall x\, Fx$.
It is true exactly when k of the instances are true.
In a structure where no object at all satisfies $F$, what is the value of $\forall x\,(Fx \to Gx)$?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The domain is $\{a, b, c\}$, the names $a$, $b$ and $c$ picking out those objects. $F$ holds of $a$ alone, and $G$ holds of $a$ and $c$. Fill in the value of each atomic sentence.
| $F$ holds of it? | $G$ holds of it? | |
|---|---|---|
| $a$ | ||
| $b$ | ||
| $c$ |
You can symbolise claims about a kind in first-order logic and evaluate them in a small structure. Say in your own words why a universal claim about a kind takes a conditional and an existential claim takes a conjunction.
8. Your turn: symbolise *only birds sing*, step 2