Eerste Orde logica

Introductie

Eerste orde logica is een uitbreiding van de predicaten logica. Je kunt er meer soorten zinnen in kwijt.

Bij propsitionele logica spreken we over relaties tussen proposities (uitspraken die in hun geheel waar of onwaar zijn), we spreken over de relaties tussen de verschillende relaties tussen de proposities en we hebben diverse mechanismen om logische conclusies te trekken op basis van die relaties tussen proposities.

Bijvoorbeeld:
zin p: Jack kent Jille
zin q: Jill kent Jack

premisse: Jack kent Jill (p)
premisse: als Jack kent Jill dan Jill kent Jack(p -> q)
Implication elimation: Jill kent Jack (q)

Stel nu dat we meer generieke uitspraken willen doen over de wereld. Bijvoorbeeld: "Als een persoon, een ander persoon kent dan kent de tweede persoon de eerste ook" en we weten dat Jack, Jill kent.

Eerste orde Logica is een uitbreding van predicaten logica om dit soort zinnen uit te drukken in een formele taal en op basis daarvan logsche conclusies te maken.

Syntax

 In Relational Logic, there are no propositional constants; instead we have object constants, relation constants(predicate), and variables en Functies.

Let op functies en relaties lijken wat vorm erg op elkaar p(a,a) en q(a,b), maar een relatie geeft waar of niet waar en een functes geeft op basis van de parameters een objectconstante terug.

There are three types of sentences in Relational Logic, viz. relational sentences (the analog of propositions in Propositional Logic), logical sentences (analogous to the logical sentences in Propositional Logic), and quantified sentences

 

Negation:		(¬p(a))
Conjunction:		(p(a) ∧ q(b, c))
Disjunction:		(p(a) ∨ q(b, c))
Implication:		(p(a) ⇒ q(b, c))
Biconditional:		(p(a) ⇔ q(b, c))

A universally quantified sentence is used to assert that all objects have a certain property.

(∀x.(p(x) ⇒ q(x,x)))

An existentially quantified sentence is used to assert that some object has a certain property.

(∃x.(p(x) ∧ q(x,x)))

 Note that quantified sentences can be nested within other sentences.

∀x.p(x) ⇒ q(x)     en ∀x.(p(x) ⇒ q(x)) zijn verschillend
 
Precedence:  In Relational Logic, the precedence relations of the logical operators are the same as in Propositional Logic, and quantifiers have higher precedence than logical operators.


Eigenschappen van gekwantificeerde zinnnen:(hebben we strtaks nodig bij vaststellen demantiek)

An expression in Relational Logic is ground if and only if it contains no variables. For example, the sentence p(a) is ground, whereas the sentence ∀x.p(x) is not.

An occurrence of a variable is free if and only if it is not in the scope of a quantifier of that variable

For example, y is free and x is bound in the following sentence.
∃x.q(x,y)

A sentence is open if and only if it has free variables.

Semantiek

The Herbrand base for a vocabulary is the set of all ground relational sentences that can be formed from the constants of the language. Said another way, it is the set of all sentences of the form r(t₁,...,t_n), where r is an n-ary relation constant and t₁, ... , t_n are object constants.

For a vocabulary with object constants a and b and relation constants p and q where p has arity 1 and q has arity 2, the Herbrand base is shown below.
{p(a), p(b), q(a,a), q(a,b), q(b,a), q(b,b)}

A truth assignment for a Relational Logic language is a function that maps each ground relational sentence in the Herbrand base to a truth value.

p(a)	→	1
p(b)	→	0
q(a,a)	→	1
q(a,b)	→	0
q(b,a)	→	1
q(b,b)	→	0

Wanneer de Herbrand-base is vastgesteld kun je complexere zinnen maken met de logische connectoren. Net las bij Propositielogica:

Alleen waar P en Q staat, kun je vervangen door p(a) en p(b)

omgaan met kwantifiers

A universally quantified sentence is true for a truth assignment if and only if every instance of the scope of the quantified sentence is true for that assignment.

An existentially quantified sentence is true for a truth assignment if and only if some instance of the scope of the quantified sentence is true for that assignment.


satisfies a sentence with free variables if and only if it satisfies every instance of that sentence. A truth assignment satisfies a set of sentences if and only if it satisfies every sentence in the set.

omgaan met functies

For a vocabulary with a single object constant a and a single unary function constant f and a single unary relation constant r, the Herbrand base consists of the sentences shown below.
{r(a), r(f(a)), r(f(f(a))), ...}

hum: probleem oneindige bas -> hoe gaan we waarheidstabel maken?

Luckily, things are not always so bad. In some cases, only finitely many elements of the Herbrand base are true. In such cases, we can describe a truth assignment in finite space by writing 

 

 Werken met één zin (die kwantifiers heeft)

Evaluatie
Gegeven eerdere interpratatie van de Herbrand-baswat is de volgende zin true of vals

∀x.(p(x) ⇒ q(x,x))

p(a) ⇒ q(a,a)  
p(b) ⇒ q(b,b)

p(a) ⇒ q(a,a))	→	1
(p(b) ⇒ q(b,b))	→	1

allebei 1 dus

∀x.(p(x) ⇒ q(x,x)) → 1


Bij een existentiele zin minimaal 1 instantie waar, maakt de hele zin waar.
 

Satisfactie

p(a)

	p(b)	q(a)	q(b)	p(a) ∨ p(b)	∀x.(p(x) ⇒ q(x))	∃x.q(x)
1	1	1	1	1	1	1
1	1	1	0	1	0	1
1	1	0	1	1	0	1
1	1	0	0	1	0	0
1	0	1	1	1	1	1
1	0	1	0	1	1	1
1	0	0	1	1	0	1
1	0	0	0	1	0	0
0	1	1	1	1	1	1
0	1	1	0	1	0	1
0	1	0	1	1	1	1
0	1	0	0	1	0	0
0	0	1	1	0	1	1
0	0	1	0	0	1	1
0	0	0	1	0	1	1
0	0	0	0	0	1	0

Looking at the table, we see that there are twelve truth assignments that make the first sentence true, nine that make the second sentence true, twelve that make the third sentence true, and five that make them all true (rows 1, 5, 6, 9, and 11).

omgaan met functies:
The good news is that, even though evaluation and satisfaction are not directly computable, there are effective procedures for indirectly determining validity, contingency, unsatisfiability, logical entailment, and so forth that work in many cases even when our usual direct methods fail.



Werken met 2 of meer zinnen (entailment)

nader uit te werken