Hello, i need yours help…
Could someone give me an example for the transformation from a logical
expression to DNF or KNF?
Thanks
Hello, i need yours help…
Could someone give me an example for the transformation from a logical
expression to DNF or KNF?
Thanks
Hi!
At Mon, 22 May 2006 18:29:21 +0900, [email protected] 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
Josef ‘Jupp’ SCHUGT wrote:
Hi!
At Mon, 22 May 2006 18:29:21 +0900, [email protected] 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 forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.
Sponsor our Newsletter | Privacy Policy | Terms of Service | Remote Ruby Jobs