Knowledge Representation: Practise exam
1. In a proof by contradiction, such as DPLL or tableau, I can prove that a formula F is entailed
by a knowledge base KB by showing that:
● the formula F is unsatisfiable, which implies that it must be entailed by the KB.
● the knowledge base KB and the formula F are together unsatisfiable.
● the knowledge base is unsatisfiable, which implies that the formula F must be entailed.
● the knowledge base KB and the negation of the formula are unsatisfiable.
2. A calculus is called complete w.r.t. the semantics of a logic if, and only, if
● all the formulas it proves are semantically entailed.
● it proves all the correct formulas in finite time.
● it can prove all the semantically entailed formulas.
● all the formulas it proves are tautologies.
3. A calculus is called sound w.r.t. the semantics of a logic if, and only, if
● all the formulas it proves are semantically entailed.
● it proves all the correct formulas in finite time.
● it can prove all the semantically entailed formulas.
● all the formulas it proves are tautologies.
4. A formula is in clause normal form if it is a: .. of .. of …
1: conjunction of 2: disjunctions of 3: literals
5. The semantics (meaning) of a formula in Propositional Logic is determined as:
● a truth value
● a numeric value
● multiple choice
● set membership
6. Consider ((- A v -B) -> (A -> -B)) & (A v B). Which of the following statements are true?
● The sentence is not valid, and thus also not satisfiable
● The sentence is not valid, and thus a contradiction
● The sentence is neither valid, nor satisfiable, nor a contradiction
● The sentence is satisfiable, but not valid
● The sentence is valid, but not satisfiable
7. In the following truth table X1, X2 and X3 stand for possible truth value:
Which of the following statements is correct (multiple answers possible):
● X1 =True, X2 = False, X3 = True, X3 = False, X2 = True, X1 = False
1
, Knowledge Representation: Practise exam
8. Consider the pair of sentences: (-A v -B) -> -(A & B) and ((A -> B) v (B -> C). Which of the
following statements is true? → create truth tables
● There is not enough information to know whether they are equivalent
● Both statements are logically equivalent
● The first statement entails the second, but not vice versa
● They are not logically equivalent
9. Weighted partial MAXSAT formulas. Consider the following statements about geese:
1. all geese are white
2. geese often have two legs
3. It is very likely that a goose is either white or has two legs or both
4. if a goose does not have wings, it cannot fly.
And the following variables:
W stands for goose has wings
X stands for goose is white
Y stands for goose has two legs
Z stands for goose can not fly
Which of the following statements is a faithful representation of the knowledge described
above? → here, ∞ means that its opposite must be true. By satisfying -X, you get the costs.
● F= X & (X v Y, 0.4) & (-Y,5) & (Z v W)
● F= (-X,∞) & (X v Y, 0.4) & (-Y,5) & (Z v W,∞)
● F= (X,∞) & (-(X v Y), 0.4) & (Y,5) & (-(Z v W),∞)
● F= (X,-∞) & (X v Y, 0.4) & (Y,-5) & (Z v W,-∞)
10. Use DPLL procedure to prove or disprove satisfiability of the formula
(X v Y v Z) & ( X v -Y) & (Y v -Z) & (Z v -X) & (-X v -Y v -Z). Label each step which part of the
algorithm you have used.
X = True
(Y v -Z) & Z & (-Y V -Z)
Unit rule: Z = True
Y & -Y → contradiction
Backtracking to beginning: X = False
(Y v Z) & -Y & (Y v -Z)
Y = False
Z & -Z → again contradiction and so UNSAT
11. Give a pseudocode description of GSAT
2
1. In a proof by contradiction, such as DPLL or tableau, I can prove that a formula F is entailed
by a knowledge base KB by showing that:
● the formula F is unsatisfiable, which implies that it must be entailed by the KB.
● the knowledge base KB and the formula F are together unsatisfiable.
● the knowledge base is unsatisfiable, which implies that the formula F must be entailed.
● the knowledge base KB and the negation of the formula are unsatisfiable.
2. A calculus is called complete w.r.t. the semantics of a logic if, and only, if
● all the formulas it proves are semantically entailed.
● it proves all the correct formulas in finite time.
● it can prove all the semantically entailed formulas.
● all the formulas it proves are tautologies.
3. A calculus is called sound w.r.t. the semantics of a logic if, and only, if
● all the formulas it proves are semantically entailed.
● it proves all the correct formulas in finite time.
● it can prove all the semantically entailed formulas.
● all the formulas it proves are tautologies.
4. A formula is in clause normal form if it is a: .. of .. of …
1: conjunction of 2: disjunctions of 3: literals
5. The semantics (meaning) of a formula in Propositional Logic is determined as:
● a truth value
● a numeric value
● multiple choice
● set membership
6. Consider ((- A v -B) -> (A -> -B)) & (A v B). Which of the following statements are true?
● The sentence is not valid, and thus also not satisfiable
● The sentence is not valid, and thus a contradiction
● The sentence is neither valid, nor satisfiable, nor a contradiction
● The sentence is satisfiable, but not valid
● The sentence is valid, but not satisfiable
7. In the following truth table X1, X2 and X3 stand for possible truth value:
Which of the following statements is correct (multiple answers possible):
● X1 =True, X2 = False, X3 = True, X3 = False, X2 = True, X1 = False
1
, Knowledge Representation: Practise exam
8. Consider the pair of sentences: (-A v -B) -> -(A & B) and ((A -> B) v (B -> C). Which of the
following statements is true? → create truth tables
● There is not enough information to know whether they are equivalent
● Both statements are logically equivalent
● The first statement entails the second, but not vice versa
● They are not logically equivalent
9. Weighted partial MAXSAT formulas. Consider the following statements about geese:
1. all geese are white
2. geese often have two legs
3. It is very likely that a goose is either white or has two legs or both
4. if a goose does not have wings, it cannot fly.
And the following variables:
W stands for goose has wings
X stands for goose is white
Y stands for goose has two legs
Z stands for goose can not fly
Which of the following statements is a faithful representation of the knowledge described
above? → here, ∞ means that its opposite must be true. By satisfying -X, you get the costs.
● F= X & (X v Y, 0.4) & (-Y,5) & (Z v W)
● F= (-X,∞) & (X v Y, 0.4) & (-Y,5) & (Z v W,∞)
● F= (X,∞) & (-(X v Y), 0.4) & (Y,5) & (-(Z v W),∞)
● F= (X,-∞) & (X v Y, 0.4) & (Y,-5) & (Z v W,-∞)
10. Use DPLL procedure to prove or disprove satisfiability of the formula
(X v Y v Z) & ( X v -Y) & (Y v -Z) & (Z v -X) & (-X v -Y v -Z). Label each step which part of the
algorithm you have used.
X = True
(Y v -Z) & Z & (-Y V -Z)
Unit rule: Z = True
Y & -Y → contradiction
Backtracking to beginning: X = False
(Y v Z) & -Y & (Y v -Z)
Y = False
Z & -Z → again contradiction and so UNSAT
11. Give a pseudocode description of GSAT
2
