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


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





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

~ ~

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

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, б) выражаются следующим образом.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

    конъюнктивная нормальная форма (КНФ) -- конъюнкция нескольких дизъюнкций, например, $\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.

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

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

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


Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск


Лекция 1.хх

Нормальные формы логических функций

Представление булевой функции в форме дизъюнкции конъюнктивных термов (конституент единицы) K i

, (2.7)

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

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

С учётом сказанного выше из теоремы 2.1 вытекает следующая теорема.

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

Пример 3. Пусть имеем таблично заданную функцию f (x 1 , x 2 , x 3 ) (табл. 10).

Таблица 10

f (x 1 , x 2 , x 3 )

На основании формулы (2.6) получаем:

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

Представление булевой функции в форме конъюнкции дизъюнктивных термов (конституент нуля) D i

, (2.8)

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

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

Теорема 3. Любая булева функция (не равная тождественно 1 ) может быть представлена в СКНФ , причём такое представление единственно .

Доказательство теоремы может быть проведено аналогично доказательству теоремы 2.1 на основании следующей леммы Шеннона о конъюнктивном разложении.

Лемма Шеннона . Любая булева функция f (x 1 , x 2 , …, x m ) от m переменных может быть представлена так :

. (2.9)

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

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

Пример 4. Для функции f (x 1 , x 2 , x 3 ), заданной табл. 10, написать её СКНФ.

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

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

Пример 5. Для функции f (x 1 , x 2 , x 3 ), заданной табл. 10, попробовать перейти от СДНФ к СКНФ.

Используя результат примера 2.3 получим:

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

т. к. содержит все макстермы, которых нет в выражении для СКНФ рассматриваемой функции.

1. Используя свойства операций (см. табл. 9) тождественность (), сумма по модулю 2 (), импликация (), переходим к операциям И, ИЛИ, НЕ (в базис Буля).

2. Используя свойства отрицания и законы де Моргана (см. табл. 9) добиваемся, чтобы операции отрицания относились только к отдельным переменным, а не к целым выражениям.

3. Используя свойства логических операций И и ИЛИ (см. табл. 9), получаем нормальную форму (ДНФ или КНФ).

4. При необходимости переходим к совершенным формам (СДНФ или СКНФ). Например, для получения СКНФ часто нужно использовать свойство: .

Пример 6. Преобразовать в СКНФ логическую функцию

Выполняя по порядку шаги приведённого выше алгоритма, получим:

Используя свойство поглощения, получим:

Таким образом, мы получили КНФ функции f (x 1 , x 2 , x 3 ). Чтобы получить её СКНФ, нужно каждую дизъюнкцию, в которой не хватает какой-либо переменной, повторить дважды – с этой переменной и с её отрицанием:

2.2.6. Минимизация логических функций

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

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

Метод Квайна

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

, (2.10)

а затем поглощения

, (2.11)

и эта пара этапов применяется многократно. Таким образом, удаётся снизить ранг термов. Это процедура повторяется до тех пор, пока не останется ни одного терма, допускающего склеивание с каким-либо другим термом.

Заметим, что левую часть уравнения (2.10) сразу можно было минимизировать более простым и очевидным способом:

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

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

Метод карт Карно

Метод карт (таблиц) Карно является более наглядным, менее трудоёмким и надёжным способом минимизации логических функций, но его использование практически ограничено функциями 3-4 переменных, максимум – 5-6 переменных.

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

Таблицы истинности и карты Карно для функций И и ИЛИ двух пер е менных представлены на рис. 8. В каждую клетку карты записывается зн а чение функции на соответствующем этой клетке наборе значений аргуме н тов.

А ) И б ) ИЛИ

Рис. 8. Пример карт Карно для функций двух переменных

В карте Карно для функции И только одна 1, поэтому её ни с чем невозможно склеить. В выражении для минимальной функции будет только терм, соответствующий этой 1:

f = x y .

В карте Карно для функции ИЛИ уже три 1 и можно составить две склеивающиеся пары, при этом 1, соответствующая терму xy , используется дважды. В выражении для минимальной функции нужно записать термы для склеиваемых пар, оставляя в них все переменные, которые для этой пары не меняются, и убирая переменные, которые меняют своё значение. Для горизонтальной склейки получим x , а для вертикальной – y , в итоге получим выражение

f = x + y .

На рис. 9 приведены таблицы истинности двух функций трёх переменных (а ) и их карты Карно (б и в ). Функция f 2 отличается от первой тем, что на трёх наборах переменных она не определена (в таблице это обозначено прочерком).

При определении минимальной ДНФ функции используются следующие правила. Все клетки, содержащие 1, объединяются в замкнутые прямоугольные области, которые называются k -кубами , где k = log 2 K , K – количество 1 в прямоугольной области. При этом каждая область должна представлять собой прямоугольник с числом клеток 2 k , где k = 0, 1, 2, 3, … . Для k = 1 прямоугольник называется один-куб и содержит 2 1 = 2 единицы; для k = 2 прямоугольник содержит 2 2 = 4 единицы и называется два-куб ; при k = 3 область из 2 3 = 8 единиц называется три-куб ; и т. д. Единицы, которые невозможно объединить в прямоугольники, можно назвать ноль-кубами , которые содержат только одну единицу (2 0 = 1). Как видно, при чётном k области могут иметь форму квадрата (но не обязательно), а при нечётном k – только прямоугольников.

б в

Рис. 9. Пример карт Карно для функций трёх переменных

Эти области могут пересекаться, т. е. одни и те же клетки могут входить в разные области. Затем записывается минимальная ДНФ функции как дизъюнкция всех конъюнктивных термов, соответствующих k - кубам.

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

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

Для функции по карте Карно на рис. 9, б находим

поскольку для верхней замкнутой области переменные x 1 и x 2 имеют значения без инверсий, для нижней x 1 имеет значение с инверсией, а x 3 – без инверсии.

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

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

Карты Карно можно рисовать разными способами (рис. 10).

x 2 x 3

а б

Рис. 10. Разные способы изображения карт Карно
для функции 3 переменных

Но самыми удобными вариантами карт Карно для функций 2-4 переменных являются показанные на рис. 11 таблицы, т. к. в них для каждой ячейки показ а ны все переменные в прямом или инверсном виде.

а б

Рис. 11. Наиболее удобное изображение карт Карно
для функций 3 (а ) и 4 (б ) переменных

Для функций 5 и 6 переменных больше подходит способ, показанный на рис. 10, в .

Рис. 12. Изображение карты Карно для функции 5 переменных

Рис. 13. Изображение карты Карно для функции 6 переменных

Другие похожие работы, которые могут вас заинтересовать.вшм>
9020. ПРИНЦИП ДВОЙСТВЕННОСТИ. РАЗЛОЖЕНИЕ БУЛЕВЫХ ФУНКЦИЙ ПО ПЕРЕМЕННЫМ. СОВЕРШЕННЫЕ ДИЗЪЮНКТИВНАЯ И КОНЪЮНКТИВНАЯ НОРМАЛЬНЫЕ ФОРМЫ 96.34 KB
Данная теорема носит конструктивный характер, так как она позволяет для каждой функции построить реализующую ее формулу в виде совершенной д. н. ф. Для этого в таблице истинности для каждой для функции отмечаем все строки, в которых
6490. Описание и минимизация логических функций 187.21 KB
В словесной форме выражается взаимосвязь между аргументами функции и ее значениями. Пример: функция трех аргументов принимает значение когда любые два или более аргументов функции равны. Состоит в построении таблицы истинности содержащей значения функции для всех наборов значений аргументов. В данном примере по таблице истинности получаем такую запись в виде ДНФ...
6707. Проектирование реляционных баз данных. Проблемы проектирования в классическом подходе. Принципы нормализации, нормальные формы 70.48 KB
Что такое проект реляционной базы данных Это набор взаимосвязанных отношений в которых определены все атрибуты заданы первичные ключи отношений и заданы еще некоторые дополнительные свойства отношений которые относятся к принципам поддержки целостности. Поэтому проект базы данных должен быть очень точен и выверен. Фактически проект базы данных это фундамент будущего программного комплекса который будет использоваться достаточно долго и многими пользователями.
4849. Формы и методы осуществления функций государства 197.3 KB
Термин «функция» имеет в отечественной и зарубежной научной литературе далеко не одинаковое значение. В философском и общесоциологическом плане, он рассматривается, как «внешнее проявление свойств какого-либо объекта в данной системе отношений»; как совокупность обычных или же специфических действий отдельных лиц или органов
17873. Формирование логических УУД у учащихся 3 класса 846.71 KB
Психолого-педагогические аспекты проблемы формирования логических универсальных действий у младших школьников Методики оценки сформированности логических УУД. Разработка концепции развития универсальных учебных действий в системе общего образования отвечает новым социальным запросам. Важнейшей задачей современной системы образования является формирование универсальных учебных действий УУД. Сформированность универсальных учебных действий является залогом профилактики школьных трудностей.
2638. Техническая реализация логических связей в системах автоблокировки 1.04 MB
Техническая реализация логических связей в системах автоблокировки Техническая реализация алгоритмов управления трехзначной и четырехзначной АБ может быть достигнута при помощи релейных контактных и бесконтактных дискретных и интегральных логических элементов...
10203. ПРИМЕНЕНИЕ КОНЦЕПЦИИ РИСК ОРИЕНТИРОВАННОГО ПОДХОДА ДЛЯ ПОСТРОЕНИЯ СТРУКТУРНО-ЛОГИЧЕСКИХ МОДЕЛЕЙ ВОЗНИКНОВЕНИЯ И РАЗВИТИЯ ЧС 70.8 KB
Общий анализ риска Производственная среда насыщается мощными технологическими системами и технологиями которые делают труд человека производительным и менее тяжелым физически однако более опасным. Для риска характерны неожиданность и внезапность наступления опасной ситуации. Ежедневно мы сталкиваемся с многочисленными рисками но большая часть из них остается потенциальными т. Теория риска предусматривает количественную оценку негативного воздействия на человека а также нанесения ущерба его здоровью и жизни.
11576. Понятие, виды и формы сделок. Последствия несоблюдения требуемой формы сделок 49.82 KB
Признание сделки недействительной виды недействительной сделки. Прикладная ценность курсовой работы заключается в упрощении понятия сделки то есть публичного его представления в более доступной форме.
6213. Приближение функций 3.08 MB
Первая состоит в замене некоторой функции заданный аналитически или таблично другой функцией близкой к исходной но более простой и удобной для вычислений. Например замена функции многочленом позволяет получать простые формулы численного интегрирования и дифференцирования; замена таблицы приближающей функцией позволяет получать значения в ее промежуточных точках. Возникает также и вторая задача восстановление функции на некотором отрезке по заданным на этом отрезке значениям функции в дискретном множестве точек. Ответ на такой вопрос...
14058. Эволюция функций государства 29.99 KB
Российское государство как правовое явление прежде всего должно обеспечивать реализацию назначения государства а также его основных конституционных характеристик как демократического федеративного правового социального светского государства с республиканской формой правления. Главное назначение государства определяется ст.

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

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

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

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

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

Примеры: 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

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