Представление логических выражений в дизьюнктивной (коньюнктивной) нормальной форме. Теорема Шеннона и принцип двойственности.

Разложение логических (булевых) функций по переменным. Дизъюнктивная и конъюнктивная нормальные формы. Бывают случаи, когда формула принимает на всех наборах значение true (1). Если обратиться к смыслу, заключенном в таком сложном высказывании, то получается, что факт, к которому мы пришли в результате рассуждений, является неопровержимой истиной. Напротив, если сложное высказывание, построенное нами из простых высказываний, всегда ложно, это означает, что наше рассуждение привело к противоречию.

a	b	a×b

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

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

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

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

Чтобы перейти к представлению логических формул через ДНФ (КНФ) сначала рассмотрим так называемое разложение булевой функции по переменным. Введем следующее обозначение

Теорема(Шеннона). Каждую булеву функцию f(x₁,x₂,…,x_n) при любом 1£ m £ n можно представить в виде:

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

Для доказательства достаточно проверить эквивалентность правой и левой части.

Давайте посмотрим для одной переменной. Получим следующее.

Если f(x₁,x₂,…,x_n)= 0 при значении x ₁ = 1, то первая элементарная конъюнкция равна нулю. Если же функция принимает значение 1 при x ₁=0, то мы умножаем ее на отрицание x ₁, то есть на 1. Поскольку дизъюнкция принимает значение 0 (false) только если оба операнда ложны, а во всех остальных случаях она истинна, в логической сумме можно оставить один операнд, при котором f(x₁,x₂,…,x_n)= 1. Отсюда получаем: Проделав такое разложение последовательно для всех остальных переменных, получим выражение

Таким образом, при m=n мы приходим к представлению, у которого в правой части стоят значения функции на конкретных двоичных наборах, а именно тех, которые соответствуют значениям f(s₁,s₂,…,s_n)= 1. Тогда мы можем в элементарных конъюнкциях полученного разложения опустить операнд f(s₁,s₂,…,s_n) и оставить только :

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

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

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

Из таблицы видно, что на наборах «антипеременных» , мы получаем значения , соответствующие дизъюнкции этих «антипеременных». То есть = является так называемой двойственной функцией по отношению к a×b. Заметим сразу, что понятие двойственной функции в общем случае не равносильно введенному раньше понятию «антиоперации».

Функция, двойственная к некоторой функции f, получается заменой всех переменных на их отрицания и самой функции f на ее отрицание. Двойственную функцию для f будем обозначать f*. То есть и . Функция, у которой двойственная функция на одинаковых наборах переменных принимает те же самые значения, называется самодвойственной. Пример самодвойственной функции: a × b Ú b × c Ú a × c.

Итак, мы выяснили, что . Можно показать точно так же, что .(эти соотношения, вытекающие из принципа двойственности, называются законами де Моргана.)

В качестве примера получим СДНФ и СКНФ для логической функции, (таблица истинности кот. в 1вопросе). Эта функция принимает значение 1 на двух наборах: { a =1, b =0, c =0} и { a =0, b =1, c =0}. Отсюда получаем следующее представление для функции в совершенной дизъюнктивной нормальной форме.

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