Элементы математической логики. 4 страница

Минимальным базисом называется такой базис, для которого удаление хотя бы одной функции f₁ , образующей этот базис, превращает систему функций (f₁, f₁,…, f_m) в неполную.

Любая функция, как было показано ранее, может быть представлена в виде СДНФ или СКНФ:

(x₁, x₂,…, x_n)=

(x₁, x₂,…, x_n)= .

Верно утверждение о полноте системы, состоящей из трех функций: конъюнкции, отрицания и дизъюнкции.

Минимизация функций алгебры логики

Любая ФАЛ может быть записана в виде СДНФ или СКНФ. Покажем на примере, что такая запись в ряде случаев является неэкономной.

Пример. Пусть задана ФАЛ в СДНФ.

f(x₁, x₂, x₃)= & x₂&x₃ x₁& x₂& x₁& & x₃ x₁& & & x₂& x₃.

Добавим к функции один конъюнктивный член & x₂&x₃. Это добавление не меняет данной функции так как x x=x:

f(x₁, x₂, x₃)= x₂x₃ x₁ x₂ x₁ x₃ x₁ x₂x₃ x₂x₃.

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

f(x₁, x₂, x₃)= x₂ (x₃ ) x₁ ( x₃ ) x₂ x₃ (x₁ ).

Используя свойство дизъюнкции, получаем:

Аналогично предыдущему делаем дальнейшие преобразования:

.

Из примера видна неэкономность совершенных нормальных форм для представления ФАЛ.

Проблема простейшего представления функций сводится к проблеме выбора базиса и проблеме наиболее экономного представления функций в этом базисе.

К настоящему времени существенные результаты в решении задачи минимизации лишь в базисе, состоящем из отрицания, конъюнкции и дизъюнкции.

Приведем ряд определений.

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

Определение. Ранг элементарной конъюнкции — это число элементов, образующих эту конъюнкцию. Ранг — это ''n''.

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

Определение. ДНФ для функции f(x₁, x₂,…, x_n), состоящей из элементарных конъюнкций ранга n, называется дизъюнктивной совершенной нормальной формой.

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

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

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

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

Аналогичные определения можно дать для случая конъюнктивных нормальных форм.

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

U₁,…U_n — элементарные конъюнкции.

,

где все различны; число r — ранг конъюнкции.