PARENTS:
LOGIC WORKSHOP
WORKSHOPS
ARCHIVE
===============================================================================
Exact Two-dimensional Propositional Calculus.
---------------------------------------------
Propositional Calculus encompasses operands and operators. Operands are
statements with which we associate a variable "certainty".
For Exact Calculus certainty may take one of two values: "true" and "false",
symbolized respectively with "1","0".
For simplicity's sake we shall say that a statement is true, or that its value
is 1, always implying the certainty of the statement.
For two-dimensional Calculus operators operate on two operands and have a
certainty variable being function of those of both operands. As for operands,
we shall say "operator is true/false", implying by it its certainty.
For example operator "and" is true if and only if both operands are true, which
may be symbolized for a couple of operands p,q as follows:
and(p,q)
1 1 1
0 1 0
0 0 1
0 0 0
For above 4 combinations of p,q we have clearly 16 operators (o1-o16) listed
below:
p q o1 o2 o3 o4 o5 o6 o7 o8
1 1 0 1 1 1 0 0 0 1
1 0 1 0 1 1 0 1 1 0
0 1 1 1 0 1 1 0 1 0
0 0 1 1 1 0 1 1 0 1
p q o9 o10 o11 o12 o13 o14 o15 o16
1 1 1 1 0 0 0 1 0 1
1 0 0 1 0 0 1 0 0 1
0 1 1 0 0 1 0 0 0 1
0 0 0 0 1 0 0 0 0 1
Following operators are particularly important: (Lists of their certainties may
be more concisely shown as horizontal strings.)
operator horizontal string
-------- -----------------
o14: and 1000
o4: or 1110
o7: orr, exclusive or, either or 0110
o2: implica1ion 1011
o8: equivalence 1001
Operators may in turn become operands, which allows chains of operations, known
as "inference chains", or shortly "inferencing" as shown in the simple example:
orr( (and(p,q)),(or(r,s)) )
1 0 1 0
0 1
1
Inferencing may extend over thousands of operations. Certainties of the lowest
level (p,q,r,s) may be factual and inferencing determines their logical
consequences.
Besides the above mentioned binary operators the Calculus encompasses a unary
operator "not" which operates on one operand and negates its certainty replacing
1 by 0 and vice versa:
not(p)
0 1
1 0
Besides the essential symbols, i.e. operators, operands and brackets, we shall
introduce for convenience expressions, explained in the following example.
===============================================================================
Example of Calculus' operations.
An expression marked "En" encompasses a main operator followed by bracketed
structure of operators/operands. Expression has an associated certainty string
which it shares with the main operator. En, Em having identical strings are
equal and marked En=Em. Otherwise, they are not equal and marked En!=Em.
"=" symbol is also used to associate expression with its main operator:
E1=and(pq).
Operators and expressions can become in turn operands and searching,
for instance, the solution of:
(1) if and(pq) implies or(pq) then X(pq) where X is an unknown operator.
We may write it in form of expressions:
E1=imp(and(pq).or(pq))
E2=X(pq)
E3=and(pq)
E4=or(pq)
thus E1=imp(E3,E4)
We evaluate expressions starting by those in brackets:
E3=and(pq)
1..1...11
0..0...10
0..0...01
0..0...00
E4=or(pq)
1..1..11
1..1..10
1..1..01
0..0..00
E1=imp(E3,E4)
1..1...1..1
0..0...0..1
0..0...0..1
1..1...0..0
Now, by equalizing E1 with E2 we may search X.
E1=E2=X(pq)
1..1..1.11
0..0..0.10
0..0..0.01
1..1..1.00
Looking up the operators table we see that X=eq and we can write the solution
of (1):
if and(pq) implies or(pq) then q is equivalent to p
The same chain of operations could be written without simplification by E3, E4
in one step:
E1=imp(and(pq).or(pq))=E2=eq(pq)
1..1...1...11..1..11...1..1..11
0..0...0...10..1..10...0..0..10
0..0...0...01..1..01...0..0..01
1..1...0...00..0..00...1..1..00
It's more difficult, but with a little practice it becomes very easy to write
directly such summaries even for much more complex expressions. However, when
in doubt, it's advisable to follow Descartes and to decompose a complex
expression into several simple ones.
Let's note: Calculus tells us that if and(pq) implies or(pq) then p and q
are equivalent.
Result by no means obvious and quite useful for instance in programming where
we can replace "imp(and(pq).or(pq))" with much simpler "eq(pq)".
Similarly:
if(and(pq)) does not imply (or(pq)) then p and q are mutually exclusive:
E1=not(imp(and(pq).or(pq)))=E2=orr(pq)
0..0...1...1...11..1..11....0..0...11
1..1...0...0...10..1..10....1..1...10
1..1...0...0...01..1..01....1..1...01
0..0...1...0...00..0..00....0..0...00
===============================================================================
EXERCISE B
Many beginning programmers replace intuitively and wrongly
E1=and(not(p),not(q)) with E5=not(and(pq))
It's difficult to explain them their error without help of the Calculus and
very easy to do it using Calculus.
1.Show the error.
2.Find correct X in E1=E2=not(X(pq)).
First using intermediary expressions E3=not(p) E4=not(q) and afterwards
without them.
===============================================================================
EXERCISE C
A theorem of Calculus says that any operator may be constructed from any two
other ones with optional help of "and" and "not".
Example:
--------
Show that "imp" may be constructed from
"eq" and "or".
E1=imp(pq) = E2=or(eq(pq),and(not(p),q))
1..1...11....1..1..1..11..0...0...1..1
0..0...10....0..0..0..10..0...0...1..0
1..1...01....1..1..0..01..1...1...0..1
1..1...00....1..1..1..00..0...1...0..0
Thus E1=E2 QED
Exercise:
---------
Show that "orr" may be constructed from "or" and "and":
===============================================================================
PARENTS:
LOGIC WORKSHOP
WORKSHOPS
ARCHIVE