20

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ” Кафедра “Системного аналізу та управління” Курсова робота Дисципліна “Дискретна математика" Тема “Булева алгебра. Мінімізація СДНФ. Iмпликантні іспити” (Варіант №2-13) Керівник роботи: доц. каф. САіУ, канд.техн.наук Жданов А.П. Виконавець: студентка групи ІФ-50в Пушкарьова К.В. Харків – 2005

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Кафедра “Системного аналізу та управління”

Оцінка

________________________

голова комісії

доц. каф.САиУ

____________ /Кащеєв Л.Б./

« » ___________ 200 _ р.

КУРСОВА РОБОТА

Дисципліна: „Дискретна математика”

Тема: „Булава алгебра. Мінімізація СДНФ. Iмпликантні іспити”

(Варіант №2-13)

Виконавець: ст. гр. ИФ-50^в К.В.Пушкарьова

“ ” 200 р.

Керівник роботи: доц., канд. техн. наук О.П.Жданов

“ ” 200 р.

Харків 2005

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Кафедра “Системного аналізу та управління”

Студентка К.В.Пушкарьова Група ИФ-50^в

ЗАВДАННЯ на науково-дослідну курсову роботу

Дисципліна: “Дискретна математика”

Тема: „Булева алгебра.Мінімізація СДНФ.Iмпликантні іспити” (Варіант №2-13)

Короткий зміст роботи:

а) теоретична частина

Розробка методики дослідження булевої функції:

Провести запис таблиці істинності, усіх функцій, які використовуються; перевірити, чи може бути сукупність даних функцій базисом; побудувати таблицю істинності даної функції; по таблиці істинності побудувати карту Карно; мінімізувати функцію за картою Карно; мінімізувати функцію методом Квайна-МакКласки; перевірити здобуту тупикову ДНФ матрицею імплікатних іспитів; перевірити здобуту тупикову ДНФ методом Петрика; запропонувати схемну реалізацію мінімальної ДНФ на релейних контактах и мікросхемах.

б) програмно-розрахункова частина

Розробка програмного забезпечення, яке реалізує заповнення таблиці істинності та побудову СДНФ, друга частина програми повинна здобувати мінімальної ДНФ за картою Карно

Дата видачі завдання: 15.03.2006 Термін захисту: 21.05.2006

Керівник курсової роботи: / канд. техн. наук, доц. САіУ

А.П.Жданов/

Содержание

Введение …….………..…………………………………………………………3

1 Булева алгебра ………..………………………………………………………4

1.1 Таблицы истинности применяющихся булевых функций…………4

1.1.1 Базис булевых функций, теорема Поста …………………………4

1.1.2 Таблица истинности заданной функции ……………………….....4

1.1.3 Карта Карно …………………………………………………………4

1.2 Минимизация булевой функции ……………………………………4

1.2.1 Минимизация по карте Карно …………………..…………………5

1.2.4 Минимизация методом Квайна-МакКласки ………………………5

1.2.5 Проверка тупиковой ДНФ матрицей импликантных испытаний ..5

1.2.6 Проверка полученной тупиковой ДНФ методом Петрика..……...5

1.3 Схемная реализация минимизированной функции ..……………….7

1.3.1 Реализация в виде релейной схемы..…………………………….7

1.3.2 Реализация на микросхемах ………….………………………….7

2. Постановка задачи на программирование ……………………………….14

2.1. Постановка задачи ………………………………………………………14

2.2. Описание разработанного объекта ……………………………………..14

2.2.1. Иерархия наследования ………………………………………..14

2.2.2. Организация объекта ……………………..…………………….15

2.3. Интерфейс программы ………………………………………………….16

Заключение …………………………………………………………………...19

Список использованных источников ……………………………………….20

Введение

Аппарат математической логики в значительной степени сложился под влиянием прикладных проблем, в рамках которых развились его специфические особенности. Первой такой проблемой среди технических приложений стала задача анализа и синтеза контактных схем. Успехи в этой области послужили стимулом для использования математического аппарата булевой алгебры (названо по имени G.Boole [1815-1864]) и в других областях. Наикрупнейшими «потребителями» математических идей и алгоритмов этой области математики в настоящее время являются вычислительная техника и программирование.

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

1 БУЛЕВА ФУНКЦИЯ

1. Таблицы истинности используемых функций

Исходная функция из задания:

Сумма по модулю 2, обозначение: a₁  a₂.

a1	0	1	0	1
a2	0	0	1	1
a1  a2	0	1	1	0

Отрицание, обозначение: a.

a	0	1
a	0	1

Дизъюнкция, обозначение: a₁  a₂.

a1	0	1	0	1
a2	0	0	1	1
a1  a2	0	1	1	1