Файл: Учебника по курсу Основы дискретной математики и логики.pdf

Конъюнкция считается самой сильной операцией. При отсутствии скобок она выполняется в первую очередь. Операция дизъюнкции имеет больший приоритет, чем операция импликации. В свою очередь, импликация считается сильнее эквивалентности.
Знак отрицания над формулой играет роль скобок и позволяет не заключать в скобки стоящее под ним выражение.
Одна и та же функция алгебры логики может быть задана различными формулами.
От формульного задания функции всегда можно перейти к ее табличному заданию. И наоборот, если функция задана таблицей, то можно построить формулу, выражающую данную функцию.
Слайд 122
Рассмотрим пример построения таблицы булевой функции, заданной формулой.
Выпишем в таблицу под символами переменных все наборы значений, которые эти переменные принимают, а под символами булевых операций запишем значения функций, соответствующие этим наборам. Ниже символов булевых функций написаны номера столбцов, над которыми производится действие.
Исходя из правил приоритета операций, сначала строим столбец значений функции отрицания, которая принимает значения, противоположные значениям переменной x[икс]. Следующей будет операция конъюнкции, которая дает значение нуль, если хотя бы одна переменная равна нулю. Далее выполняется операция дизъюнкции для четвертого и пятого столбцов. В последнюю очередь выполняется операция импликации, которая и дает значения функции f[эф].
Слайд 123
Рассмотрим еще один пример построения таблицы булевой функции, которая является суперпозицией двух функций от трех переменных.

Распишем полностью таблицу истинности функций f
1
и f
2
, чтобы видеть все наборы переменных. Функция h[аш] является функцией двух переменных, поэтому достаточно рассмотреть четыре набора значений для переменных x[икс] и y[игрек].
Рассмотрим первый набор значений переменных для функции h[аш], это будет набор (0, 0)[ноль ноль]. Определяем значение функции f
1
на соответствующем наборе с помощью ее таблицы истинности. Оно равно единице, а значит, набор, на котором требуется вычислить значение функции
f
2
, есть (0, 0, 1)[ноль ноль один]. Определяем по таблице ее значение на рассматриваемом наборе. Полученное значение единица и является искомым значением функции h[аш].
Проделываем такие же операции для оставшихся трех наборов. На каждом из них функции h[аш] принимает значение 1. Выписываем окончательный результат.
Слайд 124
Рассмотрим основные свойства элементарных функций. Основная их часть уже известна вам из алгебры высказываний. Но здесь добавляются новые свойства, поскольку появились новые функции – сложение по модулю два, штрих Шеффера и стрелка Пирса.
Как видно на слайде, свойством идемпотентности обладают только операции конъюнкции и дизъюнкции. Свойством коммутативности, помимо операций конъюнкции и дизъюнкции, обладают еще четыре операции – сложение по модулю два, эквивалентность, штрих Шеффера и стрелка Пирса.
Из семи важнейших булевых функций данное свойство не присуще только импликации. Свойством ассоциативности обладают четыре операции – конъюнкция, дизъюнкция, сложение по модулю два и эквивалентность.
Свойство ассоциативности позволяет не ставить скобки в выражениях, представляющих собой конъюнкцию или дизъюнкцию нескольких булевых переменных. То же самое касается суммы по модулю два и эквивалентности.

Конъюнкция обладает свойством дистрибутивности относительно дизъюнкции и сложения по модулю два. Дизъюнкция обладает свойством дистрибутивности относительно конъюнкции. На слайде представлены формульные выражения указанных свойств.
Свойство инволюции состоит в том, что двукратное применение операции отрицания к переменной x[икс] приводит снова к переменной
x[икс]. Законы де Моргана устанавливают связь между операциями дизъюнкции и конъюнкции.
Все перечисленные здесь равенства доказываются с помощью определений соответствующих функций и их таблиц истинности. Обоснуем, например, свойство 4а. Левая часть равенства обращается в единицу только тогда, когда по крайней мере две переменные принимают значение один. То же самое можно сказать и про правую часть равенства. Таким образом, функции, задаваемые формулами в левой и правой частях рассматриваемого равенства, совпадают.
Слайд 125
На данном слайде приводится еще несколько свойств булевых функций.
Первый представленный здесь блок свойств можно охарактеризовать как законы действий с нулем и единицей. Исходя из таблицы истинности функции дизъюнкции, можно утверждать, что присутствие нуля в дизъюнкции не играет роли, а появление единицы делает всю дизъюнкцию равной единице. И наоборот, наличие единицы в конъюнкции не играет роли, а присутствие нуля приводит к тому, что вся конъюнкция обращается в ноль. В сумме по модулю два не играет роли наличие нуля, а прибавление единицы изменяет значение выражения на противоположное.
Важное значение имеет третий блок свойств, с помощью которых одна из булевых функций выражается через другие булевы функции.

Представленные на слайде законы склеивания и поглощения доказываются с помощью свойств дистрибутивности.
Отметим, что все перечисленные свойства булевых функций останутся справедливыми, если вместо участвующих в них переменных подставить любые формулы. При этом, естественно, предполагается, что одна и та же переменная всюду заменяется на одну и ту же формулу.
Свойства булевых функций позволяют упрощать формулы.
Слайд 126
Покажем на примере, как свойства булевых функций используются для упрощения формул.
Обратимся к задаче, представленной на слайде. Исходное выражение представляет собой дизъюнкцию пяти элементов. Для ее упрощения на первом этапе применяем закон де Моргана. В результате появляются две одинаковые конъюнкции, и по закону идемпотентности одну из них можно убрать. В получившемся выражении ко второй и четвертой конъюнкциям можно применить закон склеивания. Результатом склеивания является переменная z[зет].
Итак, мы получили дизъюнкцию трех элементов. Теперь ко второму и третьему ее элементам применяем закон дистрибутивности, и во вторых скобках получается единица, которая в конъюнкции не играет роли. Остается еще раз применить закон склеивания.
Отметим, что изложенный способ упрощения данной формулы не является единственно возможным.
Слайд 127
Тема 4.3. Нормальные формы. Понятия тупиковой, минимальной и сокращенной ДНФ.
Методы получения сокращенной и минимальной ДНФ
Далее рассмотрим специальные виды булевых функций.

Простой, или элементарной, конъюнкцией называется конъюнкция одной или нескольких переменных, при этом каждая переменная встречается не более одного раза – либо она сама, либо ее отрицание.
Дизъюнктивной нормальной формой, далее ДНФ[дэ эн эф], называется дизъюнкция различных простых конъюнкций.
Совершенной дизъюнктивной нормальной формой, далее СДНФ[эс дэ эн эф], называется такая дизъюнктивная нормальная форма, у которой в каждую конъюнкцию входят все переменные данного списка, либо сами, либо их отрицания, причем в одном и том же порядке.
Если заменить в приведенных выше определениях конъюнкцию на дизъюнкцию, а дизъюнкцию – на конъюнкцию, то получим определения простой дизъюнкции, конъюнктивной нормальной формы и совершенной конъюнктивной нормальной формы. Для двух последних понятий в дальнейшем будут использоваться сокращения КНФ[ка эн эф] и СКНФ[эс ка эн эф].
На слайде представлены примеры функций указанных видов. Третье выражение является дизъюнктивной нормальной формой, но не совершенной, так как первая простая конъюнкция не содержит переменные
y[игрек] и z[зет], а вторая – переменную х[икс].
Для перехода от КНФ[ка эн эф] к ДНФ[дэ эн эф] или наоборот используются законы дистрибутивности.
Слайд 128
Остановимся на задачах перехода от одной нормальной формы к другой.
Пусть нам нужно осуществить переход от ДНФ[дэ эн эф] к СДНФ[эс дэ эн эф]. Так как нам дана нормальная форма, не являющая совершенной, то в некоторой конъюнкции не хватает переменной и необходимо ее добавить.
Для этого в конъюнкцию добавляем единицу в соответствии с законами нуля и единицы. Добавленную единицу представляем в виде дизъюнкции

переменной и ее отрицания. После этого применяем закон дистрибутивности.
В конце преобразований при необходимости применяем закон идемпотентности.
Аналогично, для перехода от КНФ к СКНФ в неполную дизъюнкцию добавляем нуль, который представляем в виде конъюнкции переменной и ее отрицания. Применяя законы дистрибутивности и идемпотентности, получаем окончательный результат.
Всякую отличную от нуля функцию можно представить в виде СДНФ с помощью ее таблицы истинности. Для этого нужно взять наборы, для которых функция принимает значение один, и составить по ним простые конъюнкции по следующему правилу. Если итая переменная равна нулю, то включаем ее в конъюнкцию с отрицанием. Если итая переменная принимает значение один, то включаем ее в простую конъюнкцию. Составляя дизъюнкцию этих простых конъюнкций, придем к СДНФ.
Аналогично, с помощью таблицы истинности можно для любой отличной от единицы функции составить ее СКНФ. В этом случае нам понадобятся наборы значений переменных, на которых функция принимает нулевое значение, причем если переменная принимает значение один, то записываем ее с отрицанием, в противном случае – без отрицания.
Таким образом, любую логическую функцию можно выразить через три логические функции – конъюнкцию, дизъюнкцию и отрицание.
Приведенные правила позволяют для любой таблично заданной функции написать ее формулу. На практике часто возникает необходимость получить вместо СДНФ как можно более «короткую» ДНФ.
Слайд 129
Словам «короткая дизъюнктивная нормальная форма» можно придать разный смысл.
Элементарная конъюнкция Е[е] называется импликантой булевой функции f[эф], если импликация «из E[е] следует f[эф]» тождественно равна

единице. Исходя из определения импликации, получаем, что если на некотором наборе значений переменных функция f[эф] принимает значение один, то и импликация на этом наборе принимает значение один.
Определение простой импликанты булевой функции представлено на слайде. Здесь же приведено определение ядровой импликанты.
Сокращенной дизъюнктивной нормальной формой называется ДНФ, состоящая из всех простых импликант данной булевой функции.
Тупиковой дизъюнктивной нормальной формой функции называется такая ее ДНФ, состоящая из простых импликант, что удаление из нее любой конъюнкции нарушает равносильность ДНФ данной функции. Другими словами, в тупиковую ДНФ входят только ядровые импликанты.
Минимальная дизъюнктивная нормальная форма данной функции – это
ДНФ, имеющая наименьшее число символов переменных из всех ДНФ, задающих функцию.

Первым подходящим набором является набор из четырех нулей. Ему соответствует конъюнкция
[не икс, не игрек, не зет, не тэ]. Следующий набор – 0-0-0-1[ноль, ноль, ноль, один], ему соответствует конъюнкция
[не икс, не игрек, не зет, тэ]. Аналогичным образом записываем простые конъюнкции для остальных наборов. Дизъюнкция составленных простых конъюнкций дает совершенную дизъюнктивную нормальную форму.
Построим также совершенную конъюнктивою нормальную форму. Как мы говорили ранее, для этого берем нулевые наборы функции, т. е. наборы, на которых функция принимает значение нуль. Таких наборов у данной функции шесть. Для каждого такого набора записываем элементарную дизъюнкцию, которая, исходя из определения совершенной формы, будет содержать все четыре переменные. Если переменная принимает значение один, то записываем ее с отрицанием.
Таким образом, первый нулевой набор – это набор 0-0-1-0[нуль, нуль, один, нуль]. Ему соответствует элементарная дизъюнкция
[икс дизъюнкция игрек дизъюнкция не зет дизъюнкция тэ]. Аналогично составляем элементарные дизъюнкции для оставшихся пяти нулевых наборов. Конъюнкция этих элементарных дизъюнкций дает нам совершенную конъюнктивную форму.
Слайд 131
Основным методом минимизации логических функций, представленных в виде совершенных форм, является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами – членами, содержащими одинаковые переменные, вхождения которых – прямые и инверсные, совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке.