Consider the proof system BOOL given in Table 6.7.

Note that the rules AND 13 of BOOL are replaced by the rules AND 1 and AND 2 of BOOL and the rules OR 24 of BOOL are replaced by the rules OR 2 and OR 3 of BOOL. Also, the rule AND 6 of BOOL is split in BOOL into two rules, AND 3 and AND 6 and analogously for the rules OR 6 of BOOL and OR 3 and OR 6 of BOOL

(i) Prove that if a non-failed Boolean CSP is closed under the applications of the rules of the proof system BOOL, then it is hyper-arc consistent.

(ii) Show that the converse result does not hold. Hint. Take the CSP x y = z ; x = 1, y {0, 1}, z {0, 1}.

(iii) Call a Boolean CSP limited if none of the following four CSPs forms a subpart of it:

x y = z ; x = 1, y {0, 1}, z {0, 1},

x y = z ; x {0, 1}, y = 1, z {0, 1},

x y = z ; x = 0, y {0, 1}, z {0, 1},

x y = z ; x {0, 1}, y = 0, z {0, 1}.

Prove that if a non-failed Boolean CSP is limited and hyper-arc consistent, then it is closed under the applications of the rules of the proof system BOOL