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

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

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

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

Совершенная дизъюнктивная нормальная форма (СДНФ)

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

Примеры: y, ¬ y, х 1 ∧ ¬ х 2 ∧ х 3 ∧ х 4

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

ДНФ записывается в следующей форме: F 1 ∨ F 2 ∨ ... ∨ F n , где F i - элементарная конъюнкция

Примеры: ¬ х 1 ∧ х 2 ∨ х 1 ∧ ¬ х 2 ∨ х 1 ∧ ¬ х 2 ∧ х 3 , ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

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

Пример: (¬ х 1 ∧ х 2 ∧ х 3) ∨ (х 1 ∧ ¬ х 2 ∧ х 3) ∨ (х 1 ∧ х 2 ∧ ¬ х 3)

Совершенная конъюнктивная нормальная форма (СКНФ)

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

Примеры: ¬ х 3 , х 1 ∨ х 2 , х 1 ∨ х 2 ∨ ¬ х 3

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

КНФ записывается в следующей форме: F 1 ∧ F 2 ∧ ... ∧ F n , где F i - элементарная дизъюнкция

Примеры: (х 1 ∨ ¬ х 2) ∧ х 3 , (х 1 ∨ х 2) ∧ (¬ х 1 ∨ х 2 ∨ х 3) ∧ (х 1 ∨ ¬ х 2 ∨ ¬ х 3)

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

Пример: (х 1 ∨ х 2 ∨ х 3) ∧ (¬ х 1 ∨ ¬ х 2 ∨ х 3)

Заметим, что любую логическую функцию, не равную тождественно 0 или 1, можно представить в виде СДНФ или СКНФ .

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

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

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

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

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

Пример: Дана таблица истинности логической функции от трех переменных. Построить логическую формулу, реализующую эту функцию.

x	y	z	F (x, y, z)
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Т.к. на большинстве строк таблицы истинности значение функции равно 1, то построим СКНФ. В результате получим следующую логическую формулу:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Проверим полученную формулу. Для этого построим таблицу истинности функции.

x	y	z	¬ x	¬ x ∨ y ∨ z	¬ z	¬ x ∨ y ∨ ¬ z	F (x, y, z)
0	0	0	1	1	1	1	1
0	0	1	1	1	0	1	1
0	1	0	1	1	1	1	1
0	1	1	1	1	0	1	1
1	0	0	0	0	1	1	0
1	0	1	0	1	0	0	0
1	1	0	0	1	1	1	1
1	1	1	0	1	0	1	1

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

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

Элементарной дизъюнкцией называется выражение вида

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

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

Произвольная логическая функция, заданная аналитическим выражением, может быть приведена к КНФ путем выполнения следующих операций:

Использования правила инверсии, если операция отрицания применена к логическому выражению;

Использования аксиомы дистрибутивности относительно умножения:

Использования операции поглощения:

Исключения в дизъюнкциях повторяющихся переменных или их отрицаний;

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

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

Справедливость перечисленных операций вытекает из основных аксиом и тождественных соотношений алгебры логики.

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

Преобразование КНФ к совершенной КНФ осуществляется путем выполнения следующих операций:

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

Использования аксиомы дистрибутивности;

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

В совершенной КНФ может быть представлена любая логическая функция, кроме

тождественно равной единице (). Отличительным свойством совершенной КНФ является то, что представление в ней логической функции единственно.

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

Логическая функция константа нуля в совершенной КНФ представляется конъюнкцией 2nконституент нуля. Сформулируем правило составления СКНФ логической функции по таблице соответствия.

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

Пример 3.4. Для логической функции z(x), заданной таблицей соответствия 2.2, определим совершенную конъюнктивную форму.

Для первой строки таблицы, которая соответствует нулевому набору функции 000, находим конституенту нуля . Выполнив аналогичные операции для второй, третьей и пятой строк, определим искомую совершенную КНФ функции:

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

Определение 1. Конъюнктивным одночленом (элементарной конъюнкцией) от переменных называется конъюнкция этих переменных или их отрицаний.

Например , – элементарная конъюнкция.

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

Например , – элементарнаядизъюнкция.

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

Например, – ДНФ.

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

Например , – КНФ.

Для каждой формулы алгебры высказываний можно найти множество дизъюнктивных и конъюнктивных нормальных форм.

Алгоритм построения нормальных форм

С помощью равносильностей алгебры логики заменить все имеющиеся в формуле операции основными: конъюнкцией, дизъюнкцией, отрицанием:

Избавиться от знаков двойного отрицания.

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

2.6. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы

Любая булева функция может иметь много представлений в виде ДНФ и КНФ. Особое место среди этих представлений занимают совершенные ДНФ (СДНФ) и совершенные КНФ (СКНФ).

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

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

Определение 2. Совершенной дизъюнктивной нормальной формой (СДНФ) формулы алгебры высказываний называется ее ДНФ, обладающая следующими свойствами:

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

Конструктивно СКНФ для каждой формулы алгебры высказываний, приведенной к КНФ, можно определить следующим образом.

Определение 4. Совершенной конъюнктивной нормальной формой (СКНФ) данной формулы алгебры высказываний называется такая ее КНФ, которая удовлетворяет следующим свойствам.

Теорема 1. Каждая булева функция от переменных, не являющаяся тождественно ложной, может быть представлена в СДНФ, и притом единственным образом.

Способы нахождения СДНФ

1-й способ

2-й способ

выделяем строки, где формула принимает значение 1;

составляем дизъюнкцию конъюнкций при условии, что если переменная входит в конъюнкцию со значением 1, то записываем эту переменную, если со значением 0, то ее отрицание. Получаем СДНФ.

Теорема 2. Каждая булева функция от переменных, не являющаяся тождественно истинной, может быть представлена в СКНФ, и притом единственным образом.

Способы нахождения СКНФ

1-й способ – с помощью равносильных преобразований:

2-й способ – с помощью таблиц истинности:

выделяем строки, где формула принимает значение 0;

составляем конъюнкцию дизъюнкций при условии, что если переменная входит в дизъюнкцию со значением 0, то записываем эту переменную, если со значением 1, то ее отрицание. Получаем СКНФ.

Пример 1. Постройте КНФ функции .

Решение

Исключим связку «» с помощью законов преобразования переменных:

= /законы де Моргана и двойного отрицания/ =

/дистрибутивные законы/ =

Пример 2. Приведите к ДНФ формулу .

Решение

Выразим логические операции ичерез,и:

= /отнесем отрицание к переменным и сократим двойные отрицания/ =

= /закон дистрибутивности/ .

Пример 3. Запишите формулу в ДНФ и СДНФ.

Решение

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

Для построения СДНФ составим таблицу истинности для данной формулы:

Помечаем те строки таблицы, в которых формула (последний столбец) принимает значение 1. Для каждой такой строки выпишем формулу, истинную на наборе переменных ,,данной строки:

строка 1: ;

строка 3: ;

строка 5: .

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

Пример 4. Приведите формулу к СКНФ двумя способами:

а) с помощью равносильных преобразований;

б) с помощью таблицы истинности.

Решение:

Преобразуем вторую элементарную дизъюнкцию:

Формула имеет вид:

б) составим таблицу истинности для данной формулы:

Помечаем те строки таблицы, в которых формула (последний столбец) принимает значение 0. Для каждой такой строки выпишем формулу, истинную на наборе переменных ,,данной строки:

строка 2: ;

строка 6: .

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

Вопросы и задачи для самостоятельного решения

1. С помощью равносильных преобразований приведите к ДНФ формулы:

2. С помощью равносильных преобразований приведите к КНФ формулы:

3. С помощью второго дистрибутивного закона преобразуйте ДНФ в КНФ:

а) ;

4. Преобразуйте заданные ДНФ в СДНФ:

5. Преобразуйте заданные КНФ в СКНФ:

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

б) ;

Нормальная форма логической формулы не содержит знаков импликации, эквивалентности и отрицания неэлементарных формул.

Нормальная форма существует в двух видах:

конъюнктивная нормальная форма (КНФ) -- конъюнкция нескольких дизъюнкций, например, $\left(A\vee \overline{B}\vee C\right)\wedge \left(A\vee C\right)$;

дизъюнктивная нормальная форма (ДНФ) -- дизъюнкция нескольких конъюнкций, например, $\left(A\wedge \overline{B}\wedge C\right)\vee \left(B\wedge C\right)$.

СКНФ

Совершенная конъюнктивная нормальная форма (СКНФ) -- это КНФ, удовлетворяющая трем условиям:

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

ни одна из дизъюнкций не содержит одинаковых переменных;

каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ.

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

Правила построения СКНФ по таблице истинности

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

СДНФ

Совершенная дизъюнктивная нормальная форма (СДНФ) -- это ДНФ, удовлетворяющая трем условиям:

не содержит одинаковых элементарных конъюнкций;

ни одна из конъюнкций не содержит одинаковых переменных;

каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке.

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

Правила построения СДНФ по таблице истинности

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

Примеры нахождения СКНФ и СДНФ

Пример 1

Записать логическую функцию по ее таблице истинности:

Рисунок 1.

Решение:

Воспользуемся правилом построения СДНФ:

Рисунок 2.

Получим СДНФ:

Воспользуемся правилом построения СКНФ.

Стандартный базис. Элементарные формулы - литералы. Элементарная конъюнкция (дизъюнкция). Дизъюнктивная (конъюнктивная) нормальная форма и совершенная форма. Теорема: любая булева функция, отличная от 0 (от 1) представима в виде СДНФ (СКНФ). Полнота стандартного базиса. Примеры полных базисов: базис Жегалкина, штрих Шеффера, стрелка Пирса.

Стандартный базис - это набор из трех исходных операций булевой алгебры: сложения (объединения), умножения (пересечения) и отрицания.

Здесь мы будем называть литералом переменную x или ее отрицание x и обозначать xˆ. Булево пересечение нескольких литералов, определяемых различными переменными, т.е. выражение вида X = xˆ 1 xˆ 2 . . . xˆ л, называется элементарной конъюнкцией . Требование, чтобы все переменные были различны обусловливается следующим. Если в конъюнкцию входит несколько одинаковых литералов, то в силу коммутативности, ассоциативности и идемпотентности конъюнкции можно, переходя к эквивалентной формуле, оставить лишь один литерал (например, x 1 x 1 = x 1). Если в конъюнкцию входит переменная и ее отрицание, то формула эквивалентна константе 0, поскольку x x = 0 и для любой формулы Y имеем Y x x = 0.

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

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5 .

Если состав переменных в каждой элементарной конъюнкции данной ДНФ один и тот же, то ДНФ называется совершенной . Приведенный пример - это ДНФ, не являющаяся совершен- ной. Напротив, формула

x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4

есть совершенная форма.

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

Теорема 1.4. Любая булева функция, отличная от константы 0 представима в виде СДНФ.

◀Условимся под x σ понимать формулу x, если σ = 1, и формулу x , если σ = 0. Пусть функция f(y 1 , . . . , y n) принимает значение 1 на векторе (t 1 , . . . , t n) (такой вектор называют конституэнтой единицы ). Тогда элементарная конъюнкция также принимает значение 1 на этом наборе, но обращается в нуль на всех остальных n-мерных булевых векторах. Рассмотрим формулу

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

Нетрудно заметить, что формула Φ обращается в 1 при тех, и только при тех значениях переменных, при которых обращается в 1 рассматриваемая функция. Значит, формула Ψ представляет функцию f.

Следствие 1.1. Стандартный базис является полным.

◀ Действительно, если функция не является константой 0, то она представима либо в виде СДНФ, которая является формулой над стандартным базисом. Константу 0 можно представить, например, формулой f(x 1 , x 2 , . . . , x n) = x 1 x 1 .

Пример 1.2. Рассмотрим функцию трех переменных m(x 1 , x 2 , x 3) (табл. 1.4), называемую мажоритарной функциеи ̆. Эта функция принимает значение 1, если больше половины ее аргументов имеют значение 1. Поэтому ее часто называют функцией голосования. Построим для нее СДНФ.

Полнота стандартного базиса позволяет подбирать и другие полные системы функций. Полнота множества F может быть установлена из следующих соображений. Предположим, каждая из трех функций стандартного бузиса представима формулой над F . Тогда в силу теоремы 1.3 иножество F будет полным.

Пример 1.3. Множество из операций сложения по модулю 2, умножения и константы 1 называют базисом Жегалкина . Сложение по модулю 2 и умножение - базовые операции кольца Z2, выражения, составленные с их помощью - это многочлены над кольцом Z2. Кон- станта 1 в данном случае необходима для записи свободного члена. Поскольку xx = x, то все сомножители в многочлене имеют степень 1. Поэтому при записи многочлена можно обойтись без понятия степени. Примеры формул над базисом Жегалкина:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Любую такую формулу называют полиномом Жегалкина. Фактически полином Жегалкина - это многочлен над кольцом Z2.

Нетрудно сконструировать формулы над базисом Жегалкина, представляющие операции сложения и отрицания стандартного базиса (умножение у двух базисов общее):

x+y=x⊕y⊕xy, x =x⊕1.

Поэтому базис Жегалкина - полное множество.
Можно показать, что для любой булевой функции полином Жегалкина определен однозначно

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

Пример 1.4. Рассмотрим множество из единственной функции - штриха Шеффера*. Это множество полно, что следует из следующих легко проверяемых тождеств:

x =x|x, xy=x|y =(x|y)|(x|y), x+y=x |y =(x|x)|(y|y).

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

*Штрих Шеффера - бинарная, но не ассоциативная операция. Поэтому при использовании инфиксной формы следует быть внимательным: результат зависит от порядка выполнения операций. В этом случае рекомендуется явно указывать порядок операций при помощи скобок, например писать (x | y) | z, а не x | y | z, хотя обе формы равнозначны.