[Tutor] How different is math logic from computer logic?

Magnus Lycka magnus@thinkware.se
Sun Dec 8 19:01:06 2002


Computer logic is 19th century math logic. It's certainly
present in todays programming languages, but due to the
advanced modern computers and the level of abstraction in
programming languages like Python, you don't have to use it
all the time...

You can write something like "print 5 + 3 * 7" and let the
software and hardware turn all that into logic expressions.

At 22:43 2002-12-07 -0500, James M Lang wrote:
>If I work, I cannot study. Either I work or I pass Math. I pass Math. 
>Therfore, I studied.

I'd say this is "philosophy logic" rather than "math logic".
Although, when Aristotele invented this in the 4th century BC,
I don't think people made any distinction. Aristotele's main
interest was syllogism, the kind of conclusion drawing that you
give an example of above.

In the 19th century, british mathematician George Boole introduced
symbolic logic or Boolean Algebra as we call it today. Basically,
he made a simple and a complete algebraic system containing only two
"digits": True and False, and three operations, AND, OR and NOT. If
we use the following symbols:

True: 1
False: 0
And: *
Or: +

We end up with something very similar to ordinary algebra:

0 * 0 = 0
0 * 1 = 0
1 * 0 = 0
1 * 1 = 1

This means that if we have two statements A and B, then the
statement "A and B" will only be true if both A and B are
true.

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1

This means that "A or B" is only true is at least one of A or
B are true.

The last one "1+1=1" is obviously different from normal argebra, but
7 out of 8 isn't bad? ;) So, this is a slightly different system
than normal algebra, and it's purpose was to make it possible to
handle logic issues as if they where mathematical equations.

Note that there is a source of confusion here. When we normally say
"5 and 3 is 8", we mean "5 + 3 = 8", but logic AND isn't written with
'+' but with '*'. This is because logical AND resembles multiplication
very much, and logical OR is more similar to addition, as you see above.

But there is one opetaion missing: NOT. The NOT operator is often
written with a bar above the symbol, like this:
_
X

But that's inconvenient with email etc, so now we often write !
instead, and thus we get:

1 = !0 (True is not false)
0 = !1 (False is not true)

Then we can write things like "I will go out if it's not raining
and if it's warm" like:

will_go_out = !raining * warm

Normal English is a little tricky. A sentence like "I will go
out if it's not raining and if it's warm or if I have a warm
coat" might either mean...

will_go_out = (!raining * warm) + warm_coat

...or...

will_go_out = !raining * (warm + warm_coat)

...the difference being whether I will go out if I have a warm
coat, it's not warm, and it's raining. As you see, all contracts
ought to be written in Boolean Algebra instead of English etc
to avoid these kinds of ambiguities. Boolean logic binds * harder
than + just like normal algebra, so

will_go_out = !raining * warm + warm_coat

means the same as

will_go_out = (!raining * warm) + warm_coat

By making much more complex boolean equations we can perform
ordinary algebraic additions, subtractions, multiplications etc.

For instance, to be able to add two two bit positive numbers
(in other words 0, 1, 2 or 3) like this:
0 + 0 = 0
0 + 1 = 1
0 + 2 = 2
...
3 + 3 = 6

Or in binary:
00+00=000
00+01=001
00+10=010
00+11=011
01+00=001
01+01=010
01+10=011
01+11=100
10+00=010
10+01=011
10+10=100
10+11=101
11+00=011
11+01=100
11+10=101
11+11=110

You need three equations, since you need three output bits (6 is
110 in binary, a three bit value, right?)

Assuming the four input bits are called I1 to I4, and the
output bits are called O1 to O3, the following logic equation will
do the job.

O1 = I1 AND I2 AND I4 OR I2 AND I3 AND I4 OR I1 AND I3

O2 = I1 AND I2 AND I3 AND I4 OR NOT I1 AND I2 AND NOT I3 AND I4 OR
      I1 AND NOT I2 AND NOT I3 OR I1 AND NOT I3 AND NOT I4 OR NOT I1
      AND NOT I2 AND I3 OR NOT I1 AND I3 AND NOT I4

O3 = I2 AND NOT I4 OR NOT I2 AND I4

O3 is the simplest equation. It says that the output will be
odd if either input (but not both) are odd.

(A modern CPU will be slightly more complex ;) and do things like
multiply or divide two 32 bit numbers. I'm not going to show
complete equations for that... It's not your problem unless you
design a brand new CPU...)

As you know, transistors, and later integrated circuits with many
transistors (etc) on a chip of e.g. silicon, were invented in the
middle of the last century. IIRC, it was in a M.Sc. paper at MIT,
that someone suggested that the combination of transistors and
Boolean Algebra could be used to build calculation machines.

By using a convention like current on = true and current off = false
(or vice versa, or let the voltages control rather than the current)
we can model our states true and false.

Using a few transistors, we can build circuits that perform the
boolean operations AND, OR and NOT.

This URL gives an example of how to add two binary digits with
transistor based circuits that model Boolean Algebra.
http://isweb.redwoods.cc.ca.us/INSTRUCT/CalderwoodD/diglogic/full.htm

You can look at http://www.play-hookey.com/digital/ to find out more
about that kind of components that computers are built on.

Once upon a time, this was central to all programming, but as I
wrote in the beginning, we don't need to bother with this all the
time now.

We do have the tools to do it if we want though.

Python has the logic operators like and, not and or. It has
binary operators like &, | and ^. You have if-statements and
you can write expressions. So, using Python to describe logic
is typically simple. What is not so simple is to make the
computer draw conclusions based on your facts. Other programming
languages are better at that. Prolog for instance.


/Magnus


-- 
Magnus Lycka, Thinkware AB
Alvans vag 99, SE-907 50 UMEA, SWEDEN
phone: int+46 70 582 80 65, fax: int+46 70 612 80 65
http://www.thinkware.se/  mailto:magnus@thinkware.se