Контрольная работа: Математическая логика

11. Связь импликации с отрицанием – и дизъюнкцией :

.

12. Связь эквивалентности ~ с дизъюнкцией , конъюнкцией и отрицанием:

~ y =.

Всякая функция алгебры логики может быть реализована некоторой формулой языка с символами ~, –.

1.2 Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ)

ДНФ и КНФ играют особую роль в алгебре логики и ее приложениях. Введем обозначение:

Так определенная переменная или ее отрицание называется первичным термом.

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

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ):

.

Формула вида называется элементарной дизъюнкцией.

Всякая конъюнкция элементарных дизъюнкций называется конъюктивной нормальной формой (КНФ):

.

Пример.

Привести формулу ~z к ДНФ и КНФ .

1) Приведем формулу к ДНФ (последовательно: на основании определений операций импликации и эквивалентности, законов де Моргана и дистрибутивности):

~ ~(()=

.

2) Применив закон дистрибутивности к последнему выражению, получим КНФ :

Совершенной ДНФ (СДНФ) называется ДНФ , в которой нет равных элементарных конъюнкций и все элементарные конъюнкции содержат одни и те же переменные, причем каждую переменную – только один раз (включая вхождения под знаком отрицания).

Совершенная КНФ (СКНФ) определяется как такая КНФ , в которой нет одинаковых сомножителей; все сомножители содержат одни и те же переменные, причем каждую переменную – только один раз.

Для каждой ФАЛ можно построить реализующую ее СДНФ :

,

где дизъюнкция берется по тем двоичным наборам, на которых f = 1.

Каждая функция алгебры логики реализуется следующей СКНФ :