Forum: Ruby Transformation in DNF and KNF ?

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Guest (Guest)
on 2006-05-22 13:29
Hello, i need yours help...
Could someone give me an example for the transformation from a logical
expression to DNF or KNF?

Thanks
Josef 'Jupp' SCHUGT (Guest)
on 2006-05-22 17:41
(Received via mailing list)
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
(Guest)
on 2006-05-22 17:45
(Received via mailing list)
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
This topic is locked and can not be replied to.