http://moiidei.com/nauka-estestvennyie/prakticheskaya-minimizatsiya-bulevyih-funktsiy.
http://idshoohov.livejournal.com/155488.
http://obdamaskin.livejournal.com/87309.html
Практическая минимизация булевых функций.
Practical minimization of Boolean functions.
Представление информации булевой формулой.
Submission of information through a Boolean formula.
Определения.
Definitions
Под минимизацией булевых функций понимается построение булевой
формулы, описывающей булеву функцию, с минимальным числом букв.
Under the minimization of Boolean functions is understood to build a
Boolean formula with a minimum number of letters describing the
Boolean function.
Буква, входящая в формулу, обозначает одну из двоичных переменных,
являющуюся аргументом булевой функции.
The letter, included in the formula, represents one of the binary
variables that are arguments of a Boolean function.
Пример формулы:
Formula example
((ym+i)(j+zy)+u)(ml+h+vw)+lvwz
В этой формуле 16 букв.
In this formula, 16 letters.
Функция задаётся таблицей истинности, т.е. таблицей, устанавливающей
связь между значением аргумента (входящей переменной) и значением
самой функции.
Напомню, что и входящие переменные, и сама функция могут принимать
только одно из двух значений - 0 и 1. В некоторых случаях значения
функции могут быть не определены.
Function is given truth table, i.e. table, which establishes the
connection between the value of the argument (input variables) and the
value of the function.Let me remind you that the incoming variables
and the function itself can only take one of two values - 0 and 1.
In some cases, the values of the function can not be determined.
Пример таблицы истинности для 6 пар переменных.
An example of the truth table for 6 pairs of variables.
Переменные попарно:
The variables in pairs:
{h,u}; {i,v}; {j,w}; {k,x}; {l,y}; {m,z}.
Таблица истинности
Truth table
1 2 3
номер значения переменных значение функции F для примеров
строки values of variables value of the function F for examples
line
number h u i v j w k x l y m z F(1) F(2) F(3) F(4) F(5) F(6)
0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1
1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0
2 1 0 1 0 1 0 1 0 0 1 1 0 1 1 1 0 0
3 1 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0 0
4 1 0 1 0 1 0 0 1 1 0 1 0 1 0
5 1 0 1 0 1 0 0 1 1 0 0 1 1 0
6 1 0 1 0 1 0 0 1 0 1 1 0 1 0
7 1 0 1 0 1 0 0 1 0 1 0 1 1 1
8 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 1
9 1 0 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0
10 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0
11 1 0 1 0 0 1 1 0 0 1 0 1 1 1 1 0
12 1 0 1 0 0 1 0 1 1 0 1 0 0 1
13 1 0 1 0 0 1 0 1 1 0 0 1 0 0
14 1 0 1 0 0 1 0 1 0 1 1 0 0 0
15 1 0 1 0 0 1 0 1 0 1 0 1 1 1
16 1 0 0 1 1 0 1 0 1 0 1 0 0 0 0 1 1
17 1 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0
18 1 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0
19 1 0 0 1 1 0 1 0 0 1 0 1 0 0 0 0 1
20 1 0 0 1 1 0 0 1 1 0 1 0 0 0
21 1 0 0 1 1 0 0 1 1 0 0 1 0 1
22 1 0 0 1 1 0 0 1 0 1 1 0 1 0
23 1 0 0 1 1 0 0 1 0 1 0 1 0 1
24 1 0 0 1 0 1 1 0 1 0 1 0 0 0 0 1 1
25 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 1
26 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 1
27 1 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0
28 1 0 0 1 0 1 0 1 1 0 1 0 0 0
29 1 0 0 1 0 1 0 1 1 0 0 1 1 0
30 1 0 0 1 0 1 0 1 0 1 1 0 0 1
31 1 0 0 1 0 1 0 1 0 1 0 1 0 1
32 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0
33 0 1 1 0 1 0 1 0 1 0 0 1 0 0 0 1
34 0 1 1 0 1 0 1 0 0 1 1 0 0 1 0 1
35 0 1 1 0 1 0 1 0 0 1 0 1 0 0 0 0
36 0 1 1 0 1 0 0 1 1 0 1 0 0
37 0 1 1 0 1 0 0 1 1 0 0 1 0
38 0 1 1 0 1 0 0 1 0 1 1 0 1
39 0 1 1 0 1 0 0 1 0 1 0 1 0
40 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1
41 0 1 1 0 0 1 1 0 1 0 0 1 0 0 0 1
42 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0
43 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1
44 0 1 1 0 0 1 0 1 1 0 1 0 0
45 0 1 1 0 0 1 0 1 1 0 0 1 0
46 0 1 1 0 0 1 0 1 0 1 1 0 0
47 0 1 1 0 0 1 0 1 0 1 0 1 1
48 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1
49 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0
50 0 1 0 1 1 0 1 0 0 1 1 0 0 0 0
51 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0
52 0 1 0 1 1 0 0 1 1 0 1 0 0
53 0 1 0 1 1 0 0 1 1 0 0 1 0
54 0 1 0 1 1 0 0 1 0 1 1 0 0
55 0 1 0 1 1 0 0 1 0 1 0 1 1
56 0 1 0 1 0 1 1 0 1 0 1 0 1 1 1
57 0 1 0 1 0 1 1 0 1 0 0 1 1 1 1
58 0 1 0 1 0 1 1 0 0 1 1 0 1 1 1
59 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1
60 0 1 0 1 0 1 0 1 1 0 1 0 1
61 0 1 0 1 0 1 0 1 1 0 0 1 1
62 0 1 0 1 0 1 0 1 0 1 1 0 1
63 0 1 0 1 0 1 0 1 0 1 0 1 1
Методика минимизации булевых функций
The method of minimization of Boolean functions
В принципе методика разработана для практически любого числа
переменных, но пока она всё ещё отрабатывается только для 6 пар
переменных или меньше. Программа работает достаточно медленно, так как
процедура построения требуемой булевой формулы предусматривает
перебор вариантов, а число вариантов определяется, в том числе, и
структурой искомой формулы. Чем сложнее формула, тем больше времени
требуется для её построения.
Исходной информацией для программы являются данные графы 3 таблицы
истинности, т.е. последовательность из 64 знаков 0, 1 или отсутствия
любого их этих знаков. Для удобства записи вместо пустого места в
последовательности будем писать букву "a", чтобы видны были границы
последовательности.
Например, для построения формулы булевой функции F(1) для 5 пар
переменных (исключена пара k,x) из графы 3 таблицы истинности нужно
ввести в программу последовательность
In principle, the technique developed for virtually any number of
variables, but so far it has worked only for 6 pairs of variables or
less. The program works very slowly, as the procedure for constructing
a Boolean formula provides options for sorting and duration determined
by the number of options, depending on the structure of the formula. A
more complicated formula takes longer to build.
The input to the program are the data column 3 of the truth table,
i.e. sequence of 64 digits 0, 1, or the absence of any of these signs.
For convenience, instead of an empty place in the sequence, we write
the letter "a", so we could see the boundaries of the sequence.
For example, to construct a formula of a Boolean function F (1) 5
pairs of variables (removed a couple of k, x) from column 3 of the
truth table must be entered in the program sequence
1111aaaa0001aaaa0010aaaa0100aaaa1000aaaa1000aaaa1000aaaa1111aaaa (1)
Через некоторое время программа выдаст формулу для данной последовательности, т.е.
After some time, the program will give a formula for the sequence, i.e.
F(1) = ((ym+i)(j+zy)+u)(ml+h+vw)+lvwz (16 букв в формуле) (16 letters in the formula)
Для F(2) (для тех же переменных) таблица истинности даёт несколько
иную последовательность
For F (2) (for the same variables) truth table gives a slightly different sequence
1111aaaa0001aaaa0010aaaa0100aaaa0010aaaa0001aaaa0001aaaa1111aaaa (2)
и, соответственно, программа другую формулу для F(2)
and, accordingly, the program gives another formula for F (2)
F(2) = (v(lz+u)w+(i+(m+u)y)(hj+y(z+ji)))(h+v+m+w) (19)
Функция F(3) определяется всеми 6-ю парами переменных.
Последовательность её значений из таблицы истинности не содержит
пустых мест и выглядит так
The function F (3) is defined by all 6 pairs of variables. The
sequence of its values from the truth table contains no empty seats
and looks like
1111111100010001001000100100010010000010100000011000000111111111 (3)
Формула для F(3), определённая с помощью программы,
The program has found the formula for F (3)
F(3) = (u+lz)vw+(j+zy+u)(klm+h)(i+ym+u)+yxu((v+w)z+ijm) (26)
Наконец, обратим внимание на ещё один пример функции F(4) всё тех же
5 пар переменных, отличающийся тем, что там в соответствующей графе
таблицы истинности отсутствуют значения функции не только в связи с
отсутствием пары переменных x и k, но и просто потому, что значения
этой функции по тем или иным причинам не определены. Например,
разработчику логической схемы абсолютно безразлично какое значение
будет у булевой функции при данном сочетании значений переменных. В
этом случае программа сама как бы выбирает такое значение функции для
пустого места, которое гарантирует минимальность формулы. В этом
заключается существенное различие между примерами для F(1), F(2) и
функцией F(4).
Finally, we turn our attention to another example of a function F (4)
of the same 5 pairs of variables, characterized in that there is a
truth table corresponding box missing values of not only the lack of
a pair of x and k, but simply because that the values of this
function for one reason or another are not determined. For example, a
developer logic is absolutely indifferent to what value will be a
Boolean function for a given combination of variables. In this case,
the program itself as it chooses a value function for an empty place,
which ensures minimal formula. This is a significant difference
between the models for F (1), F (2) and the function F (4).
Последовательность для F(4) будет выглядеть так
Sequence for F (4) would look like
1000aaaa000aaaaa1110aaaa1a1aaaaa0110aaaa11a1aaaa1aaaaaaaaaa1aaaa (4)
а сама формула, как
and the formula as
F(4) = (l+m)((j+z)u+v)+uw +ljhm (12)
Если в последовательности (1) все буквы a заменить на 0, то
последовательность будет выглядеть следующим образом
If all the letters a replaced by 0 in the sequence (1), the sequence
is as follows
1111000000010000001000000100000010000000100000001000000011110000 (1.1)
и соответствующая формула
and the corresponding formula
F(1.1) = k( ((ym+i)(j+zy)+u)(ml+h+vw)+lvwz ) (17)
Практически формула осталась та же, но появилась ещё одна буква k за
счёт фактического перехода от 5 пар переменных к 6 парам.
Замена же всех букв a на 0 в последовательности (4) приведёт к другой
формуле F(4.1) с определённо бОльшим числом букв в ней.
Almost formula remained the same, but there is another letter k for
the actual transition from 5 to 6 pairs of variables pairs.
Substitution of all the letters a to 0 in the sequence (4) leads to
another formula F (4.1) with a definitely a great number of letters in
it.
100000000000000111000001010000001100000110100001000000000010000 (4.1)
F(4.1) = k((m(hv+jl)+(zwy+i(l+jm))u)(v+w+h+y+z)+ljhv) (23)
Пример функции F(5) в таблице истинности тоже для 5 пар переменных,
но отсутствует пара {h,u}. В этом случае последовательность значений
функции выглядит так
Example of a function F (5) of the truth table for the same 5 pairs of
variables, but there is no pair {h, u}. In this case, the sequence of
the function looks like this
10000001100010011001010111100011aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa (5)
Для последовательности (5) программа даёт результат
For a sequence (5) the program gives the result
F(5) = (l(iw+k)m+(y+(j+k)v)(xz+v(w+zy)))(x+l+j+m) (19)
Небольшое заключение.
Finally, a small.
Таким образом, если надо получить формулу для некоторой булевой
функции, то просто присылайте последовательность значений функции из
таблицы истинности. Можно прислать и просто формулу для данной
функции, полученную каким то другим способом. Программа может и в
этом случае построить свой вариант формулы.
So, if you need to get a formula for some Boolean function, then just
send the sequence of the function of the truth table. You can send and
simple formula for this function, obtained some other way. The program
can also in this case to construct its own version of the formula.
