рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Решение

Решение - раздел Математика, ДИСКРЕТНАЯ МАТЕМАТИКА Используя Законы Логики, Приведем Данную Формулу К Виду, Содержащему Только Д...

Используя законы логики, приведем данную формулу к виду, содержащему только дизъюнкции элементарных конъюнкций. Полученная формула и будет искомой ДНФ:

 

Для построения СДНФ составим таблицу истинности для данной формулы:

           

 

Помечаем те строки таблицы, в которых формула (последний столбец) принимает значение 1. Для каждой такой строки выпишем формулу, истинную на наборе переменных , , данной строки:

строка 1: ;

строка 3: ;

строка 5: .

Дизъюнкция этих трех формул будет принимать значение 1 только на наборах переменных в строках 1, 3, 5, а следовательно, и будет искомой совершенной дизъюнктивной нормальной формой (СДНФ):

.

Пример 4. Приведите формулу к СКНФ двумя способами:

а) с помощью равносильных преобразований;

б) с помощью таблицы истинности.

Решение:

a)

 

Преобразуем вторую элементарную дизъюнкцию:

.

Формула имеет вид:

 

 

 

б) составим таблицу истинности для данной формулы:

 

             

 

Помечаем те строки таблицы, в которых формула (последний столбец) принимает значение 0. Для каждой такой строки выпишем формулу, истинную на наборе переменных , , данной строки:

строка 2: ;

строка 6: .

Конъюнкция этих двух формул будет принимать значение 0 только на наборах переменных в строках 2 и 6, а следовательно, и будет искомой совершенной конъюнктивной нормальной формой (СКНФ):

.

 

Вопросы и задачи для самостоятельного решения

1. С помощью равносильных преобразований приведите к ДНФ формулы:

а) ;

б) ;

в) .

2. С помощью равносильных преобразований приведите к КНФ формулы:

а) ;

б) ;

в) .

3. С помощью второго дистрибутивного закона преобразуйте ДНФ в КНФ:

а) ;

б) .

 

 

4. Преобразуйте заданные ДНФ в СДНФ:

а) ;

б) ;

в) .

5. Преобразуйте заданные КНФ в СКНФ:

а) ;

б) ;

в) .

6. Для заданных логических формул постройте СДНФ и СКНФ двумя способами: с помощью равносильных преобразований и с помощью таблицы истинности.

а) ;

б) ;

в) .

 

 

3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

3.1. Основные понятия теории графов

Графы возникли в XVIII столетии, когда известный математик, Леонард Эйлер пытался решить теперь уже классическую задачу о Кёнигсбергских мостах. В то время в городе Кёнигсберге (Калининград) было два острова, соединенных семью мостами с берегами реки Преголь и друг с другом.

Задача состояла в том, что необходимо было совершить прогулку по городу таким образом, чтобы, пройдя ровно по одному разу по каждому мосту, вернуться в то же место, откуда начиналась прогулка.

В 1736 г. Эйлер показал, что сделать это невозможно.

С тех пор поток задач с применением графов нарастал. Однако теория графов как математическая дисциплина сформировалась только в середине 30-х гг. XX в. благодаря работам таких математиков, как Г. Кёниг,
Л.С. Понтрягин, А.А. Зыков и др.

Впервые же понятие «граф» ввел венгерский математик Д. Кёниг в 1936 г.

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

Определение 1.Неориентированным графом (или графом) называется совокупность двух множеств – непустого множества (множества вершин) и множества неупорядоченных пар различных элементов множества ( – множество ребер).

Обычно граф изображают в виде диаграммы, на которой вершины обозначаются точками, а ребра, соединяющие две вершины, – линиями между этими точками.

Например, изображение графа с множеством вершин и множеством ребер может иметь следующий вид (рис. 12).

Изображение графа с множеством вершин и множеством ребер может иметь вид, представленный на рис. 13.

 

   
Рис. 12 Рис. 13

 

Определение 2. Пусть – вершины, – соединяющее их ребро. Тогда вершина и ребро инцидентны, вершина и ребро также инцидентны, при этом называются концами ребра. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

Определение 3.Ребро, соединяющее вершину саму с собой, называют петлей. Ребра, инцидентные одной и той же паре вершин, называются параллельными, или кратными.

Определение 4.Степенью вершины называется удвоенное количество петель, инцидентных этой вершине, плюс количество остальных инцидентных ей ребер. Обозначение: . Вершина степени 0 называется изолированной, а степени 1 – висячей (концевой). Ребро, инцидентное висячей вершине, называют концевым.

Например,в графе (рис. 14) вершины и – смежные, и инцидентны ребру и являются его концами; – смежные ребра; вершины и не являются смежными, поскольку между ними есть вершина , и – не являются смежными ребрами:

, .

В графе (рис. 15) вершина – изолированная, вершина – висячая; ребро, соединяющее вершину саму с собой, образует петлю:

, , .

 

     
Рис. 14 Рис. 15

 

Теорема 1.Сумма степеней вершин графа всегда четная.

Теорема 2. Сумма степеней всех вершин графа равна удвоенному числу ребер, т. е. , где – число ребер.

Определение 5. Ребро, имеющее направление от одной вершины к другой, называется направленным (или ориентированным, или дугой) и изображается стрелкой, направленной от вершины, называемой началом, к вершине, именуемой концом. Граф, содержащий направленные ребра, называется ориентированным графом (или орграфом).

Замечание 1. В орграфе у каждой вершины две степени: входящая (число ребер, входящих в вершину) и исходящая (число ребер, выходящих из вершины). Петля несет вклад в обе степени по одному.

  Рис. 16
Например, изображение орграфа (рис. 16) с множеством вершин и множеством дуг .

Дуга : 1 – начало дуги, 2 – конец дуги; – петля; ребра , – кратные: , , , , .

Определение 6. Чередующаяся последовательность вершин и ребер в графе (или только ребер), в которой любые два элемента инцидентны, называется маршрутом. Количество ребер , входящих в маршрут, называют длиной маршрута.

Определение 7. Маршрут, все ребра которого различны, называется цепью, а маршрут, для которого различны все вершины, называется простой цепью.

Определение 8. Замкнутая цепь называется циклом, а замкнутая простая цепь – простым циклом.

Определение 9. Цикл, который содержит все ребра графа, называется эйлеровым циклом. Простой цикл, содержащий все вершины графа, называется гамильтоновым.

Например, в графе (рис. 17):

– маршрут, но не цепь (длина – 3);

– цепь, но не простая цепь (длина – 5);

– простая цепь (длина – 4);

– цикл, но не простой цикл (длина – 6);

– простой цикл (длина – 3).

Определение 10.Для орграфов цепь называется путем, а цикл – контуром.

Например, в орграфе (рис. 18):

и – пути;

– контур.

 

   
Рис. 17 Рис. 18

Основные виды графов:

1) мультиграф – граф, содержащий кратные ребра;

2) граф с петлями – граф, содержащий петли (рис. 15);

3) псевдограф – граф, содержащий как петли, так и кратные ребра (рис. 16);

4) простой граф – граф без петель и кратных ребер (рис. 14);

5) полный граф – простой граф, в котором каждая пара вершин соединена ребром (рис. 19);

6) дерево – простой граф, не содержащий циклов;

7) эйлеровый граф – граф, содержащий эйлеровый цикл;

8) гамильтоновый граф – граф, содержащий гамильтоновый цикл.

 

 

Рис. 19

 

Вопросы и задачи для самостоятельного решения

1. Для следующего графа (рис. 20):

а) выпишите смежные вершины и смежные ребра;

б) выпишите вершины с инцидентными ребрами;

в) определите степени каждой вершины графа;

г) укажите, как называются вершины ; ребра V и VI;

д) укажите, как называется такой граф.

2. Для следующих графов определите, чем являются последовательности ребер и вершин.

2.1. Для графа на рис. 21:

а) ; в) ;

б) ; г) .

2.2. Для графа на рис. 22:

а) ; в) ;

б) ; г) .

2.3. Для графа на рис. 23: .

3. Для следующего графа (рис. 24):

а) выпишите степени всех вершин;

б) определите, чем являются последовательности ребер и вершин: 1, 2, 1, 3, 4 и 1, 2, 4.

 

   
Рис. 20 Рис. 21

 

     
Рис. 22 Рис. 23 Рис. 24

 

4. Найдите эйлеровый граф (рис. 25).

а


в
б

Рис. 25

 

3.2. Способы задания графов

В подразд. 3.1 мы уже познакомились с двумя способами описания графов: в виде задания двух множеств вершин и ребери графичес­ким способом.

Рассмотрим другие способы задания графов.

1. Матрица инцидентности.

Пусть дан граф , где – количество вершин, – количество ребер, тогда матрица инцидентности имеет размер .

Для неориентированного графа она имеет вид

 

Для орграфа

 

Замечание 1.Если граф без петель, то в матрице смежности по главной диагонали стоят нули.

Пример 1.Составьте матрицы инцидентности для следующих графов (рис. 26, а, б).

 

а

 

б

Рис. 26

Решение:

а) ; б) .

В каждом столбце матрицы инцидентности неориентированного или ориентированного графа только два элемента отличны от нуля (или один, если ребро является петлей). Для матрицы инцидентности ориентированного графа либо столбец содержит один элемент, равный 1, либо один элемент, равный , либо столбец нулевой.

Отношение инцидентности можно еще задать списком ребер графа. Каждая строка этого списка соответствует ребру, в котором записаны номера вершин, инцидентных ему.

2. Матрица смежности.

Пусть дан граф , где – количество вершин, тогда матрица смежности отражает смежность вершин и имеет размер .

Для неориентированного графа она имеет вид

 

Для орграфа

 

Для неориентированного мультиграфа значение равно количеству ребер, инцидентных i-й и j-й вершинам, для ориентированного графа этот элемент матрицы смежности равен количеству ребер с началом в i-й вершине и концом в j-й. Таким образом, матрица смежности неориентированного графа симметрична, а ориентированного – не обязательно симметрична.

Пример 2. Найдите матрицы смежности для графов (рис. 27, а, б).

 

а
б

 

Рис. 27

– Конец работы –

Эта тема принадлежит разделу:

ДИСКРЕТНАЯ МАТЕМАТИКА

Федеральное агентство железнодорожного транспорта... Федеральное государственное бюджетное образовательное учреждение высшего... Дальневосточный государственный университет путей сообщения...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Решение

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Васильева, В.С.
В 191 Дискретная математика : учеб. пособие / В.С. Васильева, С.В. Коровина, Л.В. Марченко. – Хабаровск : Изд-во ДВГУПС, 2013. – 119 с. : ил.   Учебное пособ

Решение
Мера множества – это площадь фигуры. Для данного примера – это площадь треугольника: ед2. Вопросы и задачи для самостоятельного решения 1. Какие из приведенных заданий

Решение
а) множество состоит из элементов: . Так как объединению множеств и принадлежат элементы, входящие или во множество или во множество , причем одинаковые элементы включаются только один раз, то ;

Решение
Выпишем элементы, из которых состоят множества и . Тогда , т. е. симметрическая разность состоит из пяти элементов. Вопросы и задачи для самостоятельного решения 1. Дайте определе

Решение
Построим множество, соответствующее левой части заданного тождества. Множество представлено закрашенной областью на рис. 6, а. Множеству соответствует закрашенная область на рис. 6, б

Решение
= /закон де Моргана/ = = = /закон дистрибутивности/ = = = /закон коммутативности/ = = = /закон дистрибутивности/ = = = /закон коммутативности/ =

Решение
Введем обозначения: ; ; ; . Из условия задачи: , , , , , , и . Тогда . Откуда , т. е. – количество студентов, занимающихся туризмом.

Решение
В соответствии с определением декартова произведения – множество точек, расположенных в квадрате с вершинами , , и (рис. 10).     Рис. 10

Свойства бинарных отношений
1.Бинарное отношение на множестве рефлексивное, если для всякого выполняется . 2.Бинарное отношение на множестве антирефлексивное, если для

Решение
. Подставим , получим ; , получим . Прообразом отображения (в силу непрерывности функции) являются те , которые попадают в отрезок , тогда . Пример 3. О

Решение
Выделим простые высказывания и запишем их через переменные: – «ветра нет»; – «пасмурно»; – «дождь». Запишем логические функции (сложные высказывания) через введенные переменные:

Алгоритм построения нормальных форм
1. С помощью равносильностей алгебры логики заменить все имеющиеся в формуле операции основными: конъюнкцией, дизъюнкцией, отрицанием: ; ; . 2. Заменить знак отр

Решение
Изображение графа представлено на рис. 28. Рис. 28 Так как у графа пять вершин, то матрица смежности будет : Вопросы и задачи

Решение
Применяя формулу для числа перестановок, запишем соотношение в виде . Подберем значение , исходя из равенств , , , , , . Следовательно, , откуда и . Вновь рассмотрим множ

Решение
Применяя формулы для числа перестановок и числа размещений, запишем соотношение в виде . После сокращения получим , , , . Поскольку число натуральное, то смысл имеет только значение .

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги