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

UptoLike

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

10
8. a) Известно, что импликация
y
x
®
истинна, а эквивалентность
y
x
«
ложна. Что можно сказать о значении импликации
x
y
®
?
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) при оди-
наковых наборах значений входящих в них высказываний (пишут
2
1
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
Имеет место
Теорема:
2
1
UU º тогда и только тогда, когда (
2
1
UU « )
1
º
(доказать
самостоятельно).
Равносильность формул можно доказывать либо с помощью таблиц
истинности, либо методом равносильных (эквивалентных) преобразо-
ваний, используя основные равносильности алгебры логики высказыва-
ний. Основные равносильности также применяются для упрощения фор-
мул, для приведения формул к заданному виду.