Hi,
I am looking for some code to convert a truth table to a symbolic
boolean expression.Any ideas?
Thanks
Hans
--
I'm trying a new usenet client for Mac, Nemo OS X.
You can download it at http://www.malcom-mac.com/nemo
On 11 Mai, 10:17, kkk <····@kkk.org> wrote:
> Hi,
>
> I am looking for some code to convert a truth table to a symbolic
> boolean expression.Any ideas?
>
http://en.wikipedia.org/wiki/Karnaugh_diagram
ciao,
Jochen
kkk <···@kkk.org> writes:
> Hi,
>
> I am looking for some code to convert a truth table to a symbolic
> boolean expression.Any ideas?
See http://darcs.informatimago.com/emacs/pjb-sources.el
(karnaugh-solve '(a b c) '(open close)
'((0 0 0 0 0 )
(0 0 1 0 0 )
(0 1 0 0 1 )
(0 1 1 1 0 )
(1 0 0 1 0 )
(1 0 1 1 1 )
(1 1 0 0 0 )
(1 1 1 0 0 ))
'(0 . 1))
-->
((open . (lambda (a b c) (or (and (not a) b c) (and a (not b) (not c)) (and a (not b) c))))
(close . (lambda (a b c) (or (and (not a) b (not c)) (and a (not b) c)))))
But simplification of the expressions is not implemented yet.
--
__Pascal Bourguignon__ http://www.informatimago.com/
HEALTH WARNING: Care should be taken when lifting this product,
since its mass, and thus its weight, is dependent on its velocity
relative to the user.
From: kkk
Subject: Re: convert truth table to boolean expression
Date:
Message-ID: <46476a97@news.uni-ulm.de>
On 2007-05-11 19:17:03 +0200, Pascal Bourguignon <···@informatimago.com> said:
> kkk <···@kkk.org> writes:
>
>> Hi,
>>
>> I am looking for some code to convert a truth table to a symbolic
>> boolean expression.Any ideas?
>
> See http://darcs.informatimago.com/emacs/pjb-sources.el
>
> (karnaugh-solve '(a b c) '(open close)
> '((0 0 0 0 0 )
> (0 0 1 0 0 )
> (0 1 0 0 1 )
> (0 1 1 1 0 )
> (1 0 0 1 0 )
> (1 0 1 1 1 )
> (1 1 0 0 0 )
> (1 1 1 0 0 ))
> '(0 . 1))
> -->
> ((open . (lambda (a b c) (or (and (not a) b c) (and a (not b) (not c))
> (and a (not b) c))))
> (close . (lambda (a b c) (or (and (not a) b (not c)) (and a (not b) c)))))
>
>
> But simplification of the expressions is not implemented yet.
Thanks for the post!
Is this the desired behaviour?
(karnaugh-solve '(a b c) '(tt)
'((0 0 0 1)
(0 0 1 0)
(0 1 0 0)) '(0 . 1))
((TT LAMBDA (A B C) (OR (AND (NOT A) (NOT B) (NOT C)))))
kkk writes:
> On 2007-05-11 19:17:03 +0200, Pascal Bourguignon <···@informatimago.com> said:
>
>> kkk <···@kkk.org> writes:
>>
>>> Hi,
>>> I am looking for some code to convert a truth table to a symbolic
>>> boolean expression.Any ideas?
>> See http://darcs.informatimago.com/emacs/pjb-sources.el
>> (karnaugh-solve '(a b c) '(open close)
>> '((0 0 0 0 0 )
>> (0 0 1 0 0 )
>> (0 1 0 0 1 )
>> (0 1 1 1 0 )
>> (1 0 0 1 0 )
>> (1 0 1 1 1 )
>> (1 1 0 0 0 )
>> (1 1 1 0 0 ))
>> '(0 . 1))
>> -->
>> ((open . (lambda (a b c) (or (and (not a) b c) (and a (not b) (not
>> c)) (and a (not b) c))))
>> (close . (lambda (a b c) (or (and (not a) b (not c)) (and a (not b) c)))))
>> But simplification of the expressions is not implemented yet.
>
> Thanks for the post!
>
>
> Is this the desired behaviour?
>
> (karnaugh-solve '(a b c) '(tt)
> '((0 0 0 1)
> (0 0 1 0)
> (0 1 0 0)) '(0 . 1))
>
> ((TT LAMBDA (A B C) (OR (AND (NOT A) (NOT B) (NOT C)))))
Yes. Note that the lisp printer doesn't distinguish cons cells from
lists, when the cdr is itself a list.
So (a . (b c)) prints as (a b c), but it is the same, you can still
use car and cdr to get the name and the lambda expression:
(mapcar
(lambda (f) (setf (symbol-function (car f)) (byte-compile (cdr f))) (car f))
(karnaugh-solve '(a b c) '(tt)
'((0 0 0 1)
(0 0 1 0)
(0 1 0 0)) '(0 . 1)))
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
From: Hans Kestler
Subject: Re: convert truth table to boolean expression
Date:
Message-ID: <4647f648@news.uni-ulm.de>
On 2007-05-13 22:14:43 +0200, Pascal Bourguignon <···@informatimago.com> said:
> kkk writes:
>
>> On 2007-05-11 19:17:03 +0200, Pascal Bourguignon <···@informatimago.com> said:
>>
>>> kkk <···@kkk.org> writes:
>>>
>>>> Hi,
>>>> I am looking for some code to convert a truth table to a symbolic
>>>> boolean expression.Any ideas?
>>> See http://darcs.informatimago.com/emacs/pjb-sources.el
>>> (karnaugh-solve '(a b c) '(open close)
>>> '((0 0 0 0 0 )
>>> (0 0 1 0 0 )
>>> (0 1 0 0 1 )
>>> (0 1 1 1 0 )
>>> (1 0 0 1 0 )
>>> (1 0 1 1 1 )
>>> (1 1 0 0 0 )
>>> (1 1 1 0 0 ))
>>> '(0 . 1))
>>> -->
>>> ((open . (lambda (a b c) (or (and (not a) b c) (and a (not b) (not
>>> c)) (and a (not b) c))))
>>> (close . (lambda (a b c) (or (and (not a) b (not c)) (and a (not b) c)))))
>>> But simplification of the expressions is not implemented yet.
>>
>> Thanks for the post!
>>
>>
>> Is this the desired behaviour?
>>
>> (karnaugh-solve '(a b c) '(tt)
>> '((0 0 0 1)
>> (0 0 1 0)
>> (0 1 0 0)) '(0 . 1))
>>
>> ((TT LAMBDA (A B C) (OR (AND (NOT A) (NOT B) (NOT C)))))
>
> Yes. Note that the lisp printer doesn't distinguish cons cells from
> lists, when the cdr is itself a list.
>
> So (a . (b c)) prints as (a b c), but it is the same, you can still
> use car and cdr to get the name and the lambda expression:
>
> (mapcar
> (lambda (f) (setf (symbol-function (car f)) (byte-compile (cdr f))) (car f))
> (karnaugh-solve '(a b c) '(tt)
> '((0 0 0 1)
> (0 0 1 0)
> (0 1 0 0)) '(0 . 1)))
Thank you!
What would be the ideal data structure to represent a large collection
of boolean functions, e.g. 2^(2^k), in table format? Would you use a
hash table?
Hans
Hans Kestler wrote:
> What would be the ideal data structure to represent a large collection
> of boolean functions, e.g. 2^(2^k), in table format?
Just use a simple vector, and construct an integer index
where each bit contains one of the original index values.
--
Dan
www.prairienet.org/~dsb/
Dan Bensen <··········@cyberspace.net> writes:
> Hans Kestler wrote:
>> What would be the ideal data structure to represent a large
>> collection of boolean functions, e.g. 2^(2^k), in table format?
>
> Just use a simple vector, and construct an integer index
> where each bit contains one of the original index values.
Yes, the set of boolean functions is rather "dense". If you have
k-variable functions, there are only 2^(2^k) different boolean
functions, so your 2^(2^k) makes me think perhaps you just have all of
them.
So perhaps the best representation is to not represent them,
or if the order matters and it's an injection, represent them as a
permutation (mapping the index to the integer representing the boolean
function). Well the point is that your representation will best
depend on the actual set of functions you have.
For example for the function tt defined as:
(karnaugh-solve '(a b c) '(tt)
'((0 0 0 1)
(0 0 1 0)
(0 1 0 0)) '(0 . 1))
(with 3 variables you have 2^(2^3) = 256 different functions).
you can write all the combinations of a b c, and add a column for the
value of tt, then take all the bits of the columns for tt and convert
them into an integer which represents the function:
a b c tt
0 0 0 1 ---> 00000001 (binary) = 1 (decimal)
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 0
If your table contains all these 2^(2^k) functions in order, then you
don't need to store it, since it would map 0->0,1->1,2->2,3->3 etc.
If they are in a different order, then you can just store a
permutation.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
From: Petter Gustad
Subject: Re: convert truth table to boolean expression
Date:
Message-ID: <87d511rugn.fsf@gustad.com>
kkk <···@kkk.org> writes:
> I am looking for some code to convert a truth table to a symbolic
> boolean expression.Any ideas?
(defun bool-table-to-expr (table names)
(cons 'bool-expr-ior
(loop for e in table
collect (bool-expr-single e names))))
(defun bool-expr-single (bits names)
(cons 'bool-expr-and
(loop for b in bits
for n in names
collect (if (zerop b) `(bool-expr-not ,n) n))))
(bool-table-to-expr '((0 0 0) (0 0 1) (1 1 1)) '(A B C))
=>
(BOOL-EXPR-IOR
(BOOL-EXPR-AND (BOOL-EXPR-NOT A) (BOOL-EXPR-NOT B) (BOOL-EXPR-NOT C))
(BOOL-EXPR-AND (BOOL-EXPR-NOT A) (BOOL-EXPR-NOT B) C)
(BOOL-EXPR-AND A B C))
Petter
--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?