Дискретная математика. Элементы теории задачи и упражнения. Часть 2. Булгакова И.Н - 14 стр.

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
60
b) Известно, что эквивалентность
y
x
истинна. Что можно сказать о
значениях
y
x
и
y
x
?
c) Известно, что
x
имеет значение 1. Что можно сказать о значениях
импликации
z
y
x
;
(
)
zyx
?
d) Известно, что
y
x
имеет значение 1. Что можно сказать о значе-
ниях
(
)
yxz
; yyx →→ ;
(
)
zyx
?
9. Найдите логические значения
x
и
y
, при которых выполняются равен -
ства :
a)
(
)
01
=
yx
;
b)
x
y
x
=
.
4.2 Равносильные формулы.
Основные равносильности алгебры высказываний
Две формулы алгебры логики
1
U
и
2
U
называются равносильными,
если они принимают одинаковые логические значения (0 или 1) при оди-
наковых наборах значений входящих в них высказываний (пишут
21
UU
).
Например, формулы BAU →=
1
, BAU ∨=
2
равносильные форму-
лы:
BABA ≡→ , т.к.
1
U и
2
U либо одновременно 0, либо одновременно 1
при любом наборе значений высказываний, входящих в эти формулы.
A
B
BA
A
B
A
0 0 1 1 1
0 1 1 1 1
1 0 0 0 0
1 1 1 0 1
Имеет место
Теорема:
21
UU тогда и только тогда, когда (
21
UU )
1
(доказать !).
Равносильность формул можно доказывать либо с помощью таблиц
истинности, либо методом равносильных (эквивалентных ) преобразо-
ваний, используя основные равносильности алгебры логики высказыва-
ний. Основные равносильности также применяются для упрощения фор-
мул, для приведения формул к заданному виду.