Отношения логической эквивалентности и логического следствия.
Определение.
Формулы
и
называются логически эквивалентными
тогда и только тогда, когда формула
– тавтология.
Замечание.
Формула
– тавтология, если таблицы истинности
формул
и
совпадают.
Пример.
По законам де Моргана, логически
эквивалентны формулы
и
,
а также формулы
и
.
Теорема. Отношение логической эквивалентности является отношением эквивалентности.
Рефлексивность, симметричность и транзитивность данного отношения следуют из замечания.
Справедливы правило подстановки и правило замены.
Пусть
и
– формулы, содержащие букву
,
и
– формулы, полученные из формул
и
соответственно подстановкой вместо
буквы
формулы
.
Правило
подстановки. Если
формула
логически эквивалентна формуле
,
то формула
логически эквивалентна формуле
.
Пусть
– формула, в которой выделена некоторая
подформула
,
– формула, полученная из формулы
заменой
на некоторую формулу
.
Правило
замены. Если
формулы
и
логически эквивалентны, то логически
эквивалентны и формулы
и
.
Доказательства правил подстановки и замены основано на сравнении таблиц истинности соответствующих формул.
Пример.
Известна
тавтология
(проверьте самостоятельно). По правилу
подстановки, формула
логически эквивалентна формуле
.
По правилу замены, примененному к закону
двойного отрицания, получаем, что формула
логически эквивалентна формуле
.
Следовательно, по свойству транзитивности,
формулы
и
логически эквивалентны.
Определение.
Говорят, что формула
логически влечет формулу
(из формулы
логически следует формула
),
если формула
является тавтологией.
Теорема. Отношение логического следствия является отношением предпорядка, то есть рефлексивным и транзитивным отношением.
Пример.
Формула
логически влечет формулу
.
В самом деле, в примере 1 предыдущего
пункта было доказано, что формула
является тавтологией.
В Содержание.
Задачи.
1. Установить, является ли предложение высказыванием, и если является, истинно оно или ложно.
Волга впадает в Каспийское море.
Студент второго курса.
.
.Существует человек, который не старше своего отца.
.Марс есть спутник Земли.
.
.Который час?
2. Установить, является ли предложение высказыванием, и если является, истинно оно или ложно.
.
.
.
.
.
.
.
.
.
.
3. Среди следующих высказываний выделить элементарные и составные. В составных высказываниях обозначить элементарные высказывания буквами и записать с помощью логических символов.
Число 6 является делителем числа 36.
Число 225 делится нацело на 5.
Число 225 делится нацело на 5 и не делится на 10.
Если 81 делится нацело на 9, то 81 делится на 3.
16 кратно 2.
18 кратно 2 и 3.
.Число 39 имеет 2 простых делителя.
Двузначное число 19 простое.
Корнями уравнения
являются числа 2 и 3.
4.
Пусть
обозначает высказывание“Я
увлекаюсь горным туризмом”, а
обозначает высказывание“Я
изучаю программирование”. Дайте
словесную формулировку следующих
высказываний:
; 2)
;
3)
;
4)
;
5)
;
6)
;
7)
;
8)
;
9)
;
10)
.
5. Проверить, является ли формула тавтологией, без построения таблицы истинности.
|
1)
|
6)
|
|
2)
|
7)
|
|
3)
|
8)
|
|
4)
|
9)
|
|
5)
|
10)
|
.
.
.
.
.
.
.
.
.
.
6. Доказать, что формула является тавтологией, без построения таблицы истинности. Во всех формулах выделить всевозможные подформулы.
.
.
.
.
.
.
.
.
.
.
Доказать, что формулы логически эквивалентны.
и
.
и
.
и
.
и
.
и
.
и
.
и
.
и
.
и
.
и
.
Доказать, что первая формула логически влечет вторую формулу.
;
.
;
.
;
.
;
.
;
.
;
.
;
.
;
.
;
.
;
.
9. Доказать теорему о том, что отношение логической эквивалентности является отношением эквивалентности.
10. Доказать теорему о том, что отношение логического следования является отношением предпорядка.
В Ответы и указания.
В Содержание.