CH 16 Flashcards
Logic that can be used for the basic needs of the formal logic:
Symbolic Logic
Predicate Calculus
Particular form of the symbolic logic that is used for the logic programming.
Terms that represent the object representation:
Constant and Variable
Constant
Symbol that represents an object.
Variable
Symbol that represents different objects at different times.
Atomic Propositions
Consist of compound terms
Compound terms
One element of mathematical relation, written like a mathematical function (mapping and can be written as a table)
Parts of the Compound term
Functor (a function symbol that names the relationship); Ordered list of params (tuple)
Forms of propositions:
Fact & Query
Compound proposition:
two or more atomic propositions
propositions are connected by operators
Antecedent
Right side
Consequent
Left Side
Usage of Propositions:
To discover new theorems that can be inferred from the known axioms and theorems.
Resolution
An inference principle that allows inferred propositions to be computed from the given propositions.
Unification
Finding the values for the variables in the propositions that allows matching process to succeed.
Instantiation
Assigning temporary values to the variables to allow unification to succeed.
If matching process fails during unification, we may need to
backtrack
Proof By contadiction
This theorem is proved by finding an inconsistency.
Hypotheses
A set of pertinent propositions
Forms of Horn Clause
Headed: single atomic proposition on LHS
Headless: Empty LHS (facts)
Declarative Semantic
Simple way to determine the meaning of each statement.
Describing the characterstics of the sorted list rather than the process of rearranging the list.
N/A
University of Aix-Marseille for the origins of the Prolog
Natural Language Processing
University of Edinburgh
Automated Theorem Proving
Term
Constant
Variable
Structure
Constant (Edinburgh Syntax of the Prolog)
An atom or an integer
Atom (Edinburgh Syntax of the Prolog)
Sumbolic value of the Prolog
Atoms consist of:
a string of letters, digits, underscores beginning with the lowercase letter.
a string of printable ASCII characters delimited by the apostrophes
Variable (Edinburgh Syntax for the Prolog)
Any string of letters, digits, and underscore beginning with the uppercase letter
Structure (Edinburgh Syntax for the Prolog)
Represents an atomic proposition
functor(parameter list)
Rule Statements
Headed Horn Clause
For Hypotheses
Conjunction
Multiple terms separated by logical AND operations
Goal Statements
In form of propositons to prove or disprove.
Headless Horn
If a goal is a compound proposition, each of the facts is a
subgoal.
Matching/Satisfying/Resolution
Process of proving a subgoal when a goal is the compound proposition.
Matching
Process of proving a proposition
Approaches to the Matching:
Top-Down resolution: from goal to the sequence that leads to facts in the database. (For a small set of possibly correct answers)
Bottom-Up Resolution: from the facts and goals in the databse to the sequence that leads to goal. (For a large set of possibly correct answers)
Prolog implementations uses ___________
backward chaining
When goal has more than one subgoal,
Depth-first search: find a complete proof of the first subgoal than others
Breadth-first search: work on all the subgoals in parallel
Disadvantages of Backtracking:
Consumes large amount of time and space
Prolog supports
integer var and intger arithmetic
is operator
arithmetic expression == right operand
Variable == left operand
Is ‘is operator’ equal to the assignment operator?
Not
TRACE
Built in structure that displays instantions at each step.
Events in TRACE:
Call
Exit
Redo
Fail
List Structure
Sequence of any number of elements (can be any atom or atomic proposition, or other terms)
The underscore character in list means:
an anonymous variable
Deficiencies of Prolog
Lack of Resolution order control: nondeterministic order of the attempted matches.
The closed-world assumption: The only knowledge is what is in databse.
The negation problem: Anything not stated in the database is assumed to be false.
Intrinsic Limitations: Easy to sort a process in the logic, but it is difficult to actually do (don’t know how to sort)
Applications of Logic Programming
Relational Database management systems
Expert Systems
Natural Language Processing
