Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л

Таблица 9.

X	Y	X Y
0	0	0
0	1	1
1	0	1
1	1	0

Пример 3.3. Представить логической формулой высказывание «Сегодня четверг или пятница». Высказывание - «сегодня четверг», высказывание - «сегодня пятница». Высказыванию «Сегодня четверг или пятница» соответствует формула .

3.4. Основные законы, определяющие свойства введенных логических операций.

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

Формула высказываний называется противоречием, неразрешимой или тождественно ложной, если при подстановке вместо переменных высказываний любых конкретных высказываний она превращается всегда в ложное высказывание.

Формула высказываний называется разрешимой (выполнимой), если может превращаться как в истинное, так и ложное высказывание.

Перечислим основные законы (тавтологии), определяющие свойства введенных логических операций:

1) Идемпотентность дизъюнкции и конъюнкции:

, .

2) Коммутативность дизъюнкции и конъюнкции:

, .

3) Ассоциативность дизъюнкции и конъюнкции:

, .

4) Дистрибутивность операций дизъюнкции и конъюнкции относительно друг друга:

, .

5) Двойное отрицание:

.

6) Закон Моргана:

, .

7) Склеивание:

, .

8) Поглощение:

, .

9) Действие с логическими константами 0 и 1:

, , , , .

10) Закон исключения третьего:

.

11) Тождество:

X↔X.

12) Отрицание противоречия:

.

13) Контрапозиция:

.

14) Цепное заключение:

.

15) Противоположность:

.

16) Модус поненс (ponens):

.

Сформулированные законы легко проверить с помощью таблицы истинности.

Докажем, что формула , соответствующая контрапозиции, является тавтологией. Составим соответствующую таблицу истинности.

Таблица 10.

Так как в последнем столбце стоят только единицы, то формула является тавтологией.

Если известно, что высказывания имеют одинаковые таблицы истинности, то такие высказывания являются равносильными (эквивалентными).

На практике для доказательства равносильности пользуются признаками равносильности:

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

2. Две формулы и равносильны тогда и только тогда, когда формула - тавтология.

Заметим, что при исследовании различных высказываний на эквивалентность ( равносильность) логическую связку ↔ можно заменить обычным знаком равенства =.

Полезным оказывается правило исключения логических символов и : для каждой формулы можно указать равносильную ей формулу, не содержащую логических символов и . Из следующей таблицы истинности видно, что X→Y эквивалентно .

Таблица 11.

X	Y	X→Y
0	0	1	1
0	1	1	1
1	0	0	0
1	1	1	1

Задачи по теме “Логические операции»

Задача 1. Докажите тождественную истинность формулы. .

Решение. Составим таблицу истинности:

Таблица 12.

X	Y
0	0	1	1	1
0	1	1	1	1
1	0	0	0	1
1	1	0	1	1

Последний столбец состоит из 1, ч.т.д.

Задача 2. Докажите эквивалентность .

Решение. Пусть . Составим таблицу истинности:

Таблица 13.