AI 4365 Test 2

[AI-CSP] (AI-208) A variable in a CSP is ___ if all the values in the variable's domain satisfy the variable's unary constraints.

node-consistent

[AI-CSP] (AI-211) Assume a CSP with n variables, each with domain size at most d, and with c binary constraints (arcs). Then the worst-case time-complexity for any algorithm to check n-consistency is ___.

O(e^n) (that is, exponential in n)

[AI-CSP] (AI-212) For a large resource-limited problems with integer values in CSP, domains are represented by upper and lower bounds and are managed by ___.

bounds propagation

[AI-CSP] (AI-211) A CSP is ___ if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any k-th variable.

k-consistent

[AI-CSP] A Constraint satisfaction problem (CSP) consists of three components: a set of variables X and a set of domain D for X, and ___.

a set of constraints C restricting the values for the variables X simultaneously.

[AI-CSP] (AI-211) A CSP is strongly k-consistent if it is k-consistent and is also x-consistent for all x which is greater than ___ and less than ___.

0, k

[AI-CSP] (AI-219) The ___ method backtracks to the most recent assignment in the conflict set.

backjumping

[AI-CSP] (AI-212) The Alldiff constraint in CSP says that all the variables (Vars) involved must have distinct values (as discussed in the book and class). In SWI-Prolog CLP, it is done via ___ for variables Vars.

all_different(Vars)

[AI-CSP] In CSP, ____ is a recursive algorithm. It maintains a partial assignment of the variables. In this algorithm, consistency is defined as the satisfaction of all constraints whose variables are all assigned.

backtracking

[AI-CSP] ____ methods are incomplete satisfiability algorithms. They work by iteratively improving a complete assignment over the variables. At each step, a small number of variables are changed value, with the overall aim of increasing the number of constraints satisfied by this assignment.

local search

[AI-CSP] (AI-208 A CSP network is ___ if every variable is ___ with every other variable.

arc-consistent

[AI-CSP] (AI-214) Applying a standard depth-first search for a CSP problem, a state would be a partial assignment where each action (generating a child node) is to assign a value (from a domain of size d) to a variable. For a CSP with n variables of domain size d, there are only ___ possible complete assignments.

O(d^n). That is, d to the power of n

[AI-CSP] (AI-214) Applying a standard depth-first search for a CSP problem, a state would be a partial assignment where each action (generating a child node) is to assign a value (from a domain of size d) to a variable. In particular, a CSP problem is ___ if the order of application of any given set of actions has no effect on the outcome.

commutative

[AI-CSP] arc-consistency and path-consistency is the most known and used form of ____. Select one best answer.

local consistency

[AI-CSP] (AI-212) One important higher-order constraint is the ___ constraint, sometimes called the Atmost constraint. For example, in a scheduling problem, let P1, P2, P3, P4 denote the numbers of personnel assigned to each of four tasks. The constraint that no more than 10 personnel are assigned in total is written as Atmost(10, P1, P2, P3, P4).

resource

[AI-CSP] (AI-214) Applying a standard depth-first search for a CSP problem, a state would be a partial assignment where each action (generating a child node) is to assign a value (from a domain of size d) to a variable. For a CSP with n variables of domain size d, one may generate a tree with ___ leaves.

O(n! * (d^n)). That is, n factorial times (d to the power of n).

[AI-CSP] In constraint hypergraph a hyper-node represents n-ary ___.

constraints

[AI-CSP] (AI-218) Although forward checking detects many inconsistencies, it does not detect all of them. The problem is that it makes the current variable arc-consistent, but does not look ahead and make all the other variables arc-consistent. The ___ algorithm detects this inconsistency.

MAC

[AI-CSP] (AI-210) ____ consistency tightens down the binary constraints using implicit constraints that are inferred by looking at triples of variables.

path

[AI-CSP] (AI-209) The most popular algorithm for ___ is called AC-3 algorithm.

arc-consistent

[AI-CSP] (AI-225) One efficient heuristic to solve a complicated case of CSP graph is to make it a tree after removal of a subset S of the CSP's variables, and first to find each possible assignment to the variables in S to solve all the constraints on S. Here S is called a ___.

cycle cutset

[AI-CSP] ___ is a type of inference: using constraints to reduce the number of legal values in CSP.

constraint propagation

[AI-CSP] (AI-217) This ___ heuristic can be effective in some cases as it prefers the value that rules out the fewest choices for the neighboring variables in constraint graph.

LCV

[AI-CSP] Constraint satisfaction problems (CSP) on finite domains are typically solved using a form of search. What is not one of the most used techniques in CSP?

global search

[AI-CSP] (AI-216) This ___ heuristic attempts to reduce the branching factor on future choices by selecting the variable that is involved in the largest number of constraints on other unassigned variables.

degree

[AI-CSP] A type of constraint which restricts the value of a single variable is ___.

unary constraint

[AI-CSP] (AI-209) Assume a CSP with n variables, each with domain size at most d, and with c binary constraints (arcs). Then the complexity of AC-3 algorithm for the worst case time is ___.

O(cdd*d)

[AI-CSP] (AI-208) A variable in a CSP is ___ if every value in its domain satisfies the variable's binary constraints.

arc-consistent

[AI-CSP] A constraint involving an arbitrary number of variable is called ___.

global constraint

[AI-CSP] (AI-212) A CSP is ___ if for every variable X, and for both the lower-bound and upper-bound values of X, there exists some value of Y that satisfies the constraint between X and Y for every variable Y.

bounds consistent

[AI-CSP] (AI-212) For example, in an airline-scheduling problem in CSP, let's suppose there are two flights, F1 and F2, for which the planes have capacities 165 and 385, respectively. The initial domains for numbers of passengers on each flight are then D1 = [0, 165] for F1, and D2 = [0,385] for F2. Now suppose we have the additional constraint that two flights together must carry 420 people (F1 + F2 = 420). We reduce the domains to ____

D1=[35,165] and D2=[255,385]

(A ∨ B) ∧ (￢C ∨ ￢D ∨ E) ⊨ (A ∨ B) ∧ (￢D ∨ E) is ___.

unsatisfiable

(Entailment) α is valid if and only if True ⊨ α

True

(Entailment).(A ∧ B) ⇒ C ⊨ (A ⇒ C) ∨ (B ⇒ C) is ___.

True

Select an equivalent statement for each statement below.
¬∃x p(x) ¬∀x p(x) ∃x p(x) ∀x q(x)

C. ∀x ¬p(x) A. ∃x ¬p(x) B. ∃y p(y) D. ∀y q(y)

"(A ⇔ B) ⇔ C" is ___.

satisfiable

(Entailment - True/False) Note: a ⊨ b. This reads "a entails b". M(X) is a model of X.

a ⊨ b if and only if, in every model in which b is true, a is also true.

False

(Entailment - True/False) Note: a ⊨ b. This reads "a entails b". M(X) is a model of X.

a ⊨ b means "a is stronger than b".

True

As we discussed in the class, select the best choice for each statement. a sentence is ___ if it is true for all interpretations.

a setence is ___ if it is true for all interpretations.

a sentence is ___ if it is true for some interpretations.

a sentence is ___ if it is false for all interpretations.

B. tautology A. satisfiable C. unsatisfiable

(Entailment)A ⇔ B ⊨ ￢A ∨ B is ____.

True

(Entailment) For any α, False ⊨ α

True

As we discussed in the class, a sentence is ___ if it is false for all interpretations.

unsatisfiable

"(A ∨ B) ∧ ￢(A ⇒ B)" is ___.

satisfiable

(Entailment)(C ∨ (￢A ∧ ￢B)) ≡ ((A ⇒ C) ∧ (B ⇒ C)) is ___.

True

(Entailment.) (False ⊨ True) is ___.

True

Consider a vocabulary with only four propositions, A, B, C, and D. How many models are there for the following sentence? (A → B) ∧ A ∧ ¬B ∧ C ∧ D

0

(Entailment).(True ⊨ False) is ___.

False

Consider a vocabulary with only four propositions, A, B, C, and D. How many models are there for the following sentence? B ∨ C

12

(Entailment) α ≡ β if and only if the sentence (α ⇔ β) is valid.

True

(Entailment).A ⇔ B ⊨ A ∨ B is ____.

False

Consider a vocabulary with only four propositions, A, B, C, and D. How many models are there for the following sentence? ¬A ∨ ¬B ∨ ¬C ∨ ¬D

15

(Entailment) α ⊨ β if and only if the sentence (α ∧ ￢β) is unsatisfiable.

True

"(A ⇔ B) ∧ (￢A ∨ B)" is ____

satisfiable

If α ⊨ (β ∧ γ) then α ⊨ β and α ⊨ γ

True

(Entailment).(A ∧ B) ⊨ (A ⇔ B) is ___.

True

(Entailment - True/False)Note: a ⊨ b. This reads "a entails b". M(X) is a model of X.

a ⊨ b if, in every model in which a is true, b is also true.

True

What is the clausal form of the following FOL clause [1]?

[1] ∀x [∀y Animal(y) ⇒ Loves(x, y)] ⇒ [∃y Loves(y, x)]

(Animal(F(x)) ∨ Loves(G(x), x)) ∧ (¬Loves(x, F(x)) ∨ Loves(G(x), x))

What is the predicate form of the following statement? "No drug pusher was a VIP"

∀x [d_pusher(x) ⇒ ¬ VIP(x)]

What is the predicate form of the following statement? "All dogs are animals."

∀x (dog(x) => animal(x))

The goal to prove (by refutation) is: "At least one of the custom officials was a drug pusher." What should be the goal in Clausal Form?

¬official(x) ∨ ¬d_pusher(x)

As we discussed in the class, a sentence is ___ if it is true for all interpretations.

valid

As we discussed in the class, a sentence is ___ if it is true for some interpretations.

satisfiable

If α ⊨ γ or β ⊨ γ, then (α ∧ β) ⊨ γ

True

(Entailment - True/False)Note: a ⊨ b. This reads "a entails b". M(X) is a model of X.

a ⊨ b if and only if M(a) ⊆ M(b).

True

The following step in conversion from (1) FOL to (2) Clausal form is to ___.
[1] ∀x [¬ ∀y ¬ Animal(y) ∨ Loves(x, y)] ∨ [∃y Loves(y, x)]
[2] ∀x [∃ y Animal(y) ∧ ¬ Loves(x, y)] ∨ [∃y Loves(y, x)]

Move negation inward

The following step in conversion from (1) FOL to (2) Clausal form is to ___.
[1] ∀x [Animal(F(x)) ∧ ¬ Loves(x, F(x))] ∨ Loves(G(x), x)
[2] [Animal(F(x)) ∧ ¬ Loves(x, F(x))] ∨ Loves(G(x), x)

Drop Universal Quantifier

In the process of proving the goal [G] with KB given below:
[1] ¬food(x) ∨ likes(John, x)
[2] food(Apple)
[3] food(Chicken)
[4] ¬eats(x,y) ∨ killed(x,y)) ∨ food(y)
[5] eats(Bill, Peanuts)
[6] ¬killed(Bill, Peanuts)
[7] ¬eats(Bill,x) ∨ eats(Sue,x)
Which clause(s) is/are used to get the following resolvent: food(Peanuts).

The resolvent of (4 & 5) & 6

What is the predicate form of the following statement? "Some of the drug pushers entered this country and they were only searched by drug pushers"

∃x ∀y [entered_country(x) ∧ d_pusher(x)] ∧ [searched(y,x) ⇒ d_pusher(y)]

Entailment.(A ∨ B) ∧ (￢C ∨ ￢D ∨ E) ⊨ (A ∨ B) is ___.

True

[Prolog] Which of the following selections is correct? This ____ is to add a new fact or rule (clause).

assert/1

[Prolog] For the following Prolog query, X is ____. ?- X=[ 1 | X ].

all of the above

[Prolog] What is the predicate ___ for the following query and its result?
?- ___(2,loves(richard, sarah), X).
X = sarah

arg/3

[Prolog] Negation in Prolog is negation by ____.

failure

[Prolog] Given member/2 where member(X, Y) checks whether X is an element of a list Y, write a Prolog program union/3 where union(A, B, C) will establish a "union" relationship where a list C is a union of a list A and a list B.

union([X|Y],Z,W) :- member(X,Z), union(Y,Z,W).
union([X|Y],Z,[X|W]) :- + member(X,Z), union(Y,Z,W).
union([],Z,Z).

[Prolog] Which of the following selections is correct?This ____(H,B) retrieves clauses in memory whose head matches H and body matches B. H must be sufficiently instantiated to determine the main predicate of the head.

clause/2

[Prolog] Which of the following selections is correct? This ____ tests whether X is bound to a symbolic atom.

atom/1

[Prolog] What would it be the result of the following prolog query?
?- [a, b, c] = [X | Y].

X=a, Y=[b, c]

[Prolog] Which of the following selections is correct? This ____(P) forces P to be a goal; succeed if P does, else fail.

call/1

[Prolog] What is the result of the following query? ?- P=..[parent,jack,mary].

P = parent(jack,mary)

[Prolog] What is the result of the following query? ?- transpose([[1,2,3],[4,5,6],[7,8,9]], Ts).

Ts = [[1, 4, 7], [2, 5, 8], [3, 6, 9]].

[Prolog] Consider the following program (all 5 facts): p(1,3,5). p(2,4,1). p(3,5,2). p(4,3,1). p(5,2,4). What is the result of the following query for Bag? ?- findall(Z,p(X,Y,Z),Bag).

Bag = [5, 1, 2, 1, 4]

[Prolog] Which of the following selections is correct? This ____ tests whether X and Y are currently co-bound, i.e., have been bound to or share same value, or not, respectively.

==, ==

[Prolog] Which of the following selections is correct? This ____ is to delete or remove a fact or rule (clause):

retract/1

[Prolog] Using append/3, what would be the definition for prefix of a list?

prefix(P,L) :- append(P,_,L).

[Prolog-4] As discussed in the class. Select the correct definition of prefix/2 (assuming append/3 provided).

prefix(P, L) :- append(P, _, L).

[Prolog] What is the result of the following query? ?- parent(a,X) = .. L.

L = [parent, a, _X001]

[Prolog] What is the predicate ___ for the following query and its result?
?- ____(f(a,b),F,A).
A = 2 F = f

functor/3

[Prolog] What is the following mystery/2 about (using member/2)?
mystery([X|Y],M,[X|Z]) :- member(X,M), mystery(Y,M,Z).
mystery([X|Y],M,Z) :- + member(X,M), mystery(Y,M,Z).
mystery([],M,[]).

intersection

[Prolog] Write a Prolog program (append/3) where two lists (A and B) are appended to the third list (C) in 'append(A, B, C)'.

append([X|Y],Z,[X|W]) :- append(Y,Z,W). append([],X,X).

[Prolog] Which of the following selections is correct? This ____ tests whether X is bound to a Prolog variable.

var/1

[Prolog] Consider the following mystery/3 predicate.
mystery(X,[X|R],R).
mystery(X,[F|R],[F|S]) :- mystery(X,R,S).
What is the result L of the following query: ?- mystery(1,[1,2,3], L).

L=[2,3]

[Prolog] Write a prolog program (factorial/2) to compute a factorial F of an integer N, where factorial of 0 is 1.

factorial(0,1).
factorial(N,F) :- N>0, N1 is N-1, factorial(N1,F1), F is N * F1.

[Prolog] What would it be the result of T for the following prolog query?
?- [a, b, c] = [X, Y, Z | T].

T=[ ].

[Prolog] Explain the behavior or goal of the following program (mystery/3). What would be the result of the query below?
mystery(A,B) :- mystery(A,[],B).
mystery([X|Y],Z,W) :- mystery(Y,[X|Z],W).
mystery([],X,X).
?- mystery([1,2,3], A).

A = [3,2,1].

[Prolog] What is a correct definition of negation in Prolog?

not(P) :- call(P), !, fail. not(P).

[Prolog] Consider the following op/3 predicate. ?- op(500,yfx,'#'). What is the result of the following query? ?- (A#B) = 1#2#3#4.

A = 1 # 2 # 3. B = 4.

[Prolog] Write a prolog program (factorial/3 or factorial(N,A,F)) to compute a factorial F of an integer N, in tail-recursion with an accumulating variable A.

factorial(0,F,F).
factorial(N,A,F) :- N > 0, A1 is N*A, N1 is N -1, factorial(N1,A1,F).

[Prolog] What is it called for the variable matching process in Prolog?

unification

[Prolog] Consider the following bachelor Prolog program.
bachelor(P) :- male(P), not married(P).
male(henry). male(tom).
married(tom).
What would be the incorrect result of a query (query => result)?

?- male(P). => false.

[Prolog] Consider the following program (all 5 facts): p(1,3,5). p(2,4,1). p(3,5,2). p(4,3,1). p(5,2,4). What is the result of the following query for Bag? ?- setof(Z,X^Y^p(X,Y,Z),Bag).

Bag = [1, 2, 4, 5]