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

UptoLike

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

11
Основные равносильности алгебры высказываний
1.
A
A
º
закон двойного отрицания;
2.
1
º
Ú
A
A
закон исключения третьего;
3. 0ºA&A закон противоречия;
4.
þ
ý
ü
º
ºÚ
AA&A
AAA
закон идемпотентности;
5.
;A&A;&A
;A;AA
ºº
º
Ú
º
Ú
100
110
6.
þ
ý
ü
ºÚ
ºÚ
A)A&B(A
A)AB(&A
закон поглощения;
7.
þ
ý
ü
º
ÚÚºÚÚ
C&)B&A()C&B(&A
C)BA()CB(A
закон ассоциативности;
8. )C&A()B&A()CB(&A
Ú
º
Ú
первый дистрибутивный закон;
9. )CA(&)BA()C&B(A
Ú
Ú
º
Ú
второй дистрибутивный закон;
10.
ï
þ
ï
ý
ü
Úº
ºÚ
BAB&A
B&ABA
законы де Моргана;
11. ;BABA Úº®
12. );AB(&)BA()AB(&)BA(BA ÚÚº®®º«
13. );B&A()B&A(BA Úº«
14. ;BABA «ºÅ
15. ;BABA Úº¯
16.
A
.B&AB =
ЗАДАЧИ И УПРАЖНЕНИЯ
1. Проверить, справедливы ли следующие соотношения:
1)
(
)
(
)
(
)
z&xy&xzy&x
®
®
;
2)
(
)
(
)
(
)
zxyxzyx
Å
Ú
Å
Ú
Å
;
3)
(
)
(
)
(
)
zxyxzyx
Ú
«
Ú
«
Ú
;
4)
(
)
(
)
(
)
zxyxzyx
®
«
®
=
«
®
;
5)
(
)
(
)
(
)
z&xy&xzy&x
Å
Å
;
6)
(
)
(
)
(
)
z&xy&xzy&x
«
=
«
;
7)
(
)
(
)
(
)
zxyxzyx
®
Å
®
=
Å
®
; 8)
(
)
(
)
(
)
zxyxzyx
Å
®
Å
=
®
Å
.
               Основные равносильности алгебры высказываний

1. A � A – закон двойного отрицания;
2. A � A � 1 – закон исключения третьего;
3. A & A � 0 – закон противоречия;

      A � A � A�
4.             � – закон идемпотентности;
      A & A � A�

      A � 0 � A ; A � 1 � 1;
5.
      A & 0 � 0; A &1 � A;

      A & ( B � A ) � A�
6.                     � – закон поглощения;
      A � ( B & A ) � A�

      A� ( B � C ) � ( A� B )� C �
7.                               � – закон ассоциативности;
      A &( B &C ) � ( A & B )&C�

8. A & ( B � C ) � ( A & B ) � ( A & C ) – первый дистрибутивный закон;
9. A � ( B & C ) � ( A � B ) & ( A � C ) – второй дистрибутивный закон;

      A � B � A & B ��
10.                  � – законы де Моргана;
      A & B � A � B ��

11. A � B � A � B ;
12. A � B � ( A � B ) & ( B � A ) � ( A � B ) & ( B � A );
13. A � B � ( A & B ) � ( A & B );
14. A � B � A � B ;
15. A � B � A � B ;
16. A │ B � A & B .

                               ЗАДАЧИ И УПРАЖНЕНИЯ

1. Проверить, справедливы ли следующие соотношения:
 1) x & � y � z � � � x & y � � � x & z � ; 2) x � � y � z � � � x � y � � � x � z � ;
 3) x � � y � z � � � x � y � � � x � z � ; 4) x � � y � z� � � x � y� � � x � z� ;
 5) x & � y � z � � � x & y � � � x & z � ;    6) x & � y � z � � � x & y � � � x & z � ;
 7) x � � y � z � � � x � y � � � x � z � ;    8) x � � y � z � � � x � y � � � x � z � .

                                              11