# Transformation in DNF and KNF?

**URL:** <https://www.ruby-forum.com/t/transformation-in-dnf-and-knf/61243>\
**Category:** Ruby\
**Created:** [May 22, 2006, 11:29am UTC](https://www.ruby-forum.com/t/transformation-in-dnf-and-knf/61243 "2006-05-22T11:29:13Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![guest](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/8dc957/32.png) [@guest](https://www.ruby-forum.com/u/guest)\
**Post date:** [May 22, 2006, 11:29am UTC](https://www.ruby-forum.com/t/transformation-in-dnf-and-knf/61243/1 "2006-05-22T11:29:13Z")

</div>

Hello, i need yours help…  
Could someone give me an example for the transformation from a logical  
expression to DNF or KNF?

Thanks

---

<div class="post-metadata">

**Author:** ![guest](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/8dc957/32.png) [@guest](https://www.ruby-forum.com/u/guest)\
**Post date:** [May 22, 2006, 3:41pm UTC](https://www.ruby-forum.com/t/transformation-in-dnf-and-knf/61243/2 "2006-05-22T15:41:55Z")

</div>

Hi!

At Mon, 22 May 2006 18:29:21 +0900, removed\_email\_address@domain.invalid wrote:

> Could someone give me an example for the transformation from a logical  
> expression to DNF or KNF?

A boolean expression can allways be transformed into a table of  
values. Say the expression is

f(x,y,z) = (x + y) \* z

This results in the following table:

i | x y z | f  
–±------±–  
0 | 0 0 0 | 0  
1 | 0 0 1 | 0  
2 | 0 1 0 | 0  
3 | 0 1 1 | 1  
4 | 1 0 0 | 0  
5 | 1 0 1 | 1  
6 | 1 1 0 | 0  
7 | 1 1 1 | 1

For DNF collect all terms that result in f(x,y,z) = 1 (allow me to use  
uppercase for negation):

f(x,y,z) = Xyz + xYz + xyz = m3 + m5 + m7

For KNF you exploit the fact that NOT(NOT(f)) is the same as f by  
first expressing NOT(f) in DNF, negating the whole term and then using  
NOT(x+y) = X \* Y as well as NOT(x\*y) = X + Y:

f(x,y,z) = NOT(XYZ + XYz + XyZ + xYZ + xyZ)  
= NOT(XYZ) \* NOT(XYz) \* NOT(XyZ) \* NOT(xYZ) \* NOT(xyZ)  
= (x+y+z) \* (x+y+Z) \* (x+Y+z) \* (X+y+z) \* (X+Y+z)  
= M0 \* M1 \* M2 \* M4 \* M6

Wait a moment. I did not tell you to actually go through that  
process. The real solution of the task is _way_ simpler.

For DNF sum up all minterms with indices that have a 1 in the result  
column, that is:

f(x,y,z) = m3 + m5 + m7

For KNF multiply all Maxterms with indices that have a 0 in the result  
column:

f(x,y,z) = M0 + M1 + M2 + M4 + M6

In a program the above pocess may look like this:

dnf = Array.new  
knf = Array.new

(0…7).each do |i|  
if fun(i) then  
dnf.push i  
else  
knf.push i  
end  
end

p dnf.sort  
p knf.sort

where “fun” is defined so that for a number i with least significan  
boolean digits xyz and

a = (x == 1 ? true : false)  
b = (y == 1 ? true : false)  
c = (z == 1 ? true : false)

fun(i) = f(a,b,c)

HTH,

Josef ‘Jupp’ Schugt

---

<div class="post-metadata">

**Author:** ![guest](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/8dc957/32.png) [@guest](https://www.ruby-forum.com/u/guest)\
**Post date:** [May 22, 2006, 3:45pm UTC](https://www.ruby-forum.com/t/transformation-in-dnf-and-knf/61243/3 "2006-05-22T15:45:28Z")

</div>

Josef ‘Jupp’ SCHUGT wrote:

> Hi!
> 
> At Mon, 22 May 2006 18:29:21 +0900, removed\_email\_address@domain.invalid wrote:
> 
> > Could someone give me an example for the transformation from a logical  
> > expression to DNF or KNF?
> 
> A boolean expression can allways be transformed into a table of  
> values.

Thx. My German is not good, googling for “DNF or CNF” gives many good  
English discussions of this