Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Южно – Российский государственный технический университет
(Новочеркасский политехнический институт)
Шахтинский институт (филиал) ЮРГТУ (НПИ)
Методические указания
к лабораторным занятиям по дисциплине
“Дискретная математика”
Новочеркасск 2008
УДК 517.8
Рецензент – канд. физ – мат. наук Б. Х. Олигов
Составитель Романенко Г. Н.
Методические указания к лабораторным занятиям по дисциплине “Дискретная математика”/
Сост. Г.Н. Романенко; Шахтинский ин-т (филиал) ЮРГТУ (НПИ). – Новочеркасск: ЮРГТУ, 2008. –
24 с. – 50 экз.
Даны указания и приведены задания к лабораторным занятиям по дисциплине “Дискретная математика”.
Предназначены для студентов специальности 230201 (071900) “Информационные системы и технологии”.
УДК 517.8
© Шахтинский институт ЮРГТУ, 2008
© Романенко Г.Н., 2008
Введение
Математика является базой для рационального решения большей части инженерных задач. Современная математика развивается преимущественно в интересах решения прикладных задач. Дискретная математика – это область математических знаний, предметом рассмотрения которой являются дискретные величины, объекты и процессы. Все современные устройства обработки информации являются дискретными устройствами. Логические устройства и средства компьютерной техники оперируют с числовой информацией, представленной в дискретной форме.
В данной работе приведены задания к лабораторным работам по курсу “Дискретная математика”, даны методические указания к выполнению лабораторных работ.
Цель методических указаний: активизировать самостоятельную работу студентов и способствовать освоению основных положений и математических методов решения задач теории множеств, теории графов, теории булевых функций, математической логики.
Алгебра высказываний
Таблица истинности
Таблица истинности формулы алгебры высказываний содержит столько строк, сколько всевозможных наборов значений истинности переменных можно образовать. В случае n переменных таблица истинности содержит строк. При построении таблицы истинности наборы значений переменных располагаются сверху вниз в лексикографическом порядке. Затем, в соответствии с порядком действий, последовательно заполняют столбцы подформул, из которых образуется формула. Последним заполняется столбец значений истинности формул.
Пример 1. Построить таблицу истинности формулы ≡ x → z, (В дальнейшем знак ► означает начало доказательства, решения примера и т. д., а знак ◄ - окончание).
► Определим порядок действий в формуле
x z.
Пользуясь определениями операций , , →, заполним таблицу 1.:
Таблица 1
Таблица истинности
| x | y | z |
| x | x → z |
| 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 | 1 |
◄
Упрощение формул
Первым шагом при решении задач на упрощение формул является переход к булевым операциям с помощью формул
a → b ≡ b,
a b ≡ ab .
Успешное решение примера зависит от умелого, эффективного применения основных равносильностей булевой алгебры высказываний.
Пример 1.С помощью равносильных преобразований упростить формулу
≡ x → z.
►Перейдем к булевым операциям и воспользуемся основными равносильностями булевой алгебры высказываний:
≡ x → z ≡ z ≡ z ≡ y z.◄
1.3 Двойственность в алгебре высказываний
Булев принцип двойственности состоит в следующем: формула двойственная к булевой формуле получается заменой , , 0 на 1, 1 на 0 и сохранением структуры формулы.
Пример 1. Найти формулу, двойственную к формуле
≡ x → z.
►Воспользовавшись булевым принципом двойственности, найдем формулу (, двойственную к формуле :
( ≡ ≡ ( у)z.◄
1.4 Нормальные формы
Нормальные формы формул алгебры высказываний бывают двух типов: дизъюнктивные и конъюнктивные, в каждом из этих типов выделен класс совершенных форм. СДНФ и СКНФ можно строить по таблице истинности формулы или с помощью равносильных преобразований.
Пример 1.Для формулы ≡
≡ xy z найти СДНФ и СКНФ по таблице истинности.
►Схема построения СДНФ и СКНФ по таблице истинности приведена ниже для формулы ≡ xy z:
Таблица 2
Построение СДНФ, СКНФ
| x | y | z | xy | xy z |
| 0 | : 1px solid #000000; border-bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: none; padding-top: 0in; padding-bottom: 0in; padding-left: 0.08in; padding-right: 0in;">0 | 0 | 0 | 1→ |
| 0 | 0 | 1 | 0 | 0→xy |
| 0 | 1 | 0 | 0 | 1→ |
| 0 | 1 | 1 | 0 | 0→x |
| 1 | 0 | 0 | 0 | 1→x |
| 1 | 0 | 1 | 0 | 0→ |
| 1 | 1 | 0 | 1 | 0→ |
| 1 | 1 | 1 | 1 | 1→xyz |
≡ x xyz – СДНФ
≡ (xy)( x)()() –СКНФ◄
Множества
2.1.Операции над множествами. Подмножество
При решении задач этого раздела нужно знать определения подмножества и основных операций над множествами.
Пример 1. Пусть А = , В = . Найти АВ, АВ, АВ, ВА, АВ.
►По определению операций над множествами получим:
АВ = ; АВ ={4}; АВ = {1, 5},
ВА = {2};AB = {1, 2, 5}. ◄
Пример 2. Найти все подмножества множества А ={1, 4, 7}.
►Множество всех подмножеств множества А обозначается ,
= {, {1}, {4}, {7}, {1, 4}, {1, 7}, {4, 7}, {1, 4, 7}},
, А – несобственные подмножества А, остальные подмножества - собственные.◄
Булева алгебра множеств
Основным типом примеров этого пункта является доказать равенство множеств, заданных формулами алгебры множеств. Решение таких примеров следует начинать с построения диаграмм Виенна для левой и правой частей. Если картинки не совпали, то вы уже решили пример и показали, что равенство не имеет места. В противном случае рекомендуется перейти к булевым формулам алгебры множеств и воспользоваться основными равенствами булевой алгебры множеств.
Пример 1. Доказать, что А(АВ) = АВ,
►Построим диаграммы Виенна левой и правой частей (рис. 1.1).
левая часть
→ →
AB A(AB)
правая часть
→
АВ
Рис.1.1. Диаграммы Виенна
Перейдем к булевым формулам алгебры множеств:
А(АВ) = А = А = А() = = А(В) = (А) (А) = (АВ) = = АВ◄
Графы
Во многих задачах теории графов графы удобно описывать матрицами. Выделяют матрицу смежности и матрицу инцидентности.
Пример 1. Для графа G, приведенного на рис. 1.2, найти матрицу смежности A(G) и матрицу инцидентности B(G).
Рис. 1.2. Граф G
►По определению:
A = ,
B = .◄
Минимизация булевых функций
Минимизация – это упрощение логических выражений путем уменьшения количества операций и символов в формулах, которые реализуют булевые функции. Одной из целей минимизации является упрощение логических устройств и достижение максимальной экономичности разрабатываемых систем.
Для минимизации булевых функций используется ряд методов, среди которых наибольшее применение находят:
метод неопределенных коэффициентов;
метод Квайна – Мак Класски.
Пример 1. Методом неопределенных коэффициентов минимизировать функцию = Y.
►Представим функцию в виде ДНФ самого общего вида:
= 1 2 3 ,
где , ,…, - неопределённые коэффициенты, принимающие значение 0 или 1 и подбираемые так, чтобы получающаяся после этого ДНФ была минимальной.
Подставив наборы значений переменных в ДНФ, получим:
После вычёркивания нулевых коэффициентов имеем:
Результат:
Ответ:
5. Задания к лабораторным работам
Лабораторная работа №1
Таблицы истинности. Нормальные формы
Цель работы:научиться строить таблицы истинности формул алгебры высказываний, упрощать формулы, находить двойственные формулы и совершенные нормальные формы.
Задания.
Для данной формулы алгебры высказываний:
а) построить таблицу истинности;
б) найти двойственную формулу и построить таблицу истинности двойственной формулы;
в) найти СДНФ и СКНФ по таблице истинности с помощью равносильных преобразований.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
Лабораторная работа №2
Алгебра множеств
Цель работы:освоить основные понятия теории множеств, научиться решать типовые задачи.
Задания.
1) Для данного универсального множества Е и данных множеств А и В найти
А .
2) Для данного универсального множества
Е и данных множеств А и В найти
.
3) Доказать равенства.
=
=
Лабораторная работа №3
Графы и их матрицы
Цель работы:освоить основные понятия теории графов, находить матрицы графов.
Задания.
Для данного графа G(X,U,f) найти:
а) число связности C(G) и число сильной связности SC(G).
б) мосты ;
в) хроматическое число X(G) ;
г) матрицу смежности A(G) ;
д) матрицу инцидентности B(G).
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
Лабораторная работа №4
Минимизация булевых функций
Цель работы:научиться минимизировать булевые функции методом неопределённых коэффициентов и методом Квайна – Мак Класки.
Задания.
Данную булеву функцию f минимизировать:
а) методом неопределённых коэффициентов;
б) методом Квайна – Мак Класки.
f(X1, X2, X3, X4) = Y(0,1,5,7)
f(X1, X2, X3, X4) = Y(2,6,7,8,10)
f(X1, X2, X3, X4) = Y(0,1,2,1,2,13)
f(X1, X2, X3, X4) = Y(2,4,5,10,14)
f(X1, X2, X3, X4) = Y(3,4,8,9,10)
f(X1, X2, X3, X4) = Y(0,1,4,5,12)
f(X1, X2, X3, X4) = Y(0,3,4,6,7)
f(X1, X2, X3, X4) = Y(0,1,2,3,9,10)
f(X1, X2, X3) = Y(0,2,4,5)
f(X1, X2, X3) = Y(0,1,5,6)
f(X1, X2, X3, X4) = Y(2,5,6,10,11)
f(X1, X2, X3, X4) = Y(0,1,5,7,8)
f(X1, X2, X3, X4) = Y(2,4,6,10)
f(X1, X2, X3, X4) = Y(0,5,6,7,8,9)
f(X1, X2, X3, X4) = Y(0,4,6,12,14)
f(X1, X2, X3) = Y(0,1,2,3,4,7)
f(X1, X2, X3, X4) = Y(2,4,6,8,10)
f(X1, X2, X3) = Y(3,5,6,9,10)
f(X1, X2, X3, X4) = Y(0,1,3,7,8,9)
f(X1, X2, X3) = Y(1,5,6,7,8)
f(X1, X2, X3, X4) = Y(0,1,2,3,4)
f(X1, X2, X3, X4) = Y(2,7,8,9,10)
f(X1, X2, X3, X4) = Y(3,6,7,9,10)
f(X1, X2, X3, X4) = Y(7,8,9,10,12)
f(X1, X2, X3, X4) = Y(10,11,12,14)
Библиографический список
Яблонский С. В. Введение в дискретную математику. Учебное пособие для вузов. / Под ред. В. А. Садовничего. – 3-изд., Высш. шк.; 2001. – 384с.
Романенко Г. Н. Курс лекций по дисциплине «Дискретный анализ». Шахтинский институт ЮРГТУ. Новочеркасск: ЮРГТУ, 2002. – 148с.
Учебно-практическое издание
Методические указания к лабораторным занятиям
по дисциплине «Дискретная математика»
Составитель Романенко Галина Николаевна
Редактор Кузнецова И. М.
Темплан 2008 г. Подписано в печать 10. 01. 08 г
Формат 60х841/16. Бумага офсетная. Ризография.
Усл.-печ.л. 1,39 . Уч.-изд. л. 1,5 . Тираж 50 экз.
Южно-Российский государственный технический университет
Адрес ун-та: 346428,г. Новочеркасск, ул. Просвещения, 132
Шахтинский институт (филиал) ЮРГТУ (НПИ)
Адрес ин-та:346500,г. Шахты, пл. Ленина, 1
26