Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site sbcs.UUCP
Path: utzoo!linus!philabs!sbcs!debray
From: debray@sbcs.UUCP (Saumya Debray)
Newsgroups: net.ai
Subject: re: trivial reasoning problem?
Message-ID: <572@sbcs.UUCP>
Date: Fri, 13-Jan-84 11:11:49 EST
Article-I.D.: sbcs.572
Posted: Fri Jan 13 11:11:49 1984
Date-Received: Sat, 14-Jan-84 23:49:15 EST
Organization: SUNY at Stony Brook
Lines: 49

Re: Marcel Schoppers' problem: given two lamps A and B, such that:

	condition 1) at least one of them is on at any time; and
	condition 2) if A is on then B id off,

	we are to enumerate the possible configurations without an exhaustive
	generate-and-test strategy.
-----
The following "pure" Prolog program that will generate the various
configurations without exhaustively generating all possible combinations:
-----

config(A, B) :- cond1(A, B), cond2(A, B).   /* both conditions must hold */

cond1(1, _).	/* at least one is on an any time ... condition 1 above */
cond1(_, 1).

cond2(1, 0).	/* if A is on then B is off */
cond2(0, _).	/* if A is off, B's value is a don't care */
----
executing Prolog gives:

| ?- config(A, B).

A = 1
B = 0 ;

A = 0
B = 1 ;

no
| ?- halt.
[ Prolog execution halted ]
----
Tracing the program shows that the configuration "A=0, B=0" is not generated.
This satisfies the "no-exhaustive-listing" criterion. Note that attempting
to encode the second condition above using "not" will be both (1) not pure
Horn Clause, and (2) using exhaustive generation and filtering.
-- 
Saumya Debray
Dept. of Computer Science
SUNY at Stony Brook

		{floyd, bunker, cbosgd, mcvax, cmcl2}!philabs!
							      \
	Usenet:						       sbcs!debray
							      /
		   {allegra, teklabs, hp-pcd, metheus}!ogcvax!
	CSNet: debray@suny-sbcs@CSNet-Relay