Тема: Теория множеств. Элементы теории нечетких множеств. Нечеткие алгоритмы.
№ варианта
1. Докажите тождества, используя метод взаимного включения и диаграммы Эйлера-Венна
2. , , , . Изобразите , графически. Найдите матрицу . Проверьте с помощью матрицы, является ли отношение рефлексивным, симметричны, антисимметричным, транзитивным? К какому классу отношений оно относится?
3. Найдите область определения, область значений отношения P. Является ли отношение P рефлексивным, антирефлексивным, симметричным, антисимметричным, не симметричным, транзитивным? К какому классу отношений оно относится? Обоснуйте ответ.
1.
;
2.
;
3.
;
4.
;
5.
;
6.
;
7.
;
8.
;
9.
;
10.
;
Тема: Комбинаторика
4. Решить задачи.
№ Варианта
1.
В комнате 10 лампочек. Сколько всего может быть разных способов освещения комнаты, при котором горит ровно 5 лампочек? Сколько всего может быть различных способов освещения комнаты?
На одной из боковых сторон треугольника взято n точек, на другой – m точек. Каждая вершина при основании треугольника соединена прямыми с точками, взятыми на противоположной стороне. Сколько точек пересечения этих прямых образуется внутри треугольника? На сколько частей делят треугольник эти прямые?
Ювелиру принесли пять одинаковых изумрудов, шесть одинаковых рубинов и семь одинаковых сапфиров. Сколько различных браслетов (из всех 18 камней) может сделать ювелир? Сколькими способами он может из этих камней выбрать три камня для кольца?
2.
Городской совет состоит из мэра и шести старейшин. Сколько различных комиссий из четырех членов можно сформировать из членов городского совета, если мэр входит в каждую комиссию? А если мэр города не входит ни в одну комиссию?
Сколькими способами шесть человек могут выбрать из шести перчаток по правой и левой перчатке так, чтобы ни один из них не получил пары?
Сколько различных десятизначных чисел можно написать, пользуясь тремя цифрами 1, 2, 3, если цифра 3 применяется в каждом числе ровно два раза? Сколько из этих чисел делится на 9?
3.
Сколькими способами можно выбрать 12 человек из 17, если данные двое из этих 17 не могут быть выбраны вместе?
В посольстве готовятся к приему. Сколькими способами можно посадить рядом троих англичан, троих немцев и троих французов так, чтобы никакие три соотечественника не сидели рядом?
У мамы 2 яблока, 3 груши и 4 апельсина. Каждый день в течении девяти дней подряд она выдает Сереже по одному фрукту. Сколькими способами это можно сделать?
4.
Сколько имеется четырехзначных чисел, у которых каждая следующая цифра больше предыдущей? А у которых каждая следующая цифра меньше предыдущей?
Сережа утверждает, что число трехбуквенных слов, которые можно составить из букв, составляющих слово ГИПОТЕНУЗА, равно числу всех возможных перестановок букв, составляющих слово ПРИЗМА. Прав ли Сережа?
На билетах банка России стоит серийный номер из двух букв русского алфавита и семи цифр. Сколько купюр одного достоинства может быть напечатано?
5.
У мамы два одинаковых яблока и три одинаковых груши. Каждый день в течении и пяти дней подряд она выдает Сереже по одному фрукту. Сколькими способами это может быть сделано?
В железнодорожном вагоне имеется 5 мест расположенных по ходу поезда и 5 мест – против хода поезда. Сколькими способами можно посадить в вагон 10 пассажиров, если 4 желают сидеть лицом по ходу поезда, а трое – лицом против хода поезда, остальным безразлично как сидеть?
Трое юношей и две девушки выбирают место работы. В городе есть 3 завода, где требуются рабочие в литейные цеха (только мужчины), 2 ткацкие фабрики (только женщины) и 2 фабрики, где требуются и мужчины и женщины. Сколькими способами они могут распределиться между этими предприятиями?
6.
Скольким различными способами можно разделить 25 одинаковых монет между четырьмя школьниками? (Способы считаются различными, если при их использовании хотя бы один из школьников получает разные суммы денег).
Сколькими способами можно посадить за круглый стол 5 мужчин и 5 женщин так, чтобы никакие два лица одного пола не сидели рядом?
В селении проживают 2000 жителей. Доказать, что по крайней мере двое из них имеют одинаковые инициалы.
7.
В железнодорожном вагоне десять мест расположены по ходу поезда и десять мест – против хода поезда. Сколькими способами можно посадить в вагон восемь пассажиров, если двое отказываются сидеть лицом по ходу поезда, а трое – лицом против хода поезда?
Укротитель хищников хочет вывести на арену 5 львов и четыре тигра, при этом нельзя, чтобы 2 тигра шли друг за другом. Сколькими способами он может расположить зверей?
В n ичной системе счисления используется n цифр. Сколько в этой системе натуральных чисел, записываемых ровно k знаками?
8.
В классе 35 учащихся из них 15 посещают факультатив по статистике, 11 – по логике и 10 – по комбинаторике. 4 учащихся не посещают ни один из факультативов. Сколько учащихся посещают все факультативы.
Сколькими способами можно переставлять буквы слова ЮПИТЕР так чтобы гласные шли в алфавитном порядке?
Сережа хочет отгадать какие пять монет держит в руке Таня. Она располагает достаточным количеством монет достоинством в 1, 5, 10, 50 коп. и 1 р. и 2 р. Сколько может быть дано различных неверных ответов?
9.
Если повернуть лист белой бумаги на 180°, то цифры 0, 1, 8 не изменяются, цифры 6 и 9 переходят друг в друга, а остальные цифры теряют смысл. Сколько существует семизначных чисел, величина которых не изменяется при повороте листа бумаги на 180°?
На собрании акционеров должны выступить пять человек (А, Б, В, Г, Д). Сколькими способами можно расположить этих акционеров в списке ораторов, если Б не должен выступать до выступления А? Если А не должен выступать непосредственно перед Б?
В кондитерском магазине продаются четыре сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?
10.
У англичан принято давать детям несколько имен. Сколькими способами можно назвать ребенка, если общее число имен равно 300, а ему дают не более трех имен?
Сколькими способами 8 человек могут встать в очередь в кассе?
Сколькими способами 12 одинаковых монет достоинством 1 р. можно разложить по пяти различным пакетам, если ни один из пакетов не должен быть пустым?
Тема: Логические исчисления
5. Докажите тождество, воспользовавшись законами алгебры логики. Представьте одно из выражений в базисе элементарных функций:
y1
y2
y3
y4
y5
y6
y7
y8
y9
y10
y11
a
В наборе номеров базисных функций должны фигурировать цифры вашего варианта. Например, для варианта 1 могут быть взяты y1, y11, y10, недостающие функции отбираются на основе теоремы Поста о полноте.
№ варианта
Задачи
1.
6. В таблице заданы номера наборов аргументов (в лексикографическом порядке), на которых логическая функция принимает значение равное единице. Запишите эту функцию в СДНФ, СКНФ, СПНФ. Произведите ее минимизацию методом Квайна и методом Карно.
№ Вар.
Номера конституент
-
-
-
№ Варианта
7. Каждую клаузу доказать следующими методами: Квайна, редукции, аксиоматическим, натурального исчисления, резолюций. По вашему выбору для двух из трех клауз составьте легенды.
8. Привести формулу логики предикатов к пренексной нормальной форме. Является ли формула на множестве M={1,2}: 1) выполнимой, 2) опровержимой, 3) общезначимой, 4) невыполнимой? Вычислить значение истинности формулы на множестве М со следующими предикатами:
x
Q(x,y)
P(x)
R(x)
8.1.
8.2.
8.3.
8.4.
8.5.
8.6.
8.7.
8.8.
8.9.
8.10.
9. Установить истинность логического выражения двумя методами: 1) по определению кванторов и 2) методом конкретизации.
9.1. ,
9.2. ,
9.3. ,
9.4. ,
9.5. ,
9.6. ,
9.7. ,
9.8. ,
9.9. ,
9.10. ,
10. Доказать истинность методом резолюций:
10.1.
10.2.
10.3.
10.4.
10.5.
10.6.
10.7.
10.8.
10.9.
10.10.
11. Для приведенной легенды запишите с использованием 4-6 различных букв клаузу, отвечающую контексту легенды, для чего сформулируйте необходимые посылки и два следствия: одно истинное и одно ложное. Проверить оба заключения на логическое следование из заданных посылок (любым методом).
11.1. Если в цепи будет большой перепад напряжения, то сгорит предохранитель, что повлечет за собой необходимость его замены. При целом предохранителе телевизор, конечно, будет работать, но только- если он включен в сеть питания. Если телевизор работает нормально, то я увижу сегодняшние «Новости». Итак, я смотрю телевизионные «Новости» при условии отсутствия перепада напряжения и подключения телевизора к сети питания.
11.2. Современный футбол – это надежная защита, хорошая скорость, напористая атака и убедительная результативность. Матвеев мне результативность обеспечит, но голы он забивает только по вдохновению, когда складывается игра. Без Федотова такой игры не получится. Он видит поле, чувствует, где надо находиться, но бегать не может. Скорость команде сообщит Комаров, хотя он может развалить всю защиту. Попробовать Петрова в обороне, но в паре с Матвеевым он не играет. Квасов умеет блокировать бомбардиров противника, но левой у него не получается. Надо ставить Земерова, чтобы левый край прикрыл. Однако Земеров в последнее время точный пас отдать не может. Ну нет команды! Завтра встречу точно проиграем.
11.3. Мотоцикл я сначала не заметил, так как его заслонил бензовоз, а «Волга» вывернула из-за угла, когда «Жигули» были уже вблизи светофора. «Иномарка» проскочила на красный свет и явилась, как мне кажется, причиной всей этой аварии. Из-за нее «Волга» резко затормозила, и мотоцикл оказался на асфальте. «Жигули», чтобы не задавить мотоциклиста, свернули на тротуар, а бензовоз в это время врезался в «Волгу». Если бы не было мотоцикла, то опасной ситуации тоже могло и не быть. Хотя виноват и водитель «Волги», поскольку он явно превысил скорость.
11.4. Увеличение денег в обращении влечет за собой инфляцию. Но рост денежной массы происходит по двум причинам: из-за денежной эмиссии или снижения товарооборота. Снижение товарооборота приводит к безработице и спаду производства. Из-за инфляции падает курс денежной единицы. Рекомендации экономиста Иванова: увеличить денежную эмиссию и поднять производство, тогда избежим безработицы и курс денежной единицы останется неизменным.
11.5. «Я вижу, у Вас поднялось давление». – «Это последствие рыбалки, доктор». – «Рыбалка, напротив, должна успокаивать и укреплять здоровье». – «Верно, доктор, но я переволновался, так как ловил рыбу в запрещенном месте». –«Ай-ай-ай! Зачем же Вы на это пошли?» – «Там, где разрешено, доктор, рыбы нет». – «В таком случае рыбы много в магазине. Я же Вам прописал отдых на свежем воздухе». – «Хорошо, доктор, тогда завтра я пойду охотиться». – «Только, пожалуйста, голубчик, не стреляйте в зоопарке».
11.6. Если усложнить схему устройства, то возрастет его производительность, а если использовать новую элементную базу, то увеличится период эксплуатации. Устройство начнут хорошо раскупать только при одновременном росте его производительности и периода эксплуатации. Но устройство не пользуется спросом.
11.7. Преступник изготовит партию фальшивых денег, если у него имеются соответствующие материалы и работает станок. Эти два условия, к сожалению, выполняются. Однако фальшивые деньги не появятся, если хорошо работает милиция. Милиция же работает хорошо тогда и только тогда, когда каждый милиционер получает высокую зарплату. Увы, пока такой зарплаты нет, но есть высокая сознательность всех работников милиции.
11.8. Уменьшение температуры приводит к снижению давления и уменьшению объема. Увеличение объема приводит к росту скорости потока. Повышение давления приводит к падению уровня, если при этом уменьшать температуру. Снижение скорости приводит к уменьшению давления или росту температуры. Технолог Иванов рассудил так: «Мне надо повысить давление при одновременном снижении скорости потока, поэтому я должен увеличить объем и температуру».
11.9. Сегодня посмотрю футбол, если трамвай не задержится. Трамвай не опоздал, но случилась другая беда: у меня не оказалось денег на билет. Рискну доехать «зайцем». В салоне оказался контролер, и я лихорадочно стал рыться по карманам. К моему счастью, нашелся один неиспользованный трамвайный талон. До компостера я добрался вовремя, хотя футбольный матч я гак и не увидел; вместе с деньгами я дома оставил и билет на матч.
11.10. «Хочешь яблоко?» – «Яблоки я не ем после рыбы, а рыбу я не ем после борща. Борщ я сегодня не ел, но съел немного горохового супа. После него я съел кусочек жареного хека. Если я ем гороховый суп, то в этот день уже не буду отказываться от яблок, но при условии, что к столу не подавали салат. Итак, давай сюда яблоко».
Тема: Графы
№ Варианта
12. Даны графы G1 и G2. Задайте их структурами смежности, матрицами смежности, матрицами инцидентности и списками ребер. Найдите , , , и их матрицы смежности и инцидентности.
14.
14.1. Постройте матрицу расстояний.
14.2. Найдите радиус, диаметр, центр графа.
14.3. Является ли граф Эйлеровым? Если да, то постройте эйлеров цикл, используя алгоритм Флери.
14.4. Является ли граф планарным? Если да, то постройте его плоскую реализацию.
14.5. Постройте остов методами поиска в ширину и в глубину.
14.6. Найдите минимальную правильную раскраску вершин и ребер графа
, 
, 
, 
. Изобразите 
, 
графически. Найдите матрицу 
. Проверьте с помощью матрицы, является ли отношение 
; 
; 
; 
; 
; 
; 
; 
; 
; 
; 
,
,
,
,
,
,
,
,
,
, 
, 
, 
и их матрицы смежности и инцидентности.
G1 
G2
G1 
G2
G1 
G2
G1 
G2
G1 
G2
G1 
G2
G1 
G2
G1 
G2
G1 
G2
G1 
G2
