Chapter 10

Question 1

What is the consequence operator of TpX

Answer 1

The consequence operator of TpX = {h(r) |r ∈ P, B(r)+ ⊆ X}
The heads of the rules of the program, where rules exist in the positive body.

Question 2

Y contains X implies TpX ⊆ TpY

Answer 2

false. it implies
TpY ⊆ TpX

Question 3

X is a stable model of P iff X = Cn(pX)

Answer 3

the consequences of (pX) is a stable model.

Question 4

X ⊆ Y implies pY ⊆ pX implies Cn(pY) ⊆ Cn(pX)

Answer 4

X is contained within Y implies the stable model Y of P is contained in the stable model X of P which implies the consequences of pY are contined in the consequences of pX

Question 5

What is P^Y

Answer 5

P^Y is the reduct of P with respect to Y

Question 6

What is Propagation via approximation?

Answer 6

Duducing or updating information about the possible values based on the constraints itteritvely to narrow down the search space. Narrowing down the search space by approximation and deducing new information.

Question 7

What is a Nondeterministic polynomial time problem?

Answer 7

A problem is called NP (nondeterministic polynomial)if its solution can be guessed and verified in polynomial time; nondeterministic means that no particular rule is followed to make the guess.

Question 8

what is Search by propagation and case-analysis?

Answer 8

When a variable is assigned a value the constraints involving that variable my impose restrictions on other variables.
Case analysis involves systematically considering and anlyizing different possilble cases to solve a problem.

Question 9

Let a be an atom and X be a set of atoms

Answer 9

Let a be an atom and X be a set of atoms
• For a positive disjunctive logic program P
• deciding whether X is a stable model of P is co-NP-complete
• deciding whether a is in a stable model of P is NPNP-complete
• For a disjunctive logic program P
• deciding whether X is a stable model of P is co-NP-complete
• deciding whether a is in a stable model of P is NPNP-complete
• For a disjunctive logic program P with optimization statements
• deciding whether X is an optimal stable model of P is co-NPNP-complete
• deciding whether a is in an optimal stable model of P is ∆p3-complete
• For a propositional theory Φ
• deciding whether X is a stable model of Φ is co-NP-complete
• deciding whether a is in a stable model of Φ is NPNP-complete

Question 10

For any programP, if (L’,U’) is the result of expand p(L,U), and there is a stable model X such that L is contained in X and X is contained in U, then L’ is contained in X and X is contained in U’

Answer 10

True. If both conditions of the and are met the third condition will be.

Question 11

For any program P, if (L’,U’) is the result of expand p(L,U) and L’=U’, the L’ is a stable model of P.

Answer 11

True: If L’ = U’ L’ and U’ are the stable model.

Question 12

For any program P, if (L’,U’) is the result of expand p(L,U), then there is a stable model X such that L’ is contained in X and X is ontained in U’.

Answer 12

False. L would need to be contained in X and X in U.

Question 13

The stable model of a program can be computed using the function expand p(L,U), starting with L being the empty set and U being the set of all atoms in the program, and choosing an atom to become true or false whenever the result of the expand p(L,U) leaves undecided atoms.

Answer 13

True: This is the non-deterministic way to use the expand to find a stable model.

Question 14

What are the steps to reduct

Answer 14

Remove the rules that contian facts as negative body literals.
if we reduct with the empty set we remove all negative body literals.
reduct of all rules must be contained in the original set.