How the query converted to DNF?

Question

How the below query converted to DNF?

Query: t1 AND (t2 OR NOT t3 )

DNF: (t1 ∧t2 ∧t3) ∨(t1 ∧t2 ∧not t3) ∨(t1 ∧not t2 ∧not t3)

Comments

Which lecture was this question targeted to?

---

This is an example in lecture Collaborative Intelligence.

Answer 1

There are many ways how to generate a DNF of a given formula. 

A first way is to build its truth table and thereby, you just need to focus on the satisfying assignments that make the formula true. 

 -------------
  t1 t2 t3 |
 -------------
  1  0  0  | 1
  1  1  0  | 1
  1  1  1  | 1
 -------------

Now you can read the three minterms from the above table:

    t1 ∧ ¬ t2 ∧ ¬t3 ∨
    t1 ∧  t2 ∧ ¬t3 ∨
    t1 ∧  t2 ∧  t3

The above is usually bad since it may make a lot of effort. 

Another way is to use rewrite laws from Boolean algebra; in your example, you just need the distributive law:

t1 ∧ (t2 ∨ ¬t3) = t1 ∧ t2 ∨ t1 ∧ ¬t3

Note that DNFs are usually not canonical unless further restrictions are required. For example, if only minterms are listed as with the first approach. The latter does not yet provided this, but is also a DNF, i.e., a disjunction of conjunctions of literals. 

There are many other ways how to compute DNFs, e.g., using BDDs and enumerating the paths from the root to the 1-leaf.  

Answer 2

You can see that every single minterm (co-clause/conjunction of literals containing all variables) is present in the DNF. This looks like the origin is a truth table from which all minterms were formed.

t1	t2	t3	t1&(t2|!t3)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

The highlighted lines of the truth table represent the satisfying assignments of the formula. The disjunction of the corresponding minterms is exactly the DNF you presented.

One can also multiply out and get a formula like this:

(t1 ∧ t2) ∨ (t1 ∧ ¬t3)

The left-most co-clause doesn't contain t3, the right most one doesn't contain t2. This means, that the co-clause is satisfied for arbitrary values of the respective variable. One introduce the missing variables by creating one co-clause where it is added positively (without negation), and where it is added negatively (with negation). This yields:

(t1 ∧ t2 ∧ t3) ∨ (t1 ∧ t2 ∧ ¬t3) ∨ (t1 ∧ t2 ∧ ¬t3) ∨ (t1 ∧ →t2 ∧ ¬t3)

The co-clause (t1 ∧ t2 ∧ ¬t3) occurs twice. We remove one of the copies and get

(t1 ∧ t2 ∧ t3) ∨ (t1 ∧ t2 ∧ ¬t3) ∨ (t1 ∧ →t2 ∧ ¬t3)

Exactly the DNF you presented.