Проверить двумя способами эквивалентность формул:
• составлением таблиц истинности;
• с помощью эквивалентных преобразований.
2. С помощью эквивалентных преобразований привести формулы к ДНФ, КНФ, СДНФ, СКНФ.
3. Построить многочлен Жегалкина.
4. Упростить функции алгебры логики, используя методы минимизации.
5. Проверить, является ли полной данная система функций. Образует ли она базис?6. Составить контактную схему для формул.
Ответ
1) формулы и не являются эквивалентными;
2) :
ДНФ: ;
КНФ: ;
CДНФ: ;
CКНФ: ;
:
ДНФ: ;
КНФ: ;
CДНФ: ;
CКНФ: ;
3) многочлены Жегалкина:
, ;
4) МДНФ: , ;
5) система функций является полной; она не образует базис;
6) контактные схемы – на рис.1 и рис.2.
Решение
А) Используя определения булевых операций и правила приоритета, составим таблицу истинности заданных формул:
х1 x2 x3
0 0 0 1 0 0 0 1 1 0 0
0 0 1 0 0 0 0 1 1 1 1
0 1 0 1 1 1 0 0 1 0 0
0 1 1 0 0 0 0 0 0 1 1
1 0 0 1 0 1 0 1 0 1 1
1 0 1 0 0 1 1 1 0 1 1
1 1 0 1 1 1 0 0 1 1 1
1 1 1 0 0 1 1 1 0 1 1
х y z
0 0 0 1 1 0 1 1 0 1
0 0 1 0 1 0 1 1 0 1
0 1 0 0 1 0 1 1 0 1
0 1 1 0 1 0 1 1 0 1
1 0 0 1 1 0 0 0 1 1
1 0 1 0 0 1 0 1 0 0
1 1 0 0 0 1 1 0 0 0
1 1 1 0 0 1 1 1 0 0
Как видим из таблицы истинности, формулы и принимают равные значения не на всех одинаковых наборах переменных, поэтому они не являются эквивалентными.
б) Выпишем основные логические законы:
Закон двойного отрицания:
.
Идемпотентность:
, .
Коммутативность:
, .
Ассоциативность:
, .
Дистрибутивность:
, .
Законы де Моргана:
, , , .
Формулы с константами:
,, ,
, , .
Дополнительные равносильности:
,
,
,
,
,
,
,
,
, (законы склеивания),
(законы поглощения),
(закон обобщенного склеивания),
, (законы Блейка-Порецкого).
Используя вышеуказанные тождества, преобразуем первую формулу (для упрощения знак конъюнкции опускаем, а отрицание показываем чертой сверху):
Преобразуем вторую формулу:
Если в первой формуле положить x1=x, x2=y, x3=z, то получим
.
Очевидно, что формулы и не тождественно равны, поэтому формулы и не являются эквивалентными.
2) Рассмотрим первую формулу:
.
При преобразовании первой формулы в пункте 1) мы получили ее ДНФ (дизъюнктивную нормальную форму – дизъюнкцию конъюнктивных одночленов):
.
Эта же форма одновременно является и ее КНФ (конъюнктивной нормальной формой – конъюнкцией дизъюнктивных одночленов).
Используя законы склеивания и поглощения, перейдем от ДНФ к СДНФ – совершенной дизъюнктивной нормальной форме:
Используя законы склеивания и поглощения, перейдем от КНФ к СКНФ – совершенной конъюнктивной нормальной форме:
.
Рассмотрим вторую формулу:
.
При преобразовании второй формулы в пункте 1) мы получили ее ДНФ:
.
Перейдем от ДНФ к КНФ:
Перейдем от ДНФ к СДНФ:
Перейдем от КНФ к СКНФ:
3) Алгоритм построения полинома (многочлена) Жегалкина логической формулы состоит из следующих шагов:
1)построить формулу с использованием связок или построить СДНФ функции;
2)заменить всюду на
. Если построена СДНФ, заменить в ней все операции на операции , т.к. для ортогональных элементарных конъюнкций имеет место соотношение , если
3)раскрыть скобки, пользуясь дистрибутивным законом и привести подобные члены, используя правило алгебры Жегалкина .
Построим полином Жегалкина для первой формулы, используя ее СДНФ:
Построим полином Жегалкина для второй формулы:
4) Минимизируем функции в базисе СДНФ, т.е. найдем МДНФ. Составим диаграмму Вейча (Карно), записав единицы в клетки диаграммы, которые соответствуют конституентам единицы, входящим в данную функцию, а в остальных клетках записываем нули (или можно и не писать их, оставив клетки пустыми).
Рассмотрим СДНФ первой функции:
Покажем вначале на диаграмме Вейча для функции трех переменных наборы.
х2
х1 111 110 100 101
011 010 000 001
х3 х3
Для нашей функции
х2
х1 1 1 1 1
1
1
х3 х3
Сама минимизация производится по следующим правилам:
1
Задать вопрос
на новый заказ в Автор24.
