PowerBASIC Forums
  Cafe PowerBASIC
  A Logical Puzzle

Post New Topic  Post A Reply
profile | register | preferences | faq | search

UBBFriend: Email This Page to Someone! next newest topic | next oldest topic
Author Topic:   A Logical Puzzle
Charles Pegge
Member
posted January 18, 2007 02:56 PM     Click Here to See the Profile for Charles Pegge     Edit/Delete Message   Reply w/Quote
A minimalist programming language called has only 2 operators.

One is NOT the other is OR.

examples:
(A) means NOT(A)
A B means A OR B
(A B) means NOT(A OR B)

You can use any number of A B and nesting pairs of brackets

How would you express A AND B ?
How would you express A XOR B ?

------------------
www.pegge.net

IP: Logged

Eros Olmi
Member
posted January 18, 2007 03:17 PM     Click Here to See the Profile for Eros Olmi     Edit/Delete Message   Reply w/Quote
...


------------------
thinBasic forum
eros.olmi@thinbasic.com

[This message has been edited by Eros Olmi (edited January 18, 2007).]

IP: Logged

Simon Morgan
Member
posted January 18, 2007 04:10 PM     Click Here to See the Profile for Simon Morgan     Edit/Delete Message   Reply w/Quote
((A) (B))
(((A) (B)) (A B))

IP: Logged

David Roberts
Member
posted January 18, 2007 04:12 PM     Click Here to See the Profile for David Roberts     Edit/Delete Message   Reply w/Quote
Without spending too much time on this my first thought is that we cannot. 'AND' is independent and thus cannot be represented by 'NOT' and 'OR'. 'XOR' is not independent but does require 'AND'.

IP: Logged

Donald Darden
Member
posted January 18, 2007 04:52 PM     Click Here to See the Profile for Donald Darden     Edit/Delete Message   Reply w/Quote
When CDC (Computer Data Corporation) built the 1604, 1604a, and
C160a computers for the Navy back in the 1950s, they only employed
one type of logic gate, the NOR (Not OR) gate. You can build any
other type of logic gate by stringing NOR gates together in various
combinations.

------------------
Old Navy Chief, Systems Engineer, Systems Analyst, now semi-retired

IP: Logged

Maciej NEYMAN
Member
posted January 18, 2007 04:57 PM     Click Here to See the Profile for Maciej NEYMAN     Edit/Delete Message   Reply w/Quote
Hi Charles,
1.)I think there is typographic mistake in the first line of your examples:
it is : (A) means NOT (A)
I think it should be: (A) means NOT A
Please confirm.

2.) It seems to me that there is only one operator in yours
minimalistic language called - it is brackets them self
( ). They negate everything what is inside the brackets.

Very interesting, regards,
Maciej

Edited:
I think Donald spoted it very well (he posted his observation
while I have been typing - regards Donald!) - it is NOR gate
logic. Lack of brackets produces OR logic.
------------------

[This message has been edited by Maciej NEYMAN (edited January 18, 2007).]

IP: Logged

David Roberts
Member
posted January 18, 2007 05:14 PM     Click Here to See the Profile for David Roberts     Edit/Delete Message   Reply w/Quote
That's interesting Donald. It may have been only one gate but it is a combination of NOT and OR ie two independent logics. I may have to look at it again.

There is no typing error - the third line follows from the first two and wasn't required.

Added: No need. Just checked Simon's post. Well done, Simon.

[This message has been edited by David Roberts (edited January 18, 2007).]

IP: Logged

Aleksandr Dobrev
Member
posted January 19, 2007 02:14 AM     Click Here to See the Profile for Aleksandr Dobrev     Edit/Delete Message   Reply w/Quote
quote:

How would you express A AND B ?
How would you express A XOR B ?

Replace "AND" and "XOR" with OR-NOT combination:


#COMPILE EXE
#DIM ALL
'
TYPE bf
a AS BIT*1 IN BYTE
b AS BIT*1
r AS BIT*1
ra AS BIT*1
END TYPE
'
FUNCTION PBMAIN () AS LONG
LOCAL var AS bf
LOCAL sRes AS STRING
'
var.a=1 ' play here all possible combination
var.b=0 ' play here all possible combination
sRes="a="+STR$(var.a)+$CRLF
sRes=sRes+"b="+STR$(var.b)+$CRLF+REPEAT$(40,"-")
'
'---- realization AND with help only OR-NOT---------------------------------------
var.r=NOT(NOT(var.a) OR NOT(var.b)) 'same as (a AND b)
var.ra= var.a AND var.b ' test with real AND
sRes=sRes+$CRLF+"AND based on OR-NOT combination ="+STR$(var.r)+$CRLF+"real (a AND b) = "+STR$(var.ra)+$CRLF+REPEAT$(40,"-")
'
'-----realization XOR with help only OR-NOT----------------------------------------
var.r = (NOT(NOT(NOT(var.a)) OR NOT(var.b))) OR (NOT(NOT(var.a) OR NOT(NOT(var.b))))
var.ra= var.a XOR var.b ' test with real XOR
sRes=sRes+$CRLF+"XOR based on OR-NOT combination ="+STR$(var.r)+$CRLF+"real (a XOR b) = "+STR$(var.ra)
'-----------------------------------------------------------------------------------
? sRes,,"Test"
END FUNCTION

------------------
-=Alex=-

[This message has been edited by Aleksandr Dobrev (edited January 19, 2007).]

IP: Logged

Charles Pegge
Member
posted January 19, 2007 04:40 AM     Click Here to See the Profile for Charles Pegge     Edit/Delete Message   Reply w/Quote
Thank you everybody. The answers that Simon produced are correct.
By applying NOT to both inputs and output OR is turned into AND, and vice-versa.

AND ( (A) (B) )
XOR ( ( (A) (B) ) (A B) )

and Alex has demostrated the PB equivalent.

If you are interested in this kind of minimalism then:

http://www.lawsofform.org

------------------
www.pegge.net

IP: Logged

Aleksandr Dobrev
Member
posted January 19, 2007 04:55 AM     Click Here to See the Profile for Aleksandr Dobrev     Edit/Delete Message   Reply w/Quote
Yes, operation XOR can be done in a various way,
depend what kind of chip I have on a shelf for replace XOR-chip (when i don't have XOR-chip at time when i need it)

it can be done as


var.r = NOT(NOT(NOT(var.a)) OR NOT(var.b))) OR (NOT(NOT(var.a) OR NOT(NOT(var.b))) 'main 1
var.r = NOT(NOT(var.a) OR var.b) OR NOT(var.a OR NOT(var.b)) ' main 2
var.r = not(not(not(var.a) or not(var.b) ) or not(var.a or var.b)) ' variant by Simon Morgan

result is the same.

More intersting result can be done with help of card of Carno


#COMPILE EXE
#DIM ALL
'
TYPE bf
x1 AS BIT*1 IN BYTE
x2 AS BIT*1
x3 AS BIT*1
x4 AS BIT*1
y1 AS BIT*1
y2 AS BIT*1
END TYPE
'
FUNCTION PBMAIN () AS LONG
LOCAL var AS bf
'
var.x1=0
var.x2=0
var.x3=0
var.x4=1
'assume we have logical expression as
var.y1=(var.x1 AND var.x2 AND var.x3 AND var.x4) OR _
(NOT(var.x1) AND var.x2 AND var.x3 AND var.x4) OR _
(var.x1 AND NOT(var.x2) AND var.x3 AND var.x4) OR _
(var.x1 AND NOT(var.x2) AND var.x3 AND NOT(var.x4)) OR _
(NOT(var.x1) AND NOT(var.x2) AND var.x3 AND var.x4)
'
'by plaing on cards of Carno(Karno) we can simplify expression to
'
var.y2=(var.x3 AND var.x4) OR (var.x1 AND var.x2 AND var.x3)
'
? "var.y2="+STR$(var.y2),,"var.y1="+STR$(var.y1)
END FUNCTION

Sometimes its very helpful for optimization by speed.

------------------
-=Alex=-

[This message has been edited by Aleksandr Dobrev (edited January 19, 2007).]

IP: Logged

All times are EasternTime (US)

next newest topic | next oldest topic

Administrative Options: Close Topic | Archive/Move | Delete Topic
Post New Topic  Post A Reply
Hop to:

Contact Us | PowerBASIC BASIC Compilers

Copyright © 1999-2006 PowerBASIC, Inc. All Rights Reserved.


Ultimate Bulletin Board 5.45c