Математический аппарат инженера

φ*(x₁, x₂, ..., x_n) = φ̅(x̅₁, x̅₂, ..., x̅_n)

т. е. двойственная формула выражается как отрицание формулы, полученной из исходной замещением каждой переменной ее отрицанием. Таблица соответствия двойственной функции получается заменой аргументов и значений в исходной функции на противоположные, т. е. 0 заменяется на 1, а 1 - на 0. Формула или функция, равносильная своей двойственной, называется самодвойственной.

Если формулы φ₁(x₁, x₂, ..., x_n) и φ₂(x₁, x₂, ..., x_n) равносильны, то и двойственные им формулы φ*₁(x₁, x₂, ..., x_n) и φ*₂(x₁, x₂, ..., x_n) также равносильны.

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

Функция приводится к нормальной форме следующим путем: 1) с помощью законов де Моргана формула преобразуется к такому виду, чтобы знаки отрицания относились только к отдельным переменным; 2) на основе первого (второго) дистрибутивного закона формула сводится к дизъюнкции конъюнкций (конъюнкции дизъюнкций); 3) полученное выражение упрощается и соответствии с тождествами xx = x и xx̅ = 0 (x ∨ x = x и x ∨ x̅ = 1).

- 514 -

Пример: (xy ∨ y̅z)¬(xu)=(xy ∨ y̅z)(x ∨ u̅) = (xy ∨ y̅z)x ∨ (xy ∨ y̅z)u̅ = xyx ∨ y̅zx ∨ xyu̅ ∨ y̅zu̅ = xy ∨ xyu̅ ∨ y̅zu̅

(дизъюнктивная нормальная форма); (xy ∨ y̅z)¬(xu)=(xy ∨ y̅z)(x ∨ u̅) = (x ∨ y̅z)(y ∨ y̅z)(x ∨ u̅) = (x ∨ y̅)(x ∨ z)(y ∨ y̅)(y ∨ z) x ∨ u̅) = (x ∨ y̅)(x ∨ z)(x ∨ u̅) (конъюнктивная нормальная форма).

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

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

¬(x → (x̅~z))(y → z̅) ∨ ¬(x → z) = ¬(x̅ ∨ ( ∨ z)(x̅ ∨ z̅))(y̅ ∨ z̅) ∨ ¬(x̅ ∨ z) = x¬((x ∨ z)(x̅ ∨ z̅))(y̅ ∨ z̅) ∨ xz̅ = x(x̅z̅ ∨ xz)(y̅ ∨ z̅) ∨ xz̅ =(xx̅z̅ ∨ xxz)(y̅ ∨ z̅) ∨ xz̅ =xz(y̅ ∨ z̅) ∨ xz̅=xzy̅ ∨ xzz̅ ∨ xz̅ = xyz̅ ∨ xz̅.

3. Совершенные нормальные формы. Если в каждом члене нормальной формы представлены все переменные (либо в прямом, либо в инверсном виде), то она называется совершенной нормальной формой.

Можно показать, что любая булева функция, не являющаяся тождественным нулем (единицей), имеет одну и только одну совершенную дизъюнктивную (конъюнктивную) нормальную форму. Если какой-либо член j дизъюнктивной (конъюнктивной) нормальной формы не содержит переменной х, то она вводится тождественным преобразованием φ = φ(x_i ∨ x̅_i) = φx_i ∨ φx̅_i (соответственно φ = φ ∨ x_ix̅_i =(φ ∨ x_i)(φ ∨ x̅_i)). В силу тождеств φ ∨ φ = φ и φφ = φ одинаковые члены, если они появляются, заменяются одним таким членом.

Продолжая второй пример, приведем данную функцию к совершенной дизъюнктивной нормальной форме: xy̅z ∨ xz̅ = xy̅z ∨ xz̅(y ∨ y̅) = xy̅z ∨ xy̅z̅.

Приведение к совершенной конъюнктивной нормальной форме иллюстрируется следующим примером:

¬(x ∨ yz̅)(x ∨ z)=x̅¬(yz̅)(x ∨ z)=x̅(y̅ ∨ z)(x ∨ z)=(x̅ ∨ yy̅)(y̅ ∨ z ∨ xx̅)(x ∨ z ∨ yy̅) =

=(x̅ ∨ y)(x̅ ∨ y̅)(y̅ ∨ z ∨ x)(y̅ ∨ z ∨ x̅)(x ∨ z ∨ y)(x ∨ z ∨ y̅)=

= (x̅ ∨ yzz̅)(x̅ ∨ y̅ ∨ zz̅)(x ∨ y̅ ∨ z)(x̅ ∨ y̅ ∨ z)(x ∨ y ∨ z)(x ∨ y̅ ∨ z)=

=(x̅ ∨ y ∨ z)(x̅ ∨ y ∨ z̅)(x̅ ∨ y̅ ∨ z)(x̅ ∨ y̅ ∨ z̅)(x ∨ y̅ ∨ z)(x̅ ∨ y̅ ∨ z)(x ∨ y ∨ z)(x ∨ y̅ ∨ z)=

=(x̅ ∨ yCz)(x̅ ∨ y ∨ z̅)(x̅ ∨ y̅ ∨ z̅)(x̅ ∨ y̅ ∨ z)(x ∨ y̅ ∨ z)(x ∨ y ∨ z).

- 515 -

4. Проблема разрешимости. Формула(или соответствующая ей функция) называется выполнимой, если она не является тождественным нулем или единицей. Решение с помощью конечного числа действий вопроса, является ли данная формула выполнимой, т. е. не равна ли она тождественно нулю или единице, носит название проблемы разрешимости.

Ответ на этот вопрос можно получить, построив для данной формулы таблицу соответствия, что сводится по существу к определению значений формулы при всевозможных наборах значении входящих в нее переменных. Если на всех наборах формула принимает значения только 0 или только 1, то она невыполнима.

При большом количестве переменных такой способ практически неосуществим из-за огромного числа возможных наборов значений переменных. Более удобный путь - приведение формулы к нормальной форме. Если в процессе такого приведения формула не обращается в тождественный 0 или 1, то это свидетельствует о ее выполнимости.