First Order Logic

Question 1

What are properties of Expressive Logic?

Answer 1

It is declarative: Separation between knowledge and control
It is expressive: Ability to handle unknown information or partially-known information
It is compositional: The meaning of a sentence is a function of the meaning of its parts

Question 2

What are the shortcomings of propositional logic?

Answer 2

Verbosity: Stating simple facts often requires listing a large number of propositions.
Low expressiveness: Many facts cannot be expressed by propositional logic in a meaningful way.

Question 3

What is a first-order interpretation?

Answer 3

A tuple:
(D, R1, R2, …, Rk, f1, …, fl)
- D is a set of elements and is called the domain.
- Each Ri is a relation or predicate defined on D
- Each f is a function defined on D

Question 4

What is a bounded variable?

Answer 4

A variable occuring in a formula if it is within scope of some sub-formula. If a variable is not bounded, then it is called a free variable

Question 5

What is Satisfaction Relation?

Answer 5

Lets have w be a sentence and I be an interpretation. We inductively define the satisfaction relation in such a way that satisfies w, written I |= q, if w is true according to the interpretation I.

Question 6

What is a first-order knowledge base?

Answer 6

A set of first-order sentences in some signature. To define a model of FO-KB, we make the following two assumptions:
1. Closed-world assumption: if any atomic sentence is not to be known or shown to be true, then it is false.
2. Domain-closure assumption: In a model of the KB, all elements fo the domain appear as ground terms that can be expressed using constants.

Question 7

What is an axiom?

Answer 7

The basic factual information from which useful conclusions can be derived.

Question 8

What is a theorem?

Answer 8

Theorems are factual information derived from the axioms.

Question 9

What is the inference problem?

Answer 9

It takes as input a KB and a formula w, and outputs whether KB |= w.

Question 10

What is grounding?

Answer 10

1. Instantiate variable with constants
2. This turns a sentence into a proposition
3. Then use methods for propositional logic to carry out inference.

Question 11

What is lifting?

Answer 11

1. Inference is directly applied to first-order logic formulas
2. Generalise propositional methods to first-order logic
3. Unification is an important task here.

Question 12

What is the aim of grounding?

Answer 12

To reduce first-order logic inference task to propositional logic inference task.

Question 13

What is the method of grounding?

Answer 13

Turn first-order logic sentences into equivalent propositions.

Question 14

What is the terminology of grounding?

Answer 14

A substitution is of the form x/t where x is a variable and t is a term.
For a set S of substitutions and formula x, we use subset to denote the formula obtained by applying substitutions in S and w.

Question 15

What are the observations of grounding?

Answer 15

A sentence without any quantifier is essentially a proposition.
We need existential sentences of the form Ex: w(x) and universal sentences of the form Vx:w(x)

Question 16

What is existential instantiation?

Answer 16

From Ex: w(x), derive w(c), where c is a new constant symbol, called the Skolem constant and c is not the original signature.

Question 17

What is universal instantiation?

Answer 17

From Vx: w(x) derive w(t) where t is any ground term.
Applying universal instantiation produces a sentence that is only an instance of the universal sentence.

Question 18

What is Herbrand’s theorem?

Answer 18

If a sentence w is entailed by a first-order KB, then is is entailed by a finite subset of KB.
We may thus perform inference by propositionalisation:
1. Apply grounding rules to introduce propositions to KB.
2. Apply proposition logic inference
3. If a proof to w is not found, repeat to generate more propositions.

Question 19

What is the undecidability theorem?

Answer 19

First-order inference is undecidable.
- If the search finds a proof, then the sentence w is indeed true
- But no algorithm exists that decides whether w is true or not.

Question 20

What are the shortcomings of propositionalization?

Answer 20

It generates too many sentences, resulting in a very large propositional knowledge base for inference.
We need to only generate relevant sentences. This will allow us to do inference on first-order sentences.

Question 21

How does a unification algorithm work?

Answer 21

It takes two sentences w1 and w2 and returns a substitution S, such that:
Subset(S, w1) = Subset(S, w2)