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

Министерство транспорта Российской Федерации

Федеральное агентство железнодорожного транспорта

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

«Дальневосточный государственный университет путей сообщения»

Кафедра «Высшая математика»

В.С. Васильева, С.В. Коровина, Л.В. Марченко

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

Рекомендовано
Методическим советом ДВГУПС
в качестве учебного пособия

Хабаровск

Издательство ДВГУПС

УДК [510.2 + 510.6 + 519.1] (075.8)

ББК B 176я73

В 191

Рецензенты:

Кафедра математики ДВГГУ

(заведующий кафедрой кандидат педагогических наук,
доцент И.В. Карпова)

Кандидат физико-математических наук,

доцент кафедры «Высшая математика» ТОГУ
Н.В. Маркова

Васильева, В.С.

Учебное пособие соответствует ФГОС ВПО направлений подготовки 270800.62… Рассмотрены базовые разделы математики, необходимые для изучения дисциплин естественно-научного цикла. Помимо…

ББК B 176я73

ã ДВГУПС, 2013

ВВЕДЕНИЕ

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

А. Сухотин

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

Основной особенностью дискретной математики (ДМ) является отсутствие предельного перехода и непрерывности, характерных для классической (непрерывной) математики.

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

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

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

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

Раздел «Дискретная математика» позволяет освоить базовые математические понятия, способствующие успешному овладению последующими курсами естественных наук и получению специализированных компетенций: способности корреспондировать с профессиональной деятельностью базовые знания естественных наук; владения методами поиска необходимой информации, алгоритмами последовательного, доказательного мышления; приемами работы с источниками знания.

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

В первом разделе рассматриваются основные сведения теории множеств: понятие множества; операции над множествами и их свойства; определяется понятие бинарного отношения на множестве, исследуются различные виды отношений, в том числе и функция.

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

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

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

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

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

Для более глубокого изучения разделов дискретной математики можно обратиться к дополнительному теоретическому материалу [1–30] из библиографического списка, приведенного в конце учебного пособия.

1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

1.1. Основные понятия теории множеств.
Способы задания множеств

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

Под множеством следует понимать совокупность некоторых объектов, которые назовем элементами множества. В дальнейшем будем обозначать множества прописными (большими) латинскими буквами , , , а элементы множества – строчными (малыми) латинскими буквами , , .

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

Запись означает, что элемент не принадлежит множеству .

Например, – множество студентов ДВГУПС; – множество улиц города Хабаровска; – множество страниц данного пособия; R – множество действительных чисел. Так, число 5 – действительное число, поэтому .

Определение 1. Множество, содержащее конечное число элементов, называется конечным, в противном случае – бесконечным.

Рассматриваемые в математике числовые множества имеют следующие обозначения:

– множество натуральных чисел;

– множество целых чисел;

–множество целых неотрицательных чисел;

–множество целых неположительных чисел;

– множество рациональных чисел;

– множество действительных чисел;

– множество неотрицательных действительных чисел;

– множество положительных действительных чисел;

– множество неположительных действительных чисел;

– множество отрицательных действительных чисел.

Все перечисленные множества являются бесконечными.

Чтобы задать (описать) множество, надо или перечислить его элементы, или указать некоторые характерные свойства элементов данного множества.

Способы задания множеств

1. Перечисление – задание списка элементов (возможно только для конечных множеств).

Например, – множество, содержащее элементов. – множество, содержащее три элемента.

2. Порождающая процедура описывает способ получения элементов множества на основе уже ранее описанных множеств.

3. Описание характеристических свойств – словесное, аналитическое или процедурное описание элементов множества:

– множество, состоящее из таких элементов , которые обладают свойством .

Например, – множество, состоящее из натуральных чисел, не больших 15;

– множество нечетных чисел;

Определение 2.Множество, не содержащее ни одного элемента, называется пустым множеством. Обозначение: .

Пустое множество встречается в реальных задачах и не является «изобретением» математиков. Так, например, может оказаться, что множество студентов, получивших две неудовлетворительные оценки, пусто (таких студентов просто нет).

Определение 3.Число элементов в конечном множестве называется его мощностью. Обозначение: , или .

Например,мощность множества равна трем ( ).

Замечание 1.Мощность нулевого множества равна нулю: .

Определение 4.Если , то множества называются равномощными.

Определение 5.Множество называется подмножеством (говорят включено в , или содержится в ), если все элементы множества принадлежат . Обозначение: .

Замечание 2. Пустое множество является подмножеством любого множества.

Определение 6.Множество называется собственным (строгим) подмножеством множества , если и , т. е. в есть элементы, не содержащиеся в . Обозначение: .

Например, – множество всех четырехугольников, – множество всех трапеций, – множество всех параллелограммов, тогда .

Если В – множество студентов Института транспортного строительства, – множество студентов 412-й группы ДВГУПС, тогда .

Для перечисленных ранее числовых множеств верно, что .

Определение 7.Множества и равны ( ), если и , другими словами, все их элементы совпадают.

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

Например, для множества совокупность всех его подмножеств (булеан) имеет следующий вид:

Определение 9. Если для множества указан порядок расположения элементов, то множество называется упорядоченным: поменяв местами хотя бы два элемента, мы получим, вообще говоря, другое множество.

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

Определение 10. Универсальным множеством называется такое множество, что все рассматриваемые множества являются его подмножествами. Обозначение: .

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

Пример 1.Найдите меру отрезка , лежащего на оси .

Решение

Мера отрезка – это его длина. Следовательно, .

Рис. 1

Пример 2.Найдите меру множества , изображенного на рис. 1.

Решение

Вопросы и задачи для самостоятельного решения 1. Какие из приведенных заданий множеств , , , являются… 2. Является ли множество, состоящее из числа 0, пустым множеством?

Решение

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

Решение

Вопросы и задачи для самостоятельного решения 1. Дайте определения объединения, пересечения, разности и дополнения… 2. Укажите порядок выполнения операций над множествами.

Решение

Построим дополнение множества до универсального множества (рис. 5, а). Множеству соответствует закрашенная область (рис. 5, б). Таким образом, видно, что на диаграммах Эйлера – Венна множества и изображаются одинаково, поэтому .

Рис. 5

Пример 2. Покажите, что .

Решение

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

Решение

= = /закон дистрибутивности/ = = = /закон коммутативности/ = = = /закон дистрибутивности/ =

Решение

Введем обозначения:

;

Тогда , , , .

Следовательно, – количество студентов, не посещающих дополнительных курсов.

Замечание 1.Теорему включений и исключений можно сформулировать для случая трех множеств:

Пример 3.На курсе обучаются 42 студента. Из них 16 занимаются в секции по легкой атлетике, 24 – в футбольной секции, 15 – в шахматной секции, 11 – и в секции по легкой атлетике, и в футбольной; 8 – и в легкоатлетической, и в шахматной; 12 – и в футбольной, и в шахматной; а 6 – во всех трех секциях. Остальные студенты увлекаются туризмом. Сколько студентов являются туристами?

Решение

; ; ;

Решение

;

Найдем мощность: .

Пример 2. Даны множества , , . Найдите число элементов декартова произведения множеств и укажите эти элементы.

Решение

Найдем пересечение множеств , содержащее общие элементы обоих множеств: . Так как множество содержит четыре элемента, а множество – два элемента, то количество соответствующих пар декартова произведения будет . Перечислим всевозможные пары: , , , , , , , .

Пример 3. Даны множества и . Найдите и изобразите на координатной плоскости .

Решение

Рис. 10 Понятие декартова произведения можно обобщить на случай множеств. Если – произвольные… Замечание. Если – конечные множества, то .

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

2.Бинарное отношение на множестве антирефлексивное, если для любых и , для которых выполнено , следует, что . 3. Бинарное отношение на множестве симметричное, если из выполнения … 4.Бинарное отношение на множестве антисимметричное, если из выполнения и следует, что .

Решение

Функция содержит корень четной степени, следовательно, она определена только в случае неотрицательного подкоренного выражения, т. е. , откуда ; .

Пример 2. Найдите прообраз множества при отображении .

Решение

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

Решение

Запишем логические функции (сложные высказывания) через введенные переменные: § если не будет ветра, то будет пасмурная погода без дождя: ; § если будет дождь, то будет пасмурно и без ветра: ;

Алгоритм построения нормальных форм

; ; .

Способы нахождения СДНФ

1-й способ – с помощью равносильных преобразований:

§ получаем одну из ДНФ;

§ если в полученной ДНФ входящая в нее элементарная конъюнкция не содержит переменную , то используем равносильность и получаем две элементарных конъюнкции;

§ если в ДНФ входят две элементарные конъюнкции, то лишнюю можно отбросить.

2-й способ – с помощью таблиц истинности:

§ выделяем строки, где формула принимает значение 1;

§ составляем дизъюнкцию конъюнкций при условии, что если переменная входит в конъюнкцию со значением 1, то записываем эту переменную, если со значением 0, то ее отрицание. Получаем СДНФ.

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

Способы нахождения СКНФ

1-й способ – с помощью равносильных преобразований:

§ получаем одну из КНФ;

§ если в полученной КНФ входящая в нее элементарная дизъюнкция не содержит переменную , то используем равносильность и получаем две элементарных дизъюнкции;

§ если в КНФ входят две элементарные дизъюнкции, то лишнюю можно отбросить.

2-й способ – с помощью таблиц истинности:

§ выделяем строки, где формула принимает значение 0;

§ составляем конъюнкцию дизъюнкций при условии, что если переменная входит в дизъюнкцию со значением 0, то записываем эту переменную, если со значением 1, то ее отрицание. Получаем СКНФ.

Пример 1. Постройте КНФ функции .

Решение

Исключим связку « » с помощью законов преобразования переменных:

= /законы де Моргана и двойного отрицания/ =

/дистрибутивные законы/ =

Пример 2. Приведите к ДНФ формулу .

Решение

Выразим логические операции и через , и :

= /отнесем отрицание к переменным и сократим двойные отрицания/ =

= /закон дистрибутивности/ .

Пример 3. Запишите формулу в ДНФ и СДНФ.

Решение

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

Решение

а) ; б) .

Замечание 2.Для неориентированного графа матрица смежности симметричная.

Пример 3. Нарисуйте граф c множеством вершин и множеством ребер . Найдите его матрицу смежности.

Решение

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

Решение

Подберем значение , исходя из равенств , , , , , . Следовательно, , откуда и . Вновь рассмотрим множество, состоящее из различных элементов , зафиксируем некоторое натуральное число и…

Решение

После сокращения получим , , , . Поскольку число натуральное, то смысл имеет только значение . 4.2. Сочетания и их свойства

Вариант 1

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.

3.На одной из кафедр университета работают человек, среди которых человек не знают ни одного иностранного языка. человек знают английский, – немецкий, – французский. знают английский и немецкий, – английский и французский, – немецкий и французский. знают все три языка. По заданным в таблице условиям восстановите недостающую информацию.


								?

4.Даны множества и . Найдите .

5.Для отношения найдите множество определения, множество значений и установите, какими свойствами оно обладает.

6.Отображение действует по правилу . Найдите образ .

7.Постройте таблицу истинности для булевой функции .

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

«Я сдам этот экзамен только в том случае, если буду регулярно выполнять домашние задания».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Для полярной экспедиции из 8 претендентов ( = 1, 2, 3, 4, 5, 6, 7, 8) надо отобрать 6 специалистов: биолога, гидролога, синоптика, радиста, механика и врача. Обязанности биолога могут выполнять и , гидролога – и , синоптика – и , радиста – и , механика – и , врача – и . Хотя некоторые претенденты владеют двумя специальностями, в экспедиции каждый сможет выполнять только одну обязанность.

Кого и кем следует взять в экспедицию, если не может ехать без , без и без , не может ехать одновременно с , не может ехать вместе с ?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин и ребер .

14.Даны графы и . Выпишите для каждого графа множества вершин и ребер. Определите степень каждой вершины. Найдите матрицы смежности и инцидентности. Укажите для графа какой-либо маршрут из вершины 1. Укажите для графа подграфы.

15.Автомобильные номера состоят из трех букв (используются только те буквы латинского алфавита, написание которых совпадает с буквами русского алфавита) и трех цифр (используются все 10 цифр). Сколько автомобилей можно занумеровать таким образом, чтобы никакие два автомобиля не имели одинакового номера?

Вариант 2

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


	?

4.Дано декартово произведение множеств

. Выпишите множества и .

6.Найдите прообраз множества при отображении .

7.Постройте таблицу истинности для булевой функции .

«Регулярное выполнение домашних заданий является необходимым условием для того, что я сдам этот экзамен».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Три одноклассника – Влад, Тимур и Юра – встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего – регби. Юра сказал, что на туризм ему не хватает времени, хотя его сестра – единственный врач в семье, заядлый турист. Врач сказал, что он разделяет увлечение коллеги. Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен.

Определите, кто, чем любит заниматься в свободное время и у кого какая профессия.

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин и ребер .

15.Сколькими способами можно составить расписание занятий на понедельник, если в этот день должно быть пять занятий: по алгебре, геометрии, истории, географии, литературе, причем алгебра и геометрия не должны следовать непосредственно друг за другом?

Вариант 3

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


			?

4.Даны множества и . Найдите .

6.Отображение действует по правилу . Найдите образ .

7.Постройте таблицу истинности для булевой функции .

«Сдача этого экзамена является достаточным условием того, что я регулярно выполнял домашние задания».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Известно следующее: если Петя не видел Колю на улице, то Коля либо ходил в кино, либо Петя сказал правду; если Коля не ходил в кино, то Петя не видел Колю на улице, и Коля сказал правду. Если Коля сказал правду, то либо он ходил в кино, либо Петя солгал.

Выясните, ходил ли Коля в кино.

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин и ребер .

15.На книжной полке требуется расположить 10 различных книг по математике, 12 различных книг по физике и 15 различных книг по информатике. Сколькими способами это можно сделать, если:

1) не существует никаких ограничений;

2) все книги по одному и тому же предмету должны стоять рядом?

Вариант 4

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


							?

4.Даны множества и . Найдите .

6.Найдите прообраз множества при отображении .

7.Постройте таблицу истинности для булевой функции .

«Я сдам этот экзамен в том и только в том случае, если я буду регулярно выполнять домашние задания».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.В поездке пятеро друзей – Антон, Борис, Вадим, Дима и Гриша – знакомились с попутчицей. Они предложили ей отгадать их фамилии, причём каждый из них высказал одно истинное и одно ложное утверждение: Дима сказал: «Моя фамилия – Мишин, а фамилия Бориса – Хохлов». Антон сказал: «Мишин – это моя фамилия, а фамилия Вадима – Белкин». Борис сказал: «Фамилия Вадима – Тихонов, а моя фамилия – Мишин». Вадим сказал: «Моя фамилия – Белкин, а фамилия Гриши – Чехов». Гриша сказал: «Да, моя фамилия Чехов, а фамилия Антона – Тихонов».

Какую фамилию носит каждый из друзей?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин и ребер .

15.Энциклопедия состоит из 8 томов с 1-го по 8-й. Сколькими способами ее можно поставить на полке в беспорядке (чтобы тома не следовали друг за другом)?

Вариант 5

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


?

4.Дано декартово произведение множеств А×D = {(0,1), (0,2), (0,3), (1,1), (1,2), (1,3)}. Выпишите множества и .

6.Отображение действует по правилу . Найдите образ .

7.Постройте таблицу истинности для булевой функции .

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

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу .

11.Три девочки – Роза, Маргарита и Анюта – представили на конкурс цветоводов корзины выращенных ими роз, маргариток и анютиных глазок. Девочка, вырастившая маргаритки, обратила внимание Розы на то, что ни у одной из девочек имя не совпадает с названием любимых цветов.

Какие цветы вырастила каждая из девочек?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин и ребер .

15.Из пункта в пункт можно доехать либо автобусом (4 рейса), либо самолетом (2 рейса). Сколько всего способов добраться до пункта ?

Вариант 6

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.

3.На одной из кафедр университета работают человек, среди которых
человек не знают ни одного иностранного языка. человек знают английский, – немецкий, – французский. знают английский и немецкий, – английский и французский, – немецкий и французский. знают все три языка. По заданным в таблице условиям восстановите недостающую информацию.


					?

4.Даны множества и . Найдите .

6.Найдите прообраз множества при отображении .

7.Постройте таблицу истинности для булевой функции .

«Если Ира поедет в Москву, то будет покупать билеты предварительно».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу .

11.Пятеро одноклассников – Ира, Тимофей, Катя, Эльдар и Захар – стали победителями олимпиад школьников по физике, математике, информатике, литературе и географии. Известно, что:

§ победитель олимпиады по информатике учит Иру и Тимофея работе на компьютере;

§ Катя и Эльдар тоже заинтересовались информатикой;

§ Тимофей всегда побаивался физики;

§ Катя, Тимофей и победитель олимпиады по литературе занимаются плаванием;

§ Тимофей и Катя поздравили победителя олимпиады по математике;

§ Ира сожалеет о том, что у нее остается мало времени на литературу.

Победителем какой олимпиады стал каждый из этих ребят?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

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

Вариант 7

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


		?

4.Дано декартово произведение множеств

. Выпишите множества и .

6.Отображение действует по правилу . Найдите образ .

7.Постройте таблицу истинности для булевой функции .

«Неверно, что ветер дует тогда и только тогда, когда идет дождь».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

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

Назовите фамилии слесаря, токаря и плотника.

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин и ребер .

15.Хор состоит из 10 участников. Сколькими способами можно в течение трех дней выбрать по 6 участников, так, чтобы каждый день были различные составы хора?

Вариант 8

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера –Венна.


				?

4.Дано декартово произведение множеств

. Выпишите множества и .

6.Найдите прообраз множества при отображении .

7.Постройте таблицу истинности для булевой функции

«Будет ли Петров поступать в институт или нет, зависит от того, закончит ли он школу».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Когда сломался компьютер, его хозяин сказал «Память не могла выйти из строя». Его сын предположил, что сгорел процессор, а винчестер исправен. Пришедший специалист по обслуживанию сказал, что, скорее всего, с процессором все в порядке, а память неисправна. В результате оказалось, что двое из них сказали все верно, а третий – все неверно. Что же сломалось?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин и ребер .

15.Сколькими способами можно группу из 20 человек разбить на две подгруппы по 10 человек?

Вариант 9

1.Для заданных множеств , , , найдите мощность следующих множеств:,,,.

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


								?

4.Даны множества и . Найдите .

6.Отображение действует по правилу . Найдите образ .

7.Постройте таблицу истинности для булевой функции .

«Аня любит мандарины и неверно, что она любит яблоки и груши».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Ира любит мороженое с фруктами. В кафе был выбор из таких вариантов:

§ пломбир с орехами;

§ пломбир с бананами;

§ пломбир с черникой;

§ шоколадное с черникой;

§ шоколадное с клубникой.

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

Какое же мороженое и с какими фруктами любит Ира?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин и ребер .

15.Сколько четырехбуквенных слов можно образовать из букв слова интеграл?

Вариант 10

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера –Венна.


	?

4.Дано декартово произведение множеств

. Выпишите множества А и D.

6.Найдите прообраз множества при отображении .

7.Постройте таблицу истинности для булевой функции .

«Неверно, что если дует ветер, то солнце светит только тогда, когда нет дождя».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.При составлении расписания на пятницу были высказаны пожелания, чтобы информатика была первым или вторым уроком, физика – первым или третьим, история – вторым или третьим.

Можно ли удовлетворить одновременно все высказанные пожелания?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин и ребер .

15.Сколько существует трехзначных чисел, составленных из цифр 1, 2, 3, 4, 5, и таких, чтобы в каждое число входила цифра 1 при условии, что каждую цифру в числе можно использовать не более одного раза?

Вариант 11

1.Для заданных множеств , , , найдите мощность следующих множеств:, , ,.

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


			?

4.Даны множества и . Найдите .

6.Отображение действует по правилу . Найдите образ .

7.Постройте таблицу истинности для булевой функции .

«Чтобы погода была солнечной, достаточно, чтобы не было ни ветра, ни дождя».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу .

11.В соревнованиях по плаванию участвовали Андрей, Виктор, Саша и Дима. Их друзья высказали предположения о возможных победителях:

§ первым будет Саша, Виктор будет вторым;

§ вторым будет Саша, Дима будет третьим;

§ Андрей будет вторым, Дима будет четвёртым.

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

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Сколько различных шестизначных чисел можно составить из цифр 4, 5, 6, 7, 8, 9, чтобы каждая употреблялась не более одного раза?

Вариант 12

1.Для заданных множеств , , , найдите мощность следующих множеств:, , ,.

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


							?

4.Дано декартово произведение множеств

. Выпишите множества и .

6.Найдите прообраз множества при отображении .

7.Постройте таблицу истинности для булевой функции .

«Неверно, что если погода пасмурная, то дождь идет тогда и только тогда, когда нет ветра».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Три клоуна Бим, Бам и Бом вышли на арену в красной, зеленой и синей рубашках. Их туфли были тех же цветов. У Бима цвета рубашки и туфель совпадали. У Бома ни туфли, ни рубашка не были красными. Бам был в зеленых туфлях, а в рубашке другого цвета. Как были одеты клоуны?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Хоккейная команда состоит из 2 вратарей, 7 защитников и 10 нападающих. Сколькими способами тренер может образовать стартовую шестерку, состоящую из вратаря, двух защитников и трех нападающих?

Вариант 13

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера –Венна.


?

4.Даны множества и . Найдите .

6.Отображение действует по правилу . Найдите образ .

7.Постройте таблицу истинности для булевой функции .

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

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Семья, состоящая из отца , матери и трех дочерей , , , купила телевизор. Условились, что в первый вечер будут смотреть передачи в таком порядке:

§ когда отец смотрит передачу, то мать делает то же;

§ дочери и , обе или одна из них, смотрят передачу;

§ из двух членов семьи – мать и дочь – смотрят передачу одна и только одна;

§ дочери и или обе смотрят, или обе не смотрят;

§ если дочь смотрит передачу, то отец и дочь делают то же;

Кто из членов семьи в этот вечер смотрел передачу?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Семь девушек водят хоровод. Сколькими способами они могут встать в круг?

Вариант 14

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


					?

4.Дано декартово произведение множеств

. Выпишите множества и .

6.Найдите прообраз множества при отображении .

7.Постройте таблицу истинности для булевой функции .

«Необходимо иметь шлем, чтобы играть в американский футбол».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

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

Сколько существует возможных вариантов расписания и каковы они?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

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

Вариант 15

1.Для заданных множеств , , , найдите мощность следующих множеств:, , ,.

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


		?

4.Даны множества и . Найдите .

6.Отображение действует по правилу . Найдите образ .

7.Постройте таблицу истинности для булевой функции .

«Для меня сдать этот курс достаточно, чтобы получить диплом».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Для какого имени истинно высказывание «первая буква имени гласная четвертая буква имени согласная»: 1) ЕЛЕНА 2) ВАДИМ 3) АНТОН 4) ФЕДОР.

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.На вершину горы ведут 5 тропинок. Сколькими способами турист может подняться в гору и потом спуститься с нее при условии, что подъем и спуск должен происходить по разным тропинкам?

Вариант 16

1.Для заданных множеств , , , найдите мощность следующих множеств:, , ,.

2.Докажите тождество с помощью диаграмм Эйлера –Венна.


				?

4.Дано декартово произведение множеств

. Выпишите множества и .

6.Найдите прообраз множества при отображении .

7.Постройте таблицу истинности для булевой функции

«Если розы не красные, то фиалки не синие».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу .

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

§ один считает, что первой будет Наташа, а Маша будет второй;

§ другой болельщик предположил, что второе место займет Люда, а Рита – четвертое место;

§ третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй.

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

Какое место на чемпионате заняли Наташа, Маша, Люда, Рита?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Сколькими способами можно расставить на полке 12 различных книг?

Вариант 17

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.

3.На одной из кафедр университета работают человек, среди которых человек не знают ни одного иностранного языка. человек знают английский, – немецкий, – французский. – знают английский и немецкий, – английский и французский, – немецкий и французский. знают все три языка. По заданным в таблице условиям восстановите недостающую информацию.


								?

4.Даны множества и . Найдите .

6.Отображение действует по правилу . Найдите образ .

7.Постройте таблицу истинности для булевой функции

«Розы красные или фиалки не синие».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.В первом туре школьного конкурса «Эрудит» в четверку лучших вошли: Дима, Катя, Миша и Нина. И, конечно, болельщики высказывали свои предположения о распределении мест во втором, финальном, туре. Один считал, что первым будет Дима, а Миша будет вторым. Другой болельщик выразил надежду на то, что Катя займет четвертое место, а второе место достанется Нине. Третий же был уверен в том, что Катя займет третье место, а на втором месте будет Дима. В результате оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов.

Какие места заняли Дима, Катя, Миша, Нина?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Сколько трехзначных чисел можно составить из цифр 4, 5, 6, чтобы каждая цифра употреблялась не более одного раза?

Вариант 18

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера –Венна.


?

4.Дано декартово произведение множеств

. Выпишите множества и .

5.Найдите прообраз множества при отображении .

6.Для отношения найдите множество определения, множество значений и установите, какими свойствами оно обладает.

7.Постройте таблицу истинности для булевой функции

«Либо розы красные, либо фиалки синие» (но не одновременно).

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу .

11.Алеша, Витя и Игорь после уроков нашли на полу в кабинете физики маленькую гирьку. Каждый из них, рассматривая находку, высказал два предположения. Алеша сказал: «Это гирька из латуни, и весит она, скорее всего, 5 г», Витя предположил, что гирька сделана из меди и весит 3 г. Игорь же считал, что гирька не из латуни и вес ее – 4 г. Учитель физики обрадовался, что пропажа нашлась, и сказал ребятам, что каждый из них прав только наполовину.

Из какого металла – латуни (Л) или меди (М) – изготовлена гирька, и каков ее вес?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Сколькими способами можно расположить в ряд 5 белых и 4 черных шара так, чтобы черные шары не лежали рядом?

Вариант 19

1.Для заданных множеств , , , найдите мощность следующих множеств:, , ,.

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


	?

4.Даны множества и . Найдите .

6.Отображение действует по правилу . Найдите образ .

7.Постройте таблицу истинности для булевой функции

«Сергей пойдет гулять, если пойдут гулять Никита и Тимофей, или все трое останутся дома».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Четыре друга – Антонов ( ), Вехов ( ), Сомов ( ), Деев ( ) – решили провести каникулы в четырех различных городах – Москве, Одессе, Киеве и Ташкенте. Определите, в какой город должен поехать каждый из них, если имеются следующие ограничения:

§ если не едет в Москву, то не едет в Одессу;

§ если не едет ни в Москву, ни в Ташкент, то едет в Москву;

§ если не едет в Ташкент, то едет в Киев;

§ если не едет в Москву, то не едет в Москву;

§ если не едет в Одессу, то не едет в Москву;

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Сколько вариантов существует в лотерее: а) 5 из 36; б) 6 из 49?

Вариант 20

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера –Венна.


						?

4.Дано декартово произведение множеств

. Выпишите множества и .

6.Найдите прообраз множества при отображении .

7.Постройте таблицу истинности для булевой функции

«Неверно, что является истинным высказыванием».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.На одной улице стоят в ряд 4 дома, в которых живут 4 человека: Борис, Виктор, Андрей и Федор. Известно, что каждый из них владеет ровно одной из следующих профессий: дантист, слесарь, плотник и токарь, но неизвестно, кто какой, и неизвестно, кто в каком доме живет. Однако, известно, что:

§ Фёдор не дантист;

§ Дантист живёт через дом от слесаря;

§ Борис живёт рядом с плотником;

§ Токарь живет левее дантиста;

§ Виктор живет справа от дантиста;

§ Токарь живет не рядом со слесарем;

§ Андрей живет рядом с токарем;

§ Плотник живет правее дантиста.

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

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Сколько различных слов можно получить, переставляя буквы слова комбинаторика?

Вариант 21

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


			?

4.Даны множества и . Найдите .

6.Отображение действует по правилу . Найдите образ .

7.Постройте таблицу истинности для булевой функции

«Неверно, что если красный мячик меньше синего, а синий меньше зеленого, то зеленый мячик меньше красного».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Пять школьников из пяти различных городов Брянской области прибыли для участия в областной олимпиаде по математике. На вопрос: «Откуда вы?» каждый дал ответ:

§ Иванов: «Я приехал из Клинцов, а Дмитриев – из Новозыбкова»;

§ Сидоров: «Я приехал из Клинцов, а Петров – из Трубчевска»;

§ Петров: «Я приехал из Клинцов, а Дмитриев – из Дятькова»;

§ Дмитриев: «Я приехал из Новозыбкова, а Ефимов – из Жуковки»;

§ Ефимов: «Я приехал из Жуковки, а Иванов живет в Дятькове».

Откуда приехал каждый из школьников, если одно из утверждений верно, а другое ложно?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Сколько существует способов распределения трех первых мест, если в соревновании участвует восемь команд?

Вариант 22

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


							?

4.Дано декартово произведение множеств

. Выпишите множества и .

6.Найдите прообраз множества при отображении .

7.Постройте таблицу истинности для булевой функции

«Я пойду на рыбалку независимо от того, какая будет погода: солнечная или пасмурная».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Три молодые мамы Анна, Ирина и Ольга, гуляя в парке со своими малышами, встретили свою четвертую подругу. На вопрос, как зовут малышей, желая подшутить над подружкой, они ответили: Анна: «Моего малыша зовут Денис, а Кирилл – сын Ирины». Ирина: «Моего сыночка зовут Максим, а Кирилл – сын Анны». Ольга: «Мой мальчик – Кирилл, а сына Анны зовут Максим». Каждая из них один раз сказала правду и один раз солгала. Как зовут мальчиков Анны, Ирины и Ольги?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.На первой из двух параллельных прямых лежит 10 точек, на второй – 20. Сколько существует треугольников с вершинами в этих точках?

Вариант 23

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


					?

4.Даны множества и . Найдите .

6.Отображение действует по правилу . Найдите образ .

7.Постройте таблицу истинности для булевой функции

«Если в треугольнике любая его медиана не является высотой и биссектрисой, то этот треугольник неравнобедренный и неравносторонний».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Определите, кто из четырех студентов сдал экзамен, если известно:

§ если первый сдал, то и второй сдал;

§ если второй сдал, то третий сдал или первый не сдал;

§ если четвертый не сдал, то первый сдал, а третий не сдал;

§ если четвертый сдал, то и первый сдал.

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

14.Даны графы и . Выпишите для каждого графа множества вершин и ребер. Определите степень каждой вершины. Найдите матрицы смежности и инцидентности. Укажите для графа , какой-либо маршрут из вершины 1. Укажите для графа подграфы.

15.Сколько различных четырехзначных чисел можно составить из цифр 0, …, 9, если каждая цифра в обозначении числа встречается не более одного раза?

Вариант 24

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


		?

4.Дано декартово произведение множеств

. Выпишите множества и .

6.Найдите прообраз множества при отображении .

7.Постройте таблицу истинности для булевой функции

«Неверно, что ни Вера, ни Ира не балерины».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Кто из друзей (Иван, Петр, Алексей, Николай или Борис) коллекционирует марки, если известно, что:

§ если Борис коллекционирует марки, то их коллекционируют Иван и Николай;

§ если их коллекционирует Иван, то Петр тоже коллекционирует марки;

§ из двух друзей (Петр и Алексей) коллекционирует марки только один;

§ Алексей лишь в том случае коллекционирует марки, если их коллекционирует Николай;

§ по крайней мере, Николай или Борис коллекционирует марки.

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Сколькими способами пятеро юношей могут выбрать себе партнершу для танца из восьми девушек?

Вариант 25

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


				?

4.Даны множества и . Найдите .

6.Отображение действует по правилу . Найдите образ .

7.Постройте таблицу истинности для булевой функции

«Ира занимается спортом, и неверно, что она не играет на флейте».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Кто из абитуриентов , , и играет, а кто не играет в шахматы, если известно следующее: если или играет, то не играет; если не играет, то играют и ; – играет.

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Сколькими способами можно выбрать 6 карт из колоды, содержащей 52 карты, так, чтобы среди них были карты каждой масти?

Вариант 26

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


								?

4.Дано декартово произведение множеств

. Выпишите множества и .

6.Найдите прообраз множества при отображении .

7.Постройте таблицу истинности для булевой функции

«Неверно, что если красный мячик больше синего, а синий меньше зеленого, то зеленый мячик больше красного».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

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

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Сколькими способами из натуральных чисел от 1 до 30 можно выбрать три различных числа так, чтобы их сумма была четной?

Вариант 27

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


?

4.Даны множества и . Найдите .

6.Отображение действует по правилу . Найдите образ .

7.Постройте таблицу истинности для булевой функции

«Если Саша выше Жени и Женя ниже Андрея, то или Саша выше Андрея или Андрей выше Саши».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Есть пять коробочек: белая, черная, красная, синяя и зеленая. И десять шариков тех же цветов, что и коробочки, по два каждого цвета. В каждой коробочке лежат по два шарика. При этом:

§ ни один шарик не лежит в коробочке того же цвета, что и он сам;

§ в красной коробочке нет синих шариков;

§ в коробочке нейтрального цвета (белый или черный) лежат один красный и один зеленый шарик;

§ в черной коробочке лежат шарики холодных тонов (зеленые и синие тона);

§ в одной из коробочек лежат один белый и один синий шарик;

§ в синей коробочке находится один черный шарик.

Какого цвета шарики лежат в какой коробочке?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Сколькими способами из натуральных чисел от 1 до 20 можно выбрать два различных числа так, чтобы их сумма была четной?

Вариант 28

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


	?

4.Дано декартово произведение множеств

. Выпишите множества и .

6.Найдите прообраз множества при отображении .

7.Постройте таблицу истинности для булевой функции

«Света пойдет кататься на велосипеде тогда и только тогда, когда пойдет с ней сестра и когда на улице не будет лить дождь».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу .

11.После опроса пассажиров четырех маршрутов трамвая: 55-го, 15-го, 25-го и 33-го, среди которых были Андрей, Павел, Вилмош и Лайош, оказавшиеся каждый из них представителем одной из четырех профессий: слесарь, электромонтер, маляр и фрезеровщик, выяснилось что:

§ номер трамвайного маршрута, которым следует Вилмош, начинается не с единицы;

§ о 33 маршруте рассказывал кто-то из рабочих-металлистов;

§ номер трамвайного маршрута, которым следовал фрезеровщик, составлен из таких цифр, что их сумма равна числу букв в имени фрезеровщика;

§ Лайош рассказывал о трамвайном маршруте, номер которого состоит из двух одинаковых цифр;

§ имя электромонтера начинается не с буквы В;

§ Павел спросил у опрашивающего, где лучше сойти, чтобы пересесть на двадцать пятый маршрут;

§ в памяти опрашивающего вдруг отчетливо всплыла фраза, сказанная Лайошем кому-то из пассажиров: «Вы сели не на тот трамвай, вам нужно пересесть на пятьдесят пятый».

Определите имя и профессию каждого пассажира, номер маршрута, о котором он рассказал?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Сколько диагоналей в выпуклом 100-угольнике?

Вариант 29

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


			?

4.Даны множества и . Найдите .

6.Отображение действует по правилу . Найдите образ .

7.Постройте таблицу истинности для булевой функции

«Для того, чтобы четырехугольник был квадратом, достаточно, чтобы его диагонали были равны и перпендикулярны».

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Митя, Сережа, Толя, Костя и Юра пришли в музей до открытия и встали в очередь в кассу. Митя пришел позже Сережи, Толя раньше Кости, Митя раньше Толи, Юра позже Кости.

В каком порядке ребята стояли в очереди?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Из пункта в пункт ведут 3 дороги, из в – 4 дороги. Сколькими способами можно совершить поездку из в через ?

Вариант 30

1.Для заданных множеств , , , найдите мощность следующих множеств: , , , .

2.Докажите тождество с помощью диаграмм Эйлера – Венна.


					?

4.Дано декартово произведение множеств

. Выпишите множества и .

6.Найдите прообраз множества при отображении .

7.Постройте таблицу истинности для булевой функции

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

9.Определите вид логической формулы (тавтология, противоречие или выполнимая) :

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

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

10.Используя законы логики, упростите формулу

11.Пытаясь вспомнить победителей прошлогоднего турнира, пять бывших зрителей турнира заявили:

§ Антон был вторым, а Борис – пятым;

§ Виктор был вторым, а Денис – третьим;

§ Григорий был первым, а Борис – третьим;

§ Антон был третьим, а Евгений – шестым;

§ Виктор был третьим, а Евгений – четвертым.

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

Каково было истинное распределение мест в турнире?

12.Для логической формулы постройте СДНФ и СКНФ двумя способами:

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

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

13.Нарисуйте граф с множеством вершин

и ребер .

15.Сколько пятизначных целых чисел начинаются с 4 и заканчиваются на 2 или содержат цифру 8?

ЗАКЛЮЧЕНИЕ

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

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

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

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

В пособии рассмотрены теория множеств, математическая логика, теория графов и комбинаторика.

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Азарнова, Т.В. Методические указания для решения задач по курсу «Дискретная математика» / Т.В. Азарнова, И.Н. Булгакова. – Воронеж :
Изд-во ВГУ, 2000. – 50 с.

2. Акимов, О.Е. Дискретная математика: логика, группы, графы / О.Е. Акимов. – М. : Лаборатория базовых знаний, 2001. – 352 с.

3. Алексеев, В.Е. Сборник задач по дискретной математике : задачник
/ В.Е. Алексеев, Л.Г. Киселева, Т.Г. Смирнова. – Н. Новгород : Нижегородский гос. ун-т, 2010. – 53 с.

4. Андерсон, Д.А. Дискретная математика и комбинаторика / Д.А. Андерсон. – М. : Вильямс, 2004. – 960 с.

5. Аристов, В.В. Сборник заданий и упражнений по дискретной математике : практикум / В.В. Аристов, В.Н. Гудинов. – Омск : Изд-во ОмГТУ, 2006. – 52 с.

6. Балабко, Л.В. Дискретная математика. Алгебра логики (Алгебра высказываний) : метод. указания к выполнению самостоятельных и контрольных работ / Л.В. Балабко. – Архангельск : Изд-во ФГАОУ ВПО «Северный (Арктический) федер. ун-т им. М.В. Ломоносова», 2011. – 42 с.

7. Баранов, И.В. Задачи по дискретной математике / И.В. Баранов, В.Н. Глушкова, В.В. Ларченко. – Ростов на/Д : Издат. центр ДГТУ, 2001. – 16 с.

8. Белоусов, А.И. Дискретная математика / А.И. Белоусов, С.Б. Ткачев.
– М. : Изд-во МГТУ им. Н.Э. Баумана, 2004. – 744 с.

9. Булгакова, И.Н. Дискретная математика. Элементы теории. Задачи и упражнения : учеб. пособие / И.Н. Булгакова, Г.Ф. Федотенко. – Воронеж : Изд-во ВГУ, 2004. – 62 с.

10. Гаврилов, Г.П. Задачи и упражнения по дискретной математике : учеб. пособие. – 3-е изд., перераб. / Г.П. Гаврилов, А.А. Сапоженко. – М. : ФИЗМАТЛИТ, 2005. – 416 с.

11. Галушкина, Ю.И. Конспект лекций по дискретной математике
/ Ю.И. Галушкина, А.Н. Марьямов. – М. : Айрис-пресс, 2007. – 176 с.

12. Глаголев, В.В. Методы дискретной математики : учеб. пособие
/ В.В. Глаголев. – Тула : ТулГУ, 2000. – 232 с.

13. Лекции по дискретной математике / Ю.В. Капитонова [и др.]. – СПб. : БХВ-Петербург, 2004. – 624 с.

14. Кожухов, И.Б. Курс дискретной математики : учеб. пособие / И.Б. Кожухов, А.А. Прокофьев, Т.В. Соколова. – М. : МИЭТ, 2000. – 208 с.

15. Кондратьев, А.И. Основы дискретной математики : учеб. пособие
/ А.И. Кондратьев. – Хабаровск : Изд-во ДВГУПС, 2004. – 108 с.

16. Кузнецов, О.П. Дискретная математика для инженера / О.П. Кузнецов, Г.М. Адельсон-Вельский. – 2-е изд., перераб. и доп. – М. : Энергоатомиздат, 1988. – 480 с.

17. Лавров, И.А. Задачи по теории множеств, математической логике и теории алгоритмов / И.А. Лавров, Л.Л. Максимова. – 3-е изд. – М. : Физматлит, 1995. – 247 с.

18. Лихтарников, Л.М. Математическая логика. Курс лекций. Задачник-практикум и решения / Л.М. Лихтарников, Т.Г. Сукачева. – СПб. : Лань, 1999. – 288 с.

19. Макоха, А.Н. Дискретная математика : учеб. пособие / А.Н. Макоха, П.А. Сахнюк, Н.И. Червяков. – М. : ФИЗМАЛИТ, 2005. – 368 с.

20. Марченко, Л.В. Элементы математической логики / Л.В. Марченко.
– Хабаровск : Изд-во ДВГУПС, 2002. – 54 с.

21. Меньших, В.В. Практические занятия по дискретной математике : учеб. пособие / В.В. Меньших, О.В. Пьянов. – Воронеж : Воронежский ин-т МВД России, 2007. – 155 с.

22. Москинова, Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях : учеб. пособие. – М. : Логос, 2000. – 240 с.

23. Новиков, Ф.А. Дискретная математика для программистов / Ф.А. Новиков. – СПб. : Питер, 2000. – 304 с.

24. Плотников, А.Д. Дискретная математика : учеб. пособие / А.Д. Плотников. – М. : Новое знание, 2005. – 288 с.

25. Усов, С.В. Дискретная математика : учеб.-метод. пособие для студентов направления «Информатика и вычислительная техника» / С.В. Усов.
– Омск : Изд-во ОмГУ, 2011. – 60 с.

26. Спирина, М.С. Дискретная математика : учеб. для студентов учреждений сред. проф. образования / М.С. Спирина, П.А. Спирин. – 5-е изд., стер. – М. : Академия, 2009. – 368 с.

27. Судоплатов, С.В. Элементы дискретной математики : учебник
/ С.В. Судоплатов, Е.В. Овчинникова. – М. : ИНФРА-М; Новосибирск :
Изд-во НГТУ, 2002. – 280 с.

28. Судоплатов, С.В. Дискретная математика : учебник / С.В. Судоплатов, Е.В. Овчинникова. – 2-е изд., перераб. – М. : ИНФРА-М; Новосибирск : Изд-во НГТУ, 2007. – 256 с.

29. Хаггард, Г. Дискретная математика для программистов : учеб. пособие / Г. Хаггард, Дж. Шлипф, С. Уйтсайдс. – М. : БИНОМ, Лаборатория знаний, 2010. – 627 с.

30. Хаггарти, Р. Дискретная математика для программистов / Р. Хаггарти. – М. : Техносфера, 2004. – 320 с.

Оглавление

ВВЕДЕНИЕ........................................................................................................................................... 3

1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ..................................................................................... 5

1.1. Основные понятия теории множеств. Способы задания множеств............................. 5

1.2. Операции над множествами................................................................................................. 8

1.3. Диаграммы Эйлера – Венна................................................................................................ 11

1.4. Свойства операций над множествами.............................................................................. 14

1.5. Декартово произведение множеств.................................................................................. 17

1.6. Бинарные отношения. Свойства бинарных отношений............................................... 19

1.7. Функция.................................................................................................................................. 21

2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ................................................................ 23

2.1. Математическая логика как наука.................................................................................... 23

2.2. Высказывания. Логические операции и их основные свойства................................. 24

2.3. Способы решения логических задач................................................................................ 34

2.3.1. Решение логических задач средствами алгебры логики................................ 34

2.3.2. Решение логических задач табличным способом............................................ 37

2.3.3. Решение логических задач с помощью рассуждений..................................... 38

2.4. Булевы функции. Свойства элементарных булевых функций.................................... 39

2.5. Дизъюнктивные и конъюнктивные нормальные формы булевых функций............ 42

2.6. Совершенная дизъюнктивная и совершенная конъюнктивная
нормальные формы............................................................................................................... 43

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

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

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

3.3. Связность графов.................................................................................................................. 57

4. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ....................................................................................... 60

4.1. Перестановки, размещения и их количество.................................................................. 60

4.2. Сочетания и их свойства..................................................................................................... 63

4.3. Выборки с повторением...................................................................................................... 64

5. ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ......................................................................................... 66

ЗАКЛЮЧЕНИЕ............................................................................................................................... 107

БИБЛИОГРАФИЧЕСКИЙ СПИСОК........................................................................................... 107

Учебное издание

Васильева Вера Сергеевна

Коровина Светлана Викторовна

Марченко Любовь Васильевна

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

Учебное пособие

Редактор Т.М. Яковенко

Технический редактор Н.В. Ларионова

————————————————————————————

План 2013 г. Поз. 9.8. Подписано в печать 14.06.2013.

Гарнитура Times New Roman. Печать RISO.

Усл. печ. л. 7,0. Уч.-изд. л. 7,5. Зак. 167. Тираж 125 экз. Цена 198 р.

————————————————————————————

Издательство ДВГУПС

680021, г. Хабаровск, ул. Серышева, 47.