Exam 2 Flashcards
What is logic programming?
A collection of facts and rules. Facts are logical statements assumed to be true (axioms), and rules are logical statements that derive new facts from existing facts that support the premise.
What is forward-chaining?
Start with the facts and work forwards towards the query (the goal).
What is backward-chaining?
Start with the query (the goal) and move backwards saving any facts that supports the goal
Data-Driven vs. Goal-Driven Search
Data-driven is best for automatic processing such as object recognition, routine decisions; may do lots of work that is irrelevant to the goal. Goal driven is more appropriate for problem solving such as where are my keys? How do I get into a PhD program? Goal driven is often used in expert systems that are designed for medical diagnosis or other types of diagnostic systems
What is first-order predicate logic?
Boolean logic assumes the world contains facts that are either true or false, predicate logic assumes the world contains objects and relationships.
What are some symbols in predicate calculus?
A constant, a variable, a function, or a predicate. Constants being with lowercase letters, variables being with an uppercase letter, the arity of a function is the number of arguments of the functor, and a predicate names a relationship between objects in the world.
Everyone likes ice cream.
There does not exist someone who doesn’t like icecream.
There exists a person that likes broccoli is the same as?
It is not true that no one likes broccoli
“If it doesn’t rain on Monday, Tom will go to the mountains.”
not(weather(rain, monday) → go(tom, mountains))
Emma is a Doberman pinscher and a good dog.
is_a(emma, doberman) good_dog(emma)
“All basketball players are tall.”
X (basketball_player(X) → tall(X))
“Nobody likes taxes.”
not( X likes(X, taxes))
What are prolog statements constructed from?
Terms. A term is a constant, a variable, or a structure. A constant is an atom or an integer. An an atom is a string of letters, digits, or underscores that begins with a lowercase letter.
What is a variable in ProLog?
A variable is any string of letters, digits, or underscores that begins with an uppercase letter or an underscore
Variables are not bound to types by declarations
The binding of a value to a variable (hence its type) is called an instantiation
Instantiation occurs as a result of resolution
Instantiations last only as long as it takes to satisfy one complete goal, which involves the proof or disproof of one proposition
What is a headless horn clause?
The headless Horn clause is an unconditional assertion (a fact, or a proposition that is assumed to be true). For example,
male(bill).
What is a headed horn clause?
Represents a rule, such that a conclusion can be drawn if a given set of conditions is satisfied
consequence :- antecedent_expression
i.e. ancestor(mary, shelley) :- mother(mary, shelley)
When are variables in prolog assumed to universally quantified vs existentially quantified?
Variables in the consequence are assumed to be universally quantified
Variables in the antecedent expressions are assumed to be existentially quantified
What is the syntax of a goal statement?
Headless Horn statement.
Prolog to append a list to another list to produce a third list:
append( [ ], B, B).
append( [H | T], A, [H | L] ) :- append(T,A,L).
What is the “is” operator in prolog?
It takes an arithmetic expression as its right operand and a variable as its left operand. X is 1+2.
X = 3.
Will 1+2 is 4-1 work?
No, because first argument 1+2 is already instantiated.
Will X is Y work?
No, Y must already be instantiated.
Will Y is 1+2, X is Y. work?
Yes, if y is instantiated by the time it is needed. Y =3, X =3
What is the prolog tracing model?
The prolog tracing model of execution has four events: - call (beginning of attempt to satisfy goal), Exit (when a goal has been satisfied), Fail (when goal fails), Redo (when backtracking occurs).
Explain backtracking in Prolog.
Prolog searches the database in the order that the statements are listed for each attempt to satisfy a goal. Attempts to satisfy sub-goals left to right after matching a goal to a fact/rule in database. Failure to satisfy a sub-goal undoes unification (uninstantiates variables) and the database search is resumed.
The search for a proof (resolution) in prolog proceeds in a depth-first manner. Can take lots of time and space because may find all possible proofs to every subgoal.
How can we make prolog more efficient?
Allows the user to control the ordering of pattern matching during backtracking for resolution. If a user knows that certain rules are much more likely to succeed than the others, then place those rules before the others.
What is the cut operator?
A goal that is always satisfied immediately, it cannot be resatisified through backtracking. Side effect is that sub-goals that come after it in a compound goal cannot be re-satisfied through backtracking.
What is the closed-world assumption?
Prolog can prove that a given goal is true, but it can never provate that a goal is false. When the system receives a query and the database does not have information to prove it is true, the query is assumed to be false.
What is the negation problem?
The prolog operator not is not the same as the logical “not”. Consider not(X = Y), if this statement succeeds it does not necessarily mean that X is not equal to Y, it means that resolution cannot prove from the database that X is the same as Y.
Resolution requires that the problem be expressed in what?
Conjunctive normal form.
What is the conjunctive normal form?
It is a conjunction of disjunctions. X1 Λ X2 Λ X3 Λ … Λ Xn where each clause, Xi, is of the form: Y1 v Y2 v Y3 v … v Yn The Ys are literals For example, A Λ (B v C) Λ (¬A v ¬B v ¬C v D) is in conjunctive normal form
Convert A -> B to CNF
not A v B
Convert not(A ^ B) to CNF
not A v not B
What is a horn clause?
A disjunctive clause that has at most one positive literal: ¬B v ¬C v ¬D v ¬E v A …
This can also be written as an implication:
B Λ C Λ D Λ E → A
In PROLOG, this is written:
A :- B, C, D, E
Know the resolution rule
Let us resolve: {(¬A,B), (¬A,¬B,C), A, ¬C}
We begin by resolving the first clause with the second clause, thus eliminating B and ¬B:
{(¬A,C), A, ¬ C}
{C, ¬C}
Now we can resolve both remaining literals, which gives falsum (a contradiction):
^
If we reach falsum, we have proved that our initial set of clauses were inconsistent
This is written:
{(¬A,B),(¬A,¬B,C),A,¬C} ╞ ^
Proof by contradiction
Negate its conclusion, convert it to clause form, and then derive falsum using resolution. If we derive falsum, then our clauses were inconsistent, meaning the original argument was valid, since we negative its conclusion.
Prove the following 3 statements using proof by contradiction:
(A Λ ¬B) → C
A Λ ¬ B
C
Negate the conclusion and convert to clauses:
{(¬A,B,C), A, ¬B, ¬C}
Now resolve:
{(B,C), ¬B, ¬C}
{C, ¬C}
^
We have reached falsum, so our original argument was valid
Prove or disprove the following:
A → B, B → C, C → D, D → E F
A→F
First, we negate the conclusion to give (A→F)
Next we convert to clause form:
D → E F ≡ D (E F) and (A → F) ≡ (A F) ≡ A F
So our clauses are: {(A,B), (B,C), (C,D), (D,E,F), A, F}
This will resolve to {E}; we cannot reach falsum. Hence, we can conclude that our original conclusion was not valid. (You can prove this for yourself by using a truth table.)
Where does Unification come in to Resolution?
To complete the resolution of clauses, we often need to make substitutions. For example:
{ (p(W, X)), (¬p(Y, Z)) }
To resolve, we need to substitute Y for W, and Z for X, in other words, {Y/W, Z/X}, giving:
{ (p(Y, Z)), (¬p(Y, Z)) }
These resolve to give falsum (a contradiction
What are some issues with unification?
A constant is considered a “ground instance” and cannot be replaced
A variable cannot be unified with a term containing the variable
For example, X cannot be replaced with p(X) as this creates an infinite expression: p(p(p(p(…X)))
Unifying substitutions must be made consistently across all occurrences within the scope of the variable in both expressions being matched
Once a variable is bound to a constant, that variable may not be given a new binding in a future unification
Why have a methodology or notation for language semantics?
Programmers need to know what statements mean
Compiler writers must know exactly what language constructs do
Correctness proofs would be possible
Compiler generators would be possible
Designers could detect ambiguities and inconsistencies
What are some reasonable semantic rules that cannot be checked at reasonable cost, either statically, or by compiler-generated code at runtime?
All loops should terminate. Termination is undecidable.
Concurrent programs should be free from race conditions. Also undecidable.
Improper use of variants. Decidable but difficult.
Use of un-initialized variables. Decidable but difficult.
Deadlock freedom. Decidable but difficult.
The requirement that a program be unable to tell the difference between reference and value-result parameters. Decidable but difficult.
What is a predicate?
A souped up boolean since it can indicate relationships.
Why doesn’t sum = sum + number work?
- If sum is already instantiated, it cannot be reinstantiated. 2.If it is not instantiated, we cannot do unification on it.
What is call by value?
Copy going in
What is call by result?
copy going out
What is value result?
copy going in and copy going out.
What is call by reference?
pass a pointer
What is call by name?
re-evaluate actual parameter on every use. For simple variables, this is the same as call by reference. For actual parameters that are expressions, the expression is evaluated on each access.
