Автор Тема: Лекция 12. Специальные классы булевых функций  (Прочитано 541 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 12. Специальные классы булевых функций


В настоящей лекции рассмотрим булевы функции, обладающие некоторые важными свойствами: свойством сохранять нуль или единицу, самодвойственностью, линейностью и монотонностью. Следуя традиции, множества булевых функций, обладающих эти свойствами, мы будем называть классами. Важность указанных выше свойств станет ясна в следующей лекции, посвящённой полным системам булевых функций.

***

Пусть \(  \large f(x_1,x_2, \ldots, x_n)  \) - некоторая булева функция.
 
Определение 12.1. Говорят, что булева функция \(  \large f  \) сохраняет нуль, если \(  \large f(0,0, \ldots, 0)=0  \).

Замечание 12.1. Булева функция сохраняет нуль, если её значение на наборе значений переменных, состоящем из нулей, равно нулю.

Замечание 12.2. Класс булевых функций, сохраняющих нуль, обозначается через \(  \large P_0  \).

Замечание 12.3. Булева функция не сохраняет нуль, если \(  \large f(0,0, \ldots, 0 ) =1  \).

Задача 12.1. Найти все элементарные булевы функции, которые сохраняют нуль.

Решение. Ясно, что тождественный нуль сохраняет нуль, а тождественная единица его не сохраняет. Переходим к отрицанию. Оно не сохраняет нуль, так как

\(  \large 0'=1  \).


Конъюнкция и дизъюнкция сохраняют нуль, поскольку

\(  \large 0 \cdot 0=0  \), \(  \large 0 \vee 0=0  \).


Импликация и эквиваленция нуль не сохраняют, так как

\(  \large 0 \to 0=1  \), \(  \large 0 \leftrightarrow 0=1  \).


Сумма Жегалкина сохраняет нуль:

\(  \large 0 \oplus 0=0  \).


Наконец, штрих Шеффера и стрелка Пирса не относятся к классу функций, сохраняющих нуль, так как

\(  \large 0 \mid 0=1  \), \(  \large 0 \downarrow 0=1  \).

Задача 12.2. Выяснить, сохраняет ли нуль булева функция:

\(  \large f(x,y,z)=((x \mid z) \downarrow y) \to (y \downarrow z')  \).

Решение. Пусть

\(  \large x=y=z=0  \).

Тогда, используя определения элементарных булевых функций, получим:

\(  \large f(0,0,0)=((0 \mid 0) \downarrow 0) \to (0 \downarrow 0')=(1 \downarrow 0) \to (0 \downarrow 1)=0 \to 0=1  \).

Значит, функция \(  \large f  \) не сохраняет нуль.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 12. Специальные классы булевых функций
« Ответ #1 : Декабрь 28, 2017, 03:03:51 pm »
Теорема 12.1. Если булева функция является композицией булевых функций, сохраняющих нуль, то она сохраняет нуль.

Доказательство. Пусть \(  \large f_1,f_2, \ldots, f_n  \) - булевы функции, которые зависят от \(  \large n-1 \) переменных и сохраняют нуль. Рассмотрим функцию

\(  \large f_n(f_1,f_2, \ldots, f_{n-1})  \).

Она представляет собой композицию сохраняющих нуль булевых функций. В силу определения булевой функции, сохраняющей нуль,

\(  \large f_1(0,0, \ldots, 0)=f_2(0,0, \ldots, 0)= \ldots = f_{n-1}(0,0, \ldots, 0)=0  \).

Значит,

\(  \large f_n( f_1(0,0, \ldots, 0),f_2(0,0, \ldots, 0), \ldots , f_{n-1}(0,0, \ldots, 0))=f_n(0,0, \ldots, 0)  \).

Но

\(  \large f_n(0,0, \ldots, 0)=0  \),

так как \(  \large f_n  \) сохраняет нуль. Следовательно, \(  \large f_n(f_1,f_2, \ldots, f_{n-1})  \) также сохраняет нуль. Теорема доказана.

Замечание 12.4. Теорема 12.1 даёт нам достаточное условие наличия свойства сохранять нуль. Известно, что из элементарных булевых функций нуль сохраняют лишь тождественный нуль, конъюнкция, дизъюнкция и сумма Жегалкина.  Значит, если булева функция есть композиция элементарных функций, сохраняющих нуль, то, используя теорему 12.1, сразу можно сделать вывод, что она сохраняет нуль.

Пример 12.1. Функции \(  \large (x \oplus y) \vee (xz)  \) и \(  \large ((x \vee z) \oplus y) \vee 0  \) сохраняют нуль, так как представляют собой композиции сохраняющих нуль булевых функций.

Теорема 12.2. Если функция не сохраняет нуль, то она не является композицией функций, сохраняющих нуль.

Доказательство сводится к применению закона контрапозиции к теореме 12.1. Теорема доказана.

Замечание 12.5. Высказывание, обратное теореме 12.1, ложно, поскольку существуют булевы функции, сохраняющие нуль и при этом являющиеся композициями функций, которые нуль не сохраняют. Примером такой функции является сумма Жегалкина, которая, как известно, сохраняет нуль, но является композицией эквиваленции и отрицания, которые нуль не сохраняют.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 12. Специальные классы булевых функций
« Ответ #2 : Декабрь 28, 2017, 04:40:50 pm »
Определение 12.2. Говорят, что булева функция \(  \large f  \) сохраняет единицу, если \(  \large f(1,1, \ldots, 1)=1  \).

Замечание 12.6. Булева функция сохраняет единицу, если её значение на наборе значений переменных, которое состоит из единиц, равно единице.

Замечание 12.7. Класс булевых функций, сохраняющих единицу, обозначается через \(  \large P_1  \).

Замечание 12.8. Булева функция не сохраняет единицу, если \(  \large f(1,1, \ldots, 1 ) =0  \).

Задача 12.3. Выяснить, какие элементарные булевы функции сохраняют единицу.

Решение. Очевидно, что тождественный нуль не сохраняет единицу, а тождественная единица - сохраняет. Отрицание не сохраняет единицу, так как

\(  \large 1'=0  \).

Конъюнкция и дизъюнкция, а также импликация и эквиваленция сохраняют единицу:

\(  \large 1 \cdot 1=1  \), \(  \large 1 \vee 1=1  \), \(  \large 1 \to 1=1  \), \(  \large 1 \leftrightarrow 1=1  \).


Функции Жегалкина, Шеффера и Пирса не сохраняют единицу, поскольку

\(  \large 1 \oplus 1=0  \), \(  \large 1 \mid 1= 0  \), \(  \large 1 \downarrow 1=0  \).

Задача 12.4. Выяснить, сохраняет ли единицу булева функция:

\(  \large f(x,y,z)=(z \downarrow y) \to ((x \mid y) \to z)  \).

Решение. Будем использовать определения элементарных булевых функций. Если

\(  \large x=y=z=1  \),

то

\(  \large f(1,1,1)=(1 \downarrow 1) \to ((1 \mid 1) \to 1)=0 \to (0 \to 1)=0 \to 1=1  \).

Следовательно, рассматриваемая функция алгебры логики сохраняет единицу.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 12. Специальные классы булевых функций
« Ответ #3 : Декабрь 28, 2017, 07:45:33 pm »
Теорема 12.3. Если булева функция есть композиция функций, которые сохраняют единицу, то она сохраняет единицу.

Доказательство настоящей теоремы полностью аналогично доказательству теоремы 12.1. Пусть \(  \large f_1,f_2, \ldots, f_n  \) - булевы функции, зависящие от \(  \large n-1 \) переменных и сохраняющие единицу. Рассмотрим функцию

\(  \large f_n(f_1,f_2, \ldots, f_{n-1})  \).

Она представляет собой композицию функций, которые сохраняют единицу. Значит, согласно определению булевой функции, сохраняющей единицу,

\(  \large f_1(1,1, \ldots, 0)=f_2(1,1, \ldots, 1)= \ldots = f_{n}(1,1, \ldots, 1)=1  \).

Тогда

\(  \large f_n( f_1(1,1, \ldots, 1),f_2(1,1, \ldots, 1), \ldots , f_{n-1}(1,1, \ldots, 1))=f_n(1,1, \ldots, 1)=1  \).

Следовательно, \(  \large f_n(f_1,f_2, \ldots, f_{n-1})  \) сохраняет единицу. Теорема доказана.

Замечание 12.9. Теперь мы знаем, в чём заключается достаточное условие наличия свойства сохранять единицу. Известно, что из элементарных функций алгебры логики единицу сохраняют лишь тождественная единица, конъюнкция, дизъюнкция, импликация и эквиваленция. Если функция алгебры логики представлена как композиция элементарных функций, сохраняющих единицу, то, учитывая теорему 12.3, можем сделать вывод о её принадлежности к классу сохраняющих единицу функций.

Пример 12.2. Функции \(  \large (x \to(y \leftrightarrow z)) \vee xy   \) и \(  \large (x \leftrightarrow 1) (x \to (xz))  \) сохраняют единицу, поскольку представляют собой композиции сохраняющих единицу элементарных булевых функций.

Теорема 12.4. Если булева функция не сохраняет единицу, то она не является композицией функций, которые сохраняют единицу.

Доказывается с помощью предыдущей теоремы и закона контрапозиции. Теорема доказана.

Замечание 12.10. Обратное теореме 12.2 высказывание теоремой не является, так как существуют функции алгебры логики, сохраняющие единицу и являющиеся при этом композициями функций, единицу не сохраняющих. Такой функцией, например, является эквиваленция (она является композицией суммы Жегалкина и отрицания).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 12. Специальные классы булевых функций
« Ответ #4 : Декабрь 29, 2017, 01:48:01 pm »
Определение 12.3. Булева функция \(  \large g(x_1,x_2, \ldots, x_n)  \) называется двойственной функции \(  \large f(x_1,x_2, \ldots, x_n)  \), если \(  \large (g(x_1,x_2, \ldots, x_n))'=f(x_1',x_2', \ldots, x_n')  \).

Замечание 12.11. Булева функция \(  \large g(x_1,x_2, \ldots, x_n)  \) называется двойственной функции \(  \large f(x_1,x_2, \ldots, x_n)  \), если отрицание \(  \large g  \) равно функции \(  \large f  \) после замены всех переменных их отрицаниями.

Замечание 12.12. Функция \(  \large g  \) не является двойственной функции \(  \large f  \), если \(  \large (g(x_1,x_2, \ldots, x_n))' \not =f(x_1',x_2', \ldots, x_n')  \).

Замечание 12.13. Если \(  \large g  \) двойственна \(  \large f  \), то верно и обратное. Будем использовать закон двойного отрицания. В самом деле, равенство

\(  \large (g(x_1,x_2, \ldots, x_n))'=f(x_1',x_2', \ldots, x_n')  \)

эквивалентно равенству

\(  \large g(x_1,x_2, \ldots, x_n)=(f(x_1',x_2', \ldots, x_n'))'  \),

которое, в свою очередь, эквивалентно равенству

\(  \large (f(x_1,x_2, \ldots, x_n))'=g(x_1',x_2', \ldots, x_n')  \).

Учитывая данный факт, в подобных случаях будем говорить, что функции \(  \large f  \) и \(  \large g  \) двойственны.

Задача 12.5. Доказать, что функция \(  \large f_1(x,y,z) =(x \vee y) \to (z \downarrow x) \) двойственна функции \(  \large f_2(x,y,z)=(x \mid x) \vee (y \downarrow z)  \).

Решение. Найдём отрицание функции \(  \large f_1  \):

\(  \large ((x \vee y) \to (z \downarrow x))'=((x \vee y)' \vee (z \vee x)')'=(x \vee y)(x \vee z)=x \vee yz  \).

Заменим в функции \(  \large f_2  \) все переменные их отрицаниями:

\(  \large (x' \mid x') \vee (y' \downarrow z')=(x' \cdot x')' \vee (y' \vee z')'=x \vee yz  \).

Итак, первая функция двойственна второй функции.

Задача 12.6. Найти функции, двойственные элементарным булевым функциям

Решение. Ясно, что тождественный нуль и тождественная единица двойственны самим себе, поскольку всегда принимают значение, равное нулю и единице соответственно. Для удобства введём следующие обозначения:

\(  \large f_1(x)=x'  \),

\(  \large f_2(x,y)=xy  \),

\(  \large f_3(x,y)=x \vee y  \),

\(  \large f_4(x,y)=x \to y  \),

\(  \large f_5(x,y)= x \leftrightarrow y  \),

\(  \large f_6(x,y)=x \oplus y  \),

\(  \large f_7(x,y)= x \mid y  \),

\(  \large f_8(x,y) = x \downarrow y  \).

Найдём \(  \large (f_1(x))'  \):

\(  \large (f_1(x))'=x''=x  \).

Легко понять, что

\(  \large  x=x''=f_1(x') \).

Значит, отрицание двойственно самому себе. Далее будем вычислять \(  \large (f(x,y))'  \) и искать такую функцию \(  \large g(x',y')  \), что \(  \large (f(x,y))'=g(x',y')  \). Имеем:

\(  \large (f_2(x,y))= (xy)'=x' \vee y' \),

\(  \large f_3(x',y')= x' \vee y'  \).

Следовательно, конъюнкция и дизъюнкция - двойственные функции.

Далее:

\(  \large (f_4(x,y))'=(x \to y)'=(x' \vee y)'=xy'  \).


Подберём двойственную функцию:

\(  \large g(x,y)=x'y  \).

Действительно,

\(  \large g(x',y')=x''y'=xy'  \).

Функция \(  \large g(x,y)  \) не является элементарной, однако её можно представить в виде суперпозиции элементарных функций:

\(  \large g(x,y)=x'y=(x \vee y')'=(y \to x)'  \).

Значит, импликация двойственна отрицанию обратной импликации. Переходим к эквиваленции:

\(  \large (f_5(x,y))'=(x \leftrightarrow y)'=x \oplus y \oplus 1 \oplus 1= x \oplus y  \),

\(  \large f_6(x',y')=x' \oplus y' = x \oplus 1 \oplus y \oplus 1= x \oplus y  \).

Следовательно, эквиваленция и сумма Жегалкина - двойственные функции.

Функция Шеффера двойственна стрелке Пирса, поскольку:

\(  \large (f_7(x,y))=(x \mid y)'=(xy)''=xy  \),

\(  \large f_8(x',y')=(x' \downarrow y')=(x' \vee y')'=xy  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 12. Специальные классы булевых функций
« Ответ #5 : Январь 05, 2018, 11:36:08 am »
Определение 12.4. Булева функция \(  \large f  \) называется самодвойственной, если \(  \large (f(x_1,x_2, \ldots, x_n))'=f(x_1',x_2', \ldots, x_n')  \).

Замечание 12.14. Булева функция \(  \large f  \) является самодвойственной, если двойственная ей функция, равна \(  \large f  \).

Замечание 12.15. Класс самодвойственных функций обозначается через \(  \large S  \).

Замечание 12.16. Среди элементарных булевых функций, самодвойственны только логические константы и отрицание. Это было показано при решении задачи 12.6.

Задача 12.7. Доказать, что булева функция самодвойственна, используя определение:

\(  \large f(x,y,z)=(x' \to (yz)) \to (y \downarrow z)  \).

Решение. Для удобства упростим булеву функцию. Выразим импликацию и стрелку Пирса через другие булевы функции:

\(  \large (x' \to (yz)) \to (y \downarrow z)=(x'' \vee yz)' \vee (y \vee z)'  \).

Используем закон двойного отрицания и второй закон де Моргана:

\(  \large (x'' \vee yz)' \vee (y \vee z)' =(x \vee yz)' \vee y'z'  \).

Снова прибегнем к помощи законов де Моргана:

\(  \large (x \vee yz)' \vee y'z'=(x'(y' \vee z')) \vee y'z'  \).

Раскроем скобки:

\(  \large (x'(y' \vee z')) \vee y'z'=x'y' \vee x'z' \vee y'z'  \).

Теперь найдём \(  \large (f(x,y,z))'  \) и \(  \large f(x',y',z')  \):

\(  \large (f(x,y,z))'=(x'y' \vee x'z' \vee y'z')=(x \vee y)(x \vee z)(y \vee z)  \),

\(  \large f(x',y',z')=xy \vee xz \vee yz  \).

Раскрыв скобки в первом случае и используя законы поглощения, получим, что функция является самодвойственной.

Теорема 12.5. Булева функция самодвойственна тогда и только тогда, когда представляющий её двоичный вектор антисимметричен относительно линии, делящей таблицу значений этой функции пополам.

Доказательство. Легко заметить, что таблица значений любой булевой функции устроена следующим образом. Наборы значений булевых переменных антисимметричны относительно середины таблицы. Поясним на примере булевой функции от трёх переменных. Например, в первых трёх клетках второй строки таблицы значений стоят числа \(  \large 0, \ 0 , \ 1  \), а в седьмой строке - \(  \large 1, \ 1, \ 0  \) (отрицания переменных второй строки). Пусть булева функция \(  \large f(x,y,z)   \) самодвойственна. Согласно определению, данной свойство имеет место тогда и только тогда, когда

\(  \large (f(x,y,z))'=f(x',y',z')  \),

что эквивалентно 

\(  \large f(x,y,z)=(f(x',y',z'))'  \).

Это имеет место, если и только если значение функции функции при

\(  \large x=a,y=b,z=c  \)


равно отрицанию значения функции при

\(  \large x=a',y=b',z=c'  \).

А это эквивалентно антисимметричности вектора значений булевой функции относительно середины таблицы значений. Теорема доказана.

Замечание 12.17. Доказанная выше теорема даёт признак (критерий) самодвойственности булевой функции.

Теорема 12.6. Булева функция не является самодвойственной, если и только если представляющий её двоичный вектор не является антисимметричным относительно линии, которая делит пополам таблицу значений этой функции.

Для доказательства достаточно применить закон противоположности к теореме 12.5. Теорема доказана.

Пример 12.3. Функция \(  \large f=(00010010)  \) не является самодвойственной, а функция \(  \large g=(11001100)  \) самодвойственна.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 12. Специальные классы булевых функций
« Ответ #6 : Январь 05, 2018, 12:06:38 pm »
Теорема 12.7. Если булева функция есть композиция самодвойственных функций, то она самодвойственна.

Доказательство. Пусть \(  \large f_1,f_2, \ldots, f_n  \) - самодвойственные булевы функции, зависящие от \(  \large n-1  \) переменных. Докажем, что функция \(  \large f_n(f_1,f_2, \ldots, f_{n-1})  \) самодвойственна. Требуется доказать, что

\(  \large   f_n(f_1(x_1,x_2, \ldots, x_{n-1}) ,f_2(x_1,x_2, \ldots, x_{n-1}), \ldots, f_{n-1}(x_1,x_2, \ldots, x_{n-1}))= \)

\(  \large = f_n'(f_1(x_1',x_2', \ldots, x_{n-1}') ,f_2(x_1',x_2', \ldots, x_{n-1}'), \ldots, f_{n-1}(x_1',x_2', \ldots, x_{n-1}')) \).

Поскольку функции \(  \large f_1,f_2, \ldots, f_{n-1}  \) являются самодвойственными, то

\(  \large f_i(x_1,x_2, \ldots, x_{n-1})=f_i'(x_1',x_2', \ldots,x_{n-1}'), \ i=1,2, \ldots, n-1  \).

Значит,

\(  \large f_n(f_1(x_1,x_2, \ldots, x_{n-1}) ,f_2(x_1,x_2, \ldots, x_{n-1}), \ldots, f_{n-1}(x_1,x_2, \ldots, x_{n-1}))=  \)

\(  \large =f_n(f_1'(x_1',x_2', \ldots, x_{n-1}') ,f_2'(x_1',x_2', \ldots, x_{n-1}'), \ldots, f_{n-1}'(x_1',x_2', \ldots, x_{n-1}'))  \).

Так как функция \(  \large f_n  \) тоже самодвойственна, то, учитывая закон двойного отрицания, получим:

\(  \large f_n(f_1'(x_1',x_2', \ldots, x_{n-1}') ,f_2'(x_1',x_2', \ldots, x_{n-1}'), \ldots, f_{n-1}'(x_1',x_2', \ldots, x_{n-1}')) =  \)

\(  \large =f_n'(f_1'(x_1,x_2, \ldots, x_{n-1}) ,f_2'(x_1,x_2, \ldots, x_{n-1}), \ldots, f_{n-1}'(x_1,x_2, \ldots, x_{n-1}))   \).

Снова используем самодвойственность функций \(  \large f_1,f_2, \ldots, f_{n-1}  \):

\(  \large f_n'(f_1'(x_1,x_2, \ldots, x_{n-1}) ,f_2'(x_1,x_2, \ldots, x_{n-1}), \ldots, f_{n-1}'(x_1,x_2, \ldots, x_{n-1}))=  \)

\(  \large =f_n'(f_1(x_1',x_2', \ldots, x_{n-1}') ,f_2(x_1',x_2', \ldots, x_{n-1}'), \ldots, f_{n-1}(x_1',x_2', \ldots, x_{n-1}'))  \),

что и требовалось. Теорема доказана.

Замечание 12.18. В доказанной только что теореме содержится достаточное условие самодвойственности булевой функции.

Пример 12.4. Функция \(  \large f(x)=x  \) (тождественная функция) является самодвойственной, поскольку её можно представить как композицию самодвойственных функций:

\(  \large x=x''  \).

Теорема 12.8. Если функция не является самодвойственной, то она не является композицией самодвойственных функций.

Доказывается с помощью теоремы 12.7 и закона контрапозиции.

Замечание 12.19. Обратное теореме 12.7 высказывание теоремой не является, так как, например, тождественную единицу, которая является самодвойственной функцией, можно представить как композицию несамодвойственных функций:

\(  \large 1=x \to x  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 12. Специальные классы булевых функций
« Ответ #7 : Январь 08, 2018, 02:08:20 pm »
Определение 12.5. Булева функция называется линейной, если в представляющем её полиноме Жегалкина нет слагаемых, имеющих степень выше первой.

Замечание 12.20. Полином Жегалкина линейной булевой функции имеет вид

\(  \large a_0  \oplus a_1x_1 \oplus \ldots \oplus a_n x_n   \).

Замечание 12.21. Функция не является линейной, если хотя бы одно слагаемое в её многочлене Жегалкина имеет степень выше первой.

Замечание 12.22. Класс линейных булевых функций обозначается через \(  \large L  \).

Замечание 12.23. Учитывая, что

\(  \large x \oplus x =0  \), \(  \large x \oplus 0 =x  \),

всякую линейную функцию можно представить как нелинейную, прибавив к ней пару одинаковых слагаемых любой степени. Например,

\(  \large x \oplus y= xy \oplus xy \oplus x \oplus y  \).

Однако не всякую нелинейную функцию можно представить как линейную.

Замечание 12.24. Среди элементарных функций алгебры логики линейными являются лишь константы (нуль можно представить как \(  \large 0=x \oplus x  \), а единицу - как \(  \large 1=x \oplus x \oplus 1  \)), отрицание, сумма Жегалкина и эквиваленция. Дизъюнкция, конъюнкция, импликация, а также функции Шеффера и Пирса не являются линейными.

Задача 12.8. Выяснить, является ли булева функция линейной:

\(  \large (x \downarrow y) \to ((y \mid z) \to x')  \).

Решение. Задача сводится к вычислению полинома Жегалкина. Используем полиномиальные представления стрелки Пирса, штриха Шеффера и отрицания:

\(  \large (x \downarrow y) \to ((y \mid z) \to x') =(xy \oplus x \oplus y \oplus 1) \to ((yz \oplus 1) \to (x \oplus 1))  \).

Теперь избавимся от внутренней импликации:

\(  \large (xy \oplus x \oplus y \oplus 1) \to ((yz \oplus 1) \to (x \oplus 1)) =(xy \oplus x \oplus y \oplus 1) \to (xyz \oplus x \oplus 1)  \).

Выразим оставшуюся импликацию через сумму Жегалкина и конъюнкцию:

\(  \large (xy \oplus x \oplus y \oplus 1) \to (xyz \oplus x \oplus 1) =1  \).

Итак, функция тождественно равна единице. Значит, она линейна.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 12. Специальные классы булевых функций
« Ответ #8 : Январь 08, 2018, 02:22:42 pm »
Теорема 12.9. Если булева функция является композицией линейных булевых функций, то она линейна.

Доказательство. Пусть, как и при доказательстве теорем 12.1 и 12.3, функции \(  \large f_1,f_2, \ldots, f_n  \) зависят от \(  \large n-1  \) переменных. И пусть все эти функции линейны. Значит, все они имеют полиномиальное представление степени не выше первой. Снова рассмотрим функцию

\(  \large f_n(f_1,f_2, \ldots, f_{n-1})  \).

Очевидно, что данная функция представляет собой сумму Жегалкина \(  \large n-1  \) линейных функций. Значит, она снова является линейной. Теорема доказана.

Замечание 12.25. Доказанная выше теорема даёт нам достаточное условие линейности. Если функция алгебры логики есть композиция элементарных функций, которые линейны, то этого достаточно для признания булевой функции линейной.

Пример 12.5. Функция \(  \large f(x,y,z)=((x \leftrightarrow y) \leftrightarrow z ) \oplus z \oplus 1 \) линейна, поскольку она является композицией линейных булевых функций - эквиваленции, суммы Жегалкина и тождественной единицы.

Теорема 12.10. Если булева функция не является линейной, то она не является композицией линейных булевых функций.

Применение закона контрапозиции к теореме 12.9 доказывает настоящую теорему.

Замечание 12.26. Высказывание, обратное теореме, ложно. Например, функция \(  \large x \oplus y  \) линейна, однако её можно представить как как композицию нелинейных функций. Пусть, например,

\(  \large f_1(x,y)= xy \oplus x  \),

\(  \large f_2(x,y)=xy \oplus x \oplus y   \),

\(  \large f_3(x,y)=xy  \).

Тогда

\(  \large f_1(f_2,f_3)=(xy \oplus x \oplus y)xy \oplus xy \oplus x \oplus y=x \oplus y  \).

Линейная функция \(  \large f_1(f_2,f_3)  \) является композицией нелинейных функций \(  \large f_1,f_2, f_3  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 12. Специальные классы булевых функций
« Ответ #9 : Январь 08, 2018, 02:23:34 pm »
Определение 12.6. Булева функция \(  \large f(x_1,x_2,...,x_n) \) называется монотонной, если для любых \(  \large \alpha_1, \alpha_2,...,\alpha_n, \beta_1, \beta_2,...,\beta_n \) из

\(  \large \alpha_1 \le \beta_1, \ \alpha_2 \le \beta_2, ... , \alpha_n \le \beta_n \)

следует

\(  \large f(\alpha_1, \alpha_2,...,\alpha_n) \le f( \beta_1, \beta_2 , ... , \beta_n) \).

Замечание 12.27. Булева функция не является монотонной, если найдутся такие \(  \large \alpha_1, \alpha_2,...,\alpha_n, \beta_1, \beta_2,...,\beta_n \), что

\(  \large \alpha_1 \le \beta_1, \ \alpha_2 \le \beta_2, ... , \alpha_n \le \beta_n \)

и

\(  \large  f(\alpha_1, \alpha_2,...,\alpha_n) > f( \beta_1, \beta_2 , ... , \beta_n)  \).

Замечание 12.28. Класс всех монотонных функций обозначается через \(  \large M \).

Задача 12.9. Найти все монотонные функции среди элементарных булевых функций.

Решение. Составим общую таблицу значений для всех элементарных булевых функций:

\(  \large \displaystyle \begin{array}{|c|c|}
\hline
x &  y & 0 & 1 & x' & xy & x \vee y & x \to y & x \leftrightarrow y & x \oplus y & x \mid y & x \downarrow y \\
\hline
0 &  0 &  0  & 1 & 1 & 0 & 0 & 1 & 1&0&1& 1\\
\hline
0 & 1 & 0  & 1 & 1 & 0 & 1&1&0&1&1&0\\
\hline
1 & 0 & 0 & 1  & 0  & 0&1&0&0&1&1&0\\
\hline
1 & 1 & 0  & 1 & 0 & 1&1&1&1&0&0&0\\
\hline
\end{array}  \)

Ясно, что нуль, единица, конъюнкция и дизъюнкция монотонны. Отрицание не монотонно, так как

\(  \large 0 \le 1, 1=f(0) < f(1)=0  \).

Импликация (как и эквиваленция) не монотонна, поскольку

\(  \large 0 \le 1, 0 \le 0, 1=f(0,0)> f(1,0)=0  \).

Функция Жегалкина (как и функция Шеффера) не монотонна:

\(  \large 1 \le 1, 0 \le 1, 1=f(1,0)>f(1,1)=0  \).

Наконец, функция Пирса не является монотонной, так как

\(  \large 0 \le 1, 0 \le 1,1=f(0,0) > f(1,1)=0  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 12. Специальные классы булевых функций
« Ответ #10 : Январь 16, 2018, 01:35:03 pm »
Теорема 12.11. Если булева функция является композицией монотонных булевых функций, то она монотонна.

Доказательство. Пусть \(  \large f_1,f_2, \ldots , f_n  \) - монотонные булевы функции от \(  \large n-1  \) переменных. Рассмотрим функцию \(  \large f_n(f_1, f_2, \ldots, f_{n-1})  \), которая является композицией функций \(  \large f_1,f_2, \ldots, f_n  \). Поскольку функции \(  \large f_1,f_2, \ldots, f_{n-1}  \) монотонны, то, какими бы ни были \(  \large \alpha_1,\alpha_2, \ldots, \alpha_{n-1}, \beta_1,\beta_2, \ldots, \beta_{n-1}  \), из

\(  \large \alpha_1 \le \beta_1, \ldots, \alpha_{n-1} \le \beta_{n-1}  \)

следует

\(  \large f_i(\alpha_1, \alpha_2, \ldots, \alpha_{n-1}) \le f_i(\beta_1, \beta_2, \ldots, \beta_{n-1})  \),

где \(  \large i=1,2, \ldots, n-1  \).

Так как функция \(  \large f_n  \) тоже монотонна, то для любых \(  \large \gamma_1,\gamma_2, \ldots, \gamma_{n-1}, \delta_1,\delta_2, \ldots, \delta_{n-1}  \), в том числе для

\(  \large \gamma_i=f_i(\alpha_1,\alpha_2, \ldots, \alpha_{n-1}), \delta_i= f_i(\beta_1,\beta_2, \ldots, \beta_{n-1}), i=1,2, \ldots, n-1  \),

из

\(  \large \gamma_1 \le \delta_1, \ldots, \gamma_{n-1} \le \delta_{n-1}  \)

следует

\(  \large f_n(\gamma_1, \gamma_2, \ldots, \gamma_{n-1}) \le f_i(\delta_1, \delta_2, \ldots, \delta_{n-1})  \).

Значит, функция \(  \large f_n(f_1, f_2, \ldots, f_{n-1})  \) монотонна. Теорема доказана.

Замечание 12.29. Достаточное условие монотонности - тот факт, что функция является композицией монотонных булевых функций.

Пример 12.6. Функция \(  \large x(y \vee z) (x \vee z) \vee 1  \) монотонна, так как конъюнкция, дизъюнкция и тождественная единица монотонны.

Теорема 12.12. Если функция алгебры логики не монотонна, то она не является композицией монотонных функций.

Доказательство заключается в применении закона контрапозиции к теореме 12.11. Теорема доказана.

Замечание 12.30. Обратная теорема для теоремы 12.11 не выполняется, так как существуют монотонные функции, которые являются композициями немонотонных функций, например, конъюнкция. Она монотонна, однако может быть представлена как композиция немонотонных штриха Шеффера и отрицания: \(  \large xy=(x \mid y)'  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 12. Специальные классы булевых функций
« Ответ #11 : Январь 16, 2018, 01:55:01 pm »
Свойства сохранения нуля (единицы), линейности, монотонности и понятие двойственности тесно связаны. Эта связь показана в следующих теоремах.

***

Пусть \(  \large f  \) - произвольная булева функция.

Теорема 12.13. Если функция \(  \large f  \) сохраняет нуль, то функция, двойственная к \(  \large f  \), сохраняет единицу.

Доказательство. Пусть \(  \large f  \) сохраняет нуль. Значит, в силу определения,

\(  \large f(0,0, \ldots, 0 )=0  \).

Тогда, учитывая определение двойственной функции и закон двойного отрицания, функцией, двойственной к \(  \large f  \), будет функция

\(  \large (f(x_1',x_2', \ldots, x_n'))'  \).

Значит,

\(  \large (f(1',1', \ldots, 1'))'=(f(0,0, \ldots, 0))'=0'=1  \).

Теорема доказана.

Теорема 12.14. Если функция \(  \large f  \) сохраняет единицу, то функция, двойственная к \(  \large f  \), сохраняет нуль.

Доказательство. Если \(  \large f  \) сохраняет единицу, то, в силу определения,

\(  \large f(1,1, \ldots, 1 )=1  \).

Тогда

\(  \large (f(0',0', \ldots, 0'))'=(f(1,1, \ldots, 1))'=1'=0  \).

Теорема доказана.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 12. Специальные классы булевых функций
« Ответ #12 : Январь 22, 2018, 02:26:21 pm »
Теорема 12.15. Если булева функция линейна, то двойственная ей функция тоже линейна.

Доказательство данной теоремы очень просто. Пусть \(  \large f  \) - линейная булева функция от \(  \large n  \) переменных. Значит, согласно определению линейной функции, её можно представить в виде

\(  \large f(x_1,x_2, \ldots, x_n) =a_0 \oplus a_1x \oplus a_2 x_2 \oplus \ldots a_nx_n  \).

И пусть \(  \large g  \) - функция, двойственная функции \(  \large f  \). Следовательно, в силу определения двойственности функций,

\(  \large g(x_1,x_2, \ldots, x_n)=(f(x_1',x_2', \ldots, x_n'))'  \).

Тогда, используя полиномиальное представление отрицания, получим:

\(  \large g(x_1,x_2, \ldots, x_n)=(a_0 \oplus a_1x \oplus a_1 \oplus a_2 x_2 \oplus a_2 \oplus \ldots a_nx_n \oplus a_n)'  \).

Снова выражаем отрицание через функцию Жегалкина и единицу:

\(  \large g(x_1,x_2, \ldots, x_n)=a_0 \oplus a_1x \oplus a_1 \oplus a_2 x_2 \oplus a_2 \oplus \ldots a_nx_n \oplus a_n \oplus 1  \).

Итак,

\(  \large g(x_1,x_2, \ldots, x_n)=a_1x \oplus a_2 x_2 \oplus a_nx_n \oplus b   \),

где

\(  \large b= a_0  \oplus a_1 \oplus a_2 \oplus a_n \oplus 1  \).

Следовательно, функция \(  \large g  \) тоже линейна. Теорема доказана.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 12. Специальные классы булевых функций
« Ответ #13 : Январь 22, 2018, 10:35:23 pm »
Теорема 12.16. Если функция алгебры логики монотонна, то двойственная ей функция тоже будет монотонной.

Доказательство. Пусть \(  \large f(x_1,x_2, \ldots, x_n)  \) - монотонная функция. Тогда для любых альфа и бета, согласно определению,

\(  \large \alpha_i \le \beta_i, \ i=1,2, \ldots, n  \)

влечёт

\(  \large f(\alpha_1, \alpha_2, \ldots, \alpha_n) \le f(\beta_1, \beta_2, \ldots, \beta_n)  \).

Рассмотрим двойственную \(  \large f  \) функцию алгебры логики:

\(  \large g(x_1,x_2, \ldots, x_n)=f(x_1 \oplus 1, x_2 \oplus 1, \ldots, x_n \oplus 1) \oplus 1  \).

Нужно доказать, что она тоже монотонна.

Поскольку прибавление единицы к обеим частям неравенства не меняет это неравенство, то

\(  \large \alpha_i  \oplus 1 \le \beta_i \oplus 1, \ i=1,2, \ldots, n  \)

влечёт

\(  \large f(\alpha_1 \oplus 1, \alpha_2 \oplus 1, \ldots, \alpha_n \oplus 1) \le f(\beta_1 \oplus 1, \beta_2 \oplus 1, \ldots, \beta_n \oplus 1)  \),

какими бы ни были альфа и бета.

А последнее неравенство равносильно

\(  \large f(\alpha_1 \oplus 1, \alpha_2 \oplus 1, \ldots, \alpha_n \oplus 1) \oplus 1 \le f(\beta_1 \oplus 1, \beta_2 \oplus 1, \ldots, \beta_n \oplus 1) \oplus 1 \).

Значит, для любых альфа и бета

\(  \large \alpha_i \oplus 1 \le \beta_i \oplus 1, \ i=1,2, \ldots, n  \)

влечёт

\(  \large f(\alpha_1 \oplus 1, \alpha_2 \oplus 1, \ldots, \alpha_n \oplus 1) \oplus 1 \le f(\beta_1 \oplus 1, \beta_2 \oplus 1 , \ldots, \beta_n \oplus ) \oplus 1  \).

Итак, функция \(  \large g(x_1,x_2, \ldots, x_n)  \) тоже монотонна. Что и требовалось доказать.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 12. Специальные классы булевых функций
« Ответ #14 : Февраль 16, 2018, 04:22:02 pm »
Рассмотрим задачу, где требуется найти булеву функцию, если известны некоторые свойства этой функции и значения на каких-то наборах значений переменных.

***

Задача 12.10. Найти функцию алгебры логики, зависящую от четырёх переменных (не менее двух из которых существенны), если известно, что она сохраняет нуль, самодвойственна, линейна и \(  \large f(1,1,0,1)=1  \).

Решение. Поскольку искомая функция алгебры логики линейна и зависит от четырёх переменных (пусть и некоторые из них фиктивны), будем искать её в виде

\(  \large f(x_1,x_2, x_3, x_4)=a_0 \oplus a_1x_1 \oplus a_2 x_2 \oplus a_3x_3 \oplus a_4 x_4  \).

Так как \(  \large f  \) сохраняет нуль, то

\(  \large a_0 \oplus a_1 \cdot 0 \oplus a_2 \cdot 0 \oplus a_3 \cdot 0 \oplus a_4 \cdot 0= 0  \).

Значит,

\(  \large a_0=0  \).

Итак, искомая булева функция имеет вид

\(  \large f(x_1,x_2, x_3, x_4)=a_1x_1 \oplus a_2 x_2 \oplus a_3x_3 \oplus a_4 x_4   \).

Используем самодвойственность функции \(  \large f  \);

\(  \large a_1x_1 \oplus a_2 x_2 \oplus a_3x_3 \oplus a_4 x_4=(a_1x_1' \oplus a_2x_2' \oplus a_3x_3' \oplus a_4x_4')'  \).

Выразим отрицание через сумму Жегалкина и единицу:

\(  \large a_1x_1 \oplus a_2 x_2 \oplus a_3x_3 \oplus a_4 x_4=a_1x_1 \oplus a_2x_2 \oplus a_3x_3 \oplus a_4x_4 \oplus a_1 \oplus a_2 \oplus a_3 \oplus a_4 \oplus 1 \).

Отсюда

\(  \large a_1 \oplus a_2 \oplus a_3 \oplus a_4 \oplus 1=0   \),

что эквивалентно

\(  \large a_1 \oplus a_2 \oplus a_3 \oplus a_4 =1  \).

Известно, что

\(  \large f(1,1,0,1)=1  \).

Следовательно,

\(  \large a_1 \cdot 1 \oplus a_2 \cdot 1 \oplus a_3 \cdot 0 \oplus a_4 \cdot 1=1  \).

Значит,

\(  \large a_1 \oplus a_2 \oplus a_4=1  \).

Итак, получим систему уравнений относительно неизвестных коэффициентов полинома Жегалкина:

\(  \large \begin{cases}  a_1 \oplus a_2 \oplus a_4=1  \\  a_1 \oplus a_2 \oplus a_3 \oplus a_4 =1 \end{cases}  \).

Решим её. Подставляя \(  \large 1  \) вместо  \(  \large a_1 \oplus a_2 \oplus a_4  \) во второе уравнение, получим:

\(  \large \begin{cases}  a_3=0  \\  a_1 \oplus a_2 \oplus a_4=1  \end{cases}  \).

Теперь нам известно, что третий коэффициент искомого полинома Жегалкина равен нулю. Осталось найти первый, второй и четвёртый. Для этого нужно решить уравнение

\(  \large a_1 \oplus a_2 \oplus a_4=1  \).

Учитывая первую теорему о сумме констант и тот факт, что функция существенно зависит не менее чем от двух переменных, делаем вывод, что

\(  \large a_1=a_2=a_4=1  \).

Тогда искомая функции имеет следующий вид:

\(  \large f(x_1,x_2,x_4)=x_1 \oplus  x_2 \oplus x_4  \).