The Truth is Out There!
by Dale Wick for AdamCon 13, July 13, 2001
It is often said that the world from a computer's perspective can be
broken down into two camps. Those are variously called 0 and 1 or true
and false or on and off. In electronics these are also 0 volts and +5 volts.
Now if you use the Adam, you probably have never spent time giving it
instructions as a string of 0's and 1's. This is because the actual details
are "abstracted" from you to make it easy to acomplish ever larger tasks.
abstraction is the process of hiding all of the details of
the solution to a problem.
Today we will actually work with the following functions:
- NOT - inversion is false if A is true
- AND - requires that both A and B are true.
- OR - called an inclusive or, which is true if any of A or B are true.
- XOR - exclusive or, which is true of one but not both A and B are true.
- NAND - inverted version of AND
- NOR - inverted version of OR
Understanding symbols
To work with these there is an abreviated notation:
- AND is represented by 'x' or no symbol (like multiplication)
- OR is represented by '+'
- NOT is represented by '!' or a bar overtop
Truth Tables
A truth table is a table that shows all of the inputs, and the output with each combination of inputs:
| A |
B |
!A |
!B |
AB |
!(AB) |
(!A) + (!B) |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 |
Algebraic simplification
Whenever you have a formula, you can translate it using the following
substitutions.
A + 0 = A
A + 1 = 1
A + A = A
A + !A = 1
A + AB = A
A!B + B = A + B
AB + A!B = A
AB + BC + (!A)C = AB + (!A)C
|
A x 0 = 0
A x 1 = A
A x A = A
A x !A = 0
A(A + B) = A
(A + !B)B = AB
(A + B)(A + !B) = A
(A + B)(A + C) = A + BC
|
Experimenting in SmartBASIC
10 print "A","B","result"
100 a=0: b=0: GOSUB 200
110 a=0: b=1: GOSUB 200
120 a=1: b=0: GOSUB 200
130 a=1: b=1: GOSUB 200
199 END
200 REM The formula
210 c=a OR b
220 ? a,b,c
230 RETURN
Change the formula in line 210 to each of the following:
210 c=NOT a
210 c=NOT (a AND b)
210 c=NOT (a OR b)
210 c=a AND b
210 c=a OR b
210 c=(a OR b) AND a<>b
Now we can prove some of the subsitutions using truth tables.
