Chapter 1: First-Order Logic

First-Order Logic (BB: 1.1)

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),
    (HATE,2),
    (CUSTOMER,1),
    (ROBBER,1),
    (MIA,0),
    (VINCENT,0),
    (HONEY-BUNNY,0),
}.

Prolog Exercises:

Exercise 1.1.1 Consider the following situation: Vincent is relaxed. The gun rests on the back of the seat, pointing at Marvin. Jules is driving. Marvin is tense. Devise a vocabulary suitable for talking about this situation. Give the vocabulary in the set-theoretic notation used in the text.

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.

First-Order Models

A model $M$ is an ordered pair $(D,F)$ with a non-empty domain $D$ and interpretation function $F$.

Describe the model $M$.

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.

Repräsentation von Modellen in Prolog

Wir wählen folgendes Repräsentationsformat für Modelle in Prolog:

% model(Domain,InterpretationFunctionF).
model([d1,d2,d3,d4,d5],
   [f(0,jules,d1),
   f(0,vincent,d2),
   f(0,pumpkin,d3),
   f(0,honey_bunny,d4),
   f(0,yolanda,d5),
   f(1,customer,[d1,d2]),
   f(1,robber,[d3,d4]),
   f(2,love,[(d3,d4)])]).

Übung: Übertrage das folgende Modell in die Prolognotation:

F2(MIA) = d2 
F2(HONEY-BUNNY) = d1 
F2(VINCENT) = d4 
F2(YOLANDA) = d3 
F2(CUSTOMER) = {d1,d2,d4} 
F2(RODBER) = {d3}
F2(LOVE) = {}.

Programmieraufgabe: Schreibe ein Prädikat isModel/1, das überprüft, ob ein Modell ein Modell in Prolognotation ist. Als Argument erhält das Prädikat ein Modell in der obigen Notation model/2.

First-Order Languages (Note the plural!)

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

1. All the symbols in the vocabulary. (non-logical symbols)
2. A countably infinite collection of variables x, y, z, w, …
3. The boolean connectives $\neg$, (negation), $\wedge$ (conjunction), $\vee$ (disjunction), and $\rightarrow$ (implication).
4. The quantifiers $\forall$ (the universal quantifier) and $\exists$ (the existential quantifier).
5. 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):

1. All atomic formulas are wffs.

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

3. 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.)

4. Nothing else is a wff.

Klammern werden wie üblich nach folgender Konvention (Prä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:

1. Any occurrence of any variable is free in any atomic formula.
2. 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)$.
3. 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$.
4. 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:

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

Während der Sitzung: Welche der Sätze du bearbeiten sollst, errechnest du über die folgende Rechnung:
q= ‚Quersumme deines Geburstages‘
Aufgabennummer = 1+ (q mod 4)
(Beispiel: 4.6.1999, q=4+6+1+9+9+9=38, Aufgabennummer = 1+ (38 mod 4) = 1+2 = 3)
Poste deine Lösung dann hier im Etherpad

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$.

Repräsentation von Formeln in Prolog

Atomare Formeln stellen wir wie oben als Prologterme dar. Eine zweistellige Relation hat zum Beispiel die Form love(mia, vincent). Variablen werden durch Prologvariablen repräsentiert, also love(mia, X).

Die boolschen Konnektoren ∧, ∨,→ und ¬ werden durch die Terme
and/2, or/2, imp/2 und not/1 dargestellt. Statt einer Infixnotation wird also die Präfixnotation verwendet, d.h. der Konnektor steht vor seinen Argumenten.

Die Quantoren ∀ und ∃ erhalten die Darstellung all/2 und some/2, wobei das erste Argument eine Prologvariable ist und das zweite Argument eine Formel.
So wird die Formel ∀x(dog(x)→bark(x)) dargestellt als all(X, imp(dog(X),bark(X)).

% Übertrage die Beispiele in Pädikatenlogik
 some(X,some(Y,love(X,Y))).
 not(all(X,all(Y,love(X,Y)))).
 all(X,or(robber(X),customer(X))).

Übertrage die folgenden Formeln in die Prologrepräsentation:

• ∃x robber(x)
• ∀x ∃y ((robber(x) ∧ customer(y)) → love(x,y))
• ∀x (¬robber(x) ∨ customer(x))

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

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?
∃xLOVE(x,VINCENT)
∀x(ROBBER(x)→¬CUSTOMER(x))
∃x∃y(ROBBER(x)∧¬ROBBER(y)∧LOVE(x,y))

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

1. $HAS\_GUN(VINCENT)$
2. $\forall x (HAS\_GUN(x) \rightarrow AGGRESSIVE(x))$
3. $HAS\_MOTORBIKE(BUTCH)$
4. $\forall y (HAS\_MOTORBIKE(y) \lor  AGGRESSIVE(y))$

Exercise 1.1.15 (optional) We claimed that when evaluating sentencessentences, 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

Mithilfe von Funktionssymbolen können komplexe Terme konstruiert werden, die Definition von Termen wird erweitert.

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

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

1. All constants and variables are terms.
2. 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.
3. 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.

In Kapitel 6 werden wir auf „sorted first-order logics“ zurückkommen.

Question: some analogies made in the text:

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

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

Three Inference Tasks (BB: 1.2)

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 ≈ makes sense
• inconsistency ≈ 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:

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