Logic for Computer Science and Artificial Intelligence E-Book

Ricardo Caferra

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 537

Veröffentlichungsjahr: 2013

Beschreibung

Logic and its components (propositional, first-order, non-classical) play a key role in Computer Science and Artificial Intelligence. While a large amount of information exists scattered throughout various media (books, journal articles, webpages, etc.), the diffuse nature of these sources is problematic and logic as a topic benefits from a unified approach. Logic for Computer Science and Artificial Intelligence utilizes this format, surveying the tableaux, resolution, Davis and Putnam methods, logic programming, as well as for example unification and subsumption. For non-classical logics, the translation method is detailed. Logic for Computer Science and Artificial Intelligence is the classroom-tested result of several years of teaching at Grenoble INP (Ensimag). It is conceived to allow self-instruction for a beginner with basic knowledge in Mathematics and Computer Science, but is also highly suitable for use in traditional courses. The reader is guided by clearly motivated concepts, introductions, historical remarks, side notes concerning connections with other disciplines, and numerous exercises, complete with detailed solutions, The title provides the reader with the tools needed to arrive naturally at practical implementations of the concepts and techniques discussed, allowing for the design of algorithms to solve problems.

Leseprobe

Table of Contents

Preface

Chapter 1: Introduction

1.1. Logic, foundations of computer science, and applications of logic to computer science

1.2. On the utility of logic for computer engineers

Chapter 2: A Few Thoughts Before the Formalization

2.1. What is logic?

2.2. Some historic landmarks

Chapter 3: Propositional Logic

3.1. Syntax and semantics

3.2. The method of semantic tableaux

3.3. Formal systems

3.4. A formal system for PL (PC)

3.5. The method of Davis and Putnam

3.6. Semantic trees in PL

3.7. The resolution method in PL

3.8. Problems, strategies, and statements

3.9. Horn clauses

3.10. Algebraic point of view of propositional logic

Chapter 4: First-order Terms

4.1. Matching and unification

4.2. First-order terms, substitutions, unification

Chapter 5: First-Order Logic (FOL) or Predicate Logic (PL1, PC1)

5.1. Syntax

5.2. Semantics

5.3. Semantic tableaux in FOL

5.4. Unification in the method of semantic tableaux

5.5. Toward a semi-decision procedure for FOL

5.6. Semantic trees in FOL

5.7. The resolution method in FOL

5.8. A decidable class: the monadic class

5.9. Limits: Gödel’s (first) incompleteness theorem

Chapter 6: Foundations of Logic Programming

6.1. Specifications and programming

6.2. Toward a logic programming language

6.3. Logic programming: examples

6.4. Computability and Horn clauses

Chapter 7: Artificial Intelligence

7.1. Intelligent systems: AI

7.2. What approaches to study AI?

7.3. Toward an operational definition of intelligence

7.4. Can we identify human intelligence with mechanical intelligence?

7.5. Some history

7.6. Some undisputed themes in AI

Chapter 8: Inference

8.1. Deductive inference

8.2. An important concept: clause subsumption

8.3. Abduction

8.4. Inductive inference

8.5. Generalization: the generation of inductive hypotheses

Chapter 9: Problem Specification in Logical Languages

9.1. Equality

9.2. Constraints

9.3. Second Order Logic (SOL): a few notions

Chapter 10: Non-Classical Logics

10.1. Many-valued logics

10.2. Inaccurate concepts: fuzzy logic

10.3. Modal logics

10.4. Some elements of temporal logic

Chapter 11: Knowledge and Logic: Some Notions

11.1. What is knowledge?

11.2. Knowledge and modal logic

Chapter 12: Solutions to the Exercises

Bibliography

Index

First published 2011 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd John27-37 St George’s RoadLondon SW19 4EUUKWiley & Sons, Inc.111 River StreetHoboken, NJ 07030USAwww.iste.co.ukwww.wiley.com

© ISTE Ltd 2011

The rights of Ricardo Caferra to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Caferra, Ricardo, 1945-

Logic for computer science and artificial intelligence / Ricardo Caferra.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-84821-301-2

1. Computer logic. 2. Artificial intelligence. I. Title.

QA76.9.L63C34 2011

006.3--dc23

2011014705

British Library Cataloguing-in-Publication Data A CIP record for this book is available from the British Library

ISBN 978-1-84821-301-2

Preface

These notes result from a certain conception of knowledge transmission and from the experience gained after several years of teaching at the Grenoble Institute of Technology (Ensimag).

If the table of contents is interpreted too literally, the task at hand is infeasible: each of the themes developed in the different chapters has been the topic of thousands of pages (books, monographs, articles, popularization books, etc.) published by numerous authors, and some of these pages are of the highest scientific quality. On top of this, we must consider all the information available on the Internet.

The aim of these notes, which is probably ambitious but hopefully not disproportionate, is to attempt to provide a unified overview of the concepts and techniques that are useful in many well-identified domains of modern computer science and artificial intelligence. It is difficult to find all these topics in the same document, and they should also be a good starting point for a reader wishing to explore further topics.

Conceptual rigor will always be preferred to formal rigor. This approach is essential for the transmission of knowledge in the modern world, especially for those domains in which the readers will have to keep acquiring additional knowledge throughout their professional life.

The presentation method of all the topics will always be the same: informal description of the topic under consideration (motivation) historical background examples possible conceptualizations comparative analysis formalization technical aspects.

Of course, the algorithmic point of view is privileged and for almost every considered problem, the goal is to design an algorithm capable of solving it. Examples play a crucial role in these notes: they have been chosen so as to guide in the conceptualization of pertinent abstractions for classes of problems. Digressions and remarks allow for an in-depth view of some of the topics and for the discovery of their relationship with other topics and other domains. Exercises are an essential complement to the topics treated, which cannot be understood and assimilated without solving them (solutions to the exercises are included in the final chapter). It is clear that the material treated here has already been discussed in other books. However, some of these topics are approached in an original manner in this book.

In addition to carrying out their original goal within a university syllabus, these pages will hopefully be agreeable to the reader and will also be an incentive to those wanting to know more and ask further questions.

Chapter 1

Introduction

We briefly analyze the relationship between logic and computer science, by focusing successively on two points of views, in a somewhat natural order. We first underline the importance of logic in the foundations of computer science and how it is used in many computer science domains. Then we explain why logic is useful for computer engineers.

1.1. Logic, foundations of computer science, and applications of logic to computer science

Trying to underline the importance of logic for computer science in the 21st Century is the same as trying to reinvent the wheel. Indeed, in 1969, C.A.R. Hoare wrote:

Computer programming is an exact science, in that all the properties of a program and all the consequences of executing it can, in principle, be found out from the text of the program itself by means of purely deductive reasoning.

More recently, in 1986, Hoare stated that “computers are mathematical machines and computer programs are mathematical expressions”.

Of course, in our defence of logic, we will not make use of arguments relying on Hoare’s renowned expertise, as these arguments may turn out to be fallacious; however, we attempt to shed some light on this kind of sentence and to convince the reader that the importance of logic for computer science is a fact and not a matter of opinion.

Logical concepts have been of prime importance in computer science, and this is still the case nowadays.

Instead of making a potentially tedious enumeration, we shall simply mention two typical concepts of computer science, production rules and formal languages, the origins of which are seldom mentioned and which were, respectively, invented by logicians in 1921 (Post) and 1879 (Frege).

We cannot overstate the importance of studying the foundations and the history of a discipline, as proved by the following quote.

In 1936, A. Turing introduced his notion of an abstract computer, as part of his solution to one of the problems posed by D. Hilbert. Yet, H. Aiken (one of the pioneers of computer science) wrote in 1956 (as quoted by M. Davis):

If it should turn out that the basic logics of a machine designed for the numerical solution of differential equations coincide with the logics of a machine intended to make bills for a department store, I would regard this as the most amazing coincidence that I have ever encountered.

Such a statement would make any undergraduate-level computer scientist smile today.

Another point of view, which does not have such a good press currently, is the philosophical point of view. To convince oneself of its importance, it suffices to recall the role of intuitionisms in computer science (constructive program synthesis, etc.). Several philosophical questions arise naturally in elementary logic (paradox, truth value, possible worlds, intention, extension, etc.).

The importance of temporal logic in modern computer science is undeniable, and is due (including for philosophical motivations) to philosophers-logicians such as A. N. Prior (see section 10.4).

The philosophical point of view is essential to understand a topic, and of course, understanding is crucial from a practical point of view.

An example is the popular term ontology. J. McCarthy borrowed it in the 1970s for philosophy. Currently, in computer science and artificial intelligence (AI) the meaning of this term has connections (even though they may not be that obvious) with its original philosophical meaning, i.e. “Theory of being as such – the branch of metaphysics that deals with the nature of being, as opposed to the study of their memberships or attributes”.

We conclude this section by mentioning three so-called theoretical topics, of the utmost practical importance:

– The NP-completeness of the consistency problem (satisfiability and validity) of classical propositional calculus (SAT), which was proved by Cook in 1971. The wide array of applications of propositional calculus (verification of critical systems, intelligent systems, robotics, constraints, etc.) provides an idea of the importance of this result.

– The study of finite structures, which is closely related to computer science and has numerous applications in databases, multi-agent systems, etc.

– Non-classical logics (modal, temporal and multi-valued logics) are extremely useful in, e.g. program analysis and knowledge representation (in particular in distributed knowledge representation).

1.2. On the utility of logic for computer engineers

Although no one could say for sure which concepts and techniques will be useful to a computer scientist in, say, 10, 20, 30, or 40 years, or even if computer scientists will still be around by then, human beings will probably not have changed that much and will have to cope with an increasingly complex world (at least in developed countries). Abstract concepts will turn out to be more and more useful from the point of view of understanding and efficiency (e.g. it suffices to keep in mind all the advantages – conception, encoding, and updating - that offer very high-level languages).

It is also important to remember that one of the most efficient and rewarding recipes to success from an economical point of view, especially in the modern world, is originality. History shows that the original ideas that have led to important progress in science and techniques are mostly a consequence of an in-depth analysis (and possibly a revision) of principles.

Some of the fundamental notions of logic are used by computer engineers (sometimes with different names and presentations). For example, proposition, definition, semantics, inference, language/meta-language, intention, intension, extension, subclass of formulas, and model.

The notion of proposition from an intuitionistic point of view, for example, represents an intention, a task or a problem. The notion of definition, which has been studied for centuries by logicians, is closely related to that of specification and is used in the process of program construction (folding and unfolding rules).

The role of logic as a language for software specification/verification/development is unchallenged. The notion of semantics leads directly to that of compilation (the assignment of a semantics can be viewed as a translation). Inference is a way of expliciting information and is therefore strongly related to algorithms design. The notion of intention is related not only to that of specification but also to that of system modeling (and not only program modeling), in which it is also necessary to model the environment (including users). The notions of intension and extension are used, for example, in languages such as Datalog (studied in logic and databases). The notion of decidable subclasses of formulas is an example of a problem whose nature changes when one of its subproblems is considered. The notion of models in the context of abduction (which is used for example in diagnostics, or in the understanding of natural languages) is similar to that of empirical sciences.

These are, of course, very general concepts, but let us mention some concrete examples that have extremely important practical applications. The Davis-Putnam method is used, for example, in system validation. The notion (algorithm) of subsumption is used, among other things, in knowledge representation languages.

This notion is essential in so-called ontologies (considered as sets of concepts, relationships between these concepts and means to reason on these concepts), which are widely used in taxonomies and sometimes defined as the explicit specification of a simplified and abstract view of a world we wish to represent.

The notion (algorithm) of unification has been at the intersection of logic and computer science for many years. This algorithm is specified in a very natural way as a set of inference or rewriting rules (see section 4.2). Databases are one of the traditional areas of application of computer science. We can view a relational database as a first-order structure, and first-order logic as a query language (see remark 6.1). The search for increasingly powerful query languages shows the practical need for logics with a greater expressive power.

These examples should be enough to convince the reader of the importance of logic for computer engineers.

To answer those for whom the incentive to learn logic can only come from its recent applications or its relationship to recent applications, we enumerate some applications that have been receiving increasing attention.

The first application is multi-agent systems, which are used in important domains such as robotics, the Internet, etc. These systems can possess extremely complex configurations, and it is becoming necessary to have (formal) techniques to reason in (and on) these systems. The notions and tools that are used include temporal logic, knowledge representation logics, deduction, abduction (i.e. the discovery of hypotheses that are capable of explaining an observation or permit us to reach a conclusion), and the notion of proof that can be used to convince an agent (in particular a human agent) of the pertinence of a piece of information, etc.

Modal logics (temporal logic, dynamic logic, etc.) are used in the industry, for example, to capture reactive behaviors, or in concurrent systems, etc.

An increasing number of computer engineers now work in the economic and financial industry. In these disciplines, the modeling of the actors and their knowledge (beliefs) of the other actors (on the market, in the society) is indispensable for comprehension and decision. Assertions such as “X knows (believes) that Y knows (believes) that Z knows (believes) that…” can be treated formally by knowledge (belief) logics.

In a science popularization article that was published in a well-known journal in May 2001, we could read:

The semantic web is…an extension of the current one.

[…]

For the semantic web to function, computers must have access to structured collections of information and sets of inference rules that they use to conduct automated reasoning.

Logic is very important for natural language processing, which has many applications (e.g. on the Internet, for information retrieval, in question answering systems, etc).

Interdisciplinarity has reached the most recent computer science applications, such as multimedia indexing (i.e. the way of finding multimedia documents in digital libraries), where the roles of semantics and inference are essential.

We conclude this section with some considerations that are more directly related to the technical problems that arise in computer system programming.

– It is possible to prove that a program is not correct, but it is generally impossible to prove that a program is correct using examples. The importance of detecting potential errors in programs (or in integrated circuit designs) is evidenced by two dramatic examples that took place 30 years apart.

The spacecraft Mariner 1 (July 1962) was meant to land on Venus but failed because of an error in the on-board program (a syntactically correct instruction, very close to the intended one, had an entirely different meaning).

Logical techniques have been developed to prove program correctness, to detect programming errors and to construct programs that satisfy a given specification. Most of these techniques can be performed automatically. To reason automatically on a program, it is necessary to have a formal semantics, a formal logical theory, and an automated theorem prover for this theory.

In general, we are interested in verifying specifications, i.e. in proving properties satisfied by the specifications rather than in proving properties satisfied by the programs themselves.

Nowadays, people use more and more certified software. The practical importance of this notion cannot be overstated (it suffices to reflect on the importance of having certified software in a plane or a hospital). More recently (mid-1990’s), errors were discovered in a digital circuit that had already been commercialized. It had been sold by the biggest manufacturer of digital circuits. This error occurred when rare data were provided to the circuit.

This error served as an argument to those who advocated for the necessity of replacing simulation with exhaustive tests by formal verification, so as to prove the correctness of a design before the construction phase.

Theorem proving and model checking are two techniques that enable us to certify the correctness of the aforementioned digital circuits. Logic (both classical and non- classical) plays a key role in these two approaches.

Some resounding successes in software and hardware engineering have proved that these approaches can indeed be applied to real-world problems.

Formal verification had typically been a neglected domain because it was considered too theoretical, but now, it can have a huge financial impact.

– Logic programming consists of using logic as a programming language. The programming language Prolog, as well as others that followed, in particular, constraint logic programming languages, arose naturally from the notions and methods that are studied in logic.

– Some logical paradoxes, in particular, the one named Russell’s paradox, are closely related to the halting problem, i.e. the existence of an algorithm that can decide whether any program provided as an input will halt or not. The impossibility of creating such an algorithm is well known.

– Over the past few years, there has been a boom of computer systems that exhibit an intelligent behavior (such systems are mostly studied in the discipline known as AI).

The principles that are used to design these systems are closely related to classical and non-classical logic. The role of logic in social sciences must not be discarded. Logic is considered as a preferred tool in, e.g. the study of intelligent interactions.

Chapter 2

A Few Thoughts Before the Formalization

2.1. What is logic?

We cannot give a formal answer to this question right away (we will get back to it though). In order to be understood, the answer would require some hindsight on the topic about to be studied.1

Try to understand what mathematics is about by only relying on its definition: mathematics, the science of quantity and space.

To choose an answer would not be very helpful right now, because a lack of criteria and references to concrete cases make it difficult to judge the pertinence of the answer.

A problem that is closely related to the one under consideration inspired the following thought to a famous philosopher (D. Hume):

The fact that ideas should logically entail one another is nothing but a fact, no more understandable by itself than any fact of the material world.

And this one from another less famous philosopher:

A logical formula is the expression of a natural phenomenon, as is gravitation or the growth of a tree.

2.1.1. Logic and paradoxes

Let us return to the history of logic and try to analyze some of the well-known concepts that are involved.

Logical difficulties arose very early in philosophy, religious “treaties”, and literature. Here are two examples:

– the liar’s paradox, due to Eubulides of Miletus (see digression 2.2): I am lying;

– the sentence: this sentence is false;

– the version of the liar’s paradox due to Epimenides of Knossos (6th Century BC): All Cretans are liars.

Are these really paradoxes?

What is a paradox?

Etymologically (15th Century AD): paradox: contrary to common opinion (doxa: opinion, from which originated heterodox and paradox).

Other definitions characterize paradoxes as argumentations (or assertions) that lead to a contradiction (logical paradoxes).

Paradoxes are sometimes associated with results (obtained by using correct reasoning) that are contrary to intuition and common sense, thus provoking surprise and perplexity.

One may also call a paradox a proposition that seems true (false) and is actually false (true).

Consider the following story (an excerpt from a masterpiece of universal literature):

A soldier is given the order to ask every person about to cross a bridge the following question:

(*) “What have you come here for?”

– If the person tells the truth, he is allowed to cross the bridge.

– If the person is lying, he must be hanged next to the bridge.

Someone arrives, and when asked question (*), shows the gallows next to the bridge and replies: “I have come to be hanged in these gallows”.

Imagine how embarrassed the soldier must feel, as he must either allow someone who lied to cross the bridge, or hang someone who was telling the truth!

There also exist paradoxes that occur in board games.

The rule Every rule has exceptions gives rise to problems. As it is a rule, it must admit some exceptions. Which means that there exist rules that do not admit any exception.

Here is another one:

i) The sentence below is false.

ii) The sentence above is true.

If (i) is T then (ii) is F hence (i) is F.

If (i) is F then (ii) is T hence (i) is T.

If (ii) is F then (i) is T hence (ii) is T.

If (ii) is T then (i) is F hence (ii) is F.

2.1.2. Paradoxes and set theory

Perhaps those paradoxes that had the most impact are those that involve set theory: probably because of the importance of set theory in mathematics, and particularly in the foundations of mathematics.

Bolzano introduced (in 1847) the notion of a “set” for the first time:

A set is a collection of elements the order of which is not pertinent, and nothing essential is changed by only changing this order.

But it is Cantor who developed set theory.

In naive set theory, according to Cantor, a set is:

Any collection of objects from our intuition or our thoughts, that are both defined and different.

…But allowing the use of any property to define a set can be dangerous:

There exist sets that do not contain themselves. For example:

The set of prime numbers < 150

There are others that contain themselves. For example:

The set of all ideas.

The catalog of all catalogs.

From a more abstract point of view:

The set of all sets.

It is simple to show that accepting as a set all the sets in the universe (U) leads to a problem.

If this is a set, it must contain itself. But the set of its subsets is also a set, and card. Thus, there would exist a set containing more sets than the universe itself!