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

on 2006-05-22 11:29

on 2006-05-22 15:41

Hi! At Mon, 22 May 2006 18:29:21 +0900, pisteur@hotmail.de 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

on 2006-05-22 15:45

Josef 'Jupp' SCHUGT wrote: > Hi! > > At Mon, 22 May 2006 18:29:21 +0900, pisteur@hotmail.de 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