Introduction to logic and

formalism
Formal specification
KARANJA Mwangi
Predicate calculus
 2.2 The predicate calculus
• In propositional calculus each atomic symbol (P, Q, e.t.c),
denotes a proposition of some complexity. Its not easy to
access the components of an individual assertion.
• Predicate calculus provides the ability of accessing the
components of an individual assertion.
– For example, instead of letting a single propositional
symbol, P, denote the entire sentence "it rained on
Tuesday," we can create a predicate weather that
describes a relationship between a date and the weather:
weather (tuesday, rain). Through inference rules we can
manipulate predicate calculus expressions, accessing their
individual components and inferring new sentences.
– Predicate calculus also allows expressions to contain
variables:

2
• Variables let us create general assertions
about classes of entities. E.g. we could state
that for all values of X where X is a day of the
week, the statement weather(X, rain) is true
meaning it rains everyday

3
 2.2.1 Syntax of Predicates and Sentences
• Before we define the syntax of correct expressions in the predicate
calculus we define the alphabet and grammar for creating the symbols of
the language. Predicate calculus symbols can be represented as strings
of letters and digits beginning with a letter.
– Blanks and non alphanumeric characters (e.g #) cannot appear within
the string, although the underscore, _, may be used to improve
readability.

PREDICATE CALCULUS SYMBOLS

• The alphabet that makes up the symbols of the predicate calculus
consists of'.
– 1. The set of letters, both upper- and lowercase, of the English
alphabet.
– 2. The set of digits, 0, 1, ..., 9.
– 3. The underscore,_.

4
• Symbols in the predicate calculus begin with a letter and are
followed by any sequence of these legal characters.
Legitimate characters in the alphabet of predicate calculus
symbols include
– aR69p_z
• Examples of characters not in the alphabet include
– #%@/& ....
• Legitimate predicate calculus symbols include
– George fire3 tom_andierry bill friends of
• Examples of strings that are not legal symbols are
– 3jack, "no blanks allowed" , ab%ed, **'71 , duck!!!

5
 predicate calculus symbols

• l(g,k) and likes(george, kate) are formally

equivalent, the second can be of great help (for
human readers) in indicating what relationship
the expression represents.
• descriptive name are intended solely to improve
the readability of expressions.
• improper symbols: include parentheses "( )",
commas ",", and periods ".“ are used to construct
well formed expressions and do not denote
objects or relations in the world.
6
• Predicate calculus symbols may represent either
variables, constants, functions, or predicates.
– Constant symbols must begin with a lowercase letter. The
constants true and false are reserved as truth symbols.
Thus george, tree, tall, blue are examples of well formed
constant symbols
– Variable symbols are used to designate general classes of
objects or properties in the world. Variables are
represented by symbols beginning with an uppercase
letter. Thus George, Bill, Kate are legal variables, whereas
geoRGE and bill are not.
– Functions denote a mapping of one or more elements in a
set into a unique element of another set. Function
symbols (likes) begin with a lowercase letter.
7
• A (function or predicate) symbol of arity 0 is called a
constant
• Sometimes we use the superscript to indicate the
arity of a symbol e.g we may write f2 for a binary
function symbol, or plus could be a function of arity
2. if plus(2,3) is a function expression whose value is
an integer 5 , then the act of replacing a function
with its value is called evaluation
• We use letters f, g, h .. ..to denote function symbols
and use P, Q, R to denote predicate symbols

8
 Definition: SYMBOLS and TERMS

• Predicate calculus symbols include:

– 1. Truth symbols true and false (these are reserved symbols).
– 2. Constant symbols are symbol expressions having the first character
lowercase.
– 3. Variable symbols are symbol expressions beginning with an
uppercase character.
– 4. Function symbols are symbol expressions having the first character
lowercase. Functions have an attached arity indicating the number of
elements of the domain mapped onto each element of the range.
A function expression is a function symbol followed by its arguments.
The argument are the elements from the domain of the function.
Hence the number of argument is equal to the arity of the function. A
predicate calculus term is either a constant, variable, or function
expression.

9
• thus a predicate calculus term may be used to
denote objects and properties in a problem domain.
– cat, times(2,3), X, blue, mother(jane), kate
• Symbols in predicate calculus may also represent
predicates. Predicate symbols, begin with a
lowercase letter.
– likes, equals, on, near, part_of

10
• atomic sentence:
– the most primitive unit of the predicate calculus language,
is a predicate of arity n followed by n terms enclosed in
parentheses and separated by commas.
– likes(george, kate) likes(X, george)
– likes(george, susie) likes(X, X)
– likes(george, sarah, tuesday) friends(bill,richard)
– friends(bill, george) friends(father_of(david),
father_of(andrew))
– helps(bill,george) helps(richard,bill)
– The predicate symbols in these expressions are likes, friends, and
helps.
– Bill, george, kate are constant symbols and represent objects in the
problem domain
– The arguments to a predicate are terms and may also include variables
or function expressions. E.g
– friends(father_of(david), father_of(andrew))

11
 Definition: PREDICATES and ATOMIC
SENTENCES

• Predicate symbols are symbols beginning with a lowercase letter.

• Predicates have an associated non-negative integer referred to as the

arity or "argument number" for the predicate. Predicates with the same
name but different arities are considered distinct.

• An atomic sentence is a predicate constant of arity n, followed by n

terms, t1, t1, …tn, enclosed in parentheses and separated by commas.

• The truth values, true and false, are also atomic sentences.

Atomic sentences are also called atomic expressions, atoms, or propositions.

12
 variable quantifiers

The universal quantifier, ,

indicates that the sentence is true for all values of the variable
The existential quantifier, ,
indicates that the sentence is true for at least one value in the domain.

example
Y friends(Y, peter)
X likes(X, ice_cream)

13
 Definition: PREDICATE CALCULUS
SENTENCES
Every atomic sentence is a sentence
1. If s is a sentence, then so is its negation, ¬s.
2. If s1 and s2 are sentences, then so is their conjunction, s1 Λ s2
3. If s1 and s2 are sentences, then so is their disjunction s1 ٧ s2
4. If s1 and s2 are sentences, then so is their implication s1 → s2
5. If s1 and s2 are sentences, then so is their equivalence s1 ≡ s2
6. if X is a variable and s a sentence, then ∀X s is a sentence
7. If X is a variable and s is a sentence, then 3X s is a sentence

14
 Examples of well-formed sentences
• Let times and plus be function symbols of
arity 2 and let equal and foo be predicate
symbols with arity 2 and 3 respectively.
• plus(two,three) is a function and thus not an atomic
sentence
• equal(plus(two,three), five) is an atomic sentence
• equal(plus(2,3),seven) is an atomic sentence. I n this
sentence, the standard interpretation of plus and
equal is false. Well-formedness and truth values are
two different issues.

15
 Examples..ctd
• ∃X foo(X,two, plus(two, three)) ∧
equal(plus(two, three),five) is a
sentence because both conjuncts are
sentences

16
 recursive algorithm
• function verify_sentence(expression);
• begin
• case
• expression is an atomic sentence: return SUCCESS;
• expression is of the form Q X s, where Q is either V or 3, X is a variable,
• and s is a sentence:
• if verify_sentense(s) returns SUCCESS
• then return SUCCESS
• else return FAIL;
• expression is of the form ￢s:.
• if verify_sentence(s) returns SUCCESS
• then return SUCCESS
• else return FAIL;
• expression is of the form s1 op s2, where op is a binary logical operator:
• if verify_sentence(s1) returns SUCCESS and
• verify_sentense(s2) returns SUCCESS
• then return SUCCESS
• else return FAIL;
• otherwise: return FAIL
• end
• end.

17
 Concluding predicate calculus
• Example-use of predicate calculus to describe a
simple world.
mother(eve, abel)
mother(eve, cain)
father(adam, abel)
father(adam, cain)
• ∀X∀Y(father(X, Y)) ∨ mother(X,Y)→parent(X,Y)
• ∀X∀Y∀Z(parent(X,Y)) ∧ parent(X,Z)→sibling(Y,Z)
• Mother and father are used to define the parent-
child relationships.
• Implications give general definitions of other
relationships, i.e. parent and sibling
• Implications can be used to infer facts such as
sibling(cain , abel)

18
• Care must be taken in defining an
inference algorithm and ensure that
such algorithms draw correct
conclusions from a set of predicate
calculus assertions

19
 Semantics for the predicate calculus
• Predicate calculus semantics provide a formal basis for
determining the truth value of the well formed expressions.
The truth of the expressions depends on the mapping of
constants, varables, predicates, and functions into objects and
relations in the domain of discourse. The truth of
relationships in the domain determines the truth of the
corresponding expressions. e.g. george and his friends may be
expressed as follows.
• friends(george, susie)
• friends(george, kate)
• If it is true that george is a friend of susie and george is a
friend of kate then each expression would have a truth value
(assignment) T.

20
 Relationships btwn negation and the
universal and existential quantifiers
• For predicates p and q and variables X and Y

X p( X )  X p( X )
X p( X )  X p( X )
X p( X )  Y p(Y )
X q( X )  Y q(Y )
X ( p( X )  q( X ))  X p( X )  Yq(Y )
X ( p( X )  q( X ))  X p( X )  Yq(Y )
• In the above, universally and existentially quantified variables may refer only to
objects (constants) in the domain of discourse. Predicate and function names may
not be replaced by quantified variables. This language is called the first-order
predicate calculus

21
 first-order predicate calculus(1)
• First-order predicate calculus allows variables
to refer to objects in the domain of discourse
and not to predicates or functions
• E.g ∀(Likes)Likes(george, kate) is not
a well formed expression in the
first- order predicate calculus

22
 first-order predicate calculus(2)
• The predicate calculus includes a
wider range of entities. It permits
the description of relations and the
use of variables. It also requires an
understanding of quantification.
• The language of predicate calculus
requires:
• Variables
• Constants
– ---these include the logical
constants The non-logical constants include
– The last two logical constants are both the `names' of entities that are
additions to the logical related and the `names' of the
connectives of propositional
calculus ---they are known as relations. For example, the constant
quantifiers dog might be a relation and the
constant fido an entity.
Dog(fido)
23
 first-order predicate calculus(3)
• jim is tall
• might be represented either as
– tall(jim)
– or
– jim(tall)
• loves(jane,jim).
• then jane and jim refer to specific objects. Both jane and jim are constants
• NOTE: Because Prolog is modeled on a subset of first order predicate logic,
all predicate names must be constants ---but not numbers
• NO PREDICATE MAY BE A VARIABLE
• we cannot have X(jane,jim) as representing the fact that jane and jim are
related in some unknown way

24
 exercise
• Represent the following sentences in prolog form
1. bill likes ice-cream
2. bill is tall
3. jane hits jimmy with a cricket bat
4. john travels to london by train
5. bill takes jane some edam cheese
Note: (1)constants do not start with upper case letters
(2) there are several ways of representing the
above statements

25
Examples of English sentences represented
in predicate calculus
• If it doesn' t rain on Monday, Tom will go to the mountains.
weather(rain, monday)  go(tom, mountains)
• Emma is a Doberman pinscher and a good dog.
Isa(emma, doberman)  gooddog(emma)
• All basketball players are tall.
X (basketball_player(X )  tall(X))
• Some people like anchovies.
X (person(X)  likes(X, anchovies))
• If wishes were horses, beggars would ride.
equal(wishes, horses)  ride(beggars)
• Nobody likes taxes.
X likes(X, taxes)
26
 exercise
• Represent the following sentences in predicate calculus
1. All animals eat custard
2. Everyone loves bebecool’s music
3. Jim likes fred’s possessions
4. If someone needs a bike then they may
borrow janes

27
 Examples of predicate logic to practice
on!!!!!!!
1. All fruit is tasty if it is not cooked. This apple is not cooked. Therefore, it is
tasty.
2. All fruit is tasty if it is not cooked. This apple is cooked. Therefore, it is not
tasty.
3. Some fruit is tasty if it is not cooked. This apple is cooked. Therefore, it is
not tasty.
4. Some fruit is tasty if it is not cooked. This apple is not cooked. Therefore,
it is tasty.
5. All that glistens is not gold. This pot does not glisten. Therefore, it is gold.
6. No lecturer who spends her time writing books on logic or who devotes
herself to her students will come to the notice of the establishment. No
one who does not come to the notice of the establishment will secure
preferment. Therefore, no lecturer who spends her time writing books on
logic will secure preferment.

28
 Examples of predicate logic
7. Dilly loves all and only those who love Milly. Milly loves all and only those
who do not love Dilly. Dilly loves herself. Therefore, Milly loves herself.
8. All those who honor both their parents are blessed. If anyone dislikes any
of his siblings he does not honor his parents. Jack likes his sister, Jill.
Therefore Jack is blessed.
9. All lecturers are determined. Anyone who is determined and intelligent
will give satisfactory service. Clare is an intelligent lecturer. Therefore
Clare will give satisfactory service.
10. All men are mortal. Socrates is mortal. Therefore Socrates is a man.
11. All men are mortal. Socrates is a man. Therefore Socrates is mortal.
12. Every student likes logic. If a person likes logic and studies hard, she will
pass all her exams. Joann is a lover of logic who studies hard. Therefore,
Joann will pass her tomorrow's exam.
13. Some musician are writers. Some mathematicians are not writers.
Therefore, some mathematicians are not musicians.

29
 Satisfy, model, valid, inconsistent
(cont’d)
•A set of expressions is satisfiable iff there is an interpretation and variable
assignment that satisfy every element.
•If a set of expressions is not satisfiable, it is said to be inconsistent.
•If X has a value T for all possible interpretations, X is said to be valid.
•The expression X(p(X)∧¬p(X)) is incosistent because it cant be satisfied
under any interpretation. On the other hand ∀X(p(X)∨¬p(X)) is valid
•The truth table method can be used to test validity for an expression not
containing variables. However there are proof procedures that can produce
any expression that logically follows from a set of expressions. These are
called complete proof procedures

30