Дискретная математика. Элементы теории задачи и упражнения. Часть 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 → . 
                                           55
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
      Отметим, что все операции, кроме импликации, симметричны.
      Из этих простых (элементарных) высказываний строятся составные
(сложные) высказывания.
      Формулой алгебры логики высказываний называется всякое состав-
ное высказывание, которое получается комбинированием конечного числа
указанных выше основных операций ( ∨, &,→ , ↔ , � ). Для любых формул
можно построить таблицу истинности.
      Таблицей истинности формулы называется сводная таблица всех
значений входящих в нее высказываний и соответствующих значений са-
мой формулы. Таблица содержит 2 n строк, где n — число простых
высказываний.
      Формула U называется тождественно истинной, или тавтологи-
ей (записывается U ≡1 ), если для всех наборов значений входящих в нее
переменных (высказываний) она принимает значение 1 («истинно»).
      Формула U называется тождественно ложной, или противоречи-
ем (записывается U ≡0 ), если для всех наборов значений входящих в нее
переменных (высказываний) она принимает значение 0 («ложь»).
      Заметим, что отрицание любой тавтологии есть противоречие:
(      )
 U ≡1 ≡0 . Все остальные формулы называются выполнимыми.

      Пример 1 . Следующие высказывания записать формулами. Соста-
вить для них таблицы истинности.
   a) Если Джон умен, а Джим глуп, то Джон получает приз.
   b) Джон получает приз в том и только том случае, если Джон умен
   или если Джим глуп.
   c) Если Джим глуп, и Джону не удается получить приз, то Джон не
   умен.
      Решение. Обозначим простые высказывания буквами:
    A — Джон умен;
    B — Джим глуп;
   C — Джон получает приз.
      Тогда составные высказывания запишем в виде формул:
   a) ( A & B ) → C ;
   b) C ↔ ( A ∨ B );
   c) (B & C ) → A .

Страницы