Канонические формы логических формул

Всякая логическая формула определяет некоторую булевую функцию. С другой стороны, для всякой булевой функции можно записать бесконечно много формул, ее представляющих. Одна из основных задач алгебры логики — нахождение канонических форм (т. е. формул, построенных по определенному правилу, канону), а также наиболее простых формул, представляющих булевы функции.

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

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

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

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

ДНФ И СДНФ

Формула называется дизъюнктивной нормальной формой(ДНФ), если она является дизъюнкцией неповторяющихся элементарных конъюнкций. ДНФ записываются в виде: А1 v А2 v ... v Аn , где каждое Аn— элементарная конъюнкция.

Формула Аот kпеременных называется совершенной дизъюнктивной нормальной формой (СДНФ), если:
1.А является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных х1, х2, …, xk, причем на i-м месте этой конъюнкции стоит либо переменная хiлибо ее отрицание;
2. Все элементарные конъюнкции в такой ДНФ попарно различны.

Например:А = х1 & НЕ х2 v х1 & х2

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

Она является примером однозначного представления булевой функции в виде формульной (алгебраической) записи.

Теорема о СДНФ

Пусть f(x1 х2, …, хn) – булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная дизъюнктивная нормальная форма, выражающая функцию f.

Алгоритм построения СДНФ по таблице истинности:

1.В таблице истинности отмечаем наборы переменных, на которых значение функции f = 1.
2.Записываем для каждого отмеченного набора конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае – ее отрицание.
3.Все полученные конъюнкции связываем операциями дизъюнкции.

Билет №10Канонические формы логических формул. Элементарная дизъюнкция. Конъюнктивная нормальная форма (КНФ). Совершенная КНФ (СКНФ). Теорема о существовании СКНФ.

КНФ И СКНФ

Формула называется конъюнктивной нормальной формой (КНФ), если она является конъюнкцией неповторяющихся элементарных дизъюнкций. КНФ записываются в виде: А1 & А2 & ... & Аn , где каждое Аn– элементарная дизъюнкция.

Формула А от k переменных называется совершенной конъюнктивной нормальной формой (СКНФ), если:
1. А является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных x1, х2, …, хk, причем на i-м месте этой дизъюнкции стоит либо переменная xi, либо ее отрицание;
2. Все элементарные дизъюнкции в такой КНФ попарно различны.

Например:А = (х1 v НЕ х2) & (х1 v х2)

Теорема о СКНФ

Пустьf(x1 х2, …, хn) – булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная конъюнктивная нормальная форма, выражающая функцию f.

Алгоритм построения СКНФ по таблице истинности:

1.В таблице истинности отмечаем наборы переменных, на которых значение функции f = 0.
2.Записываем для каждого отмеченного набора дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 0, то в дизъюнкцию включаем саму переменную, в противном случае – ее отрицание.
3.Все полученные дизъюнкции связываем операциями конъюнкции.

Из алгоритмов построения СДНФ и СКНФ следует, что если на большей части наборов значений переменных функция равна 0, то для получения ее формулы проще построить СДНФ, в противном случае – СКНФ.

Пример

Построить формулу для функции f(x1, х2, х3), заданной таблицей истинности:

Решение

На большей части наборов значений переменных функция равна 0, поэтому проще построить СДНФ

F(x1,х2,х3) = x1 & х2 & х3 vx1 & х2 & х3 vx1 & х2 & х3.

Примечание: А это статьи о ДНФ и КНФ из любимой Википедии. Если кому то вдруг недостаточно материала, который был выше J