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

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

Оффлайн Admin

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


В предыдущей лекции были рассмотрены специальные классы булевых функций. Для чего всё это нужно? Ответ содержится в настоящей лекции. Сначала мы дадим определение полной системы булевых функций, рассмотрим полные системы булевых функций, в том числе состоящие из одной-единственной функции, а затем докажем теорему, содержащую необходимое и достаточное условие полноты системы булевых функций. Данная теорема была доказана американским математиком Эмилем Постом в начале двадцатого века. В этой лекции слово "система" понимается как синоним слова "множество". Система булевых функций - устоявшийся термин. Его использование - дань традиции. Кроме того, подробно рассмотрим понятие "базис булевых функций".

***

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

Замечание 13.1. Известно, что любая функция алгебры логики, которая не является тождественной единицей, может быть представлена в СКНФ. Тождественную единицу можно представить как \(  \large x \vee x'  \). Значит, система булевых функций \(  \large \{ \vee, \cdot , ' \}  \) полна. Иначе говоря, всякая булева есть суперпозиция дизъюнкции, конъюнкции и отрицания.

Задача 13.1. Выразить логические константы, отрицание, конъюнкцию, дизъюнкцию, импликацию, эквиваленцию, сумму Жегалкина и стрелку Пирса через штрих Шеффера.

Решение. Используй идемпотентность конъюнкции и определение штриха Шеффера, имеем:

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

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

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

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

\(  \large xy=(x \mid y)'  \).

Воспользуемся идемпотентностью дизъюнкции:

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

Применим первый закон де Моргана:

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

Снова используем определение штриха Шеффера:

\(  \large ((x \mid y) \cdot (x \mid y))' =(x \mid y) \mid (x \mid y)  \).

Представим тождественный нуль как суперпозицию функции Шеффера. Для этого нам понадобится закон противоречия и найденные выше выражения для отрицания и конъюнкции:

\(  \large 0=xx'=x(x \mid x)=(x \mid (x \mid x)) \mid (x \mid (x \mid x))  \).

Учитывая это тождество, нетрудно найти выражения для тождественной единицы единицы:

\(  \large 1=0'=((x \mid (x \mid x)) \mid (x \mid (x \mid x)))'= ((x \mid (x \mid x)) \cdot (x \mid (x \mid x)))''=(x \mid (x \mid x)) \).

Помимо недавно найденного тождества, мы использовали определения отрицания и штриха Шеффера, идемпотентность конъюнкции и закон двойного отрицания.

Выразим импликацию через дизъюнкцию и отрицание, а затем воспользуемся первым законом де Моргана и законом двойного отрицания:

\(  \large x \to y = x' \vee y= (xy')'=(x \cdot (y \mid y))'  \).

После этого используем определение штриха Шеффера:

\(  \large (x \cdot (y \mid y))'=x \mid (y \mid y)  \).

Переходим к эквиваленции. Её можно представить как суперпозицию импликации и конъюнкции:

\(  \large x \leftrightarrow y =(x \to y)(y \to x)  \).

Выше мы нашли выражение импликации через штрих Шеффера:

\(  \large (x \to y)(y \to x)=(x \mid (y \mid y)) \cdot (y \mid (x \mid x))  \).

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

\(  \large (x \mid (y \mid y)) \cdot (y \mid (x \mid x))=((x \mid (y \mid y)) \mid (y \mid (x \mid x)))'  \).

Наконец, используем тот факт, что \(  \large x'=x \mid x  \). Имеем:

\(  \large ((x \mid (y \mid y)) \mid (y \mid (x \mid x)))'=((x \mid (y \mid y)) \cdot (y \mid (x \mid x))) \mid ((x \mid (y \mid y)) \cdot (y \mid (x \mid x)))  \).

Нам осталось найти выражения для суммы Жегалкина и стрелки Пирса. С суммой Жегалкина всё довольно просто. Известно, что \(  \large x \oplus y =(x \leftrightarrow y)'  \), а выражения для эквиваленции (в том числе промежуточные) и отрицания нам хорошо известны. Значит,

\(  \large x \oplus y=((x \mid (y \mid y)) \mid (y \mid (x \mid x)))''= (x \mid (y \mid y)) \mid (y \mid (x \mid x))  \).

Похожая ситуация и со стрелкой Пирса:

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

Замечание 13.2. Итак,

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

\(  \large 1 =x \mid (x \mid x)  \),

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

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

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

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

\(  \large x \leftrightarrow y= ((x \mid (y \mid y)) \cdot (y \mid (x \mid x))) \mid ((x \mid (y \mid y)) \cdot (y \mid (x \mid x)))  \),

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

\(  \large x \downarrow y=((x \mid x) \mid (y \mid y)) \mid ((x \mid x) \mid (y \mid y))   \).

Замечание 13.3. Система, состоящая из функции штрих Шеффера, полна, поскольку отрицание, конъюнкция и дизъюнкция (функции, образующие полную систему) выражаются через штрих Шеффера.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 13. Полные системы булевых функций
« Ответ #1 : Январь 17, 2018, 12:10:34 pm »
Задача 13.2. Выразить логические константы, отрицание, конъюнкцию, дизъюнкцию, импликацию, эквиваленцию, сумму Жегалкина и штрих Шеффера через стрелку Пирса.

Решение. Вспомним, что дизъюнкция идемпотентна, и используем определение стрелки Пирса:

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

Выразив отрицание через стрелку Пирса, переходим к конъюнкции. Применим второй закон де Моргана, закон двойного отрицания и тождество \(  \large x'= x \downarrow x  \). Имеем:

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

Займёмся дизъюнкцией:

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

Мы использовали определение стрелки Пирса и найденное выше выражение для отрицания. Найдём выражения для тождественного нуля и тождественной единицы. Используя закон исключённого третьего, а также тождества, выражающие отрицание и дизъюнкцию через стрелку Пирса, получим:

\(  \large 1=x \vee x'= x \vee (x \downarrow x)=(x \downarrow (x \downarrow x)) \downarrow (x \downarrow (x \downarrow x))   \).

Применим определение отрицания, стрелки Пирса идемпотеность дизъюнкции и закон двойного отрицания:

\(  \large 0=1'= ((x \downarrow (x \downarrow x)) \downarrow (x \downarrow (x \downarrow x)))' = ((x \downarrow (x \downarrow x)) \vee (x \downarrow (x \downarrow x)))''=x \downarrow (x \downarrow x)  \).

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

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

С эквиваленцией поступим немного иначе. Сначала представим её как суперпозицию конъюнкции, дизъюнкции и отрицания:

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

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

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

Вспомним определение стрелки Пирса и тождество \(  \large x'= x \downarrow x  \):

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

Теперь избавимся от конъюнкции:

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

Выражение получилось довольно громоздким. Однако его можно сократить, если учесть, что

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

Имеем:

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

С суммой Жегалкина всё довольно просто, если вспомнить, что она представляет собой отрицание эквиваленции:

\(  \large x \oplus y=(x \leftrightarrow y)'=(x \leftrightarrow y) \downarrow (x \leftrightarrow y)=  \)

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

Наконец, выразим штрих Шеффера через стрелку Пирса:

\(  \large x \mid y=(xy)'=((x \downarrow x) \downarrow (y \downarrow y))'= ((x \downarrow x) \downarrow (y \downarrow y)) \downarrow ((x \downarrow x) \downarrow (y \downarrow y)) \).

Мы использовали определение штриха Шеффера и найденные выше выражения для конъюнкции и отрицания.

Замечание 13.4. Итак,

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

\(  \large 1= (x \downarrow (x \downarrow x)) \downarrow (x \downarrow (x \downarrow x))   \),

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

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

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

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

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

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

\(  \large x \mid y =((x \downarrow x) \downarrow (y \downarrow y)) \downarrow ((x \downarrow x) \downarrow (y \downarrow y))  \).

Замечание 13.5. Стрелка Пирса образует полную систему булевых функций (состоящую из одной-единственной функции), так как штрих Шеффера, который также образует полную систему, можно представить как суперпозицию от стрелки Пирса.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 13. Полные системы булевых функций
« Ответ #2 : Январь 17, 2018, 12:10:59 pm »
Дадим определения собственного и замкнутого классов функций алгебры логики, а затем докажем, что классы \(  \large P_0  \), \(  \large P_1  \), \(  \large S  \), \(  \large L  \) и \(  \large M  \) являются как собственными, так и замкнутыми. Данная теорема используется при доказательстве теоремы Поста.

***

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

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

Замечание 13.6. Замкнутые классы булевых функций называются также классами Поста.

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

Доказательство того факта, что эти классы являются собственными заключается в предъявлении функций, относящихся к классу, и функций, не относящейся к классу. Из лекции 12 известно, что стрелка Пирса не сохраняет нуль и единицу, а дизъюнкция - сохраняет. Отрицание самодвойственно, а дизъюнкция - нет. Эквиваленция линейна, а штрих Шеффера - нет. Дизъюнкция монотонна, а сумма Жегалкина - нет. Доказательство замкнутости у нас уже есть: теорема 12.1, теорема 12.3, теорема 12.7, теорема 12.9 и теорема 12.11. Теорема доказана.
 

Оффлайн Admin

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

***

Теорема 13.2. Система булевых функций полна тогда и только тогда, когда в этой системе есть функция, не принадлежащая к классу \(  \large P_0  \), есть функция, не принадлежащая к классу \(  \large P_1  \), есть функция, не принадлежащая к классу \(  \large S  \), есть функция, не принадлежащая к классу \(  \large L  \), есть функция не принадлежащая к классу \(  \large M  \).

Доказательство.

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

Теорема 13.3. Система булевых функций неполна, если и только если в этой системе все функции принадлежат к классу \(  \large P_0  \), или все функции принадлежат к классу \(  \large P_1  \), или все функции принадлежат к классу \(  \large S  \), или все функции принадлежат к классу \(  \large L  \), или все функции принадлежат к классу \(  \large M  \).

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

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 13. Полные системы булевых функций
« Ответ #4 : Январь 17, 2018, 12:12:29 pm »
Определение 13.4. Булева функция называется шефферовой, если она сама образует полную систему булевых функций.

Замечание 13.7. Шефферовы функции называются также обобщёнными функциями Шеффера.

Задача 13.3. Дана функция \(  \large f(x,y,z)=(10000001)  \). Выяснить является ли данная функция шефферовой. Если нет, то какую одну функцию надо добавить к ней, чтобы получить полную систему. Единственным ли образом можно это сделать?

Решение. Чтобы найти аналитическое выражение данной функции, используем СДНФ:

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

В силу теоремы 13.2, равносильной теореме Поста, данная функция не является шефферовой, так как она сохраняет единицу:

\(  \large f(1,1,1)=(1' \cdot 1' \cdot 1') \vee (1 \cdot 1 \cdot 1) =0 \vee 1=1 \).

Функция не сохраняет нуль, так как

\(  \large f(0,0,0)=(0' \cdot 0' \cdot 0') \vee (0 \cdot 0 \cdot 0) =1 \vee 0=1 \).

Функция не является линейной, так как представляющий её полином Жегалкина имеет вид

\(  \large p(x,y,z)=xy \oplus xz \oplus yz \oplus x \oplus y \oplus z \oplus 1 \).

Она не является самодвойственной, поскольку

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

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

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

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

\(  \large 0 \le 0, \ 0 \le 0, \ 0 \le 1 \),

но

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

Добавим к этой функции, например, \(  \large f(x,y)=x \oplus y=(0110) \). Она не сохраняет единицу, так как

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

Тогда, согласно теореме Поста, система \(  \large \{\ (10000001), \ (0110) \}\  \) является полной.

Можно добавить и любую другую функцию, не сохраняющую единицу, например, \(  \large f(x,y,z)=x \oplus y \oplus z' \). Следовательно, можно образовать полную систему не единственным образом.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 13. Полные системы булевых функций
« Ответ #5 : Январь 17, 2018, 12:12:44 pm »
Определение 13.5. Базисом булевых функций называется такая полная система булевых функций, удаление из которой любой функции делает систему неполной.

Замечание 13.8. Любая обобщённая функция Шеффера является базисом.

Задача 13.4. Составить таблицу Поста и доказать, что система булевых функций полна.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 13. Полные системы булевых функций
« Ответ #6 : Январь 17, 2018, 12:12:59 pm »
Задача 13.5. Доказать, что система, состоящая из отрицания и импликации, является базисом, и выразить в этом базисе все не являющиеся константами элементарные булевы функции.

Решение. Из лекции 12 мы знаем, что отрицание не сохраняет нуль и единицу, самодвойственно и линейно, но не является монотонной булевой функцией. Импликация не сохраняет нуль, но сохраняет единицу, не обладает свойствами самодвойственности, линейности и монотонности. Используя эти данные, составим таблицу Поста:

\( \begin{array}{|c|c|}
\hline
 &  P_0 &  P_1 & S & L & M  \\
\hline
' &  - &  - & +& +& -  \\
\hline
\to  & - & + & - & - & - \\
\hline
\end{array}  \)

Итак, в рассматриваемой системе есть функция, которая не сохраняет нуль и единицу (отрицание), и есть функция, которая не является самодвойственной, линейной и монотонной (импликация). Значит, система \(  \large \{ ', \to \}  \) полна. Она является базисом по следующим причинам. Если исключить из неё отрицание, то в этой системе не будет функции, которая не сохраняет единицу, а если исключить импликацию, то не будет функции, которая не является самодвойственной и линейной. Теперь выразим в базисе \(  \large \{ ', \to \}  \) тождественный нуль, тождественную единицу, отрицание, конъюнкцию, дизъюнкцию, импликацию, эквиваленцию, функции Жегалкина, Шеффера  Пирса. Используемые при этом тождественные преобразования довольно просты, поэтому оставим их без комментариев:

\(  \large 1=x \vee x' =x' \vee x=x \to x  \),

\(  \large 0=1'=(x \to x)' \),

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

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

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

\(  \large x \leftrightarrow y= (x \to y)(y \to x)=((x \to y)' \vee (y \to x)')'=((x \to y) \to (y \to x)')'  \),

\(  \large x \oplus y=(x \leftrightarrow y)'= (x \to y) \to (y \to x)' \),

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

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

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 13. Полные системы булевых функций
« Ответ #7 : Февраль 16, 2018, 04:21:05 pm »
Теорема 13.4. Система булевых функций является базисом тогда и только тогда, когда она полна и содержит не более четырёх функций.

Доказательство.

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

Теорема 13.5. Система булевых функций не является базисом, если и только если она не полна или содержит более четырёх функций.
 
Доказательство. По закону противоположности. Теорема доказана.

Замечание 13.9. Значение данных теорем заключается в следующем. Рассмотрим некоторую систему булевых функций \(  \large \{f_1, f_2, \ldots, f_n \}  \). Если \(  \large n \le 4  \), то для доказательства того, что данная система есть базис, достаточно доказать её полноту. Если \(  \large n>4  \), то этого достаточно, чтобы сделать вывод о том, что система базисом не является.