1. RE: Q: function to simplify a boolean expression
Jerry,
Back in school we used a program called Espresso to reduce equations too
big for K-maps.
You can find the C source code at Programmer's Heaven.
http://www.programmersheaven.com/zone3/cat414/16591.htm
Good luck,
-- Brian
Jerry wrote:
> Question:
> Where can I find, or how can I make, a function that takes a
> boolean expression and returns it simplified as much as it can be
> simplified?
>
> Jerry Story
>
2. RE: Q: function to simplify a boolean expression
- Posted by bensler at mail.com
Jan 16, 2002
Am I missing something?
Euphoria will reduce any expression you give it:
print(1, (1 > 2) )
print(1, (1 < 2) )
Chris
jstory at freenet.edmonton.ab.ca wrote:
> Question:
> Where can I find, or how can I make, a function that takes a
> boolean expression and returns it simplified as much as it can be
> simplified?
>
> Jerry Story
>
>
3. RE: Q: function to simplify a boolean expression
On Thu, 17 Jan 2002 bensler at mail.com wrote:
> Am I missing something?
> Euphoria will reduce any expression you give it:
> print(1, (1 > 2) )
> print(1, (1 < 2) )
1st day: John Q. Fiddlesticks drinks beer and apple juice and gets drunk.
2nd day: JQF drinks beer and tomato juice and gets drunk.
3rd day: JQF drinks apple juice and tomato juice and does not get drunk.
4th day: JQF drinks vodka and apple juice and gets drunk.
..... etc. etc. .....
John Q. Fiddlesticks is trying to figure out what the hell is making him
drunk.
So he makes a truth table:
B = beer V = vodka A = apple juice T = tomato juice
B V A T got drunk
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
John Q. Fiddlesticks collects all the cases where he gets drunk and
makes a boolean expression:
(-B, V, -A, -T) or (-B, V, -A, T) or (-B, V, A, -T) or (-B, V, A, T) or
( B, -V, -A, -T) or ( B, -V, -A, T) or ( B, -V, A, -T) or ( B, -V, A, T) or
( B, V, -A, -T) or ( B, V, -A, T) or ( B, V, A, -T) or ( B, V, A, T)
This boolean expression reduces to: (B or V)
So JQF concludes that what is making him drunk is: beer or vodka
---------------
Smurf Village is plagued with Smurfitis, a strange disease that results in
multi-colored polka dots all over your body.
Doctor Smurf has collected a large amount of data. He is in a perfect
position to collect data because he is the doc.
The data has, not 4 variables but 8 variables. From this data, he has
made a very long boolean expression.
Doctor Smurf wants to know how to simplify this very long boolean expression,
and others like it for other diseases. Like maybe a function.
Doctor Smurf says: "I'm a doctor, not a programmer." (paraphrasing McCoy)
All the wisest and most learned people in Smurf Village, all the
sages and soothsayers and astrologers and magicians have failed to solve
this problem.
But word got around that there exists a source, called the Euphoria list,
where anyone can ask any question and get an answer, and where there are
people who are far more learned and more wise than anyone in all of
Smurf Village.
Doctor Smurf and the people of Smurf Village eagerly await an answer.
-----------------
About espresso.zip:
This looks as complicated as hell. I was hoping for something simple.
Like:
s2 = simplify_boolean_expression(s1)
(either written in Euphoria or easily translatable to Euphoria)
Maybe for my purpose it doesn't need to be as complicated as espresso.
Jerry Story
4. RE: Q: function to simplify a boolean expression
- Posted by bensler at mail.com
Jan 17, 2002
Someone once told me, "if you never ask the question, you'll never get
the answer" ;P
I was missing something :)
Chris
jzeitlin at cyburban.com wrote:
> On Thu, 17 Jan 2002 03:46:55 -0800, bensler at mail.com wrote:
>
> >Am I missing something?
> >Euphoria will reduce any expression you give it:
> >print(1, (1 > 2) )
> >print(1, (1 < 2) )
>
> No. This is 'evaluating', not 'simplifying'. 'Simplifying' is reducing
> the expression to its simplest form, regardless of the actual truth
> values
> of the various variables. Jerry's example later in this digest was
> _very_
> complex, but illustrated what he's after very well.
>
> I suggest that you read up on boolean logic and the propositional
> calculus.
> Surprisingly, a fairly accessible explanation of both is included in
> Douglas Hofstadter's book
> _Gödel,_Escher,_Bach:_An_Eternal_Golden_Braid_.
>
> >jstory at freenet.edmonton.ab.ca wrote:
> >> Question:
> >> Where can I find, or how can I make, a function that takes a
> >> boolean expression and returns it simplified as much as it can be
> >> simplified?
>
> >> Jerry Story
>
> --
> Jeff Zeitlin
> jzeitlin at cyburban.com
>
>
5. RE: Q: function to simplify a boolean expression
Hi Jerry,
Don't think this will help you.... The drunk thing is quit simple. If
got drunk is 0 all switches on 1 can be deleted. The ones that are left
on the list can make him drunk. Very easy to make a program that does
the job. In this case the number of "switches" doesn't matter. It's easy
because "got drunk" is the only thing to find out and can be just 0 or
1.
Bye,
Jasper.
