Logic Programming

Chapter 12 - Metaknowledge

12.1 Introduction

One of the interesting features of our language is that it allows us to encode information about information. The trick is to represent sentences as terms in our language and then write sentences about these terms, thereby effectively writing sentences about sentences. There are numerous uses of this technique. In this chapter, we look at two of these - describing the syntax and semantics of other languages within our language and representing Boolean Logic within Logic Programming.

12.2 Natural Language Processing

Pseudo English is a formal language that is intended to approximate the syntax of the English language. One way to define the syntax of Pseudo English is to write grammatical rules in Backus Naur Form (BNF). The rules shown below illustrate this approach for a small subset of Pseudo English. A sentence is a noun phrase followed by a verb phrase. A noun phrase is either a noun or two nouns separated by the word and. A verb phrase is a verb followed by a noun phrase. A noun is either the word mary or the word pat or the word quincy. A verb is either like or likes.

<sentence> ::= <np> <vp>
<np> ::= <noun>
<np> ::= <noun> "and" <noun>
<vp> ::= <verb> <np>
<noun> ::= "mary" | "pat" | "quincy"
<verb> ::= "like" | "likes"

Alternatively, we can use rules to formalize the syntax of Pseudo English. The sentences shown below express the grammar described in the BNF rules above. Here, we are using the app relation to talk about the result of appending words.

sentence(Z) :- np(X) & vp(Y) & app(X,Y,Z)
np(X) :- noun(X)
np(W) :- noun(X) & noun(Y) & app(X,and,Z) & app(Z,Y,W)
vp(Z) :- verb(X) & np(Y) & app(X,Y,Z)

Using these rules, we can test whether a given sequence of words is a syntactically legal sentence in Pseudo English and we can enumerate syntactically legal sentences, like those shown below.

mary likes pat
pat and quincy like mary
mary likes pat and quincy

One weakness of our BNF and the corresponding axiomatization is that there is no concern for agreement in number between subjects and verbs. Hence, with these rules, we can get the following expressions, which are ungrammatical in Natural English.

× mary like pat
× pat and quincy likes mary

Fortunately, we can fix this problem by elaborating our rules just a bit. In particular, we can add an argument to some of our relations to indicate whether the expression is singular or plural, and we can then use this to block sequences of words where the numbers do not agree.

sentence(Z) :- np(X,W) & vp(Y,W) & app(X,Y,Z)
np(X,singular) :- noun(X)
np(W,plural) :- noun(X) & noun(Y) & app(X,and,Z) & app(Z,Y,W)
vp(Z,W) :- verb(X,W) & np(Y,V) & app(X,Y,Z)

With these rules, the syntactically correct sentences shown above are still guaranteed to be sentences, but the ungrammatical sequences are blocked. Other grammatical features can be formalized in similar fashion, e.g. gender agreement in pronouns (he versus she), possessive adjectives (his versus her), reflexives (himself versus herself), and so forth.

12.3 Boolean Logic

Throughout this volume, we have been using English to talk about Logic Programming. A natural question to ask is whether it is possible formalize Logic Programming within Logic Programming. The answer is yes, but there are some limits to what can be done.

In this section, we look at a simple version of this problem, viz. using Logic Programming to formalize the syntax and semantics of Boolean Logic. Sentences in Boolean Logic are simpler that those in Logic Programming. The vocabulary consists of atomic propositions, and sentences are either propositions or complex expressions formed from logical operators. The sentence shown below is an example. This is a statement that either p is true and q is false or p is false and q is true.

(p ∧ ¬q) ∨ (¬pq)

In what follows, we associate a symbol with each proposition in our Boolean Logic language. For example, we use p, q, and r to represent proposition p, q, and r.

Next, we introduce constructors o form complex sentences. There is one constructor for each logical operator - not for ¬, and for ∧, and or for ∨. Using these constructors, we can represent Boolean Logic sentences as terms in our language. For example, we could represent the sentence above as follows.


Finally, we introduce a selection of predicates to express the types of various expressions in our Boolean Logic language. We use the unary predicate proposition to assert that an expression is a proposition. We use the unary predicate negation to assert that an expression is a negation. We use the unary predicate conjunction to assert that an expression is a conjunction. We use the unary predicate disjunction to assert that an expression is a disjunction. And we use the unary predicate sentence to assert that an expression is a sentence.

With this vocabulary, we can characterize the syntax of our language as follows. We start with declarations of our proposition constants.


Next, we define the types of expressions involving logical operators.

negation(not(X)) :- sentence(X)
conjunction(and(X,Y)) :- sentence(X) & sentence(Y)
disjunction(or(X,Y)) :- sentence(X) & sentence(Y)

Finally, we define sentences as expressions of these types.

sentence(X) :- proposition(X)
sentence(X) :- negation(X)
sentence(X) :- conjunction(X)
sentence(X) :- disjunction(X)

A truth assignment is a mapping from proposition constants to Boolean values (true or false). We can encode a truth assignment with a binary relation value that relates a proposition constant and the associated value. For example the following facts constitute a truth assignment for the proposition constants above. In this case, p is true, q is false, and r is true.


Given a truth assignment, we can define a truth value for every sentence in our language. A proposition is true if and only if it is assigned the value true. A negation is true if and only if its argument is false. A conjunction is true if and only if both conjuncts are true. A disjunction is true if and only if at least one of its disjuncts is true.

truth(P) :- value(P,true)
truth(not(P)) :- ~truth(P)
truth(and(P,Q)) :- truth(P) & truth(Q)
truth(or(P,Q)) :- truth(P)
truth(or(P,Q)) :- truth(Q)

We can make our formalization more interesting by reifying truth assignments as objects. We could then talk about properties of sentences such as validity and satisfiability. A sentence is valid if and only if it is true in every truth assignment. A sentence is satisfiable if and only if some truth assignment satisfies it. A sentence is falsifiable if and only if some truth assignment makes it false. A sentence is unsatisfiable if and only if no truth assignment makes it true.


Exercise 12.1: Suppose we were to add the words himself and herself to the grammar in section of Pseudo English. Modify the rules defining our Pseudo English grammar so that these words appear only as the objects of sentences and so that, when one of these words is used in a sentence, its number and gender corresponds to the number and gender of the subject of that sentence.

Exercise 12.2: Say whether each of the following sentences is a consequence of the sentences in the section on Boolean Logic.

(a) conjunction(and(not(p),not(q)))
(b) conjunction(not(or(not(p),not(q))))
(c) sentence(not(not(p)))
(d) sentence(or(not(p),not(q),not(r)))
(d) sentence(and(p,not(p))

Exercise 12.3: Which of the following sentences are consequences of the truth assignment and rules in the section on Boolean Logic?

(a) truth(or(not(p),not(q)))
(b) truth(not(and(not(p),not(q))))
(c) truth(and(p,not(p))

Exercise 12.4: Suppose we wanted to add the xor operator to our Boolean Logic language. xor(p,q) is true if and only if the valuation of p is different from the valuation of q. Write a rule to extend our definition of truth to accommodate the xor operator.