1. Logic & AI
In this chapter, well introduce a topic that is vital not only to the world of artificial intelligence (AI) but also to many other areas of knowledge, such as mathematics, physics, medicine, philosophy, and so on. It has been deeply studied and formalized since ancient times by great philosophers like Aristotle, Euclid, and Plato and by some of the greatest mathematicians of all time. Born in the early ages of mankind, it represents a basic tool that allowed science to flourish up to the point where it is today. It clarifies and straightens our complicated human minds and brings order to our sometimes disordered thoughts.
Logic, this matter to which we have been referring thus far, will be the main focus of this chapter. Well be explaining some of its fundamental notions, concepts, and branches, as well as its relation to computer science and AI. This subject is fundamental to understanding many of the concepts that will be addressed throughout this book. Furthermore, how can we create a decent artificial intelligence without logic? Logic directs rationality in our mind; therefore, how can we create an artificial version of our mind if we bypass that extremely important element (logic) that is present in our natural intelligence and dictates decisions in many casesor, to be precise, rational decisions.
Propositional logic; first-order logic; practical problems where well learn how to create a logic framework, how to solve the SAT (satisfiability) problem using an outstanding algorithm called DPLL , and how to code a first, simple, naive cleaning robot using first-order logic componentsthese topics will get us started in this book.
Note
Logic can be branched into mathematical logic, philosophical logic, computational logic, Boolean logic, fuzzy logic, quantum logic, and so forth. In this book, we will be dealing with computational logic, the field related to those areas of computer science and logic that necessarily overlap.
What Is Logic?
Intuitively we all have a notion of what logic is and how useful it can be in our daily lives. Despite this common sense or cultural concept of logic, surprisingly there is, in the scientific community, no formal or global definition (as of today) of what logic is.
In seeking a definition from its founding fathers, we could go back in time to its roots and discover that the word logic actually derives from the Ancient Greek logike , which translates as concept, idea, or thought.
Some theorists have defined logic as the science of thought. Even though this definition appears to be a decent approximation of what we typically associate with logic, its not a very accurate definition because logic is not the only science related to the study of thoughts and reasoning. The reality is that this subject is so deeply ingrained at the foundation of all other sciences that its hard to provide a formal definition for it.
In this book, well think of logic as a way to formalize human reasoning.
Since computational logic is the branch of logic that relates to computer science, well be describing some important notions on this subject. Ultimately, the concepts described here will be useful throughout this book and in every practical problem to be presented.
Note
Logic is used extensively in computer science: at the processor level by means of logical gates, in hardware and software verification such as floating-point arithmetic, in high-level programming like constraint programming, and in artificial intelligence for problems such as planning, scheduling, agents control, and so forth.
Propositional Logic
In daily life and during our human communication process, we constantly listen to expressions of the language that possess a certain meaning; among these we can find the propositions.
Propositions are statements that can be classified according to their veracity (True or 1, False or 0, etc.) or according to their modality (probable, impossible, necessary, etc.). Every proposition expresses a certain thought that represents its meaning and content. Because of the wide variety of expressions in our language, they can be classified as narratives, exclamatory, questioning, and so forth. In this book, well focus on the first type of proposition, narratives, which are expressions of judgment, and well simply call them propositions from this point on.
The following list presents a few examples of propositions:
Smoking damages your health.
Michael Jordan is the greatest basketball player of all time.
Jazz is the coolest musical genre in the world.
100 is greater than 1.
There are wonderful beaches in Havana.
World War II ended in 1945.
I listen to Stings music.
I will read poems from Spanish poet Rafael Alberti.
These are simple or atomic propositions that we can use in any ordinary day during any ordinary conversation. In order to add complexity and transform them into something a bit more meaningful we can rely on compound propositions , which are obtained by means of logical connectors linking simple propositions like the ones previously listed.
Hence, from the propositions just listed we could obtain the following (not necessarily correct or meaningful) compound propositions .
There are NOT wonderful beaches in Havana.
Smoking damages your health AND 100 is greater than 1.
Michael Jordan is the greatest basketball player of all time OR World War II ended in 1945.
IF Jazz is the coolest musical genre in the world THEN I listen to Stings music.
I will read poems from Spanish poet Rafael Alberti IF AND ONLY IF 100 is greater than 1.
Logical connectives in these cases are shown in capital letters and are represented by the words or phrases NOT , AND , OR , IF THEN and IF AND ONLY IF .
Simple or atomic propositions are denoted using letters (p, q, r, etc.) known as propositional variables . We could name some of the preceding propositions as follows:
p = Smoking damages your health.
q = Michael Jordan is the greatest basketball player of all time.
r = Jazz is the coolest musical genre in the world.
s = 100 is greater than 1.
A proposition that can be either True (1) or False (0) depending on the truth value of the propositions that compose it is known as a formula . Note that a formula can be simple; in other words, it can be composed of a single proposition. Consequently, every proposition is considered a formula.
The syntax of propositional logic is governed by the following rules:
All variables and propositional constants (True, False) are formulas.
If F is a formula then NOT F is also a formula.
If F, G are formulas then F AND G, F OR G, F => G, F <=> G also represent formulas.
An interpretation of a formula F is an assignation of truth values for every propositional variable that occurs in F and determines a truth value for F. Since every variable always has two possible values (True, False or 1, 0) then the total number of interpretations for F is 2n where n is the total number of variables occurring in F.
A proposition that is True for every interpretation is said to be a tautology or logic law .