Дискретная математика. Элементы теории задачи и упражнения. Часть 2. Булгакова И.Н - 9 стр.

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
55
Отметим, что все операции, кроме импликации, симметричны.
Из этих простых (элементарных ) высказываний строятся составные
( сложные ) высказывания.
Формулой алгебры логики высказываний называется всякое состав-
ное высказывание, которое получается комбинированием конечного числа
указанных выше основных операций (
,
,
&,
,
). Для любых формул
можно построить таблицу истинности.
Таблицей истинности формулы называется сводная таблица всех
значений входящих в нее высказываний и соответствующих значений са -
мой формулы. Таблица содержит
n
2
строк, где
n
число простых
высказываний.
Формула
U
называется тождественно истинной, или тавтологи -
ей (записывается
1
U
), если для всех наборов значений входящих в нее
переменных (высказываний) она принимает значение 1 («истинно»).
Формула
U
называется тождественно ложной, или противоречи-
ем (записывается
0
U
), если для всех наборов значений входящих в нее
переменных (высказываний) она принимает значение 0 («ложь» ).
Заметим, что отрицание любой тавтологии есть противоречие:
(
)
01 ≡≡ U
. Все остальные формулы называются выполнимыми.
Пример 1 . Следующие высказывания записать формулами. Соста-
вить для них таблицы истинности.
a) Если Джон умен , а Джим глуп, то Джон получает приз.
b) Джон получает приз в том и только том случае, если Джон умен
или если Джим глуп.
c) Если Джим глуп, и Джону не удается получить приз, то Джон не
умен .
Решение. Обозначим простые высказывания буквами:
A
Джон умен ;
B
Джим глуп;
C
Джон получает приз.
Тогда составные высказывания запишем в виде формул:
a)
(
)
CB&A
;
b)
(
)
BAC
;
c)
(
)
AC&B .