Введение в математическую логику

Основы дискретной математики

Основная литература

1. Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учеб. пособие. - М.: Изд-во МАИ, 1992.

2. Новиков Ф.А. Дискретная математика для программистов. СПб: Питер, 2001.

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

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

 

Дополнительная литература

5. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. - М.: Наука, 1977.

6. Козырев О.Р., Куркин А.А., Максимов А.Г., Митяков С.Н. Теория обработки экономической информации. - Нижний Новгород: НГТУ, 2000.

Введение

 

1. Пользуясь алгоритмом Евклида, найдите наибольший общий делитель
чисел а) 32 и 24; б) 75 и 125.

2. Докажите, что число является иррациональным.

3. Докажите, что среди любых пяти последовательных натуральных чисел обязательно найдется число, делящееся на 5.

4. Докажите, что для всех натуральных n верны равенства:

а) ; б) 1²+2²+3²+…+ n ²= ;

в) ;

г) .

5. Докажите формулы для суммы первых n членов арифметической и геометрической прогрессий.

6. Докажите формулу:

.

7. Доказать, что для всех натуральных n

а) выражение делится без остатка на 3; б) выражение кратно 6;

в) кратно 16; г) кратно 4; д) кратно 17.

8. Докажите неравенство Якоба Бернулли (1654-1705 гг.): если x >-1, то для всех натуральных значений n выполняется неравенство .

9. Докажите неравенство для натуральных n ³3: 2 ⁿ >2 n +1.

10. Доказать, что для всех натуральных n справедливы неравенства:

а) ;

б) , если a >0 и b >0.

11. Числовая последовательность задана рекуррентным способом: x ₁=1, , где . Вывести формулу n -го члена этой последовательности.

12. Дано: a ₁=2, a_{n +1}=3 a_n +1. Докажите, что a_n = , где .

13. Числовая последовательность а ₁, а ₂, …, а_n,… задана условиями: a ₁=1, a ₂=9,
, где . Докажите, что .

14. Дано: a ₁=29, a ₂=85, . Докажите, что , где .

15. Последовательность задана условиями: а ₀=0, .
Докажите, что для всех имеем: .

16. Последовательность Фибоначчи определяется следующими условиями:

a ₀=0, a ₁=1, . Докажите, что .

17. На плоскости проведено n прямых, из которых никакие две не параллельны и никакие три не проходят через одну точку. На сколько частей разбивают плоскость эти прямые?

 

Теория множеств

18. Докажите утверждение: .

19. Даны 2 множества: A =(1; 3), B =(2; 4). Составьте множества А È В, А Ç В, А \ В, А Ä В.

20. Даны конечные множества: A ={ a, b, c, h, z }, B ={ a, c, e, f, z }, C ={ a, d, e, h }. Из каких элементов состоят множества , , ?

21. Даны множества:
, , .
Изобразите на плоскости (x, y) множества ; ; .

22. Изобразите на диаграмме Венна-Эйлера следующие множества:

а) ; б) ; в) ; г) .

23. Даны множества A, B, C. При помощи операций È, Ç, \ запишите множество элементов, которые принадлежат:

а) всем трём указанным множествам;

б) по крайней мере, одному из этих множеств;

в) любым двум из этих множеств, но не принадлежат всем трём.

г) по крайней мере, двум из этих множеств;

д) любому одному из этих множеств, но не принадлежат двум другим.

 

24. С помощью диаграммы Венна-Эйлера упростите выражения:

а) ; б) ; в) ;

г) ; д) .

25. Какие отношения включения справедливы для следующих пар множеств:

а) и ; б) и ;

в) и ?

26. Замените знак * операцией алгебры множеств (È, Ç, \, Ä) так, чтобы равенство
было верным. Ответ обоснуйте с помощью диаграммы
Венна.

27. Какому множеству соответствуют прямоугольники диаграммы Венна для трёх
множеств с номерами

а) {4, 5}, б) {2, 3, 7}?

Запишите это множество с помощью не более чем трёх операций алгебры множеств: È, Ç, \, Ä (каждая операция считается столько раз, сколько встречается в этом выражении; абсолютное дополнение можно использовать сколько угодно раз). Изобразите полученный результат на диаграмме Венна.

 

28. С помощью диаграммы Венна-Эйлера покажите справедливость законов

а) де Моргана; б) поглощения.

29. Проверьте на диаграмме Венна, выполняются ли законы:
а) ассоциативности разности;

б) ассоциативности симметрической разности;

в) дистрибутивности объединения относительно симметрической разности;

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

30. Упростите выражения с помощью законов алгебры множеств:

a) ; б) ; в) ;

г) ; д) ;

е) ; ж) .

31. Составьте множество всех подмножеств (булеан) множества А, если

а) ; б) ; в) .

32. Даны множества: A=[0; 3], B=[-1; 1].

Изобразите на плоскости (x; y) прямое произведение этих множеств и .

33. Проверьте справедливость четырех законов дистрибутивности (´ относительно È; ´ относительно Ç; È относительно ´; Ç относительно ´) на примере множеств A =[0; 1], B =[1; 2], C =[-1; 3]. Изобразите в пространстве (x; y; z) множества и .

34. Даны 2 множества: A ={2; 3}, B ={5; 6}.
а) Составьте множества , , .

б) Какова мощность множества ?
Выпишите любые 4 элемента этого множества.

в) Из каких элементов состоит заданное на множестве бинарное
отношение ? Постройте матрицу такого
отношения. Найдите D _r и Е _r.

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

35. Даны 2 множества: A ={1; 2; 3}, B ={4; 5; 6}.
а) Составьте множества и .

б) Какова мощность множеств и ?
Выпишите любые 4 элемента каждого из этих множеств.

в) Из каких элементов состоит заданное на множестве бинарное
отношение ? Постройте матрицу такого отношения. Найдите D _r и Е _r.

г) Сколько существует разбиений множества A È В, все блоки которых равны между
собой по мощности и каждый из них содержит ровно одно нечетное число этого
множества?

36. Бинарные отношения r₁ и r₂ заданы матрицами.

а)

Постройте матрицу композиции r₁Or₂.

 

б)

, .

Постройте матрицу композиции r₁Or₂. Является ли отношение r₁Or₂ рефлексивным или антирефлексивным, симметричным или антисимметричным?

 

в)

, .

Постройте матрицу композиции r₂Or₁. Является ли отношение r₂Or₁ рефлексивным или антирефлексивным, симметричным или антисимметричным?

 

37. Составьте матрицу для заданного на множестве бинарного отношения r. Является ли r отношением эквивалентности или порядка (полного или частичного? cтрогого или нестрогого?)? Для заданий (в) и (г) найдите также
r^-1 и rOr^-1.

 

а) X={3, 6, 9, 12, 18}, ;

б) X={1, 3, 5, 6, 7}, ;

в) X={4, 8, 12, 24, 36}, ;

г) X={1, 2, 3, 4, 5}, .

38. Является ли бинарное отношение r рефлексивным или антирефлексивным, симметричным или антисимметричным, транзитивным, полным?

а) x r y = «x – сестра y » (на множестве людей);

б) x r y = «число x больше числа y на 1» (на множестве целых чисел).

 

 

Комбинаторика

39. Для проведения опроса преподаватель приготовил три вопроса. Студент Половинкин, присутствующий на занятии, знает ответ лишь на первый из них. При скольких вариантах распределения вопросов Половинкин получит “двойку” при опросе, если в классе 25 студентов, по каждому вопросу спрашивается только один человек, и каждый студент может выступить только один раз?

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

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

42. Сколько четырехзначных чисел, составленных из цифр 0, 1, 2, 3, 4, 5, содержат цифру 3 (цифры в числах не повторяются)?

43. Сколькими способами можно разложить 9 орехов по трем карманам? (Карманы разные, а орехи одинаковые.)

44. Доказать тождества:

а) ; б) ; в) ; г) .

45. Номер автомобильного прицепа состоит из 2 букв и 4 цифр. Сколько различных номеров можно составить, используя 30 букв и 10 цифр?

46. 5 шахматистов играют друг с другом в 2 круга (т.е. каждый дважды встречается с любым другим). Сколько всего партий будет сыграно в таком турнире?

47. Сколькими способами можно из 8 человек составить комиссию из 3 человек, если а) все члены комиссии имеют равные права и обязанности? б) комиссия состоит из председателя, заместителя председателя и секретаря?

48. Сколькими способами можно упорядочить множество натуральных чисел
{1, 2, 3, …, 2 n } так, чтобы любое четное число стояло на четном месте?

49. Сколькими способами можно разместить на полке 10 книг так, чтобы 3 нужные книги оказались стоящими рядом?

50. Сколькими способами можно разложить 20 одинаковых шаров по 4 различным урнам?

51. В соревнованиях по баскетболу участвуют 12 команд, из которых 4 являются фаворитами. Команды жеребьевкой делятся на 2 подгруппы. Сколько существует таких исходов жеребьевки, что 3 фаворита попадут в одну подгруппу (подгруппы отличаются между собой номерами)?

52. В ювелирную мастерскую привезли 6 изумрудов, 9 алмазов и 7 сапфиров. Ювелиру заказали браслет, в котором 3 изумруда, 5 алмазов и 2 сапфиров. Сколькими способами он может выбрать камни на браслет?

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

54. Сколько четырехзначных чисел, делящихся на 5, можно составить из цифр 0, 1, 3, 5, 7, если каждое число не должно содержать одинаковых цифр?

55. Группа из 8 человек садится за круглый стол. Сколько существует таких способов размещения этой группы, что 2 определенных лица окажутся сидящими рядом?

56. Сколько существует различных номеров серии облигаций, не содержащих одинаковых цифр, если номер серии может быть любым 5-значным числом, начиная с 00001?

57. Расписание одного дня содержит 4 пары. Определите количество таких расписаний при выборе из 11 дисциплин.

58. Сколькими способами можно разбить 10 человек на две баскетбольные команды по 5 человек в каждой?

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

60. Шесть коробок с мороженым шести видов нужно развезти по 5 магазинам. Сколькими способами можно распределить мороженое по магазинам, если в каждой коробке имеется мороженое лишь одного вида? В скольких вариантах в 1-ый магазин доставляется какая-либо одна коробка?

61. В скольких случаях при выборе из колоды в 52 карты 10 карт среди них окажутся все 4 туза?

62. Буквы азбуки Морзе состоят из символов (точек и тире). Сколько букв можно изобразить, если потребовать, чтобы каждая буква содержала не более 5 символов?

63. Лифт, в котором находится 9 пассажиров, может останавливаться на 10 этажах. Пассажиры выходят группами по 2, 3, и 4 человека. Сколькими способами это может произойти?

64. Каков наибольший коэффициент разложения , если сумма всех коэффициентов равна 4096?

65. При каком значении х четвертое слагаемое разложения в 20 раз больше m, если биномиальный коэффициент четвертого слагаемого относится к биномиальному коэффициенту второго слагаемого, как 5:1?

66. Найти наибольший биномиальный коэффициент разложения , если произведение четвертого от начала и четвертого от конца слагаемых равно 14400?

67. Третье слагаемое разложения не содержит х. При каких значениях х это слагаемое равно второму слагаемому разложения ?

68. Стрелок совершает серию из 10 выстрелов. Сколько существует различных вариантов распределения попаданий по номерам выстрелов в серии, содержащей 4 попадания в “яблочко” и 4 попадания в остальную часть мишени?

69. Сколькими способами можно поселить 7 студентов в три комнаты: одноместную, двухместную и четырехместную?

70. Сколькими способами группу из 25 человек можно разбить на 7 коалиций: 2 – по 5 человек, 1 – 7 человек, 4 – по 2 человека?

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

72. Сколько существует натуральных чисел, меньших 1000, которые не делятся ни на 3, ни на 5, ни на 7?

73. Дано множество А ={1, …, 20} и 3 его подмножества:
А ₁={ a | a кратно 4}, А ₂={ a | a >8}, А ₃={ a | 5< a <17}. Сколько элементов множества А не принадлежат ни одному из этих подмножеств?

74. Из 100 сотрудников фирмы 52 человека знает английский язык, 36 - французский язык, 40 - немецкий язык. Сколько сотрудников владеет всеми тремя языками, если каждой парой вышеназванных языков владеет по 10 человек и каждый сотрудник знает хотя бы 1 иностранный язык?

75. Сколькими способами из группы в 30 человек можно сформировать 5 команд для игры “Что? Где? Когда?” (по 6 равноправных человек в каждой)?

Алгебра логики

76. Таблицами истинности заданы 7 функций.

а) Определите, какие переменные у них являются фиктивными, и исключите их.

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

 

x	y	f 1	f 2	f 3

 

 

x	y	z	f 4	f 5	f 6	f 7

 

77. Даны функции

, , , ,

, , , .

По заданным суперпозициям

, ,

1) напишите формулы, реализующие функции f, g, h;

2) составьте таблицы истинности для этих функций;

3) найдите фиктивные переменные и исключите их.

78. Представьте функции и в виде суперпозиций функций f_i (i =1…8) из задачи 77. Cоставьте таблицы истинности для функций f и g. Есть ли у этих функций фиктивные переменные?

79. Проверьте, справедливы ли следующие равенства:

а) ;б) ;

в) ; г) .

80. Без составления таблицы истинности получите двойственные функции к , и .

81. Упростите данные СДНФ и СКНФ:
а) ; б) ;

в) ; г) .

82. Даны функции
f (x, y, z)=(10100101), g (x, y, z)=(01001111), h (x, y, z)=(01100101).

1) Найдите фиктивные переменные и исключите их.

2) постройте таблицу значений для функций f*, g*, h*, двойственных к данным;

3) напишите СДНФ и СКНФ для функций f, g и h;

4) минимизируйте СДНФ для функций f, g и h;

5) с помощью принципа двойственности получите формулы для функций f*, g*, h*;

6) разными способами получите полиномы Жегалкина для функций f, g и h.

83. Постройте полиномы Жегалкина для функций:

а) ; б) ; в) .

84. Функции f ₁, g ₁, h ₁, f ₂, g ₂, h ₂ заданы таблицами истинности.

x	y	z	f 1	g 1	h 1	f 2	g 2	h 2

1) Запишите эти функции в виде СДНФ или СКНФ.

2) Постройте для них полиномы Жегалкина.

3) Получите из каждой из этих функций, если возможно, константу, инверсию и конъюнкцию.

 

85. Получите конъюнкцию из функций и .

86. С помощью теоремы о полноте второй системы докажите полноту следующих систем булевых функций:

а) {¤}, б) {Ø, ®}, в) {1, &, Å}.

87. Функции f ₁, g ₁, h ₁, f ₂, g ₂, h ₂ заданы в условии задачи 84.

1) Является ли система данных функций { f ₁, g ₁, h ₁, f ₂, g ₂, h ₂} полной?

2) Найдите все возможные базисы в этой системе.

3) Какие новые базисы образуются при добавлении к данной системе функций
и ?

88. С помощью теоремы Поста о функциональной полноте выясните, являются ли полными системы булевых функций

а) { x ¯ y, x Å y }, б) {0, x & y, x~y }, в) { , }.

89. Найдите все возможные базисы в системе функций { f ₁, f ₂, f ₃, f ₄, f ₅}, где
, , ,
, .

Из функций f ₄ и f ₅ получите, если возможно, константу, инверсию и конъюнкцию.

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

91. Является ли полным класс булевых функций SÈ{ }?

92. Даны функции

, , , ,

, , , .

По заданным суперпозициям

1) напишите формулы, реализующие функции f, g, h;

2) составьте таблицы истинности для этих функций;

3) найдите фиктивные переменные и исключите их;

4) постройте таблицу значений для функций f*, g*, h*, двойственных к данным;

5) напишите СДНФ и СКНФ для функций f, g, h;

6) разными способами получите полиномы Жегалкина для функций f, g, h;

7) принадлежат ли данные функции важнейшим замкнутым классам алгебры логики T₀, T₁, S, М, L?

8) является ли полной система функций { f, g, h }?

9) из функций f, g, h получите, если возможно, константу, инверсию и конъюнкцию.

 

Введение в математическую логику

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

а) Если идет дождь, то дует ветер.

б) Дождь начнется, только если подует ветер.

в) Завтра или пойдет дождь, или будет снегопад.

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

д) Для того чтобы х было нечетным, достаточно, чтобы х было простым.

е) Петя ходит в кино только тогда, когда там показывают новый триллер.

 

94. Докажите рассуждениями тождественную истинность формул:
а) ; б) ; в) ; г) .

95. Докажите рассуждениями следующие равносильности:
а) ; б) ; в) .

96. Докажите равносильности с помощью законов логики высказываний:
а) ;

б) .

97. Докажите равносильности методом математической индукции:
а) - обоснование метода перебора;

б) обобщенные законы де Моргана для & и Ú;

в) обобщенные законы дистрибутивности Ú относительно & и & относительно Ú.

98. Пусть А и В – жители острова, обитатели которого относятся либо к “рыцарям”, всегда говорящим только правду, либо к “лжецам”, изрекающим только ложь. А говорит относительно себя и В: “По крайней мере один из нас лжец”. Кто А и кто В?

99. Пусть А и В – жители острова, обитатели которого относятся либо к “рыцарям”, всегда говорящим только правду, либо к “лжецам”, изрекающим только ложь. А говорит: “Если я рыцарь, то В - рыцарь”. Кто А и кто В?

100. Пусть А и В – жители острова, обитатели которого относятся либо к “рыцарям”, всегда говорящим только правду, либо к “лжецам”, изрекающим только ложь. А говорит про себя, В и С: “Мы все лжецы”. В говорит про себя и С: “Один из нас двоих рыцарь, а другой лжец”. Кто А, кто В и кто С?

101. Обвиняемые А, В, С дали следующие показания:

A: “ B виновен, а С невиновен”.

В: “ A невиновен или С виновен”.

С: “Я невиновен, но хотя бы один из А и В виновен”.

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

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

1) если 1-ый сдал, то и 2-ой сдал;

2) если 2-ой сдал, то 3-ий сдал или 1-ый не сдал;

3) если 4-ый не сдал, то 1-ый сдал, а 3-ий не сдал;

4) если 4-ый сдал, то и 1-ый сдал.

103. Не составляя таблиц истинности, приведите данные формулы к CДНФ или CКНФ и выясните, являются ли они тавтологиями или тождественно ложными.

а) ; б) ;

в) .

104. Пользуясь законом контрпозиции , докажите следующие теоремы:

а) Если mn – нечетное число, то m и n – нечетные числа.

б) Если , то или .

105. Докажите, что рассуждения по схемам

а) (A Þ B, A) Þ B и б) (A Þ B, ) Þ

являются правильными.

 

106. Можно ли на основании посылок “Если предмет интересен, то он полезен” и “Предмет неинтересен” заключить, что предмет бесполезен?

 

107. Следует ли из предложения “Если студент много занимается, то он успешно сдает экзамены” предложение “Студент, провалившийся на экзамене, мало занимался”?

 

108. Проверьте правильность следующих рассуждений методом редукций.

1. Если не повысят налоги, то в бюджете возникнет дефицит. Если в бюджете будет дефицит, то сократятся расходы на социальные нужды. Следовательно, если повысят налоги, то расходы на социальные нужды не сократятся.

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

3. Если сегодня вечером будет мороз, то я пойду на каток. Если завтра будет оттепель, то я пойду в кино. Сегодня вечером будет мороз или завтра будет оттепель. Следовательно, я пойду на каток и в кино.