Transcript Turing’s discovery

Introduction to Logic and
Prolog
Sabu Francis, B.Arch (Hons)
Turing’s discovery
Faced with the complex problem of decoding encrypted
Nazi messages, Alan Turing invented the modern
computer in the forties.
The breakthrough came when he realized that any algorithm
can be carried out using a linear process involving instructions
that manipulated symbols
Instruction pointer
Tracking the instruction pointer
While developing a program,
programmers implicitly track
the movement of the instruction
pointer linearly through the
code.
Algorithm = Logic + Control
If you look at the entire sequence of arrows, you will find
that these arrows will always be stitched up together in one
large unbroken sequence
In short, the programmer has to work on
how the logic of the program is to be
controlled
Can we separate logic
from control?
If a programmer can disconnect the logic of the code from
the way that logic is to be controlled …
The source code becomes smaller and the
time spent stitching up the instruction
pointer becomes lesser. In short: Fewer
bugs!
Prolog =
Programming in Logic
When using Prolog to solve problems, it is important to
discard all notions of procedural programming
Issues such as stitching up the instruction
pointer is no longer your concern. The
Prolog system will do it for you. Just have
faith, and worry only about the logic (and
a few other things which we’ll come to
later)
But before we jump to Prolog ….
What is logic?
The words logic, logical, etc. has common interpretations.
We need to be more rigorous than that and recognize that
logic as used in Prolog is purely an important part of
mathematics.
For example; sometimes the word logical
is used to represent something that is
carefully thought out – which is reasonable
or acceptable to the world around.
All aspects of
logic are equally useable
It is well known that the mathematical symbols “1”, “2”,
“3”, etc are equally weighted. That means, none of them
have “superiority” over the others.
Equivalently, in the field of logic; you
would encounter concepts such as true,
false, if->then, not, and, or … etc. None
of them are more “superior” than the other.
The context determines the outcome and
they are all equally useful.
Logic is a tool
Logic is the tool for correct reasoning. However, not all logical
operations may lead to scientifically valid conclusions. Or even
things that are useful to us. It all depends on core premises that may
have been made in the said operation.
For example, consider the following sequence of logical
statements that constitute an “inference”:
a) Some real estate will increase in value.
b)Anything that will increase in value is a good investment.
c)Therefore, some real estate is a good investment.
Is the above inference right?
The maths is right, but ...
This inference is logically correct, because the conclusion “some real estate
is a good investment” necessarily follows once we accept the premises
“some real estate will increase in value” and “anything that will increase in
value is a good investment”. Yet this same inference may not be a
demonstration of its conclusion, because one or both of the premises may
be faulty. Thus logic can help us to clarify our reasoning, but it can only go
so far. The real issue in this particular inference is ultimately one of finance
and economics, not logic.
If the above inference was used in Navi Mumbai during 1999, it
would have been a disaster. Because the premise “some real
estate will increase in value” was incorrect during that period.
Many investors lost considerable money during that period
because of this. Some even lost their lives!
Propositions
Of all the sentences that are used by humans to yield meaning,
logic concerns itself with only those that yield truth values. Such
sentences are known as statements or by some authors as
propositions. The English teacher calls them declarative
sentences. This may be the reason why Prolog is often called a
declarative language.
Examples:
“The fruit is an apple” is a proposition
(true if the indicated fruit is actually an apple, false otherwise)
But
“Is the fruit an apple?” is not. It is just a question that humans ask,
and logic by itself cannot provide an answer that results in a truth
value. Similarly, “Oh my God!” is just an exclamation. No logic
there.
All truth values are
useful in reasoning
In arithmetic, we are allowed to write expressions like this:
2+3 = 5 (and the maths has no clue what in the world does “5” represent. It
cannot even determine whether that expression is useful to us)
... and this expression would be incorrect,
2+3= 7
If we now regard 2+3=5 and 2+3=7 as two logical statements (i.e. From
the field of logic and not arithmetic), then both are allowed. The truth
value of the first statement is “true” and the second one “false”. Hence
both are logical statements and therefore allowed in the field of logic.
In fact, the field of mathematics is famous for using the principle of
reductio-ad-absurdum where theorems are proved by inferring a
premise that is logically false, which will make the starting premise null
and void. (E.g. The theorem for proving the existence of an infinite
number of primes)
Which of these are propositions?
1) X=X
2) Everyone belongs here
3) All humans fly
4) Take a book from this pile
5) I am requesting you to take this book
Propositions – Venn diagram
World of sentences
World of propositions
Aristotle gave the basics
A proposition contains a subject and a predicate. The subject is the thing for
which the truth value is being determined. The predicate is something that is being
told about the subject (property, mode of existence of the subject, etc.) When we
examine the predicate in context of the subject we can determine the truth value of
the proposition.
Aristotle gave three fundamental rules of predication:
a) A is A = The principle of identity
(E.g. A baby boy will grow to become a man and not an oak!)
b) A is not A is impossible = The principle of non-contradiction
(E.g. An honest man cannot be a thief)
c) Either A or non-A = The principle of Either-or
A given predicate either belongs or does not belong to a given subject in a given
respect at a given time. (E.g. A society must be either free or not free.)
Syllogisms
The basic unit of reasoning is a syllogism, as per Aristotelian logic. For example,
the real estate inference which was presented above is a syllogism. It is of the
form:
a) Some A is B. b) All B is C. c) Therefore, some A is C.
Here A denotes real estate, B denotes increase in value, and C
denotes a good investment. Just as in the case of this
example, every syllogism consists of two premises and one
conclusion. The premises and conclusion are all propositions
(i.e. Statements yielding truth values).
All propositions fall in 4 classes
Each of the premises and the conclusion is of one of four types:
a) universal affirmative:
All A is B.
b) universal negative:
No A is B.
c) particular affirmative:
Some A is B.
d) particular negative:
Some A is not B
The letters A, B, C are known as terms. Every syllogism
contains three terms. The two premises always share a
common term which does not appear in the conclusion.
This is known as the middle term. In our real estate
example, the middle term is B, i.e., that which increases in
value.
pons asinorum: Bridge of Asses
In order to classify the various types of syllogisms, one must understand that
certain premises are symmetric and therefore equivalent. In particular, “no A
is B” and “no B is A” are equivalent, as are “some A is B” and “some B is A”.
Furthermore, the order of the two premises in a syllogism does not matter.
Allowing for these symmetries, we can enumerate a total of 126 possible
syllogistic forms. Of these 126, only 11 represent correct inferences. For
example, the form
all A is B, all B is C, therefore all A is C represents a correct inference, while
all A is B, all C is B, therefore some A is C does not.
Medieval thinkers developed ingenious mnemonics to aid in distinguishing
the correct forms from the incorrect ones. This culminated in the famous
pons asinorum (``bridge of asses''), an intricate diagram which illustrates all
of the syllogistic forms by means of a contrast between the good and the
pleasurable.
The first hurdle in logical reasoning
Apart from using the wrong syllogism for
inferences, classifying propositions into the wrong
category is an even more basic issue that affect our
reasoning.
For example; we sometimes put a proposition into the
universal affirmative instead of the particular
affirmative.
This often happens in inductive arguments, where we
take an empirical observation and assume that it is a
universal truth.
This is a classification error, which can lead to serious
problems whether it is writing logical code using
Prolog or simply ... arguing!
Compound propositions
Often simple propositions may not be sufficient to declare a
premise. We may need to stitch up several propositions into
one compound proposition. This is done using connectives.
1. Conjunctions- (P and Q) - for proposition to be true both P and Q must be
true, if either of them is false, proposition is false.
2. Disjunctions- (P or Q) - for proposition to be true only one of the
component simple statements need be true.
3. Negations- (NOT P) - in this type of proposition the simple proposition is
modified so that the truth value is reversed.
4. Conditionals- (IF P, THEN Q) - in this proposition, the first part is
identified as the antecedent, and the second part as the consequent. For this
statement to be true, the condition expressed for the truth of Q must not be
compromised. The only case when this happens is when P is true and Q is
false.
5. IF_AND_ONLY_IF or equivalence.
There are symbols that are used as short-forms for the above connectives.
Truth Tables
Each compound proposition can be examined against a truthtable to determine the truth value of the compound
proposition.
For example; the truth-table for the or connective is :
T or T
T or F
F or T
F or F
=T
= T
=T
= F
Other truth-tables can be looked up from any reference book.
Misunderstanding the truth table of a compound proposition
is another common source of errors when interpreting
premises.
Predicate logic and Prolog
In 1879 the German philosopher Gottlob Frege gave a more
powerful logical reasoning system that lead to the development of
predicate logic. It overcame some of the problems in representing
logical issues using propositional logic.
In the 1970's, the French mathematician, Colmereur developed
Prolog that used predicate logic and its extensions to develop a
natural language processor. It had a logic control system built-in so
the programmer did not have to worry about the control portion of
any algorithm.
But what were the shortcomings of propositional logic?
Shortfalls of Propositional logic
a) A proposition talks about the subject and its predicate. Both have to be
known before hand. So propositions cannot be used in all logical reasoning
that humans are involved in.
For example, the assertion "x is greater than 1", where x is a variable, is not a
proposition because you can not tell whether it is true or false unless you
know the value of x. Thus the propositional logic can not deal with such
sentences. However, such assertions appear quite often in mathematics and we
want to carry out inferences on those assertions.
Shortfalls of Propositional logic
b) Propositional logic cannot be used for some equivalence determination. For
example; the pattern involved in the following logical equivalences can not be
captured by the propositional logic:
"Not all birds fly" is equivalent to "Some birds don't fly".
"Not all integers are even" is equivalent to "Some integers are not even".
"Not all cars are expensive" is equivalent to "Some cars are not expensive"
If only propositional logic is used and an inference is sought,
each of these equivalences must be listed individually and acted
upon.
A general formula that covers all these equivalences collectively
and instantiating it as they become necessary would have been a
better approach ... and that is exactly what predicate logic gives!
Predicates as proposition builders
We had learnt earlier that a predicate describes a property of objects, or a
relationship among objects.
In predicate logic, the predicate acts as a verb template to which the
subject and objects are given as arguments.
Now let us use a predicate as a template; something that builds a
proposition as required:
For example, the propositions "The car Tom is driving is blue", "The sky
is blue", and "The cover of this book is blue" come from the template "is
blue" by placing an appropriate noun/noun phrase in front of it. The
phrase "is blue" is a predicate and it describes the property of being
blue.
Predicates are often given a name. For example any of "is_blue", "Blue"
or "B" can be used to represent the predicate "is blue" among others. If
we adopt B as the name for the predicate "is_blue", sentences that assert
an object is blue can be represented as "B(x)", where x represents an
arbitrary object. B(x) reads as "x is blue".
Atomic formulas and wff
Just like propositions can be stitched up together to form compound
propositions using one of the 5 logical operators, similarly simple
predicates can also be stitched up.
A simple predicate like the is_blue ( or Bx) predicate is also known as an
atomic formula.
If A is an atomic formula, and so is B then
a) not(A)
b) A and B
c) A or B
d) if A then B
e) A is equivalent to B
are known as well formed formula or wff
… and obviously, an atomic formula is also well-formed.
Propositions from predicates
A predicate with variables is not a proposition. For example, the
statement x > 1 with variable x over the universe of real numbers is
neither true nor false since we don't know what x is. It can be true or
false depending on the value of x. For x > 1 to be a proposition either we
substitute a specific number for x or change it to one of two types:
“There is a number x for which x > 1 holds”
or
“For every number x, x > 1 holds.”
More generally, a predicate with variables can be made a
proposition by applying one of the following two
operations to each of its variables:
1. assign a value to the variable – a process called
binding in Prolog
2. quantify the variable using a quantifier
Quantifiers
In general, a quantification is performed on formulas of predicate
logic (called wff ), such as x > 1 or P(x), by using quantifiers on
variables. There are two types of quantifiers: universal quantifier and
existential quantifier.
The universal quantifier turns, for example, the statement x > 1 to
"for every object x in the universe, x > 1", which is expressed as " x
x > 1". This new statement is true or false in the universe of
discourse. Hence it is a proposition once the universe is specified.
Similarly the existential quantifier turns, for example, the statement
x > 1 to "for some object x in the universe, x > 1", which is expressed
as " x x > 1." Again, it is true or false in the universe of discourse,
and hence it is a proposition once the universe is specified.
Predicates using Prolog syntax
Predicate logic will now onwards be described using the language
Prolog, rather than the syntax adopted in mathematics books.
The objective of Prolog is to declare a set of predicates that describe the
logical reasoning required to derive an inference. The “is_blue”
predicate described earlier can be written down as follows:
is_blue(X)
If you note, the variable x is now capitalized.
This is how Prolog distinguishes a variable
from other parts of the program. Any word with
an initial letter capitalized is a variable.
The above predicate can act as proposition
builder, provided we give some more
information to it. This is done via a hornclause ...
Horn Clauses
If we want the template
is_blue(X)
to generate propositions, we need to give more information. What
may X stand for? This is done using horn clauses thus:
is_blue(X):X = “Tom's Car”.
Note the :- that demarcates the head of the horn-clause
from the body. Also, note the full-stop at the end of the
horn-clause.
The statement X = “Tom's car” is itself a declaration
which states that X is no longer a variable, but it has now
got bound to the value “Tom's car”.
Clauses and facts
Though in this example there is only one statement, the clause body can
describe a compound set of predicate calls stitched up by conjunctions. The
syntax for the and conjunction is the plain ole’ comma.
If a horn-clause becomes a wff (well formed formula) using exactly one
clause, then it is known as a fact. Just as its real-world meaning, a fact is
always true! The Prolog system need not investigate further. In fact, a set of
facts is collectively known in as a database (some call it knowledgebase)
/* database has two facts*/
parent(fred, greta). /*fact*/
parent(greta, henry). /*fact*/
/*this is a predicate that has a clause
body*/
grandparent(X, Z):parent(X, Y), /*and operator*/
parent(Y, Z).
Anatomy of a Prolog program
A Prolog program can be roughly be described as follows:
It contains a set of facts, or a knowledgebase
It contains a set of horn-clauses (or rules) that determine how to make
deductions
The program starts by a starting horn-clause which it checks whether it is
true. In order to do that, it goes through a logical path which may involve
examining other horn-clauses and the available process.
Side-effects would be simultaneously performed as each truth statement
is evaluated.
Our first Prolog program
At this point, we have given the Prolog system all that is needed to
get a simple inference done.
After entering the horn-clause, we can now ask Prolog a question at
the prompt (which in many Prolog systems is a question mark):
? is_blue(X)
At this point, you would see Prolog answering back like this:
X= “Tom's car”
true
The first line contained the answer.
The second line contained the truth value.
(Some Prolog systems may indicate the number of
solutions that were yielded on the second line)
This means Prolog
generated propositions on
the fly, using the hornclauses given to it, and
used those proposition to
get an inference done.
Prolog querying
This is not all. If we now give
? is_blue(“Tom's pants”)
At this point, you would see Prolog answering back
like this:
false
(some Prolog systems may answer “No solutions” or
signal an error)
This means Prolog generated a proposition on the fly,
using the horn-clauses given to it, and used that
proposition to get an inference done. In this case, it
was not calculating the value of X. But instead, it was
using the value that we had supplied and it was
checking if such a value existed as an argument in its
proposition for is_blue. It could not find any, and
therefore it returned false.
Free and bound variables
What has happened here, is that the simple three line program can
be used by Prolog in multiple ways.
This happens because a variable in Prolog, unlike in any other
procedural language, can either be bound or free.
In the first case, the horn-clause is_blue was being used where the
variable X was free. (i.e. We did not supply any constant as an
argument. Instead we passed on an “empty box” metaphorically
speaking)
Prolog then filled that empty box and returned the bound
variable back to us.
Think of a bound variable as a box which has something
inside it.
Bound variables
In the second example, the value “Tom's pants” was passed as an
argument to the horn-clause. Prolog implicitly created a variable (a
box), and filled it with the words “Tom's pants” (i.e. The variable
became bound to “Tom's pants”).
This time around, Prolog intelligently deduced that we do not want
any value back from the system, but we want the system to
determine if such an assertion was true.
It then went around making propositions form the horn-clause
template, and found that is_blue(“Tom's pants”) can never be
true. Hence it returned false. (Some Prolog systems may
return an error)
This is one simple demonstration that shows how Prolog
controls the program on your behalf.
A pause …
Our first Prolog program is ready. Now let us tackle some issues
that we had left for later in the earlier slides. For example; we said
that in a Prolog program we need to describe the logic and a few
other things.
What are those?
from the world outside
from within the computer …
Control
Logic
Problem space
Internal data
Algorithm
What is in our hands?
in our hands!
from the world outside
Not in our hands!
from within the computer …
Not in our hands!
Control
Logic
Problem space
Internal data
Interpretation is in our hands!
Algorithm
The most critical step
Problem space
Internal data
One wrong interpretation can destroy your code!
Critical thinking is a must at this step!
In architecture, they say: “God is in the details” (Mies Van De Rohe)
In computer software, we should say: “God is in the Data”
The representation issue
Theories regarding representing the real word in a logically correct mathematical
model has occupied the minds of most philosophers. Fortunately, much of the
problem space that programmers encounter is not as complicated as those handled
by philosophers! This is because programs written today are for extremely
focussed problem spaces, which are actually quite small – even if the programmer
may think otherwise. The area of interest to the programmer is also known as the
universe of discourse or just universe in some literature.
In Prolog, the outside problem-space is handled by understanding the domains that
are needed.
What is a domain?
The concept can be understood if we take a
specific example:
When we say sin(X) what do we understand
about X ?
Domains
When we say sin(X) what implications can we make about X ?
X has to be an angle which will invariably lie between zero and 2pi. In short, we
understand that of the various things nice, beautiful, ugly, whatever that is out
there in the whole wild, wide world, X can only be bound to values from one small
corner of it. We therefore have clearly established the domain of X.
Another example: In the is_blue(X) predicate, the
variable X happened to be belong to the domain of
strings.
Domain matching
It is up to us as programmers to clearly delineate which domain a particular
variable ought to belong to, and use that consistently in all the horn-clauses
that we set-up in the Prolog system.
Technically speaking Prolog is loosely typed. This means, we do not have to
specify the domain for a variable. It remembers the variable type the first time
it was used in a horn-clause, and within that horn-clause that data type should
not change, else the horn-clause will become false.
Note: In some Prolog systems (e.g. Visual Prolog) the variables
are strongly typed, and programmers do have to specify the
domain type in a “header” file before a predicate is used.
However, they have given some other flexibility that can more
or less get back the advantages of loosely typed languages.
Complex domains
How we wish a problem-space can be defined purely by simple data
types like strings, integers, etc.
Unfortunately, data representation is not as simple as that. How do we
represent stuff which have multiple-components?
For e.g. If we wanted a data type in C that represented the name of a
person, the gender and the religion and the person’s age; we could use this
typedef of a struct:
typedef struct {
char name [30];
char gender[2];
char religion[30];
int age; } aPersonType ;
And whenever we want to use a variable, we can simply use it thus:
main (void) { aPersonType thePerson; /*…. */ }
Functors
Complex domains are represented in Prolog using functors.
Syntatically, a functor is written quite similarly to a predicate.
The earlier “C” example can be written down in Prolog thus:
…
X= aperson(Name,Religion,Gender,Age)
…
The above is part of a horn-clause, where a variable X is bound to the
stated functor.
Note two differences from C:
a) We “made up” the functor the moment we felt the need
for it – right in the middle of our “code” (not in any header
file) and
b) There are variables (words starting with capital letters)
within the functor which are positionally recognized to the
actual real-world data they represent. We do not need struct
indirection (using the –> operator ) to use the components
of the complex domain. We can simply use the internal
functor variables themselves.
Does Prolog really manage control?
There are four important concepts in Prolog that
allow it to control the execution of a program
Binding,
unification,
backtracking,
fail