Prolog/Introduction to logic

Since Prolog is based heavily on formal logic, it's useful to have some experience with it before starting to learn the language. This is a short introduction to logic for people who want to learn Prolog. It will discuss two logical languages: propositional logic and first-order logic.

Propositional Logic

Propositional logic has two basic elements, terms and connectives. Terms are represented by letters (usually upper-case), and represent the values true and false, i. e. a term can be either true or false, though it doesn't always have to be made clear which they represent. They are in this sense like variables in mathematics since they represent an unknown value.

Connectives, like the word suggests, connect two terms. The result of this connection takes on the value true or false, depending on the values of the two terms. Consider, for instance, the connective AND. It could connect the terms A and B to make the logical sentence "A AND B". (Anything that can take on the values true or false is called a sentence.) The sentence "A AND B" is true if both A and B are true. If one or both of them are false, the sentence is false. Connectives are usually represented by symbols rather than words. The following table shows the most commonly used connectives, their meaning and the symbols that are often used to represent them.

Name	Usage	Translate	Meaning	symbols
conjunction	$A\land B$	A and B	the sentence is true if and only if both terms are true	$\land \quad ,$
disjunction	$A\lor B$	A or B	the sentence is true if one or both of the terms are true	$\lor \quad ;$
exclusive or	$A\oplus B$	A xor B	the sentence is true if one of the terms is true, but not both	$\oplus \quad {\underline {\lor }}\quad$
negation	$\lnot A$	not A	the sentence is true if the term is false and false if the term is true	$\sim \quad \lnot \quad {\bar {q}}$
implication	$A\rightarrow B$	A logically implies B	if A is true the sentence is true only if B is true, if A is false, the sentence is true	$\rightarrow \quad \Rightarrow \quad \models$
equality	$A\leftrightarrow B$	A is logically equivalent to B	the sentence is true if both terms are true or if both terms are false	$\leftrightarrow \quad \Leftrightarrow \quad =$

Beware of the meaning of implication, as it can be counter-intuitive. $A\rightarrow \;B$ basically says, if A is true, then so is B, otherwise B can be either true or false.

Since each term can only take on two values, all possibilities can easily be enumerated in a so-called truth table:

$A$	$B$		$A\land B$	$A\lor B$	$A\oplus B$	$\neg A$	$A\Rightarrow \;B$	$A\Leftrightarrow \;B$
F	F		F	F	F	T	T	T
F	T		F	T	T	T	T	F
T	F		F	T	T	F	F	F
T	T		T	T	F	F	T	T

The next step is to connect these sentences, using connectives, to make more complex sentences, such as $(A\land B)\Rightarrow \;(B\Leftrightarrow \;A)$ or $(A\lor B)\lor (A\lor C)$. In the last sentence, the brackets can be omitted, since $A\lor (B\lor C)$ is the same as $(A\lor B)\lor C$. However, when in doubt, it's best to use brackets to make the meaning of the sentence completely clear.

You can analyse complex sentences with truth tables as well:

$A$	$B$		$A\land B$	$A\lor B$	$(A\land B)\lor (A\lor B)$
F	F		F	F	F
F	T		F	T	T
T	F		F	T	T
T	T		T	T	T

We can now divide sentences in three groups: valid, unsatisfiable and satisfiable.

• Valid sentences (a.k.a. tautologies) are always true, no matter what values their terms take.
  Examples of valid sentences include
  1. $A\lor (\lnot A)$
  2. $A\Rightarrow A$
  3. $(A\Rightarrow B)\lor (A\land (\lnot B))$
• Unsatisfiable sentences (a.k.a. inconsistencies) are always false, no matter what values their terms take.
  Examples of unsatisfiable sentences include
  1. $A\land (\lnot A)$
  2. $(A\Rightarrow B)\land (A\land (\lnot B))$
• Satisfiable sentences (a.k.a. contingencies) are those that can be either true or false, depending on the values that their terms take.
  Examples of satisfiable sentences include
  1. $A$
  2. $A\lor B$
  3. $A\land B$

Meaning and Intention

It's very important in logical languages to realize that these sentences can be used in different ways. $A\wedge B$, for instance, does not imply any meaning on its own. It's just a formal way of creating logical constructions. Someone can state that $A\wedge B$ is true, which would give the sentence a meaning (namely that A and B are both true), which can be used to derive further truths if other things are known about A and B. Someone might also ask if $A\wedge B$ is true, to which the person asked this would have to find an answer based on things already known about A and B. In other words, a logical sentence on its own doesn't mean anything. The reader needs to know the intention behind the sentence (usually question or statement) to be able to do something with it. A common construct in logic is a knowledge base, a collection of sentences that are stated to be true, and a single sentence that is posed as a question. The question is whether the question is true, given the knowledge base. Consider, for instance, the following knowledge base:

$A\wedge B$
$~B$

With the question

$A$

That is, is A true, given that the Knowledge base is. It's clear that the question is indeed true, since $A\wedge B$ is true, and B is too. This knowledge base/question construction is in fact the way that prolog works. You write a knowledge base (your program) and ask prolog a question. In comparison to conventional programming languages, the knowledgebase is your program, the question is its input and prolog resolving your question is the running of the program.

First Order Logic

First Order Logic (also known as predicate logic) expands on propositional logic, by using predicates, variables and objects. In propositional logic, the atomic sentences (the smallest elements that can take on a true/false value) are terms, symbols represented by letters. In first order logic the atomic sentences are predicates. Predicates have a name (starting with a capital) which is followed by several variables (starting with a lowercase letter). The following are examples of predicates:

• Predicate(variable1, variable2)
• BrotherOf(sibling, brother)
• MotherOf(child, mother)
• HasWheels(thing)

These variables can be instantiated with objects. Objects are elements represented by words that start with a capital letter. For instance, in the predicate $HasWheels(thing)$ the variable thing can be instantiated with the objects Car, Bike, or Banana. Based on the instantiation of the variables, the predicate is true or false ($HasWheels(Car)$ is true whereas $HasWheels(Banana)$ is false). Note however that these names are for readability only, they do not actually mean anything. $HasWheels(Banana)$ is not functionally different from $X(A)$, or indeed $WrUlS(OvqPv)$. Whether $HasWheels(Banana)$is true or false needs to be defined in some formal way (such as a knowledge base, which is described below).

These predicates can be joined in sentences, just like the terms in propositional logic, using connectives (the connectives are the same as in propositional logic). Usually there is a collection of sentences that are assumed to be true, to create a logical definition of predicates. Such a collection of sentences that are true is called a knowledge base. Such a knowledge base could, for instance contain the following sentences:

HasWheels(Car)
MotherOf(Charles, Elizabeth)

The sentences tell us that the HasWheels predicate is true, if its first element is car; and the MotherOf predicate is true, if its first element is Charles and the second is Elizabeth. To construct this kind of sentences with variables in them we need to state what exactly we mean when we use the variables. If HasWheels(x) is true, do we mean it's true for instantiations of x or that there exists an instantiation of x that makes HasWheels(x) true? To define this we use quantifiers, ie. they determine the quantity of a variable. First order logic has two quantifiers, the universal quantifier $\forall$ and the existential quantifier $\exists$. These quantifiers are placed before a variable to signify what the variable means in the sentence that follows the quantifier. For instance, the sentence $\forall xHasWheels(x)$ means that for all possible instantiations of x, HasWheels(x) is true, that is, all possible objects have wheels. The sentence $\exists xHasWheels(x)$ means that there exists at least one object x for which HasWheels(x) is true, in other words there is at least one thing that has wheels. To understand the use of the quantifiers, consider the following examples:

• If x is a land vehicle, then x has wheels. (if x is not a land vehicle, this sentence says nothing about x)

$\forall {x}LandVehicle(x)\Rightarrow HasWheels(x)$

• If x has a child y and x is a man, x is the father of y.

$\forall {x,y}HasChild(x,y)\wedge Man(x)\Rightarrow FatherOf(y,x)$

• There exists at least one object that has wheels and isn't a car

$\exists {x}HasWheels(x)\wedge \sim Car(x)$

• All mothers have a child

$\forall {x}Mother(x)\Rightarrow \exists {y}Child(y)\wedge HasChild(x,y)$

Logic in Prolog

The logic used in prolog is a version of first order logic, with the use of capital letters inverted (predicates and objects start with a lowercase letter, variables start with an uppercase letter). A prolog program consists of a knowledge base where each sentence is a conjunction of predicates connected to a final predicate with an implication. For instance:

$\forall a,b,c,dPred1(a,b)\wedge Pred2(b,c)\wedge Pred3(c,d)\Rightarrow Pred4(a)$

A sentence like this is called a Horn Clause. In prolog the above sentence would look like this:

pred4(A) :- pred1(A, B), pred2(B, C), pred3(C, D).

Note that the implication sign is reversed, commas are used for conjunction, a period is used to end the sentence and all variables are assumed to be universally quantified.

Examples

for all x: cat(x) or dog(x) implies pet(x)

Exercises

(x) Write out a truth table for the following sentences in propositional logic.
a) $(A\wedge B)VC$
b) $A$
c) $A$
d) $A$
e) $A$

(x) How many connectives are possible, that connect two terms? Why?

(x) Try to find a formula to fit the following truth tables
a)
b)
c)
d)

(x) Truth tables are a great way to prove that a propositional formula is true. Could you do the same thing for first order logic? Explain how, or why not.

(x) Convert the following sentences to first order logic. Try to follow the logical structure of the sentence closely (using objects for individuals, variables for groups of people, connectives for logical constructions and predicates for the rest).
a) All kids are short.
b) Certain kids own shoes.
c) If someone is a kid and a boy, he likes cars.
d) All kids that own shoes, wear them.
e) All kids have a mother.
f) If a woman is a mother, she has a kid.
g) No kid likes a vegetable if it's overcooked.
h) No mother likes a teacher if he punishes her kid.

(x) (advanced)The following questions concern the = symbol. It takes two variables and is true if they are bound to the same thing, in other words x = y is true if x and y represent the same object.
(a) Is the = symbol a function, predicate or a connective? Why?
(b) The = symbol shouldn't be confused with the equality connective. How are the different?
(c) Can you think of a sentence in first order logic that, when added to a knowledge base (and thus considered always true) does the same thing as the = symbol. That is, through it's definition in the knowledge base, this sentence, with 'inputs' x and y, is true if x and y are equal.
(d) The existential quantifier $\exists x$ defines that a sentence is true if it's true for at least one possible instantiation of x. Can you think of a way to quantify a variable x for a sentence so that the sentence is true if it's true for only one instantiation of x, but no more? You'll probably need the = symbol for this.