Лекции ДМ

2. Важнейшие равносильности алгебры логики.

Рассмотрим важнейшие равносильности алгебры логики, которые можно разбить на три основные группы.

I группа. Основные равносильности .

1) x Ù x º x; x Ú x º x – законы идемпотентности;

2) x Ù 1 º x; x Ú 1 º 1;

3) x Ù 0 º 0; x Ú 0 º x.

x Ù` º 0 – закон противоречия; x Ú` º 1 – закон исключения третьего;
- закон снятия двойного отрицания;

6) законы поглощения:

x Ù (x Ú y) º x,

x Ú (x Ù y) º x.

Доказать справедливость каждого тождества можно, построив таблицы истинности. Например, докажем справедливость закона поглощения относительно дизъюнкции. Таблица истинности будет содержать 4 строки:

х	у	уvx	х(уvx)
0	0	0	0
1	0	1	1
0	1	1	1
1	1	1	1

Сравнивая значения последнего столбца с соответствующими значениями высказывания х можно сделать вывод о справедливости тождества.

II группа. Равносильности, выражающие одни логические операции через другие.

1) x ® y º` Ú y;

2) x « y º (x ® y) Ù (y ® x);

3) Закон де Моргана (закон инверсии или отрицания):

4) и 5) тождества докажем, применив закон двойного отрицания и тождества 3) второй группы:

Докажем, составив таблицу истинности справедливость тождества 2):

х	у	ху	ху	ух	(ху)( ух)
0	0	1	1	1	1
1	0	0	0	1	0
0	1	0	1	0	0
1	1	1	1	1	1

Сравнивая значения третьего столбца и последнего приходим к выводу о справедливости тождества.

III группа. Основные законы алгебры логики.

1) коммутативность:

x Ù y º y Ù x,

x  y  y  x;

2) ассоциативность:

x Ù (y Ù z) º (x Ù y) Ù z

x Ú (y Ú z) º (x Ú y) Ú z

3) дистрибутивность:

x Ù (y v z) º x Ù y Ú x Ù z – относительно дизъюнкции,

x Ú (y Ù z) º (x Ú y) Ù (x Ú z) – относительно конъюнкции.

Докажем справедливость дистрибутивности относительно конъюнкции. Составим таблицу истинности, которая содержит 2³ = 8 строк:

х	у	z	yz	x v yz	x v y	x v z	(x v y)( x v z)
0	0	0	0	0	0	0	0
1	0	0	0	1	1	1	1
0	1	0	0	0	1	0	0
0	0	1	0	0	0	1	0
1	1	0	1	1	1	1	1
0	1	1	1	1	1	1	1
1	0	1	0	1	1	1	1
1	1	1	1	1	1	1	1

Содержание