Òåõíè÷åñêèå íàóêè / 6.Ýëåêòðîòåõíèêà è ðàäèîýëåêòðîíèêà
Danilov V.V.
National Research Nuclear University MEPhI
Algorithm
for representing a random three-valued logic function in the basis of the
conjunction and the loop
Emil Leon Post
showed that the system functions of the conjunction and the loop is the basis
of any k-valued logic. Any three-valued logic function can be represented in
this basis. This work describes an algorithm developed by the author. It allows
representing a random three-valued logic function in the basis of ternary
functions: the conjunction and the loop.
Truth table of
the conjunction (^) and the loop (
) functions in the
three-valued asymmetric logic listed in Table 1.
Table 1
Truth table of the conjunction and the loop functions
|
a |
Conjunction |
Loop |
||
|
b |
|
|||
|
0 |
1 |
2 |
||
|
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
1 |
1 |
2 |
|
2 |
0 |
1 |
2 |
0 |
Algorithm for representing a random three-valued logic
function F in the basis of the
conjunction and the loop is performed in three stages:
In the
first stage introduced the concept of component functions (1), and the
original function F is represented by
these component functions (2).
(1)
Equation (1)
describes the component functions for a particular function F, which should represent in the basis
of the conjunction and the loop. The number of component functions equals the
number of different sets of input variables (3n, where n – number
of input variables of the function). Each component function only on a certain
set (a0, a1, …, an) has the value of F
on the same set, and equals two for
other values of input variables. It allows representing the function F as a conjunction of the all relevant
component functions (2).
(2)
All component functions
for sets in which F is 2, is a
function of "constant two" and so in the future they can be ignored. Consequently,
selected those input signals values sets on which the function takes the value
0 or 1 in the first stage of the representing of three-valued logic functions
in the basis of the conjunction and the loop. We construct the component
functions 
(in one set is 0, in other is 2) for the corresponding sets in which
F takes the value 0. And we construct
(on the one set is 1) for the sets in which F takes the value 1.
In the
second stage of the representing a random three-valued logic function F in the basis of the conjunction and
the loop introduced the concept of the characteristic function of the input
signal (3), and component functions are represented as a twice looped
conjunction of the characteristic functions (4), (5).
(3)
Equation (3)
describes the characteristic function of the input variable. This form allows representing
the component functions as a twice looped conjunction of the characteristic
functions of all input variables:
(4)
(5)
In the
third stage the characteristic functions are represented in the basis
of the conjunction and the cycle by the following formulas (6) - (11):
(6)
(7)
(8)
(9)
(10)
(11)
You can represent any random three-valued
logic function F in the basis of the
conjunction and the loop by using this algorithm.
References
1. G. Frieder and C. Luk.
Algorithms for binary coded balanced and ordinary ternary operations // IEEE
Trans. Comput. – 1975. – V. 24, Feb. – P. 212
2. Henning Gundersen, Yngvar
Berg. A Novel Ternary More, Less and Equality Circuit Using Recharged
Semi-Floating Gate Devices. – Oslo: Department of Informatics, Microelectronic
Systems Group, University of Oslo, 2006.
3. Yasushi Yuminaka, Kyohei
Kawano. A Ternary Partial-Response Signaling Scheme for Capacitively Coupled
Interface. 40th IEEE International Symposium on Multiple-Valued Logic, ISMVL
2010, Barcelona, Spain, 26-28 May 2010. IEEE Computer Society 2010, ISBN
978-0-7695-4024-5. p. 331-336