Программа курса D

математической логике. Действительно, так как высказывание ложно только в случае "истина"→"ложь", то истинными являются высказывания: "Если 22=5, то этот текст написан Римским Папой", "Если 22=5, то этот текст написан не Римским Папой" и даже "Если 22=5, то 22=4". Этот принцип – из лжи следует что угодно – весьма разумен.

5. Эквивалентностью высказываний а и b называется высказывание, обозначаемое в нашем курсе (в литературе иногда ), которое истинно тогда и только тогда, когда a и b либо оба истинны, либо оба ложны. Таким образом, таблица истинности для операции эквивалентности имеет вид:

Операции эквивалентности соответствуют выражения "… тогда и только тогда, когда …", "чтобы …, необходимо и достаточно, чтобы …", "… в том и только в том случае, когда …". Например, если a – высказывание "10 делится на 2", b – высказывание "10 делится на 3", а c – высказывание "15 делится на 2", то высказывания и ложны, а высказывание истинно.

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

Пример. Записать утверждение "Число делится на 6 тогда и только тогда, когда оно делится на 2 и на 3" в виде сложного высказывания с использованием соответствующих логических операций.

Решение. Введем простые высказывания: а – "число делится на 2"; b – "число делится на 3"; с – " число делится на 6". Тогда требуемое утверждение запишется в виде: .

Свойства логических операций

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

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

Будем называть сложное высказывание формулой. Для формул будем употреблять большие латинские буквы: A, B, C, …

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

Пример. Пусть , . Доказать, что .

Решение. Пользуясь таблицами истинности для импликации, отрицания и дизъюнкции, построим таблицы истинности для формул А и В и убедимся в том, что значения А и В при всех значениях a и b совпадают:

а	b
0	0	1	1
0	1	1	1
1	0	0	0
1	1	1	1

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

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. .

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

Пример. Упростить формулу .

Решение. Используя свойства 11, 8, 5, 2, 1, 10, 3 и предыдущий пример, получаем следующую цепочку:





.

Заметим, что всякую формулу логики высказываний можно рассматривать как некоторую функцию: каждому набору значений входящих в формулу простых высказываний (аргументов) однозначно ставится в соответствие одно из двух значений – истина или ложь – представленного формулой сложного высказывания. Такие функции называются булевыми функциями. Это понятие вполне аналогично привычному понятию числовой функции из элементарной алгебры. Различие в том, что областью определения и областью значений числовых функций являются числовые множества (обычно бесконечные), а для булевых функций области определения каждого из аргументов и область значений функции содержат лишь два элемента: «истина» и «ложь». Логические операции по отношению к высказываниям играют ту же роль, что алгебраические операции сложения, умножения, возведения в степень и др. играют по отношению к числовым переменным и константам.

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

Задачи

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

а) если число делится на 4, то оно делится на два;

б) если студент Петя не выучит законы логики, то он не сдаст экзамен и будет отчислен из института;

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

2. С помощью таблиц истинности докажите свойства 1-12.

3. Упростите формулы:

а) ;

б) ;

в) .

4. Из трех данных высказываний a, b, c постройте формулу, определяющую сложное высказывание, которое

а) истинно тогда и только тогда, когда все данные высказывания истинны;

б) ложно тогда и только тогда, когда все данные высказывания ложны;

в) истинно тогда и только тогда, когда все данные высказывания ложны;

г) ложно тогда и только тогда, когда все данные высказывания истинны;

д) истинно тогда и только тогда, когда истинны высказывания a и b;

е) истинно тогда и только тогда, когда ложны высказывания a и b;

ж) ложно тогда и только тогда, когда истинны высказывания a и b;

з) ложно тогда и только тогда, когда ложны высказывания a и b;

и) истинно тогда и только тогда, когда либо все данные высказывания истинны, либо ложны;

к) ложно тогда и только тогда, когда либо все данные высказывания истинны, либо ложны;

л) ложно тогда и только тогда, когда ложно лишь высказывание c.

Пример решения. л) Искомое высказывание ложно лишь в одном случае: когда высказывание c ложно, а оба высказывания a и b истинны. Таким высказыванием могло бы стать высказывание вида , где сложное высказывание M должно быть так сконструировано из высказываний a и b, что M ложно тогда и только тогда, когда ложно хотя бы одно из высказываний a или b. Ясно, что этим требованиям удовлетворяет конъюнкция . Таким образом, искомое высказывание имеет вид .

5. Определите, истинно или ложно последнее высказывание, исходя из истинности или ложности предыдущих высказываний.

а) , , ;

б) , ;

в) , ;

г) , , ;

д) , , ;

е) , , ;

ж) , , , ;

з) , , , ;

и) , , , ;

к) , ;

л) , , ;

м) , .

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

Элементы теории графов

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

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

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

Вершины, имеющие четную степень, называются четными, имеющие нечетную степень – нечетными.

Теорема. Число нечетных вершин любого графа четно.

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

Допустим, в графе нечетное число нечетных вершин. Сумма их степеней нечетна как сумма нечетного числа нечетных слагаемых. Сумма степеней всех четных вершин в любом случае четна. Тогда сумма степеней всех вершин нечетна, что противоречит первой части доказательства. Значит, в графе четное число нечетных вершин, что и требовалось доказать.

Пример. Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?

Решение. Допустим, описанное построение возможно. Поставим в соответствие каждому из отрезков вершину графа и соединим те и только те пары вершин, соответствующие которым отрезки пересекаются. Получим граф с девятью вершинами, каждая из которых имеет степень 3. Но согласно приведенной выше теореме такого графа не существует! Значит, наше предположение было неверным: построить такие 9 отрезков невозможно.

Дадим несколько важных определений.

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

Граф называется связным, если любые две его вершины могут быть соединены путем.

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

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

Эйлеровы графы

Первая работа о графах, принадлежащая Леонарду Эйлеру, появилась в 1736 г. Эйлер начал свою работу с рассмотрения одной головоломки – так называемой "задачи о кёнигсбергских мостах". Город Кёнигсберг расположен на берегах реки Прегель и двух островах. Различные части города были соединены семью мостами. Вопрос заключался в том, можно ли совершить прогулку по городу таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту? Изложив решение задачи о кёнигсбергских мостах, Эйлер в своей работе перешел к следующей общей проблеме теории графов: на каких графах существует цикл, содержащий все ребра графа, причем каждое ребро в точности по одному разу?

Такие графы сейчас называются эйлеровыми.

Теорема. Граф является эйлеровым тогда и только тогда, когда он связен и все его вершины – четны.

Иногда этому факту придают несколько иной вид:

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

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

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

Теорема. На любом связном графе с 2k нечетными вершинами имеется k простых путей, которые в совокупности содержат все ребра графа в точности по одному разу.

Деревья

Определение. Связный граф, не имеющий циклов, называется деревом.

Теорема 1. Граф, в котором любые две вершины соединены ровно одним простым путем, является деревом.

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

Верно и обратное:

Теорема 2. В дереве любые две вершины можно соединить ровно одним простым путем.

Таким образом, мы получаем другое определение дерева, эквивалентное предыдущему: дерево – это граф, в котором любые две вершины соединены ровно одним путем.

Теорема 3. В дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется висячей).

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

Теорема 4. В дереве число вершин на 1 больше числа ребер.

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

Теорема 5. Связный граф, число вершин которого на 1 больше числа ребер, является деревом.

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

Теорема 6. На n вершинах можно построить n^n-2 различных дерева.

Задачи

1. Пусть в графе каждые две вершины соединены не более чем одним ребром. Существует ли такой граф с шестью вершинами, степени которых равны: а) 3, 3, 3, 4, 4, 4; б) 3, 3, 3, 5, 5, 5; в) 2, 2, 2, 2, 5, 5; г) 2, 3, 3, 4, 4, 4; д) 0, 1, 2, 3, 4, 5?

2. В городе Перми в 1905 году было 45 телефонных аппаратов, некоторые из которых были соединены проводами. Могло ли быть так, что каждый из них был соединен ровно с пятью другими?

3. Семеро друзей, разъезжаясь в отпуск, условились, что каждый из них пошлет открытки ровно троим из остальных. Может ли случиться, что каждый из них получит открытки именно от тех троих друзей, которым напишет сам?

4. Из столицы Тридевятого царства выходит в другие города 21 авиалиния. Из города Захолустного выходит только одна авиалиния, из всех остальных городов – по 10 авиалиний. Докажите, что из столицы можно долететь до Захолустного (напрямую или с пересадками в других городах).

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

6. Дан кусок проволоки длиной 120 см. а) Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см? б) Какое наименьшее число раз придется ломать проволоку, чтобы все-таки изготовить указанный каркас?

7. В стране Дубравии 101 город, некоторые из которых соединены дорогами. Любые два города соединяет ровно один путь. Сколько в этой стране дорог?

8. В графе все вершины имеют степень 3. Докажите, что в нем есть цикл.

9. Докажите теорему 2.

10. Докажите теорему 4.

11. Докажите обобщение теоремы 3: любое дерево содержит как минимум две висячие вершины.

12. Докажите, что при удалении из дерева любого ребра дерево превращается в несвязный граф.

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

14. Докажите, что можно проехать по дорогам через все города страны Связной (см. задачу 5), сделав не более а) 198 переездов, б) 196 переездов?

Задачи для курсовой работы

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

Следовать указаниям не обязательно: в частности, при решении можно вообще не использовать понятие графа. Идейное творчество приветствуется! – только не стоит относится к задачам слишком самоуверенно.

Задачи

1. В некоторой стране n городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать по дорогам в любой другой (через другие города)?

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

2. В Швамбрании N городов, каждые два из них соединены дорогой. Дороги сходятся лишь в городах (перекрестков нет, при пересечении одна дорога поднята над другой эстакадой). Злой волшебник хочет установить на всех дорогах одностороннее движение таким образом, что если из города можно выехать, то в него нельзя вернуться (передвигаясь только по дорогам в заданном направлении).

Докажите, что

а) волшебник может осуществить свое намерение; в таком случае

б) найдётся город, из которого можно будет добраться до всех остальных городов и найдётся город, из которого нельзя будет выехать;

в) будет существовать – и притом единственный – путь, обходящий все города;

наконец, г) волшебник может осуществить своё намерение способами.

Указание. Удобно выполнять пункты именно в порядке а)-б)-в)-г).

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

Указание. Удобно рассматривать граф: вершины – поля доски; ребра соединяют вершины, соответствующие полям, связанным ходом коня.

4. Из восьми маленьких кубиков сложен куб. Можно ли, выйдя из центра большого куба и двигаясь по рёбрам маленьких кубиков, обойти все вершины маленьких кубиков, побывав в каждой ровно один раз?

Указание. Рассмотрите два множества: множество вершин, до которых из центра можно добраться за чётное число ходов, и множество вершин, до которых можно добраться за нечётное число ходов.

5. В Простоквашинской начальной школе учатся всего 20 детей. У любых двух из них есть общий дед. Докажите, что у одного из дедов в этой школе учатся не менее 14 внуков и внучек.

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

6. На конкурсе задач по математике в институте МИМИНО предлагалось 20 задач. На закрытие пришло 20 студентов. При этом выяснилось, что каждый из пришедших студентов решил 2 задачи и каждую из задач решили 2 студента. Докажите, что можно так организовать разбор задач, чтобы каждый из студентов рассказал решение одной из решенных им задач и решения всех задач были разобраны.

Указание. Каждого студента обозначим вершиной графа. Соединим те вершины, соответствующие которым студенты решили одну и ту же задачу.

Теперь задачи на использование специальных терминов:

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

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

а) б)

7. Обозначим через V число вершин плоского графа, E – число ребер, F – число областей, на которые граф разбивает плоскость, если его изобразить так, чтобы рёбра не пересекались. (Например, граф на рисунке б) разбивает плоскость на 4 области, одна из которых бесконечная). Докажите следующую теорему Эйлера: для любого плоского графа имеет место равенство .

Указание. Посмотрите, как изменятся числа V, E и F при удалении из графа одного ребра (произвольного).

8. Можно ли построить три дома, вырыть три колодца и соединить тропинками каждый дом с каждым колодцем так, чтобы тропинки не пересекались?

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

Два графа называются изоморфными, если между множествами их вершин можно установить взаимно однозначное соответствие так, что две произвольные вершины одного графа соединены ребром в том и только том случае, когда соединены ребром соответствующие вершины другого графа. Грубо говоря, изоморфные графы – это «одинаковые» графы.

9. Найти все графы, изоморфные своему смежностному графу. Обосновать, что других нет.

10. Пусть про данный граф известно, что он является смежностным к некоторому другому графу. Всегда ли этот последний граф единственный? Другими словами, всегда ли граф однозначно определяется своим смежностным графом?

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

11. В волейбольном турнире участвовало 12 команд, причём после его окончания выяснилось, что ни одна из них не набрала ровно 7 очков. Докажите, что найдутся три команды А, В и С такие, что А выиграла у В, В у С и С у А.

12. Генерал Шито-Крыто послал на необитаемый остров для тренировки 20 шпиончиков. Через сутки он получил два сообщения:

а) каждый шпиончик установил слежку за 10 другими;

б) никакие шпиончики не следят друг за другом.

Может ли генерал доверять своему отделу информации?

Указание. Обозначим шпиончиков точками на плоскости, а факт «А следит за В» – отрезком АВ со стрелкой от А к В. Получим ориентированный граф. Требуется выяснить, существует ли граф, удовлетворяющий условиям задачи.

13. Дана последовательность из 36 нулей и единиц, первые пяти цифр которой – нули. Среди пятерок подряд стоящих цифр встречаются все 32 возможные комбинации: 00000, 00001, 00010, 00011, 00100 и т. д. Найдите пять последних цифр последовательности.

Замечание: считается доказанным, что рассматриваемая последовательность существует (ср. с условием следующей задачи).

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

14. Докажите, что последовательность из нулей и единиц, описанная в условии предыдущей задачи, существует.

И еще «призовые» задачи. В случае успешного решения одной из

них экзамен засчитывается «автоматом» (все темы курса!). Но: не стоит увлекаться этими задачами, если вы не уверены в своих силах.

15. * В пространстве расположены n точек. Сколькими способами можно построить дерево, вершины которого – данные точки? Используются все n вершин. (То есть докажите теорему 6 – см. конец методички.)

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

16. * Двое играют в игру: по очереди расставляют по одной шашке на свободные поля шахматной доски. Выигрывает тот, кому удаётся поставить шашку на такое поле, до которого на данный момент игры не может добраться шахматный конь, прыгая по свободным полям доски, начиная с поля а1 (если поле а1 занято, то конь ни до какого свободного поля не может добраться). Если никому не удаётся выиграть до того как все поля доски окажутся занятыми, то игра считается закончившейся вничью. Имеет ли кто-либо из игроков выигрышную стратегию? Если да, то кто – делающий первый ход или его партнёр?

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

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

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

Литература

1. Г. Г. Асеев, О. М. Абрамов, Д. Э. Ситников. Дискретная математика. Ростов-на-Дону: Феникс, 2003.

2. С.В. Судоплатов, Е.В. Овчинникова. Дискретная математика. М.: Инфра-М, Новосибирск, Изд-во НГУ, 2003.

3. Г.А. Гончарова, А.А. Мочалин. Элементы дискретной математики. М.: Форум – Инфра-М, 2004.

4. С. В. Яблонский. Введение в дискретную математику. М.: Наука, 1979, переработанное издание 1986, недавно снова переиздана.

Дополнительная литература по разделам курса:

5. Н. Я. Виленкин. Рассказы о множествах. М., "Наука", 1965.

6. Н. Я. Виленкин. Комбинаторика. М., "Наука", 1969.

7. И. М. Яглом. Необыкновенная алгебра. М., "Наука", 1968.

8. Л. А. Калужин. Что такое математическая логика? М., "Наука", 1964.

9. О. Оре. Графы и их применение. М., "Мир", 1962.