I'm trying to come up with a program that evalues a boolean expression like
(AND d (OR a c)(NOT b))
The problem is that I cant come up with a function that can come up with all
possible combinatoins of T/F. Can anybody point me in the right direction?
DB> ... The problem is that I
DB> cant come up with a function that can come up with all
DB> possible combinatoins of T/F. Can anybody point me in the
DB> right direction?
I'd be interested to see an elegant solution to this. What I usually
do in these situations is count and look at bit positions (think of
the least significant n bits of an integer as n boolean values and count
up from 0).
BM
In article <············@martha.csc.albany.edu>,
Dylan Bramblett <··········@hotmail.com> wrote:
>I'm trying to come up with a program that evalues a boolean expression like
>(AND d (OR a c)(NOT b))
>The problem is that I cant come up with a function that can come up with all
>possible combinatoins of T/F. Can anybody point me in the right direction?
Enumerate all the integers from 0 to 2^n-1 -- their binary representations
will contain all the combinations you care about. Then to get true/false
value for one of them, use (logbitp x i) for n from 0 to n-1.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
I don't need to enumerate the integers, i just need to substitute the
variables with T or NILL. I don't have a problem with this, I need a
function that comes up with all the T/NIL combonations. Supposedly This
parrt can be done in under 6 lines.
"Barry Margolin" <······@bbnplanet.com> wrote in message
·······················@burlma1-snr2...
> In article <············@martha.csc.albany.edu>,
> Dylan Bramblett <··········@hotmail.com> wrote:
> >I'm trying to come up with a program that evalues a boolean expression
like
> >(AND d (OR a c)(NOT b))
> >The problem is that I cant come up with a function that can come up with
all
> >possible combinatoins of T/F. Can anybody point me in the right
direction?
>
> Enumerate all the integers from 0 to 2^n-1 -- their binary representations
> will contain all the combinations you care about. Then to get true/false
> value for one of them, use (logbitp x i) for n from 0 to n-1.
>
> --
> Barry Margolin, ······@bbnplanet.com
> GTE Internetworking, Powered by BBN, Burlington, MA
> *** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to
newsgroups.
> Please DON'T copy followups to me -- I'll assume it wasn't posted to the
group.
In article <············@martha.csc.albany.edu>,
Dylan Bramblett <··········@hotmail.com> wrote:
>I don't need to enumerate the integers, i just need to substitute the
>variables with T or NILL. I don't have a problem with this, I need a
>function that comes up with all the T/NIL combonations. Supposedly This
>parrt can be done in under 6 lines.
My suggestion was that use an enumeration of integers to come up with the
T/NIL combinations, because there's a one-to-one mapping between them.
You could also write a simple binary odometer-like routine.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Thnaks for the help. I misread your first post. I was leaning towards the
binary relation, I just didn't know which functions to use.
"Barry Margolin" <······@bbnplanet.com> wrote in message
····················@burlma1-snr2...
> In article <············@martha.csc.albany.edu>,
> Dylan Bramblett <··········@hotmail.com> wrote:
> >I don't need to enumerate the integers, i just need to substitute the
> >variables with T or NILL. I don't have a problem with this, I need a
> >function that comes up with all the T/NIL combonations. Supposedly This
> >parrt can be done in under 6 lines.
>
> My suggestion was that use an enumeration of integers to come up with the
> T/NIL combinations, because there's a one-to-one mapping between them.
>
> You could also write a simple binary odometer-like routine.
>
> --
> Barry Margolin, ······@bbnplanet.com
> GTE Internetworking, Powered by BBN, Burlington, MA
> *** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to
newsgroups.
> Please DON'T copy followups to me -- I'll assume it wasn't posted to the
group.
Dylan Bramblett <··········@hotmail.com> schrieb in im Newsbeitrag:
············@martha.csc.albany.edu...
> I don't need to enumerate the integers, i just need to substitute the
> variables with T or NILL. I don't have a problem with this, I need a
> function that comes up with all the T/NIL combonations. Supposedly This
> parrt can be done in under 6 lines.
This is a combinatorial problem: ranking and unranking the subsets of a set.
The solution Barry Margolin proposes is the standard solution.
Janos Blazi
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
From: Gareth McCaughan
Subject: Re: Coming up with 2^n
Date:
Message-ID: <86d7orwu6s.fsf@g.local>
Dylan Bramblett wrote:
> I'm trying to come up with a program that evalues a boolean expression like
> (AND d (OR a c)(NOT b))
> The problem is that I cant come up with a function that can come up with all
> possible combinatoins of T/F. Can anybody point me in the right direction?
It would be better to say explicitly that this is homework;
otherwise people might think you're trying to hide the fact
from them and get them to do your work for you.
Anyway: why don't you show us what you've tried and why it
didn't work? Then we can be more helpful. Otherwise, about
the only thing to do is to write the code for you, and
that would completely miss the point.
--
Gareth McCaughan ················@pobox.com
sig under construction
You're right, it is a class assignment. If I thought it was relevant to the
problem I would have let you know. And if you wan tto know what I have so
far, not a problem. It's not much, but it's a start.
The first function that I have takes the logical expresion and makes a list
of all the variables in it.
I have a function that will substitute a value for a variable (A little
redundant now that Iknow about subst).
And the 3rd function I have is one that evals the statement after the
variables have been substituted.
That's it. As for the binary list idea from Barry Margolin, I hd it almost
working, when I found out you couldn't use any type of counter. It has to
all be done with recursion. Oh well, back to the drawing board.
And to you Gareth, I'm new to lisp. Never in my post did I ask for people
to give me code for anything. My words were "point me in the right
direction." If sombody gives me code, hey, great. I still got to learn
what it does and why. But I'd prefer if sombody would just give me some
function names and say "Hey take a look at these. They may be able to help
you do what you need to do." After all I am just learning the language.
"Gareth McCaughan" <················@pobox.com> wrote in message
···················@g.local...
> Dylan Bramblett wrote:
>
> > I'm trying to come up with a program that evalues a boolean expression
like
> > (AND d (OR a c)(NOT b))
> > The problem is that I cant come up with a function that can come up with
all
> > possible combinatoins of T/F. Can anybody point me in the right
direction?
>
> It would be better to say explicitly that this is homework;
> otherwise people might think you're trying to hide the fact
> from them and get them to do your work for you.
>
> Anyway: why don't you show us what you've tried and why it
> didn't work? Then we can be more helpful. Otherwise, about
> the only thing to do is to write the code for you, and
> that would completely miss the point.
>
> --
> Gareth McCaughan ················@pobox.com
> sig under construction
From: Gareth McCaughan
Subject: Re: Coming up with 2^n
Date:
Message-ID: <86d7oqmqvi.fsf@g.local>
Dylan Bramblett wrote:
> You're right, it is a class assignment. If I thought it was relevant to the
> problem I would have let you know.
The point is that we get a lot of people turning up in c.l.l
who are taking classes in Lisp, don't really care about understanding
the language, and want to find someone who'll do their homework
for them. You don't want to look like one of those -- it puts
people off, you know...
> The first function that I have takes the logical expresion and makes a list
> of all the variables in it.
> I have a function that will substitute a value for a variable (A little
> redundant now that Iknow about subst).
> And the 3rd function I have is one that evals the statement after the
> variables have been substituted.
>
> That's it. As for the binary list idea from Barry Margolin, I hd it almost
> working, when I found out you couldn't use any type of counter. It has to
> all be done with recursion. Oh well, back to the drawing board.
Well, that's fair enough. But a word of warning: a lot of
people who teach classes in Lisp seem to think that everything
in Lisp has to be done by recursion, or that Lisp doesn't
have any data structures other than lists. Actually,
modern Lisps have a lot more than is widely thought;
Common Lisp especially so. I'm saying all this just to
help you guard against falling into the trap of confusing
artificial restrictions imposed on you because your prof
wants you to learn about recursion, with actual restrictions
imposed by the language...
> And to you Gareth, I'm new to lisp. Never in my post did I ask for people
> to give me code for anything. My words were "point me in the right
> direction." If sombody gives me code, hey, great. I still got to learn
> what it does and why. But I'd prefer if sombody would just give me some
> function names and say "Hey take a look at these. They may be able to help
> you do what you need to do." After all I am just learning the language.
(I think you read my words as more accusing than they were;
never mind.)
OK, here's a suggestion.
You have your expression, with some variables in it.
You want a list of all the expressions that result from
replacing each variable with either T or NIL. (Or maybe
you want a list of the result of evaluating those. That
doesn't make much difference here.)
So, suppose you take the first variable and replace it
with NIL. What's left? Answer: an expression with some
variables in it (albeit fewer). What if you replace the
first variable with T? Again, an expression with some
variables in it.
In other words, doing either of those replacements
gives you an expression like the one you started with,
but simpler. The alarm bell in your head labelled
"recursion" ought to be going off at this point.
Does that help?
I don't think you need any functions to do this that
you're likely not to know about already.
--
Gareth McCaughan ················@pobox.com
sig under construction
> (I think you read my words as more accusing than they were; never mind.)
Gareth: I apoligize if I seemed a little "snappy" in my response. It was
late and I was getting annoyed with tutoring and then having to come back
and work on my stuff.
Oh well. It's pretty much too late to hand in the project so I guess it's
ok to print what I got so far and see if anybody can help. It's gonna'
drive me crazy untill I get it to work.
First function (getvars) - Extracts the variables from the the expression.
It's only argument is a list of boolean expressions.
>(setq f1 (and (a) (or b (not c))))
(AND (A) (OR B (NOT C))))
>(getvars f1)
(A B C)
Second function (mysub) - Supose to subistute T/Nil Values for the
variables. I can get it to replace all the varibales with the same value,
but don't know how to get it to come up with all possible combinations of
T/Nil. As of right now, it takes 2 arguments. (1)The list of expressions,
and (2) the list of variables.
>(mysub f1 (getvars f1))
(AND (T) (OR T (NOT T)))
The third function just evaluates the the result of the mysub and returns a
truth value.
It is only allowed to take 1 argument, the origional boolean expression.
>(consistent (f1)
T
The Purpose of the program is to take a boolean expression and decide wether
it can ever be true or not. The funal function can only call one argument
and no iteratino or counters are allowed. It must use recursive funtcions.
The problem with the program so far is that it can only substitute 1 value
for all the variables. I can't seem to come up with 1 or 2 functions that
computes all possible T/nil Values and then substitutes them in specific
order. In reality I don't need to come up with all combintations. Once it
finds a true value it can stop. I think I'd use OR and a recursive function
due to the fact that once it gets a T value, it returns T. Beyond these
ideas, I'm stuck. If anybody could help out, my sanity would be most
thankful. This program can be done in about 5 functions, at most 4-5 lines
a piece.
From: Gareth McCaughan
Subject: Re: Coming up with 2^n
Date:
Message-ID: <86wvmv6g4x.fsf@g.local>
Dylan Bramblett wrote:
> First function (getvars) - Extracts the variables from the the expression.
> It's only argument is a list of boolean expressions.
>> (setq f1 (and (a) (or b (not c))))
> (AND (A) (OR B (NOT C))))
>> (getvars f1)
> (A B C)
Well, if you've managed to do this then you've grasped a lot
of the important issues...
> Second function (mysub) - Supose to subistute T/Nil Values for the
> variables. I can get it to replace all the varibales with the same value,
> but don't know how to get it to come up with all possible combinations of
> T/Nil. As of right now, it takes 2 arguments. (1)The list of expressions,
> and (2) the list of variables.
>> (mysub f1 (getvars f1))
> (AND (T) (OR T (NOT T)))
Did my suggestion not help at all? Let me try to make it
a bit more explicit, then.
The list of all possible substituted things
= the list of all possible substituted things in which the first
variable becomes T
+
the list of all possible substituted things in which the first
variable becomes NIL
(unless there are no variables left, in which case the list of all
possible substituted things is a one-element list that you should
have no trouble making.)
And
The list of all possible substituted things in which the first
variable becomes T
= the list of all possible substituted things, where
- your list of variables is the same but with
the first variable removed
- your expression is the same as before but with
the first variable replaced with T.
Similarly for NIL.
> The third function just evaluates the the result of the mysub and returns a
> truth value.
> It is only allowed to take 1 argument, the origional boolean expression.
>> (consistent (f1)
> T
Write a function that evaluates a single expression with no
variables left. Apply that to each of the expressions in the
list returned by the MYSUB function. See whether all the
results are T. As you say, you can do this recursively.
--
Gareth McCaughan ················@pobox.com
sig under construction
AHHHH!!!! Now I see what yo mean. I'm not completly in the recusrive
mindset just yet, but I'm begining to see more clearly. Thanks for your
help. Now hopefully I can get this to work.
> Did my suggestion not help at all? Let me try to make it
> a bit more explicit, then.
>
> The list of all possible substituted things
> = the list of all possible substituted things in which the first
> variable becomes T
> +
> the list of all possible substituted things in which the first
> variable becomes NIL
> (unless there are no variables left, in which case the list of all
> possible substituted things is a one-element list that you should
> have no trouble making.)
>
> And
>
> The list of all possible substituted things in which the first
> variable becomes T
> = the list of all possible substituted things, where
> - your list of variables is the same but with
> the first variable removed
> - your expression is the same as before but with
> the first variable replaced with T.
>
> Similarly for NIL.
>
> > The third function just evaluates the the result of the mysub and
returns a
> > truth value.
> > It is only allowed to take 1 argument, the origional boolean expression.
> >> (consistent (f1)
> > T
Thanks for the help Gareth, got my function to work. And by the sound of
it, it's smaller than most of my friends'. To anybody that that wants to
see the source, I'll post it after the extended deadline expires.
"Dylan Bramblett" <··········@hotmail.com> writes:
> I'm trying to come up with a program that evalues a boolean expression like
> (AND d (OR a c)(NOT b))
> The problem is that I cant come up with a function that can come up with all
> possible combinatoins of T/F. Can anybody point me in the right direction?
The code from the Norvig/Russell book Artificial Intelligence: A
Modern Approach includes a truth table generator for propositional
logic.
Christopher
Christopher R. Barry <······@2xtreme.net> wrote in message
···················@2xtreme.net...
| "Dylan Bramblett" <··········@hotmail.com> writes:
|
| > I'm trying to come up with a program that evalues a boolean expression like
| > (AND d (OR a c)(NOT b))
| > The problem is that I cant come up with a function that can come up with all
| > possible combinatoins of T/F. Can anybody point me in the right direction?
|
| The code from the Norvig/Russell book Artificial Intelligence: A
| Modern Approach includes a truth table generator for propositional
| logic.
|
| Christopher
found at:
http://www.cs.berkeley.edu/~russell/code/doc/overview-LOGIC.html
Coby