Session 13

Session 13

Saturday, 13 January 2018

Today is the last session before the final exam. This session talks about "Logic Programming Language". This session, Miss Yanfi make a mind-map/concept-map for us.

Programs in logic languages are expressed in a form of symbolic logic. Symbolic logic is logic which can be used for the basic needs of formal logic.

Objects in propositions are represented by simple terms: either constants or variables. Atomic propositions consist of compound terms,  elements of a mathematical relation, written like a mathematical function. 

Declarative semantics, there is a simple way to determine the meaning of each statement, simpler than the semantics of imperative languages.

Programming is nonprocedural. Programs do not state now a result is to be computed, but rather the form of the result.

The origin of prolog:

• University of Aix-Marseille (Calmerauer & Roussel)

– Natural language processing.

• University of Edinburgh (Kowalski)

– Automated theorem proving.

Term is a constant, variable, or structure. Constant is an atom or an integer. Atom is symbolic value of Prolog. Atom consists of either a string of letters, digits, and underscores beginning with a lowercase letter or a string of printable ASCII characters delimited by apostrophes.

Variable is any string of letters, digits, and underscores beginning with an uppercase letter. Instantiation is binding of a variable to a value, lasts only as long as it takes to satisfy one complete goal. Structure represents atomic proposition.

Fact Statements and Rule Statements are used for the hypothesis. The different is Fact Statements are headless horn clause and Rule Statements are headed horn clause. Goal Statements are statements that are in form of proposition that we want system to prove or disprove.

Approaches :

• Matching is the process of proving a proposition.

• Proving a subgoal is called satisfying the subgoal.

• Bottom-up resolution, forward chaining.

• Top-down resolution, backward chaining.

• Prolog implementations use backward chaining.

When goal has more than one subgoal, can use either Depth-first search or Breadth-first search. Prolog uses depth-first search, can be done with fewer computer resources. 

Backtracking is reconsidering previous subgoal to find an alternative solution if fail to show truth of one of subgoals in a goal with multiple subgoals. Backtracking can take lots of time and space.

Trace is built-in structure that displays instantiations at each step. Tracing model of execution - four events:

– Call (beginning of attempt to satisfy goal)

– Exit (when a goal has been satisfied)

– Redo (when backtrack occurs)

–Fail (when goal fails)

Application of Logic Programming :

• Relational database management systems.

• Expert systems.

• Natural language processing.

Thats all for today session.