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

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

Оффлайн Никита

  • Пользователь
  • Сообщений: 32
    • Просмотр профиля
Составить таблицу Поста и найти базисы из следующих булевых функций:

\(  \large f_1(x,y,z) \equiv x \vee (y \leftrightarrow z) , \ f_2(x,y) \equiv x(x + y), \ f_3(x,y,z) \equiv (x \to z) y, \ f_4(x,y) \equiv x' \mid ( y \vee x  )  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 4954
  • Поблагодарили: 1572 раз(а)
    • Просмотр профиля
Чтобы составить таблицу Поста, нужно решить вопрос о принадлежности каждой из четырёх рассматриваемых функций к классам \(  \large P_0, \ P_1, \ S, \ L, \ M \). Если некоторая функция принадлежит тому или иному классу, то на пересечении соответствующей строки и соответствующего столбца ставится знак "плюс", если не принадлежит, то ставится знак "минус"

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

а) \(  \large f_1(x,y,z)=xy+xz+y+z+1 \);

б) \(  \large f_2(x,y)=xy+x \);

в) \(  \large f_3(x,y,z)=xyz+xy+y \);

г) \(  \large f_4(x,y)=xy+y+1 \).

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

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

2) Решим вопрос о принадлежности функций к классу \(  \large P_0 \). Имеем:

а) \(  \large f_1(0,0,0)=0 \cdot 0+0 \cdot 0+0+0+1=0+0+0+0+1=1 \);

б) \(  \large f_2(0,0)=0 \cdot 0+0=0+0=0 \);

в) \(  \large f_3(0,0,0)=0 \cdot 0 \cdot 0+0 \cdot 0+0=0+0+0=0 \);

г) \(  \large f_4(0,0)=0 \cdot 0+0+1=0+0+1=1 \).

Итак, функции \(  \large f_2 \) и \(  \large f_3 \) сохраняют нуль, а функции \(  \large f_1 \) и \(  \large f_4 \) - не сохраняют.

3) Проверим, какие из функций принадлежат к классу \(  \large P_1 \). Имеем:

а) \(  \large f_1(1,1,1)=1 \cdot 1 +1 \cdot 1+1+1+1=1+1+1+1+1=0+0+1=1 \);

б) \(  \large f_2(1,1)=1 \cdot 1+1=1+1=0 \);

в) \(  \large f_3(1,1,1)=1 \cdot 1 \cdot 1+1 \cdot 1+1=1+1+1=0+1=1 \);

г) \(  \large f_4(1,1)=1 \cdot 1+1+1=1+1+1=0+1=1 \).

Вывод: все рассматриваемые функции, кроме \(  \large f_2 \), сохраняют единицу.

4) Выясним, какие функции принадлежат к классу \(  \large S \). Используя определение самодвойственной функции, получим:

а) \(  \large (f_1(x,y,z))'=(xy+xz+y+z+1)'=xy+xz+y+z \);

\(  \large f_1(x',y',z')=x'y'+x'z'+y'+z'+1=xy+xz+1  \);

б) \(  \large (f_2(x,y))'=(xy+x)'=xy+x+1 \);

\(  \large f_1(x',y')=x'y'+x'=xy+y \);

в) \(  \large (f_3(x,y,z))'=(xyz+xy+y)'=xyz+xy+y+1 \);

\(  \large f_3(x',y',z')=x'y'z'+x'y'+y'=xyz+yz+xz+y+z+1 \);

г) \(  \large (f_4(x,y))'=(xy+y+1)'=xy+y \);

\(  \large f_4(x',y')=x'y'+y'+1=xy+x+1 \).

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

5) Используя определения элементарных булевых функций, составим таблицы значений для функций \(  \large f_1, \ f_2, \ f_3, \ f_4 \) и выясним, являются ли они монотонными.



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



Рассмотрим первую и вторую строки таблицы. Функция \(  \large f_1 \) не является монотонной, так как

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

но

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



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



Рассмотрев третью и четвертую строки таблицы, делаем вывод, что функция \(  \large f_2 \) также не является монотонной, поскольку

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

но

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



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



Рассмотрим третью и седьмую строки таблицы. Функция \(  \large f_3 \) не является монотонной, так как

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

но

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



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



Рассмотрев первую и вторую строки таблицы, замечаем, что 

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

но

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

Значит, функция \(  \large f_4 \) также не является монотонной.

Используя полученные выше данные, составим таблицу Поста:



\( \begin{array}{|c|c|}
\hline
 &  P_0 &  P_1 & S & L & M  \\
\hline
f_1 &  - &  + & - & -& -  \\
\hline
f_2 & + & - & - & - & - \\
\hline
f_3 & + & + & - & - & -  \\
\hline
f_4 & - & + & - & - & - \\
\hline
\end{array}  \)




Согласно теореме Поста, системы \(  \large \{ f_1,f_2,f_3,f_4 \} \), \(  \large \{ f_1,f_2,f_3 \} \), \(  \large \{ f_1,f_2,f_4 \} \), \(  \large \{ f_2,f_3,f_4 \} \), \(  \large \{ f_1,f_2 \} \), \(  \large \{f_2 ,f_4 \} \) полны, поскольку в каждой из них есть функция, не сохраняющая нуль, есть функция, не сохраняющая единицу, есть функция, не являющаяся самодвойственной, есть нелинейная функция, есть немонотонная функция. Системы \(  \large \{f_1 ,f_3,f_4 \} \), \(  \large \{ f_1,f_3 \} \), \(  \large \{ f_1,f_4 \} \), \(  \large \{ f_2,f_3 \} \), \(  \large \{ f_3,f_4 \} \), \(  \large \{ f_1 \} \), \(  \large \{ f_2 \} \), \(  \large \{ f_3 \} \), \(  \large \{f_4 \} \), в силу той же теоремы, не являются полными. Но являются ли перечисленные выше полные системы базисами? Будем рассуждать, используя определение базиса булевых функций. Системы \(  \large \{ f_1,f_2 \} \), \(  \large \{f_2 ,f_4 \} \) есть базисы, поскольку после удаления из них любой функции они превращаются в систему из одной функции, а все такие системы, как сказано выше, не полны. Удаляя из системы \(  \large \{ f_1,f_2,f_3 \} \) функцию \(  \large f_3 \) получаем полную систему, удаляя из системы \(  \large \{ f_1,f_2,f_4 \} \) функцию \(  \large f_1 \) получаем полную систему, удаляя из системы \(  \large \{ f_2,f_3,f_4 \} \) функцию \(  \large f_3 \) получаем полную систему. Следовательно, системы \(  \large \{ f_1,f_2,f_3 \} \), \(  \large \{ f_1,f_2,f_4 \} \), \(  \large \{ f_2,f_3,f_4 \} \) не являются базисами. Система \(  \large \{f_1, f_2,f_3,f_4 \} \) не базис, так как, например, удаление из неё функции \(  \large f_4 \) приводит к полной системе.

Итак, базисами являются только две системы: \(  \large \{ f_1,f_2 \} \) и \(  \large \{f_2 ,f_4 \} \).
 
Сказали спасибо: programmizd, dota2