Автор Тема: Лекция 11. Полиномы Жегалкина  (Прочитано 533 раз)

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

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 11. Полиномы Жегалкина
« : Декабрь 12, 2017, 02:45:16 pm »
Лекция 11. Полиномы Жегалкина


Наряду с совершенными нормальными формами существует ещё одна стандартная форма представления функций алгебры логики - это полиномы Жегалкина. Определим это понятие, а затем докажем, что для всякой булевой функции существует единственное полиномиальное представление.

***

Определение 11.1. Полиномом Жегалкина называется булева функция вида

\(  \large a_0 \oplus a_1x_1 \oplus a_2x_2 \oplus \cdots \oplus a_nx_n \oplus a_{12}x_1x_2 \oplus a_{13}x_1x_3 \oplus \ldots \oplus a_{12 \ldots n}x_1x_2 \ldots x_n  \),

где \(  \large a_0,a_1, \ldots, a_{12 \ldots n} \in \{ 0,1\}  \).

Замечание 11.1. Если \(  \large a_i=0  \), то соответствующий одночлен отсутствует в полиноме, так как \(  \large 0 \cdot x=0  \) и \(  \large x \oplus 0=x  \).

Замечание 11.2. Полином Жегалкина называется также алгебраической нормальной формой булевой функции. Сокращённо - АНФ.

Замечание 11.3. Здесь и далее будем считать, что конъюнкция имеет приоритет над функцией Жегалкина, и лишние скобки не пишем.

Пример 11.1. Следующие булевы функции представлены в алгебраической нормальной форме:

1) \(  \large xyz \oplus xy \oplus yz \oplus x \oplus y  \);

2) \(  \large x \oplus y \oplus z  \);

3) \(  \large x_1x_2 \oplus x_1 \oplus x_3 \oplus x_4x_2 \oplus 1   \).

***

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

***

Пусть \(  \large f_1, \ f_2, \ \ldots, \ f_n  \) - произвольные булевы функции.

Теорема 11.1. Сумма Жегалкина функций \(  \large f_1, \ f_2, \ \ldots, \ f_n  \) равна единице тогда и только тогда, когда количество слагаемых, равных единице, нечётно.

Доказательство. Необходимость. Пусть

\(  \large f_1 \oplus f_2 \oplus \ldots \oplus f_n=1  \).

Предположим, что

\(  \large f_1=f_2= \ldots =f_{2k-1}=f_{2k}=1  \),

где \(  \large k \in \{0,1,2, \ldots \}  \), \(  \large 2k \le n  \). Рассмотрим два случая. Пусть \(  \large 2k=n  \). Тогда, используя тождества \(  \large x \oplus x =0  \) и \(  \large x \oplus 0=x  \), получим:

\(  \large f_1 \oplus f_2 \oplus \ldots \oplus f_n=(f_1 \oplus f_2) \oplus (f_3 \oplus f_4) \oplus \ldots \oplus (f_{2k-1} \oplus f_{2k})= \)

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

Противоречие. Пусть теперь \(  \large 2k < n  \). Иначе говоря, \(  \large 2k  \) слагаемых равны единице, а остальные равны нулю. Тогда

\(  \large f_1 \oplus f_2 \oplus \ldots \oplus f_n=(f_1 \oplus f_2) \oplus (f_3 \oplus f_4) \oplus \ldots \oplus (f_{2k-1} \oplus f_{2k}) \oplus f_{2k+1} \oplus \ldots \oplus f_{2n}= \)

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


Снова получили противоречие. Значит, количество равных единице слагаемых нечётно.

Достаточность. Пусть

\(  \large f_1=f_2= \ldots= f_{2k}= f_{2k+1}=1  \),

причём \(  \large k \in \{0,1,2, \ldots \}  \), \(  \large 2k+1 \le n  \). Снова рассмотрим два случая. Пусть \(  \large 2k+1=n  \). Тогда

\(  \large (f_1 \oplus f_2) \oplus \ldots \oplus (f_{2k-1} \oplus f_{2k}) \oplus f_{2k+1}=  \)

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

Пусть \(  \large 2k+1<n  \). Значит, кроме \(  \large 2k+1  \) равных единице слагаемых, есть некоторое количество слагаемых, равных нулю. Следовательно,

\(  \large (f_1 \oplus f_2) \oplus \ldots \oplus (f_{2k-1} \oplus f_{2k}) \oplus f_{2k+1} \oplus f_{2k+2} \oplus \ldots \oplus f_{2n}=  \)

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

Итак, в обоих случаях сумма слагаемых равна единице. Теорема доказана.

Теорема 11.2. Сумма Жегалкина функций \(  \large f_1, \ f_2, \ \ldots, \ f_n  \) равна нулю тогда и только тогда, когда количество слагаемых, равных единице, чётно.

Доказательство. Настоящая теорема равносильна предыдущей, учитывая закон противоположности. Теорема доказана.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 11. Полиномы Жегалкина
« Ответ #1 : Декабрь 16, 2017, 11:56:38 am »
Теорема 11.3. Для каждой булевой функции существует единственный полином Жегалкина.

Доказательство. Существование. Каждая функция алгебры логики может быть представлена как композиция дизъюнкции, конъюнкции и отрицания. Учитывая, что дизъюнкция выражается через конъюнкцию и сумму Жегалкина:

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

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

\(  \large x' = x \oplus 1  \),

существование доказано.

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

\(  \large p_1(x,y)=a_1xy \oplus a_2 x \oplus a_3 y \oplus a_4  \),

\(  \large p_2(x,y)=b_1xy \oplus b_2 x \oplus b_3 y \oplus b_4  \).

Так как \(  \large p_1 \not = p_2  \), то, например,

\(  \large a_2 \not = b_2, a_1=b_1, a_3=b_3, a_4=b_4  \).

Пусть, например, \(  \large a_2=0,b_2=1  \). Тогда

\(  \large p_1(x,y)=b_1xy \oplus  b_3 y \oplus b_4  \),

\(  \large p_2(x,y)=b_1xy \oplus b_2 x \oplus b_3 y \oplus b_4  \).

Поскольку полиномы представляют одну и ту же функцию, то, например, при \(  \large x=1,y=0  \), их значения должны быть равны. Имеем:

\(  \large p_1(1,0)= b_4  \),

\(  \large p_2(1,0)=b_2 \oplus b_4  \).

Итак, \(  \large b_4=b_2 \oplus b_4  \). Значит, \(  \large b_2=0  \), так как \(  \large x=x \oplus 0  \). Однако \(  \large b_2=1  \). Противоречие. Значит, \(  \large p_1=p_2  \). Иначе говоря, если у булевой функции два полинома Жегалкина,
 то они совпадают. Теорема доказана.

Замечание 11.4. Существует несколько способов нахождения полинома Жегалкина. Мы рассмотрим только два - метод тождественных преобразований и метод неопределённых коэффициентов. Первый метод заключается в применении основных тождеств теории булевых функций. Он аналогичен соответствующему методу вычисления нормальных форм булевых функций. Он обычно применяется для функций алгебры логики, заданных аналитически. Второй метод чаще всего применяется для функций, заданных векторным способом. Метод неопределённых коэффициентов заключается в следующем. Пусть требуется построить полином Жегалкина для функции \(  \large f(x,y,z)  \), заданной двоичным набором \(  \large (b_1b_2 \ldots b_n)  \). Запишем функцию в виде полинома с неопределёнными коэффициентами \(  \large a_0,a_1, \ldots, a_7  \):

\(  \large f(x,y,z)=a_1xyz \oplus a_2xy \oplus a_3xz \oplus a_4yz \oplus a_5x \oplus a_6y \oplus a_7z \oplus a_8  \).

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

\(  \large (0,0,0), (0,0,1), \ldots, (1,1,1)  \),

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

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 11. Полиномы Жегалкина
« Ответ #2 : Декабрь 16, 2017, 11:56:45 am »
Задача 11.1. Найти полиномиальные представления всех элементарных булевых функций, не являющихся константами.

Решение. Нам уже известны полиномы Жегалкина для отрицания и дизъюнкции:

\(  \large x' =x \oplus 1  \),

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

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

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

Избавимся от отрицания:

\(  \large x' \vee y= (x \oplus 1) \vee y  \).


Используем полиномиальное представление дизъюнкции и тождество \(  \large x \cdot 1 = x  \):

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

Вычеркнем парные слагаемые:

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

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

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

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

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

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

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

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

\(  \large (xy)'=xy \oplus 1  \).

Наконец, вычислим полином для стрелки Пирса. Представим её как композицию дизъюнкции и отрицания:

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

Используем полиномиальное представление дизъюнкции:

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

Избавимся от отрицания:

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

Мы нашли АНФ стрелки Пирса.

Итак,

\(  \large x \to y=xy \oplus x \oplus 1  \),

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

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

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

Найденные представления будут использоваться в последующем.
 
Сказали спасибо: Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 11. Полиномы Жегалкина
« Ответ #3 : Декабрь 16, 2017, 11:56:53 am »
Рассмотрим примеры вычисления полинома Жегалкина методом тождественных преобразований и методом неопределённых коэффициентов. Далее будем вычёркивать повторяющиеся члены конъюнкции, используя закон идемпотентность и не упоминая всякий раз об этом.

***

Задача 11.2. Найти полином Жегалкина для булевой функции, заданной аналитически, двумя способами:

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

Решение. Сначала найдём полином Жегалкина методом тождественных преобразований. Используем найденные выше полиномиальные представления эквиваленции и штриха Шеффера:

\(  \large (x \leftrightarrow z)(y \to (x \downarrow z)) =(x \oplus z \oplus 1)(y \to (xz \oplus x \oplus z \oplus 1))  \).

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

\(  \large (x \oplus z \oplus 1)(y \to (xz \oplus x \oplus z \oplus 1))=(x \oplus z \oplus 1)(y(xz \oplus x \oplus z \oplus 1) \oplus y \oplus 1)  \).

Раскроем скобки и вычеркнем парные одночлены:

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

Повторяем указанные манипуляции:

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

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

\(  \large p(x,y,z)= xyz  \oplus x \oplus z \oplus 1   \).

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

\( \begin{array}{|c|c|}
\hline
x &  y &  z &  f(x,y,z)  \\
\hline
0 &  0 &  0 & 1  \\
\hline
0 & 0 & 1 & 0 \\
\hline
0 & 1 & 0 &  1 \\
\hline
0 & 1 & 1 & 0 \\
\hline
1 & 0 & 0 & 0  \\
\hline
1 & 0 & 1 & 1  \\
\hline
1 & 1 & 0 & 0  \\
\hline
1 & 1 & 1 &  0 \\
\hline
\end{array}  \)

Полином Жегалкина будем искать в виде

\(  \large p(x,y,z)=a_1xyz \oplus a_2xy \oplus a_3xz \oplus a_4yz \oplus a_5x \oplus a_6y \oplus a_7z \oplus a_8 \).

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

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

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

Используя эти данные, составим и решим систему уравнений:

\(  \large \begin{cases}a_8=1 \\ a_7 \oplus a_8=0 \\ a_6 \oplus a_8=1 \\ a_4 \oplus a_6 \oplus a_7 \oplus a_8=0 \\ a_5 \oplus a_8=0 \\ a_3 \oplus a_5 \oplus a_7 \oplus a_8=1 \\ a_2 \oplus a_5 \oplus a_6 \oplus a_8=0 \\ a_1 \oplus a_2 \oplus a_3 \oplus a_4 \oplus a_5 \oplus a_6 \oplus a_7 \oplus a_8=0 \end{cases} \ \Leftrightarrow \ \begin{cases} a_1=1 \\ a_2=0 \\ a_3=0 \\ a_4=0 \\ a_5=1 \\ a_6=0 \\ a_7=1 \\ a_8=1 \end{cases} \).

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

\(  \large p(x,y,z)=xyz \oplus x \oplus z \oplus 1 \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 11. Полиномы Жегалкина
« Ответ #4 : Декабрь 16, 2017, 11:57:02 am »
Задача 11.3.  Найти алгебраическую нормальную форму для булевой функции от трёх переменных, которая задана двоичным набором \(  \large (00000111)  \).

Решение. Известно, что каждая булева функция имеет единственную алгебраическую нормальную форму (полином Жегалкина). Запишем искомую АНФ с неопределёнными коэффициентами:

\(  \large p(x,y,z)=a_1xyz \oplus a_2 xy \oplus a_3 xz \oplus a_4 yz \oplus a_5 x \oplus a_6 y  \oplus a_7 z \oplus a_8 \).

Нам известно, что

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

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

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

\(  \large \begin{cases} a_8=0 \\ a_7 \oplus a_8=0 \\ a_6 \oplus a_8 =0 \\ a_4 \oplus a_6 \oplus a_7 \oplus a_8 =0 \\ a_5 \oplus a_8=0 \\ a_3 \oplus a_5 \oplus a_6 \oplus a_8=1 \\ a_2 \oplus a_5 \oplus a_6 \oplus a_8=1 \\ a_1 \oplus a_2 \oplus \cdots \oplus a_8=1 \end{cases} \).

Решая её, находим:

\(  \large a_1=a_2=a_3=1, \ a_4=a_5= \cdots = a_8=0 \).

Значит,

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

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

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

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

\(  \large xy'z \vee xyz' \vee xyz=xy'z \vee (xy(z' \vee z))  \).

Применяем закон исключённого третьего и правило \(  \large x \cdot 1 = x  \):

\(  \large xy'z \vee (xy(z' \vee z))=xy'z \vee xy  \).

Вынесем икс зак скобки:

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

Используем дистрибутивный закон:

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

Снова вспомним про закон исключённого третьего и правила действий с логическими константами:

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

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

\(  \large x(z \vee y) =xyz \oplus xy \oplus xz  \).

Итак,

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

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 11. Полиномы Жегалкина
« Ответ #5 : Декабрь 16, 2017, 12:29:11 pm »
Рассмотрим задачи, где применяются полиномы Жегалкина. К таким задачам, в частности, относятся задачи на проверку равенства функций алгебры, а также системы уравнений с логическими функциями.

***

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

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

Решение. Будем искать полиномы Жегалкина с помощью основных тождеств теории булевых функций и найденных ранее полиномиальных представлений элементарных функций алгебры логики. Начнём с левой части равенства. Избавимся от дизъюнкции и штриха Шеффера:

\(  \large (x \to (y \vee z)) \to (x \mid z)=(x \to (yz \oplus y \oplus z)) \to (xz \oplus 1)  \).

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

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

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

\(  \large (xyz \oplus xy \oplus xz \oplus x \oplus 1) \to (xz \oplus 1) =  \)

\(  \large =(xyz \oplus xy \oplus xz \oplus x \oplus 1)  (xz \oplus 1) \oplus xyz \oplus xy \oplus xz \oplus x \oplus 1 \oplus 1  \).

Осталось раскрыть скобки и вычеркнуть парные слагаемые:

\(  \large (xyz \oplus xy \oplus xz \oplus x \oplus 1)  (xz \oplus 1) \oplus xyz \oplus xy \oplus xz \oplus x \oplus 1 \oplus 1=xz \oplus 1  \).

Займёмся правой частью равенства. Избавимся от отрицания и импликации:

\(  \large y' \downarrow (x \to z)'=(y \oplus 1) \downarrow (xz \oplus x \oplus 1 \oplus 1)  \).

Вычёркиваем две парные единицы:

\(  \large (y \oplus 1) \downarrow (xz \oplus x \oplus 1 \oplus 1)=(y \oplus 1) \downarrow (xz \oplus x)  \).

Используем полиномиальное представление стрелки Пирса:

\(  \large (y \oplus 1) \downarrow (xz \oplus x)=(y \oplus 1) (xz \oplus x) \oplus y \oplus 1 \oplus  xz \oplus x \oplus 1  \).

Раскрыв скобки и вычеркнув все парные слагаемые, получим:

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

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

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 11. Полиномы Жегалкина
« Ответ #6 : Декабрь 16, 2017, 12:29:32 pm »
Задача 11.5. Известно, что:

1) если работает агрегат \(  \large x  \), то работает агрегат \(  \large y  \);
2) либо работает агрегат \(  \large y  \), либо работает агрегат \(  \large z  \);
3) агрегат \(  \large x   \) работает тогда и только тогда, когда работает агрегат \(  \large t  \);
4) агрегат \(  \large x  \) работает или работает агрегат \(  \large y  \).

Составить систему уравнений с булевыми переменными и найти её решение.

Решение. Введём булевы переменные \(  \large x  \), \(  \large y  \), \(  \large z  \) и \(  \large t  \), которым поставим с соответствие высказывания "работает агрегат \(  \large x  \)", "работает агрегат \(  \large y  \)", работает агрегат \(  \large z  \)" и "работает агрегат \(  \large t  \)". Все эти высказывания истинны. Тогда, используя условие задачи, составим систему логических уравнений. Отметим, что оборот "либо..., либо..." мы будем понимать как строгую дизъюнкцию, которой в теории булевых функций соответствует сумма Жегалкина. Имеем:

\(  \large \begin{cases} x \to y=1 \\ y \oplus z=1 \\ x \leftrightarrow t=1 \\ x \vee y=1 \end{cases}   \).

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

\(  \large \begin{cases} x  y \oplus x \oplus 1=1 \\ y \oplus z=1 \\ x \oplus  t \oplus 1=1 \\ x  y \oplus x \oplus y=1 \end{cases}   \).

Преобразуем первое и третье уравнения, прибавив к обеим его частям единицу и используя тождество \(  \large x \oplus 0 =x  \):

\(  \large \begin{cases} x  y \oplus x =0 \\ y \oplus z=1 \\ x \oplus  t =0 \\ x  y \oplus x \oplus y=1 \end{cases}   \).

Учитывая вторую теорему о сумме констант и используя уравнения \(  \large x \oplus t=0  \), заключаем, что либо \(  \large x=t=1  \), либо \(  \large x=t=1  \). Согласно первой теореме о сумме констант, либо \(  \large y=1, \ z= 0  \), либо \(  \large y=0, \ z=1  \), поскольку \(  \large y \oplus z=1  \). Итак, у нас четыре решения:

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

Используя первое и четвёртое уравнения системы, легко проверить, что ей удовлетворяют только первое и последнее решения.

Итак, \(  \large \{(0,1,0,0); \ (1,1,0,1) \}\ \) - решение системы уравнений. Значит, либо работает агрегат \(  \large y  \), а все остальные не работают, либо не работает агрегат \(  \large z  \), а все остальные работают.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 11. Полиномы Жегалкина
« Ответ #7 : Февраль 16, 2018, 04:22:53 pm »
Задача 11.6. Решить систему логических уравнений:

\(  \large \begin{cases} (x \downarrow y) \leftrightarrow z=1 \\ (x \leftrightarrow y) \to z=0 \\  y(x \vee z) =1 \end{cases} \).

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

\(  \large \begin{cases} (xy \oplus x \oplus y \oplus 1) \leftrightarrow z=1 \\ (x \oplus y \oplus 1) \to z=0 \\  xyz \oplus xy \oplus xz=1\end{cases}  \).

Осталось избавиться от оставшихся эквиваленции и импликации:

\(  \large \begin{cases} xy \oplus x \oplus y \oplus 1 \oplus z \oplus 1=1 \\ xz \oplus yz \oplus z \oplus x \oplus y \oplus 1 \oplus 1=0 \\  xyz \oplus xy \oplus xz=1\end{cases}  \).

Вычеркнем парные единицы:

\(  \large \begin{cases} xy \oplus x \oplus y  \oplus z =1 \\ xz \oplus yz \oplus z \oplus x \oplus y =0 \\  xyz \oplus xy \oplus xz=1\end{cases}  \).

Рассмотрим второе уравнение системы и заметим, что прибавление к обеим его частям суммы \(  \large xz \oplus yz  \) приводит данное уравнение к следующему виду:

\(  \large x \oplus y \oplus z= xz \oplus yz  \).

Подставим в первое уравнение \(  \large xz \oplus yz  \) вместо \(  \large x \oplus y \oplus z  \):

\(  \large xy \oplus xz \oplus yz=1  \).

Итак, система уравнений примет вид

\(  \large \begin{cases} xy \oplus xz \oplus yz =1 \\ x \oplus y \oplus z= xz \oplus yz \\ xyz \oplus xy \oplus yz =1\end{cases}  \).

Рассмотрим первое уравнение и вспомним теорему о сумме констант. Согласно данной теореме, сумма Жегалкина \(  \large xy  \), \(  \large xz  \) и \(  \large yz  \) равна единице, если и только если количество равных единице слагаемых нечётно. Иначе говоря, такое слагаемое либо одно, либо их три. Рассмотрим все случаи.

1) Пусть

\(  \large xy=xz=yz=1  \).

В силу определения конъюнкции, это равенство выполняется тогда и только тогда, когда

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

Подставим эти значения во второй уравнение системы:

\(  \large 1 \oplus 1 \oplus 1= 1 \oplus 1  \).

Очевидно, это ложное равенство. Значит, тройка \(  \large (1,1,1)  \) не является решением системы.

2) Пусть

\(  \large xy=1, \ xz=yz=0  \).

Первое равенство эквивалентно \(  \large x=y=1  \). Это совместимо с двумя последними равенствами только при \(  \large z=0  \). Проверим, удовлетворяет ли тройка \(  \large (1,1,0)  \) двум другим уравнениям системы. Подставим найденные значения во второе уравнение:

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

Получили истинное равенство. Теперь проверим третье уравнение:

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

Это равенство также истинно. Следовательно, \(  \large (1,1,0)  \) - решение системы.

3) Пусть \(  \large xy=yz=0, \ xz=1  \). Последнее равенство эквивалентно \(  \large x=z=1  \). Это совместимо с первыми двумя равенствами, если и только если \(  \large y=0  \). Покажем, что тройка \(  \large (1,0,1)  \) не удовлетворяет третьему уравнению системы:

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

4) Пусть \(  \large xy=xz=0, \ yz=1  \). Согласно определению конъюнкции, последнее равенство возможно тогда и только тогда, когда \(  \large y=z=1  \). Это совместимо с первыми двумя равенствами только при \(  \large x=0  \). Однако тройка \(  \large (0,1,1)  \) обращает второе уравнение системы в ложное равенство:

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

Итак,

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

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

\( \begin{array}{|c|c|}
\hline
x &  y &  z &  x \downarrow y & (x \downarrow y) \leftrightarrow z & x \leftrightarrow y & (x \leftrightarrow y) \to z & x \vee z & y(x \vee z)  \\
\hline
0 &  0 &  0 & 1  & 0 & 1 & 0 & 0 & 0  \\
\hline
0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\
\hline
0 & 1 & 0 &  0 & 1 & 0 & 1 & 0 & 0\\
\hline
0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\
\hline
1 & 0 & 0 &0 & 1 & 0 & 1 & 1 &0  \\
\hline
1 & 0 & 1 & 0& 0 & 0 & 1 & 1 & 0  \\
\hline
1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\
\hline
1 & 1 & 1 &  0 & 0 & 1 & 1 & 1 & 1\\
\hline
\end{array}  \)

Замечаем, что только при \(  \large x=y=1, \ z=0  \) (седьмая строка таблицы значений) первая и третья функции обращаются в единицу, а вторая функция - в нуль.