First-Order Logic

Pros and Cons of Propositional Logic

pros

1. Propositional logic은 declaritive(선언형)이다. 행동에 대한 구문으로 이루어져 있다.

(명령형 프로그램은 알고리즘을 명시하고 목표는 명시하지 않는 데 반해 선언형 프로그램은 목표를 명시하고 알고리즘을 명시하지 않는 것이다.)

2. Propositional logic은 partial/disjunctive/negated information을 허락한다. 

3. Propositional logic은 compositional 하다. B1,1 ∧ P1,2는 B1,1와 P1,2에서 유래 됐다는 것을 의미한다.

4. Propositional logic은 context-independent하다. context에 의존하는 natural language와는 다르다.

 

cons

1. Propositional logic은 굉장히 제한적인 expressive power를 가지고 있다.

---

First-order Logic

Propositional logic은 world가 facts를 포함한다고 가정하는 반면에, first-order logic은 world가

Objects(people, houses, numbers...), Relations(red, round, bogus, prime, bigger than, .. ), Functions(father of, best friend, one more than ..)를 포함한다고 가정한다.

 

FOL : objects with relations between them that hold or do not hold

---

Syntax of FOL: Basic Elements

Constants : KingJohn, 2, UCB, ...

Predicates : Brother, >,...

Functions : Sqrt, LeftLegof, ...

Variables : x, y, a, b, ...

Connectives : ∧, ∨, ¬, ⇒, ⇔

Equality : =

Quantifiers : ∀,∃

---

Atomic Sentences

Atomic sentences = predicate(term1,...,termn) or term1=term2

Term = function(term1,...,termn) or constant or variable

 

ex) Brother(KingJohn,RichardTheLionheart)>(Length(LeftLegOf(Richard)),Length(LeftLegOf(KingJohn)))

 

---

Complex Sentences

Complex sentence는 connective를 사용한 atomic sentence들로 만들어 진다.

Connectives : ∧, ∨, ¬, ⇒, ⇔

ex) Sibling(KingJohn,Richard) ⇒ Sibling(Richard,KingJohn)

      >(1,2)∨≤(1,2)

      >(1,2)∧¬>(1,2)

∀,∃

Universal quantification

∀ < variables > < sentence >

ex) Everyone at Sogang is smart : ∀xAt(s,Sogang)⇒Smart(x)

 

Existential quantification

∃ < variables > < sentence > 

ex) Someone at Sogang is smart : ∃xAt(x, Sogang)⇒Smart(x)

---

Truth in First-order Logic

Sentence는 model의 관점에서 ture이다.

Model은 objects(domain elements)와 symbols의 interpretation을 포함한다.

 

constant symbol -> object in domain D

predicate symbol -> relation

function symbol -> functional relation

 

각각의 arity k의 predicate symbol이 relation { < object1, ... , objectk > }에 map된다.

{ < object1, ... , objectk > } is a set of k-tuples over D^k which are true or, equivalently, a function from D^k to {true,false}.

( arity : the number of arguments that a function can take )

 

각각의 arity k의 function symbol은 D^k의 function 에서 D+1(domain+an invisible object)로 map된다.

 

atomic sentence predicate(term1,...,termn)는 term1,...,termn으로 부터 호출된 object가 predicate에 의해 호출된 relation에 있다면 true이다.

 

term1 = term2 는 term1과 term2가 같은 object에서 호출되었다는 given interpretation 아래에서 참이다.

 

The semantics of sentences formed with logical connectives is identical to that in PL.

---

Models for FOL : Example

 

The intended interpretation

Constant : Richard -> Richard th Lionheart

Constant : John -> King John

Predicate : Brother -> the brotherhood relation 

{ < Richard the Lionheart, King John >,< King John, Richard the Lionheart > }

Predicates : OnHead, Person, King, Crown,...

Function LeftLeg : < Richard the Lionheart > -> Richard's left leg

                                  < King John > -> John's left leg

---

Models for FOL

Entailment가 정의 될 수 있다.

KB vocabulary를 이용해 model을 enumerate할 수 있으나 그 수가 너무 많아서 매우 힘들다.

---

Quantifiers

Quantifier는 enumerating을 하지 않고 objects의 collection의 properties를 표현 할 수 있게 해준다.

Universal : "for all" ∀

Existential : "there exists" ∃

---

Universal Quantification

∀ <variables> <sentence>

 

Everyone at Berkeley is smart : ∀x At(x,Berkeley) ⇒ Smart(x)

 

∀x P is true in a model m iff P is true with x being each possible object in the model.

 

∀ 기호 하나로 Berkeley에 있는 모든 사람을 enumerate할 필요가 없어졌다.

 

일반적으로, ⇒가 ∀의 main connective이다.

∧를 ∀의 main connective로 사용하면 안된다.

∀x At(x,Berkeley)∧Smart(x)라고 하면 "Everyone is at Berkely and everyone is smart"가 되버린다.

---

Existential Quantification

∃ < variables > < sentence > 

 

Someone at Stanford is smart : 

∃x At(x,Stanford)∧Smart(x)

∃x P is true in a model m iff P is true with x being some possible object in the model.

 

일반적으로, ∧가 ∃의 main connective이다.

⇒를 ∃의 main connective로 사용하면 안된다!!

---

Properties of Quantifiers

∀x ∀y = ∀y ∀x

∃x ∃y = ∃y ∃x

하지만

∃x ∀y 와 ∀y ∃x는 다르다.

∃x ∀y Loves(x,y) - "There is a person who loves everyone in the world"

∀y ∃x Loves(x,y) - "Everyone in the world is loved by at least one person"

 

¬∃ = ∀이다. 역도 성립한다.(Quantifier duality)

 

 

 

---

Using FOL

Brothers are siblings : ∀x,y Brother(x,y)⇒Sibling(x,y)

"Sibling" is symmetric : ∀x,y Sibling(x,y)⇔Sibling(x,y)

One's mother is one's female parent :  ∀x,y Mother(x,y)⇔(Female(x)∧Parent(x,y))

A first cousin is a child of a parent's sibling:

∀x,y FirstCousin(x,y)⇔ ∃p,ps Parent(p,x)∧Sibling(ps,p)∧Parent(ps,y)

---

Exactly one 표현 방법

∀x∃y(B(x,y)∧∀z((z≠y)⇒¬B(x,z)))