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

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

Онлайн Admin

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


В алгебре высказываний рассматриваются логические операции - отрицание, конъюнкция, дизъюнкция (в том числе строгая), импликация и эквиваленция. При построении данной математической теории важно истинностное значение, а не содержание простых и составных высказываний, формул, полученных с помощью указанных выше операций. Мы уже обозначали истину единицей, а ложь нулём, отвлекаясь по сути от понятий "истина" и "ложь" и оперируя лишь нулями и единицами. Учитывая, что в классической логике всего два истинностных значения, логические связки можно рассматривать как функции, определённые на некотором двухэлементном множестве и принимающие значение в том же множестве. В качестве такого множества удобно выбрать неупорядоченную пару \(  \large \{ 0,1 \}  \). Эти функции называются булевыми в честь английского математика и логика Джорджа Буля.

***

Определение 10.1. Булевой функцией от \(  \large n  \) переменных называется отображение

\(  \large f \colon \{ 0,1 \}^n \to \{ 0,1 \}  \).

Замечание 10.1. Здесь \(  \large \{ 0,1 \}^n  \) - декартова \(  \large n  \)-ая степень множества \(  \large \{ 0,1 \}  \).

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

Замечание 10.3. Константы \(  \large 0  \), \(  \large 1  \) и переменные \(  \large x_1,x_2, \ldots, x_n  \) также называются булевыми.

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

Замечание 10.5. Из определения ясно, что булевы функции от \(  \large n  \) переменных являются \(  \large n  \)-арными операциями.

Замечание 10.6. Поскольку булевы функции от одной и двух переменных есть унарные и бинарные операции соответственно, для них применяются обозначения, характерные для этих операций.
 
Сказали спасибо: Alexey

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 10. Основные понятия теории булевых функций
« Ответ #1 : Декабрь 10, 2017, 08:52:54 pm »
Как и операции алгебры высказываний, булевы функции можно определить табличным способом. Применительно к функциям алгебры логики говорят о таблице значений, а не о таблице истинности, поскольку в данном случае полностью абстрагируются от понятий истины и лжи. Отрицание, конъюнкция, дизъюнкция, строгая дизъюнкция, импликация и эквиваленция определяются и обозначаются точно так же, как и соответствующие операции алгебры высказываний. Конъюнкцию иногда называют логическим умножением, а дизъюнкцию - логическим сложением (хотя последнее название представляется не вполне удачным). Строгая дизъюнкция называется суммой Жегалкина или сложением по модулю два. Новыми в теории булевых функций являются две функции - стрелка Пирса и штрих Шеффера. Сумму Жегалкина называют также функцией Жегалкина, стрелку Пирса - функцией Пирса, а штрих Шеффера - функцией Шеффера. Определим новые булевы функции с помощью таблиц значений.

***

Определение 10.2. Стрелкой Пирса называется булева функция, заданная следующей таблицей значений:

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

Замечание 10.7. Итак, стрелка Пирса равна единице тогда и только тогда, когда обе её переменные равны нулю.

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

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

Замечание 10.8. Согласно определению, штрих Шеффера равен нулю, если и только если обе его переменные равны единице.

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

Замечание 10.10. Значения булевой функции, соответствующие наборам значений переменных, расположенных в порядке возрастания двоичных чисел, образуют двоичный набор, который, как и таблица значений, однозначно определяет булеву функцию. Этот набор для булевой функции от \(  \large n  \) переменных представляет собой кортеж длины \(  \large 2^n  \), поскольку таблица значений для такой функции имеет ровно \(  \large 2^n  \) строк. Двоичный набор, определяющий функцию алгебры логики, содержится в последнем столбце её таблицы значений. Такое представление функции алгебры логики ещё называется векторным. Если, например, двоичный вектор \(  \large (01010100)  \) определяет булеву функцию \(  \large f  \), то используется следующая символическая запись:

\(  \large f=(01010100)  \).

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

\(  \large x'=(10)  \);

\(  \large xy=(0001)  \);

\(  \large x \vee y= (0111)  \);

\(  \large x \oplus y= (0110)  \);

\(  \large  x \to y= (1101)  \);

\(  \large x \leftrightarrow y= (1001)  \);

\(  \large  x \downarrow y=(1000)  \);

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

Замечание 10.12. Если булева функция представлена в виде формулы (например, \(  \large x \vee (y \to z')  \)), то говорят, что она задана аналитически.
 
Сказали спасибо: Alexey

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 10. Основные понятия теории булевых функций
« Ответ #2 : Декабрь 10, 2017, 10:08:39 pm »
Задача 10.1. Зная аналитическое представление булевой функции, найти определяющий её двоичный набор:

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

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

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

Таблица значений составляется точно так же, как и таблица истинности. Сначала находим значения \(  \large x'  \) и \(  \large y'  \), потом - значения \(  \large x' \downarrow y'  \), наконец, находим значения \(  \large (x' \downarrow y') \to z  \). Итак,

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

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 10. Основные понятия теории булевых функций
« Ответ #3 : Декабрь 10, 2017, 10:49:48 pm »
Булевы функции, как и любые другие отображения, являются бинарными отношениями, значит, они равны тогда и только тогда, когда они равны как множества. Однако применительно к булевым функциям есть одна особенность, связанная с равенством функций. С понятием равенства в теории булевых функций тесно связаны понятия "существенная переменная" и "фиктивная переменная".

***

Пусть \(  \large f(x_1,x_2, \ldots, x_n)  \) - некоторая булева функция.

Определение 10.4. Переменная \(  \large x_i  \), где \(  \large 1 \le i \le n  \), называется существенной для функции \(  \large f  \), если существуют такие значения

\(  \large a_1, \ldots, a_{i-1}, a_{i+1}, \ldots, a_n  \)

переменных

\(  \large x_1, \ldots, x_{i-1}, x_{i+1}, \ldots, x_n  \),

что

\(  \large  f(a_1, \ldots, a_{i-1},0, a_{i+1}, \ldots, a_n) \not = f(a_1, \ldots, a_{i-1}, 1, a_{i+1}, \ldots, a_n)   \).

Определение 10.5. Переменная \(  \large x_i  \), где \(  \large 1 \le i \le n  \), называется несущественной для функции \(  \large f  \), если выполняется равенство

\(  \large  f(a_1, \ldots, a_{i-1},0, a_{i+1}, \ldots, a_n)  = f(a_1, \ldots, a_{i-1}, 1, a_{i+1}, \ldots, a_n)   \),

какими бы ни были значения

\(  \large a_1, \ldots, a_{i-1}, a_{i+1}, \ldots, a_n  \)

переменных

\(  \large x_1, \ldots, x_{i-1}, x_{i+1}, \ldots, x_n  \).

Замечание 10.13. Несущественные переменные булевой функции называются также фиктивными.

Замечание 10.14. Булевы функции рассматриваются с точностью до несущественных переменных: функции \(  \large f  \) и \(  \large g  \) считаются равными, если одна из этих функций получается из другой добавлением или изъятием фиктивных переменных. Тождество булевых функций и тождественность их преобразований понимается в этом смысле.

Замечание 10.15. Булевы функции, принимающие значение \(  \large 0  \) и \(  \large 1  \) на любых наборах значений переменных, будем называть тождественным нулём  (или просто нулём) и тождественной единицей (или просто единицей) вне зависимости от количества переменных. Их также именуют булевыми константами или просто константами.

Замечание 10.16. Булевы константы можно считать функциями, не имеющими ни одной существенной переменной.

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

Замечание 10.18. Константы \(  \large 0  \) и \(  \large 1  \) можно считать нульарными операциями.
 

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 10. Основные понятия теории булевых функций
« Ответ #4 : Декабрь 10, 2017, 11:55:46 pm »
Задача 10.2. Найти существенные и фиктивные переменные булевой функции:

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

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

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

Используя таблицу значений, замечаем, что

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

Следовательно, переменная \(  \large x  \) существенна для функции \(  \large x' \to (x( y \downarrow z))  \). Переменная \(  \large y  \) не является существенной для этой функции, поскольку

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

какими бы ни были значения переменных \(  \large x  \) и \(  \large z  \). Поскольку для любых значений переменных \(  \large x  \) и \(  \large y  \) выполняется равенство

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

переменная \(  \large z  \) также не является существенной для рассматриваемой булевой функции.
 

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 10. Основные понятия теории булевых функций
« Ответ #5 : Декабрь 10, 2017, 11:57:19 pm »
Булевы функции обладают теми же свойствами, что и соответствующие операции алгебры высказываний. Эти свойства носят те же самые названия и доказываются с помощью таблиц значений. По сравнению со свойствами операций алгебры высказываний, новыми являются лишь свойства, связанные со стрелкой Пирса и штрихом Пирса. 

Основные свойства булевых функций

1) \( \large x''=x \);

2) \( \large x \cdot x=x \);

3) \( \large x \vee x=x \);

4) \( \large (x  y)'=x' \vee y' \);

5) \( \large (x \vee y)'=x'y' \);

6) \( \large x  (x \vee y)=x \);

7) \( \large x \vee (xy)=x \);

8) \(  \large xy=yx \);

9) \( \large x \vee y=y \vee x \);

10) \( \large (xy)z=x(yz) \);

11) \( \large (x \vee y) \vee z=x \vee (y \vee z) \);

12) \( \large x \vee (yz)=(x \vee y)(x \vee z) \);

13) \( \large x(y \vee z)=(x  y) \vee (x  z) \);

14) \( \large x \mid y= (xy)' \);

15) \( \large x \downarrow y= (x \vee y)' \);

16) \( \large x \oplus y= (x \leftrightarrow y)' \);

17) \( \large x \to y= x' \vee y \);

18) \( \large x \leftrightarrow y= (x \to y)(y \to x) \);

19) \( \large x \vee x'=1 \);

20)  \( \large x \cdot x'=0 \);

21) \( \large x \vee 1=1 \);

22) \( \large x \vee 0=x \);

23) \( \large x \cdot  1=x \);

24) \( \large x \cdot  0=0 \);

25) \( \large x \oplus y=y \oplus x \);

26) \( \large (x \oplus y) \oplus z=x \oplus (y \oplus z) \);

27) \( \large (x \oplus y)z=xz \oplus yz \);

28) \( \large x \oplus 0= x \);

29) \( \large x \oplus x=0 \);

30) \( \large x'=x \oplus 1 \);

31) \( \large x \vee y=xy \oplus x \oplus y \).
 
Сказали спасибо: Fedor1995, total2018

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 10. Основные понятия теории булевых функций
« Ответ #6 : Декабрь 11, 2017, 12:04:31 am »
Фрагмент теории булевых функций, посвящённый совершенным нормальным формам, идентичен соответствующему фрагменту в алгебре высказываний, если заменить понятие "формула алгебры высказываний" на понятие "булева функция", понятие "пропозициональная переменная" - на понятие "булева переменная", понятия "истина" и "ложь" - на единицу и нуль соответственно. Всякую булеву функцию можно представить как композицию дизъюнкции, конъюнкции и отрицания. Следовательно, любую булеву функцию можно представить в КНФ и ДНФ. Любую булеву функцию, не являющуюся тождественной единицей (тождественным нулём), можно представить в СКНФ (СДНФ), причём такое представление единственно. Совершенные нормальные формы функций алгебры логики можно находить как табличным способом, так и с помощью тождественных преобразований. При записи ДНФ будем опускать лишние скобки, считая, что конъюнкция имеет приоритет над дизъюнкцией. Например, вместо

\(  \large (xyz') \vee (x'y'z) \vee (xy'z)   \)


будем писать

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

Рассмотрим задачу на отыскание ДНФ, КНФ, СДНФ и СКНФ функции алгебры логики.

***

Задача 10.3. Дана булева функция:

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

Найти ДНФ, КНФ, СДНФ, СКНФ методом тождественных преобразований. Найти СДНФ, СКНФ табличным способом (сравнить с СДНФ, СКНФ, полученными с помощью тождественных преобразований).

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

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

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

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

Выразим штрих Шеффера через конъюнкцию и отрицание:

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

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

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

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

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

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

\(  \large x' \vee (y \cdot (x \oplus z))=x' \vee (y(x \leftrightarrow z)')  \).


Выразим эквиваленцию через импликацию и конъюнкцию:

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

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

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

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

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

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

\(  \large x' \vee (y((xz') \vee (zx'))=x' \vee xyz' \vee x'yz  \).

Применим второй закон поглощения:

\(  \large x' \vee xyz' \vee x'yz =x' \vee xyz'  \).

Получили дизъюнктивную нормальную форму функции:

\(  \large x' \vee xyz'  \).

Используя найденную выше ДНФ, найдём СДНФ с помощью тождественных преобразований. Так как \(  \large x \cdot 1 =x  \), то

\(  \large x' \vee xyz'=(x' \cdot 1 \cdot 1) \vee xyz'  \).

Применим закон исключённого третьего:

\(  \large (x' \cdot 1 \cdot 1) \vee xyz'=(x' \cdot (y \vee y') \cdot (z \vee z')) \vee xyz'  \).


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

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

Получили совершенную дизъюнктивную нормальную форму функции.

Найдём конъюнктивную нормальную форму, зная, что

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

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

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

Используем закон исключённого третьего и одно из правил действий с константой \(  \large 1  \):

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

Получили КНФ функции алгебры логики.

Зная КНФ, будем искать СКНФ, используя тождественные преобразования. Добавим к каждой дизъюнкции по нулю, используя тождество \(  \large x \vee 0 =x  \). Имеем:

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

Применим закон противоречия:

\(  \large (x' \vee y \vee 0)(x' \vee 0 \vee z') =(x' \vee y \vee (zz'))(x' \vee (yy') \vee z')   \).

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

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

Получили совершенную конъюнктивную нормальную форму функции.

Используя определения булевых функций, составим таблицу значений для функции \(  \large x \mid (( y \downarrow y)' \mid (x \oplus z)) \) и найдём СДНФ, а также СКНФ.

\( \begin{array}{|c|c|}
\hline
x &  y &  z &  y \downarrow y & (y \downarrow y)' & x \oplus z & (y \downarrow y)' \mid (x \oplus z) &  x \mid ((y \downarrow y)' \mid (x \oplus z)) \\
\hline
0 &  0 &  0 & 1 & 0 & 0 & 1 & 1  \\
\hline
0 & 0 & 1 & 1  & 0 & 1 & 1 & 1\\
\hline
0 & 1 & 0 & 0& 1 & 0 & 1 & 1 \\
\hline
0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 \\
\hline
1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\
\hline
1 & 0 & 1 & 1 & 0 & 0 & 1 & 0  \\
\hline
1 & 1 & 0 &0 & 1 & 1 & 0 & 1   \\
\hline
1 & 1 & 1 & 0& 1 & 0 & 1 & 0 \\
\hline
\end{array}  \)

Используем алгоритм нахождения СДНФ формулы алгебры логики. Выберем все те наборы значений переменных, на которых функция принимает значение \(  \large 1  \):

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

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

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

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

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

Для каждого такого набора выпишем элементарную конъюнкцию, принимающую значение \(  \large 1  \) на этом наборе и только на нём:

\(  \large x'y'z'  \);

\(  \large x'y'z  \);

\(  \large x'yz'  \);

\(  \large x'yz  \);

\(  \large xyz'   \).

Полученные элементарные конъюнкции соединим знаками дизъюнкции и получим СДНФ:

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

Применяем алгоритм поиска СКНФ формулы алгебры логики. Выберем все те наборы значений переменных, на которых функция принимает значение, равное нулю:

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

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

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

Для каждого такого набора выпишем элементарную дизъюнкцию, которая принимает значение \(  \large o  \) на этом наборе и только на нём:

\(  \large x' \vee y \vee z  \);

\(  \large x' \vee y \vee z'  \);

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

Объединим эти дизъюнкции в конъюнкцию и получим СКНФ:

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

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

Онлайн Admin

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

***

Задача 10.4. Доказать или опровергнуть тождество, используя основные тождества теории булевых функций.

\(  \large (x \leftrightarrow y) \oplus 1= ((x \downarrow x) \mid (y \mid y)) (x \mid y) \).

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

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

Вспомним, что конъюнкция и дизъюнкция идемпотентны:

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

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

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

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

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

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

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

Раскрываем скобки, а затем применяем закон противоречия и правила действий с нулём:

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

Переходим к эквиваленции:

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

Наконец, используем тождество \(  \large (x \to y)(y \to x) =x \leftrightarrow y  \):

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

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

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 10. Основные понятия теории булевых функций
« Ответ #8 : Декабрь 12, 2017, 01:16:25 pm »
Задача 10.5. Проверить, является ли импликация самодистрибутивной:

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

Решение. Покажем, что тождество выполняется. Для этого преобразуем его правую часть тождественным образом.

Выразим внутренние импликации через логическое сложение и отрицание:

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

Представим внешнюю импликацию в виде композиции логического сложения и отрицания, а затем применим один из законов де Моргана и закон двойного отрицания:

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

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

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

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

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

Перейдём от логического сложения и отрицания к импликации:

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

Итак, импликация самодистрибутивна (дистрибутивна относительно самой себя).
 

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 10. Основные понятия теории булевых функций
« Ответ #9 : Декабрь 14, 2017, 04:52:37 pm »
Задача 10.6. Упростить булеву функцию:

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

Решение. Выразим штрих Шеффера через конъюнкцию и отрицание, а стрелку Пирса - через дизъюнкцию и отрицание:

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

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

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

Применяем второй закон де Моргана и закон двойного отрицания:

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

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

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

Осталось воспользоваться законом противоречия и правилом \(  \large x \vee 0 =x  \). Имеем:

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

Итак,

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

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 10. Основные понятия теории булевых функций
« Ответ #10 : Декабрь 17, 2017, 12:51:56 pm »
Задача 10.7. Доказать, что булева функция тождественно равна единице:

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

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

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

Значит, \(  \large y \mid y = y'  \). Аналогичным образом упростим функцию \(  \large y \downarrow y  \). Имеем:

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

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

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

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

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

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

\(  \large (x' \to 0) \to (x' \downarrow 0)   \).

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

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

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

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

Тогда

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

Итак, мы доказали, что функция есть тождественная единица.
 

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Задача 10.8. Доказать, что булева функция тождественно равна нулю:

\(  \large y(x \oplus z)((x \downarrow x) \mid y)(x \mid y)  \).

Решение. Поскольку \(  \large x \downarrow x=x'  \), то

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

Избавимся от функции Пирса:

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

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

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

Применим дистрибутивный закон:

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

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

\(  \large y(x \oplus z)(y' \vee (xx'))=yy'(x \oplus z)  \).

Повторяем то же самое:

\(  \large yy'(x \oplus z) =0  \).