
Christian  M. H a m a n n Lev C h t c h e r b a n s k i
Informatik / KI + Bionik / ES
TFHBerlin / Germany TUBerlin / Germany
hamann@tfhberlin.de
********************************************
* *
* Positional Logic Algebra *
* *
*  PLA  *
* *
* A fascinating alternative approach *
* *
********************************************
ICSI Technical Report (1997) TR97039
Abstract

The Russian researcher, M. Telpiz, presented 1985 in Russia a totally new
approach to logic algebra (and L. Chtcherbanski, a friend of his, brought
the ideas to Berlin/Germany in 1995). PLA may be an elegant and better
representation for some problem domains then the Boolean Algebra.
Highlights of PLA are:
o Only one simple algorithm holds for all calculations
o Invert operators build invert functions
o Operators are directly applicable on operators and therefore
o Compilation of multilayer networks are possible via simple
calculations over operators only
PLA has a potential for new applications in logical calculus problems,
specially with many variables. Because operators are directly applicable
on operators, PLA may be of special interest in research areas of
Genetic Algorithms, EvolutionStrategy and Artificial Life.
********
In solving logic calculations with conventional Boolean Algebra the
exponential increase in complexity with the increasing number of variables
is a sound problem. The "Positional Logic Algebra" (PLA), first presented
by Telpiz in 1985, promised to give tools for braking down this problem.
Each logic algebra deals with the functional dependencies of the values from
the logic variables and the values from the logic function. One can say: A
function is a transformation from one set into another set. If we have a
set of variables with twovalues {0,1} and a function which produces a new
set with twovalues {0,1}, then this function is called a logic function in
dual logic or Boolean Logic.
1. Boolean Algebra

X Y  X AND Y  X OR Y Z  NOT Z
================================== ===============
0 0  0  0 0  1
0 1  0  1 1  0
1 0  0  1
1 1  1  1
Tab.1 Truthtables of AND, OR and NOT

The truthtables shown above, are the bestknown functions AND and OR,
connecting two logic variables X and Y, and the function NOT for negation
of a variable Z. A logic function of many variables is defined by a set of
terms. Each term is a unique nary combination of zeros and ones. Following
the convention, the terms are sorted in dualcode sequence. The set of all
terms (associated with the functionvalue) is called the logic function.
With these 3 logic soundfunctions AND, OR and NOT all other functions of
the dual logic can be made. But the function NAND (NOTAND, Sheffer Stroke)
alone or the function NOR (NOTOR, Peirce Function) alone could be used as
soundfunctions.
The following table shows systematically all possible Boolean functions for
two variables X and Y.
Nr.X=0 0 1 1 Boolean equivalent mathematical short colloquial
Y=0 1 0 1 Operatorsound function description  language
============================================================================
0  0 0 0 0  0  Contradiction FALSE never
1  0 0 0 1  X ^ Y  Conjunction  AND and
2  0 0 1 0   X ^ ~Y Inhibition2  
3  0 0 1 1  X  Projection1  
4  0 1 0 0   ~X ^ Y Inhibition1  
5  0 1 0 1  Y  Projection2  
6  0 1 1 0  X \= Y  (X^~Y)v(~X^Y) Disvalence  XOR eitheror
7  0 1 1 1  X v Y  Disjunction  OR or
8  1 0 0 0  X * Y  ~X ^ ~Y PeirceFunc.  NOR neithernor
9  1 0 0 1  X = Y  (X^Y)v(~X^~Y) Equivalence  EQ ifandonlyif
10  1 0 1 0  ~Y  Negation2  
11  1 0 1 1  X < Y  X v ~Y Implication1  thenif
12  1 1 0 0  ~X  Negation1  
13  1 1 0 1  X > Y  ~X v Y Implication2  ifthen
14  1 1 1 0  X  Y  ~X v ~Y ShefferFunc. NAND allnot
15  1 1 1 1  1  Tautology  TRUE ever
Tab.2 All possible Boolean functions for two variables X and Y

2. Positional Logic Algebra

The following example shows, how the value of a logical function P(X) with
the variables X1 ... X4 is calculated in the Positional Logic Algebra (PLA)
with the Positional Operator p.
In the line of these 4 variables X1 ... X4 we mark 4 + 1 positions:
"Infrontof", "between 1 ... 3" and "behind". The positions are labeled
with symbols ":" and "_", for example:
P(:X1_X2:X3_X4_)
^ ^ ^ ^ ^
0 1 2 3 4 < position number k
The Positional Operator p is the sequence of the labels ":" (=1) and
"_" (=0). The bracketed values (1 or 0) make it possible, to apply
operators on operators (as shown further below).
p = (: _ : _ _) = (10100)
Simple Positional Operators

Inside the operator the label ":" in position k0, k1, k2, ... , ks means:
The line with the values of the variables X1 ... Xn contains k0 (= no) "1"
or k1 or k2 or ... ks "1". The value of the function P(X1 ... Xn) is equal
to the label in the operator p (in 0;1 representation) on the position
number which equals the sum of 1 in this line.
An example:
Function P(:X1_X2:X3_X4_) with operator p = (: _ : _ _) = (10100)

X1 X2 X3 X4  P  Remarks
========================================================================
0 0 0 0  1  No times "1", that's why pos. "0" gives us "1"
0 0 0 1  0  one times "1", that's why pos. "1" gives us "0"
0 0 1 0  0  one times "1", that's why pos. "1" gives us "0"
0 0 1 1  1  two times "1", that's why pos. "2" gives us "1"
0 1 0 0  0  one times "1", that's why pos. "1" gives us "0"
0 1 0 1  1  two times "1", that's why pos. "2" gives us "1"
0 1 1 0  1  two times "1", that's why pos. "2" gives us "1"
0 1 1 1  0  three times "1", that's why pos. "3" gives us "0"
1 0 0 0  0  one times "1", that's why pos. "1" gives us "0"
1 0 0 1  1  two times "1", that's why pos. "2" gives us "1"
1 0 1 0  1  two times "1", that's why pos. "2" gives us "1"
1 0 1 1  0  three times "1", that's why pos. "3" gives us "0"
1 1 0 0  1  two times "1", that's why pos. "2" gives us "1"
1 1 0 1  0  three times "1", that's why pos. "3" gives us "0"
1 1 1 0  0  three times "1", that's why pos. "3" gives us "0"
1 1 1 1  0  four times "1", that's why pos. "4" gives us "0"
Tab.3 Example of how to get the value P out of the operator p

With these "Simple" Positional Operators for n variables one can formulate
2^(n+1) logic functions. The whole number of dual logic functions with n
variables is however 2^(2^n). This means that with Simple Positional Operators
only a subset of dual logic functions can be represented.
This subset contains the well known symmetric logic functions. They are called
symmetric, because the value of the logic function holds, independent of the
permutation of the input variables.
If we write down all possible Simple Positional Operators for two variables,
we find the following functions:
P0(_X1_X2_), P1(_X1_X2:), P2(_X1:X2_), P3(_X1:X2:), ... P7(:X1:X2:)
Each Simple Positional Operator can be described in a binary code. Take all
possibilities for two variables and put it in order of dual code. We get
000, 001, 010, 011, 100, 101, 110, 111. Let's name the operators p0 ... p7
the functions P0 ... P7 and let's make a table:
Operator: p0 p1 p2 p3 p4 p5 p6 p7

X1  X2  000  001  010  011 : 100  101  110  111
==============================================================
0  0  0  0  0  0 : 1  1  1  1
0  1  0  0  1  1 : 0  0  1  1
1  0  0  0  1  1 : 0  0  1  1
1  1  0  1  0  1 : 0  1  0  1

Operation: FALSE AND XOR OR : NOR EQ NAND TRUE
Function: P0 P1 P2 P3 P4 P5 P6 P7
Tab.4 Symmetric properties of PLA operators for two variables

In analyzing the table, it shows that operators and function values of the
left side are mirrored to those of the right side of the table and that the
inverted operator generate the appropriate inverted function!
It is also remarkable, that for calculations of all functions only one simple
algorithm is used: First calculate the number of "1" in the term and then
choose the symbol {0;1} according to the position in the operator.
If we write down all possible functions Q0 ... Q3 for one variable Z, we get:
Operator: q0 q1 q2 q3

Z  (_Z_)  (_Z:)  (:Z_)  (:Z:)
============================================
0  0  0  1  1
1  0  1  0  1

Operation: FALSE Z ~Z TRUE
Function: Q0 Q1 Q2 Q3
Tab.5 All possible PLA functions for one variable

The special functions and its operators are:
Q1(_Z:) q1 = (_:) = (01) "IDENTITY"
Q2(:Z_) q2 = (:_) = (10) "NOT"
A Useful PLA Example: The Parity Detector for 32 Bit

X31 X30 X29 ... X03 X02 X01 X00 Input ( 32 Bit )
o o o o o o o
      
++
ShouldBeOdd ShouldBeEven
++
 
o o
SBO SBE Output ( 1 Bit each )
Fig.1 32 Bit Parity Detector

The "inner" PLA function to calculate parity is P:
P(_X31:X30_X29: ... _X03:X02_X01:X00_)
With the IDENTITY and NOT we calculate the output functions:
SBO(_P:) and SBE(:P_)
Multilayer Calculations / Compilations

Positional Logic Algebra allows the application of operators on operators
in order to get new operators. In Boolean Algebra this is not possible:
A construction like ( AND ( OR AND )) is in Boolean Algebra meaningless.
The following example shows, how the operator b ( the function B ) is
calculated by application of operator c on the operators ai.
++ ++ ++
X1 o = a1    X1 o  
=   c1 o B1  b1 o B1
++    
X2 o . ++ . ++ X2 o .  
. = a2  . equivalent . ++
. =  . . ++
X3 o . ++ ++ X3 o .  
++    
= a3   c2 o B2  b2 o B2
X4 o =    X4 o  
++ ++ ++
Fig.2 Example of how to compile a multilayer in a singlelayer network
 (Dots mean: Connect leftside points with all rightside points)
Look at an example of the functions A1, A2 and A3 with the operators a1, a2
and a3 given:
A1(_X1_X2:X3:X4_) a1 = (00110)
A2(_X1:X2_X3_X4:) a2 = (01001)
A3(:X1_X2_X3:X4:) a3 = (10011)
Lets make the operators c1 and c2
c1 = (0101)
c2 = (1010)
with the functions C applied on the functions A we will get functions B
(as shown in Fig.2):
C1(_A1:A2_A3:) = B1( X1 ... X4 )
C2(:A1_A2:A3_) = B2( X1 ... X4 )
For compiling the network, we search for the operators b1 and b2 and find them
by application of operators c1 and c2 on operators a1...a3 in handling these
like variables!
k  a1 a2 a3  s  b1 b2
===================================
0  0 0 1  1  1 0
1  0 1 0  1  1 0
2  1 0 0  1  1 0
3  1 0 1  2  0 1
4  0 1 1  2  0 1
Tab.6 see text

In Tab.6 k is the position number of the operator ai (written as columns).
s is the number of "1s" in the lines of ai. These refer to the positions in
c1 resp. c2. One get operator b equal "1", if there is a colon (resp. 1) in
operator c, or "0", if there is an underline (resp. 0) in it.
So we find:
B1(:X1:X2:X3_X4_) b1 = (: : : _ _) = (11100)
B2(_X1_X2_X3:X4:) b2 = (_ _ _ : :) = (00011)
In calculating the whole truthtable, one can prove the result. One can see:
o With this easy received operator b, applied on the variable X one can get
the function B directly without detour via A and C and
o The operators c1 and c2 are inverted; the results of B1 and B2 are
inverted also.
X1 X2 X3 X4  A1 A2 A3  B1 B2
==========================================
0 0 0 0  0 0 1  1 0
0 0 0 1  1 0 0  1 0
0 0 1 0  1 0 0  1 0
0 0 1 1  0 1 0  1 0
0 1 0 0  1 0 0  1 0
0 1 0 1  0 1 0  1 0
0 1 1 0  0 1 0  1 0
0 1 1 1  0 1 1  0 1
1 0 0 0  1 0 0  1 0
1 0 0 1  0 1 0  1 0
1 0 1 0  0 1 0  1 0
1 0 1 1  0 1 1  0 1
1 1 0 0  0 1 0  1 0
1 1 0 1  0 1 1  0 1
1 1 1 0  0 1 1  0 1
1 1 1 1  1 0 1  0 1
Tab.7 Truthtable of the multilayer network

Complex Positional Operators

Unsymmetrical logic functions can be traced back to the symmetrical ones
(see Boolean table, Tab.2) via transfer functions. For example the two
Implications:
IF X THEN Y <=> (NOT X) OR Y resp. X > Y <=> ~X v Y
X THEN IF Y <=> X OR (NOT Y) resp. X < Y <=> X v ~Y
The function OR for two variables was (see Tab.4):
P3(_X1:X2:) p3 = (_::) = (011) "OR"
The functions NOT for one variable was (see Tab.5):
Q2(:X0_) q2 = (:_) = (10) "NOT"
With OR and NOT and the transfer functions we get the two possible
Implication functions with "Complex" Positional Operators:
Pi2(_(:X_):Y:) pi2 = (_(:_)::) = (0(10)11) "Implication2"
Pi1(_X:(:Y_):) pi1 = (_:(:_):) = (01(10)1) "Implication1"
With the following truthtable, one can get the proof:
X Y  (:X_) (:Y_)  (_(:X_):Y:)  (_X:(:Y_):)

0 0  1 1  1  1
0 1  1 0  1  0
1 0  0 1  0  1
1 1  0 0  1  1

X Y  ~X ~Y  ~X v Y  X v ~Y
 X > Y  X < Y
============================
Tab.8 Truthtable to proof the Implications

3. Positional Logic Algebra vs. Boolean Algebra

What is the relation between Positional Logic Algebra and Boolean Algebra?
As shown above (Tab.4), the soundfunctions AND, OR and NOT and also the
functions NOR and NAND are representable with Simple Positional Operators.
Tab.9 is summerizing all symmetrical Boolean functions on two variables:
P0(_X1_X2_) p0 = (_ _ _) = (000) "FALSE"
P1(_X1_X2:) p1 = (_ _ :) = (001) "AND"
P2(_X1:X2_) p2 = (_ : _) = (010) "XOR"
P3(_X1:X2:) p3 = (_ : :) = (011) "OR"
P4(:X1_X2_) p4 = (: _ _) = (100) "NOR"
P5(:X1_X2:) p5 = (: _ :) = (101) "EQ"
P6(:X1:X2_) p6 = (: : _) = (110) "NAND"
P7(:X1:X2:) p7 = (: : :) = (111) "TRUE"
Tab.9 All possible PLAfunctions and PLAoperators for two variables

We can say: The Boolean Algebra contents the Positional Logic Algebra. PLA
may be an elegant and better representation for some problem domains then
the Boolean Algebra. PLA has obviously a potential for new applications in
logical calculus problems, specially with many variables. Because operators
are directly applicable on operators, PLA may be of special interest in the
research areas of Genetic Algorithms, EvolutionStrategy and Artificial Life.
In the appendix there is a copy of EMail we received in June 1997 from the
Telpizgroup. He is founding a company in Sweden to commercialize his ideas
and he gives some aspects of possible applications he has in mind.
Summarizing the highlights of PLA:
o Only one simple algorithm holds for all calculations
o Invert operators build invert functions
o Operators are directly applicable on operators and therefore
o Compilation of multilayer networks are possible via simple
calculations over operators only
We think, PLA is worthwhile for further research investigations!
4. Literature

[Tel85] Telpiz, M.
"Representation of functions with a logical algebra"
Cybernetica 4(1985)3740 (in Russian)
[CH96] Chtcherbanski, L. + Hamann, C.M.
"Positionelle Logische Algebra 
Eine Alternative mit vielversprechenden Moeglichkeiten"
VDIBrandenburg, TeltowerInnovationsTage, 9.Nov.1996
5. Appendix

In the appendix there is a copy of EMail we received in June 1997 from the
Telpizgroup. He is founding a company in Sweden to commercialize his ideas
and he gives some aspects of possible applications he has in mind.
START OF EMAIL QUOTATION:
***************************************************************************
Extended Computer Logics: ECL System AB
Org. Num. 5565216438
Box 12095
40241 Goteborg
Sweden
Company Profile And Perspectives in April 1997

The Swedish company ECL System AB formed in November 1996 is developing
an exciting new technology called digital logics (or positional logics).
The technology is based on the published new results in fundamental
mathematics but it extends the theory that existed previously and adapts
it for the solution of practical problems in various application domains.
In contrast to the classical logics and programming systems based on it,
in digital logics, knowledge is stored much like the decimal numbers are
used in everyday life or as binary numbers are stored in computers. The
positionbased representation of logical formulas uses a special alphabet
with symbols (productions) corresponding to highlevel transformations of
the logical formulas. The action of these transformations is dependent on
their position in the combined operator (clause). It is important that this
representation of logical formulas is extremely compact. For example, to
express the nonequality of Nbit numbers takes just 1 clause instead of
2^N clauses in the corresponding disjunctive normal form (a conventional
way of representing constraints in logics and arithmetics). The digital
representation of logical information is usually a conjunction of clauses
(a conjunctive form, CF), which can be manipulated upon quite efficiantly
by using algebraic operations and welldefined algorithms.
The company has developed a number of algorithms starting with SATsolver
(used to solve the problems expressed in conjunctive normal form, CNF)
characterized by extremely small and constant memory requirements and
completeness, all the way through to algorithms using progressively
larger number of positional logic productions.
The application domain of digital logics is very wide. Significant gains
can be achieved in almost all problems known as NPcomplete or difficult
problems in discrete mathematics. Below is the list of the potential
application areas where excellent results can be obtained quite fast.
1. Knowledge Learning:
This is a very direct application of the digital logics technology.
Logical knowledge learning is different from the neural networks
because it stores the information as logic formulas that can be
directly interpreted as expert advices of 'professionals' in the
field. This has parallels to constructing a program given the inputs
and outputs, discovering a law of nature based on obsevations,
discovering what an electronic black box is based on sets of its
inputs and outputs, a game AI engine discovering the strategy the
player uses, etc. Expert systems can be constructed automatically
this way. Usually, the logical information is stored as decision
trees or decision lists. Given the highly expressive power of the
digical logics, one can construct (or 'learn') similar but extremely
compact representations of the knowledge when the system is
presented with examples of correct or desirable course of events.
2. Electrical engineering:
Circuits design, logic synthesis, design verification.
The technology can be used for conventional synthesis, but also,
an entirely new type of electronic devices can be developed. The
characteristic properties of those would include compact size,
reversibility, speed, extensibility, testability, and direct
combination of logics, arithmetics, and control. One result
obtained by our research team is of particular importance to
electronics applications: A special reduced representation of the
conjunctive form allows for output of solution vectors in linear
time, and given an enormous expressive power of positional logics
formulas, this form is quite compact, and lends itself for direct
hardware implementation.
3. Integer linear programming, integerdomain equations:
Addressing these types of hard (NPcomplete) problems by converting
them to conjunctive normal form (CNF) leads to exponential texts,
and, obviously, exponential solution times. Suppose you want to
write down the constraint that the two 5bit numbers are equal if a
certain flag is set: f=>(a==b). In conjunctive normal form (CNF)
one writes 2^5=32 clauses, while only one positional logics clause
is sufficient for 5 bits and any larger number of bits. Moreover,
the clauses that constitute the problem can be a conjunction of
arithmetic, logical constraints (like a+3b<4, 15ca>3, d=(a=b),
(d OR g)=>(t1 OR t2)), and special control statements. The mixture
of linear programming and logical constraints and control has
enormous application potential, and we would like to see concrete
customers problems in this field. We are also in the process of
writing a generalpurpose integer linear programming solver.
4. Recource allocation, scheduling
(including multiprocessor scheduling):
These areas typically require the problems of graphcoloring type
to be solved efficiently. The specialized algorithms are under
development that will find the solutions very fast. In particular,
complete versions of algorithms make it possible to prove that a
given coloring does not exist. By combining the algorithm with
conventional techniques, we expect to achieve record performance.
5. Optimal classification (discretization) problem:
Given the set of multiparameter observations on a system, find
optimal classifiers (minimum number of planes) that divide the
multidimensional parameter space in boxes with one or no
observation in each box. This important step is needed to reduce
the multiparameter realvalued information about the complex
system for feeding into any type of decisionmaking system (for
example, the abovementioned a decisiontree system or a neural
network).
6. Theorem proof and firstorder logic engines.
In addition to the development for the mentioned immediate applications
of the technology, the company is extending its lead in the area of
computational logics by conducting extensive research. The ultimate goal
is the construction of the complete set of productions that should
achieve linear computation times (provided the problem is written down
using these operators) and open the perspective for the computers capable
of reasoning. The other future plans include the development of extremely
fast algorithms for large number factorization problems.
ECL System AB will now be concluding cooperation agreements with some
European hightech companies (including transportation, communications,
and medical companies). The company will also be negotiating a special
agreement with IBM Research in US to implement a new technology for
digital circuits verification.
...
Discussion Items for the Forthcoming Meetings with Companies in May 1997

1. Arithmetization of logics:
Functions are stored in a positional way resembling numbers in any
positional system (decimal, binary...).
The 'digits' in the alphabet are called productions, the 'numbers'
are called operators.
There is a large class of logical and arithmetical functions that
can be expressed as one operator.
Any operator can be negated in linear time.
All logical functions can be expressed as collections (tables) of
operators with different logical operations between them.
Generalized resolution infers knowledge by transforming collections
of operators into a form that excludes conflicts in the full set of
symmetrically equivalent failure paths; this form contains all
solutions to the problem and can generate them in linear time.
Obviously, one operator generates solutions in linear time.
2. Important recent engineering results:
Any linear system in GF(2) (a conjunction of parity functions) is
expressed as one operator; moreover, any negation, disjunction, or
conjunction of linear systems are all together expressed as one
operator.
If I and J are Nbit numbers then
I <, =, !=, > const
I <, =, !=, > J
require only one operator.
The above operators can be 'controlled' by setting values to a
subset of bits, then the remaining bits of the solutions can be
output in linear time.
3. CNFsolver. Main features:
Complete;
Very small memory requirements;
Memory is strictly constant during the run including the
case when all solutions are sought;
Record performance for crossoverpoint hardest problems;
It is an optimal replacement for DaviesPutnamLoveland types
of programs.
4. Generalpurpose ConjunctiveForm solver. Main features:
Accepts data in the form of operators with 5 productions;
Runs pigeonhole benchmarks in absolutely record time (6 sec for
hole10, 1900 sec for hole14 on Pentium Pro 180, 40 MB RAM);
May be used for the problems of the asynchronous design type,
planner applications etc.;
Can be adjusted for other types of problems.
5. Application areas:
Knowledge learning: Discovery af approximate logical functions
from a set of examples. This can be also used in design
verification of IC's.
Electronics design  one can suggest entirely new designs of IC's.
Planning, scheduling, resource allocation.
Graphcolouring type problems.
Any problem where local search is used: One writes down the
problem as a collection of positional operators and performs a
local search on this very compact representation.
An algorithm to solve nonlinear systems in GF(2) of arbitrary
degree was developed and will be implemented shortly. This opens
up a very broad application field.
Our research and development process provides us with valuable
insights into the interesting boundary between the P and
NPcomplete problems and we hope will clarify this central problem
of modern discrete mathematics.
***************************************************************************
END OF EMAIL QUOTATION
===========================================================================
© C.HAMANN http://public.BHTBerlin.de/hamann impressum 11/11/05
