logo
Elektronny_praktikum_po_MLTA_2014

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

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

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

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

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

a → b ≡ b;

a b ≡ & b a & ;

a b ≡ a & b & .

a b ≡ ( a & b)

a b ≡ ( a b)

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

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

2. применение законов алгебры логики. Таблица 3. Свойства и законы алгебры логики

Название

Содержание

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

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

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 ≡ Л

Законы склеивания

(a b) ( b) ≡ b

(a b) ( b) ≡ b

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

1. Докажите: x ;

1) x x (по закону де Моргана);

2) x (x ) (по дистрибутивному закону);

3) (x ) И (по закону исключения третьего);

4) И (по свойству логической константы И).

2. Упростите: x (y → x) →

1) x (y → x) → x ( x) → (по равносильности);

2) x ( x) → (по равносильности);

3) ( ) (по закону де Моргана);

4) ( ) (y ) (по закону снятия дв.отрицания);

5) (y ) (по закону поглощения).

3. Определите тождественную истинность или ложность формулы

X Y →Y

1) X Y →Y Y (по равносильности)

2) Y Y (по закону де Моргана)

3) Y X Y (по закону снятия дв.отрицания);

4) X Y X Y (по коммутативному закону);

5) X Y И И И (по закону исключения третьего).