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

UptoLike

ВУЗ: 

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

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

Рубрика: 

P \/ 0 ⇔ P,
(1.42)
P & 1 ⇔ P,
(1.43)
P & 0 ⇔ 0.
(1.44)
Для упрощения формул исчисления высказываний полезны
следующие равносильности, называемые правилами склеивания:
(P
1
& P
2
) \/ (P
1
&
⎯
P
2
) ⇔ P
1
,
(1.45)
(P
1
\/ P
2
) & (P
1
\/
⎯
P
2
) ⇔ P
1
;
(1.46)
правила поглощения:
P
1
\/ (P
1
& P
2
) ⇔ P
1
,
(1.47)
P
1
& (P
1
\/ P
2
) ⇔ P
1
;
(1.48)
формулы Блейка - Порецкого:
(P
1
&P
2
)\/(P
3
&
⎯
P
2
) ⇔ (P
1
&P
2
)\/(P
3
&
⎯
P
2
)\/(P
1
&P
3
),
(1.49)
(P
1
\/P
2
) & (P
3
\/
⎯
P
2
) ⇔ (P
1
\/P
2
)&(P
3
\/
⎯
P
2
)&(P
1
\/P
3
)
(1.50)
и формулы равносильности:
P
1
\/ (
⎯
P
1
& P
2
) ⇔ P
1
\/ P
2
,
(1.51)
P
1
& (
⎯
P
1
\/ P
2
) ⇔ P
1
& P
2
,
(1.52)
P &
⎯
P ⇔ 0,
(1.53)
P \/
⎯
P ⇔ 1,
(1.54)
P & P ⇔ P,
(1.55)
P \/ P ⇔ P.
(1.56)
⎤
⎯
P ⇔ P.
(1.57)
Часто требуется упростить формулу исчисления высказываний,
т.е. получить формулу равносильную исходной, но содержащую по
возможности меньшее число пропозициональных букв и символов
логических операций. Например, дана формула
(X
1
\/X
2
\/X
3
)&(X
1
\/
⎯
X
2
\/X
3
)&(X
1
\/
⎯
X
3
)&(X
2
\/X
3
\/X
4
)&
(X
1
\/
⎯
X
2
\/
⎯
X
3
)& (X
1
\/ X
3
\/
⎯
X
4
)&(X
1
\/X
2
).
94

Страницы