Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!mit-eddie!bloom-beacon!eru!hagbard!sunic!mcsun!ukc!axion!tharr!uk.ac.bristol.siva From: ARD@uk.ac.bristol.siva (Tony Duell) Newsgroups: comp.sys.handhelds Subject: HP48 & symbolic boolean algebra Keywords: HP48 boolean algebra Message-ID: <1038@tharr.UUCP> Date: 27 Sep 90 09:15:26 GMT Sender: pm111@tharr.UUCP Reply-To: Tony Duell Organization: Public Access to Usenet in the UK Lines: 432 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