Построение графиков онлайн. Смотреть страницы где упоминается термин суперпозиция функций Функции, сохраняющие “1”
Пусть имеется некоторый набор K , состоящий из конечного числа булевых функций. Суперпозицией функций из этого набора называются новые функции, полученные с помощью конечного числа применения двух операций;
можно переименовать любую переменную, входящую в функцию из K ;
вместо любой переменной можно поставить функцию из набора K или уже образованную ранее суперпозицию.
Суперпозицию еще иначе называют сложной функцией.
Пример 7. 1. Если дана одна функция х |y (штрих Шеффера), то ее суперпозициями, в частности, будут следующие функции x|x , x| (x|y ), x| (y|z ) и т. д.
Замыканием набора функций из K называется множество всех суперпозиций. Класс функций K называется замкнутым , если его замыкание совпадает с ним самим.
Набор функций называется полным , если его замыкание совпадает со всеми логическими функциями. Иначе говоря, полный набор - это множество таких функций, через которые можно выразить все остальные булевы функции.
Неизбыточный полный набор функций называется базисом (“неизбыточный” означает, что если какую-то функцию удалить из набора, то этот набор перестанет быть полным).
Пример 7.2. Конъюнкция, дизъюнкция и отрицание являются полным набором (в этом убедились в разд. 5), но не являются базисом, так как это набор избыточен, поскольку с помощью правил де Моргана можно удалить конъюнкцию или дизъюнкцию. Любую функцию можно представить в виде полинома Жегалкина (разд. 6). Ясно, что функции конъюнкция, сложение по модулю 2 и константы 0 и 1 являются полным набором, но эти четыре функции также не являются базисом, поскольку 1+1=0, и поэтому константу 0 можно исключить из полного набора (для построения полиномов Жегалкина константа 0 необходима, поскольку выражение “1+1” не является полиномом Жегалкина).
Легко видеть, что одним из способов проверки полноты какого-то набора К является проверка того, что через функции из этого набора выражаются функции другого полного набора (можно проверить, что через функции из К можно выразить конъюнкцию и отрицание или дизъюнкцию и отрицание.
Существуют такие функции, что одна такая функция сама является базисом (здесь достаточно проверить только полноту, неизбыточность очевидна). Такие функции называются шефферовскими функциями. Это название связано с тем, что штрих Шеффера является базисом. Напомним, что штрих Шеффера определяется следующей таблицей истинности:
Так как очевидно , т. е. отрицание является суперпозицией штриха Шеффера, а дизъюнкция тогда 
, штрих Шеффера сам является базисом. Аналогично, стрелка Пирса является шефферовской функцией (студенты могут проверить это сами). Для функций 3-х или более переменных шефферовских функций очень много (конечно, выражение других булевых функций через шефферовскую функцию большого числа переменных сложно, поэтому в технике они редко используются).
Заметим, что вычислительное устройство чаще всего базируется на полном наборе функций (часто на базисах). Если в основе устройства лежат конъюнкция, дизъюнкция и отрицание, то для этих устройств важна проблема минимизации ДНФ; если в основе устройства лежат другие функции, то полезно уметь алгоритмически минимизировать выражения через эти функции.
Перейдем теперь к выяснению полноты конкретных наборов функций. Для этого перечислим 5 важнейших классов функций:
- Т 0 - это набор всех тех логических функций, которые на нулевом наборе принимают значение 0 (Т 0 - это класс функций, сохраняющих 0);
- Т 1 - это набор всех логических функций, которые на единичном наборе принимают значение 1 (Т 1 - это класс функций, сохраняющих единицу ) (заметим, что число функций от п переменных принадлежащих классам Т 0 и Т 1 равно 2 2n-1);
- L - класс линейных функций т. е. функций, для которых полином Жегалкина содержит только первые степени переменных;
- М - класс монотонных функций. Опишем класс этих функций более подробно. Пусть имеются 2 набора из п переменных: s1 = (x 1 , x 2 ,..., x n)
s 1 = (х 1 , х 2 , … , х п ) и s 2 = (y 1 , y 2, … , y п) . Будем говорить, что набор s 1 меньше набора s 2 (s 1 £ s 2 ), если все х i £ y i . Очевидно, что не все наборы из п переменных сравнимы между собой (например, при п = 2 наборы (0,1) и (1,0) не сравнимы между собой). Функция от п переменных называется монотонной , если на меньшем наборе она принимает меньшее или равное значение. Разумеется, эти неравенства должны проверяться только на сравнимых наборах. Понятно, что несравнимые наборы - это те, в которых есть некоторые координаты типа (0,1) в одном наборе и (1,0) в другом на соответствующих местах (в дискретной математике монотонные функции это только как бы “монотонно возрастающие функции”, “монотонно убывающие” функции здесь не рассматриваются).
Пример. В нижеследующей таблице функции f 1 , f 2 являются монотонными функциями, а функции f 3 , f 4 - нет.
Естественный порядок переменных обеспечивает тот факт, что если какой-то набор меньше другого набора, то он обязательно расположен в таблице истинности выше “большего” набора. Поэтому если в таблице истинности () вверху стоят нули , а затем единицы , то эта функция точно является монотонной . Однако возможны инверсии, т. е. единица стоит до каких-то нулей , но функция является все равно монотонной (в этом случае наборы, соответствующие “верхней” единице и “нижнему” нулю должны быть несравнимы ; можно проверить, что функция, задаваемая таблицей истинности при естественном порядке набора переменных (00010101), является монотонной);
Теорема . Классы функций Т 0 , Т 1 , L , M , S замкнуты .
Это утверждение следует непосредственно из определения самих этих классов, а также из определения замкнутости.
В теории булевых функций очень большое значение имеет следующая теорема Поста.
Теорема Поста . Для того чтобы некоторый набор функций K был полным, необходимо и достаточно, чтобы в него входили функции, не принадлежащие каждому из классов T 0 , T 1 , L , M , S .
Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора К входили в один из перечисленных классов, то и все суперпозиции, а значит, и замыкание набора входило бы в этот класс и класс К не мог быть полным.
Достаточность этого утверждения доказывается довольно сложно, поэтому здесь не приводится.
Из этой теоремы следует довольно простой способ выяснения полноты некоторого набора функций. Для каждой из этих функций выясняется принадлежность к перечисленным выше классам. Результаты заносятся в так называемую таблицу Поста (в нашем примере эта таблица составлена для 4-х функций, причем знаком “+” отмечается принадлежность функции соответствующему классу, знак “-” означает, что функция в него не входит).
В соответствии с теоремой Поста набор функций будет полным тогда и только тогда, когда в каждом столбце таблицы Поста имеется хотя бы один минус. Таким образом, из приведенной таблицы следует, что данные 4 функции образуют полный набор, но эти функции не являются базисом. Из этих функций можно образовать 2 базиса: f 3 , f 1 и f 3 , f 2 . Полными наборами будут любые наборы содержащие, какой-либо базис.
Непосредственно из таблицы Поста следует, что число базисных функций не может быть больше 5. Нетрудно доказать, что на самом деле это число меньше или равно 4.
Соответствием G между множествами А и В называется подмножество . Если , то говорят, что b
соответствует а. Множество всех соответствующих элементу
Называется образом элемента а. Множество всех которым соответствует элемент , называется
прообразом элемента b .
Множество пар (Ь, а) таких, что называется обратным по
отношению к G и обозначается . Понятия образа и прообраза для
" G и взаимно обратны.
Примеры. 1) Поставим в соответствие натуральному числу п
множество действительных чисел 
. Образом числа 5
будет полуинтервал
(так обозначают наибольшее целое, меньшее или равное X ). Прообразом числа 5 при этом соответствии является бесконечное множество: полуинтервал . Получение [М ]по исходному множеству М называется операцией замыкания . Множество М называется функционально замкнутым классом , если [М ] = М . Подмножество m Í M называется функционально полной системой в М , если [m ] = М .
Замыкание [М ]представляет собой все множество функций, которое можно получить из М путем применения операции суперпозиции, т.е. всех возможных подстановок.
Замечания. 1. Очевидно, любая система функций {f } является функционально полной в себе самой.
2 . Без ограничения общности можно считать, что тождественная функция f (х )=х , не изменяющая значений истинности переменных, изначально входит в состав любой системы функций.
Пример 2 . Для рассмотренных ниже систем функций {f } выполнить следующие действия:
1) найти замыкание [f ],
2) выяснить, будет ли система {f } замкнутым классом,
3) найти функционально полные системы в {f }.
Решение .
I. {f }={0}. При подстановке функции {fº 0} в саму себя получаем ее же, т.е. никаких новых функций не образуется. Отсюда следует: [f ] = {f }. Рассмотренная система является функционально замкнутым классом. Функционально полная система в ней одна и равна всей {f }.
II. {f }= {0,Ø }. Подстановка Ø (Ø х )дает тождественную функцию, которая формально не расширяет исходную систему. Однако при подстановке Ø (0) получим тождественную единицу - новую функцию, которой не было в исходной системе: Ø (0)=1. Применение всех других подстановок не приводит к появлению новых функций, например: ØØ 0= 0, 0(Ø х )=0.
Таким образом, применение операции суперпозиции позволило получить более широкое по сравнению с исходным множество функций [f ]={0,Ø ,1}. Отсюда следует строгое вхождение: {f } Ì [f ]. Исходная система {f }не является функционально замкнутым классом. Кроме самой системы {f }других функционально полных систем в ней нет, поскольку в случае её сужения из одной функции f= 0 нельзя путем подстановки получить отрицание, а из одной функции отрицания нельзя получить тождественный нуль.
III. {f } = {& ,Ú ,Ø }.Замыканием данной системы является все множество функций алгебры логики P 2 , так как формулу любой из них можно представить в виде ДНФ либо КНФ, в которых используются элементарные функции {f } = {& ,Ú ,Ø}. Данный факт является конструктивным доказательством полноты рассмотренной системы функций в P 2: [f ] =P 2 .
Поскольку в P 2 содержится бесконечное множество других функций, отличных от {f } = {& ,Ú ,Ø }, то отсюда следует строгое вхождение: {f }Ì[f ]. Рассмотренная система не является функционально замкнутым классом.
Помимо самой системы функционально полными в ней будут подсистемы {f } 1 = {& ,Ø } и {f } 2 = {Ú ,Ø }. Это следует из того, что при помощи правил де Моргана функцию логического сложения Úможно выразить через {& ,Ø},а функцию логического умножения & - через {Ú, Ø}:
(х & у ) = Ø (`х Ú`у ), (х Ú у ) = Ø (х &`у ).
Других функционально полных подсистем в {f } нет.
Проверку полноты подсистемы функций {f } 1 Ì {f }во всей системе {f }можно производить путем сведения {f } 1 к другой, заведомо полной в {f }системе.
Неполноту подсистемы {f } 1 в {f }можно проверить, доказав строгое вхождение [f 1 ] Ì [f ].
Определение. Подмножество m Í M называют функциональным базисом (базисом ) системы М , если [m ] = М , а после исключения из нее любой функции множество оставшихся не полно в М .
Замечание . Базисами системы функций {f} являются все ее функционально полные подсистемы {f} 1 , которые невозможно уменьшить без потери полноты в {f} .
Пример 3 . Для всех систем, рассмотренных в Примере 2, найти базисы.
Решение .В случаях 1 и 2 функционально полными являются только сами системы и сузить их невозможно. Следовательно, они же являются и базисами.
В случае 3 есть две функционально полные в {f }подсистемы {f } 1 = {&,Ø } и {f } 2 ={Ú,Ø }, которые невозможно сократить без потери полноты. Они будут базисами системы {f } = {&,Ú,Ø}.
Определение. Пусть система {f }является замкнутым классом. Ее подмножество {f } 1 Ì {f }называют предполным классом в {f }, если {f } 1 не полно в {f } ([f 1 ] Ì [f ]), а для любой функции jиз системы{f }, не входящей в {f } 1 (jÎ{f } \ {f } 1) справедливо: [j È {f } 1 ] = [f ], т.е. прибавление jк {f } 1 делает ее полной в {f }.
Задачи
1. Проверить замкнутость множеств функций:
а) {Ø }; б) {1, Ø }; в) {(0111); (10)};г) {(11101110); (0110)};д) {(0001); (00000001); (0000000000000001); … }.
2. Проверить полноту систем функций в P 2:
а) {0,Ø }; б) {(0101) , (1010) }; в) {¯ }; г) {(0001) , (1010) }.
3. Найти замыкание системы функций и ее базис:
а) {0 , 1 , Ø }; б) {(1000) , (1010), (0101) }; в) {(0001) , (1110), (10) }; г) {(1010) , (0001), (0111) }.
1.10.2 Функции, сохраняющие константы. Классы Т 0 и Т 1
Определение. Функция f (`х n ) сохраняет 0, если f (0,..., 0) = 0. Функция f (`х n ) сохраняет 1, если f (1, ... , 1) = 1.
Множества функций n переменных, сохраняющих 0 и 1, обозначают, соответственно, Т 0 n и Т 1 n . Все множества функций алгебры логики, сохраняющих 0 и 1, обозначают Т 0 и Т 1 . Каждое из множеств Т 0 и Т 1 является замкнутым предполным классом в Р 2 .
Из элементарных функций в Т 0 и Т 1 одновременно входят, например, &и Ú. Принадлежность любой функции к классам Т 0 , Т 1 можно проверить по первому и последнему значению ее вектора значений в таблице истинности либо непосредственной подстановкой нулей и единиц в формулу при аналитическом задании функции.
Определение. Дублирующей называют такую подстановку, при которой вместо нескольких независимых переменных в функцию подставляют одну и ту же переменную. При этом величины переменных в наборах, которые раньше принимали значения независимо друг от друга, всегда будут одинаковыми.
ЗАДАЧИ
1.Проверить принадлежность к классам Т 0 и Т 1 функций:
а) обощенного сложения, б) обощенного умножения, в) констант, г) ху Ú yz , д) х ® у ® ху , е) х Å у , ж)( х 1 Å… Å х n) ® ( y 1 Å… Å y m) при n,m Î N.
2. Доказать замкнутость каждого из классов Т 0 и Т 1 .
3. Доказать, что если f (`х n ) ÏТ 0 , то из нее путем дублирующей подстановки можно получить константу 1 либо отрицание.
4. Доказать, что если f (`х n ) ÏТ 1 , то из нее путем дублирующей подстановки можно получить константу 0 либо отрицание.
5. Доказать предполноту каждого из классов Т 0 и Т 1 (например, сведением дополненной системы к {f } = {& ,Ú ,Ø }).
6. Найти мощность классов Т 0 n и Т 1 n .
Функция f, получаемая из функций f 1 , f 2 ,…f n с помощью операций подстановки и переименования аргументов, называется суперпозицией функций.
Всякая формула, выражающая функцию f как суперпозицию других функций, задаёт способ её вычисления, т. е. формулу можно вычислить, если вычислены значения всех её подформул. Значение подформулы можно вычислить по известному набору значений двоичных переменных.
По каждой формуле можно восстановить таблицу логической функции, но не наоборот, т.к. каждой логической функции можно представить несколько формул в различных базисах
Формулы F i и F j представляющие одну и ту же логическую функцию f i, называются эквивалентными . Так, эквивалентными формулами являются:
1. f 2 (x 1 ; x 2)=(x 1 ×`x 2)=ù(`x 1 Úx 2)= ù(x 1 ®x 2);
2. f 6 (x 1 ; x 2)=(`x 1 ×x 2 Úx 1 ×`x 2)= ù(x 1 «x 2)=(x 1 Åx 2);
3. f 8 (x 1 ; x 2)=(`x 1 ×`x 2)= ù(x 1 Úx 2)=(x 1 ¯x 2);
4. f 14 (x 1 ;x 2)=(`x 1 Ú`x 2)= ù(x 1 ×x 2)=x 1 ½x 2 ;
5. f 9 (x 1 ;x 2)=((`x 1 ×`x 2)Ú(x 1 ×x 2))=(x 1 «x 2) ;
6. f 13 (x 1 ;x 2)= (`x 1 Úx 2)=(x 1 ®x 2).
Если какая-либо формула F содержит подформулу F i , то замена F i на эквивалентную F j не изменяет значения формулы F при любом наборе булевого вектора, но изменяет форму её описания. Вновь полученная формула F` эквивалентна формуле F.
Для упрощения сложных алгебраических выражений булевой функции выполняют эквивалентные преобразования , используя законы булевой алгебры и правила подстановки и замещения ,
При написании формул булевой алгебры следует помнить:
· число левых скобок равно числу правых скобок,
· нет двух рядом стоящих логических связок, т. е. между ними должна быть формула,
· нет двух рядом стоящих формул, т. е. между ними должна быть логическая связка,
· логическая связка “×” сильнее логической связки “Ú”,
· если “ù ” относится к формуле (F 1 ×F 2) или (F 1 Ú F 2), то прежде всего следует выполнить эти преобразования по закону де Моргана: ù(F 1 ×F 2)=`F 1 Ú`F 2 или ù(F 1 ÚF 2)=`F 1 ×`F 2 ;
· операция “× ” сильнее “Ú”, что позволяет опускать скобки.
Пример : выполнить эквивалентные преобразования формулы F=x 1 ×x 2 ×x 3 ×`x 4 Ú`x 1 ×x 3 Ú`x 2 ×x 3 Úx 3 ×x 4 .
· по закону коммутативности:
F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×`x 1 Úx 3 ×`x 2 Úx 3 ×x 4 ;
· по закону дистрибутивности:
F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×`x 1 Úx 3 ×(`x 2 Úx 4);
· по закону дистрибутивности:
F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×(`x 1 Ú`x 2 Úx 4);
· по закону дистрибутивности:
F=x 3 ×((x 1 ×x 2 ×`x 4)Ú(`x 1 Ú`x 2 Úx 4));
· по закону де Моргана:
F=x 3 ×((x 1 ×x 2 ×`x 4)Úù(x 1 ×x 2 ×`x 4));
· по закону противоречия:
Таким образом x 1 ×x 2 ×x 3 ×`x 4 Ú`x 1 ×x 3 Ú`x 2 ×x 3 Úx 3 ×x 4 =x 3 .
Пример: выполнить преобразования формулы
F=(x 1 ×`x 2 Ú`x 1 ×x 2)×ù(x 1 ×x 2)Ú(x 1 ×x 2)×ù(x 1 ×`x 2 Ú`x 1 ×x 2);
· по закону де Моргана
F=(x 1 ×`x 2 Ú`x 1 ×x 2)×(`x 1 Ú`x 2)Ú(x 1 ×x 2)×(`x 1 Úx 2)×(x 1 Ú`x 2);
· по закону дистрибутивности:
F=x 1 ×`x 2 Ú`x 1 ×x 2 Úx 1 ×x 2 ;
· по законам коммутативности и дистрибутивности:
F= `x 1 ×x 2 Úx 1 ×(`x 2 Úx 2);
· по закону противоречия:
F= `x 1 ×x 2 Úx 1 ;
· по закону Порецкого
Таким образом (x 1 ×`x 2 Ú`x 1 ×x 2)×ù(x 1 ×x 2)Ú(x 1 ×x 2)×ù(x 1 ×`x 2 Ú`x 1 ×x 2)= (x 2 Úx 1).
Пример: выполнить преобразование формулы F=ù(`x 1 Úx 2)Ú((`x 1 Úx 3)×x 2).
· по закону де Моргана:
F= ù(`x 1 Úx 2)×ù((`x 1 Úx 3)×x 2);
· по закону де Моргана:
F=x 1 ×`x 2 ×(ù(`x 1 Úx 3)Ú`x 2);
· по закону де Моргана:
F=x 1 ×`x 2 ×(x 1 ×`x 3 Ú`x 2);
· по закону дистрибутивности:
F=x 1 ×`x 2 ×`x 3 Úx 1 ×`x 2 ;
· по закону поглощения:
Таким образом ù(`x 1 Úx 2)×((`x 1 Úx 3)×x 2)= x 1 ×`x 2 .
Пример : выполнить преобразование формулы:
F=ù(x 1 ®x 2)×(`x 3 Ú`x 4)Ú(x 1 ¯x 2)×ù(x 3 ×x 4).
1) преобразовать формулу в базис булевой алгебры:
F=ù(`x 1 Úx 2)×(`x 3 Ú`x 4)Úù(x 1 Úx 2)× ù(x 3 ×x 4);
2) опустить знак “` “ до двоичных переменных:
F=(x 1 ×`x 2)×(`x 3 Ú`x 4)Ú(`x 1 ×`x 2)×(`x 3 Ú`x 4);
3) преобразовать формулу по закону дистрибутивности:
F=x 1 ×`x 2 ×`x 3 Úx 1 ×`x 2 ×`x 4 Ú`x 1 ×`x 2 ×`x 3 Ú`x 1 ×`x 2 ×`x 4 ;
4) вынести за скобку `x 2 по закону дистрибутивности:
F=`x 2 ×(x 1 ×`x 3 Úx 1 ×`x 4 Ú`x 1 ×`x 3 Ú`x 1 ×`x 4);
5) преобразовать по закону дистрибутивности:
F=`x 2 ×(`x 3 ×(x 1 Ú`x 1)Ú`x 4 ×(x 1 Ú`x 1));
6) использовать закон противоречия:
F=`x 2 ×(`x 3 Ú`x 4)
Свойства булевых функций
Часто возникает вопрос: всякая ли булева функция представима суперпозицией формул f 0 , f 1 ,..f 15 ? Для того, чтобы определить возможность формирования любой булевой функции с помощью суперпозиции этих формул, необходимо определить их свойства и условия использования функционально полной системы.
Самодвойственные булевы функции
самодвойственной , если f(x 1 ;x 2 ;…x n)=`f(`x 1 ;`x 2 ;…`x n).
Например, функции f 3 (x 1 ;x 2)=x 1 , f 5 (x 1 ;x 2)=x 2 , f 10 (x 1 ;x 2)=`x 2 и f 12 (x 1 ;x 2)=`x 1 являются самодвойственными, т. к. при изменении значения аргумента они изменяют свое значение.
Любая функция, полученная с помощью операций суперпозиции из самодвойственных булевых функций, сама является самодвойственной. Поэтому множество самодвойственных булевых функций не позволяет формировать не самодвойственные функции.
Монотонные булевы функции
Функция f(x 1 ; x 2 ;…x n) называется монотонной , если для каждого s 1i £s 2i булевых векторов (s 11 ; s 12 ;……;s 1n) и (s 21 ;s 22 ;……;s 2n) выполняется условие: f(s 11 ;s 12 ;…;s 1i ;…;s 1n)£f(s 21 ;s 22 ;…;s 2i ;…;s 2n).
Например, для функций f(x 1 ; x 2) монотонными функциями являются:
если (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).
Таким условиям удовлетворяют следующие функции:
f 0 (x 1 ; x 2)=0; f 1 (x 1 ; x 2)=(x 1 ×x 2); f 3 (x 1 ; x 2)=x 1 ; f 5 (x 1 ; x 2)=x 2 ; f 7 (x 1 ;x 2)=(x 1 Úx 2); f 15 (x 1 ; x 2)=1.
Любая функция, полученная с помощью операции суперпозиции из монотонных булевых функций, сама является монотонной. Поэтому множество монотонных функций не позволяет формировать не монотонные функции.
Линейные булевы функции
Алгебра Жегалкина, опирающаяся на базис F 4 ={×; Å; 1}, позволяет любую логическую функцию представить полиномом, каждый член которого есть конъюнкция I булевых переменных булевого вектора в пределах 0£i£n:
P(x 1 ; x 2 ;…x n)=b 0 ×1 Å b i ×x i Å 1 £ j ¹ k £ n b j ×x j ×x k Å……Å b 2n-1 ×x 1 ×x 2 ×...×x n.
Например, для логических функций f 8 (x 1 ; x 2)
полином Жегалкина имеет вид: P(x 1 ; x 2)=1Å x 1 Å x 2 Å x 1 ×x 2 .
Преимущества алгебры Жегалкина состоят в “арифметизации” логических формул, а недостатки - в сложности, особенно при большом числе двоичных переменных.
Полиномы Жегалкина, не содержащие конъюнкции двоичных переменных, т.е. P(x 1 ; x 2 ;…;x n)=b 0 ×1Åb 1 ×x 1 Å…Åb n ×x n называют линейными .
Например, f 9 (x 1 ; x 2)=1Åx 1 Åx 2 , или f 12 (x 1 ;x 2)=1Åx 1 .
Основные свойства операции сложения по модулю 2 приведены в таблице 1.18.
Если логическая функция задана таблицей или формулой в любом базисе, т.е. известны значения булевой функции для различных наборов булевых переменных, то можно вычислить все
коэффициенты b i полинома Жегалкина, составив систему уравнений по всем известным наборам двоичных переменных.
Пример : дана булева функция f(x 1 ;x 2)=x 1 Úx 2 . Значение этой функции известны для всех наборов булевых переменных.
F(0;0)=0=b 0 ×1Å b 1 ×0 Å b 2 ×0 Å b 3 ×0×0;
f(1;0)=1=b 0 ×1Å b 1 ×1Å b 2 ×0Å b 3 ×1×0;
f(1;1)=1=b 0 ×1Å b 1 ×1Å b 2 ×1Å b 3 ×1×1;
Откуда находим b 0 =0; b 1 =1; b 2 =1; b 3 =1.
Следовательно, (x 1 Úx 2)=x 1 Åx 2 Åx 1 ×x 2 , т. е. дизъюнкция есть нелинейная булева функция.
Пример : дана булева функция f(x 1 ;x 2)=(x 1 ®x 2). Значение этой функции также известны для всех наборов двоичных переменных.
F(0;0)=1=b 0 ×1Å b 1 ×0 Å b 2 ×0 Å b 3 ×0×0;
f(0;1)=1=b 0 ×1Å b 1 ×0 Å b 2 ×1Å b 3 ×0×1;
f(1;0)=0=b 0 ×1Åb 1 ×1Åb 2 ×0Åb 3 ×1×0;
f(1;1)=1=b 0 ×1Åb 1 ×1Åb 2 ×1Åb 3 ×1×1;
Откуда находим b 0 =1; b 1 =1; b 2 =0; b 3 =1.
Следовательно, (x 1 ®x 2)=1Å x 2 Å x 1 ×x 2 .
В таблице 1.19 приведены полиномы Жегалкина для основных представителей булевых функций из таблицы 1.15.
Если дано аналитическое выражение логической функции и неизвестны ее значения для различных наборов двоичных переменных, то можно построить полином Жегалкина, опираясь на конъюнктивный базис алгебры Буля F 2 ={` ; ×}:
Пусть f(x 1 ; x 2)=(x 1 Úx 2).
Тогда (x 1 Úx 2)=ù(`x 1 ×`x 2)=((x 1 Å 1)×(x 2 Å 1))Å 1=x 1 ×x 2 Å x 1 ×1Å x 2 ×1Å 1×1Å1=
(x 1 Åx 2 Åx 1 ×x 2).
Пусть f(x 1 ;x 2)=(x 1 ®x 2).
Тогда (x 1 ®x 2)=(`x 1 Úx 2)=ù(x 1 ×`x 2)=x 1 ×(x 2 Å 1)Å 1=x 1 ×x 2 Å x 1 ×1Å 1= =(1Åx 1 Åx 1 ×x 2).
Пусть f(x 1 ;x 2)=(x 1 «x 2).
Тогда (x 1 «x 2)=(`x 1 ×`x 2 Úx 1 ×x 2)=ù(ù(`x 1 ×`x 2)×ù(x 1 ×x 2))=(((x 1 Å1)×(x 2 Å1))Å1)× ×(x 1 ×x 2 Å)Å1=(x 1 ×x 2 Åx 1 Åx 2 Å1Å1)×(x 1 ×x 2 Å1)Å1=x 1 ×x 2 Åx 1 ×x 2 Åx 1 ×x 2 Åx 1 Å
x 1 ×x 2 Åx 2 Å1=(1Åx 1 Åx 2).
Любая функция, полученная с помощью операции суперпозиции из линейных логических функций, сама является линейной. Поэтому множество линейных функций не позволяет формировать нелинейные функции.
1.5.6.4. Функции, сохраняющие “0”
Функция f(x 1 ; x 2 ;...x n) называется сохраняющей “0”, если для наборов значений двоичных переменных (0; 0;...0) функция принимает значение f(0; 0;…0)=0.
Например, f 0 (0; 0)=0, f 3 (0; 0)=0, f 7 (0; 0)=0 и др.
Любая функция, полученная с помощью операции суперпозиции из функций, сохраняющих “0”, сама является функцией, сохраняющей “0” Поэтому множество функций, сохраняющих “0”, не позволяет формировать функции, не сохраняющие “0”.
1.5.6.5. Функции, сохраняющие “1”
Функция f(x 1 ; x 2 ;…x n) называется сохраняющей “1”, если для наборов значений двоичных переменных (1; 1;…1) функция принимает значение f(1;1;…1)=1.
Например, f 1 (1; 1)=1, f3(1; 1)=1, f 5 (1; 1)=1 и др.
Любая функция, полученная с помощью операции суперпозиции из функций, сохраняющих “1”, сама является сохраняющей “1”. Поэтому множество функций, сохраняющих “1”, не позволяет формировать функции, не сохраняющие “1”.
