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

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

 

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

 

Логин:

Пароль:

 

Запомнить

 

 

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

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

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

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


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


Курсовик Булевы алгебры решетки особого типа, применяемые при исследовании логики (как логики человеческого мышления, так и цифровой компьютерной логики), а также переключательных схем. Минимальные формы булевых многочленов. Теоремы абстрактной булевой алгебры.

Информация:

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

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


21
Федеральное агенство по образованию РФ Саратовский государственный университет
имени Н.Г. Чернышевского


Кафедра геометрии
курсовая работа
Минимальные формы булевых многочленов

г. Саратов 2009 г.
содержание

Введение
Основные понятия булевой алгебры
1.1 Основные этапы развития булевой алгебры
1.2 Основные определения булевой алгебры
1.3 Минимальные формы булевых многочленов
II.Решение минимальных форм булевых многочленов с
помощью метода Куайна - Мак-Класки
Заключение
Список используемых источников.
ВВЕДЕНИЕ

Булевы алгебры - это решетки особого типа, которые применяются при исследовании логики (причем как логики человеческого мышления, так и цифровой компьютерной логики), а также переключательных схем. Это последнее приложение было инициировано К. Шенноном, показавшим, что фундаментальные свойства электрических сетей, состоящих из бистабильных элементов, могут быть выражены с помощью булевых алгебр. Наряду с шенноном пионерами в применении теории булевых алгебр для решения задач релейной техники в 1936-1938 гг. были русский математик В.И. Шестаков и японцы А.Накасима и М. Ханзава. Отметим также, что ещё в 1910 г. известный физик П. Эренфест в рецензии на русский перевод книги Л. Кутюра «Алгебра логики» указал на потенциальную применимость булевой логики к проектированию автоматических телефонных станций, сформулировав вопросы о реализуемости булевых функций и минимизации схем.
Целью данной курсовой работы является изучение булевой алгебры и применение минимальных форм булевых многочленов к решению задач.
Курсовая работа состоит из введения, трех глав, заключения и списка используемых источников.
Во введении описана актуальность темы, сформулирована цель, дана структура курсовой работы.
В первой главе даны основные определения и основные понятия булевой алгебры.
Во второй главе дается определение минимальных форм булевых многочленов и намечен курс дальнейшего исследования.
Третья глава посвящена применению минимальных форм булевых многочленов к решению задач.
В заключении сформулированы основные выводы к работе.
I. ОСНОВНЫЕ ПОНЯТИЯ БУЛЕВОЙ АЛГЕБРЫ

1.1 Основные этапы развития булевой алгебры.

В 1847 году Дж. Буль написал маленькую, но эпохальную книгу «математический анализ логики», в которой логика трактовалась как чисто формальная система; интерпретация в обычном языке пришла позже. Буль писал, что математика характеризуется своей формой, но не содержанием. В своей последующей книге «Исследование законов мышления» (1854) он ввел понятие булевой алгебры.
Булевское исчисление логики сосредоточено на формальной трактовке логики посредством математических (особенно алгебраических) методов и на описании логических тождеств. Следуя Булю, школа английских математиков, а также Шрёдер, Уайтхед разработали аксиоматику операций конъюнкции, дизъюнкции, отрицания; с другой стороны, Пирс и Шрёдер создали аксиоматику порядка, используя отношение включения в качестве фундаментального понятия. В 1904 году Хантингтон исследовал две системы аксиом и начал трактовать булевы алгебры как самостоятельные математические структуры, не обязательно связанные с логикой.
Буль использовал дистрибутивность пересечения относительно объединения, которую еще до него отметил Ламберт. Буль работал с множествами. Обозначая пересечение х и у через ху, а объединение - через х + у, если х и у дизъюнкты. Подобно Лейбницу, он интерпретировал отношение включения х у как ху = х, что легко давало возможность получить классические правила силлогизма. Затем Джевонс распространил операцию объединения на произвольные х и у; Де Морган и, позже, Пирс доказали соотношение двойственности, называемые законами де Моргана.
Большинство логиков девятнадцатого века не высказывало большого интереса к применению в математике своих находок. Одной из причин этого было отсутствие кванторов, введенных позже Фреге и Пирсом. Пеана, среди прочих, ввел символы , , - для объединения, пересечения и вычитания множеств. После книги ван дер Вардена по современной алгебре понятие универсальной алгебры было уже не за горами. Биркгоф развил концепцию «алгебры», отправляясь от подходов ван дер Вардена, и взял название «универсальная алгебра» из книги Уайтхеда. в 1934 году, будучи в Геттингене, Маклейн также высказывал некоторые мысли об универсальной алгебре, но не опубликовал их. Одна из фундаментальнейший статей по теории решеток была напечатана Оре в 1935 году. Последующие годы ознаменовались целым рядом исследований в области, как теории, так и приложений решеток, например, в теории групп, проектированной геометрии, квантовой механике, функциональном анализе, теории меры и интегрирования.
В 1933 - 1937 гг. М. Стоун получил важные результаты о булевых алгебрах, которые он интерпретировал как специальные кольца, а именно как булевы кольца, где была применима теория идеалов. Другие фундаментальные вопросы, рассматривавшиеся Стоуном, - это вопросы о представлении булевых алгебр и приложения булевых алгебр в топологии. С тех пор теория решеток превратилась во вполне жизнеспособную, сильную и самостоятельную дисциплину.
1.2 Основные определения и понятия булевой алгебры
Определение: Булевой алгеброй (обозначим В) называется непустое множество элементов с двумя бинарными операциями «+», «*» и одной унарной операцией «`», а так же специальными элементами 0 и 1, если выполняются следующие свойства:
a + b = b + a , a , b B
a * b = b * a , a, b B
a + (b * c) = (a + b) * (a + c)
a* (b + c) = (a * b) + (a * c)
a + 0 = a, a * 1 = a. (Тождественность)
a + a` = 1, a * a`= 0. (Дополнительность)
Эта система аксиом является полной и независимой.
Пример 1: Пусть множество В - это множество В= {1,0} на котором заданы две бинарные операции:
+
1
0
*
1
0
1
1
1
1
1
0
0
1
0
0
0
0

И унарная операция: 0` = 1, 1` = 0.
Пример 2: Множество делителей числа 70:<1,2,5,7,10,14,35,70>
1. a + b = НОД (a, b)
2. a * b = НОК (a, b)
3. a` = 70/a
Определение: Пусть С - непустое подмножество множества В. Говорят, что С - подалгебра алгебры В, если она сама является алгеброй с теми же операциями.
Подмножество С - есть подалгебра алгебры В С замкнуто относительно трех операций.
Пример 3: Если С=<1,2,35,70> замкнуто относительно операций «+», «*», «`», тогда С является подалгеброй алгебры В.
Определение: Две булевы алгебры В и В` изоморфны: В В`, если существует взаимно-однозначная функция f: BB`, такая, что:
f (a + b) = f (a) + f (b)
f (a * b) = f (a) * f (b)
f (a`) = (f (a))`
Для булевой алгебры справедливы принципы дуальности.
Основные теоремы абстрактной булевой алгебры.
Идемпотентный закон: a + a = a, a * a = a.
Граничный закон: a + 1 = 1, a + 0 = a.
Абсорбционный закон: a + (a * b) = a, a * (a + b) = a.
Ассоциативный закон: a + (b + c) = (a + b) + c, a * (b * c) = (a * b) * c.
Единственность дополнения: если x: a + x = 1 , a * x = 0, то x = a`.
Инволютивный закон: ((a`))` = a 0` = 1 , 1` = 0.
Закон де Моргана: (a + b)`=a` * b`, (a * b)` = a` + b`.
Булева алгебра как решетка.
Поскольку для булевой алгебры справедливы ассоциативный, коммутативный и абсорбционный законы, то согласно определению булева алгебра есть решетка. В этой решетке
а, а + 1 = 1 а 1 , а * 0 = 0 0 а.
Таким образом В есть ограниченная решетка, кроме того аксиомы (2) и (4) указывают на то, что решетка дистрибутивна и дополнена. И наоборот, любая ограниченная, дистрибутивная и дополненная решетка есть булева алгебра.
Определение: Булева алгебра - это ограниченная, дистрибутивная и дополненная решетка.
Мы можем ввести на булевой алгебре отношение частичного порядка. Полагаем, что a b
a b = b , a b = a.
Теорема. В булевой алгебре следующие выражения эквивалентны:
1) a + b = b
2) a * b = a
3) a` + b = 1
4) a * b` = 0.
Доказательство.
Докажем эквивалентность (1) и (3)
а) Пусть (1) верно, тогда
a` + b = a`+ (a + b) = (a` + a) + b = 1 + b = 1;
Пусть (3) верно, тогда
a + b = (a` + b) * (a + b) = b * (a + a`) = b * 1 = b;
Докажем эквивалентность (3) и (4)
Пусть (3) верно, тогда
0 = 1` = (a` + b)` = (a`)` * b` = a * b`;
b) Пусть (1) верно, тогда
1 = 0` = (a + b`)` = a` + (b`)` = a` + b;
Докажем эквивалентность (2) и (4)
Пусть (2) верно, тогда
a * b` = (a * b) * b` = a * (b * b`) = a * 0 = 0;
Пусть (4) верно, тогда
a * b = a * b + 0 = a * b + a * b` = a * (b + b`) = a * 1 = a;
Тогда выражения (1), (2), (3), (4) эквивалентны.

Пример 1. Рассмотрим алгебру множеств - модель булевой алгебры.

А В если А В.

АВ=В

АВ=А

АВ=U

АВ`=

Любая конечная булева алгебра может содержать лишь 2 в степени n элементов, где n - натуральное число.

Пример 2. 1) Множество делителей 70-ти D=<1,2,5,7,10,14,35,70>. Множество A=<2,5,7> -множество атомов решетки D.

10 = 2 5

14 = 2 7

35 =5 7

70 = (2 5) 7

70

14 35

2 5 7

1

2) Множество А = {2,5,7}

Отношение вложенности.

{2,5,7}

{2,5} {2,7} {5,7}

{2} {5} {7}

Эта решетка изоморфна предыдущей.

Алгебра множеств и алгебра высказываний являются моделями абстрактной булевой алгебры. Все абстрактные булевы алгебры (которые состоят из одинакового числа элементов) изоморфны.

1.3 Минимальные формы булевых многочленов

Определение. Понятие булева многочлена определяется рекурсивно. Пусть Хn = {x1,…, xn} - множество из n символов (называемых неизвестными или переменными), которое не содержит символов 0 и 1. Булевы многочлены над Хn суть объекты, которые могут быть получены последовательным применением следующих правил:

(I) х1, х2, …, хn, 0,1 - булевы многочлены;

(II) если p и q - булевы многочлены, то таковыми являются и

(p) (q), (p) (q), (p).

Обозначим множество всех булевых многочленов над Хn через Рn.

Пример. Вот несколько примеров булевых многочленов над 1, х2}: 0,1, х1, х2, х1 х2, х1 х2, х1, х1 х2.

Так как любой булев многочлен над x1,…, xn модно рассматривать как булев многочлен над x1,…, xn, xn+1, мы имеем

Р1 Р2 Рn Рn+1

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

Определение. Назовем литералом любую переменную хi и ее дополнение хi, а также 0 и 1. Под произведением понимается произведение нескольких литералов, т.е. булев многочлен, в котором нет знака +. Дизъюнктивным выражением или просто выражением назовем буле многочлен, являющийся суммой произведений. Слагаемые в таком выражении назовем дизъюнктами.

Обсуждая упрощение булевых многочленов, мы ограничимся важным случаем сведения дизъюнктивных выражений к «минимальным выражениям» относительно специального условия минимальности. Обозначим через df общее число литералов в выражении f, а через ef - число дизъюнктов. Мы говорим, что выражение f проще выражения j, если df dg, ef eg и хотя бы одно из этих неравенств строгое. Выражение f называется минимальным, если не существует выражения, которое было бы эквивалентно f и проще f. Таким образом, мы будем искать «кратчайшее» выражение с наименьшим возможным числом литералов, которое было бы эквивалентно f. Такое минимальное выражение не всегда определено однозначно. Я опишу один из нескольких существующих методов упрощения. Он основан на работе Куайна и был улучшен Мак-Класки, поэтому называется методом Куайна - Мак-Класки.

Определение. многочлен p влечет многочлен q, если для любых b1,., bn В

рв (b1, …, bn) = 1 влечет qв (b1, …, bn) = 1;

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

Пример. Произведение х1х3 является подпроизведением как х1х2х3, так и х1х2х3, и влечет выражение

р = х1х2х3 + х1х2х3 + х1х2х3,

поскольку 1х3)(1, i2, 1) = 1 и р(1, i2, 1) = 1, а для других значений аргументов х1х3 дает 0. Ни х1, ни х3 не влекут р; например, х1(1, 1, 0) = 1, но р(1, 1, 0) = 0, поэтому х1х3 - простой импликант для р.

Теорема. Любой многочлен р Pn эквивалентен сумме всех своих простых импликантов.

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

Простые импликанты получаются из дизъюнктивной нормальной формы d булева многочлена р применением (слева направо) правила

yz + yz y,

когда это возможно. Более общо, мы используем правило

(*)

где и - произведения. следующий пример и т.д.................


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



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


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