Математическая логика и теория алгоритмов. Анкудинов Г.И - 9 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

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

Рубрика: 

1.4. Равносильные формулы
Две формулы исчисления высказываний Ф
1
(P
1
,...,P
N
) и
Ф
2
(P
1
,...P
N
) называются равносильными, если они принимают
одинаковое значение для любых значений P
1
,...P
N
. Две равносильные
формулы имеют одну и ту же таблицу истинности и, наоборот,
формулы, имеющие одну и ту же таблицу истинности, равносильны.
Условие равносильности формул выражает
Теорема 1.1. Формулы Ф
1
(P
1
,...P
N
) и Ф
2
(P
1
,...P
N
) равносильны
тогда и только тогда, когда их эквивалентность
Ф
1
(P
1
,...P
N
) ↔ Ф
2
(P
1
,...P
N
)
является тавтологией.
Отношение равносильности обозначается символом ⇔.
Например, из законов (1.12) и (1.13) следуют равносильности:
(P
1
\/ P
2
) & P
3
⇔ (P
1
& P
3
) \/ (P
2
& P
3
),
(1.30)
(P
1
& P
2
) \/ P
3
⇔ (P
1
\/ P
3
) & (P
2
\/ P
3
).
(1.31)
Из законов (1.14) и (1.15) следуют равносильности:
⎤(P
1
& P
2
) ⇔
⎯
P
1
\/
⎯
P
2
,
(1.32)
⎤(P
1
\/ P
2
) ⇔
⎯
P
1
&
⎯
P
2
.
(1.33)
Из тавтологий (1.23,...,1.29) следуют равносильности:
P
1
& P
2
⇔ ⎤(
⎯
P
1
\/
⎯
P
2
),
(1.34)
P
1
\/ P
2
⇔ ⎤(
⎯
P
1
&
⎯
P
2
),
(1.35)
P
1
↔ P
2
⇔ (P
1
→ P
2
) & (P
2
→ P
1
),
(1.36)
P
1
→ P
2
⇔ ⎤(P
1
&
⎯
P
2
),
(1.37)
P
1
→ P
2
⇔
⎯
P
1
\/ P
2
,
(1.38)
P
1
& P
2
⇔ ⎤(P
1
→
⎯
P
2
),
(1.39)
P
1
\/ P
2
⇔
⎯
P
1
→ P
2
.
(1.40)
Полезно также использовать следующие равносильности с
логическими константами:
P \/ 1 ⇔ 1,
(1.41)
93

Страницы