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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Курсовик Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геометрическое представление логических функций. Геометрический метод минимизации булевых функций. Карты Карно.

Информация:

Тип работы: Курсовик. Предмет: Математика. Добавлен: 21.02.2009. Сдан: 2009. Уникальность по antiplagiat.ru: --.

Описание (план):


2
СОДЕРЖАНИЕ

1. Полные системы булевых функций
2. Сокращенные и тупиковые дизъюнктивные нормальные формы
3. Алгоритм Квайна и Мак-Класки минимизации булевой функции
4. Геометрическое представление логических функций
5. Геометрический метод минимизации булевых функций
6. Минимизация булевой функции с помощью карты Карно
7. Построение оптимальных контактно-релейных схем
Упражнения
Библиографический список
1. Полные системы булевых функций

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

X1= 0
X2= 0
0
1
1
0
1
1
fk (X1, X2)
1
0
0
0
0
f1 = 0
2
0
0
0
1
3
0
0
1
0
4
0
0
1
1
5
0
1
0
0
6
0
1
0
1
7
0
1
1
0
8
0
1
1
1
9
1
0
0
0
10
1
0
0
1
11
1
0
1
0
12
1
0
1
1
13
1
1
0
0
14
1
1
0
1
15
1
1
1
0
16
1
1
1
1
Функция f1 называется нулевой; f16 - единичной; f2 - конъюнкцией; f8 - дизъюнкцией; f11 и f13 - отрицаниями Х1 и Х2 соответственно; f12 и f14 - импликациями; f3 и f5 - коимпликациями; f10 - эквиваленцией; f7 - сложением по модулю два или разделительной дизъюнкцией; f9 - стрелкой Пирса (функцией Вебба); f15 - штрихом (функцией) Шеффера.
Функцию, полученную из элементарных путем перенумерации аргументов и подстановки вместо аргументов в некоторых других булевых функций, называют суперпозицией функций. Нетрудно убедиться, что любая булева функция от n аргументов является суперпозицией элементарных функций, заданных табл. 1. Например, функция
является суперпозицией элементарных функций: отрицания, дизъюнкции, конъюнкции и импликации.
Система булевых функций называется полной, если любая булева функция является суперпозицией этих функций.
В последнем столбце таблицы 1 показано, что все элементарные функции двух переменных, следовательно, и любые булевы функции, могут быть записаны с помощью трех логических операций . Поэтому справедлива следующая теорема
Теорема. Отрицание, дизъюнкция и конъюнкция образуют полную систему булевых функций
Этот набор булевых функций наиболее удобен для построения сложных булевых функций и чаще всего используется в приложениях, однако он не является минимальным и может быть еще сокращен.
Полная система булевых функций называется базисом, если она перестает быть полной при удалении хотя бы одной из этих функций.
Согласно этому определению система булевых функций не является базисом. Действительно, применяя законы де-Моргана
, ,
конъюнкцию в булевой функции можно заменить на дизъюнкцию и отрицание, а дизъюнкцию - на конъюнкцию и отрицание. Следовательно, отрицание и дизъюнкция (отрицание и конъюнкция) также образуют полную систему булевых функций. Нетрудно убедиться, что наборы и являются базисными, так как их дальнейшее сокращение без нарушения полноты системы невозможно.
Для проверки полноты заданной системы булевых функций может быть использовано следующее очевидное утверждение:
Если система - полная и любая из функций f1, f2,...,fm может быть выражена с помощью суперпозиций через функции g1, g2,…, gk, то система также полная.
Пример 1. Доказать полноту системы .
Для доказательства воспользуемся системой , полнота которой уже доказана, эти функции можно выразить через g1 и g2 по формулам:
f1=g1, ,
следовательно система функций является полной.
В общем случае для проверки полноты системы булевых функций используется критерий полноты Поста. Прежде чем его сформулировать, напомним некоторые определения [3].
Функция f = (Х12,...,Хn) называется функцией, сохраняющей константу 0 (1 ), если
f(0,0, ...0) = 0, (f(l, 1....1) = 1).
Функция f (X1,X2,...,Xn) называется самодвойственной, если
f (X1,X2,..., Xn) = .
Функция f (X1,X2,...,Xn) называется монотонной, если для любых двух наборов X = (X1,X2,…,Xn) и Y = (Yl, Y2,...,Yn), таких, что XY (для любого i XiYi) имеет место неравенство:
f (X1,X2,..., Xn) f (Yl, Y2,...,Yn).
Функция f (X1,X2,..., Xn) называется линейной, если
f (X1,X2,..., Xn) = ,
где .
Первые четыре свойства проверяются с помощью таблицы истинности, а для проверки линейности функции необходимо построить многочлен Жегалкина.
Например, из табл. 1 следует, что f2 = X1X2 и f8 = X1X2 - функции, сохраняющие константу 0; f10 = X1-X2 - функция, не сохраняющая константу 0, но сохраняющая константу 1; f7 = X1X2 - несамодвойственная функция; f2, fg - монотонные функции; f14 = X1>X2 - немонотонная функция, так как монотонность нарушается на набоpax (0, 0) и (1, 0); f3 - нелинейная функция, так как соответствующий ей многочлен Жегалкина X1 + X2 + X1X2 - нелинеен.
Теорема Поста. Система D = {f1, f2, ... fm} булевых функций является полной тогда и только тогда, когда среди функций этой системы существуют: функция, не сохраняющая константу 0, функция, не сохраняющая константу 1, а также нелинейная, несамодвойственная и немонотонная функции.
Пример 2. Доказать полноту системы .
Решение. Пусть K0 - класс функций, сохраняющих константу 0; К1 - класс функций, сохраняющих константу 1; Кл, Kc, Км - классы линейных, самодвойственных и монотонных функций соответственно.
Составим таблицу Поста следующего вида.
Таблица 2

цi
K0
К1
Кл
Kc
Км
1
X1 X2
+
-
+
-
-
2
X1 X2
+
+
-
-
+
3
1
-
+
+
-
-
Знак "+", стоящий на пересечении i- й строки и j-гo столбца этой таблицы, показывает, что функция цi - принадлежит соответствующему классу, записанному в j-ом столбце,
Из табл. 1 видим, что ц1 = f7 не сохраняет константу 1 и не является монотонной, ц2 = f8 - нелинейная и несамодвойственная функция, ц3 = f16 не сохраняет константу 0. Следовательно, все условия теоремы Поста выполнены, и заданная система является полной.
Пример 3. Доказать, что система {|} является базисом.
Решение. Рассматриваемая система состоит из одной функции f15 (функции Шеффера). Из табл. 1 видим, что f15 - функция, не сохраняющая 0 и 1, немонотонная (монотонность нарушается на наборах (1, 0) и (1, 1), несамодвойственная, так как , a двойственная функция нелинейная, так как многочлен Жегалкина для этой функции имеет вид: 1 + X1X2. Следовательно, система {f15} = {|} удовлетворяет всем условиям теоремы Поста и является базисом.
Исследуя различные наборы функций, можно показать, что для множества булевых функций двух переменных существуют 17 различных базисов, в каждом из которых нельзя вычеркнуть ни одну функцию без потери полноты. Наиболее распространенными из них являются конъюнктивный базис Буля , дизъюнктивный базис Буля . импликативныи базис . базис Шеффера {|}, базис Жегалкина .
Таким образом, для аналитического задания булевой функции можно использовать различные языки формул. Критерием выпора должен служить характер рассматриваемой задачи.
2. Сокращенные и тупиковые дизъюнктивные нормальные формы

Известно [4], что всякую булеву функцию можно записать, причем единственным образом, в ДНФ, то есть в виде дизъюнкции элементарных конъюнкций (суммы произведений). В связи с этим можно ставить вопрос об отыскании для заданной функций такой ДНФ, которая была бы наиболее простой по сравнению с ее другими ДНФ.
ДНФ называется минимальной, если она содержит по сравнению с другими эквивалентными ей формами минимальное количество букв (при подсчете учитывается каждое вхождение буквы в формулу).
В простейших случаях минимизацию функции можно осуществить, выписав все ДНФ для этой функции и выбрав, из них минимальную. Однако такой примитивный метод очень трудоемок, и мы рассмотрим ниже более оптимальные способы решения этой задачи.
Элементарную конъюнкцию цк назовем импликантой булевой функции f, если не существует такого двоичного набора переменных, при котором функция цк принимает значение 1, а функция f - значение 0, то ecть цk f = f.
Для того чтобы проверить является ли заданная элементарная конъюнкция импликантой функции f, следует всем переменным, которые входят в эту конъюнкцию без знака отрицания, придать значение 1, а тем переменным, которые входят с отрицанием - значение 0. Тогда элементарная конъюнкция будет иметь истинностное значение 1. После этого следует, проверить, принимает ли функция f значение 1 при любых значениях остальных переменных. В дальнейшем для упрощения записибулевых функций знаки коньюнкции будем заменять знаками умножения или просто опускать.
Пример 4. Проверить, являются ли одночлены и импликантами булевой функции
.
Решение. Полагая в первом случае Х1 = 1, X2 = 1, имеем ц1 = l и ц2 = l и
,
следовательно, ц2 - импликанта заданной функции.
Во втором случае полагаем X1 = 0, X2 = l. Тогда
ц2 = 1, а ,
следовательно, ц2 не является импликантой функции f.
Справедливы следующие утверждения:
1. Если импликанты булевой функции f, то и также являются ее импликантами.
2. Если функция есть импликанта функции f, то функции также являются импликантами функции f.
Элементарная конъюнкция, входящая в ДНФ булевой функции, называется ее простой импликантой, если никакая ее часть не является импликантой этой функции.
Сокращенной ДНФ данной булевой функции называется ее ДНФ, составленная только из простых импликант.
Для приведения булевой функции к сокращенной ДНФ используется, так называемое правило склеивания. Оно заключается в следующем. Логическую сумму двух элементарных конъюнкций, отличающихся только знаком отрицания над одной из переменных, можно заменить одной элементарной конъюнкцией, которая является общей частью рассматриваемых слагаемых, т.е.
.
Например,
Для любой заданной функции сокращенная ДНФ является единственной. Однако онa может быть избыточной вследствие тогo, что некоторые простые импликанты этой суммы покрываются совокупностями других слагаемых. Такие импликанты называют лишними, и они могут быть удалены без нарушения равносильности формул.
Сокращенная ДНФ, из которой удалены все лишние импликанты, называется тупиковой ДНФ
Исключение лишних импликант из сокращенной ДНФ проводится с помощью правила поглощения: дизъюнкцию двух элементарных конъюнкций, из которых одна полностью содержится и другой, можно заменить конъюнкцией, имеющей меньший ранг, например, X XF = X,
.
Правила склеивания, и поглощения легко доказываются с помощью таблиц истинности. Кроме этих правил, при минимизации функции могут быть использованы любые известные равносильности.
Пример 5. Упростить булеву функцию .
Решение. Эта функция содержит только простые импликанты, т. е. является сокращенной Однако она избыточна, так как одночлен Х1X2 можно удалить, не разрушая равносильности. После этого получим функцию:
.
Пример 6. Найти минимальную ДНФ для функции
.
Решение. Склеивая первый и третий одночлены по переменкой Х2, получим Х1X3X4. Из первого и четвертого, а затем из второго и третьего слагаемых после склеивания получим соответственно X1X2X3, и т. д. Окончательный список импликант имеет вид
В этом списке имеется два одночлена X1X3 и Х2Х3Х4, которые не поглощают других одночленов из этого списка, следовательно, являются простыми импликантами. Поэтому сокращенная ДНФ имеет вид
,
пна же является и минимальной
В общем случае процесс построения минимальных ДНФ может быть охарактеризован следующей схемой.
Рис. 1
Сначала получают сокращенную ДНФ. Далее однозначный процесс переходит в ветвящийся процесс построения всех тупиковых ДНФ и, наконец, из тупиковых ДНФ выделяются минимальные. Самым трудоемким этапом этого процесса является построение тупиковых ДНФ. Его можно немного упростить, заранее удалив часть членов сокращенной ДНФ, не участвующих в построении тупиковых ДНФ и тем самым сократить количество просматриваемых подмножеств
Проблема минимизации является важнейшей для технических приложений логических функций и ей посвящено много работ, в которых предложены различные алгоритмы решения этой задачи. Рассмотрим подробнее один из таких алгоритмов.
3. Алгоритм Квайна и Мак-Класки минимизации булевой функции

Этот алгоритм используется наиболее часто, так как он может быть реализован на ЭВМ, и при его применении практически отсутствуют ограничения на число переменных. Минимизацию функции в этом методе рекомендуется выполнить в следующей последовательности.
1. Привести булеву функцию к СДНФ.
2. В СДНФ произвести все возможные склеивания Полученная после этого ДНФ является сокращённой, но среди простых импликант могут оказаться лишние.
3. Перейти от сокращённой ДНФ к минимальной, т.е. исключить лишние импликанты. Для этого рекомендуется воспользоваться импликантой матрицей, в которой каждой строке соответствует простая импликанта, а каждому столбцу - конституента ( элементарная конъюнкция, содержащая все переменные) СДНФ заданной функции Эта матрица заполняется следующим образом под конституентами, в которые входит данная простая импликанта, ставится метка "1" Для нахождения минимального покрытия функции необходимо удалить из таблицы некоторые лишние простые импликанты С этой целью реализуется следующий алгоритм.
1. Выделение ядра Квайна. Если в каком-либо столбце импликантной матрицы имеется только одна 1, то импликанта, находящаяся в соответствующем столбце, не является лишней и должна быть включена в минимальное покрытие функции. Такие импликанты называются существенными, а их совокупность называют ядром Квайна.
Вычёркивая строки, в которых находятся существенные импликанты, и столбцы, покрываемые этими импликантами, получаем матрицу меньших размеров Если в ней имеются столбцы, содержащие по одной 1, то операцию выделения существенных импликант следует повторить.
2 Сжатие по столбцам или строкам. Из матрицы вычёркивается тот столбец, в который полностью входит какой-либо другой столбец и та строка, которая полностью покрывается другой.
После выполнения всех указанных действий в матрице останутся только те простые импликанты, которые входят в минимальное покрытие функции. Соединив эти импликанты и найденные ранее существенные импликанты знаками дизъюнкций, получим минимальную ДНФ заданной функции.
Пример 7 Минимизировать булеву функцию
.
Решение. Функция задана в ДНФ, поэтому займемся сразу отысканием простых импликант, проводя операцию склеивания. Для этого представим каждую элементарную конъюнкцию двоичным набором, ставя на k-ом месте 0, если Хk входит с отрицанием, 1 - если без отрицания и знак "-", если эта переменная не входит в конъюнкцию Тогда функция примет вид:
.
Разобьем эти наборы на классы, в каждом из которых содержатся наборы с одинаковым числом единиц и расположим их в порядке возрастания суммы всех чисел набора (рис 2 а)
Для исключения переменных по правилу склеивания сравним все наборы всех смежных классов. Если при этом какая-либо переменная исключается, то в разряд, соответствующий этой переменной, записываем прочерк. Например, двоичные наборы 0100 и 0101 образуют набор 010-. Все полученные наборы опять разбиваем на классы. Объединяем снова наборы из двух смежных классов, причём сравнению подлежат только те, у которых прочерк находится в одном и том же разряде, получаем новый набор импликант (рис. 2 в). Нетрудно убедиться, что дальнейшее объединение наборов невозможно, следовательно, все полученные импликанты - простые.
Построим импликантную матрицу (табл. 3 а). Выделяя столбцы, содержащие по одной единице, находим существенные импликанты, образующие ядро Квайна: 0-0- -0-0. При этом первая из них является существенной для 0000, 0001, 0100, 0101, а вторая - для 0000, 0010, 1000, 1010. Вычёркивая столбцы с этими конституентами и строки с существенными импликантами, получим табл. 3 б. В этой таблице нет столбцов, содержащих только одн и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.