 |
Суперпозиция булевых функций
|
|
|
|
Функция f, получаемая из функций f1, f2,…fn с помощью операций подстановки и переименования аргументов, называется суперпозицией функций.
Всякая формула, выражающая функцию f как суперпозицию других функций, задаёт способ её вычисления, т. е. формулу можно вычислить, если вычислены значения всех её подформул. Значение подформулы можно вычислить по известному набору значений двоичных переменных.
По каждой формуле можно восстановить таблицу логической функции, но не наоборот, т.к. каждой логической функции можно представить несколько формул в различных базисах
Формулы Fi и Fj представляющие одну и ту же логическую функцию fi, называются эквивалентными. Так, эквивалентными формулами являются:
1. f2(x1; x2)=(x1×`x2)=ù(`x1Úx2)= ù(x1®x2);
2. f6(x1; x2)=(`x1×x2Úx1×`x2)= ù(x1«x2)=(x1Åx2);
3. f8(x1; x2)=(`x1×`x2)= ù(x1Úx2)=(x1¯x2);
4. f14(x1;x2)=(`x1Ú`x2)= ù(x1×x2)=x1½x2;
5. f9(x1;x2)=((`x1×`x2)Ú(x1×x2))=(x1«x2);
6. f13(x1;x2)=(`x1Úx2)=(x1®x2).
Если какая-либо формула F содержит подформулу Fi, то замена Fi на эквивалентную Fj не изменяет значения формулы F при любом наборе булевого вектора, но изменяет форму её описания. Вновь полученная формула F` эквивалентна формуле F.
Для упрощения сложных алгебраических выражений булевой функции выполняют эквивалентные преобразования, используя законы булевой алгебры и правила подстановки и замещения,
При написании формул булевой алгебры следует помнить:
· число левых скобок равно числу правых скобок,
· нет двух рядом стоящих логических связок, т. е. между ними должна быть формула,
· нет двух рядом стоящих формул, т. е. между ними должна быть логическая связка,
· логическая связка “×” сильнее логической связки “Ú”,
|
|
|
· если “ù ” относится к формуле (F1×F2) или (F1Ú F2), то прежде всего следует выполнить эти преобразования по закону де Моргана: ù(F1×F2)=`F1Ú`F2 или ù(F1ÚF2)=`F1×`F2;
· операция “ × ” сильнее “Ú”, что позволяет опускать скобки.
Пример: выполнить эквивалентные преобразования формулы F=x1×x2×x3×`x4Ú`x1×x3Ú`x2×x3Úx3×x4.
· по закону коммутативности:
F=x3×x1×x2×`x4Úx3×`x1Úx3×`x2Úx3×x4;
· по закону дистрибутивности:
F=x3×x1×x2×`x4Úx3×`x1Úx3×(`x2Úx4);
· по закону дистрибутивности:
F=x3×x1×x2×`x4Úx3×(`x1Ú`x2Úx4);
· по закону дистрибутивности:
F=x3×((x1×x2×`x4)Ú(`x1Ú`x2Úx4));
· по закону де Моргана:
F=x3×((x1×x2×`x4)Úù(x1×x2×`x4));
· по закону противоречия:
F=x3×1=x3.
Таким образом x1×x2×x3×`x4Ú`x1×x3Ú`x2×x3Úx3×x4=x3.
Пример: выполнить преобразования формулы
F=(x1×`x2Ú`x1×x2)×ù(x1×x2)Ú(x1×x2)×ù(x1×`x2Ú`x1×x2);
· по закону де Моргана
F=(x1×`x2Ú`x1×x2)×(`x1Ú`x2)Ú(x1×x2)×(`x1Úx2)×(x1Ú`x2);
· по закону дистрибутивности:
F=x1×`x2Ú`x1×x2Úx1×x2;
· по законам коммутативности и дистрибутивности:
F= `x1×x2Úx1×(`x2Úx2);
· по закону противоречия:
F= `x1×x2Úx1;
· по закону Порецкого
F= x1Úx2.
Таким образом (x1×`x2Ú`x1×x2)×ù(x1×x2)Ú(x1×x2)×ù(x1×`x2Ú`x1×x2)= (x2Úx1).
Пример: выполнить преобразование формулы F=ù(`x1Úx2)Ú((`x1Úx3)×x2).
· по закону де Моргана:
F= ù(`x1Úx2)×ù((`x1Úx3)×x2);
· по закону де Моргана:
F=x1×`x2×(ù(`x1Úx3)Ú`x2);
· по закону де Моргана:
F=x1×`x2×(x1×`x3Ú`x2);
· по закону дистрибутивности:
F=x1×`x2×`x3Úx1×`x2;
· по закону поглощения:
F=x1×`x2.
Таким образом ù(`x1Úx2)×((`x1Úx3)×x2)= x1×`x2.
Пример: выполнить преобразование формулы:
F=ù(x1®x2)×(`x3Ú`x4)Ú(x1¯x2)×ù(x3×x4).
|
|
|
1) преобразовать формулу в базис булевой алгебры:
F=ù(`x1Úx2)×(`x3Ú`x4)Úù(x1Úx2)× ù(x3×x4);
2) опустить знак “` “ до двоичных переменных:
F=(x1×`x2)×(`x3Ú`x4)Ú(`x1×`x2)×(`x3Ú`x4);
3) преобразовать формулу по закону дистрибутивности:
F=x1×`x2×`x3Úx1×`x2×`x4Ú`x1×`x2×`x3Ú`x1×`x2×`x4;
4) вынести за скобку `x2 по закону дистрибутивности:
F=`x2×(x1×`x3Úx1×`x4Ú`x1×`x3Ú`x1×`x4);
5) преобразовать по закону дистрибутивности:
F=`x2×(`x3×(x1Ú`x1)Ú`x4×(x1Ú`x1));
6) использовать закон противоречия:
F=`x2×(`x3Ú`x4)
Свойства булевых функций
Часто возникает вопрос: всякая ли булева функция представима суперпозицией формул f0, f1,..f15? Для того, чтобы определить возможность формирования любой булевой функции с помощью суперпозиции этих формул, необходимо определить их свойства и условия использования функционально полной системы.
Самодвойственные булевы функции
Функция f(x1; x2;…xn) называется самодвойственной, если f(x1;x2;…xn)=`f(`x1;`x2;…`xn).
Например, функции f3(x1;x2)=x1, f5(x1;x2)=x2, f10(x1;x2)=`x2 и f12(x1;x2)=`x1 являются самодвойственными, т. к. при изменении значения аргумента они изменяют свое значение.
Любая функция, полученная с помощью операций суперпозиции из самодвойственных булевых функций, сама является самодвойственной. Поэтому множество самодвойственных булевых функций не позволяет формировать не самодвойственные функции.
Монотонные булевы функции
Функция f(x1; x2;…xn) называется монотонной, если для каждого s1i£s2i булевых векторов (s11; s12;……;s1n) и (s21;s22;……;s2n) выполняется условие: f(s11;s12;…;s1i;…;s1n)£f(s21;s22;…;s2i;…;s2n).
Например, для функций f(x1; x2) монотонными функциями являются:
если (0; 0)£(0; 1), то f(0; 0)£f(0; 1),
если (0; 0)£(1; 0), то f(0; 0)£f(1; 0),
если (0; 1)£(1; 1), то f(0; 1)£f(1; 1),
если (1; 0)£(1; 1), то f(1; 0)£f(1; 1).
Таким условиям удовлетворяют следующие функции:
f0(x1; x2)=0; f1(x1; x2)=(x1×x2); f3(x1; x2)=x1; f5(x1; x2)=x2; f7(x1;x2)=(x1Úx2); f15(x1; x2)=1.
Любая функция, полученная с помощью операции суперпозиции из монотонных булевых функций, сама является монотонной. Поэтому множество монотонных функций не позволяет формировать не монотонные функции.
Линейные булевы функции
Алгебра Жегалкина, опирающаяся на базис F4={×; Å; 1}, позволяет любую логическую функцию представить полиномом, каждый член которого есть конъюнкция I булевых переменных булевого вектора в пределах 0£i£n:
|
|
|
P(x1; x2;…xn)=b0×1 Å bi×xi Å1£j¹k£n bj×xj×xk Å……Å b2n-1×x1×x2×...×xn.
Например, для логических функций f8(x1; x2)
полином Жегалкина имеет вид: P(x1; x2)=1Å x1Å x2Å x1×x2.
Преимущества алгебры Жегалкина состоят в “арифметизации” логических формул, а недостатки - в сложности, особенно при большом числе двоичных переменных.
Полиномы Жегалкина, не содержащие конъюнкции двоичных переменных, т.е. P(x1; x2;…;xn)=b0×1Åb1×x1Å…Åbn×xn называют линейными.
Например, f9(x1; x2)=1Åx1Åx2, или f12(x1;x2)=1Åx1.
Основные свойства операции сложения по модулю 2 приведены в таблице 1.18.
Если логическая функция задана таблицей или формулой в любом базисе, т.е. известны значения булевой функции для различных наборов булевых переменных, то можно вычислить все
коэффициенты bi полинома Жегалкина, составив систему уравнений по всем известным наборам двоичных переменных.
| таблица 1.18 | |
| Наименование закона | Эквивалентные формулы |
| коммутативности | x1 Å x2=x2 Å x1 |
| ассоциативности | x1Å (x2 Å x3)=(x1Å x2) Å x3; |
| дистрибутивности | x1×(x2 Å x3)=x1×x2 Å x1×x3; |
| свойство “1” | xÅ 1=`x; |
| свойство “0” | xÅ 0=x; |
| сложение по модулю 2 | xÅ x=0; xÅ`x=1. |
Пример: дана булева функция f(x1;x2)=x1Úx2. Значение этой функции известны для всех наборов булевых переменных.
f(0;0)=0=b0×1Å b1×0 Å b2×0 Å b3×0×0;
f(0;1)=1=b0×1Å b1×0 Å b2×1Å b3×0×1;
f(1;0)=1=b0×1Å b1×1Å b2×0Å b3×1×0;
f(1;1)=1=b0×1Å b1×1Å b2×1Å b3×1×1;
Откуда находим b0=0; b1=1; b2=1; b3=1.
Следовательно, (x1Úx2)=x1Åx2Åx1×x2, т. е. дизъюнкция есть нелинейная булева функция.
Пример: дана булева функция f(x1;x2)=(x1®x2). Значение этой функции также известны для всех наборов двоичных переменных.
f(0;0)=1=b0×1Å b1×0 Å b2×0 Å b3×0×0;
f(0;1)=1=b0×1Å b1×0 Å b2×1Å b3×0×1;
f(1;0)=0=b0×1Åb1×1Åb2×0Åb3×1×0;
|
|
|
f(1;1)=1=b0×1Åb1×1Åb2×1Åb3×1×1;
Откуда находим b0=1; b1=1; b2=0; b3=1.
Следовательно, (x1®x2)=1Å x2 Å x1×x2.
В таблице 1.19 приведены полиномы Жегалкина для основных представителей булевых функций из таблицы 1.15.
| таблица 1.19 | |
| fi | эквивалентные формулы |
| f7 | (x1Úx2)=x1Å x2Å x1×x2; |
| f8 | (x1¯x2)=ù(x1Úx2)=1Å x1Å x2Å x1×x2; |
| f9 | (x1«x2)=(`x1×`x2Úx1×x2)=1Å x1Å x2; |
| f12 | `x1=1Å x1; |
| f13 | (x1¯x2)=(`x1Úx2)=1Å x1Å x2Å x1×x2; |
| f14 | (x1½x2)=ù(x1×x2)=1Å x1×x2. |
Если дано аналитическое выражение логической функции и неизвестны ее значения для различных наборов двоичных переменных, то можно построить полином Жегалкина, опираясь на конъюнктивный базис алгебры Буля F2={`; ×}:
Пусть f(x1; x2)=(x1Úx2).
Тогда (x1Úx2)=ù(`x1×`x2)=((x1Å 1)×(x2Å 1))Å 1=x1×x2Å x1×1Å x2×1Å 1×1Å1=
(x1Åx2Åx1×x2).
Пусть f(x1;x2)=(x1 ®x2).
Тогда (x1 ®x2)=(`x1Úx2)=ù(x1×`x2)=x1×(x2Å 1)Å 1=x1×x2Å x1×1Å 1= =(1Åx1Åx1×x2).
Пусть f(x1;x2)=(x1 «x2).
Тогда (x1«x2)=(`x1×`x2Úx1×x2)=ù(ù(`x1×`x2)×ù(x1×x2))=(((x1Å1)×(x2Å1))Å1)× ×(x1×x2Å)Å1=(x1×x2Åx1Åx2Å1Å1)×(x1×x2Å1)Å1=x1×x2Åx1×x2Åx1×x2Åx1Å
x1×x2Åx2Å1=(1Åx1Åx2).
Любая функция, полученная с помощью операции суперпозиции из линейных логических функций, сама является линейной. Поэтому множество линейных функций не позволяет формировать нелинейные функции.
1.5.6.4. Функции, сохраняющие “0”
Функция f(x1; x2;...xn) называется сохраняющей “0”, если для наборов значений двоичных переменных (0; 0;...0) функция принимает значение f(0; 0;…0)=0.
Например, f0(0; 0)=0, f3(0; 0)=0, f7(0; 0)=0 и др.
Любая функция, полученная с помощью операции суперпозиции из функций, сохраняющих “0”, сама является функцией, сохраняющей “0” Поэтому множество функций, сохраняющих “0”, не позволяет формировать функции, не сохраняющие “0”.
1.5.6.5. Функции, сохраняющие “1”
Функция f(x1; x2;…xn) называется сохраняющей “1”, если для наборов значений двоичных переменных (1; 1;…1) функция принимает значение f(1;1;…1)=1.
Например, f1(1; 1)=1, f3(1; 1)=1, f5(1; 1)=1 и др.
Любая функция, полученная с помощью операции суперпозиции из функций, сохраняющих “1”, сама является сохраняющей “1”. Поэтому множество функций, сохраняющих “1”, не позволяет формировать функции, не сохраняющие “1”.
|
|
|
