 |
Функционально полные системы
|
|
|
|
Свойства булевых функций (самодвойственности, монотонности, линейности, сохранения “1” и “0”) представлены в таблице 1.20. Знаком “1” обозначены функции, обладающие одним из перечисленных свойств.
| таблица 1.20 | ||||||||||||||||||||||||||
| (x1; x2) | y=f(x1; x2) | |||||||||||||||||||||||||
| x1 | x2 | f0 | f1 | f2 | f3 | f4 | f5 | f6 | f7 | f8 | f9 | f10 | f11 | f12 | f13 | f14 | f15 | |||||||||
| с в о й с т в а ф у н к ц и й | ||||||||||||||||||||||||||
| сохр. “0” | ||||||||||||||||||||||||||
| сохр. “1” | ||||||||||||||||||||||||||
| само- двойств. | ||||||||||||||||||||||||||
| моно- тонная | ||||||||||||||||||||||||||
| линей- ная | ||||||||||||||||||||||||||
Опираясь на свойства булевых функций можно определить ф ункционально полную систему как совокупность таких функций fi, fj,¼fk, что произвольная булева функция f может быть записана с помощью их суперпозиции. Для этого среди множества функций fi, fj,¼fk должна быть по крайней мере одна функция, не сохраняющая “1”, одна функция, не сохраняющая “0”, одна функция не самодвойственная, одна функция немонотонная и одна нелинейная функция.
Анализ таблицы показывает, что таких {fi,fj,…fk} может быть несколько. Набор логических связок функционально полной системы порождает базис алгебраической системы Fi. Ниже даны основные базисы.
|
|
|
1. F0={×; Ú;`; Å;«; ®; ½; ¯} - сигнатура алгебры логики;
2. F1={×; Ú;` } - базис алгебры Буля;
3. F2={×;` } - базис конъюнктивный Буля;
4. F3={Ú;` } - базис дизъюнктивный Буля;
5. F4={×; Å; 1} - базис алгебры Жегалкина;
6. F5={¯} - базис Вебба;
7. F6={½} - базис Шеффера;
8. F7={®;` } - базис импликативный и т.д.
В таблицах приведены некоторые формулы в различных базисах.
| таблица 1.21 | таблица 1.22 | |||
| fi | Формулы в базисах F0 и F2 | fi | Формулы в базисах F0 и F3 | |
| f6 | (x1Åx2)=ù(`x1×`x2)×ù(x1×x2) | f6 | (x1×x2)=ù(`x1Ú`x2) | |
| f7 | (x1Úx2)=ù(`x1×`x2) | f7 | (x1Åx2)=ù(`x1Úx2)Úù(x1Ú`x2) | |
| f8 | (x1¯x2)=(`x1×`x2) | f8 | (x1¯x2)=ù(x1Úx2) | |
| f9 | (x1«x2)=ù(x1×`x2)×ù(`x1×x2) | f9 | (x1«x2)=(x1Úx2)Úù(`x1Ú`x2) | |
| f13 | (x1®x2)=ù(x1×`x2) | f13 | (x1®x2)=(`x1Úx2) | |
| f14 | (x1÷x2)=ù(x1×x2) | f14 | (x1½x2)=(`x1Ú`x2) | |
| таблица 1.23 | таблица 1.24 | |||
| fi | Формулы в базисах F0 и F5 | fi | Формулы в базисах F0 и F6 | |
| f1 | (x1×x2)=(x1¯x2)¯(x1¯x2) | f1 | (x1×x2)=(x1½x2)½(x1½x2) | |
| f6 | (x1Åx2)=[(x1¯x1)¯(x2¯x2)] ¯(x1¯x2) | f6 | (x1Åx2)=[x1½(x2½x2)]½[x2½ (x1½x1)] | |
| f7 | (x1Úx2)=(x1¯x2)¯(x1¯x2) | f7 | (x1Úx2)=(x1½x2)½(x1½x2) | |
| f9 | (x1«x2)=[x1¯(x2¯x2)]¯ [x2¯(x1¯x1)] | f8 | (x1¯x2)=[(x1½x1)½(x2½x2)½ (x2½x2)] | |
| f13 | (x1®x2)=[x2¯(x1¯x1)]¯ [x2¯(x1¯x1)] | f9 | (x1«x2)=[(x1½x1)½(x2½x2)]½ (x1½x2)] | |
| f14 | (x1÷x2)=[(x1¯x1)¯(x2¯x2)]¯ [(x1¯x1)¯(x2¯x2)] | f13 | (x1®x2)=(x1½(x2½x2). |
Разложение булевых функции
Пусть дан булевый вектор (x1; x2;...…xn), компоненты которого принимают значения siÎ{0; 1}. Тогда
Конъюнкция нескольких xisi в пределах заданного булевого вектора определяет формулу специального вида Kj=(x1s1×x2s2×…×xnsn), которую называют элементарной конъюнкцией.
|
|
|
Дизъюнкция элементарных конъюнкций по известным наборам значений булевого вектора есть разложение логической функции в дизъюнктивную нормальную форму (ДНФ).
Дизъюнкция xisi в пределах заданного булевого вектора определяет формулу специального вида D=(x1s1Úx2s2Ú…Úxnsn), которую называют элементарной дизъюнкцией.
Конъюнкция элементарных дизъюнкций по известным наборам значений булевого вектора есть разложение в конъюнктивную нормальную форму (КНФ).
ДНФ булевой функции
Всякая логическая функция f(x1; x2;...xn) может быть представлена в виде:
f(x1; x2;...xn)= Ú (x1s1×x2s2×…×xmsm)×f(s1; s2;¼sm; xm+1;…xn)),
где m£n, а дизъюнкция берётся по всем m наборам значений переменных (s1; s2;…sm).
Пусть m=1, тогда
f(x1; x2;…xn)=x1×f(1; x2;...xn)Ú`x1×f(0; x2;¼xn).
Пусть m=2, тогда
f(x1; x2;…xn)=x1×x2×f(1; 1;¼xn)Úx1×`x2×f(1; 0;…xn)Ú`x1×x2×f(0; 1;…xn)Ú `x1×`x2×f(0; 0;¼xn).
Пусть m=n, тогда
f(x1;x2;…xn)= Ú x1s1×x2s2×…×xnsn×f(s1; s2;...sn).
Чтобы элементарная конъюнкция (x1s1×x2s2×…×xnsn) представляла логическую функцию f(x1;x2;…;xn) необходимо иметь f(s1;s2;…sn)=1, т.е.
f(x1;x2;…xn)= Ú x1s1×x2s2×…×xnsn×1.
Если f(s1;s2;…sn)=0, то f(x1;x2;…xn)= Ú x1s1×x2s2×…×xn×0 = 0.
Функцию f(s1; s2;…sn)=1 называют конституентой единицы. Тогда любую булеву функцию, значение которой равно 1, представляет дизъюнкция элементарных конъюнкций булевых переменных булевого вектора.
Если элементарные конъюнкции в разложении имеют одинаковые число и имена булевых переменных, то разложение формирует совершенную дизъюнктивную нормальную форму формулы булевой функции (СДНФ).
Например, F=x1×x2×x3×x4Ú`x1×`x2×x3×x4Úx1×`x2×`x3×`x4 есть СДНФ.
Если логическая функция задана таблицей, то формулу СДНФ можно записать по значениям булевых переменных для булевой функции, имеющей значение “1”.
Например, для функции, заданной таблицей 1.25, имеем: F=x1×`x2×x3×`x4Úx1×x2×`x3×`x4
| таблица 1.25 | ||||
| булевый вектор | функция | |||
| x1 | x2 | x3 | x4 | y=f(x1; x2; x3; x4) |
| f(0;0;0;1)=0 | ||||
| f(1;0;1;0)=1 | ||||
| f(1;1;0;0)=1 | ||||
| f(0;1;1;0)=0 | ||||
| ... | ... | ... | ... | ... |
Алгоритм преобразования формулы к СДНФ:
Шаг 1: преобразовать формулу так, чтобы в ней были только операции дизъюнкции, конъюнкции и отрицания;
|
|
|
Шаг 2: преобразовать формулу так, чтобы операция отрицания была применима только к двоичным переменным;
Шаг 3: если в некоторую конъюнкцию не входит переменная xi, то дополнить её выражением (xi Ú`xi) и выполнить преобразования формулы по закону дистрибутивности:
F=x1s1×x2s2×…×xksk×(xiÚ`xi)=x1s1×x2s2×…×xksk×xi Úx1s1×x2s2×…×xksk×`xi;
Шаг 4: если в некоторую конъюнкцию не входит переменная xj, то повторить шаг 3, иначе - конец.
Пример: преобразовать формулу F=x1×x2Ú`x1×`x2×x3×x4 к виду СДНФ.
· F=x1×x2×(x3Ú`x3)Ú`x1×`x2×x3×x4;
· F=x1×x2×x3Úx1×x2×`x3Ú`x1×`x2×x3×x4;
· F=x1×x2×x3×(x4Ú`x4)Úx1×x2×`x3×(x4Ú`x4)Ú`x1×`x2×x3×x4;
· F=x1×x2×x3×x4Úx1×x2×x3×`x4Úx1×x2×`x3×x4Úx1×x2×`x3×`x4)Ú`x1×`x2×x3×x4.
КНФ булевой функции
Любую булеву функцию f(x1; x2;...xn) можно представить в следующем виде:
f(x1; x2;…xn)= & (x1`s1Úx2`s2Ú………Úxm`smÚf(s1;s2;.... sm;xm+1;……;xn)),
где m£n, а конъюнкция берётся по всем m наборам булевых переменных (s1;s2;...…;sm).
Пусть m=1, тогда
f(x1; x2;...xn)=(`x1Úf(1;x2;…xn))×(x1Úf(0;x2;...xn)).
Пусть m=2, тогда
f(x1; x2;...xn)=(`x1Ú`x2Úf(1; 1; x3;...xn))×(`x1Úx2Úf(1; 0; x3;...xn))×
(x1Ú`x2Úf(0; 1; x3;...xn))×(x1Úx2Úf(0; 0; x3;...xn)).
Пусть m=n, тогда
f(x1;x2;...xn)= & (x1`s1Úx2`s2Ú...…Úxn`snÚ f(s1;s2;…;sn)).
Чтобы дизъюнкция (x1`s1Úx2`s2Ú…Úxn`sn) могла представлять логическую функцию f(x1; x2;...xn) необходимо f(s1; s2;… sn)=0. В противном случае, когда f(s1; s2;…sn)=1, значение f(x1;x2;...xn)=1при любых значениях si.
Итак, разложение в конъюнктивную нормальную форму есть
f(x1; x2;…xn)= & (x1`s1Úx2`s2Ú…...Úxn`sn) для f(s1; s2;…sn)=0.
Функцию f(s1;s2;…;sn)=0 называют конституентой нуля. Любую булеву функцию, значение которой равно “0”, представляет конъюнкция элементарных дизъюнкций.
Если элементарные дизъюнкции в разложении имеют одинаковые число и имена булевых переменных, то разложение представляет совершенную конъюнктивную нормальную форму (СКНФ) формулы булевой функции.
Например, F=(x1Úx2Úx3Úx4)×(`x1Ú`x2Úx3Ú`x4)×(x1Ú`x2Ú`x3Ú`x4).
|
|
|
Если логическая функция задана таблицей, то формулу СКНФ можно записать по значениям булевых переменных для булевой функции, имеющей значение “0”.
Например, для функции, заданной таблицей1.26, имеем:
F=(x1Úx2Úx3Ú`x4)× (x1Ú`x2Ú`x3Úx4).
| таблица 1.26 | ||||
| булевый вектор | булева функция | |||
| x1 | x2 | x3 | x4 | |
| f(0;0;0;1)=0 | ||||
| f(1;0;1;0)=1 | ||||
| f(1;1;0;0)=1 | ||||
| f(0;1;1;0)=0 | ||||
| ... | ... | ... | ... | ... |
Алгоритм преобразования формулы к СКНФ:
Шаг 1: преобразовать формулу так, чтобы в ней были только операции дизъюнкции, конъюнкции и отрицания;
Шаг 2: преобразовать формулу так, чтобы операция отрицания была применима только к двоичным переменным;
Шаг 3: если в некоторую дизъюнкцию не входит переменная xi, то дополнить её выражение (xi ×`xi) и выполнить преобразование по закону дистрибутивности:
F= x1`s1Úx2`s2Ú……... Úxk`skÚ(xi ×`xi)=(x1`s1Úx2`s2Ú... …Úxk`skÚxi)× (x1`s1Úx2`s2Ú...…Úxk`skÚ`xi);
Шаг 4: если в некоторую дизъюнкцию не входит переменная xj, то повторить шаг 3, иначе конец.
Пример: преобразовать формулу F=(x1Úx2)×(`x1Ú`x2Úx3Úx4) к виду СКНФ.
· F=(x1Úx2Úx3×`x3)×(`x1Ú`x2Úx3Úx4);
· F=(x1Úx2Úx3)×(x1Úx2Ú`x3)×(`x1Ú`x2Úx3Úx4);
· F=(x1Úx2Úx3Úx4×`x4)×(x1Úx2Ú`x3Úx4×`x4)×(`x1Ú`x2Úx3Úx4);
· F=(x1Úx2Úx3Úx4)×(x1Úx2Úx3Ú`x4)×(x1Úx2Ú`x3Úx4)×(x1Úx2Ú`x3Ú`x4)× (`x1Ú`x2Úx3Úx4).
|
|
|
