Дискретная математика. Элементы теории задачи и упражнения. Часть 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
≡
(доказать !).
Равносильность формул можно доказывать либо с помощью таблиц
истинности, либо методом равносильных (эквивалентных ) преобразо-
ваний, используя основные равносильности алгебры логики высказыва-
ний. Основные равносильности также применяются для упрощения фор-
мул, для приведения формул к заданному виду. 
                                           60
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
   b) Известно, что эквивалентность x ↔ y истинна. Что можно сказать о
      значениях x ↔ y и x ↔ y ?
   c) Известно, что x имеет значение 1. Что можно сказать о значениях
      импликации x ∧ y → z ; x → ( y ∨ z )?
   d) Известно, что x → y имеет значение 1. Что можно сказать о значе-
       ниях z → ( x → y ) ; x → y → y ; ( x → y ) → z ?

9. Найдите логические значения x и y , при которых выполняются равен-
   ства:
    a) (1 → x ) → y =0 ;
    b) x ∨ y = x .



                           4.2 Равносильные формулы.
   Основные равносильности алгебры высказываний
      Две формулы алгебры логики U 1 и U 2 называются равносильными,
если они принимают одинаковые логические значения (0 или 1) при оди-
наковых наборах значений входящих в них высказываний (пишут U 1 ≡U 2 ).
      Например, формулы U 1 = A → B , U 2 = A ∨ B — равносильные форму-
лы:
A → B ≡ A ∨ B , т.к. U 1 и U 2 либо одновременно 0, либо одновременно 1
при любом наборе значений высказываний, входящих в эти формулы.

                     A         B          A→ B            A           A ∨B
                     0         0            1             1             1
                     0         1            1             1             1
                     1         0            0             0             0
                     1         1            1             0             1

     Имеет место
Теорема: U 1 ≡U 2 тогда и только тогда, когда ( U 1 ↔ U 2 ) ≡1 (доказать!).

      Равносильность формул можно доказывать либо с помощью таблиц
истинности, либо методом равносильных (эквивалентных) преобразо-
ваний, используя основные равносильности алгебры логики высказыва-
ний. Основные равносильности также применяются для упрощения фор-
мул, для приведения формул к заданному виду.

Страницы