Logic Flashcards
What is missing from propositional definite clause logic that is present in full propositional logic?
Disjunction, negation of atoms (biconditionals??)
What is the difference between an interpretation and a model in propositional definite clause logic?
An interpretation is a table of all possible values given the atoms of the clauses, it assigns values to variables.
A model is the set of interpretations that in the knowledge base are true (a model is all the tuples in the interpretation that satisfy the KB given)
Without using the words “model” or “interpretation”, explain what it means to say that K |= g
This means that g is a logical consequence of KB. G is true in all models of KB.
G logically follows from KB or KB entails G.
At its essence, is a proof a syntatic or semantic operation? Why?
It is semantic because you have to relate between symbols.
Define what it means for a proof procedure to be complete
K |= g implies KB |-g
so, if g is true in the KB, then a complete proof will derive g from KB.
A complete proof procedure is a proof procedure that is guaranteed to find an answer if it exists
Define what it means for a proof procedure to be sound
KB |- g implies KB |= g
if the proof derives g from kB, then g must be true in the KB
A sound proof procedure is a proof procedure only generates correct answers with respect to the semantics
Give a proof procedure that was not presented in the class slides
Induction… counter example…??
Explain how in the top-down proof procedure, the rule of inference (called SLD resolution) is performed
The rule of inference is saying if p then q.
- Select an atom from the body
- Choose the atom that corresponds with its body in the KB (the original atom chosen acts as the head in the chosen clause)
- Replace the atom with the body of the chosen atom.
When does the top-down proof procedure terminate?
When the original clause is empty (solution found), or atoms can not be replaced anymore by clauses in the KB (no solution found)
Why might you prefer to use the top-down proof procedure instead of the bottom-up proof procedure.
It allows for backwards searching, only proves atoms that are relevant to the query.
Downside is it might reprove the same atom mutiple times which is slow.
BU is might be faster, as it proves each atom only once, but it proves every atom…
Can be used to prove soundness and completeness of BU
Does it make sense to talk about the truth value of a variable in Datalog? Why or why not?
No, because there are no truth values associated with variables in Datalog, only facts and rules.
For example, parent(“Dee”, “Jan”), parent(“Jan”, “Jamie”) are both facts and a rule could be grandparent(A,C) ←parent(A,B), parent(B,C).
The answer would be grandparent(“Dee”, ”Jamie”)
No because in datalog TD is used to answer the querry, ths talking about the truth value is not useful
