Равносильные формулы. Свойства

Два высказывания называются равносильными, если равны их истинностные функции, рассматриваемые как функции от всех значений переменных, т.е. на каждом наборе значений оба высказывания принимают одинаковые значения.

Основные равносильности:

1. Коммутативность.

а) Равносильные формулы. Свойства - student2.ru (для конъюнкции);

б) Равносильные формулы. Свойства - student2.ru (для дизъюнкции).

2. Ассоциативность.

а) Равносильные формулы. Свойства - student2.ru (для конъюнкции);

б) Равносильные формулы. Свойства - student2.ru (для дизъюнкции).

3. Дистрибутивность.

а) Равносильные формулы. Свойства - student2.ru (для конъюнкции относительно дизъюнкции);

б) Равносильные формулы. Свойства - student2.ru (для дизъюнкции относительно конъюнкции).

4. Закон де Моргана.

а) Равносильные формулы. Свойства - student2.ru Равносильные формулы. Свойства - student2.ru Равносильные формулы. Свойства - student2.ru (отрицание конъюнкции есть дизъюнкция отрицаний);

б) Равносильные формулы. Свойства - student2.ru Равносильные формулы. Свойства - student2.ru Равносильные формулы. Свойства - student2.ru (отрицание дизъюнкции есть конъюнкция отрицаний).

5. Идемпотентность.

а) Равносильные формулы. Свойства - student2.ru (для конъюнкции);

б) Равносильные формулы. Свойства - student2.ru (для дизъюнкции).

6. Поглощение.

Равносильные формулы. Свойства - student2.ru .

Равносильные формулы. Свойства - student2.ru Равносильные формулы. Свойства - student2.ru

7. Расщепление (склеивание).

а) Равносильные формулы. Свойства - student2.ru (1–ый закон расщепления);

б) Равносильные формулы. Свойства - student2.ru (2–ой закон расщепления).

8. Двойное отрицание.

┐┐х=х

9. Свойства констант.

а) Равносильные формулы. Свойства - student2.ru

б) Равносильные формулы. Свойства - student2.ru

в) Равносильные формулы. Свойства - student2.ru

г) Равносильные формулы. Свойства - student2.ru

д) Равносильные формулы. Свойства - student2.ru

е) Равносильные формулы. Свойства - student2.ru .

10. Закон противоречия.

Равносильные формулы. Свойства - student2.ru

11. Закон “исключенного третьего”.

Равносильные формулы. Свойства - student2.ru

Каждая из перечисленных равносильностей может быть доказана с помощью таблиц значений функций, составленных для выражений, стоящих слева и справа от символа “ Равносильные формулы. Свойства - student2.ru ”. Докажем, например, равносильность 4а. Для этого составим таблицу.

Таблица

х у Равносильные формулы. Свойства - student2.ru Равносильные формулы. Свойства - student2.ru Равносильные формулы. Свойства - student2.ru Равносильные формулы. Свойства - student2.ru Равносильные формулы. Свойства - student2.ru Ø

Из таблицы видно, что Равносильные формулы. Свойства - student2.ru º Равносильные формулы. Свойства - student2.ru Ø, что и требовалось доказать.

Прямая, обратная и противоположная теоремы

Рассмотрим четыре теоремы:

Равносильные формулы. Свойства - student2.ru , (1) Равносильные формулы. Свойства - student2.ru , (2) Равносильные формулы. Свойства - student2.ru , (3) Равносильные формулы. Свойства - student2.ru . (4)

Определение 1: Пара теорем, у которых условие одной является заключением второй, а условие второй является заключением первой, называются взаимно обратными друг другу.

Так, теоремы (1)и (2), а также (3) и (4)- взаимно обратные теоремы. При этом, если одну из них называют прямой теоремой, то вторая называется обратной.

Определение 2: Пара теорем, у которых условие и заключение одной являются отрицанием соответственно условия и заключения другой, называются взаимно противоположными.

Так, теоремы (1) и (3), а также (2) и (4) являются взаимно противоположными теоремами.

Например, для теоремы

“Если в четырехугольнике диагонали равны, то четырехугольник является прямоугольником ” (1) обратной является теорема

“Если четырехугольник является прямоугольником, то его диагонали равны” (2).

Для теоремы (1) противоположной является теорема

“Если в четырехугольнике диагонали не равны, то четырехугольник не является прямоугольником” (3),

а для теоремы (2) противоположной является теорема

“Если четырехугольник не является прямоугольником, то его диагонали не равны ” (4).

В рассмотренном примере теоремы (1) и (4) являются одновременно ложными, а теоремы (2) и (3) одновременно истинными. Контрпримером к теореме (1) является равнобочная трапеция.

Ясно, что прямая и обратная теоремы, вообще говоря, не равносильны, т. е. одна из них может быть истинной, а другая – ложной. Однако легко показать, что теоремы (1) и (4), а также (2) и (3) всегда равносильны.

Действительно:

Равносильные формулы. Свойства - student2.ru Из этих равносильностей следует, что, если доказана теорема (1), то доказана и теорема (4), а если доказана теорема (2), то доказана и теорема (3).

Наши рекомендации