Discrete Mathematics for Computer Science

154 CHAPTER 2 Formal Logic

Next, for each satisfying truth assignment I, let T, be the set of truth variables

assigned the value TRUE by I. Compare the sets TI for the truth assignments

above by _.

Now, show that the following set of Horn clauses is satisfiable:

[P1, -' P1 V P2, P1 V -P2 V P3, -P1 V -1P2 V P4, -P3 V -1P4 V P5,

- P6 V P7, -PI V -'P7 V P6, -'P V -P6, -1P2 V -'P4 V -'P71

(e) Challenge: Prove that if 4' is a Horn clause and if I, and 12 are interpretations

satisfying 4', then the following interpretation IA also satisfies 4':

IA(X) = IT /Fotherwiseif Ii(x)= T and 12(x) = T

Using this, show that p V q is not logically equivalent to (the conjunction of) any

set of Horn clauses.

(f) Challenge: Write pseudocode for a relatively fast algorithm to determine whether

a set of Horn clauses is satisfiable. Include arguments to show that (i) your al-

gorithm returns the correct answer and (ii) your algorithm is reasonably fast (in

general, much faster than writing the truth table for the set of Horn clauses).

7. Determine if the CNF
   (x V y V -z V w V u V -v) A (--x V -y V z V -w V u V v) A
   (x v -y V -z V W V u V -v) A (X V -'y)
   or the CNF
   (p V r V v) A (-p V r V v) A (p V -'r V V) A (-p V -'r V -v) A
   (p V -r V -v) A (-p V -r V -v) A (p V r V -V) A (-p V r V -v)

is satisfiable. This exercise shows that the satisfiability problem can be solved if the

satisfiability problem can be solved for a CNF. The CNF satisfiability problem was the

first NiP-complete problem.

8. Afirst-order Horn clause is a formula such as

Vx Vy (Loves(x, y) v -EatsGarlic(x) V -EatsGarlic(y))

Inside the parentheses is a disjunction of atomic formulas (Loves(x, y)) and negated

atomic formulas (- EatsGarlic(x)). All the variables are universally quantified outside

the parentheses.

Using the predicates

Trained (x, j): x is trained to do job j.

Experienced (x, j): x is experienced at job j.

Prefers (x, j1, j2): x prefers job j1 to job j2.

Hire (x, j): hire x to do job j.

State the following with sets of first-order Horn clauses:

(a) If Britney and Aaron are both trained and experienced in marketing and account-

ing, and if Britney prefers accounting to marketing and Aaron prefers marketing

to accounting, then hire Britney to do accounting.