ARD@uk.ac.bristol.siva (Tony Duell) (09/27/90)
A few days ago, someone (I forget who) was asking about using the HP48 for
symbolic boolean algebra. Here are some routines that will do that - the
best way to find out how to use them is to try them , but I will explain
/give examples for any that you don't understand.
Here's an example:
{1 2 3} 2 SOP : A AND NOT B OR NOT A AND B OR A AND B
3 FIRST
1 SEL 1 SEL COMM REP
2 SEL COMM REP
FCTR ON A1 REP
DIST ON A1 : A OR B
Documentation:
-------------
Here's a set of routines to do symbolic boolean algebra on the HP48SX:
The file can be downloaded into your machine using kermit and contains the
following operations:
Sum of products Notation
------------------------
SOP : {n1....nn} nvars -> 'Boolean expression'
Generates the sum-of-products function defined by the list {n1..nn} on
nvars variables.
e.g.
{1 2 3 4} 3 SOP gives A AND NOT B AND NOT C OR NOT A AND B AND NOT C OR
A AND B AND NOT C OR NOT A AND NOT B AND C
SOPTRM : nvars term -> 'boolean expression'
Generates one SOP term
e.g. 2 1 SOPTRM gives A AND NOT B
De Morgans Laws
---------------
DMA : 'Boolean expression' -> 'Boolean expression'
DeMorgans law on AND
A AND B -> NOT( NOT A OR NOT B)
DMO : 'Boolean expression' -> 'Boolean expression'
DeMorgans law on OR
A OR B -> NOT (NOT A AND NOT B)
Simple Identities
---------------
DBN : 'Boolean expression' -> 'Boolean expression'
Remove DouBle Not
NOT NOT A -> A
AN : 'Boolean expression' -> 'Boolean expression'
A AND NOT A -> 0
ON : 'Boolean expression' -> 'Boolean expression'
A OR NOT A -> 1
A0 : 'Boolean expression' -> 'Boolean expression'
A AND 0 -> 0
A1 : 'Boolean expression' -> 'Boolean expression'
A AND 1 -> A
O0 : 'Boolean expression' -> 'Boolean expression'
A OR 0 -> A
O1 : 'Boolean expression' -> 'Boolean expression'
A OR 1 -> 1
I0 : 'Boolean expression' -> 'Boolean expression'
Insert 0
A -> A OR 0
I1 : 'Boolean expression' -> 'Boolean expression'
Insert 1
A -> A AND 1
Distribution operators
----------------------
DIST : 'Boolean expression' -> 'Boolean expression'
Distribute top level function over 2nd level function (on RIGHT)
A op1 (B op2 C) -> A op1 B op2 A op1 C
where op1 and op2 are AND or OR
DOO Distribute OR over OR
DOA Distribute OR over AND
DAO Distribute AND over OR
DAA Distribute AND over AND
All : 'Boolean expression' -> 'Boolean expression'
Factorisation operators - Inverses to Distribution
--------------------------------------------------
FCTR : 'Boolean expression' -> 'Boolean Expression'
Factor 2nd level out of top level
A op1 B op2 A op1 C -> A op1 (B op2 C)
FOO, FOA, FAO, FAA exact inverses of DOO etc.
Equation manipulation
---------------------
SEL : 'expression' Argno -> 'Unchanged expression' Argno 'subexpression'
Select a subexpression from the top-level function of 'expression'
Argno is 1 for the left (or only)argument, 2 for the right argument.
The stack is left in a form suitable for manipulating 'subexpression'
and using REP
e.g. 'A AND (B OR C)' 2 SUB gives 'A AND (B OR C)' 2 'B OR C'
REP : 'expression' Argno 'subexpression' -> 'changed expression'
REPlace 'subexpression' in the Argno position of the top-level function in
'expression' Use to undo SEL
e.g. 'A AND NOT NOT B' 2 'B' REP gives 'A AND B'
(SEL can be used recursively to isolate a subexpression, and then after
manipulating it, REP will re-assemble the expression)
COMM : 'expression' -> 'expression'
Commute the arguments of the top-level function in 'expression'
e.g. 'A AND B' COMM gives 'B AND A'
low-level distribution/factoring routines
----------------------------------------
DST 'expression' "OP1" "OP2" -> 'expression'
Distribute "OP1" over "OP2" in 'expression'
FCT 'expression' "OP1" "OP2" -> expression
Factor OP1 out of OP2 in expression
SETFD "OP1" "OP2" -> 'exp1' 'exp2'
Generate internal pattern-match data for DST and FCT
FIRST 'expression' n -> 'expression'
move nth term to first in expression (provided all operators above it are
of the same type)
e.g. 'A AND B AND C' 3 FIRST gives 'C AND B AND A'
NTP 'expression' -> n
Number of operators directly below or at the top level of the same
type to top
e.g. 'A AND B AND C' NTP gives 2
M1ST 'expression' n m -> expression
Internal function used by FIRST - moves mth term in string of n to first
position
TOPFN 'expression' -> "OP"
Returns name of top-level function in expression
e.g. 'A AND B' TOPFN gives "AND"
GEN1 "OP" n m -> 'expression'
Returns 'expression' containing n terms of form &A.... joined with operator
"OP". Terms occur in order except that mth term is swapped with the first.
e.g. "AND" 5 3 GEN1 gives &C AND &B AND &A AND &D AND &E
Written by A.R.Duell and placed in the public domain. This software may be
freely reproduced, and published in user-group newsletters provided this
notice is retained. Further information can be obtained by contacting me
at:
JANET: ARD@ UK.AC.BRIS.SIVA (or BRIS.PVA if you haven't updated yet)
BITNET: ARD @ SIVA.BRIS.AC.UK
2391 bytes , checksum #677Fh
---------------->8------------->8--------->8-------------cut here------->8----
%%HP: T(3)A(R)F(.);
DIR
SOP
\<< OVER SIZE \-> n
m
\<< DUP 1 GET n
SWAP SOPTRM SWAP 2
m
FOR i i
OVER SWAP GET n
SWAP SOPTRM 3 ROLL SWAP
OR SWAP
NEXT DROP
\>>
\>>
SOPTRM
\<< \-> n m
\<< 1 n
FOR i i 64
+ CHR "'" + "'"
SWAP + OBJ\-> 2 i 1 -
^ R\->B m R\->B AND B\->R
IF 0 ==
THEN NOT
END
IF i 1 >
THEN AND
END
NEXT
\>>
\>>
DMA
\<< { '&X AND &Y'
'NOT(NOT &X OR NOT
&Y)' } \|vMATCH DROP
\>>
DMO
\<< { '&X OR &Y'
'NOT(NOT &X AND NOT
&Y)' } \|vMATCH DROP
\>>
DBN
\<< { 'NOT NOT &X
' &X } \|vMATCH DROP
\>>
AN
\<< { '&X AND NOT
&X' 0 } \|vMATCH DROP
\>>
ON
\<< { '&X OR NOT
&X' 1 } \|vMATCH DROP
\>>
A0
\<< { '&X AND 0'
0 } \|vMATCH DROP
\>>
A1
\<< { '&X AND 1'
&X } \|vMATCH DROP
\>>
O0
\<< { '&X OR 0'
&X } \|vMATCH DROP
\>>
O1
\<< { '&X OR 1' 1
} \|vMATCH DROP
\>>
I0
\<< { &X '&X OR 0
' } \|vMATCH DROP
\>>
I1
\<< { &X '&X AND
1' } \|vMATCH DROP
\>>
DIST
\<< DUP TOPFN \->
fn1
\<< 2 SEL TOPFN
SWAP DROP fn1 SWAP
DST
\>>
\>>
DOO
\<< "OR" DUP DST
\>>
DOA
\<< "OR" "AND"
DST
\>>
DAO
\<< "AND" "OR"
DST
\>>
DAA
\<< "AND" DUP DST
\>>
FCTR
\<< DUP TOPFN \->
fn1
\<< 1 SEL TOPFN
SWAP DROP fn1 FCT
\>>
\>>
FOO
\<< "OR" DUP FCT
\>>
FOA
\<< "OR" "AND"
FCT
\>>
FAO
\<< "AND" "OR"
FCT
\>>
FAA
\<< "AND" DUP FCT
\>>
SEL
\<< \-> n
\<< DUP OBJ\->
DROP DUP
IF n <
THEN DROPN
ELSE \->LIST
n GET n SWAP
END
\>>
\>>
REP
\<< \-> n trm
\<< OBJ\-> \-> tfn
\<< \->LIST n
trm PUT OBJ\-> DROP
tfn EVAL
\>>
\>>
\>>
COMM
\<< DUP OBJ\-> \->
tfn
\<< DUP
IF 2 \=/
THEN DROPN
ELSE DROP
SWAP tfn EVAL SWAP
DROP
END
\>>
\>>
DST
\<< SETFD 2 \->LIST
\|vMATCH DROP
\>>
FCT
\<< SETFD SWAP 2
\->LIST \|vMATCH DROP
\>>
SETFD
\<< \-> fn1 fn2
\<< "'&X " fn1
+ "(&Y " + fn2 +
" &Z)'" + OBJ\->
"'(&X " fn1 +
" &Y )" + fn2 +
" (&X " + fn1 +
" &Z)'" + OBJ\->
\>>
\>>
FIRST
\<< OVER NTP 1 +
SWAP M1ST
\>>
NTP
\<< DUP DUP TOPFN
1 \-> tfn i
\<<
DO 1 SEL \->
sub
\<< DROP
DROP sub DUP TOPFN
'i' INCR DROP
\>>
UNTIL tfn \=/
END DROP
DROP i 1 -
\>>
\>>
M1ST
\<< 3 PICK TOPFN
\-> n m tfn
\<< tfn n 1
GEN1 tfn n m GEN1 2
\->LIST \|^MATCH DROP
\>>
\>>
TOPFN
\<<
IFERR OBJ\->
THEN DROP ""
ELSE \->STR \->
tfn
\<< DROPN tfn
\>>
END
\>>
GEN1
\<< \-> m
\<< DUP
IF 1 >
THEN "&" m
64 + CHR + SWAP 2
SWAP
FOR i
OVER " &" + " "
SWAP + +
IF i m
==
THEN
"A"
ELSE i
64 + CHR
END +
NEXT SWAP
DROP "'" + "'" SWAP
+ OBJ\->
END
\>>
\>>
END