Основные законы логики

Существует 2 способа определения истинного значения формулы. Первый – с помощью таблиц истинности, а второй – с помощью приведения формулы к нормальной форме.

Формула имеет нормальную форму, если в ней отсутствуют знаки эквиваленции, импликации, исключающей дизъюнкции, двойного отрицания, при этом знаки отрицания находятся только при переменных.

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

1. Основные законы логики	А = А; А А= 0; А +`А = 1; = А = А – закон двойного отрицания.
2. Свойства констант	`0 = 1; А+0=А; А+1=1	`1 = 0; А 0 = 0; А 1 = А
3. Закон идемпотентности (равносильности)	А + А = А	А А = А
4. Законы коммутативности	А + В = В + А	А В = В А
5. Законы ассоциативности	(А + В) + С = А + (В + С)	А (В С) = (А В) С
6. Законы дистрибутивности	А+(В С) = (А+В) (А+С)	А (В+С) = А В + А С
7. Законы поглощения	А + АВ = А	А (А + В) = А
8. Законы исключения (склеивания)	А В + `А В = В	(А + В) (`А + В) = В

Доказать законы можно, упросив левую (правую) часть тождества.

Справедливы также равенства:

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

А + В =`А `В; А В =`А +`В;   `А +`В = А В; `А ` В = А + В.

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

При преобразовании логических выражений, содержащих операции строгой дизъюнкции, импликации и эквиваленции, удобно использовать равенства:

	10. А®В =`А + В   11. А «В = А В +`А `В = (`А + В) (А +`В)   12. А " В = А `В + `А В

Пример. Доказать тождество:

(А + В + С)(А +`В + С)(А +`В +`С)(`А +`В + С)(`А +`В +`С) =А`В +`ВС

Расставим порядок действий в левой части тождества:

(А + В + С) (А +`В + С) (А +`В +`С) (`А +`В + С) (`А +`В +`С)

Выполним действия, применяя логические законы:

1) ((А + С) + В) ((А + С) +`В) = А + С (по закону исключения)

2) ((`А +`В)+С) ((`А +`В) +`С) = `А +`В (по закону исключения)

3) (А + С) ((А +`В +`С) = (А + А`В + А`С + АС) + `ВС +`СС = А + `ВС

= А (з-н поглощения)

4) (А + `ВС) (`А +`В) = А`В + (А` ВС +` ВС) = А`В +`ВС (по закону поглощения)

Дата добавления: 2014-12-27