Logic Programming

Logic

• The science of reasoning and proof

• It has existed since the time of the Ancient Greek philosophers.

Mathematical Logic or Symbolic Logic

It is the theory of mathematical proofs that began with the work of George Bool and Augustus De Morgan in the middle of the 1800s.

True

TRUE OR FALSE. Logic is closely associated with computers and programming languages in a number of ways.

True

TRUE OR FALSE. Computer circuits are design with the help of Boolean algebra.

True

TRUE OR FALSE. Boolean expressions and data are almost universally used in programming languages to control the actions of a program.

True

TRUE OR FALSE. Logical statements are used to describe axiomatic semantics, or the semantics of programming language constructs.

First-Order Predicate Calculus

• The kind of logic used in logic programming is ___.

• It is a way of formally expressing logical statements — statements that are true or false.

Logical Statements

These are statements that are either true or false.

True

TRUE OR FALSE. The following English statements are logical statements:

1. 0 is a natural number

2. 2 is a natural number

3. For all x, if x is a natural number, then so is the successor of x.

4. 21 is a natural number

Axioms

These are statements that are assumed to be true.

Example of a Translation into Predicate Calculus

natural(0)
natural(2)
For all x, natural(x) -> natural(successor(x))
natural(21)

The first and third statements can be viewed as axioms for the natural numbers: statements that are assumed to be true and from which all true statements about natural numbers can be proved.

Indeed, the second statement can be proved from these axioms, since 2 = successor(successor(0)) and natural(0) → natural ( successor(0)) → natural (successor(successor (0))). The fourth statement, on the other hand, cannot be proved from the axioms and so can be assumed to be false.

Constants

• They are usually numbers or names.

• Sometimes they are called atoms.

Predicates

These are names for functions that are true or false, like Boolean functions in a program.

They can take a number of arguments.

Functions

First-order predicate calculus distinguishes between ____ that are true or false — these examples are the predicates — and all other functions, like successor in the given example, which represent non-Boolean values.

Variables

They stand for unspecified quantities.

Connectives

These include the operations and, or, and not, just like the operations on Boolean data in programming languages.

Implication

An additional connective signified by →.

Equivalence

An additional connective signified by ←→.

Quantifiers

These are operations that introduce variables.

Universal Quantifier

for all is ____ quantifier

Existential Quantifier

• there exists is a _____ quantifier.

• It is used to state the a predicate is true of at least one thing in the universe.

True

TRUE OR FALSE. A variable is introduced by a quantifier is said to be bound by the quantifier.

True

TRUE OR FALSE. It is possible for variables also to be free, that is, not bound by any quantifier.

Punctuation Symbols

These include left and right parentheses, the comma, and the period.

Parentheses

They are used to enclose arguments and also to group operations.

True

TRUE OR FALSE. Parentheses can be left out in accordance with common conventions about the precedence of connectives, which are usually assumed to be the same as in most programming languages.

Terms

They cannot contain predicates, quantifiers, or connectives.

True

TRUE OR FALSE. In predicate calculus, arguments to predicates and functions can only be terms — that is, combinations of variables, constants, and functions.

Translation of Example Statements into First-Order Predicate

mammal(horse);
mammal(human);
for all x, mammal(x) ->
	legs(x, 4) and arms(x, 0) or legs(x, 2) and arms(x, 2)
arms(horse, 0)
not arms(human, 0)
legs(human, 0)

A horse is a mammal.

A human is a mammal.

Mammals have four legs and no arms, or two legs and two arms.

A horse has no arms.

A human has arms.

A human has no legs.

Logic Programming Language

It is a notational system for writing logical statements together with specified algorithm for implementing inference rules.

Logic Program

The set of logical statements that are taken to be axioms can be viewed as the ______, and the statement/s that are to be derived can be viewed as the input that initiates the computation.

Queries or Goals

Inputs provided by the programmer that initiates the computation.

Inference Rules

They are ways of deriving or proving new statements from a given set of statements.

Horn Clause

• It is invented by Alfred Horn.

• A specific type of logical clause with at most one positive literal.

• It is the foundation for many logic programming languages.

Unification

It is the process of matching two terms by finding a substitution that makes them identical.

Resolution

It is an inference rule used to derive new statements from existing ones by eliminating literals.

Negation as Failure

A principle where if a statement cannot be proved true, it is assumed to be false

Closed-Word Assumption

The assumption in logic programming that any statement not known to be true is considered false.

Prolog

• The most widely used logic programming language.

• Uses horn clauses and implements resolution (with backtracking) via a strictly linear depth-first strategy and a unification algorithm.

Predicate

It is a basic unit in Prolog representing a fact or relationship; usually starts with a lowercase letter.

Fact

A statement in Prolog that is unconditionally true.

Query

A question posed to the Prolog system to retrieve or infer information based on the defined facts and rules.

List

A fundamental data structure in Prolog, typically written using square brackets to represent collections of elements.

[x, y, z]