Математика. Раздел 1. Дискретная математика. Тетрадь 1.2. Казанцев Э.Ф. - 36 стр.

UptoLike

ВУЗ: 

МУМ | Москва

Составители: 

Рубрика: 

Уп ро стим дан ную фор му лу пу тем то ж де ст вен ных пре об ра зо ва -
ний:
(Y&Z) Ú (X&
Y
&Z) Ú (
X
&
Y
&Z) = (Y&Z) Ú (
Y
&Z) & (XÚ
X
) =
Z&(YÚ
Y
) = Z
Та ким об ра зом, ис ход ной элек три че ской схе ме со от вет ст ву ет эк -
ви ва лент ная схе ма, изо бра жен ная на рисунок 1.5.8.
1.5.6 То ж де ст вен но-ис тин ные фор му лы (тав то ло гии)
Пусть фор му ла A за ви сит от спи ска пе ре мен ных (X
i
, ...,X
i
).
1) Фор му ла A на зы ва ет ся тав то ло ги ей (или то ж де ст вен но-ис тин -
ной), ес ли на лю бых оцен ках спи ска пе ре мен ных (X
i
, ..., X
i
) она при ни -
ма ет зна че ние И.
2) Фор му ла A на зы ва ет ся вы пол ни мой, ес ли на не ко то рой оцен ке
спи ска пе ре мен ных (X
i
, ..., X
i
) она при ни ма ет зна че ние И.
3) Фор му ла A на зы ва ет ся то ж де ст вен но-лож ной, ес ли на лю бых
оцен ках спи ска пе ре мен ных (X
i
, ..., X
i
) она при ни ма ет зна че ние Л.
4) Фор му ла A на зы ва ет ся оп ро вер жи мой, ес ли на не ко то рой оцен -
ке спи ска пе ре мен ных (X
i
, ..., X
i
) она при ни ма ет зна че ние Л.
Как и в оп ре де ле нии рав но силь но сти, здесь не име ет зна че ния,
бу дут ли в спи ске фик тив ные переменные.
Оче вид ные след ст вия дан ных оп ре де ле ний:
5) A — тав то ло гия то гда и толь ко то гда, ко гда A не яв ля ет ся оп ро -
вер жи мой.
6) A — то ж де ст вен но-лож на то гда и толь ко то гда, ко гда A не яв ля -
ет ся вы пол ни мой.
7) A — тав то ло гия то гда и толь ко то гда, ко гда A — то ж де ст вен но-
лож на.
8) A — то ж де ст вен но-лож на то гда и толь ко то гда, ко гда A — тав то -
ло гия.
36
Рис. 1.5.8
       Упростим данную формулу путем тождественных преобразова-
ний:
     (Y&Z) Ú (X&Y &Z) Ú (X &Y &Z) = (Y&Z) Ú (Y &Z) & (XÚX ) =
Z&(YÚY ) = Z
     Таким образом, исходной электрической схеме соответствует эк-
вивалентная схема, изображенная на рисунок 1.5.8.


                               Рис. 1.5.8


       1.5.6 Тождественно-истинные формулы (тавтологии)

      Пусть формула A зависит от списка переменных (Xi, ...,Xi).
      1) Формула A называется тавтологией (или тождественно-истин-
ной), если на любых оценках списка переменных (Xi, ..., Xi) она прини-
мает значение И.

     2) Формула A называется выполнимой, если на некоторой оценке
списка переменных (Xi, ..., Xi) она принимает значение И.

     3) Формула A называется тождественно-ложной, если на любых
оценках списка переменных (Xi, ..., Xi) она принимает значение Л.

      4) Формула A называется опровержимой, если на некоторой оцен-
ке списка переменных (Xi, ..., Xi) она принимает значение Л.
      Как и в определении равносильности, здесь не имеет значения,
будут ли в списке фиктивные переменные.
      Очевидные следствия данных определений:

     5) A — тавтология тогда и только тогда, когда A не является опро-
вержимой.

      6) A — тождественно-ложна тогда и только тогда, когда A не явля-
ется выполнимой.

     7) A — тавтология тогда и только тогда, когда A — тождественно-
ложна.

     8) A — тождественно-ложна тогда и только тогда, когда A — тавто-
логия.
36

Страницы