close

Вход

Забыли?

вход по аккаунту

?

MishuraPopov

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное
образовательное учреждение высшего образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
ДИСКРЕТНАЯ МАТЕМАТИКА
ОСНОВЫ АЛГЕБРЫ ЛОГИКИ.
МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ
ПРИ ПОМОЩИ ДИАГРАММ ВЕЙЧА
Методические указания
по выполнению контрольной работы
Санкт-Петербург
2016
Составители: кандидат технических наук, доцент О. В. Мишура;
кандидат технических наук, доцент В. П. Попов
Рецензент – кандидат технических наук Н. В. Соловьев
Приведены программа и методические указания к выполнению
контрольной работы по одному из разделов дисциплины «Дискретная
математика, связанной с минимизацией логических функций при помощи диаграмм Вейча».
Предназначены для студентов заочной формы обучения по направлению 09.03.02 «Информационные системы и технологии», квалификация – бакалавр.
Подготовлены кафедрой информационно-сетевых технологий
(№53) и рекомендованы к изданию редакционно-издательским советом Санкт-Петербургского государственного университета аэрокосмического приборостроения.
Публикуется в авторской редакции.
Компьютерная верстка М. И. Дударевой
Подписано к печати 14.06.2016. Формат 60×84 1/16.
Бумага офсетная. Усл. печ. л. 0,87. Тираж 50 экз. Заказ № 261.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения (ГУАП), 2016
1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ,
ЕЕ МЕСТО В УЧЕБНОМ ПРОЦЕССЕ
Программа дисциплины «Дискретная математика» составлена в соответствии с федеральным государственным образовательным стандартом профессионального образованияпо направлению
09.03.02 «Информационные системы и технологии» для направленности «Информационные системы и технологии в бизнесе». Квалификация – бакалавр.
Одним из разделов представленной программы является «Основы алгебры логики», а именно, «Элементы булевой алгебры».
Цель преподавания дисциплины – получение студентами систематизированного представления об основных понятиях, областях
применения и методах дискретной математики, а также получение
студентами необходимых навыков в области формализации поставленных задач, выборе и эффективном применении необходимых методов.
В результате освоения данного раздела студент должен обладать
следующими компетенциями:
«способность разрабатывать средства реализации информационных технологий (методические, информационные, математические,
алгоритмические, технические и программные)».
Знать: методологию использования аппарата математической
логики; основы теории множеств, как специализированый язык
для описания дискретных объектов управления; сущность основных проблем теории графов;
Уметь: формулировать задачи в области информационных систем и технологий на математическом языке; применять методы
дискретной математики для их решения;
Владеть навыками: использования методики построения, анализа
и применения дискретно-математических моделей решаемых задач;
Иметь опыт деятельности: по решению задач теоретического и
прикладного характера из различных разделов дискретной математики.
3
В области воспитания личности в рамках подготовки по данной
дисциплине является формирования основ общекультурных и профессиональных компетенций для приобретения качеств, необходимых создателю новых приборов и технологий, таких как целеустремленность, организованность, трудолюбие, ответственность,
гражданственность, коммуникабельность и др.
Для реализации целей изучения дисциплин необходимо выполнение следующих задач:
– ознакомление студентов с основами алгебры логики, аналитического представления функций алгебры логики, минимизацией
логических функций;
– представление о современном состоянии научных проблем по
организации цифровых автоматов;
– навыки работы с технической литературой.
По окончании изучения дисциплины студент должен знать алгебру логики, типы триггеров, уметь использовать машинные коды,
функции алгебры логики, диаграммы Вейча-Карно, универсальные
базисы, иметь навыки минимизации логических выражений.
В соответствии с учебным планом общая трудоемкость дисциплины
«Дискретная математика», изучаемой в 3-ем семестре студентами заочной формы обучения, квалификация – бакалавр, составляет 144 часа,
из них лекции – 8 чаосв, практические занятия – 8 часов, самостоятельная работа – 119 часов. Студентам заочной формы обучения читаются
установочные лекции. Предусмотрено выполнение одной контрольной
работы. Полное изучение дисциплины студенты-заочники осуществляют самостоятельно. Вид итогового контроля – экзамен 9 часов.
Практические занятия включают решение конкретных задач, связанных с тематикой основных разделов изучаемой дисциплины.
Практическое занятие является одной из основных форм организации учебного процесса, заключающаяся в выполнении обучающимися под руководством преподавателя комплекса учебных
заданий с целью усвоения научно-теоретических основ учебной
дисциплины, приобретения умений и навыков, опыта творческой
деятельности.
Целью практического занятия для обучающегося является привитие обучающемся умений и навыков практической деятельности
по изучаемой дисциплине.
Планируемые результаты при освоении обучающимися практических занятий:
– закрепление, углубление, расширение и детализация знаний
при решении конкретных задач;
4
– развитие познавательных способностей, самостоятельного решения, творческой активности;
– овладение новыми методами и методиками изучения конкретной учебной дисциплины;
– выработка способности логического осмысления полученных
знаний для выполнения заданий;
– обеспечение рационального сочетания коллективной и индивидуальной ворм обучения.
Функции практических занятий:
– познавательная;
– развивающая;
– воспитательная.
По характеру выполняемых обучающимися заданий по практическим занятиям подразделяются на:
– ознакомительные, проводимые с целью закрепления и конкретизации изученного теоретического материала;
– аналитические, ставящие своей целью получение новой информации на основе формализованных методов;
– творческие, связанные с получением новой информации путем
самостоятельного выбранных подходов к решению задач.
Основной формой изучения материала является самостоятельная работа студентов-заочников с технической литературой.
5
2. КОНТРОЛЬНАЯ РАБОТА
В течение семестра каждый студент-заочник должен выполнить
одну контрольную работу. По результатам ее выполнения проверяется качество усвоения студентами той части лекционного материала, которая связана с тематикой второго и третьего разделов изучаемой дисциплины, т. е. с аналитическим представлением функций алгебры логики, минимизацией функций алгебры логики при
помощи диаграмм Вейча, представлением логических функций после минимизации в базисах Шеффера и Пирса, построением логических схем.
Выполнять контрольную работу следует только после того, как
проработана соответствующая литература.
2.1. Формулировка задания к контрольной работе
Контрольная работа имеет название: «Минимизация логической функции при помощи диаграмм Вейча» и включает следующие пункты, которые должны быть выполнены в процессе решения
конрольной работы:
1) представить таблицу истинности для функции, зависящей от
четырех переменных;
2) записать в таблице истинности выражения в СДНФ и СКНФ
для реализуемой функции;
3) минимизировать функцию, представленную в СДНФ и СКНФ,
по единицам и нулям при помощи диаграммы Вейча;
4) представить минимизированную функцию в ДНФ и КНФ;
5) подсчитать сумму рангов для функции в ДНФ и КНФ;
6) реализовать функцию, представленную в форме с минимальной суммой рангов, в базисе Шеффера и Пирса;
7) построить логические схемы для реализуемой функции в базисах Шеффера и Пирса, используя парафазный код подачи переменных, от которых зависит функция.
2.2. Пример выполнения контрольной работы
Пусть логическая функция, зависящая от четырех переменных
А, B, C и D, задана при помощи таблицы истинности (табл. 1).
Чтобы представить значение функции в СДНФ, необходимо выделить наборы переменных, на которых функция равна единице, поставить в соответствие этому набору конъюнкцию соответствующих
6
Таблица 1
А
В
С
D
f
CДНФ
0
0
0
0
1
ABCD
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
1
0
0
0
0
1
0
1
1
0
1
1
0
0
0
1
1
1
–
1
0
0
0
–
1
0
0
1
1
1
0
1
0
–
1
0
1
1
1
1
1
0
0
–
1
1
0
1
0
A ∨B ∨ C ∨D
1
1
1
0
0
A ∨B ∨C ∨ D
1
1
1
1
1
СКНФ
A ∨ B ∨ C ∨D
AB CD
A ∨ B ∨C ∨D
A ∨B ∨ C ∨D
A BC D
A ∨B ∨C ∨ D
ABC D
AB C D
ABCD
переменных, а потом полученные конъюнкции соединить знаками
дизъюнкции. Поэтому имеем:
f(A,B,C,D) = ABCD ∨ AB CD ∨ A BC D ∨
∨ ABC D ∨ AB C D∨ A B C D,
(1)
Сумма рангов полученного выражения R = 24.
Чтобы представить значение функции в СКНФ, необходимо выделить наборы переменных, на которых функция принимает нулевые значения, поставить в соответствие этому набору дизъюнкцию
соответствующих переменных, а потом полученные дизъюнкции
соединить знаками конъюнкции. Поэтому имеем:
f(A,B,C,D) = (A ∨ B ∨ C ∨D)(A ∨ B ∨C ∨D)(A ∨B ∨ C ∨D)
(A ∨B ∨C ∨ D)(A ∨B ∨ C ∨D)(A ∨B ∨C ∨ D) ,
(2)
Сумма рангов полученного выражения R = 24.
Для минимизации заданной функции представим диаграмму
Вейча, расставим в ней единичные значения функции, а также в со7
ответствующих клетках диаграммы – прочерки. Пустые клетки будут соответствовать нулевым значениям функции.
В заполненной диаграмме Вейча необходимо найти соседние области. При нахождении соседних областей необходимо помнить,
что количество областей должно быть минимальным, а количество
клеток в каждой соседней области – максимальным, но кратно 2n.
При минимизации по единицам области на рис. 1 представлены
сплошной линией. Каждой соседней области нужно поставить в соответствие конъюнкцию, в которой отсутствуют переменные, изменяющие в этой области свое значение. При получении соседних областей используются клетки с прочерками, которые увеличивают
площадь соседних областей. Полученные конъюнкции объединяются знаками дизъюнкции. Получаем выражение функции в ДНФ:
f(A,B,C,D) =BD ∨ AB ∨ A B D ∨ B C D,
(3)
Сумма рангов полученного выражения R = 10.
При минимизации по нулям области на рис. 1 представлены штриховыми линями. Каждой соседней области нужно поставить в соответствие дизъюнкцию, в которой отсутствуют переменные, изменяющие в этой области свое значение. При получении соседних областей
используются клетки с прочерками, которые увеличивают площадь
соседних областей. Полученные дизъюнкции объединяются знаками конъюнкции. Получаем выражение функции в КНФ:
f(A,B,C,D) = (B ∨ D) (A ∨B ∨C)(A ∨B ∨D).
(4)
Сумма рангов полученного выражения R = 8.
А
1
–
1
–
–
1
1
1
D
1
–
C
Рис. 1
8
Переведем оба выражения (3) и (4) в базисы Шеффера и Пирса.
При переводе в базис Шеффера воспользуемся законами де Моргана:
x Ú y = x y.
Таким образом, двойное отрицание возьмем для всего выражения, т. е. поставим его над знаками дизъюнкции, от которых нужно
избавиться:
f ( A, B, C, D) = B D Ú AB Ú ABD Ú BCD = B D Ú AB Ú ABD Ú BCD =
(
)
= S S ( B, D ), S ( A, B), S ( A, B, D ), S ( B, C, D ) . (5)
Построим логическую схему (рис. 2). Поскольку в выражении
присутствуют как прямые, так и инверсные переменные, можно
воспользоваться парафазным кодом подачи переменных.
При переводе ДНФ в базис Пирса воспользуемся законами де
Моргана:
xy = x Úy.
Таким образом, двойное отрицание возьмем от элементарных
конъюнкций в ДНФ, т. е. поставим его над знаками конъюнкций,
от которых нужно избавиться:
=
f ( A, B, C, D ) B=
D ∨ AB ∨ ABD ∨ BCD
(
) (
) (
) (
)
= B∨ D ∨ A∨ B ∨ A∨ B∨ D ∨ B∨C∨ D =
;
–
–
–
–
AABBCCDD
&
&
&
f (A,B,C,D)
&
&
Рис. 2
9
чтобы получить выражение в базисе Пирса, необходимо поставить
двойное отрицание над знаками дизъюнкций, т. е.
) (
(
) (
) (
)
= BÚD Ú AÚB Ú AÚBÚD Ú BÚCÚD =
(
(6)
)
= PP P ( B, D ), P ( A, B), P ( A, B, D ), P ( B, C, D ) .
Построим логическую схему (рис. 3). Поскольку в выражении (6)
имеются инверсные переменные, воспользуемся парафазным кодом
подачи переменных.
Переведем в базисы Шеффера и Пирса выражение функции
в КНФ (4). При переводе КНФ в базис Шеффера двойное отрицание
возьмем от отдельных дизъюнкций, т. е.
f ( A, B, C, D) = ( B Ú D )( A Ú B Ú C)( A Ú B Ú D) =( ÂD )( ABC )( ABD ) =;
для получения выражения в базисе Шеффера нужно добавить двойное
отрицание над знаками конъюнкций, объединяющих термы, т. е.
(
(
))
= ( ÂD )( ABC )( ABD ) = SS S ( B, D ), S ( A, B, C ), S A,B, D .
Затем представим логическую схему (рис. 4). Поскольку в выражении (7) присутствуют инверсные переменные, воспользуемся парафазным кодом подачи переменных.
–
–
–
–
AABBCCDD
1
1
1
1
1
Рис. 3
10
1
f(A,B,C,D)
Чтобы получить выражение в базисе Пирса от КНФ, необходимо
поставить двойное отрицание над знаками конъюнкции, которые
отсутствуют в базисе Пирса, т. е.
f ( A, B, C, D ) = ( B Ú D )( A Ú B Ú C )( A Ú B Ú D ) =
= (B Ú D) Ú ( A Ú B Ú C) Ú ( A Ú B Ú D) =
(
(8)
)
= P P ( B, D ), P ( A, B,C ), P ( A, B, D ) .
Построим логическую схему (рис. 5). Поскольку в выражении (8)
имеются инверсные переменные, воспользуемся парафазным кодом
подачи переменных.
–
–
–
–
AABBCCDD
&
&
&
&
f(A
( ,B,C,D)
(A
f(A,B,C,D)
&
Рис. 4
–
–
–
–
AABBCCDD
1
[
1
[
1
f(A,B,C,D)
1
[
Рис. 5
11
2.3. Содержание отчета по контрольной работе
1. Таблица истинности для функции, зависящей от четырех переменных. Данные для таблицы истинности берутся из таблицы вариантов заданий для контрольной работы (п. 2.4).
2. Выражения функции в СДНФ и СКНФ.
3. Диаграмма Вейча, построенная по таблице истинности.
4. Выражения функции в ДНФ и КНФ, полученные по диаграмме Вейча при минимизации функции по единицам и по нулям.
5. Перевод ДНФ и КНФ в базисы Шеффера и Пирса.
6. Логические схемы в базисах Шеффера и Пирса для парафазного кода подачи переменных.
2.4. Варианты заданий для контрольной работы
Варианты заданий представлены в табл. 2.
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Таблица 2
1
0
0
1
–
–
1
0
0
1
0
–
1
–
–
1
0
2
0
1
–
0
1
–
–
1
0
–
1
0
0
1
0
0
3
1
0
–
1
–
1
–
1
0
1
–
0
1
–
1
0
4
1
–
1
0
1
–
1
–
–
1
0
–
1
–
0
0
5
–
1
1
0
–
0
1
1
0
–
–
1
1
0
–
0
6
0
–
1
1
–
0
0
–
1
–
0
1
1
–
0
0
7
–
0
1
1
0
0
1
0
0
1
–
0
1
–
0
1
8
1
0
–
1
0
1
0
1
–
1
0
0
–
–
1
1
9
0
1
–
0
1
1
1
–
0
–
0
1
1
1
–
0
10
–
0
1
1
0
–
0
1
1
1
1
0
–
0
1
1
11
1
0
–
1
0
0
–
–
–
0
0
1
–
–
1
0
12
0
1
0
–
1
0
1
1
1
0
–
–
0
1
1
1
13
0
–
1
–
0
1
0
–
1
–
0
1
0
1
0
0
14
–
0
–
1
0
–
1
0
–
0
1
1
1
0
–
0
15
0
1
–
0
–
–
0
1
1
1
0
–
0
1
1
0
16
0
0
–
0
1
–
–
1
1
0
0
–
0
1
1
0
12
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Окончание табл. 2
17
–
0
–
0
–
1
1
0
0
1
1
–
1
1
0
0
18
0
–
0
–
1
1
1
1
0
1
1
0
–
0
–
0
19
–
0
1
–
0
0
0
1
–
–
1
0
–
0
1
1
20
0
0
–
1
1
1
1
0
–
0
–
0
1
1
0
0
21
1
–
–
–
1
0
–
–
1
0
0
1
0
–
–
1
22
0
0
0
–
0
–
1
1
0
1
–
–
1
–
1
0
23
0
1
0
0
1
–
–
1
–
–
0
1
–
1
0
–
24
1
–
–
–
0
–
1
1
1
0
–
–
1
0
–
1
13
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Мишура О. В., Попов В. П. Дискретная математика. Теория множеств. Минимизация логических функций при помощи диаграмм
Вейча: учеб.-метод. пособие, СПб.: ГУАП, 2016.
2. Пятибратов А. П., Кирпиченко А. А., Гудьно Л. П. Вычислительные системы, сети и телекоммуникации. М.: Финансы и статистика, 2002.
3. Фрикс К. Вводный курс цифровой электроники. М.: Техносфера, 2004.
14
СОДЕРЖАНИЕ
1. Цели и задачи дисциплины,
ее место в учебном процессе.......................................... 3
2. Контрольная работа.................................................. 6
2.1. Формулировка задания к контрольной работе........ 6
2.2. Пример выполнения контрольной работы.............. 6
2.3. Содержание отчета по контрольной работе............. 12
2.4. Варианты заданий для контрольной работы .......... 12
Библиографический список........................................... 14
15
Документ
Категория
Без категории
Просмотров
3
Размер файла
586 Кб
Теги
mishurapopov
1/--страниц
Пожаловаться на содержимое документа