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

      Две формулы алгебры логики U1 и U 2 называются равносильными,
если они принимают одинаковые логические значения (0 или 1) при оди-
наковых наборах значений входящих в них высказываний (пишут U1 � U 2 ).
      Например, формулы U1 � A � B , U 2 � A � B – равносильные форму-
лы: A � B � A � B , т.к. U1 и 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

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


                                        10

Страницы