User:Robert Kowalski/sandbox

Problems with the Logic section

1. "Logical inference (or deduction) is the process of proving a new statement (conclusion) from other statements that are already known to be true (the premises)."

Replace "known to be true" by "assumed to be true".

Logic

Formal Logic is used for knowledge representation and reasoning. Formal logic comes in two main forms: propositional logic (which operates on statements that are true or false and uses logical connectives such as "and", "or", "not" and "implies") and predicate logic (which also operates on objects, predicates and relations and uses quantifiers such as "Every X is a Y" and "There are some Xs that are Ys").

Deductive reasoning in logic is the process of proving a new statement (conclusion) from other statements that are given and assumed to be true (the premises). Proofs can be structured as proof trees, in which nodes are labelled by sentences, and children nodes are connected to parent nodes by inference rules.

Given a problem and a set of premises, problem-solving reduces to searching for a proof tree whose root node is labelled by a solution of the problem and whose leaf nodes are labelled by premises or axioms. In the case of Horn clauses, problem-solving search can be performed by reasoning forwards from the premises or backwards from the problem. In the more general case of the clausal form of first-order logic, resolution is a single, axiom-free rule of inference, in which a problem is solved by proving a contradiction from premises that include the negation of the problem to be solved.

Inference in both Horn clause logic and first-order logic is undecidable, and therefore intractable. However, backward reasoning with Horn clauses, which underpins computation in the logic programming language Prolog, is Turing complete. Moreover, its efficiency is competitive with computation in other symbolic programming languages.

Fuzzy logic assigns a "degree of truth" between 0 and 1. It can therefore handle propositions that are vague and partially true. Non-monotonic logics, including Horn clause logic augmented with negation as failure, are designed to handle default reasoning. Other specialized versions of logic have been developed to describe many complex domains (see knowledge representation above).

Recursion in Logic Programming

In the procedural interpretation of logic programs, clauses (or rules) of the form A :- B are treated as procedures, which reduce goals of the form A to subgoals of the form B. For example, the Prolog clauses:

path(X,Y) :- arc(X,Y).
path(X,Y) :- arc(X,Z), path(Z,Y).

define a procedure, which can be used to search for a path from X to Y, either by finding a direct arc from X to Y, or by finding an arc from X to Z, and then searching recursively for a path from Z to Y. Prolog executes the procedure by reasoning top-down (or backwards) and searching the space of possible paths depth-first, one branch at a time. If it tries the second clause, and finitely fails to find a path from Z to Y, it backtracks and tries to find an arc from X to another node, and then searches for a path from that other node to Y.

However, in the logical reading of logic programs, clauses are understood as universally quantified conditionals. For example, the recursive clause of the path-finding procedure is understood declaratively as representing the knowledge that, for any X, Y and Z, if there is an arc from X to Z and a path from Z to Y then there is a path from X to Y. In symbolic form:

$\forall X,Y,Z(arc(X,Z)\land path(Z,Y)\rightarrow path(X,Y)).$

The logical reading is independent of the way the knowledge is used to solve problems. The knowledge can be used top-down, as in Prolog, to reduce problems to subproblems. Or it can be used bottom-up (or forwards), as in Datalog, to derive conclusions from conditions. This separation of concerns is a form of abstraction, which separates declarative knowledge from problems solving methods.

_________________________________________ _________________________________________

definition

See also: Definition § Logic programs

tick

Notes for Recursion (computer science):

1. Recursion solves such recursive problems by using functions that call themselves from within their own code. Replace function.
2. In a properly designed recursive function, with each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached. This assumes a top-down or backward reasoning strategy.
3. Language designers often express grammars in a syntax such as Backus–Naur form; here is such a grammar, for a simple language of arithmetic expressions with multiplication and addition: Note that grammars can be parsed top-down or bottom-up. See Parsing#Types of parsers.
4. This is very similar to an inductive definition of lists of strings; the difference is that this definition specifies how to access the contents of the data structure—namely, via the accessor functions head and tail—and what those contents may be, whereas the inductive definition specifies how to create the structure and what it may be created from. In LP there is no difference between accessing and creating.
5. Some authors classify recursion as either "structural" or "generative". The distinction is related to where a recursive procedure gets the data that it works on, and how it processes that data. This distinction may not arise with logic programs.

__________________________________________________________________________

The text below was originally intended for the Computer program entry. I edited the entry with a much shorter text.

The remainder can be used elsewhere. But where?

____________________________________________________________________

In the simplest case of Horn clauses (or "definite" clauses), all of the H, B₁, ..., B_n are atomic formulae of the form p (t₁ ,…, t_n), where p is a predicate symbol naming a relation, and the t_n are terms naming objects (or individuals). Terms can be constants, variables or composite terms of the form f (t₁ ,…, t_n), where f is a functor (or function symbol) and the t_n are terms. Variables are written as a string beginning with an upper case letter or an underscore.

For example:

• All dragons smoke, or equivalently, a thing smokes if the thing is a dragon:

smokes(X) :-
    is_a_dragon(X).

• A creature smokes if one of its parents smokes:

smokes(X) :-
    is_a_creature(X),
    is_a_parent_of(Y,X),
    smokes(Y).

• A thing X is a parent of a thing Y if X is the mother of Y or X is the father of Y:

 
is_a_parent_of(X, Y):- is_the_mother_of(X, Y).
is_a_parent_of(X, Y):- is_the_father_of(X, Y).

• A thing is a creature if the thing is a dragon:

is_a_creature(X) :-
    is_a_dragon(X).

• Alice is a dragon, and Bob is a creature. Alice is the mother of Bob.

is_a_dragon(alice). 
is_a_creature(bob).
is_the_mother_of(alice, bob).

The example illustrates several features of Prolog and of logic programs more generally: All of the variables in a clause are universally quantified, meaning that the clause holds for all instances in which the variables are replaced by terms not containing variables. Also, all variables are local to the clause in which they occur. So, there is no relationship, for example, between the variables X and Y in the second clause and the variables X and Y in the third clause. (In fact, their roles in the parent relation in the two clauses are actually reversed.)

Notice that the second clause is a recursive (or inductive) definition. It can be understood purely declaratively, without any need to understand how it is executed. The third clause shows how functions, as in functional programming, are represented by relations. Here the mother and father relations are functions in the sense that every individual has only one mother and only one father.

Prolog is an untyped language. However, types (or classes) can be represented by predicates. The fourth clause defines dragon as a subtype (or subclass) of creature.

Computation in Prolog can be regarded as question-answering or theorem-proving. It is initiated by a query or theorem to be proved, and solutions are generated by backward reasoning. For example:

• Answer the query: which thing smokes? Or, equivalently, prove that some thing smokes!

 ?- smokes(X).

All variables in queries are existentially quantified, and execution of the program generates instances of the query that make the query true.

In the case where all clauses are Horn clauses, backward reasoning is performed by using SLD resolution, which is a variant of SL resolution for Horn clauses (or definite clauses). In this example, backward reasoning uses the first clause to reduce the goal to the subgoal:

 ?- is_a_dragon(X).

and it uses the second clause to reduce the goal to the subgoals:

 ?-  is_a_creature(X),
    is_a_parent_of(Y,X),
    smokes(Y).

It solves the subgoal is_a_dragon(X) generated by the first clause, by unifying it with the fact is_a_dragon(alice), instantiating the variable X to the constant alice, giving the solution, X = alice. It solves the three subgoals generated by the second clause, by unifying them with the facts is_a_creature(bob), is_a_parent_of(alice, bob) and smokes(alice), instantiating the variable X to the constant bob, giving a second solution, X = bob.

Goal-reduction, performed in this way, generates a generalised form of and-or tree of goals and subgoals. Prolog explores this tree depth-first, trying different clauses unifying with the same subgoal in the order in which the clauses are written, and trying to solve different subgoals coming from the same clause in the order in which the subgoals are written in the clause. In this example, the computation will generate the solution, X = alice, followed by X = bob.

Prolog programs can also include negative conditions in the body of clauses, as in:

• A creature is healthy if the creature does not smoke:

is_healthy(X) :-
    is_a_creature(X),
    not smokes(X).

Prolog uses negation as failure (NAF) to solve negative subgoals of the form not pby showing that the corresponding unnegated subgoal p fails to hold. For example, the query:

 ?- not healthy(bob).

returns the answer true, because the query

 ?- healthy(bob).

fails, because the subgoal:

 ?- not smokes(bob).

fails, because:

 ?- smokes(bob).

succeeds.

Prolog is a homoiconic language, in which atomic formulae and clauses are represented by composite terms. This is a powerful feature which has many applications, including its use for implementing metainterpreters and for representing and reasoning about propositional attitudes. For example:

• It is prohibited for a creature that the creature teaches deportment if the creature smokes. A creature is ostracised if it is prohibited for the creature that a thing and the thing holds:

prohibited(X, teaches(X, deportment)) :- creature(X), smokes(X).
ostracised(X) :- creature(X), prohibited(X, P), holds(P).

The simplest case in which a proposition P holds is defined by:

holds(A) :- clause(A, true).

where

clause(Head, Body)

is a built-in metapredicate that holds when Head can be unified with the head of a clause and Body can be unified with the corresponding clause body, where Body = true if the clause is a fact.

Given the fact (assumption or premise):

teaches(bob, deportment).

and the query:

ostracised(X).

Prolog derives the answer X = bob

These examples illustrate some of the unique features of Prolog, which distinguish it from more conventional programming languages, and which highlight its use as a logic-based language for knowledge representation and problem solving in Artificial Intelligence.

Prolog has many applications. But many large-scale applications require the use of Prolog's "impure features", which do not have an obvious logical interpretation, or they are implemented in combination with other programming languages. The broad range of Prolog applications, both in isolation and in combination with other languages is highlighted in the Year of Prolog Book , celebrating the 50 year anniversary of Prolog.