1.1 First-Order Logic

Vocabularies

Prolog Exercise:

First-Order Models
First-Order Languages (Note the plural!)

Syntax
The sentence definition

The Satisfaction Definition

Exercises

Function Symbols, Equality, and Sorted First-Order Logic

Function Symbols
Equality
Sorted first-order logic
Question: some analogies made in the text:

1.2 Three Inference Tasks

The Querying Task
The Consistency Checking Task
The Informativity Checking Task
Exercise
Relating consistency and informativity

1.1 First-Order Logic

Vocabularies

First, the vocabulary tells us what we’re going to be talking about:
- individuals: Mia …; 2-place relations: love, hate, …; 1-place relation / property: robber, …
Second, the vocabulary also tells us how we are going to talk about these things: MIA as a symbol for Mia, LOVE as a symbol for the love relation,…

Describe the given vocabulary using the right terminology(constants, relation, property, arity).

{ (LOVE,2),
(CUSTOMER,1),
(ROBBER,1),
(MIA,0),
(VINCENT,0),
(HONEY-BUNNY,0),
(YOLANDA,0) }.

Prolog Exercise:

Exercise 1.1.2 Devise a simple Prolog notation for representing vocabularies (for example, use Prolog lists in place of the curly-brackets and ordered pairs). Write a predicate is_vocab/1 which checks that something written in your notation really is a first-order vocabulary. For example, it should check that each symbol is associated with a number giving its arity, and that no symbol is used in two different ways.

Hint 1: test your predicate on one of the following lines, depending on the vocabulary notation you have chosen.

Hint 2: you may use integer/1, atom/1, member/2 and not/1

% Prolog representation of a vocabulary (1)
is_vocab([[love,2], [hate,2], [customer,1], [vincent,0], [honey_bunny,0]]).

% Prolog representation of a vocabulary (2)
is_vocab([(love,2), (hate,2), (customer,1), (vincent,0), (honey_bunny,0)]).

% Prolog representation of a vocabulary (3)
is_vocab([relation(love,2), relation(robber,1), constant(vincent), constant(mia)]).

% Prolog representation of a vocabulary (4)
is_vocab([relation(love,2), relation(sad,1), constant(butch,0), constant(mia,0)]).

First-Order Models

A model is an ordered pair $(D,F)$ with domain $D$ and interpretation function $F$ .

Describe the model $F$ .

D3 = { d1 , d2, d3, d4, d5}

F3(MIA) = d2     
F3(HONEY-BUNNY) = d1     
F3(VINCENT) = d4     
F3(YOLANDA) = d1     
F3(CUSTOMER) = {d1,d2,d4}     
F3(ROBBER) = {d3,d5}     
F3(LOVE) = {(d3,d4)}.

Exercise 1.1.4 Consider the following situation: There are four blocks. Two of the blocks are cubical, and two are pyramid shaped. The cubical blocks are small and red. The larger of the two pyramids is green, the smaller is yellow. Three of the blocks are sitting directly on the table, but the small pyramid is sitting on a cube. Devise a suitable vocabulary and present this situation as a model.

First-Order Languages (Note the plural!)

A first-order language over a vocabulary uses the following ingredients:

All the symbols in the vocabulary. (non-logical symbols)
A countably infinite collection of variables x, y, z, w, …
The boolean connectives $\neg$ , (negation), $\wedge$ (conjunction), $\vee$ (disjunction), and $\rightarrow$ (implication).
The quantifiers $\forall$ (the universal quantifier) and $\exists$ (the existential quantifier).
The round brackets ) and ( and the comma.

Some terminology:

term: any constant or any variable
atomic formula: If R is a relation symbol of arity n, and $\tau_1, \ldots, \tau_n$ are terms, then $R(\tau_1, \ldots, \tau_n)$ is an atomic formula.

Syntax

Defintion of well formed formulas (wffs):

All atomic formulas are wffs.

If $\phi$ and $\psi$ are wffs then so are $\neg \phi, (\phi \wedge \psi), (\phi \vee \psi), (\phi \rightarrow \psi)$ .

If $\phi$ is a wff, and x is $a$ variable, then both $\exists x \phi$ and $\forall x \phi$ are wffs. (We call $\phi$ the matrix of such wffs.)

Nothing else is a wff.

Klammern werden wie üblich nach folgender Konvention (Päzedenzordnung) weggelassen:

Die Quantoren $\forall$ und $\exists$ und die Negation $\neg$ haben eine höhere Präzedenz als die Konjunktion $\wedge$ und die Disjunktion $\vee$ , das heißt $\neg$ , $\forall$ , $\exists$ bindet stärker als $\wedge$ oder $\vee$ .
$\wedge$ und $\vee$ haben Präzedenz über dem Konditional $\rightarrow$ .

Zusätzlich lassen wir die äußeren Klammern weg und die Klammern in einer mehrgliedrigen Konjunktion oder Disjunktion (Assoziativitätsgesetz).

Beispiel: Statt $((a \vee b) \rightarrow c)$ schreiben wir auch $a \vee b \rightarrow c$ . Und statt $((a\vee b) \vee c)$ schreiben wir auch $a \vee b \vee c$ .

Vorsicht: bei den Quantoren gibt es unterschiedliche Konventionen. Hier im Buch und somit auch im Kurs wird den Quantoren die höchste Präzedenz und somit die engste Bindung zugeordnet. Sprich, $\exists x dog(x) \wedge bark(x)$ ist äquivalent zu $(\exists x dog(x)) \wedge bark(x)$ und nicht zu $\exists x (dog(x) \wedge bark(x))$ .

free/bound variables:

Any occurrence of any variable is free in any atomic formula.

If an occurrence of any variable is free in $\phi$ or in $\psi$ , then that same occurrence is free in $\neg\phi$ , $(\phi \wedge \psi)$ , $(\phi \vee \psi)$ , and $(\phi \rightarrow \psi)$ .

If an occurrence of a variable $x$ is free in $\phi$ , then that occurrence is free in $\forall y \phi$ and $\exists y \phi$ (for any variable y distinct from x). However, no occurrence of x is free in $\forall x \phi$ and $\exists x \phi$ .

The only free variables in a formula $\phi$ are those whose freeness follows from the preceding clauses. Any variable in a formula that is not free is said to be bound.

The sentence definition

A formula that contains no occurrences of free variables is called a sentence of first-order logic.

This is not a sentence: $\forall y (LOVE(x,y) \rightarrow ROBBER(y))$ .

But this is: $\exists w \forall y (LOVE(w,y) \rightarrow ROBBER(y))$ .

Exercise 1.1.5 Represent the following English sentences in first-order logic:

Everyone is happy, or Butch and Pumpkin are fighting, or Vincent has a weird experience.
Some cars are damaged and there are bullet holes in some of the walls.
Everybody in the basement is wearing a leather jacket or a dog collar.
Either Butch and Pumpkin are fighting or Vincent has a weird experience

Exercise 1.1.8 (optional) Give an inductive definition of subformulahood. That is, for each kind of formula in the language (atomic, boolean, and quantified) specify exactly what its subformulas are. The subformulas of a formula $\phi$ are $\phi$ itself and all the formulas used to build $\phi$ .

The Satisfaction Definition

Ziel: die Wahrheit von Sätzen in einem Modell zu definieren.
Frage: Warum lässt sich nicht so ohne weiteres induktiv (in terms of subformulas) definieren, wann ein Satz in einem Modell wahr ist?
satisfaction $\subseteq$ formulas $\times$ models $\times$ assignments

Given a model M = (D, F), an assignment of values to variables in M (or more simply, an assignment in M) is a function g from the set of variables to D.

Let M = (D, F) be a model, let g be an assignment in M, and let $\tau$ be a term. Then the interpretation of $\tau$ with respect to M and g is F( $\tau$ ) if $\tau$ is a constant, and g( $\tau$ ) if $\tau$ is a variable. We denote the interpretation of $\tau$ by $I^g_F(\tau)$ .

Let g be an assignment in some model M, and let x be a variable. If g’ is also an assignment in M, and for all variables y distinct from x we have that g’(y)= g(y), then we say that g’ is an x-variant of g.

Let $\phi$ be a formula, let M = (D, F) be a model, and let g be an assignment in M. Then the relation $M,g \models \phi$ ( $\phi$ is satisfied in M with respect to the assignment g) is defined inductively as follows:

A sentence $\phi$ is true in a model M if and only if for any assignment g of values to variables in M, we have that $M, g \models \phi$ . If $\phi$ is true in M we write $M \models \phi$ .

Exercises

Exercise 1.1.10 Consider the model with $D = \{d1,d2,d3,d4,d5\}$ and the following interpretation function $F$ :

    F(MIA) = d2
    F(HONEY-BUNNY) = d1
    F(VINCENT) = d4 
    F(YOLANDA) = d1 
    F(CUSTOMER) = {d1,d2,d3}
    F(ROBBER) = {d3,d5}
    F(LOVE) = {(d3,d4)}

Are the following sentences true or false in this model?

$\exists x LOVE(x, VINCENT)$
$\forall x (ROBBER(x) \rightarrow \neg CUSTOMER(x))$
$\exists x \exists y (ROBBER(x) \wedge \neg ROBBER(y) \wedge LOVE(x,y))$

Exercise 1.1.11 (optional) Give a model that makes all the following formulas true:

$HAS\_GUN(VINCENT)$
$\forall x (HAS\_GUN(x) \rightarrow AGGRESSIVE(x))$
$HAS\_MOTORBIKE(BUTCH)$
$\forall y (HAS\_MOTORBIKE(y) \lor AGGRESSIVE(y))$

Exercise 1.1.15 (optional) We claimed that when evaluating $sentences$ , it doesn’t matter which variable assignment we start with. Formally, we are claiming that given any $sentence$ $\phi$ and any model $M$ (of the same vocabulary), and any variable assignments $g$ and $g'$ in $M$ , then $M,g \models \phi$ iff $M, g' \models \phi$ . We want reader to do two things. First, show that the claim is $false$ if $\phi$ is not a sentence but a formula containing free variables. Second, show that the claim is $true$ if $\phi$ is a $sentence$ .

Function Symbols, Equality, and Sorted First-Order Logic

Function Symbols

An example of a function symbol is a 1-place function symbol FATHER which expresses fatherhood:

$FATHER(FATHER(FATHER(VINCENT)))$

All constants and variables are terms.

If $f$ is a function symbol of arity n, and $\tau_1, \ldots \tau_n$ are terms, then $f(\tau_1, \ldots \tau_n)$ is also a term.

Nothing else is a term.

A term is said to be closed if and only if it contains no variables.

This is a closed term: $FATHER(MIA)$

if $\tau$ is a term of the form $f(\tau_1, \ldots \tau_n)$ , then we define $I^g_F(\tau)$ to be $F(f)(I^g_F\tau_1, \ldots I^g_F\tau_n)$

Equality

$=$ is a two-place relational symbol with fixed interpretation (logical symbol): For any model $M$ , any assignment $g$ in $M$ , and any terms $\tau_1$ and $\tau_2$ : $M, g \models \tau_1= \tau_2 \text{ iff } I^g_F\tau_1 = I^g_F\tau_2$

Exercise 1.1.18 There is a famous analysis, due to the philosopher Bertrand Russell, of the meaning of the determiner the in sentences like The robber is screaming. Russell claims that this sentence would be true in some situation if (a) there was at least one robber in the situation, (b) there was at most one robber in the situation, and (c) that robber was screaming. Write down a first-order sentence which expresses this analysis of The robber is screaming. Note: you will have to use the equality symbol.

Sorted first-order logic

The domain can be sorted into subclasses (animate/inanimate ). The interpretation of a sorted variable is restricted to its corresponding subclass.

Question: some analogies made in the text:

models $\approx$ situations
formulas $\approx$ descriptions
free variables $\approx$ pronouns
terms $\approx$ the noun phrases of FO-languages
assignment of values to variables $\approx$ (highly idealised) mathematical model of context

Haben Sie noch mehr entdeckt? Können Sie die Vergleiche nachvollziehen?
Die Autoren betonen, dass aus Sicht der Linguistik satisfaction ein wichtiger Begriff ist als truth, warum?

1.2 Three Inference Tasks

The Querying Task

The Querying Task: Given a model $M$ and a first-order formula $\phi$ , is there an assignment $g$ such that $\phi$ satisfied in $M$ with respect to $g$ ?

The Consistency Checking Task

pretheoretic concept:

consistency $\approx$ makes sense
inconsistency $\approx$ does not make sense

Example: Mia smokes and Mia does not smoke.

A first-order formula is called satisfiable if it is satisfied in at least one model. A formula that is not satisfiable in any model is called unsatisfiable.

A finite set of formulas ${\phi_1,\ldots \phi_n}$ is satisfiable if $\phi_1 \wedge \ldots \wedge \phi_n$ is satisfiable.

Note that satisfiability (and unsatisfiability) are model-theoretic or (as it is sometimes put) semantic concepts.

That is, both concepts are defined using the notion of satisfaction in a model, and nothing else. Furthermore, note that satisfiability (and unsatisfiability) are mathematically precise concepts: we know exactly what first-order languages and first-order models are, and we know exactly what it means when we claim that a formula is satisfied in a model.

The Consistency Checking Task: Given a first-order formula $\phi$ , is $\phi$ consistent (that is: satisfiable) or inconsistent (that is: unsatisfiable)?

Consistency checking for first-order logic is undecidable
But, from a proof-theoretic (or syntactic, i.e. symbol manipulation) perspective rather than a model-theoretic perspective partial solution to the consistency checking problem are possible.

The Informativity Checking Task

informative = invalid, for example: $robber(x)$
uninformative (=trivial) = valid, for example: ( $robber(x) \lor \neg robber(x)$ )

A valid formula is a formula that is satisfied in all models (of the appropriate vocabulary) given any variable assignment. If $\phi$ is a valid formula we write $\models \phi$ . A formula that is not valid is called invalid ( $\not\models \phi$ ).

Suppose $\phi_1, \ldots , \phi_n$ , and $\psi$ are a finite collection of first-order formulas. Then we say that the argument with premises $\phi_1, \ldots , \phi_n$ and conclusion $\psi$ is a valid argument if and only if whenever all the premises are satisfied in some model, using some variable assignment, then the conclusion is satisfied in the same model using the same variable assignment. The notation $\phi_1, \ldots , \phi_n \models \psi$ means that the argument with premises $\phi_1, \ldots , \phi_n$ and conclusion $\psi$ is valid.

Alternative terminology:

$\psi$ is a valid inference from the premises $\phi_1, \ldots , \phi_n$
$\psi$ is a logical consequence of $\phi_1, \ldots , \phi_n$
$\psi$ is a semantic consequence of $\phi_1, \ldots , \phi_n$

The Informativity Checking Task: Given a first-order formula $\phi$ , is $\phi$ informative (that is: invalid) or uninformative (that is: valid)?

The informativity checking task is undecidable.
But again, partial solution from a proof-theoretic perspective.

Exercise

Exercise 1.2.7 The following terminology is useful: if $\phi_1, \ldots, \phi_n \models \neg \psi$ , then we shall say that $\psi$ is inconsistent with respect to $\phi_1, \ldots, \phi_n$ . Show that $\psi$ is inconsistent with respect to $\phi_1, \ldots, \phi_n$ , if and only if $\neg \psi$ is uninformative with respect to $\phi_1, \ldots, \phi_n$ ,

Exercise 1.2.2 The Semantic Decuction Theorem for first-order logic says, that $\phi_1, \ldots , \phi_n \models \psi$ if and only if $\models(\phi_1 \wedge \ldots \wedge \phi_n ) \rightarrow \psi$ (That is, we can lump together the premises using $\wedge$ , and then use $\rightarrow$ to state that this information implies the conclusion). Prove the Semantic Deduction Theorem.

Relating consistency and informativity

Consistency and informativity are related concepts:

$\phi$ is consistent (that is, satisfiable) if and only if $\neg\phi$ is informative (that is, invalid).
$\phi$ is inconsistent (that is, unsatisfiable) if and only if $\neg\phi$ is uninformative (that is, valid).
$\phi$ is informative (that is, invalid) if and only if $\neg\phi$ is consistent (that is, satisfiable).
$\phi$ is uninformative (that is, valid) if and only if $\neg\phi$ is inconsistent (that is, unsatisfiable).

Blackburn and Bos: Representation and Inference of Natural Language

Chapter 1: First-Order Logic

Wiebke Petersen