Propositional Logic, Predicate Logic, FOPL, Interpretation, Quantification, Horn Clauses

Propositional Logic

In propositional logic the atomic formulas are propositions that are assertions such as:

• A := "'Aristotle is dead"'.
• B := "‘Hildesheim is on the Rhine"’.
• C := "‘Logic is fun"’.

Atomic formulas are denoted by capital letters A, B, C, etc. Each atomic formula is assigned a truth value: true (1) or false (0). (In fuzzy logic truth values can be degrees between 0 and 1.)

Hedman states that "‘Propositional logic is not the study of truth but of the relationship between the truth of one statement and that of another"’.

The natural language words may have slightly different meanings.

For Example A ∧ B and B ∧ A should always have the same meaning. But the sentences such as:

She became sick and she went to the doctor.
and
She went to the doctor and she became sick.
have different meanings.

Predicate logic

The logic in which knowledge is represented in the form of predicates is called predicate logic. A predicate is a word which gives the relation of arguments passed within it. Predicates are the relations that bind different objects together.

FOPL

It stands for First Order Predicate Logic. FOPL is considered to be the simplest form of predicates which gives us the ability to quantify over an object. In FOPL the statements from the natural language like English are translated into the symbolic structure which is composed of relations, variables, quantifiers and logical connectives.

Quantifier

Once we have a logic that allows objects it is only natural to express properties of an entire collection of objects. Instead of enumerating the objects by name the quantifiers allow doing this. FOPL has two quantifiers and they are:

• Universal Quantifier
• Existential Quantifier.

Universal Quantifier:

The universal quantification of a predicate P(x) is the proposition. “P(x) is true for all the values of x in the universe of discourse”. We use the notation ∀xP(x) which can be read as “for all x”. If the universe of discourse is finite say {n1, n2, . . . , nk} then the universal quantifier is simply the conjunction of all the elements:
∀xP(x) ⇐⇒ P(n1) ∧ P(n2) ∧ · · · ∧ P(nk).

For example:

• Let P(x) be the predicates and “x must take a discrete mathematics course” and let Q(x) be the predicate and “x is a computer science student”.
• The universe of discourse for both P(x) and Q(x) is all UNL students.
• Express the statement “Every computer science student must take a discrete mathematics course”.
  ∀x(Q(x) → P(x)).
• Express the statement “Everybody must take a discrete mathematics course or be a computer science student”.

Existential Quantifier

The existential quantification of a predicate P(x) is the proposition. “There exists an x in the universe of discourse such that P(x) is true”. We use the notation ∃xP(x) which can be read “there exists an x”. Again if the universe of discourse is finite such as {n1, n2, . . . , nk} then the existential quantifier is simply the disjunction of all elements:
∃xP(x) ⇐⇒ P(n1) ∨ P(n2) ∨ · · · ∨ P(nk).

For example:

Express the statement “there exists a real solution to ax2 + bx − c = 0”.

Let P(x) be the statement x = −b± √ b2−4ac 2a where the universe of discourse for x is the set of reals. Note here that a, b, c are all fixed constants.

The statement can thus be expressed as ∃xP(x).

Normal Form in Predicate Logic:

1. Prenex Normal Form (PNF)
2. Clausal Normal Form (CNF)

Prenex Normal Form (PNF):

A first-order formula Q1x1...QnxnA, where Q1, ..., Qn are quantifiers and A is an open formula, is in a prenex form. The quantifier string Q1x1...Qnxn is called the prefix, and the formula A is the matrix of the prenex form. Examples: ∀x∃y(x > 0 → (y > 0 ∧ x = y 2 )) is in prenex form, while ∃x(x = 0) ∧ ∃y(y < 0) and ∀x(x > 0 ∨ ∃y(y > 0 ∧ x = y 2 )) are not in prenex form.

Clausal Normal Form:

It is a form in which all the predicates are in their disjunction. Thus this form is also known as disjunctive normal form.

For example:

∀x: dog(n) → animal (n)
¬ dog (x) Ë… animal (n).

Rules (step) to convert a predicate logic to CNF

1. Eliminate the bidirectional symbols such as→ and ↔.
2. Implication the occurrences of implications such as:
   p(n)⇔ q(n)≡¬ p(x)∨ q(n).
3. Use De-Morgan's rule if applicable as:
   ¬ (p(n) ∧q(n)) ≡ ¬ p(n)∨ ¬q(n).
   ¬ (p(n) ∨q(n)) ≡ ¬ p(n) ∧¬q(n).
4. Eliminate the existential quantifier.
   The case I: If the existential quantifier is alone or inside the universal quantifier then replace all the variables associated with existential quantifier by some arbitrary constant. This process is called constant Skolemization.
   
   Case II:If the existential quantifier is outside the universal quantifier or in between the universal quantifier then replace all the variables associated with existential quantifier by the function of all the variables associated with universal quantifier which is inside the existential quantifier. This process is called function Skolemization.
   ∀x: ∃y: ∀z: ∀k: p(x, y, z) ∧ q(y, z, k) ≡∀x:∀z:∀k: p(x, f(z, k), z)∧ q(f (z, k), z, k).
5. Drop all the universal quantifier.
6. If necessary use distributed rules to distribute the conjunction over disjunction or disjunction over conjunction.
7. Use AND elimination to separate the conjunction of predicates into the separate one.

Horn Clauses

A horn clause is either a definite clause or an integrity constant.That is, a Horn clause has either false or a normal atom as its head.

The integrity constraints allow the system to prove that some conjunction of atoms is false in all of the models of a knowledge base. That is, to prove disjunctions of negations of atoms. Recall that ¬p is the negation of p which is true in an interpretation when p is false in that interpretation and p ∨ q is the disjunction of p and q which is true in an interpretation if p is true or q is true or both are true in the interpretation. The integrity constraint false ← a₁∧... ∧a_k is logically equivalent to ¬a₁∨...∨¬a_k.

A Horn clause knowledge base can simply negations of atoms.

References

1. Elaine Rich, Kevin Knight 1991, "Artificial Intelligence".
2. Nilsson, Nils J. Principles of Artificial Intelligence, Narosa Publishing House New Delhi, 1998.
3. Norvig, Peter & Russel, Stuart Artificial Intelligence: A modern Approach, Prentice Hall, NJ, 1995
4. Patterson, Dan W. Introduction to Artificial Intelligence and Expert Systems, Prentice Hall of India Private Limited New Delhi, 1998.