ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 9599
Скачиваний: 93
56
Продолжение табл. 2.5
№
Формула
Название
6
X
X
≡
¬¬
Закон двойного отрицания
7
X
X
X
X
X
X
≡
∨
≡ ,
&
Закон идемпотентности
8
Y
X
Y
X
¬
¬
≡
∨
¬
&
)
(
Y
X
Y
X
¬
∨
¬
≡
¬
)
&
(
Законы де Моргана
9
X
Y
X
X
X
Y
X
X
≡
∨
≡
∨
)
(
&
,
)
&
(
Законы поглощения
10
X
Y
X
Y
X
≡
¬
∨
)
&
(
)
&
(
X
Y
X
Y
X
≡
¬
∨
∨
)
(
&
)
(
Законы склеивания
11
Y
X
Y
X
∨
¬
≡
→
Замена импликации
12
)
&
(
)
&
(
~
Y
X
Y
X
Y
X
¬
¬
∨
≡
Замена эквиваленции
Обратите внимание на сходство табл. 2.5 и табл.1.1. Это объясняется тем,
что алгебра множеств и алгебра высказываний изоморфны, т.е. одинаково ор-
ганизованы с точки зрения математики, обе они являются булевыми алгебра-
ми.
Пример. Пользуясь основными равносильностями логики высказываний
(табл. 2.5), показать,
что формулы
)
(
)
(
1
A
B
B
A
F
¬
→
∨
→
¬
=
и
)
&
(
2
B
A
F
¬
=
равносильны.
Преобразуем первую формулу:
.
)
&
(
)
&
(
)
)
&
((
)
(
)
&
)
((
)
(
)
(
2
3
8
9
4
,
6
8
11
1
F
B
A
A
B
A
B
A
B
B
A
A
B
B
A
A
B
B
A
F
=
¬
≡
¬
≡
¬
∨
¬
≡
¬
∨
¬
∨
¬
≡
≡
¬
∨
¬
∨
¬
¬¬
≡
¬
∨
¬
∨
∨
¬
¬
≡
Формула
2
F
получена из формулы
1
F
цепочкой равносильных преобра-
зований (над знаком равносильности указан номер применяемого закона из
табл. 2.5), следовательно,
2
1
F
F
≡
.
2.1.7. Решение задач контрольной работы №2
Задача 1. С помощью таблицы истинности выяснить, является ли форму-
ла
Y
X
Y
X
F
&
~
)
(
¬
→
=
противоречием.
Решение. Учитывая приоритет логических операций, определим порядок
действий:
.
&
~
)
(
3
2
4
1
Y
X
Y
X
F
¬
→
=
Выполним действия в указанном порядке (табл. 2.6).
57
Таблица 2.6
Таблица истинности
X Y 1 2 3 4
И
И
И
Л
Л
Л
И
Л
Л
Л
Л
И
Л
И
И
И
И
И
Л
Л
И
И
Л
Л
Формула является противоречием, если при любых значениях перемен-
ных она принимает значение “ложь”. Формула
F
на двух наборах переменных
принимает значение “истина”, следовательно, противоречием не является.
Задача 2. Пользуясь равносильными преобразованиями, выяснить, рав-
носильны ли формулы
)
~
(
1
Z
X
X
F
→
=
и
)
(
~
)
(
2
Z
X
Y
X
F
→
→
=
.
Перечислить используемые законы.
Решение. Избавимся от операций импликации и эквивалентности, при-
менив формулы
,
B
A
B
A
∨
¬
≡
→
).
&
(
)
&
(
~
B
A
B
A
B
A
¬
¬
∨
≡
Преобразуем первую формулу:
3
1
&
&
)
&
&
(
F
Z
Y
Z
Y
X
Z
Y
Z
Y
X
F
a
=
¬
¬
∨
∨
¬
≡
¬
¬
∨
∨
¬
≡
.
Преобразуем вторую формулу:
.
&
&
&
&
))
&
(
(
&
&
)
((
&
))
&
(
&
(
&
&
&
&
)))
&
(
&
&
)
&
((
))
&
(
(
))
(
&
)
(
(
))
(
&
)
((
)
(
~
)
(
3
,
,
,
,
,
2
F
Z
Y
Z
Y
X
Z
Y
X
Z
Y
Z
Y
X
X
X
Z
Y
Z
Y
X
X
Z
Y
Z
Y
X
Z
Y
X
Z
X
Y
X
Z
Y
X
Z
X
Y
X
Z
X
Y
X
Z
X
Y
X
F
к
а
т
д
к
а
и
к
а
м
д
≡
¬
¬
∨
∨
∨
¬
≡
¬
¬
∨
¬
∨
≡
¬
¬
∨
¬
∨
¬
∨
≡
¬
¬
∨
¬
∨
≡
≡
¬
¬
∨
∨
¬
≡
¬
¬
∨
∨
¬
≡
∨
¬
¬
∨
¬
¬
∨
∨
∨
¬
∨
¬
≡
∨
¬
∨
¬
≡
По свойствам отношения равносильности (симметричность, транзитив-
ность) имеем:
3
1
F
F
≡
и
3
2
F
F
≡
, значит
2
1
F
F
≡
.
Формулы
1
F
и
2
F
равносильны.
В преобразованиях использовались следующие законы:
58
а – ассоциативность;
д – дистрибутивность;
м – закон де Моргана;
к – коммутативность;
и – идемпотентность;
т – закон исключенного третьего.
2.1.8. Контрольные вопросы и упражнения
1. Сформулируйте отрицание высказывания “Сергей – мой друг”.
2.
Какое значение должна иметь высказывательная переменная
X
, что-
бы высказывание
X
∨
Л принимало значение “ложь”.
3.
Даны высказывания:
X
– “белые медведи живут в Африке”,
Y
–
“
2
5
≥
”. Какое значение принимают высказывания
,
,
&
Y
X
Y
X
∨
Y
X
Y
X
~
,
→
?
4.
Составьте таблицу истинности для формулы
A
B
A
F
¬
→
=
)
~
(
.
5.
Запишите знаки логических операций в порядке убывания приори-
тета.
6.
Какие скобки в формуле
A
B
A
B
A
F
&
))
(
)
&
((
∨
¬
→
=
можно
убрать так, чтобы значение формулы не изменилось?
7.
Какая формула логики высказываний называется выполнимой?
8.
Приведите пример формулы, являющейся тавтологией.
9.
Какая формула называется противоречием?
10.
Равносильны
ли
формулы
)
(
)
(
1
Z
X
Y
X
F
→
∨
→
=
и
)
(
2
Z
Y
X
F
∨
→
=
? Проверьте по таблице истинности.
11.
Проверьте законы поглощения и склеивания с помощью таблиц ис-
тинности.
12.
Докажите справедливость равносильности 12 (табл. 2.5).
2.2. Логические рассуждения
2.2.1. Определение логически правильного рассуждения
Математическая логика изучает то общее, что есть во всех доказатель-
ствах, рассуждениях, независимо от их содержания. Когда мы говорим, что
одно предложение
D
логически следует из другого
Р
, то имеем в виду следу-
ющее: всякий раз, когда предложение
Р
истинно, то истинно и предложение
D
. В логике высказываний мы имеем дело с формулами
P
и
D
, зависящими от
некоторых высказывательных переменных
n
X
X
X
,
,
,
2
1
…
.
Определение. Будем говорить, что из формулы
)
,
,
,
(
2
1
n
X
X
X
P
…
логически следует формула
)
,
,
,
(
2
1
n
X
X
X
D
…
и обозначать
P
− D,
если
59
для
любых
наборов
значений
n
X
X
X
,
,
,
2
1
…
при
условии
И
)
,
,
,
(
2
1
=
n
X
X
X
P
…
выполняется условие
И
)
,
,
,
(
2
1
=
n
X
X
X
D
…
.
Формула
P
называется посылкой, а
D
– заключением логического рас-
суждения.
Пример. Формула
X
D
¬
=
логически следует из формулы
Y
X
P
&
¬
=
, т.е.
Y
X &
¬
− X
¬
. Убедиться в этом можно, построив таб-
лицу истинности (табл. 2.7).
Таблица 2.7
Таблица истинности
X Y
Y
X
P
&
¬
=
X
D
¬
=
И
И
Л
Л
И
Л
Л
Л
Л
И
И
И
Л
Л
Л
И
Действительно, если
И
=
P
(при
И
Л,
=
=
Y
X
), то
И
=
D
и по опре-
делению
P
−
D
. Если
Л
=
P
, то формула
D
может принимать любые истин-
ностные значения.
Обычно в логических рассуждениях используется не одна посылка
P
, а
несколько
n
P
P
P
,
,
,
2
1
…
. В этом случае рассуждение будет логически пра-
вильным (
n
P
P
P
,
,
,
2
1
…
−
D
), если
n
P
P
P
&
&
&
2
1
…
−
D
– из конъюнкции
посылок логически следует заключение.
Пример. Покажем, что рассуждение
X
Y
X
,
→
−
Y
является логически
правильным. Составим конъюнкцию посылок
X
Y
X
P
&
)
(
→
=
и проверим
правильность логического рассуждения
P
−
D
(здесь
Y
D
=
) по таблице
истинности (табл. 2.8).
Таблица 2.8
Таблица истинности
X Y
Y
X
→
P D
И
И
И
И
И
И
Л
Л
Л
Л
Л
И
И
Л
И
Л
Л
И
Л
Л
Определение логического рассуждения выполняется, значит, это рассуж-
дение является логически правильным.
Логически правильное рассуждение будем записывать в виде схемы рас-
суждения:
60
D
P
P
P
n
,
,
,
2
1
…
Так, логически правильная схема рассуждений из последнего примера
имеет вид:
Y
X
Y
X
→
2.2.2. Проверка правильности логического рассуждения
Какими способами можно проверить правильность логического рассуж-
дения?
Первый способ - по определению:
а) записать все посылки и заключения в виде формул логики высказыва-
ний;
б)составить конъюнкцию формализованных посылок
n
P
P
P
&
&
&
2
1
…
;
в) проверить по таблице истинности, следует ли заключение
D
из фор-
мулы
n
P
P
P
&
&
&
2
1
…
.
Второй способ основан на следующем признаке логического следова-
ния.
Теорема. Формула
D
логически следует из формулы
P
тогда и только то-
гда, когда формула
D
P
→
является тавтологией.
Доказательство. Пусть
P
−
D
, тогда для всех наборов переменных
значение
P
= И влечет
D
= И. Это означает, что для всех наборов перемен-
ных
≡
→
D
P
И, т.к. формула
D
P
→
принимает значение “ложь” только в
одном случае: когда
P
=И, а
D
=Л, но такая ситуация исключена по условию.
Следовательно,
D
P
→
– тавтология.
Обратно, пусть
D
P
→
– тавтология, т.е.
≡
→
D
P
И. Отсюда по опре-
делению операции импликации заключаем: не существует такого набора зна-
чений переменных, при котором
P
=И, а
D
=Л. Значит,
P
−
D
.
Согласно доказанной теореме, проверка правильности логического рас-
суждения сводится к ответу на вопрос: является ли формула
D
P
→
тавтоло-
гией? На этот вопрос можно ответить, построив таблицу истинности для фор-
мулы
D
P
→
, или сведя эту формулу с помощью равносильных преобразова-
ний к известной тавтологии. Например, для логического рассуждения
X
Y
X
,
→
−
Y
с помощью законов логики высказываний (табл. 2.5) имеем: