МЕТОДИЧЕСКИЕ УКАЗАНИЯ по решению контрольных заданий для обучающихся по заочной форме обучения по предмету «Элементы математической логики» Специальность: 09.02.04 «Информационные системы»
методическая разработка на тему

Министерство образования и науки Хабаровского края

Краевое государственное бюджетное профессиональное образовательное учреждение

«Хабаровский промышленно – экономический техникум»

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

по решению контрольных заданий

для обучающихся по заочной форме обучения

по предмету «Элементы математической логики»

Специальность: 09.02.04  «Информационные системы»

2016 г

Составители:

преподаватель КГБ  ПОУ  ХПЭТ             ____________________            М. С. Серганова

Содержание

1 Введение

Методические указания по решению контрольных заданий для обучающихся по заочной форме обучения по предмету «Элементы математической логики», специальность  09.02.04  «Информационные системы», предназначены для изучения этого предмета в КГБ ПОУ ХПЭТ, реализующего программу подготовки специалистов среднего звена. Эти указания составлены в соответствии с методическими рекомендациями.

В методические указания входят:

1.        Введение.

2.        Примерная программа учебной дисциплины с перечнем рекомендуемой литературы, методическими указаниями по изучению каждой темы программы и вопросы для самоконтроля.

3.        Задания для контрольных работ.

4.        Перечень практических и самостоятельных работ.

5.        Вопросы для подготовки к зачету.

6.        Перечень рекомендуемой литературы для изучения предмета.

7.        Примеры решения задач.

При изучении предмета «Элементы математической логики» у обучающихся формируется информационно-коммуникационная компетентность – знания, умения, навыки, необходимые для изучения других общеобразовательных предметов, для их использования в ходе изучения специальных дисциплин профессионального цикла, в практической деятельности и повседневной жизни. Выполнение практических работ обеспечивает формирование у обучающихся умение собирать данные для анализа использования и функционирования информационной системы, взаимодействовать со специалистами смежного профиля при разработке методов, средств и технологий применения объектов профессиональной деятельности.

Методические указания содержат примерную тематику учебных проектов для организации самостоятельной деятельности обучающихся в процессе изучения предмета «Элементы математической логики».

2 Примерная программа учебной дисциплины с перечнем рекомендуемой литературы, методическими указаниями по изучению каждой темы программы и вопросы для самоконтроля.

2.1 Структура и примерное содержание учебной дисциплины.

Объем учебной дисциплины и виды учебной работы

Таблица 1 – Объем учебной дисциплины и виды учебной нагрузки

2.2 Примерный тематический план и содержание учебной дисциплины «Элементы математической логики»

Таблица 2 - тематический план и содержание учебной дисциплины «элементы математической логики»

2.3 Методические указания по изучению тем программы:

Раздел 1 Теория множеств.

Множество- это любая определенная совокупность объектов. Объекты, из которых состоит множество, называется его элементами или точками – Если а элемент множества А, то пишут а∈А. Если А и В состоят из одних и тех же элементов, то говорят, что они совпадают, и пишут А=В.

Подмножеством множества А называется такое множество В, каждый элемент которого принадлежит множеству А.

Объедининением множеств А и В называется множество А∪В, содержащее все элементы множества А и множества В, которые принадлежат хотя бы одному из множеств А или В.

А∪В={x/x∈A∨x∈B}

Пересечением множеств А и В называется множество А∩В, содержащее те элементы множества А и множества В, которые входят одновременно в оба множества, А∩В={x/x∈а∧x∈B}

Разностью множеств А и В называется множество А\В, состоящее из тех элементов,  которые лежат в А, но не лежат в В.

A\B={x/x∈A∧x∉B}

Дополнением множества А называется множество , состоящее из всех элементов, которые не принадлежат А={x/x∉A}

Пусть А и В множества, а∈А, b∈B, запишем их в определенные пары и обозначим

(a,b), такая пара элементов называется упорядоченной. Две упорядоченные пары (a,b) и (c,d)называются равными, если равны их соответственные элементы: a=c∧b=d

Прямым(декартовым)произведением множств AиBназывается множество всех упорядоченных пар этих множеств.

AB={(a,b)/a∈A,b∈B},ABB×A

Если A=B, то А×А=А2называется декартов квадрат. Любое подмножество прямого произведения А×В называется бинарным отношением  р между элементами этих множеств. p∈A×В , элементами отношения являются упорядоченные пары,  форма записи a p b, (a,b)∈p, означает, что a и bнаходятся в отношении p. Если АВ, то говорят о бинарном отношении на множестве А.

Свойства бинарных отношений

1. Бинарное отношение р, заданное на множестве А, называется рефлексивным, если элемент этого множества находится в данном отношении сам с собой ∀а∈А,(а,а)∈р
2. Бинарное отношение р, заданное на множестве А, называется симметричным, если для любых элементов a, b, c∈Aиз того, что (a,b)∈p⇒ (b,a)∈p
3. Бинарное отношение р, заданное на множестве А, называется транзитивным, если для любых элементов a, b, c∈Aвыполняется (a,b)∈p∧(b,c)∈p
4. Бинарное отношение р, заданное на множестве А, называется антисимметричным, если для любых элементов a,b∈A,(a,b)∧(b,a)∈p⇒a=b;(a,b)∈p∧a≠b ⇒(a,b)∉p
5. Бинарное отношение р, заданное на множестве А, называется связанным, если для любых элементов a,b∈A,a=b∨(a,b)∈p∨(b,a)∈p
6. Бинарное отношение р, заданное на множестве А, называется антирефлексивным, если ∀a∈A,(a,a)∉p

Раздел 2 Логика высказываний.

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

Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами:

А = {Аристотель – основоположник логики};

B = {На яблонях растут бананы}.

Истинному высказыванию ставится в соответствие 1, ложному – 0. Таким образом, А = 1, В = 0.

Составные высказывания на естественном языке образуются с помощью союзов, которые в алгебре высказываний заменяются на логические операции. Логические операции задаются таблицами истинности и могут быть графически проиллюстрированы с помощью диаграмм Эйлера-Венна.

Таблицу, показывающую, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний, называют таблицей истинности составного высказывания

Логическая операция конъюнкция (логическое умножение):

• в естественном языке соответствует союзу и;
• в алгебре высказываний обозначение ∧;

Конъюнкция – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны.

Логическая операция дизъюнкция (логическое сложение):

• в естественном языке соответствует союзу или;
• обозначение  ;

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

Логическая операция инверсия (отрицание):

• в естественном языке соответствует словам неверно, что… и частице не;
• обозначение ;

Инверсия – это логическая операция, которая каждому простому высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается.

Таблица истинности инверсии

Логическая операция импликация:

Импликация – логическая операция, ставящаяся в соответствии каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда первое высказывание истинно, а второе ложно.

Таблица истинности операции импликации:

Логическая операция эквивалентность:

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

Таблица истинности операции эквивалентности:

Раздел 3 Булевы функции.

Логической (булевой) функцией (или просто функцией) n переменных y = f(x1, x2, …, xn) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1.

Переменные, которые могут принимать только два значения 0 и 1 называются логическими переменными (или просто переменными). Заметим, что логическая переменная х может подразумевать под числом 0 некоторое высказывание, которое ложно, и под числом 1 высказывание, которое истинно. Например, высказывание “Волга впадает в Каспийское море” является истинным и, значит, с точки зрения дискретной математики принимает значение 1, а высказывание “в неделе 8 дней” является ложным, и переменная, которая заменяет это высказывание, принимает значение 0. Имеется много высказываний, которые либо истинны, либо ложны, но о которых мы не знаем, что имеет место на самом деле. Например, высказывание “студент Петров (имеется в виду конкретный человек) имеет дома компьютер”. Такого рода высказывания требуют проверки (конечно, если нам важен этот факт). Поэтому считаем, что переменная, заменяющая это высказывание может принимать значение 0 или 1.

Из определения логической функции следует, что функция п переменных – это отображение Еп в Е, которое можно задать непосредственно таблицей, называемой таблицей истинности данной функции. Например, функция трех переменных f(x,y,z) может определяться следующей таблицей истинности.

Это означает, что f(0,0,0) = 1, f(0,0,1) = 0, f(0,1,0) = 1 и т. д.

Две функции равны, если совпадают их таблицы истинности (на объединенном наборе переменных). При таком задании наборы Еп всегда упорядочены естественным образом, это позволяет определять функцию только последним столбцом (который иногда для экономии места записывается в строчку). Например, в нашем примере функцию f(x,y,z) можно задать так: f = (10110100), это означает, что последний столбец таблицы истинности. Заметим, что все функции п переменных также можно перенумеровать по принципу “скользящей единицы”. Теоретически число таких функций – 22n но некоторые из них являются по существу функциями меньшего числа переменных, а две – вообще константами. Если фактически функция не зависит от некоторой переменной, то такую переменную называют фиктивной.

Теперь можно описать основные функции дискретной математики.

Функции одной переменной y=f(x). Перенумеруем эти функции (их 4) естественным образом и расположим в виде таблицы:

Видно, что f0 (х) = 0, a f3 (х) =1, т. е. эти две функции не зависят от х, f1 (х) = х, т. е. она не меняет аргумента. Функция f2 (х) действительно содержательная функция. Она принимает значения, противоположные значениям аргумента, обозначается f2 (х)= и называется отрицанием (применяют еще обозначение ù x (читается “не x”)). Функции двух переменных z = f(x,y). Число этих функций равно 24 = 16. Перенумеруем и расположим их тоже в естественном порядке. Рассмотрим более подробно эти функции. Две из них f0 = 0 и f15 = 1 являются константами. Функции являются по существу функциями одной переменной. Наиболее важные функции двух переменных имеют специальные названия и обозначения. Заметим, что эти обозначения не всегда общеприняты.

Полином Жегалкина.

Познакомимся с определением полинома:

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

Причем, такое представление единственное.

Эта сумма называется многочленом Жегалкина.

Существует два способа представления булевой функции в виде полинома: метод неопределенных коэффициентов и метод построения полином по формуле. Опишем каждый метод подробно.

Метод неопределенных коэффициентов.

Перепишем полином в виде :

где Ki – конъюнкции, число которых равно 2n – 1, - вектор коэффициентов, где bI Î{0,1}.

Коэффициент bI указывает на присутствие или отсутствие соответствующей конъюнкции в полиноме.

Алгоритм поиска вектора коэффициентов и составления полинома.

1. по таблице истинности составить систему уравнений ,где (a1 , a2 , …, an) - все наборы значений переменных таблицы истинности для данной булевой функции (вместо переменных в полином подставить их соответствующие значения, в левой части уравнения – соответствующее этому набору значение функции).

3. пользуясь таблицей истинности для двоичного сложения и конъюнкции, вычислить коэффициенты bI ;

4. подставить в полином значения коэффициентов и составить полином.

Представление булевой функции в виде полинома называется разложением функции в многочлен или в полином.

Рассмотрим пример.

Разложить функцию f(x, y, z) = (01101000).

Составим полином 

Cоставляя уравнения, нулевые конъюнкции будем исключать:

№1 = 23-3: (001): 0 = b0+ b3;

№2 = 23-2 : (010): 1= b0+b2;

№3 = 23-2+23-3: (011): 1= b0+b2+b3+b6;

№4 = 23-1: (100): 0= b0+b1;

№5 = 23-1+23-3: (101): 1 = b0+b1+b3+b5;

№6 = 23-1+23-2: (110): 0 = b0+b1+b2+b4;

№7: (111): 0= b0+b1+b2+b3+b4+b5+b6+b7;

№8: (000): 0 = b0.

Решая систему , получим вектор коэффициентов: (0,0,1,0,1,1,0,1), тогда функция раскладывается в полином:

P(x,y,z) = 0 + y +xy + xz +xyz.

Проверку можно выполнить, составив таблицу истинности для полинома.

 Построение полинома по формуле.

 Данный метод основан на применении равносильных преобразований данной булевой функции, представленной в виде формулы, к виду полинома.

Алгоритм построения полинома по формул:

1. заменить формулу равносильной, содержащей только операции конъюнкцию и отрицание:
2. снять отрицания, пользуясь равносильностью: 
3. раскрыть скобки:
4. упростить, используя идемпотентность : х+х =0, равносильность х+0=х.

Рассмотрим примеры.

Раздел 4 Логика предикатов.

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

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

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

Логика предикатов, как и традиционная формальная логика, расчленяет элементарное высказывание на субъект (буквально – подлежащее, хотя оно может играть и роль дополнения) и предикат (буквально – сказуемое, хотя оно может играть и роль определения).

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

Например, в высказывании «7 – простое число», «7» – субъект, «простое число» – предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом».

Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х – простое число». При одних значениях х (например, х = 13, х = 17) эта форма дает истинные высказывания, а при других значениях х (например, х = 10, х = 18) эта форма дает ложные высказывания.

Определение 1. Одноместным предикатом Р(х) называется всякая функция одного переменного, в которой аргумент x пробегает значения из некоторого множества M, а функция при этом принимает одно из двух значений: истина или ложь.

Множество M, на котором задан предикат, называется областью определения предиката.

Множество , на котором предикат принимает только истинные значения, называется областью истинности предиката Р(х).

Так, предикат P(x) – «х – простое число» определён на множестве N, а множество  для него есть множество всех простых чисел.

Определение 2. Предикат Р(х), определённый на множестве M, называетсятождественно истинным (тождественно ложным), если .

Определение 3. Двухместным предикатом P(x,у) называется функция двух переменных х и у, определённая на множестве М=М1×М2 и принимающая значения из множества {1,0}.

В качестве примеров двухместных предикатов можно назвать предикаты: Q(x,у) – «х = у» предикат равенства, определённый на множестве R2=R×R; F(x,у) – «х || у» прямая х параллельна прямой у, опредёленный на множестве прямых, лежащих на данной плоскости.

Аналогично определяется n - местный предикат.

Говорят, что предикат Р(х) является следствием предиката Q(х) , если; и предикаты Р(х) и Q (х) равносильны 

Раздел 5 Графы

Теория графов - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Обычно её относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов-граф и его обобщения. Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и другие). Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ” Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может“. Кенигсбергские мосты схематически можно изобразить так:

 Правило Эйлера:

1. В графе, не имеющем вершин нечетных степеней, существует обход всех рёбер (причем каждое ребро проходится в точности один раз) с началом в любой вершине графа.
2. В графе, имеющем две и только две вершины с нечетными степенями, существует обход с началом в одной вершине с нечетной степенью и концом в другой.
3. В графе, имеющим более двух вершин с нечетной степенью, такого обхода не существует.

Существует еще один вид задач, связанных с путешествиями вдоль графов. Речь идёт о задачах, в которых требуется отыскать путь, проходящий через все вершины, причем не более одного раза через каждую. Цикл, проходящий через каждую вершину один и только один раз, носит название гамильтоновой линии (в честь Уильяма Роуэна Гамильтона, знаменитого ирландского математика прошлого века, который первым начал изучать такие линии). К сожалению, пока еще не найден общий критерий, с помощью которого можно было бы решить, является ли данный граф гамильтоновым, и если да, то найти на нём все гамильтоновы линии.

Сформулированная в середине 19 в. проблема четырех красок также выглядит как развлекательная задача, однако попытки ее решения привели к появлению некоторых исследований графов, имеющих теоретическое и прикладное значение. Проблема четырех красок формулируется так:”Можно ли область любой плоской карты раскрасить четырьмя цветами так, чтобы любые две соседние области были раскрашены в различные цвета?”. Гипотеза о том, что ответ утвердительный, была сформулирована в середине 19в. В 1890 году было доказано более слабое утверждение, а именно, что любая плоская карта раскрашивается в пять цветов. Сопоставляя любой плоской карте двойственный ей плоский граф, получают эквивалентную формулировку задачи в терминах графов: Верно ли, что хроматическое число любого плоского графа меньше либо равно четырёх?

  Многочисленные попытки решения задачи оказали влияние на развитие ряда направлений теории графов. В 1976 году анонсировано положительное решение задачи с использованием ЭВМ. Другая старая топологическая задача, которая особенно долго не поддавалась решению и будоражила умы любителей головоломок, известна как “задача об электро-, газо- и водоснабжении”. В 1917 году Генри Э.Дьюдени дал ей такую формулировку. В каждый из трёх домов, изображенных на рисунке, необходимо провести газ, свет и воду.6 Свет вода газ Можно ли так проложить коммуникации, чтобы они, нигде не пересекаясь друг с другом, соединяли каждый дом с источниками электричества, газа и воды? Иначе говоря, можно построить плоский граф с вершинами в шести указанных точках? Оказывается, такой граф построить нельзя. Об этом говорится в одной очень важной теореме – так называемой теореме Куратовского. Теорема утверждает, что каждый граф, не являющийся плоским, содержит в качестве подграфа один из двух простейших пространственных графов: В середине 19 в. появились работы, в которых при решении практических задач были получены результаты, относящиеся к теории графов. Так, например, Г. Кирхгоф при составлении полной системы уравнений для токов и напряжений в электрической схеме предложил по существу представлять такую схему графом и находить в этом графе остовные деревья, с помощью которых выделяются линейно независимые системы контуров. А. Кэли, исходя из задач подсчета числа изомеров предельных углеводородов, пришел к задачам перечисления и описания деревьев, обладающих заданными свойствами, и решил некоторые из них.

В 20 в. задачи, связанные с графами, начали возникать не только в физике, химии, электротехнике биологии, экономике, социологии и т.д., но и внутри математики, в таких разделах, как топология, алгебра, теория вероятностей, теория чисел. В начале 20 в. графы стали использоваться для представления некоторых математических объектов и формальной постановки различных дискретных задач; при этом наряду с термином «граф» употреблялись и другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт. После выхода в свет в 1936 году монографии Д. Кёнига термин «граф» стал более употребительным, чем другие. В этой работе были систематизированы известные к тому времени факты. В 1936 году вышла небольшая брошюра Ойстена Оре, содержащая блестящее элементарное введение в теорию графов. В 1962 году в Англии была издана книга французского математика Клода Бержа “Теория графов и её приложение”. Обе книги, безусловно, представляют интерес для любителей занимательной математики. Сотни известных головоломок, на первый взгляд не имеющих ничего общего друг с другом, легко решаются с помощью теории графов.7 В 20-30-х годах 20 в. появились первые результаты, относящиеся к изучению свойств связности, планарности, симметрии графов, которые привели к формированию ряда новых направлений в теории графов. Значительно расширились исследования по теории графов в конце 40-х - начале 50-х годов, прежде всего в силу развития кибернетики и вычислительной техники. Благодаря развитию вычислительной техники, изучению сложных кибернетических систем, интерес к теории графов возрос, а проблематика теории графов существенным образом обогатилась. Кроме того, использование ЭВМ позволило решать возникающие на практике конкретные задачи, связанные с большим объемом вычислений, прежде не поддававшиеся решению.

Для ряда экстремальных задач теории графов были разработаны методы их решения, например, один из таких методов позволяет решать задачи о построении макси- мального потока через сеть. Для отдельных классов графов (деревья, плоские графы и т. д.), которые изучались и ранее, было показано, что решения некоторых задач для графов из этих классов находятся проще, чем для произвольных графов (нахождение условий существования графов с заданными свойствами, установление изоморфизма графов и др.). Характеризуя проблематику теории графов, можно отметить, что некоторые направления носят более комбинаторный характер, другие - более геометрический. К первым относятся, например, задачи о подсчете и перечислении графов с фиксированными свойствами, задачи о построении графов с заданными свойствами. Геометрический (топологический) характер носят многие циклы задач теории графов, например, графов обходы, графов укладки. Существуют направления, связанные с различными классификациями графов, например, по свойствам их разложения.

Маршруты, цепи, циклы.

 Пусть G – неориентированный граф. Маршрутом в G называется такая конечная или бесконечная последовательность ребер (...е0, е1, ..., еп...), когда каждые два соседние ребра еi-1 и еi имеют общую инцидентную вершину. Одно и то же ребро может встречаться в маршруте несколько раз. В дальнейшем будут рассматриваться в основном конечные маршруты, т. е. конечные последовательности ребер (е1, е2, ..., еп). В таких маршрутах имеется первое ребро е1 и последнее ребро еп. Вершина vо, инцидентная ребру е1 и не инцидентная e2, называется началом маршрута. Аналогично определяется конец маршрута.

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

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

Матрицей смежности орграфа D называется квадратная матрица A(D)=[aij] порядка n, у которой

Матрицей инцидентности орграфа D называется (nxm) –матрица B(D)=[bij], у которой

Матрицей смежности графа G называется квадратная матрица A(G)=[aij] порядка n, у которой

Матрицей инцидентности графа G называется (nxm) –матрица B(G)=[bij], у которой

Основные свойства матриц смежности:

1. Матрица смежностей вершин неориентированного графа A (G) является квадратной и симметричной относительно главной диагонали.
2. Элементами матрицы A (G) являются целые положительные числа и число ноль.
3. Сумма элементов матрицы A (G) по i-й строке (или по i-му столбцу) равна степени соответствующей вершины δ ( xi ).

Из определения следует, что сумма элементов i-й строки матрицы A (G)орграфа равнаполустепени исхода δ+ ( xi ), а по i-му столбцу – полустепени захода δ¯ ( xi ).

Свойства матрицы инцидентности неориентированного графа:

1. Сумма элементов матрицы на i-й строке равна δ ( xi ).
2. Сумма элементов матрицы по i-му столбцу равна 2.

Матрица инцидентности орграфа G обладает следующими свойствами:

1. Сумма строк матрицы B(G) является нулевой строкой.
2. Любая строка матрицы B(G) является линейной комбинацией остальных строк.
3. Ранг матрицы B(G) равен p-1.

4. Задания для контрольных работ.

Задания 1-10 теория множеств

1)Дано множество V={1,2,…,12}, и два его подмножества А={1,3,6,9},B={2,3,9,10}

Найти: A∪B,A∩B,,  ,A\B,B\A,A B,BA,A2

2) Дано множество V={1,2,3,…,9} и два подмножества данного множества: A={1,3,4,7,9}, B={5,6,7,9}.

Найти:  A∪B,A∩B,,  ,A\B,B\A,A B,BA,A2

3) Дано множество V={1,2,3,…,14} и два подмножества данного множества: A={1,3,7,10}, B={4,6,7,8,9}.

Найти:  A∪B,A∩B,,  ,A\B,B\A,A B,BA,A2

4) Дано множество V={1,2,3,…,12} и два подмножества данного множества: A={1,2,5,8,10}, B={3,4,6,7,9}.

5) Дано множество V={1,2,3,…,13} и два подмножества данного множества: A={1,3,5,8,11}, B={2,3,8,10}.

Найти:  A∪B,A∩B,,  ,A\B,B\A,A B,BA,A2

6) Дано множество V={1,2,3,…,11} и два подмножества данного множества: A={1,3,5,6,7}, B={2,3,4,8,9}.

Найти:  A∪B,A∩B,,  ,A\B,B\A,A B,BA,A2

7) Дано множество V={1,2,3,…,10} и два подмножества данного множества: A={2,5,6,10}, B={1,2,3,4,9,10}.

Найти:  A∪B,A∩B,,  ,A\B,B\A,A B,BA,A2

8) Дано множество V={1,2,3,…,8} и два подмножества данного множества: A={1,4,5,6,8}, B={3,4,7,8,9}.

Найти:  A∪B,A∩B,,  ,A\B,B\A,A B,BA,A2

9) Дано множество V={1,2,3,…,15} и два подмножества данного множества: A={2,5,6,11,14}, B={1,2,3,5,9,10,12}.

Найти:  A∪B,A∩B,,  ,A\B,B\A,A B,BA,A2

10) Дано множество V={1,2,3,…,16} и два подмножества данного множества: A={1,2,4,6,11,14,16}, B={2,3,5,8,9,12,16}.

Найти:  A∪B,A∩B,,  ,A\B,B\A,A B,BA,A2

Задания 11-20 математическая логика

11) С помощью таблицы истинности проверить справедливость следующего тождества:

12) С помощью таблицы истинности проверить справедливость следующего тождества:

13) С помощью таблицы истинности проверить справедливость следующего тождества:

14) С помощью таблицы истинности проверить справедливость следующего тождества:

15)  С помощью таблицы истинности проверить справедливость следующего тождества:

16) С помощью таблицы истинности проверить справедливость следующего тождества:

17) С помощью таблицы истинности проверить справедливость следующего тождества:

18) С помощью таблицы истинности проверить справедливость следующего тождества:

19) С помощью таблицы истинности проверить справедливость следующего тождества:

20) С помощью таблицы истинности проверить справедливость следующего тождества:

Задания 21-30 алгебра вычетов

21) а) Записать 6 сравнений по mod 32; б)Описать классы вычетов по mod 15; к какому классу вычетов относятся числа 27, 38, -15 ?

22) а) Записать 6 сравнений по mod 33; б) Описать классы вычетов по mod 13; к какому классу вычетов относятся числа 70, -8, 12 ?

23) а) Записать 6 сравнений по mod 35; б) Описать классы вычетов по mod 16; к какому классу вычетов относятся числа 25, 36, -14 ?

24) а) Записать 6 сравнений по mod 34; б) Описать классы вычетов по mod 14; к какому классу вычетов относятся числа 80, 22, -12?

25) а)Записать 6 сравнений по mod 36; б) Описать классы вычетов по mod 17; к какому классу вычетов относятся числа 24, 33, -12 ?

26) а) Записать 6 сравнений по mod 31; б)Описать классы вычетов по mod 18; к какому классу вычетов относятся числа 29, 33, -12 ?

27) а) Записать 6 сравнений по mod 37; б) Описать классы вычетов по mod 19; к какому классу вычетов относятся числа 21, 39, -13?

28) а) Записать 6 сравнений по mod 38; б)Описать классы вычетов по mod 12; к какому классу вычетов относятся числа 28, 36, -14 ?

29) а) Записать 6 сравнений по mod 39; б)Описать классы вычетов по mod 11; к какому классу вычетов относятся числа 27, 35, -15 ?

30) а) Записать 6 сравнений по mod 40; б)Описать классы вычетов по mod 10; к какому классу вычетов относятся числа 26, 34, -16 ?

Задания 31-40 теория графов

31) Дан граф:

V5

e5

e6

e7

а) Перечислить все пары смежных вершин, смежных ребер, инцидентные ребра и вершины.

б) Указать одну простую цепь; одну цепь.

в) Указать один простой цикл; один цикл.

г) Указать два маршрута.

32)Дан граф:

e6

e7

а) Перечислить все пары смежных вершин, смежных ребер, инцидентные ребра и вершины.

б) Указать одну простую цепь; одну цепь.

в) Указать один простой цикл; один цикл.

г) Указать два маршрута.

33) Данграф:

а) Перечислить все пары смежных вершин, смежных ребер, инцидентные ребра и вершины.

б) Указать одну простую цепь; одну цепь.

в) Указать один простой цикл; один цикл.

г) Указать два маршрута.

34) Дан граф:

e2

e3

e7

e8

а) Перечислить все пары смежных вершин, смежных ребер, инцидентные ребра и вершины.

б) Указать одну простую цепь; одну цепь.

в) Указать один простой цикл; один цикл.

г) Указать два маршрута.

35) Дан граф:

а) Перечислить все пары смежных вершин, смежных ребер, инцидентные ребра и вершины.

б) Указать одну простую цепь; одну цепь.

в) Указать один простой цикл; один цикл.

г) Указать два маршрута.

36) Дан граф:

а) Перечислить все пары смежных вершин, смежных ребер, инцидентные ребра и вершины.

б) Указать одну простую цепь; одну цепь.

в) Указать один простой цикл; один цикл.

г) Указать два маршрута.

37) Дан граф:

V6

e7

e8

e9

e10

а) Перечислить все пары смежных вершин, смежных ребер, инцидентные ребра и вершины.

б) Указать одну простую цепь; одну цепь.

в) Указать один простой цикл; один цикл.

г) Указать два маршрута.

38)  Дан граф:

а) Перечислить все пары смежных вершин, смежных ребер, инцидентные ребра и вершины.

б) Указать одну простую цепь; одну цепь.

в) Указать один простой цикл; один цикл.

г) Указать два маршрута.

39) Дан граф:

V5

e5

e8

e7

а) Перечислить все пары смежных вершин, смежных ребер, инцидентные ребра и вершины.

б) Указать одну простую цепь; одну цепь.

в) Указать один простой цикл; один цикл.

г) Указать два маршрута.

40) Дан граф:

e6

e7

а) Перечислить все пары смежных вершин, смежных ребер, инцидентные ребра и вершины.

б) Указать одну простую цепь; одну цепь.

в) Указать один простой цикл; один цикл.

г) Указать два маршрута.

Задания 41-50 матрица смежности, матрица инциденций.

Составьте матрицу смежности, матрицу инциденций для графов из заданий 31-40 соответственно.

Задания 51-60 математическая индукция

51) Докажите, что при всех натуральных n       n3+11n кратно 6

52) Докажите, что при всех натуральных n       7n+3n-1 кратно 9

53) Докажите, что при всех натуральных n       5n-3n+2n кратно 4

54) Докажите, что при всех натуральных n       62n+19n-2n+1 кратно17

55) Докажите, что при всех натуральных n       5*23n-2+33n-1 кратно 19

56) Докажите, что при всех натуральных n   33n+2+7n делится на 10

57) Докажите, что при любом натуральном n  число 32n+1+2n+2 делится на 7.
58) Докажите, что при любом натуральном n  число 7n+1+82n-1 делится на 19.

59) Доказать, что при любом натуральном n  число  делится на 3n+1
60) Доказать, что при любом натуральном n  число   22n-1-9n2+21n-14 кратно 27

            4  Перечень практических и самостоятельных работ.

            4.1 Тематика самостоятельной работы (108 часов):

Таблица 3 - Тематика самостоятельной работы

4.2 Тематика практических работ (12 часов)

Таблица 4 Тематика практических работ

5 Вопросы к зачету. Содержание тестовых заданий, перечни вопросов.

1 вариант

1. Как называется операция над множествами, характеризующаяся логически словами: Элемент (Х С А)V(XCB) x принадлежит множеству А или множеству В

А) Пересечение Б) Объединение В) Разность Г) Дополнение

2. Как называется операция над множествами, характеризующаяся с помощью диаграммы Эйлера:

А) Пересечение

Б) Объединение

В) Разность

Г) Дополнение

3. Свойство бинарного отношения, когда любой элемент множества находится в этом отношении сам с собой:

А) Транзитивность Б) Симметричность В) Связанность

 Г) Рефлексивность

4. Каким будет отношение R, заданное на множестве А, если оно рефлексивно, транзитивно, симметрично:

А) Порядок Б) Строгий порядок В) Эквивалентность Г) Нестрогий порядок

5. Высказывание, которое принимает значение истины тогда и только тогда, когда А и В истинны:

А) Конъюнкция Б) Дизъюнкция В) Импликация Г) Эквивалентность

6. Закон коммутативности в логике Буля:

А) AV1=А Б) (AVB) Λ A=A B) AV B = BVA Г) АV A=A

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

А) T1 Б) Т0 В) S Г) М

8. Функциональное высказывание, где область значений функции логическая, а область аргументов предметная:

А) Множество Б) Логическое высказывание В) Булевы функции

Г) Предикат

9. По какому модулю сравнимы числа 7 и 3?

А) По mod 7 Б) По mod 3 В) По mod 2 Г) По mod 5

10.  К какому классу вычетов по mod 5 принадлежат числа 17, -13?

          _      _      _      _

     А) 2 Б) 3 В) 1 Г) 4

11. Раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.

А) Логика высказываний; Б) Алгебра вычетов; В) Теория множеств;

 Г) Комбинаторика.  

12. Сколько элементов  n должно содержать множество, чтобы число всех перестановок не превышало 30?

А) n<=5 Б) n<=3 В) n<= 6 Г) n<=4

13. С помощью какой формулы можно подсчитать число размещений из n элементов по m?

А) A   = n! Б) A   = n!/(n-m)! В) A  = n!/m!(n-m)! Г) A  = m!/(n-m)!

14. Какое из равенств верное?

А) С  = A  / P  Б) С  = AP  В) C  = P  / A  Г) С  = P  / P

15.  Какая из клауз верная:

А) xP(x) =>xP(x) Б) xP(x) =>xP(x) В) xP(x) =>xP(x)

Г) xP(x) =>xP(x)

16. Совокупность двух множеств V вершин и Е ребер V – непустое множество, а Е – множество неупорядоченных пар различных элементов V называется:

А) Граф Б) Смежность В) Инцидентность Г) Изоморфизм

17. Сколько в данном графе вершин, смежных с вершиной V1:

        V1        V2        А) 1 Б) 3 В) 4 Г) 2

        V4        V3

18. Сколько в данном графе ребер, инцидентных вершине V3:

А) 1 Б) 2 В) 3 Г) 4

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

      А) Матрицей Б) Матрицей инциденций В) Матрицей смежности Г) Матиндукцией.

     20.  Граф, состоящий из одной вершины, называется

         А) Орграфом Б) Тривиальным В) Деревом Г) Подграфом

      21. В матрице смежности для графа, если вершины смежны, то это обозначается:

А) + Б) 1 В) 0 Г) –1

22. В матрице инцидентности для орграфа, если вершина инцидентна ребру и является его началом, это обозначается:

А) + Б) 1 В) 0 Г) –1

      23. В дереве нет:

          А) циклов Б) вершин В) ребер Г) простых цепей

24. Ориентированное дерево это:

А) Подграф Б) Дополнение к графу В) Орграф, обладающий определенными свойствами Г) Объединение графов

     25. В цепи может повторяться:

          А) Ребро Б) Вершина В) Путь Г) Граф

2 вариант.

1.Как называется операция над множествами, характеризующаяся логически словами: Элемент (Х С А)(XCB) x принадлежит множеству А и множеству В

А) Объединение Б) Пересечение В) Разность Г) Дополнение

2. Как называется операция над множествами, характеризующаяся с помощью диаграммы Эйлера:

А) Объединение

Б) Пересечение

В) Разность

Г) Дополнение

3. Свойство бинарного отношения, такое, что если элемент множества

а  находится в этом отношении с элементом в, а элемент в находится в этом отношении с элементом с, то элемент а находится в этом отношении с элементом с:

А) Рефлексивность Б) Симметричность В) Связанность

Г) Транзитивность

4. Каким будет отношение R, заданное на множестве А, если оно  транзитивно, антисимметрично:

 А) Эквивалентность Б) Строгий порядок В) Порядок Г) Нестрогий порядок

5. Высказывание, которое принимает ложное значение  тогда и только тогда, когда А и В ложны:

А) Дизъюнкция Б) Конъюнкция В) Импликация Г) Эквивалентность

6. Закон поглощения в логике Буля:

А) AV1=1  Б) AV B = BVA B) (AVB) Λ A=A Г) АV A=A

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

А) T0 Б) Т1 В) S Г) М

8. Высказывание, где область значений функции  и область аргументов логическая:

А) Множество Б) Предикат В) Булевы функции

Г) Логическое высказывание

9. По какому модулю сравнимы числа 7 и 2 ?

А) По mod 7 Б) По mod 3 В) По mod 5 Г) По mod 2

10. К какому классу вычетов по mod 6 принадлежат числа 19, -11?

      _      _      _      _

А) 1  Б) 3 В) 2 Г) 4

11. Сколько элементов  n должно содержать множество, чтобы число всех перестановок не превышало 40?

А) n<=5 Б) n<=3 В) n<= 6 Г) n<=4

12. С помощью какой формулы можно подсчитать число сочетаний из n элементов по m?

А) C  = n! Б) С   = n!/ m!(n-m)! В) C  = n!/(n-m)! Г) C  = m!/(n-m)!

13. Какое из равенств верное?

А) P  = n!   Б) P  = n!/ m!(n-m)!  В) P  = n!/ (n-m)!   Г) P  = (n-m)!  

14.  Какая из клауз подтверждается примером: « Если все люди смертны, то человек  Сократ тоже смертен:

А) xP(x) =>xP(x) Б) xP(x) =>xP(x) В) xP(x) =>xP(x)

Г) xP(x) =>xP(x)

15. Любое … является предикатом:

А) выражение Б) предложение В) Сочетание Г) неравенство

16. Два ребра, инцидентные одной вершине, называются:

А) Графическими Б) Смежными В) Связанными Г) Изоморфными

17. Сколько в данном графе вершин, смежных с вершиной V2:

             V1        V2         А) 1 Б) 2 В) 4 Г) 3

            V4          V3

18. Сколько в данном графе ребер, инцидентных вершине V1:

А) 1 Б) 2 В) 3 Г) 4

19. Чередующаяся последовательность вершин и ребер, в которой любые два соседних элемента инцидентны:

А) Маршрут Б) Цепь В) Цикл Г) Простой цикл

20. Представление графа с помощью матрицы, отражающей инцидентность вершин и ребер, называется:

А) Матрицей Б) Матрицей инциденций В) Матрицей смежности Г) Матиндукцией.

21. В матрице смежности для графа, если вершины  не смежны, то это обозначается:

А) + Б) 0 В) 1 Г) –1

22. В матрице инцидентности для орграфа, если вершина инцидентна ребру и является его концом, это обозначается:

А) + Б) –1  В) 0 Г) 1

23. Если относительный порядок конечных множеств узлов фиксирован, то ордерево называется:

А) Свободным Б) Бинарным В) Эквивалентным Г) Упорядоченным

24. Связный ациклический граф является:

А) Ордеревом Б) Упорядоченным ордеревом

В) Свободным деревом Г) Бинарным

25. Ориентированное дерево является:

        А) Тривиальным графом  Б) Матрицей  В) Упорядоченным деревом Г) Графом с циклами.

Критерии оценки выполнения задания:

- "Отлично" - если студент  глубоко и прочно усвоил весь программный материал в рамках указанных общих и профессиональных компетенций, знаний и умений. Исчерпывающе, последовательно, грамотно и логически стройно его излагает, тесно увязывает с условиями современного производства, не затрудняется с ответом при видоизменении задания, свободно справляется с задачами и практическими заданиями, правильно обосновывает принятые решения, умеет самостоятельно обобщать и излагать материал, не допуская ошибок. 24-25 правильных ответов из 25 (96-100%)

- "Хорошо" - если твердо студент знает программный материал, грамотно и по существу излагает его, не допускает существенных неточностей в ответе на вопрос, может правильно применять теоретические положения и владеет необходимыми умениями и навыками при выполнении практических заданий. 19-23 правильных ответов из 25 (76-95%)

- "Удовлетворительно" - если студент усвоил только основной материал, но не знает отдельных деталей, допускает неточности, недостаточно правильные формулировки, нарушает последовательность в изложении программного материала и испытывает затруднения в выполнении практических заданий. 13-18 правильных ответов из 25 (52-75%)

-  "Неудовлетворительно" - если студент   не знает значительной части программного материала, допускает существенные ошибки, с большими затруднениями выполняет практические задания, задачи.

Меньше 13 правильных ответов из 25 (меньше 52%)

6 Примеры решения заданий

Задания 1-10 теория множеств

Дано множество V={1,2,…,12}, и два его подмножества А={1,4,6,8,9},B={2,3,9,10}

Найти: A∪B,A∩B,,  ,A\B,B\A,A B,BA,A2

A∪B={1,2,3,4,6,8,9,10},

 A∩B={9},

={2,3,5,7,10,11,12},

 ={1,4,5,6,7,8,11,12},

A \B={1,4,6,8},

B \A={2,3,10}, AB={(1,2),(1,3),(1,9),(1,10),(4,1),(4,3),(4,9),(4,10),(6,2),(6,3),(6,9),(6,10), (8,2),(8,3),(8,9), (8,10) (9,2),(9,3),(9,9), (9,10)},

BA={(2,1),(2,4),(2,6),(2,8),(3,1),(3,4),(9,1),(9,4),(9,6),(9,8),(9,9),(10,1),(10,4),(10,6), (10,8),(10,9)}

A2={(1,1),(1,4),(1,6),(1,8),(1,9),(4,1),(4,4),(4,6),(4,8),(4,9),(6,1),(6,4),(6,6),(6,8),(6,9), (8,1),(8,4),(8,6),(8,8),(8,9),(9,1).(9,4).(9,6),(9,8),(9,9)

Задания 11-20 математическая логика

   С помощью таблицы истинности доказать равносильность следующего тождества:        

Задания 21-30 алгебра вычетов

21) а) Записать 6 сравнений по mod 21; б) Описать классы вычетов по mod 6; к какому классу вычетов относятся числа 21, 8, -15 ?

а)

Разность этих чисел делится нацело на 21, поэтому они сравнимы по mod21

б) 

 ;

Задания 31-40 теория графов

а) Перечислить все пары смежных вершин, смежных ребер, инцидентные ребра и вершины.

Смежные вершины: (V1, V2); (V1, V3); (V1, V4); (V2, V3); (V3, V4)

Смежные ребра: (E1, E2); (E1, E5); (E1, E4); (E2, E3); (E2, E5); (E3, E4); (E4,E5);

Инцидентные ребра и вершины: V1: E1, E5, E4;

V2: E1, E2

V3: E2, E3, E5

V4: E3, E4

б) Указать одну простую цепь; одну цепь.

Простая цепь: V1, V2, V3, V4

Цепь: V1, V2, V3,V1, V4

в) Указать один простой цикл; один цикл.

Простой цикл: V1, V2, V3, V1

Цикл: В этом графе невозможно указать цикл. (Цикл – это замкнутая последовательность вершин и ребер, с повторяющимися вершинами, но ребра все по одному разу)

г) Указать два маршрута.

Маршруты: (1) V1, V2, V3, V2

(2) V1, V3, V1, V4

Задания 41-50 матрица смежности, матрица инциденций.

Составьте матрицу смежности, матрицу инциденций для графов из заданий 31-40 соответственно.

граф G                              

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

M(G[I,j])    0  1  1  1        

                 1  0  1  0                          

                 1  1  0  1                            

                 1  0  1  0                          

Матрица инциденций:

H(G[I,j])    1  0  0  1  1                    

                   1  1  0  0  0                                        

                   0  1  1  0  1                                      

                   0  0  1  1  0                                      

Задания 51-60 математическая индукция

Доказать , что при любом натуральном n число 32n+1+2n+2 делится на 7.
Доказательство:
Обозначим an=32n+1+2n+2.
1) Начало индукции. Если n=1 , то a1=35 делится на 7. (впрочем, здесь начать можно и с n=0)
2) Индуктивный переход. Пусть ak делится на 7. ( предположение индукции)
Докажем справедливость утверждения для n=k+1 ak+1=32(k+1)+1+2(k+1)+2=32k+1 9+ 2k+2 2= (32k+1+2k+2)9-7 *2k+2=9ak-7*2k+2
Последнее число делится на 7, т.к. представляет собой разность двух целых чисел, делящихся на 7.

7 Перечень рекомендуемой учебной литературы, методических пособий и Интернет-ресурсов

Основные источники:

1. Лупанов О. Б. Курс лекций по дискретной математике. - М., 2013.
2. Новиков Ф.А. Дискретная математика для программистов - 2014 г.
3. Яблонский С.В. Введение в дискретную математику — М. Наука, 2014.

Дополнительные источники:

1. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. — М.: Наука, 2014.
2. Гончарова Г.А., Мочалин А.А. Элементы дискретной математики: учеб. пособ.- М.: Форум: ИНФРА-М, 2014.
3. Горбатов В.А., Горбатов А.В., Горбатова М.В. Дискретная математика -М., 2013 г.
4. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. Расширенный курс. - М: Известия, 2013.
5. Кольман Э. Зих О. Занимательная логика. — М.: Наука, 2014.
6. Мендельсон Э. Введение в математическую логику. — М.: Наука, 2013.
7. Нефедов В.Н., Осипова В.А. Курс дискретной математики — М.: Издательство МАИ, 2013
8. Спирина М.С. Дискретная математика: учеб. – М.: Академия, 2014.
9. Харари Ф. Теория графов. –М., 2014 год.

Интернет-ресурсы:

1. http://otherreferats.allbest.ru/
2. http://st.educom.ru/eduoffices/gateways/get_file.
3. http://umu.kemsu.ru/Content/userfiles/files/Математический