First-Order Logic
Chapter Thirty-One
Syllabus topic Module 1, "First-Order Logic"
Pages 163 to 167 of 591
In one line
First-order logic talks about objects and the relations between them, so one sentence can say something about everything at once.
In the wording a student can write in an examination: first-order logic extends propositional logic with terms that denote objects, predicates that denote relations, functions that denote mappings from objects to objects, and two quantifiers: the universal quantifier, read "for all", and the existential quantifier, read "there exists". An atomic sentence is a predicate applied to terms. Sentences are built from atomic ones by the propositional connectives and by quantification.
What propositional logic could not do
Three failures, and each is repaired by one piece of the new language.
| Failure | Example | The repair |
|---|---|---|
| Cannot refer to objects | Square12IsSafe has no parts | terms: constants, variables, functions |
| Cannot express relations | no way to say 1,2 is next to 1,1 | predicates of more than one argument |
| Cannot generalise | one sentence per square, all obviously the same | quantifiers |
The third is the one that matters most in practice. In the six-square pit world of The Knowledge-Based Agent the rule "a breeze means a pit next door" had to be written once per square. In a hundred squares it is a hundred sentences, and the logic cannot see that they are instances of one thing. First-order logic writes it once.
The syntax
Terms denote objects. Three kinds:
| Kind | Written | Denotes |
|---|---|---|
| Constant symbol | Asha, Amba, Square12 | one particular object |
| Variable | x, y, s | an object, not yet fixed |
| Function term | Mother(Asha), Plus(x, 1) | the object the function gives for those arguments |
A function is not a predicate, and confusing them is the commonest error on this topic. Mother(Asha) is a term: it names a person, and it is neither true nor false. IsMotherOf(Rekha, Asha) is an atomic sentence: it is true or false. A function returns an object; a predicate returns a truth value. The test: can you put it after "the"? "The mother of Asha" is a term. "Rekha is the mother of Asha" is a sentence.
Predicate symbols denote relations. Safe(s) is a relation of one argument, a property. Adjacent(s1, s2) is a relation of two. Between(a, b, c) of three.
An atomic sentence is a predicate applied to terms: Safe(Square12), Adjacent(x, Square11), IsMotherOf(Mother(Asha), Asha).
Complex sentences use the same five connectives as before, plus quantification.
The two quantifiers
Universal, for all. for all x, P(x) is true when P holds of every object.
Existential, there exists. exists x, P(x) is true when P holds of at least one object.
Two idioms, and they are the whole of the marks on quantifiers.
First-Order Logic
A universal quantifier goes with an implication. "All students who attended are eligible" is
for all s, Student(s) and Attended(s) implies Eligible(s)
Writing for all s, Student(s) and Eligible(s) instead says everything in the universe is a student and is eligible, which is false and is the standard mistake. The implication is what restricts the claim to the objects you meant.
An existential quantifier goes with a conjunction. "Some student is eligible" is
exists s, Student(s) and Eligible(s)
Writing exists s, Student(s) implies Eligible(s) is far weaker than intended: an implication is true whenever its premise is false, so a single non-student anywhere in the universe makes that sentence true. It is satisfied by a chair.
The pairing is worth memorising as a slogan: "for all" with "implies", "exists" with "and".
Nesting, and why order matters
Two quantifiers of the same kind may be swapped freely. Two of different kinds may not, and this is the standard 5-mark question.
for all x, exists y, Loves(x, y)
exists y, for all x, Loves(x, y)
The first says everybody loves somebody, possibly a different somebody each. The second says there is one particular person whom everybody loves. The second is much stronger and implies the first; the first does not imply the second.
The general rule: swapping for all and exists changes the meaning, because the inner quantifier's choice may depend on the outer one's object. When exists is inside, the object it picks can vary with the outer object; when it is outside, it cannot.
The connection between the two quantifiers
They are duals, and each can be defined from the other by pushing a negation through it.
for all x, P(x) is equivalent to not (exists x, not P(x))
exists x, P(x) is equivalent to not (for all x, not P(x))
Read the first in words: everything is P exactly when nothing is not P. These are De Morgan's laws for quantifiers, and they matter for the same reason the propositional ones did: they let a negation be pushed inward, which is the first step of converting to clause form.
The consequence worth stating: "not all students passed" is not "no student passed". The first is not (for all s, Passed(s)), which is exists s, not Passed(s), one failure. The second is for all s, not Passed(s). Papers ask for exactly this.
Semantics: the interpretation
A model in propositional logic assigned true or false to each symbol. A model in first-order logic is more elaborate, and naming its parts is worth marks.
| Part | What it is |
|---|---|
| Domain, or universe of discourse | the non-empty set of objects the sentences are about |
| Interpretation of a constant | which object of the domain it names |
| Interpretation of a predicate | which tuples of objects the relation holds of |
| Interpretation of a function | a mapping from tuples of objects to objects |
First-Order Logic
Two consequences. The domain must be non-empty, or for all x, P(x) would be trivially true and exists x, P(x) never true, and the two would stop being duals. And the domain may be infinite, which is where first-order inference stops being a matter of enumeration: propositional logic had 2 to the power n models and first-order logic can have unboundedly many.
Equality, and what it buys
x = y is a built-in predicate, true when both terms denote the same object. It is worth its own mention because it does something no other predicate can.
Without equality, "Asha has exactly one mother" cannot be said. With it:
exists m, IsMotherOf(m, Asha) and (for all m2, IsMotherOf(m2, Asha) implies m2 = m)
And it is how distinctness is asserted: not (Asha = Vikram). First-order logic does not assume two different names denote different objects, which surprises people. Mumbai and Bombay may denote the same object unless you say otherwise.
Decidability, which is the price of the expressive power
This is the honest cost, and a paper can ask for it.
Propositional entailment is decidable: hard, co-NP-complete, and a procedure always terminates with the right answer.
First-order entailment is semi-decidable, also called not decidable. There is a procedure that will find a proof if one exists, but there is no procedure guaranteed to terminate when the query is not entailed: it may run forever. That is a theorem, not a gap in current knowledge, and it is what Robinson's paper and every theorem prover since have had to live with.
The practical consequence: real systems restrict the language. Definite clauses only, giving Prolog and every rule engine in Rule-Based Systems and Expert Systems; or a decidable fragment, as description logics do. The full logic is used where a person can supervise the search.
Writing English in first-order logic
A paper will ask for translations. The pattern to follow is: identify the objects, the predicates, then the quantifier, then apply the two idioms above.
| English | First-order logic |
|---|---|
| Asha attended | Attended(Asha) |
| Every student attended | for all s, Student(s) implies Attended(s) |
| Some student did not attend | exists s, Student(s) and not Attended(s) |
| No student failed | for all s, Student(s) implies not Failed(s) |
| Only students attended | for all s, Attended(s) implies Student(s) |
| Every student passed at least one paper | for all s, Student(s) implies (exists p, Paper(p) and Passed(s, p)) |
| There is a paper every student passed | exists p, Paper(p) and (for all s, Student(s) implies Passed(s, p)) |
First-Order Logic
The last two are the nesting pair again, in the form a paper sets it. And note row five: "only students attended" reverses the implication, which is a different sentence from row two and a favourite question.
Distinctions
| Function | Predicate | |
|---|---|---|
| Returns | an object | a truth value |
| Is a | term | sentence, when applied |
| Example | Mother(Asha) | IsMotherOf(Rekha, Asha) |
| Test | fits after "the" | can be true or false |
for all | exists | |
|---|---|---|
| Read as | for all, for every | there exists, for some |
| Pairs with | implies | and |
| True when | the body holds of every object | of at least one |
| Its negation is | exists of the negated body | for all of the negated body |
| Propositional logic | First-order logic | |
|---|---|---|
| Talks about | whole statements | objects, relations, functions |
| Can generalise | no | yes, with quantifiers |
| Models | 2 to the power n, finite | arbitrarily many, domain may be infinite |
| Entailment | decidable, co-NP-complete | semi-decidable |
What it does not mean
A function symbol is not a predicate. Mother(Asha) names a person and has no truth value.
for all with and is not a harmless variant. for all s, Student(s) and Eligible(s) claims everything in the universe is an eligible student.
exists with implies is not a harmless variant either. It is satisfied by any object that is not a student, so it claims almost nothing.
Swapping quantifiers is not safe. for all x, exists y and exists y, for all x are different sentences, and the second is stronger.
"Not all" is not "none". not (for all s, Passed(s)) is exists s, not Passed(s): one failure suffices.
Two different names do not denote two different objects. Distinctness has to be asserted with equality.
First-order logic is not decidable. It is semi-decidable: a proof will be found if one exists, and a non-entailed query may never terminate.
Quick revision
- Terms denote objects: constants, variables, function terms. Predicates denote relations. An atomic sentence is a predicate applied to terms.
- A function returns an object, a predicate returns a truth value.
Mother(Asha)againstIsMotherOf(Rekha, Asha). for allpairs withimplies;existspairs withand. The other pairings say things you did not mean.- Order of unlike quantifiers matters:
for all x, exists y, Loves(x, y)is everybody loves somebody;exists y, for all x, Loves(x, y)is one person loved by all, which is stronger. - Duals:
for all x, P(x)isnot (exists x, not P(x)), and conversely. So "not all passed" is "at least one failed", not "none passed". - A model is a non-empty domain plus an interpretation of every constant, predicate and function. The domain may be infinite.
- Equality is built in, and lets uniqueness and distinctness be said. Two names may denote one object unless stated otherwise.
- First-order entailment is semi-decidable: a proof is found if one exists; a non-entailed query may not terminate. Practical systems restrict the language to definite clauses or to a decidable fragment.
First-Order Logic
Test yourself
1. Name the four kinds of symbol first-order logic adds, and say what each denotes. Constant symbols denote particular objects; variables denote unspecified objects; function symbols denote mappings from objects to objects and build terms; predicate symbols denote relations and build atomic sentences.
2. Distinguish a function from a predicate with an example. A function applied to terms gives a term, which names an object and has no truth value, for example Mother(Asha). A predicate applied to terms gives a sentence, which is true or false, for example IsMotherOf(Rekha, Asha).
3. Write "every student who attended is eligible" and explain why the connective must be an implication. for all s, Student(s) and Attended(s) implies Eligible(s). With a conjunction instead, the sentence would assert of every object in the universe that it is a student, that it attended and that it is eligible, which is not the claim.
4. Write "some student is eligible" and explain why the connective must be a conjunction. exists s, Student(s) and Eligible(s). With an implication, the sentence would be satisfied by any object that is not a student, since an implication with a false premise is true, so it would assert almost nothing.
5. Distinguish for all x, exists y, Loves(x, y) from exists y, for all x, Loves(x, y). The first says everyone loves someone, and the person loved may differ from lover to lover. The second says there is one particular individual whom everyone loves. The second implies the first and the first does not imply the second.
6. State the relation between the two quantifiers and use it on "not all students passed". for all x, P(x) is equivalent to not (exists x, not P(x)), and exists x, P(x) to not (for all x, not P(x)). So "not all students passed" is not (for all s, Passed(s)), which is exists s, not Passed(s): at least one student failed, which is quite different from no student passing.
7. Compare the decidability of propositional and first-order entailment, and say what practical systems do about it. Propositional entailment is decidable, though co-NP-complete. First-order entailment is only semi-decidable: a proof will be found when one exists, but a procedure need not terminate when the query is not entailed. Practical systems therefore restrict the language, most often to definite clauses, which is what Prolog and rule engines do.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.