Tut 102 - 2006

Hi,
I am looking for a clear explanation for the production system - Qu2.
And the answer for Qu7. Why can PSAT be viewed as a constraint satisfaction problem?
Thanks for your help,
Michelle

Question 2:

Make sure the door in never left open.
Sequences:
Sequence_A : Open_A, Wait xTime , ~Open_A (open A, wait, close A)
Sequence_B : Open_B, Wait xTime , ~Open_B (open B, wait, close

Test one button at a time with priority.
States:
A1 : Button A1 pressed
A2 : Button A2 pressed
B1 : Button B1 pressed
B2 : Button B2 pressed
Open_A : Door A open
Open_B : Door B open

Rules (in order of priority):
B2 -> Sequence_B
A2 -> Sequence_A
A1 -> Sequence_A
B1 -> Sequence_B
Open_A -> ~Open_A
Open_B -> ~Open_B


Question 7:
The propositional satisfiability (PSAT) problem is the basic problem for which efficient algorithms in the classical sense do not exist. It is a special type of constraint satisfaction problem.
Given a set C of clauses over a set P of propositional variables
– a propositional variable can be assigned true or false
– a literal is a variable or its negation
– a clause is a disjunction of literals
• Is there a truth assignment for P that satisfies all clauses in C?
• SAT is NP-complete


Constraint satisfaction is the process finding a solution to a set of constraints. Such constraints express allowed values for variables, and a solution is therefore an evaluation of these variable that satisfies all constraints.
The finite domain contains a set of variables whose values can only be taken from the domain, and a set of constraints, each constraint specifying the allowed values for a group of variables.
Mathematical problems where one must find states or objects that satisfy a number of constraints or criteria.
Typically solved using a form of search. The most used techniques are variants of backtracking, constraint propagation, and local search.

In simple terms:

PSAT - to find a model for a formula in Conjunctive normal form

It is a constraint satisfaction because we have to statisfy the condition posed by the CNF

Thanks a lot for your help, I have some more questions:

Qu1.5: Diagram of the TLU: the coordinates of x1, x2 and x3 are taken from the final weight vector (2 -1 0).
=> 2(x1)-1(x2).0(x3) or 2(x1)-1(x2)+0(x3)
Is the equation = 0 or = to the final threshold or equal to the 4th value of the final weight?
=> 2(x1)-1(x2).0(x3) =0 or -1 or 1

Qu3.2: The order of the nodes using breadth-first search is given as a diagram or a list of values? It is explained in the the book p121 section 7.3, but there is no example.

Qu7.2: is it correct?

p: queen is in place r1, c1
q: queen is safe
Propositonal statement: p->q

Qu7.3???

Qu8.3: Conclusion: NeedMoney(James) or negative(NeedMoney(James))
the proof will not give nil, and it says that JAmes is not in prison???

Thanks again for all the precious advices

Qu3.2 - read the values across the graph

Q7.2 - Exisitential quantifies(x,y)(Queens(x,y) implies SAFE) with x and = 1

Q8.3 don't use resolution refutation, use Money(JAMES) to resolve the CNF.

The wffs are:

Pickpocket(James) Assumption
Pickpockets(x) implies Pickpocking(x) and Movies(x) assumption
Pickpockets(x) and Money(x) implies negateMovies(x) assumption
Pickpockets(x) and Prison(x) implies negatePickpocking(x) assumption
Money(James) Goal


you will land up with Pickpocking(James)