book

Logic for Computer Science and Artificial Intelligence

Name: Logic for Computer Science and Artificial Intelligence
Author: Ricardo Caferra
ISBN: 9781848213012

by Ricardo Caferra

August 2011

Intermediate to advanced

544 pages

9h 53m

English

Wiley

Read now

Unlock full access

Cover
Title Page
Copyright
Preface
Chapter 1: Introduction
1.1. Logic, foundations of computer science, and applications of logic to computer science1.2. On the utility of logic for computer engineers
Chapter 2: A Few Thoughts Before the Formalization
2.1. What is logic?2.1.1. Logic and paradoxes2.1.2. Paradoxes and set theory2.1.2.1. The answer2.1.3. Paradoxes in arithmetic and set theory2.1.3.1. The halting problem2.1.4. On formalisms and well-known notions2.1.4.1. Some “well-known” notions that could turn out to be difficult to analyze2.1.5. Back to the definition of logic2.1.5.1. Some definitions of logic for all2.1.5.2. A few more technical definitions2.1.5.3. Theory and meta-theory (language and meta-language)2.1.6. A few thoughts about logic and computer science2.2. Some historic landmarks
Chapter 3: Propositional Logic
3.1. Syntax and semantics3.1.1. Language and meta-language3.1.2. Transformation rules for cnf and dnf3.2. The method of semantic tableaux3.2.1. A slightly different formalism: signed tableaux3.3. Formal systems3.3.1. A capital notion: the notion of proof3.3.2. What do we learn from the way we do mathematics?3.4. A formal system for PL (PC)3.4.1. Some properties of formal systems3.4.2. Another formal system for PL (PC)3.4.3. Another formal system3.5. The method of Davis and Putnam3.5.1. The Davis-Putnam method and the SAT problem3.6. Semantic trees in PL3.7. The resolution method in PL3.8. Problems, strategies, and statements3.8.1. Strategies3.9. Horn clauses3.10. Algebraic point of view of propositional logic
Chapter 4: First-order Terms
4.1. Matching and unification4.1.1. A motivation for searching for a matching algorithm4.1.2. A classification of trees4.2. First-order terms, substitutions, unification
Chapter 5: First-Order Logic (FOL) or Predicate Logic (PL1, PC1)
5.1. Syntax5.2. Semantics5.2.1. The notions of truth and satisfaction5.2.2. A variant: multi-sorted structures5.2.2.1. Expressive power, sort reduction5.2.3. Theories and their models5.2.3.1. How can we reason in FOL?5.3. Semantic tableaux in FOL5.4. Unification in the method of semantic tableaux5.5. Toward a semi-decision procedure for FOL5.5.1. Prenex normal form5.5.1.1. Skolemization5.5.2. Skolem normal form5.6. Semantic trees in FOL5.6.1. Skolemization and clausal form5.7. The resolution method in FOL5.7.1. Variables must be renamed5.8. A decidable class: the monadic class5.8.1. Some decidable classes5.9. Limits: Gödel’s (first) incompleteness theorem
Chapter 6: Foundations of Logic Programming
6.1. Specifications and programming6.2. Toward a logic programming language6.3. Logic programming: examples6.3.1. Acting on the execution control: cut “/”6.3.2. Negation as failure (NAF)6.3.2.1. Some remarks about the strategy used by LP and negation as failure6.3.2.2. Can we simply deduce instead of using NAF?6.4. Computability and Horn clauses

Chapter 7: Artificial Intelligence
7.1. Intelligent systems: AI7.2. What approaches to study AI?7.3. Toward an operational definition of intelligence7.3.1. The imitation game proposed by Turing7.4. Can we identify human intelligence with mechanical intelligence?7.4.1. Chinese room argument7.5. Some history7.5.1. Prehistory7.5.2. History7.6. Some undisputed themes in AI
Chapter 8: Inference
8.1. Deductive inference8.2. An important concept: clause subsumption8.2.1. An important problem8.3. Abduction8.3.1. Discovery of explanatory theories8.3.1.1. Required conditions8.4. Inductive inference8.4.1. Deductive inference8.4.2. Inductive inference8.4.3. Hempel’s paradox (1945)8.5. Generalization: the generation of inductive hypotheses8.5.1. Generalization from examples and counter examples
Chapter 9: Problem Specification in Logical Languages
9.1. Equality9.1.1. When is it used?9.1.2. Some questions about equality9.1.3. Why is equality needed?9.1.4. What is equality?9.1.5. How to reason with equality?9.1.6. Specification without equality9.1.7. Axiomatization of equality9.1.8. Adding the definition of = and using the resolution method9.1.9. By adding specialized rules to the method of semantic tableaux9.1.10. By adding specialized rules to resolution9.1.10.1. Paramodulation and demodulation9.2. Constraints9.3. Second Order Logic (SOL): a few notions9.3.1. Syntax and semantics9.3.1.1. Vocabulary9.3.1.2. Syntax9.3.1.3. Semantics
Chapter 10: Non-Classical Logics
10.1. Many-valued logics10.1.1. How to reason with p-valued logics?10.1.1.1. Semantic tableaux for p-valued logics10.2. Inaccurate concepts: fuzzy logic10.2.1. Inference in FL10.2.1.1. Syntax10.2.1.2. Semantics10.2.2. Herbrand’s method in FL10.2.2.1. Resolution and FL10.3. Modal logics10.3.1. Toward a semantics10.3.1.1. Syntax (language of modal logic)10.3.1.2. Semantics10.3.2. How to reason with modal logics?10.3.2.1. Formal systems approach10.3.2.2. Translation approach10.4. Some elements of temporal logic10.4.1. Temporal operators and semantics10.4.1.1. A famous argument10.4.2. A temporal logic10.4.3. How to reason with temporal logics?10.4.3.1. The method of semantic tableaux10.4.4. An example of a PL for linear and discrete time: PTL (or PLTL)10.4.4.1. Syntax10.4.4.2. Semantics10.4.4.3. Method of semantic tableaux for PLTL (direct method)
Chapter 11: Knowledge and Logic: Some Notions
11.1. What is knowledge?11.2. Knowledge and modal logic11.2.1. Toward a formalization11.2.2. Syntax11.2.2.1. What expressive power? An example11.2.2.2. Semantics11.2.3. New modal operators11.2.3.1. Syntax (extension)11.2.3.2. Semantics (extension)11.2.4. Application examples11.2.4.1. Modeling the muddy children puzzle11.2.4.2. Corresponding Kripke worlds11.2.4.3. Properties of the (formalization chosen for the) knowledge
Chapter 12: Solutions to the Exercises
Bibliography
Index

Overview

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.

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Paradigms of Artificial Intelligence Programming

Publisher Resources

ISBN: 9781118604267Purchase book

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills