Тема 3.3. Функциональная полнота различных наборов элементарных логических функций
3.3.1. Полная совокупность элементарных логических функций
Под элементарными будем понимать логические функции (ЛФ) одного и двух аргументов.
При 2-х аргументах возможны 4 различных конкретных реализации любой функции, которые можно интерпретировать как единое 4-разрядное двоичное число. Следовательно, всего существует N = 24 = 16 различных двухэлементных ЛФ (таблица 3.7).
Таблица 3.7. Логические функции двух переменных
Окончание таблицы 3.7.
3.3.2. Абсолютная полнота наборов элементарных логических функций
Для того чтобы подбирать логические функции в функционально полные наборы (ФПН) с использованием принципа необходимости и достаточности, необходимо предварительно изучить их свойства.
В математической логике все элементарные функции подразделяют по своим свойствам на линейные, сохраняющие «0», сохраняющие «1», самодвойственные и монотонные.
1. ЛФ называется линейной, если ее можно представить полиномом первой степени вида
,
где ai= {0, 1}, i = 0, 1, 2, ..., n.
Существует только 8 линейных функций от 2-х переменных – f0,f3, f5, f6, f9, f10, f12, f15, что нетрудно видеть из таблицы 3.8:
Таблица 3.8. Линейные функции двух переменных
|
a2 |
a1 |
a0 |
Линейная функция 2-х аргументов
| |
|
0 |
0 |
0 |
|
const=0 |
|
0 |
0 |
1 |
|
const=1 |
|
0 |
1 |
0 |
|
повторение x1 |
|
0 |
1 |
1 |
|
отрицание x1 |
|
1 |
0 |
0 |
|
повторение x2 |
|
1 |
0 |
1 |
|
отрицание x2 |
|
1 |
1 |
0 |
|
неравнозначность |
|
1 |
1 |
1 |
|
эквивалентность |
2. Сохраняющие 0 функции n переменных
ЛФ называется сохраняющей 0, если на нулевом наборе аргументов (х1 = 0, х2 = 0, …, хn= 0) функция равна 0, т.е. f (0, 0, ..., 0) = 0.
Сохраняющими 0 являются первые 8 функций таблицы 3.7, т.е. функции f0 - f7.
3. Сохраняющие 1 функции n переменных
ЛФ называется сохраняющей 1, если на единичном наборе аргументов (х1 = 1, х2 =1, …, хn= 1) функция равна 1, т.е. f (1, 1, ..., 1) = 1.
К этой группе относятся нечетные функции: f1, f3, f5, f7, f9, f11, f13, f15.
4. Самодвойственные функции
ЛФ
называется самодвойственной,
если на каждой паре противоположных
наборов аргументов вида [x1],
[x2],
..., [xn]
и 
она принимает противоположные значения,
т.е.
.
В таблице 3.7 есть только две пары противоположных наборов аргументов:
0.0 и 1.1; 0.1 и 1.0.
Функций, удовлетворяющих условиям:
всего 4 – это f3, f5, f10, f12.
5. Монотонные функции
ЛФ называется монотонной, если при возрастании набора аргументов значения этой функции не убывают.
Таких функций в таблице 3.7 всего 6 – f0, f1, f3, f5, f7, f15.
Проверку на монотонность для каждой ЛФ в таблице можно проводить по двум путям:
f (0.0) ⇒f (0.1) ⇒f (1.1)
или
f (0.0) ⇒f (1.0) ⇒f (1.1).
Можно показать, что при суперпозиции любых функций (или линейных, или сохраняющих 0, или сохраняющих 1, или самодвойственных, или монотонных) получаются такие же функции. Следовательно, для того чтобы набор ЛФ был ФПН, необходимо и достаточно, чтобы в него входили:
– хотя бы одна нелинейная функция;
– хотя бы одна не сохраняющая 0;
– хотя бы одна не сохраняющая 1;
– хотя бы одна не самодвойственная;
– хотя бы одна немонотонная.
Это теорема была доказана В.М. Глушковым.
Пользуясь этой теоремой, можно четко и однозначно указать, какие совокупности ЛФ двух переменных составят ФПН (таблица 3.9)
Таблица 3.9. Таблица для выбора ФПН
