85902 (612602), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Задача. Определим форму булева многочлена р, заданного в дизъюнктивной нормальной форме

d = v’w’x’y’z’ + v’w’x’yz’ + v’w’xy’z’ + v’w’xyz’ + v’wx’y’z + v’wx’yz’ + v’wxy’z + v’wxyz’ + v’wxyz + vw’x’y’z’ + vw’x’y’z + vw’xy’z + vwx’yz’ + vwxy’z’ + vwxyz’ + vwxyz

Решение:

Шаги 1 и 2

Шаг 3. Комбинация строк (i) и (j) дает сокращение, указанное в строке (i)(j):

Повторение этого шага с новыми строками дает нам

Пометки «птичкой» и буквами сделаны после процесса упрощения. найденные простые импликанты обозначены буквами А, В, …J.

Шаг 4. Формируем таблицу простых импликантов, где индексы столбцов – слагаемые из d – представлены в виде двоичных столбцов.

	(1) 0 0 0 0 0	(2) 0 0 0 1 0	(3) 0 0 1 0 0	(4) 1 0 0 0 0	(5) 0 0 1 1 0	(6) 0 1 0 0 1	(7) 0 1 0 1 0	(8) 1 0 0 0 1	(9) 0 1 1 0 1	(10) 0 1 1 1 0	(11) 1 0 1 0 1	(12) 1 1 0 1 0	(13) 1 1 1 0 0	(14) 0 1 1 1 1	(15) 1 1 1 1 0	(16) 1 1 1 1 1
-111- А
-1-10 В
0--10 С
00--0 D
111-0 E
011-1 F
10-01 G
01-01 H
1000- I
-0000 J

В наших кратких обозначениях ядро, т.е. сумма главных членов, есть D + H + G + B + E + A. Единственным произведение, не покрываемым ядро, является (4); это и есть q₁. Простыми импликантами p_i, не входящими в ядро, являются С, F, I, J. Новая таблица имеет вид

Это обозначает, что мы получаем две минимальные форы:

1. D + H + G + B + E + A + I, если использовать I, и

2. D + H + G + B + E + A + J, если выбрать J.

В обычных обозначениях минимальная форма (i) такова:

v’w’z’ + v’wy’z + vw’y’z + wyz’ + vwxz’ + wxy + vw’x’y’.

ЗАКЛЮЧЕНИЕ

По результатам проведённого курсового исследования по теме «Минимальные формы булевых многочленов» можно сделать следующие выводы.

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

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

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1. Владимиров Д.А., Булевы алгебры – М., Издательство «Наука» 1969.

2. Дискретная математика и математические вопросы кибернетики – под общей редакцией С.В. Яблонского и О.Б. Лупанова – М., «Наука», 1974.

3. Лидл Р., Пильц Г., «Прикладная абстрактная алгебра» - Екатеринбург, «Издательство уральского университета» 1996.

4. www.exponenta.ru/educat/systemat/1006/2_tutorials/bin_log.asp

5. www.intuit.ru/department/hardware/archsys/keywords.2.html

Характеристики

Список файлов курсовой работы