First order predicate logic
Predicate logic which is also called first-order logic , predicate calculus,
or quantificational logic is a formal system that is one step above
propositional calculus (sometimes called zeroth-order logic). In addition to
declarative propositions, present in propositional calculus, first-order
logic covers predicates and quantification.
Predicate is a propositional function (assertion) that takes on a value of
true(1) or false(0) depending on a variable or of several variables that are
given as an agument. This means that the statement is undetermined until a
specific value is assigned to its arguments. This means that if in
propositional calculus we would have to define a separate atomic sentences
(propositions) in order do describe two separate occurences of same trait:
a = "Bilbo is a hobbit.",
b = "Frodo is a hobbit.".
In case of predicate logic we can define enities and predicates sepratly
ENTITIES
b = "Bilbo"
f = "Frodo"
a = "Aragorn"
PREDICATES
\(\phi(X) = \text{"X is a hobbit"} \)
Then we can simpy reuse that predicate to define our knowledge base
KNOWLEDGE BASE
\(\phi(f) \)
\(\phi(b) \)
The example of PROLOG code that creates this knowledge base looks like that
:
/* ENTITIES */
bilbo.
frodo.
aragorn.
/* ATTRIBUTES */
is_hobbit(bilbo).
is_hobbit(frodo).
Now by running query is_hobbit(X). we will
get list of all entities for which predicate is_hobbit is true. And by
running is_hobbit(aragorn). we will get
answer for question "Is Aragorn a hobbit ?" which in this case will be
false. As you can see in the code snippet above I reffered to defined
predicates as "attributes" this is because predicates can have more than one
argument. When building knowledge bases predicates with simple argument are
called attributes and two argument ones are called relations.
Remember that this is just a convention and there is nothing inherent in
those predicates that would force them to represent aftermentioned concepts.
Now lets see a bit more complex example that will include relation of being
ancestor.
ENTITIES
...
PREDICATES
\(\phi(X) = \text{"X is a hobbit"} \)
\(\theta(X,Y) = \text{"X is a parent of Y"} \)
\(\chi(X,Y) = \text{"X is an ancestor of Y"} \)
KNOWLEDGE BASE
...
/* ENTITIES */
bilbo.
frodo.
aragorn.
bungo.
mungo.
balbo.
/* ATTRIBUTES */
is_hobbit(bilbo).
is_hobbit(frodo).
is_hobbit(bungo).
is_hobbit(mungo).
is_hobbit(balbo).
/* RELATIONS */
is_parent(bungo,bilbo).
is_parent(mungo,bungo).
is_parent(balbo,mungo).
/* INFERENCE RULES */
is_child(X,Y):- is_parent(Y,X).
is_ancestor(X,Y):- is_parent(X,Y).
is_ancestor(X,Y):- is_parent(X,Z), is_ancestor(Z,Y).
As it can be seen the new code contains knowledge about releations of being
parent, being child and being ancestor. So if we run
is_parent(X,bilbo).
we will recieve "bungo" as a result. And if we call
is_ancestor(X,bilbo). the result will be
list ["bungo","mungo","balbo"]. As you can see relations "is_child" and
"is_ancestor" are called inference rules which means that they are not given
explicitly but defined by set of rules.
Quantifiers are operators that specify which entities in the domain satisfy
give formula. The universal quantifier \( \forall \) in the first
order formula $$\forall_x \phi(x)$$ expresses that everything in the domain
satisfies the property denoted by \( \phi \). The
existential quantifier \( \exists \) in the formula $$\exists_x
\phi(x)$$ expresses that there exists something in the domain which
satisfies that property. A formula where a quantifier takes a widest scope
is called a quantified formula. A quantified formula must contain a
bound variable. If an individual variable in a formula does not
appear in a scope of any quantifier bounding it, it is called a
free variable. For example in statement : $$ \forall_x \text{"x is
friend of y"} $$ variable x is bound while y is free variable. It is
possible to embed one quatified formula in another which allows us to create
more complex sentences, for example:
PREDICATES
\(\phi(X) = \text{"X is a human"} \)
\(\theta(X,Y) = \text{"X is a child of Y"} \)
KNOWLEDGE BASE
\( \forall_X \exists_Y (\phi(X) \implies \theta(Y,X)) \)
This statemetnt means that for all X fact of X being human implies that
there exists some Y that are parents of X.