Основные понятия по теме. Формула , где , , а среди переменных

Введем обозначение

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

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

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

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

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

Всякую булеву функцию , не равную тождественно нулю, можно представить совершенной дизъюнктивной нормальной формой:

(1)

Пример 1 Найти ДНФ для формулы .

Пример 2 Найти СДНФ для формулы .

1 способ (табличный). Данный способ основан на разложении (1). Суть его состоит в следующем:

1. составляется таблица истинности для данной формулы;

2. в таблице истинности выделяются наборы , для которых значение формулы истинно;

3. для каждого такого набора составляются элементарные конъюнкции;

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

2 способ (аналитический).

.

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

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

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

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

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

Всякую функцию отличную от тождественно истинной, можно представить совершенной конъюнктивной нормальной формой:

(2)

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

Пример 3 Найти КНФ для формулы .

.

Пример 4 Найти СКНФ для формулы .

1 способ (табличный). Данный способ основан на разложении (2). Суть его состоит в следующем:

1. составляется таблица истинности для данной формулы;

2. в таблице истинности выделяются наборы , для которых значение формулы ложно;

3. для каждого такого набора составляются элементарная дизъюнкция ;

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

.

2 способ (аналитический).

.

Полиномом Жегалкина называется полином вида

причем в каждом наборе все различны, а суммирование ведется по некоторому множеству таких не совпадающих наборов, - константа 0 или 1.

Справедливы следующие равносильности:

1.

2.

3.

4.

5.

Каждая булева функция может быть единственным образом выражена при помощи полинома Жегалкина.

Пример 5 Выразить формулу в виде полинома Жегалкина.

1 способ (метод неопределенных коэффициентов).

При имеем: ;

При имеем: ;

При имеем: ;

При имеем: , т.е. .

Отсюда .

2 способ.

Приведем полиномы Жегалкина элементарных булевых функций