Fundamentals of Logic Programming - Vocabulary Flashcards

Fundamentals of Logic Programming

• Axioms (Facts and Rules)
  • Facts: Statements that are assumed to be true → represent basic knowledge.
  • Rules: Logical implications or relationships between facts → define how new information can be inferred.
• Goal Statements
  • Statements or queries that the programmer wants to prove or satisfy → the desired outcomes or information sought.
• Axioms as a Theory
  • The collection of facts and rules forms the knowledge base or theory of the logic program → the initial set of assumptions.
• Goal Statements as Theorems
  • The theorems or propositions that the programmer aims to prove or derive from the given axioms.

Fundamentals of Logic Paradigm (cont.)

• Computation as Deduction
  • Computation involves deducing new information from the axioms to prove the goal statements → The process is often based on logical inference.
• Interpreter and Inference
  • The interpreter is responsible for finding a set of axioms and inference steps that lead to the proof of the goal statements → deduce conclusions by performing logical inference.
• Proof
  • The successful determination of a collection of axioms and inference steps that imply the goal statements constitutes a proof → The interpreter's goal is to find a valid proof.
• GOAL: find a set of facts and rules that logically entail the desired outcomes.

Relational Programming In Prolog

• In Prolog, a relation is specified as a predicate, and the programming paradigm is often referred to as relational programming.
• A predicate is a tuple: a relationship that defines a logical connection between its arguments.
• Contrast to Functional Programming:
  • In functional programming, functions map input values to output values, and the result is deterministic.
  • In Prolog, relations express facts or logical connections without emphasizing the idea of computation as a mapping of inputs to outputs.
  • E.g., brother(sam, bill). brother(sam, bob). → brother maps “sam” to two different range elements which is a relation (not a function).
• N-ary Relations
  • Relations in Prolog can be n-ary → involve more than two entities.
  • E.g., family(jane, sam, [ann, tim, sean]) → family relation involves three entities: Jane, Sam, and a list of children.

Defining Relations (predicates) by Facts

• Example facts:
  • parent(tom, bob).
  • parent(pam, bob).
  • parent(tom, liz).
  • parent(bob, ann).
  • parent(bob, pat).
  • goodperson(bob).
  • likes(tom, apples, oranges).
• Notes:
  • parent is the name of a relation (a predicate) expressed as a fact or rule.
  • Facts are base assertions about relationships between entities.

Directionality in Parameters

• In traditional languages (C, Java, Python), parameters have a directional interpretation (in/out).
• In Prolog, parameters are not strictly categorized as in or out; variables can be used in both input and output positions.
• When a query is executed, the Prolog engine tries to bind variables to values to satisfy rules and facts.
• Example analogy (C-like) and Prolog rule:
  • Square example:
  • Prolog:
  • prolog square(X, Result) :- Result is X * X.
  • Here, both X and Result can be considered in and out parameters.
• Query behavior examples:
  • Given the fact square(2, 4).
  • Query: square(X, 4) → Prolog binds X = 2.
  • Query: square(2, X) → Prolog binds X = 4.

Example: Knowledge Base 1

• Facts:
  • woman(mia).
  • woman(jody).
  • woman(yolanda).
  • playsAirGuitar(jody).
  • party.
• Queries and expected results:
  • ?- woman(mia). → true
  • ?- playsAirGuitar(jody). → true
  • ?- playsAirGuitar(mia). → false
  • ?- tattoed(jody). → ERROR: Unknown procedure: tattoed/1 (DWIM could not correct goal)
  • ?- party. → true

Example: Knowledge Base 2

• Facts:
  • happy(yolanda).
  • listens2music(mia).
• Rules:
  • listens2music(yolanda) :- happy(yolanda).
  • playsAirGuitar(mia) :- listens2music(mia).
  • playsAirGuitar(yolanda) :- listens2music(yolanda).
• Note: The rule syntax uses head :- body (body is a conjunction of goals).
• The line
  • fact rule rule head body :- if (implication)
  • indicates a generic layout where a fact is a rule with no body and a rule has a body.

Knowledge Base 2: Query results

• ?- playsAirGuitar(mia). → true
• ?- playsAirGuitar(yolanda). → true

In Prolog, a clause is a fundamental unit

• A clause consists of facts and rules and defines relationships and conditions as logical statements.
• Facts: simple statements about relationships between entities (base-level knowledge).
• Rules: express relationships based on conditions; consist of a head and a body:
  • head :- body. where the head is a relation and the body contains conditions that must be satisfied.
• Example: There are five clauses in a knowledge base: two facts and three rules
  • happy(yolanda).
  • listens2music(mia).
  • listens2music(yolanda) :- happy(yolanda).
  • playsAirGuitar(mia) :- listens2music(mia).
  • playsAirGuitar(yolanda) :- listens2music(yolanda).

Predicates in Prolog

• A predicate is a logical statement or relationship that defines a condition or property.
• Predicates consist of terms, which can be atoms, variables, or complex structures.
• Key components:
  • Predicate Name: identifies the relationship; usually starts with a lowercase letter.
  • Arguments: one or more, which can be constants, variables, or complex terms.
  • Arity: the number of arguments.
• Predicates are defined by clauses (facts or rules).
• Prolog interpreter uses these predicates to answer queries and derive conclusions based on the defined logic.

Predicates: Example KB (Predicates cont.)

• Three predicates in this knowledge base: happy/1, listens2music/1, playsAirGuitar/1
• Facts:
  • happy(yolanda).
  • listens2music(mia).
• Rules:
  • listens2music(yolanda) :- happy(yolanda).
  • playsAirGuitar(mia) :- listens2music(mia).
  • playsAirGuitar(yolanda) :- listens2music(yolanda).

Example: Knowledge Base 3 (queries and results)

• Facts:
  • happy(vincent).
  • listens2music(butch).
• Rule:
  • playsAirGuitar(vincent) :- listens2music(vincent), happy(vincent).
  • playsAirGuitar(butch) :- happy(butch).
  • playsAirGuitar(butch) :- listens2music(butch).
• Queries:
  • ?- playsAirGuitar(vincent). → false
  • ?- playsAirGuitar(butch). → true

Expressing Disjunction (or) in Prolog

• Disjunction is expressed using a semicolon ';'.
• Example (from KB 3 interaction):
  • playsAirGuitar(butch) :- happy(butch); listens2music(butch).
  • This represents: playsAirGuitar(butch) if either happy(butch) or listens2music(butch).

Logic Operators in Prolog

• Operators commonly used:
  • Implication: :-
  • Conjunction: ,
  • Disjunction: ;
• Negation: not(P) (or \+ P in many Prolog dialects; the transcript uses not(listens2music(vincent))).

Variables in Prolog

• Variables represent unknown values or placeholders within predicates.
• Format:
  • Variables are strings of letters, digits, and underscores; must begin with a capital letter or an underscore.
  • Examples: X, Sister, _, _thing, y47, Firstname, Z2
• Don\'t-Care Variable (‘_’): used when the specific value is not relevant.
  • Example: married(john, _).
• This indicates that John is married, but the spouse is not specified.

Comments in Prolog

• Single-Line Comment: Anything after % on the same line.
• Multi-Line Comment: /* … */ over multiple lines.
• Examples:
  • % This is a single-line comment in Prolog
  • /* This is a
    multi-line comment in Prolog. */

Atoms

• An atom is a basic data type representing a constant.
• Atoms are names/labels/identifiers consisting of letters, numbers, and underscores; start with a lowercase letter or be quoted in single quotes.
• Examples: butch, bigkahunaburger, playGuitar, 'Vincent', 'Five dollar shake', '@$%'.

Numbers

• Prolog supports integers and floating-point numbers.
• Integers: 12, -34, 22342 (optionally signed).
• Floating-point: 34573.3234, -0.001, 3.1415e-3 (exponent with 'e').

Arity

• Arity = the number of arguments a predicate takes.
• Unary predicate: arity 1; binary predicate: arity 2.
• Predicates are usually written as name/arity (e.g., loves/2).
• Predicates with different arities are distinct: loves/2 and loves/3 are different predicates.

Example: Arity in a Knowledge Base

• KB defines:
  • loves(vincent, mia).
  • happy(yolanda).
  • listens2music(mia).
  • listens2music(yolanda) :- happy(yolanda).
  • playsAirGuitar(mia) :- listens2music(mia).
  • playsAirGuitar(yolanda) :- listens2music(yolanda).
• This KB demonstrates multiple predicates with fixed arities and how they are used in rules.

Example: Queries and Predicates (KB with multiple arities)

• The following illustrates a mixture of unary and binary predicates:
  • loves(vincent, mia) (loves/2)
  • loves(marsellus, mia) (loves/2)
  • loves(pumpkin, honey_bunny) (loves/2)
  • loves(honey_bunny, pumpkin) (loves/2)
• Query example:
  • ?- woman(X).
  • Possible results: X = mia; X = jody; X = yolanda (depending on the loaded KB).
• Example traces from the transcript:
  • ?- woman(X).
  • X = mia
  • ?- woman(X).
  • X = mia; X = jody
  • ?- woman(X).
  • X = mia; X = jody; X = yolanda

Conjunctive Queries

• A conjunctive query asks for bindings that satisfy multiple goals simultaneously.
• Example:
  • Conjunctive query: ?- loves(marsellus, X), woman(X).
  • If X is a person who is loved by Marsellus and is a woman, Prolog returns X as a solution.
  • From the transcript: X = mia.

Disjunctive Queries

• Disjunctive queries ask for values that satisfy at least one of several alternatives.
• Example: ?- loves(pumpkin, X); woman(X).
• From the transcript: X = honey_bunny; X = mia; X = jody; X = yolanda.

Rules and Variables in Prolog

• Rules allow the interpreter to infer things from known facts.
• Example rule templates (variables common):
  • employs(X) :- employs(Y, X).
  • grandmother(A, C) :- mother(A, B), mother(B, C).
  • grandmother(A, C) :- mother(A, B), father(B, C).
• These illustrate the use of variables in the head and body of rules.

Variables in Prolog Rules (Example)

• Facts:
  • rainy(dallas).
  • cold(dallas).
  • rainy(houston).
• Rule:
  • snowy(X) :- rainy(X), cold(X).
• Query:
  • ?- snowy(A).
  • A = dallas.

Knowledge Base 5: Jealousy and Horn Clauses

• Facts:
  • loves(vincent, mia).
  • loves(marsellus, mia).
  • loves(pumpkin, honey_bunny).
  • loves(honey_bunny, pumpkin).
• Rule:
  • jealous(X, Y) :- loves(X, Z), loves(Y, Z).
• Query:
  • ?- jealous(marsellus, W).
  • W = vincent; W = marsellus

Horn Clauses

• Horn clauses are a specific form of logical expressions used in logic programming.
• A Horn clause defines a rule in Prolog: H :- B1, B2, …, Bn or H :- B1; B2; …; Bn
• Here: H is the head (a single goal/predicate).
• B1, B2, …, Bn (or B1; B2; …; Bn) are the body (a conjunction or disjunction of goals).
• ":-" can be read as "if" or "is implied by".
• If there are no body predicates on the right side, the Horn clause becomes a fact.

Prolog Programming Essentials

• Prolog Programming Model: Facts and Rules, Queries.
• Principle of Resolution
  • The process of resolving a query by searching for applicable rules and facts to prove the query true or false.
  • Involves pattern matching and unification.
• Unification
  • The process of finding substitutions for variables to make two terms identical.
  • When a query is posed, Prolog attempts to unify the terms in the query with terms in the program's facts and rules.
• Execution Order
  • Depth-first search strategy.
  • The order of clauses in the program is crucial and affects backtracking behavior.

Prolog Programming Essentials (cont.)

• Backtracking
  • A key feature allowing exploration of alternative paths when a search path fails.
• Other important aspects:
  • Arithmetic Operations: Allow numerical calculations within rules.
  • Lists: Fundamental data structure for sequences.
  • Cut: A powerful but complex feature to control backtracking and commit to choices.
  • Negation: Express negation to state that a goal should not be true.

A Prolog Program about Food

• Facts:

  • indian(curry).
  • indian(dahl).
  • indian(tandoori).
  • indian(kurma).
  • chinese(chow_mein).
  • chinese(chop_suey).
  • chinese(sweetandsour).
  • italian(pizza).
  • italian(spaghetti).
  • mild(dahl).
  • mild(tandoori).
  • mild(kurma).

• Rules:

  • likes(sam, Food) :- indian(Food), mild(Food).
  • likes(sam, Food) :- chinese(Food).
  • likes(sam, Food) :- italian(Food).
  • likes(sam, chips).

• This program demonstrates how to encode a domain (food preferences) with facts about cuisines and attributes, and rules that derive likes/2 relationships.

Principle of Resolution (detailed example)

• If C1 and C2 are Horn clauses, and the head of C2 matches one of the terms in the body of C1, then the term in C1 can be replaced with C2.
• Example:
  • C1: likes(sam,Food) :- indian(Food), mild(Food).
  • C2: indian(dahl).
  • C3: mild(dahl).
• By applying resolution and instantiating Food to dahl, we replace the first and second terms in C1 with C2 and C3 respectively, yielding the goal likes(sam, dahl).

Unification

• The process of associating (binding) variables and values is accomplished through unification.
• Variables that receive a value during this process are instantiated.
• Unification rules:
  • A constant unifies only with itself.
  • Two structures unify if and only if they share the same predicate and the same number of arguments, and corresponding arguments unify recursively.
  • A variable can unify with anything (other variables, constants, or complex structures).

Unify Recursively

• Unification extends to sub-components within compound terms.
• Example:
  • siblings(X, Y) :- father(Z, X), father(Z, Y).
  • Query: ?- siblings(jim, ann).
  • Prolog unifies X with jim, Y with ann, and Z with their common father, illustrating recursive unification within rule structures.

Unification - Equality

• Equality is tied to unification; an equality goal uses the operator =.
• Examples:
  • ?- dahl = dahl. → true.
  • ?- dahl = curry. → false.
  • ?- likes(Person, dahl) = likes(sam, Food). → Person = sam, Food = dahl.
  • ?- likes(Person, Food) = likes(sam, Food). → Person = sam.

End of Prolog Essentials (summary)

• Prolog programs consist of facts, rules, and queries.
• The interpreter uses unification and resolution to answer queries.
• Understanding arity, predicates, and structures is essential for building correct knowledge bases.
• Practice with: defining relations, querying with conjunctions and disjunctions, and exploring the effects of backtracking and the execution order.