Контрольная работа № 3.
Задание 1.
Определить, является ли справедливой приведённая формула алгебры высказываний, не прибегая к составлению таблицы истинности, а используя только свойства соответствующих операций:
где А, В, С, D, Е – простые высказывания.
Решение:
По правилу Моргана получаем
Нет полного совпадения с правой частью приведённой формулы. Значит, она не является справедливой.
Задание 2.
Для указанной функции трёх переменных: f (х1, х2, х3) – принимает единичные значения на наборах № 0, 1, 3, 6, 7.
- составить таблицу истинности;
- определить, к каким классам булевых функций она относится;
- записать совершенные ДНФ и КНФ;
- найти минимальную ДНФ;
- для полученной минимальной ДНФ построить логическую схему в базисах:
а) (дизъюнкция, отрицание);
б) (конъюнкция, отрицание).
Решение:
Составим таблицу истинности для функции f и двойственной функции f* (х1, х2, х3) =
№
Х1
Х2
Х3
f
f*
0
0
0
0
1
0
1
0
0
1
1
0
2
0
1
0
0
1
3
1
0
0
1
1
4
0
1
1
0
0
5
1
0
1
0
1
6
1
1
0
1
0
7
1
1
1
1
0
Функция f не сохраняет 0, сохраняет 1, не является самодвойственной, т.к. Функция f не является монотонной, т.к. на нулевом наборе она равна 1 и равна 0 на наборах с номерами 2, 4 и 5, что противоречит определению монотонности. Проверяем свойство линейности.
а0 + а1х1 + а2х2 + а3х3 = f.
Проходя по таблице истинности сверху вниз, получаем а0 = 1,
а0 + а2 = 0, откуда а2 = -1, что невозможно в определении линейности.
Способ перехода от табличного задания логической функции к СДНФ: для каждого набора значений переменных х1, х2, х3, на котjром функция
f (х1, х2, х3) равна 1, выписываются конъюнкции всех переменных: над переменными, которые на этом наборе равны 0, ставятся отрицания; все такие конъюнкции соединяются знаками дизъюнкции. В результате СДНФ имеет вид:
f.
Правило получения СКНФ функции по её таблице истинности: СКНФ строится из элементарных дизъюнкций, соответствующих обратным наборам, на которых функция равна нулю. В результате СКНФ имеет вид:
Минимальную ДНФ найдём методом Блейка-Порецкого. Метод заключается в попарном склеивании всех элементарных конъюнкций СДНФ между собой, а также полученных в процессе склеивания элементарных конъюнкций меньшего числа переменных и затем – поглощение конъюнкциями меньшего числа переменных. Пронумеруем элементарные конъюнкции СДНФ и под результатом склеивания проставим номера склеиваемых конъюнкций.
Проведём все возможные попарные склеивания:
Теперь
Затем выполняем поглощения
Получаем
Этой минимальной ДНФ соответствует логическая схема в базисе
По первому закону де Моргана
по второму закону
а) Поэтому в базисе получается логическая схема:
;
б) В базисе будет .
Задание 3.
Является ли полной система булевых функций, состоящая из импликации и отрицания? Доказать полноту (или неполноту) приведённой системы булевых функций, состоящей из импликации и отрицания.
Решение:
Полнота системы булевых функций доказана в теореме 11.2, учебного пособия . В основе доказательства лежит
Теорема 10.5. Всякая булева функция может быть представлена в виде суперпозиции конъюнкции, дизъюнкции и отрицания, причём знак отрицания стоит только непосредственно около переменной и не стоит ни перед одной из внутренних скобок.
Конъюнкцию можно выразить через дизъюнкцию и отрицание. Так утверждает теорема 9.5. а) : .
Остаётся дизъюнкцию выразить через импликацию: .
Так утверждает теорема 9.5. в).
Теперь остаётся напомнить основное определение 11.1. Система