Лекция 4

ТЕМА: РАВНОСИЛЬНЫЕ ФОРМУЛЫ АЛГЕБРЫ ЛОГИКИ. ЗАКОНЫ ЛОГИКИ.

ПЛАН:

1. Равносильные формулы алгебры логики.

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

3. Равносильные преобразования формул.

Главная

1. Равносильные формулы алгебры логики.

Рассмотрим примеры:

2х + 4у = 2(х + 2у) – это тождество или равносильность, т.к. истинно при любых х и у;

, сократим дробь, получим - получившееся равенство не является тождеством, т.к. верно не при всех х и у: при х = -2 оно не верно, т.к. х = -2 не входит в область допустимых значений дроби.

Теперь рассмотрим понятие равносильных формул в математической логике.

Определение. Две формулы алгебры логики А и В называются равносильными, если они принимают оди­наковые логические значения на любом наборе значе­ний входящих в формулы элементарных высказыва­ний.

Равносильность формул будем обозначать знаком  , а запись А  В означает, что формулы А и В рав­носильны.

Например, равносильны формулы:

(Проверьте самостоятельно).

Все формулы алгебры логики можно подразделить на три класса: тавтологии, тождественно ложные и выполнимые.

Формула А называется тождественно истинной (или тавтологией) , если она принимает значение 1 при всех значениях входящих в нее переменных.

Например, тожественно истинны формулы :

(Проверьте с помощью таблицы истинности).

Формула А называется тождественно ложной, если она принимает значение 0 при всех значениях входящих в нее переменных.

Например, тождественно ложна формула

Формула А называется выполнимой, если она принимает значения и 0 и 1.

Например, формула ху выполнимая.

Между понятиями равносильности и эквивалентно­сти существует следующая связь: если формулы А и В равносильны, то формула А  В - тавтология, и обрат­но, если формула А  В — тавтология, то формулы А и В равносильны.

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

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

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

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

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

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

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

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

5. - закон снятия двойного отрицания;

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