Computing propositional sentences (queries) into DNF form

[Subbarao Kambhampati <SUBBARAO.KAMBHAMPATI@asu.edu>]

I saw a couple of blank stares in the class about converting
propositional queries into CNF form:

Given any propositional sentence S, made up of keywords ki, you can
convert it into a set of DNF clauses

A DNF clause is a conjunction made up of either keywords or negated
keywords. 

You can convert any sentence into DNF form by doing the following
operations (repeatedly, as needed)

e.g. Q =  (K1 V K2) & ~(K5 => K6)

Change implication into disjunction (A => B  is written as ~A V B)

 (K1 V K2) & ~(~K5 V K6)

push negations inside using demorgan's laws (~(A&B) is written as ~A V ~B)
  (until the negations apply to single keywords).

 (K1 V K2) & (K5 & ~K6)

Distribute disjunction over conjunctions

  (K1 & K5 & ~K6) V (K2 & K & ~K6)

Now we have two DNF clauses:

c1: [K1 & K5 & ~K6]
c2: [K2 & K5 & ~K6]

We just return any document that has either of these conjunctions
satisfied. 


[Notice that despite what I said in the class about vector models
being used more than boolean models, vector models do have
disadvantages in that there is no clean way of saying that you *don't*
want documents containing a specific keyword. So in practice, search
engines actually wind up grafting some of the boolean querying
functionality on top of vector models.]

Rao
[Jan 24, 2001]