Элементы математической логики.

Контрольные вопросы.

1. Приведите примеры высказываний с кванторами.

2. Высказывания какого вида называются кванторами общности (кванторами существования)?

3. Как построить отрицание высказывания с квантором общности (существования)?

4. Как обосновать

а) истинность высказывания с квантором общности;

б) ложность высказывания с квантором общности;

в) истинность высказывания с квантором существования;

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

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

6. Как определяется эквиваленция двух высказываний? Какой вид имеет таблица истинности эквиваленции?

7. Что называется отношением логического следования? Приведите примеры отношений логического следования.

8. Дайте определение отношения равносильности. Приведите примеры отношений равносильности.

9. Как связаны множества истинности высказывательных форм А(х) и В(х), если

а) А(х) Þ В(х);

б) А(х) Û В(х) ?

Упражнения

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

а) Всякое число, умноженное на нуль, есть нуль.

б) Произведение любого числа и единицы есть это число.

в) При делении нуля на любое другое число получается нуль.

г) Квадрат любого числа неотрицателен.

2. Укажите способы установления значения истинности высказываний, содержащих кванторы, заполнив таблицу:

Структура высказывания Значение истинности	("хÎХ)А(х)	($хÎХ)½А(х)
И
Л

3. Докажите или опровергните следующие высказывания:

а) Существуют уравнения, множество решений которых пусто.

б) Всякое целое число является натуральным.

в) Сумма любых двух четных чисел есть число четное.

г) хотя бы одно натуральное число является решением уравнения

7 : х =2.

4. Выявите логическую структуру, определите значение истинности и постройте отрицания следующих высказываний:

а) Некоторые нечетные числа делятся на 5.

б) Хотя бы одно из чисел первого десятка составное.

в) Произведение двух любых последовательных натуральных чисел составное.

5. Предложения А(х) и В(х) заданы на множестве натуральных чисел. Следует ли из предложения А(х) предложение В(х), если В(х) - ²Число х - четное², и

а) А(х) - ²Число х делится на 6²;

б) А(х) - ²Число х делится на 7²;

в) А(х) - ²число х делится на 2² ?

6.Установите, находятся ли данные пары предложений в отношении следования:

а) Треугольник АВС – равносторонний.

Треугольник АВС – равнобедренный.

б) Четырехугольник АВСD – квадрат.

Четырехугольник АВСD – ромб.

в) х делится на 3 и х делится на 6.

г) а > 2 и a > 5.

7. Среди следующих предложений установите истинные; ответы обоснуйте:

а) Если студент А сдаст все экзамены в сессию без троек, то он будет получать стипендию.

б) Число 15а натуральное, следовательно, а - натуральное число.

в) Если в четырехугольнике все углы прямые, то этот четырехугольник - прямоугольник.

г) Если в четырехугольнике диагонали равны, то это четырехугольник - прямоугольник.

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

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

8. Для ложных высказываний из задания 7 постройте отрицания различными способами.

9. Вставьте слова ²и² либо ²или² так, чтобы следующие высказывания были истинными:

а) а*b = 0 Û a = 0 ... b = 0;

б) a*b ¹ 0 Û a ¹ 0 ... b ¹ 0;

в) xÎ A Ç B Û x Î A ... x Î B;

г) x Ï A Ç B Û x Ï A ... x Ï B

10. С помощью таблиц истинности найти значение формулы:

а) A= ;

б) B=( ) .

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

1) Когда отец А смотрит передачу, то мать В делает то же;

2) Дочери Д₂ и Д₃ обе или одна из них смотрят передачу;

3) Из двух членов семьи – мать В и дочь Д₁ – смотрит передачу одна и только одна;

4) Дочери Д₁ и Д₂ или обе смотрят или обе не смотрят;

5) Если дочь Д₃ смотрит передачу, то отец А и дочь Д₂ делают то же.

Кто из членов семьи в этот вечер смотрит телевизор.

12. Приведите примеры таких значений а, для которых данное высказывание истинно:

а)

б)

13. Пусть высказывательная форма Q(x): “х делится на у ” определена на множестве N´N. Покажите, что высказывания и имеют различные логические значения.

14. Решите задачу: В городе совершено преступление. Подозреваемые: Джонс, Смит и Браун. Один из них – уважаемый старик, другой – мошенник, а третий – мелкий чиновник. Результаты допроса:

Браун: «Я совершил это, Джонс не виноват»;

Джонс: «Браун не виноват, преступление совершил Смит»;

Смит: «Я не виноват, виноват Браун»

Кто есть кто и кто преступник, если известно, что старик сказал правду, мошенник оба раза соврал, а чиновник один раз солгал и один раз сказал правду, а преступник один.

15. Даны высказывательные формы Р(х): “x² + x + 1 > 0” и Q(x):“x² – 4x + 3 = 0”, определенные на R. Установите, какие из следующих высказываний истинны, а какие ложны:

а)

б)

в)

г)

Задание для самостоятельной работы.

I. Повторите теоретический материал по всем изученным темам.

II. Решите задачи:

1. Сформулируйте отрицания следующих высказываний:

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

б) хотя бы на одном курсе есть хотя бы один отличник;

в) хотя бы на одном курсе все студенты отличники.

2. Докажите или опровергните следующие утверждения:

а) разность любых двух натуральных чисел есть число натуральное;

б) сумма любых трех последовательных чисел кратна трем;

в) в некоторых параллелограммах диагонали не равны;

г) среди чисел 12, 15, 17, 27, 212 найдется хотя бы одно, кратное 7;

д) любое действительное число является решением уравнения

2(х-3) = 2х - 6.

3. Пусть Р(х) : ²треугольник х равносторонний², Q(x): ² треугольник х равнобедренный², R(x): ²треугольник х прямоугольный². Сформулируйте следующие высказывания и установите их значения истинности:

а) ("х) Р(х); б) ($х) Р(х); в) ($х) Р(х) Ù R(x);

г) ($х) R(x) Ù Q(x).

4. С помощью таблиц истинности найти значение формулы:

C= .

5. На судебном процессе адвокат сделал следующее заявление: “Если Джонс – убийца, то ему известно время смерти и чем был убит Смит. Поэтому, если Джонс не знает, когда умер Смит, или не знает, чем Смита убили, то он не убийца”. Прав ли адвокат?

Занятие 6.

Контрольная работа.

Примерные варианты контрольной работы.

Вариант 1.

Задача 1. Известно, что Х - множество двузначных натуральных чисел, Е - множество четных натуральных чисел, Y - множество натуральных чисел, кратных 4. Изобразите данные множества при помощи кругов Эйлера и выделите штриховкой множество: С = Х Ç (N \ Y) ÈE. Каковы характеристические свойства элементов множества С?

Задача 2. На множестве Х = {6, 7, 8, 9, 10, 11, 12, 13} задано отношение “иметь один и тот же остаток при делении на 3”. Постройте граф отношения. Какими свойствами обладает данное отношение?

Задача 3. Составьте таблицу истинности для высказывания .

Задача 4. Сформулируйте отрицания высказываний и установите, что истинно - само высказывание или его отрицание:

а) все прямоугольники имеют центр симметрии;

б) некоторые двузначные числа делятся на 11 и на 13.

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

а) Боярышник не является деревом. Все деревья имеют ствол. Боярышник не имеет ствола.

б) Все целые числа рациональные. Все натуральные числа рациональные. Все натуральные числа целые.

Вариант 2.

Задача 1. А - множество натуральных чисел, кратных 7, В - множество натуральных чисел, кратных 3, С - множество четных натуральных чисел. Изобразите с помощью кругов Эйлера множество С È В \ А и укажите характеристическое свойство его элементов.

Задача 2. На множестве Х = {0, 3, 6, 9, 12, 15, 18} задано отношение “x больше y в три раза”. Изобразите граф и выясните свойства данного отношения.

Задача 3. Составьте таблицу истинности для высказывания .

а) диагонали любого ромба не равны между собой;

б) существует натуральное число n, для которого n > 3 и n + 4 = 6.

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

а) В четырехугольнике ABCD все углы прямые. Четырехугольник ABCD - прямоугольник. Если в четырехугольнике все углы прямые, то он является прямоугольником.

б) Число 17 - нечетное. Если число делится на 2, то оно четное.

Число 17 не делится на 2.

Занятие 7.

Элементы комбинаторики.

Контрольные вопросы.

1. Как найти число элементов в объединении двух конечных множеств, если множества

а) не пересекаются;

б) имеют непустое пересечение?

2. Сформулируйте комбинаторное правило суммы на теоретико-множественном и на комбинаторном языке.

3. Как найти число элементов в декартовом произведении двух конечных множеств?

4. Сформулируйте комбинаторное правило произведения.

5. Дайте определение размещения с повторениями (без повторений).Приведите примеры размещений.

6. Приведите формулы для вычисления общего числа размещений (с повторениями и без повторений) из m элементов по k элементов.

7. Что такое перестановки из m элементов? Как найти общее число перестановок? Приведите примеры.

8. Дайте определение сочетания из m элементов по k элементов. Приведите примеры сочетаний. По какой формуле можно найти общее число сочетаний без повторений из m элементов по k элементов?

Упражнения.

1. На тарелке 8 яблок и 6 груш. Сколькими способами можно выбрать один фрукт? 2 разных фрукта?

2. В классе 40 человек. Из них 26 человек играют в баскетбол, 25 занимаются плаванием, 27-лыжами. При этом одновременно плаванием и лыжами занимаются 18 человек, плаванием и баскетболом -15, баскетболом и лыжами- 16. Один освобожден от физкультурных занятий. Сколько человек занимается только одним видом спорта?

3. Из 50 студентов 20 знают немецкий язык, 15-английский. Каким может быть число студентов, знающих оба языка? Хотя бы один язык?

4. Из 32 школьников 12 занимаются в волейбольной секции, 15 – в баскетбольной, 8 человек занимаются в обеих секциях. Сколько школьников не занимаются ни в волейбольной, ни в баскетбольной секции?

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

6. Даны 40 чисел. Из них 10 чисел кратны 3, 15 чисел кратны 2, 20 чисел не кратны ни 2, ни 3. Сколько чисел, кратных 6, среди данных 40 чисел?

7. В классе 30 учащихся. Кружок по математике посещают 12 учащихся, по физике – 11 учащихся, по химии – 13 учащихся, по математике и физике – 4 ученика, по физике и химии – 5 учеников, по химии и математике – 7 учеников. Все три кружка посещают трое учащихся. Сколько учеников не посещают ни одного кружка?

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

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

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

11. Сколько шестизначных чисел, не кратных 5, можно составить из чисел 1, 2, 4, 5, 6, чтобы цифры в записи числа не повторялись?

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

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

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

15. Имеется шесть цифр: 0, 1, 2, 3, 4, 5. Сколько четырехзначных чисел из них можно составить, чтобы:

- число было четным;

- число было нечетным и не делилось на 5;

- в записи числа не было единиц;

- сумма крайних цифр равнялась трем?

16. Коротышки, проживающие в Цветочном городе, решили провести выборы городского начальства: мэра, вице-мэра, казначея и полицмейстера. Договорились, что каждый коротышка может претендовать на любой пост, но может быть выбран только на один пост. Сколькими способами можно выбрать городское начальство, если в городе 100 коротышек?

17. Сколько различных комбинаций букв можно получить при перестановке букв в слове:

- математика;

- ананас;

- бегемот?

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

19. 25 ребят, встретившись перед занятиями, обменялись рукопожатиями. Сколько было сделано рукопожатий?

20. Сколько существует различных четырехзначных чисел с неповторяющимися цифрами?

21. В спортшколе 10 сильных лыжников и 8 сильных лыжниц. Сколькими способами можно сформировать команду из 4 лыжников и 3 лыжниц?

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

23. В части служат 20 солдат, 2 лейтенанта, 3 мл. лейтенанта, 1 майор. Сколькими способами можно сформировать караул из 4 солдат и 2 офицеров?

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

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

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

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

28. Сколько имеется трехзначных чисел, в запись которых входит ровно одна цифра 5?

29. Сколько существует шестизначных чисел, в записи которых есть хотя бы одна четная цифра? ( посчитать числа, у которых все цифры нечетные).

30. Каких чисел больше среди первого миллиона: в записи которых есть цифра 7 или в записи которых ее нет?

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

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

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

34. Сколько четырехзначных чисел можно составить из цифр 1 и 2?

35. 22. Найти значение: .

36. Вычислите: C ; C .

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

38. Сколькими способами можно выбрать три ленты различных цветов из шести лент различных цветов?

Задание для самостоятельной работы.

I. Повторите теоретический материал по теме ²Элементы комбинаторики.²

II. Попробуйте ответить на контрольные вопросы к занятию № 8. Заполните следующую таблицу:

Виды комбинаций:	Формула
на комбинаторном языке	на теоретико-множественном языке
Размещения с повторениями из m элементов по k элементов	Кортежи длины k с повторяющимися элементами, взятыми из множества, в котором m элементов
Размещения без повторений из m элементов по k элементов
Перестановки без повторений из m элементов
Сочетания без повторений из m элементов по k элементов

III. Решите задачи:

1. Из 100 человек английский язык изучают 28, немецкий - 30, французский - 42, английский и немецкий – 8, английский и французский – 10, немецкий и французский – 5. Все три языка изучают 3 студента. Сколько студентов изучает только один язык? Сколько студентов не изучает ни одного языка?

2. На уроке литературы учитель решил проверить, кто из 40 учеников класса читал книги А, В и С. Результаты опроса оказались таковы: книгу А читали 25 учащихся, книгу В – 22, книгу С – также 22. Книгу А или В читали 33 ученика, А или С – 32, С или В – 31; все три книги прочли 10 учащихся. Сколько учеников прочитали только по одной книге? Сколько учащихся не читали ни одной из этих трех книг?

3. Найти число автомобильных номеров (номер состоит из трех букв и трех цифр).

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

5. Студенту необходимо сдать 4 экзамена за 8 дней. Сколькими способами он может это сделать?

6. Из цифр 1, 2, 3, 5 составить все возможные четырехзначные числа, чтобы цифры в записи числа не повторялись. Сколько их получилось?

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

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

9. Из 7 девушек и 8 юношей надо выбрать

· Четыре пары для танца.

· 4 девушек и 4 юношей для общего танца.

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

· Последней у всех чисел была цифра 4;

· Запись каждого из них начиналась с 23?

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

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

Занятие 8.