Список практических заданий
1. Проиллюстрировать на примере предиката порядка, определённого в задаче 1, понятие истинного, ложного и переменного высказываний.
2. Записать предикатной формулой предложение, которое выражает для произвольных a,b,c N в модели N=(N;S,П,Е), называемой в логике предикатов арифметикой натуральных чисел, где N- множество натуральных чисел и S, П, Е- предикаты суммы, произведения, равенства соответственно, определённые в задаче 1:
а) коммутативность умножения;
б) ассоциативность сложения;
в) ассоциативность умножения;
г) дистрибутивность слева умножения относительно сложения;
д) дистрибутивность справа умножения относительно сложения;
е) транзитивность равенства.
3. Рассмотреть варианты навешивания кванторов на предикат Р(х), определенный на множестве натуральных чисел с нулем. Дать словесную формулировку исходных и полученных высказываний и определить их истинность, если:
4. Пусть Q(x,y)- предикат порядка х≤у, определенный на конечном множестве натуральных чисел M={0,1,2,3…9}. Рассмотреть различные варианты квантификации его переменных. Определить истинность полученных выражений.
5. Пусть предикат Р(х,у) задан на множестве М {a,b,c} таблицей.
Определить истинность следующих формул:
6. Пусть S(x,y,z) и П(x,y,z)- предикаты суммы и произведения, определенные:
а) на множестве Z всех целых чисел;
б) на множестве N0 натуральных чисел с нулем.
Какой смысл имеют формулы:
7. Рассмотреть варианты навешивания кванторов на предикат Р(х,у), описать в словесной форме полученные высказывания и определить их истинность, если:
1. Р(х,у), определенный на конечном множестве натуральных чисел , означает:
а) «х делит у»
б) «х имеет общий делитель с у»
в) «х,у делится на 3»
г)»х,у- четные числа»
2. Р(х,у), определенный на системе множеств β(U), означает:
а) «х является частью у»
б) «х пересекается с у»
3. Р(х,у), определенный на множестве людей, означает:
а) «х является родителем у»
б) «х живет в одном городе с у»
г) «х является сыном у»
8. Получить ПНФ предикатной формулы вида ;
Вопросы для обсуждения на форуме
1. Решение задач логики предикатов.
Список дополнительной литературы:
1. Колмогоров А.Н., Драгалин А.Г. Математическая логика. — М.: Едиториал УРСС, 2004. — 240 с.
2. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях \Г.И. Москинова. – М.: Логос. 2000. – 240с.
3. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1979. 272с.
Семинар №6. Комбинаторика
Цель семинара:
Закрепить пройденный теоретический материал, используя практические решения.
План занятия:
В данном семинаре рассматривается 2 темы, это комбинаторные конфигурации и разбиения, включения и исключения. На освоение практического материала выделяется 2 часа.
Задача 1.В кабину лифта девятиэтажного дома вошли 4 пассажира, каждый из которых может выйти на любом из 8 этажей. Сколько существует способов разгрузки лифта.
Решение.Обозначим через X множество пассажиров, через Y - множество этажей, на которых они могут выйти. Тогда каждая разгрузка лифта - это некоторое отображение f : X —> Y (каждому пассажиру поставлен в соответствие этаж, на котором он выходит при этой разгрузке). Следовательно число различных способов разгрузки лифта совпадает с числом различных отображений из множества X в множество Y, то есть равно |YX| = 84 = 4096.
Задача 2.В группе 25 человек. Сколько существует способов выбора из них делегации из трех человек для участия в профсоюзной конференции.
Решение.Ясно, что выбор делегации - это выбор 3-элементного подмножества из множества студентов группы. Поэтому число способов выбора равно = 25!/(3!∙22!)= 2300.
Задача 3. A = 10 {различных шоколадок}, B = 5 {различных пачек печенья}. Выбор “A или B” означает, что выбирается что-то одно и способов выбора в этом случае будет 15. Выбор “A и B” означает, что выбирается 1 шоколадка и 1 пачка печенья и различных вариантов для такого выбора будет 50.
Задача 4. Бросают 2 игральные кости. Сколькими способами они могут выпасть так, что на каждой кости выпадет четное число очков либо на каждой кости выпадет нечетное число очков.
Решение.
Пусть m – число возможностей для выпадения четного числа на одной кости, n – число возможностей для выпадения нечетного числа. Здесь m = n = 3. По правилу произведения количество выпадения четных чисел, как и нечетных, равно 9. По правилу суммы количество возможностей для выпадения двух четных и двух нечетных чисел будет 18.
Задача 5. Сколько существует способов, чтобы расположить на полке 10 различных книг.
Решение.
10!
Задача 6. Группа из 15 человек выиграла 3 различных книги. Сколькими способами можно распределить эти книги среди группы.
Решение.
Имеем = 15 ×14 ×13 = 2730.
Задача 7. Группа из 15 человек выиграла 3 одинаковых книги. Сколькими способами можно распределить эти книги.
Решение.
Задача 8. Кодовый замок состоит из четырех разрядов, в каждом разряде независимо от других могут быть выбраны цифры от 0 до 9. Сколько возможных комбинаций.
Решение.
Здесь n = 10, m = 4 и ответом будет 104.
Задача 9. Рассмотрим вектор длины m, каждая координата которого может принимать всего 2 значения: 0 или 1. Сколько будет таких векторов.
Решение.
Это есть выборка, объемом m из двух элементов.Ответ: 2m
Задача 10. Сколько различных слов можно получить, переставляя буквы в слове “математика”.
Решение.
Буква “а” входит 3 раза (k 1= 3), буква “м” – 2 раза (k2 = 2), “т” – 2 раза (k3 = 2), буквы “е”, ”к”, ”и” входят по одному разу, отсюда k3 = k4 = k5 = 1.
C10 (3, 2, , 2, 1, 1, 1) = =151200.
Задача 11. В кондитерской имеется 7 видов пирожных. Покупатель берет 4 пирожных. Сколькими способами он может это сделать (предполагается, что пирожных каждого вида ³ 4).
Решение.
Число способов будет
Задача 12. Пусть V = {a, b, c}. Объем выборки m = 2. Перечислить перестановки, размещения, сочетания, размещения с повторениями, сочетания с повторениями.
Решение.
1. Перестановки: {abc, bac, bca, acb, cab, cba}. P3=3!=6.
2. Размещения: {(ab), (bc), (ac), (ba), (cb), (ca)}.
3. Сочетания: {(ab), (ac), (bc)}.
4. Размещения с повторениями: {(ab), (bc), (ac), (ba), (cb), (ca), (aa), (bb), (cc)}. (3)= 32 = 9.
5. Сочетания с повторениями: {(ab), (bc), (ca), (aa), (bb), (cc)}.