Контрольные вопросы
1. Поясните термин “логическое высказывание”.
2. Какие логические операции вы знаете?
3. Назовите порядок выполнения логических операций в составном логическом высказывании.
4. Что называется логической формулой?
5. Каким образом задается логическая формула?
6. Как устанавливается равенство двух логических формул?
7. Как доказывается истинность логических формул, тождеств, законов?
8. Что такое булева функция?
9. Запишите все булевы функции «двух переменных».
10. Определите булевы функции «штрих Шеффера» и «стрелка Пирса».
11. Что такое функция отрицания импликации?
12. Приведите основные логические тождества и законы.
13. В чем заключается закон Де Моргана?
14. Каким образом доказывается справедливость основных логических законов и тождеств?
Задания для самостоятельной работы
1. Определить значения следующих составных высказываний:
а)
((x
) 
y)
(x
) z,
если х
= 0; y
= 1; z
= 1.
б) y ( z x y (x z)), если х = 0; y = 1; z = 0.
в) x z (x z y z) y , если х = 0; y = 0; z = 1.
г) ( y z) ( x z) x z, если х = 1; y = 0; z = 1.
д) y( y x z) (x ( z), если х = 1; y = 1; z = 1.
е) ((x z) ( z y z)) (x y ), если х = 1; y = 1; z = 1.
ж) ((x ) (x z)) (( z) (x y y)), если х = 1; y = 1; z = 0.
2. Для составных логических высказываний, заданных в пункте 1, определить набор значений логических переменных x, y, z, при котором значение составного высказывания было бы: а) ложно; б) истинно.
Ответ записать в виде таблицы истинности.
3. Используя таблицы истинности, доказать справедливость следующих тождеств:
а) x (y z) = (x y) (x z);
б) x (y z) = (x y) (x z);
в) x (x z) = x;
г) x (x y) = x;
д) (x y) (x ) = x;
е) (x y) (x ) = x;
ж) x y = y;
з) x y = ;
и) (x y) (y x) = (x y);
к) y = x = x y;
л)
x
y
=
;
м)
x y
=
;
н)
=
;
о)
=
.
3. Используя законы и тождества алгебры логики, доказать или опровергнуть справедливость следующих тождеств:
а) y = y;
б)
= x
y;
в)
= x y;
г)
= 0;
д)
=
.
Логика - это искусство рассуждений, наука о законах и формах мышления. Основная цель применения в логике символики - это свести операции с логическими заключениями к формальным действиям над символами. При этом исходные положения записываются формулами, которые преобразуются по определенным законам, а полученные результаты истолковываются в определенных понятиях.
Глава 13. Нормальные формы булевых функций
Логика – это искусство приходить к непредсказуемому выводу.
С. Джонсон
Нормальные формы булевых функций, дизъюнктивная и конъюнктивная нормальные формы, совершенная нормальная форма, способы перехода от нормальных к совершенным нормальным формам, алгебра Жегалкина, функциональная полнота булевых функций
ЦЕЛИ
Освоив эту главу, учащиеся должны знать и уметь:
основные способы перехода от нормальных к совершенным нормальным формам;
основные операции алгебры Жегалкина;
строить нормальные формы булевых функций;
определять функционально полные системы булевых функций.