Задания для самостоятельного выполнения

8. Постройте таблицы истинности формулы алгебры логики:

0)	Ú & a Å c;
1)	c → b Å & c;
2)	& b → c Å ;
3)	а ~ c Ú Å ;
4)	c & → ~ a;
5)	b Å & ~ b;
6)	а & b → ~ ;
7)	Ú b Å c &
8)	→ Ú a ~
9)	→ c Å Ú b

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

Преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.). Логические операции обладают рядом свойств и подчинены логическим законам, изложенным в следующей таблице:

Название

Содержание

Коммутативность

(переместительный)

a Ú b ≡ b Ú a a & b ≡ b & a

a Å b ≡ b Å a

Ассоциативность

(сочетательный)

a Ú (b Ú c) ≡ ( a Ú b ) Ú с

a & (b & c) ≡ ( a & b ) & c

a Å ( b Å c ) ≡ (a Å b) Å c

Дистрибутивность

(распределительный)

a & (b Ú c) ≡ ( a & b ) Ú (а & c)

a Ú (b & c) ≡ ( a Ú b ) & (а Ú c)

Закон снятия двойного отрицания

≡ а

Законы де Моргана

≡

следствие закона

a Ú b ≡ ; a & b ≡

Законы поглощения

a Ú a & b ≡ a a & (a Ú b) ≡ a

Свойства константы Л

a Ú Л ≡ a а & Л ≡ Л

Свойства константы И

а Ú И≡ И а & И ≡ a

Закон исключения третьего

Ú a ≡ И

Законы идемпотентности

a Ú a ≡ a a & a ≡ a

Закон противоречия

& a ≡ Л

Операции строгой дизъюнкции, импликации, эквиваленции, функция Шеффера и стрелка Пирса могут быть равносильно выражены через операции конъюнкции, дизъюнкции и отрицания, поэтому они считаются как-бы избыточными.

Логические равносильности алгебры логики:

1)	a → b ≡ Ú b;	4)	a Å b ≡ & b Ú a & ;
2)	a \| b ≡ Ø ( a & b) ;	5)	a ~ b ≡ a & b Ú & ;
3)	a ¯ b ≡ Ø ( a Ú b) ;	6)	a ~ b ≡ ( a Ú ) & ( Ú b) .

Равносильное упрощение формул выполняется по шагам:

1. замена операций импликации, строгой дизъюнкции, эквиваленции, функции Шеффера и стрелки Пирса равносильностями алгебры логики;

2. применение законов алгебры логики.

Примеры выполнения задания

1 .Докажите равносильность x & Ú º разными способами:
а) докажем равносильность формул, используя законы алгебры логики:
x & Ú º x & Ú & (по закону де Моргана);