Стандартный базис. Элементарные формулы - литералы. Элементарная конъюнкция (дизъюнкция). Дизъюнктивная (конъюнктивная) нормальная форма и совершенная форма. Теорема: любая булева функция, отличная от 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, хотя обе формы равнозначны.
Определение 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. Для заданных логических формул постройте СДНФ и СКНФ двумя способами: с помощью равносильных преобразований и с помощью таблицы истинности.
б)
;
Конъюнктивная нормальная форма удобна для автоматического доказательства теорем . Любая булева формула может быть приведена к КНФ. Для этого можно использовать: закон двойного отрицания , закон де Моргана , дистрибутивность .
Энциклопедичный YouTube
-
1 / 5
Формулы в КНФ :
¬ A ∧ (B ∨ C) , {\displaystyle \neg A\wedge (B\vee C),} (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E) , {\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge (D\vee \neg E),} A ∧ B . {\displaystyle A\wedge B.}Формулы не в КНФ :
¬ (B ∨ C) , {\displaystyle \neg (B\vee C),} (A ∧ B) ∨ C , {\displaystyle (A\wedge B)\vee C,} A ∧ (B ∨ (D ∧ E)) . {\displaystyle A\wedge (B\vee (D\wedge E)).}Но эти 3 формулы не в КНФ эквивалентны следующим формулам в КНФ:
¬ B ∧ ¬ C , {\displaystyle \neg B\wedge \neg C,} (A ∨ C) ∧ (B ∨ C) , {\displaystyle (A\vee C)\wedge (B\vee C),} A ∧ (B ∨ D) ∧ (B ∨ E) . {\displaystyle A\wedge (B\vee D)\wedge (B\vee E).}Построение КНФ
Алгоритм построения КНФ
1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:
A → B = ¬ A ∨ B , {\displaystyle A\rightarrow B=\neg A\vee B,} A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B) . {\displaystyle A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \neg B).}2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:
¬ (A ∨ B) = ¬ A ∧ ¬ B , {\displaystyle \neg (A\vee B)=\neg A\wedge \neg B,} ¬ (A ∧ B) = ¬ A ∨ ¬ B . {\displaystyle \neg (A\wedge B)=\neg A\vee \neg B.}3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.
Пример построения КНФ
Приведем к КНФ формулу
F = (X → Y) ∧ ((¬ Y → Z) → ¬ X) . {\displaystyle F=(X\rightarrow Y)\wedge ((\neg Y\rightarrow Z)\rightarrow \neg X).}Преобразуем формулу F {\displaystyle F} к формуле, не содержащей → {\displaystyle \rightarrow } :
F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ ¬ Y ∨ Z) ∨ ¬ X) . {\displaystyle F=(\neg X\vee Y)\wedge (\neg (\neg Y\rightarrow Z)\vee \neg X)=(\neg X\vee Y)\wedge (\neg (\neg \neg Y\vee Z)\vee \neg X).}В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:
F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X) . {\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\wedge \neg Z)\vee \neg X).}Например, следующая формула записана в 2-КНФ:
(A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C) . {\displaystyle (A\lor B)\land (\neg B\lor C)\land (B\lor \neg C).}Пример. Найти КНФ формулы
~
~ 
Совершенную дизъюнктивную нормальную форму СДНФ можно строить, используя следующий алгоритм:
1. = 1. алгоритма ДНФ
2. = 2. алгоритма ДНФ
3. = 3. алгоритма ДНФ
4. = 4. алгоритма ДНФ
5. Опустить тождественно ложные слагаемые, т. е. слагаемые вида
6. Пополнить оставшиеся слагаемые недостающими переменными
7. Повторить пункт 4.
Пример. Найти СДНФ формулы.
~ 
Для построения СКНФ можно пользоваться следующей схемой:
Пример. Найти СДНФ формулы.
~ 
Известно (теоремы 2.11, 2.12), что СДНФ и СКНФ определены формулой однозначно и, значит, их можно строить по таблице истинности формулы .
Схема построения СДНФ и СКНФ по таблице истинности приведена ниже, для формулы
~ :
~
1 0 1 0 1 1 0 1 СДНФ; СКНФ. 2.2. Задание.
2.2.1 Ниже приведены логические выражения. Максимально упростите выражения своего варианта, воспользовавшись законами логики Буля. Затем с помощью таблиц истинности сравните ваше упрощенное выражение с исходным.
2.2.2. Выяснить вопрос о равносильности f 1 и f 2 путем сведения их к СДНФ (табл. 1).
2.2.3. Найти двойственную функцию для f 3 по обобщенному и булевому принципу (табл.1). Сравнить полученные результаты.
№ f 1 f 2 f 3 
2.3. Контрольные вопросы.
2.3.1. Дайте определение высказывания.
2.3.2. Перечислите основные операции над высказыванием.
2.3.3. Что такое таблица истинности?
2.3.4. Составить таблицы истинности для следующих формул:
~ ~
~ ;2.3.5. Учитывая соглашения о порядке выполнения операций, опустить «лишние» скобки и знак « » в формулах:
;2.3.6. Применяя равносильные преобразования, доказать тождественную истинность формул:
2.3.7. Найти двойственные формулы:
)
2.3.8. Привести к совершенной ДНФ (СДНФ) форме следующие формулы:
~ 2.3.9. Привести к совершенной КНФ (СКНФ) форме следующие формулы:
~ 
Лабораторная работа № 3
Тема: «Минимизация булевых функций. Логические схемы»
Цель: Приобретение практических навыков работы с методами минимизации булевых функций.
3.1. Теоретические сведения .
Минимальные формы
Как было показано в , любая булева функция представима в совершенной нормальной форме (дизъюнктивной или конъюнктивной). Более того, такое представление является первым шагом перехода от табличного задания функции к ее аналитическому выражению. В дальнейшем будем исходить из дизъюнктивной формы, а соответствующие результаты для конъюнктивной формы получается на основе принципа двойственности .
Каноническая задача синтеза логических схем в булевом базисе сводится к минимизации булевых функций, т.е. к представлению их в дизъюнктивной нормальной форме, которая содержит наименьшее число букв (переменных и их отрицаний). Такие формы называют минимальными. При каноническом синтезе предполагается, что на входы схемы подаются как сигналы , так и их инверсий .
Формула, представленная в дизъюнктивной нормальной форме, упрощается многократными применением операции склеивания и операции поглощения и (дуальные тождества для конъюнктивной нормальной формы имеют вид: и ). Здесь под и можно понимать любую формулу булевой алгебры. В результате приходим к такому аналитическому выражению, когда дальнейшие преобразования оказываются уже невозможными, т.е. получаем тупиковую форму.
Среди тупиковых форм находится и минимальная дизъюнктивная форма, причем она может быть неединственной. Чтобы убедиться в том, что данная тупиковая форма является минимальной, необходимо найти все тупиковые формы и сравнить их по числу входящих в них букв.
Пусть, например, функция задана в совершенной нормальной дизъюнктивной форме:
Группируя члены и применяя операцию склеивания, имеем .
При другом способе группировки получим:
Обе тупиковые формы не являются минимальными. Чтобы получить минимальную форму, нужно догадаться повторить в исходной формуле один член (это всегда можно сделать, так как ). В первом случае таким членом может быть . Тогда . Добавив член , получим: . Перебрав все возможные варианты, можно убедиться, что две последние формы являются минимальными.
Работа с формулами на таком уровне подобна блужданию в потемках. Процесс поиска минимальных форм становится более наглядным и целеустремленным, если использовать некоторые графические и аналитические представления и специально разработанную для этой цели символику.
Многомерный куб
Каждой вершине -мерного куба можно поставить в соответствие конституенту единицы. Следовательно, подмножество отмеченных вершин является отображением на -мерном кубе булевой функции от переменных в совершенной дизъюнктивной нормальной форме. На рис. 3.1 показано такое отображение для функции из п.3.7.
Рис.3.1 Отображение на трехмерном кубе функции, представленной в СДНФ
Для отображения функции от переменных, представленной в любой дизъюнктивной нормальной форме, необходимо установить соответствие между ее минитермами и элементами -мерного куба.
Минитерм ( -1)-го ранга можно рассматривать как результат склеивания двух минитермов -го ранга (конституент единицы), т.е.
, На -мерном кубе это соответствует замене двух вершин, которые отличаются только значениями координаты , соединяющим эти вершины, ребром (говорят, что ребро покрывает инцидентные ему вершины). Таким образом, минитермам ( -1)-го порядка соответствуют ребра -мерного куба. Аналогично устанавливается соответствие минитермов ( -2)-го порядка - граням -мерного куба, каждая из которых покрывает четыре вершины (и четыре ребра).Элементы -мерного куба, характеризующиеся измерениями, называют -кубами. Так, вершины являются 0-кубами, ребра – 1-кубами, грани – 2-кубами и т.д. Обобщая приведенные рассуждения, можно считать, что минитерм ()-го ранга в дизъюнктивной нормальной форме для функции переменных отображается -кубом, причем каждый -куб покрывает все те -кубы низшей размерности, которые связаны с его вершинами. В качестве примера на рис. 3.2 дано отображение функции трех переменных. Здесь минитермы и соответствуют 1-кубам (), а минитерм отображается 2-кубом ().
Рис.3.2 Покрытие функции
Итак, любая дизъюнктивная нормальная форма отображается на -мерном кубе совокупностью -кубов, которые покрывают все вершины, соответствующие конституентам единицы (0-кубы). Справедливо и обратное утверждение: если некоторая совокупность -кубов покрывает множество всех вершин, соответствующих единичным значениям функции, то дизъюнкция соответствующих этим -кубам минитермов является выражение данной функции в дизъюнктивной нормальной форме. Говорят, что такая совокупность -кубов (или соответствующих им минитермов) образует покрытие функции.
Стремление к минимальной форме интуитивно понимается как поиск такого покрытия, число -кубов которого было бы поменьше, а их размерность - побольше. Покрытие, соответствующее минимальной форме, называют минимальным покрытием. Например, для функции покрытие на рис. 3.3 соответствует минимальным формам
и 
.
Рис. 3.3 Покрытия функции .
слева –
; справа
– 
Отображение функции на -мерном кубе наглядно и просто при . Четырехмерный куб можно изобразить, как показано на рис. 3.4, где отображены функция четырех переменных и ее минимальное покрытие, соответствующее выражению 
. Использование этого метода при требует настолько сложных построений, что теряется все его преимущества.Рис. 3.4 Отображение функции
на четырехмерном кубеКарты Карно
В другом методе графического отображения булевых функций используются карты Карно , которые представляют собой специально организованные таблицы соответствия. Столбцы и строки таблицы соответствуют всевозможным наборам значений не более двух переменных, причем эти наборы расположены в таком порядке, что каждый последующий отличается от предыдущего значением только одной из переменных. Благодаря этому и соседние клетки таблицы по горизонтали и вертикали отличаются значением только одной переменной. Клетки, расположенные по краям таблицы, также считаются соседними и обладают этим свойством. На рис. 3.5 показаны карты Карно для двух, трех, четырех переменных.
Рис. 3.5 Карты Карно для двух, трех и четырех переменных
Как и в обычных таблицах истинности, клетки наборов, на которых функция принимает значение 1, заполняются единицами (нули обычно не вписываются, им соответствуют пустые клетки). Например, на рис. 3.6, а показана карта Карно для функции, отображение которой на четырехмерном кубе дано на рис. 3.4. Для упрощения строки и столбцы, соответствующие значениям 1 для некоторой переменной, выделяются фигурной скобкой с обозначением этой переменной.
Рис. 3.6 Отображение на карте Карно функции четырех переменных
(а) и ее минимального покрытия (б)
Между отображениями функции на n -мерном кубе и на карте Карно имеет место взаимно-однозначное соответствие. На карте Карно s -кубу соответствует совокупность 2 соседних клеток, размещенных в строке, столбце, квадрате или прямоугольнике (с учетом соседства противоположных краев карты). Поэтому все положения, изложенные в выше (см. п. многомерный куб ), справедливы для карт Карно. Так, на рис. 3.6, б показано покрытие единиц карты, соответствующее минимальной дизъюнктивной форме
рассматриваемой функции.Считывание минитермов с карты Карно осуществляется по простому правилу. Клетки, образующие s -куб, дают минитер (n–s) -го ранга, в который входят те (n–s) переменные, которые сохраняют одинаковые значения на этом s -кубе, причем значении 1 соответствуют сами переменные, а значениям 0 – их отрицания. Переменные, которые не сохраняют свои значения на s -кубе, в минитерме отсутствуют. Различные способы считывания приводят к различным представлениям функции в дизъюнктивной нормальной форме (крайняя правая является минимальной) (рис. 3.7).
Использование карт Карно требует более простых построений по сравнению с отображением на n -мерном кубе, особенно в случае четырех переменных. Для отображения функций пяти переменных используется две карты Карно на четыре переменные, а для функции шести переменных – четыре таких карты. При дальнейшем увеличении числа переменных карты Карно становятся практически непригодными.
Известные в литературе карты Вейча отличаются только другим порядком следования наборов значений переменных и обладают теми же свойствами, что и карты Карно.
Комплекс кубов
Несостоятельность графических методов при большом числе переменных компенсируется различными аналитическими методами представления булевых функций. Одним из таких представлений является комплекс кубов , использующий терминологию многомерного логического пространства в сочетании со специально разработанной символикой.
). 0-кубы, соответствующие конституентам единицы, представляются наборами значений переменных, на которых функция равна единице. Очевидно, в записи
Рис. 3.8 Комплекс кубов функции трех переменных (а ) и его символическое представление (б )
Комплекс кубов образует максимальное покрытие функции . Исключая из него все те s -кубы, которые покрываются кубами высшей размерности, получаем покрытия, соответствующие тупиковым формам. Так, для рассматриваемого примера (рис. 3.8) имеем тупиковое покрытие
,которое соответствует функции
. В данном случае это покрытие является и минимальным.Для двух булевых функций операция дизъюнкции соответствует объединению их комплексов кубов , а операция конъюнкции - пересечению комплексов кубов . Отрицанию функции соответствует дополнение комплекса кубов, т. е. , причем определяется всеми вершинами, на которых функция принимает значение 0. Таким образом, имеет место взаимно-однозначное соответствие (изоморфизм) между алгеброй булевых функций и булевых множеств, представляющих комплексы кубов.
Представление функции в виде комплексов кубов менее наглядно, однако его важнейшие достоинства состоят в том, что снимаются ограничения по числу переменных и облегчается кодирование информации при использовании вычислительных машин.
Минимизация булевых функций
Постановка задачи. Минимизация схемы в булевом базисе сводится к поиску минимальной дизъюнктивной формы, которой соответствует минимальное покрытие. Общее число букв, входящих в нормальную форму, выражается ценой покрытия
, где - число - кубов, образующих покрытие данной функции от п переменных. Минимальное покрытие характеризуется наименьшим значением его цены.Обычно задача минимизации решается в два шага. Сначала ищут сокращенное покрытие, которое включает все -кубы максимальной размерности, но не содержит ни одного куба, покрывающегося каким-либо кубом этого покрытия. Соответствующею дизъюнктивную нормальную форму называют сокращенной, а ее минитермы - простыми импликантами. Для данной функции сокращенное покрытие является единственным, но оно может быть избыточным вследствие того, что некоторые из кубов покрываются совокупностями других кубов.
На втором шаге осуществляется переход от сокращенной к тупиковым дизъюнктивным нормальным формам, из которых выбираются минимальные формы. Тупиковые формы образуются путем исключения из сокращенного покрытия всех избыточных кубов, без которых оставшаяся совокупность кубов еще образует покрытие данной функции, но при дальнейшем исключении любого из кубов она уже не покрывает множества всех вершин, соответствующих единичным значениям функции, т. е. перестает быть покрытием.
Куб сокращенного покрытия, который покрывает вершины данной функции, не покрываемые никакими другими кубами, не может оказаться избыточным и всегда войдет в минимальное покрытие. Такой куб, как и соответствующая ему импликанта, называют экстремалью (существенной импликантой), а покрываемые им вершины - отмененными вершинами. Множество экстремалей образует ядро покрытия, ясно, что при переходе от сокращенного покрытия к минимальному прежде всего следует выделить все экстремали. Если множество экстремалей не образует покрытия, то оно дополняется до покрытия кубами из сокращенного покрытия.
Приведенные определения иллюстрируются на рис. 3.9, где сокращенное покрытие (см. рис. 3.9а,) и минимальные покрытия (рис. 3.9б) и (см. рис. 3.9, б) выражаются следующим образом.
Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний. Для каждой функции логики высказываний можно составить таблицу истинности. Обратная задача тоже всегда разрешима. Введем несколько определений.
Элементарными конъюнкциями (конъюнктами) называются конъюнкции переменных или их отрицаний, в которых каждая переменная встречается не более
одного раза.
Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнкций.
Элементарными дизъюнкциями (дизъюнктами) называются дизъюнкции переменных с отрицаниями или без них.
Конъюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнкций.
Для каждой функции алгебры высказываний можно найти множество дизъюнктивных и конъюнктивных нормальных форм.
Алгоритм построения ДНФ:
1. Перейти к булевым операциям, используя формулы эквивалентных преобразований.
2. Перейти к формулам с тесными отрицаниями, то есть к формуле, в которой отрицания располагаются не выше, чем над переменными – применить законы де Моргана.
3. Раскрыть скобки – применить законы дистрибутивности.
4. Повторяющиеся слагаемые взять по одному разу – закон идемпотентности.
5. Применить законы поглощения и полупоглощения.
Пример 6. Найти ДНФ формулы: .
В алгебре Буля справедлив принцип двойственности . Он заключается в следующем.
Функция называется двойственной к функции , если . Т.е. для нахождения функции, двойственной к заданной, необходимо построить отрицание функции от отрицаний аргументов.
Пример 7. Найти функцию, двойственную к .
Среди элементарных функций алгебры логики 1 двойственна 0 и наоборот, х двойственна х, двойственна , двойственна и наоборот.
Если в формуле F 1 представляющей функцию все конъюнкции заменить
на дизъюнкции, дизъюнкции на конъюнкции, 1 на 0, 0 на 1, то получим формулу F * , представляющую функцию * , двойственную .
Конъюнктивная нормальная форма (КНФ) – двойственное для ДНФ понятие, поэтому ее легко построить по схеме:
Пример 8. Найти КНФ формулы: .
Воспользовавшись результатом примера 6, имеем
Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы. В каждом из типов нормальных форм (дизъюнктивных и конъюнктивных) можно выделить класс совершенных форм СДНФ и СКНФ.
Совершенной элементарной конъюнкцией называется логическое произведение всех переменных с отрицанием или без них, причем, каждая переменная входит в произведение только один раз.
Всякую ДНФ можно привести к СДНФ расщеплением конъюнкций, которые содержат не все переменные, т.е. добавлением для отсутствующей переменной x i множится с применением закона дистрибутивности
Пример 9. Найти СДНФ для ДНФ примера 6
Совершенной элементарной дизъюнкцией называется логическая сумма всех переменных с отрицаниями или без них, причем, каждая переменная входит в сумму только один раз.
Всякую КНФ можно привести к СКНФ, добавляя член конъюнкции, не содержащий какой – либо переменной X i конъюнкцией и применяя дистрибутивный закон
Пример 10 . Привести КНФ к СКНФ:
Для построения СКНФ можно воспользоваться схемой
Пример 11. Найти СКНФ для формулы примера 6.
Всякая функция имеет СДНФ и, притом, единственную . Каждая функция имеет СКНФ и, притом, единственную .
Т.к. СДНФ и СКНФ определены формулами однозначно, их можно строить по таблице истинности формулы.
Для построения СДНФ необходимо выделить строки, в которых F принимает значение 1 и записать для них совершенные элементарные конъюнкции. Если значение переменной в нужной строке таблицы истинности равно единице, то в совершенном конъюнкте она берется без отрицания, если нулю – то с отрицанием. Затем совершенные конъюнкты (их число равно числу единиц в таблице) соединяются знаками дизъюнкции.
Для построения СКНФ по таблице истинности необходимо выделить в ней строки, где F=0, и записать совершенные элементарные дизъюнкции, после чего соединить их знаками конъюнкции. Если в требуемой строке таблицы истинности (F=0) значение переменной соответствует нулю, то в совершенном дизъюнкте она берется без отрицания, если единице – то с отрицанием.
Пример 12. Найти СДНФ и СКНФ по таблице истинности для формулы примера 6.
В таблице 14 приведено лишь конечное значение F=10101101. В справедливости этого утверждения следует убедиться самостоятельно, построив развернутую таблицу истинности.
Таблица 14
x y z