Сборник задач по дискретке
.pdf14. 2) |
A B , A – число делится на 3; B – число делится на 6; |
||
3) |
A :B, A – произведение чисел равно нулю, B – один из сомно- |
||
жителей равен нулю. |
|
|
|
15. 1, 3 – «тогда и только тогда; |
2, 4, 5 – «тогда»; в общем случае |
||
выражение « A тогда, когда B » преобразуется к виду «Из B следует A». |
|||
16. Существуют выводы – 2, 3, 6, 8, 9. |
|||
17. 1) |
A É (B É C), A, C ; |
2) A; |
3) A É (B É C), A, B ; |
5) (A ɬ¬ B) É (¬ B ɬ A), A ɬ¬B, ¬B ; |
|||
4), 6), 7) доказательства; |
8) A B, C ; 9) A B . |
||
20. Ложно – 1, 3, 4, 5а, 9, 11.
21. Необходимо вынуть шар из ящика, на котором написано «Белый и черный». Тогда возможны следующие варианты:
а) если мы вынули белый шар, то в этом ящике оба шара белые и, значит, в ящике с надписью «Белый и белый» находятся два черных шара, а в ящике с надписью «Черный и черный» – черный и белый шары;
б) если вынули черный шар, то здесь оба шара черные. В ящике с надписью «Белый и белый» – черный и белый шары, а в оставшемся ящике оба шара – белые.
22. Преступник третий. Указание: рассмотреть, какие ответы дадут первый, второй и третий в каждом из трех возможных случаев.
23. Ольга первая, Маша вторая, Полина третья, Наташа четвертая.
24. Экзамены на сессии стоят в следующем порядке: математический анализ, история, философия, геометрия, психология.
25. Места распределились следующим образом: первый – Григорий, далее Виктор, Антон, Евгений, Борис, Денис.
26. Варя была в красном, Клава – в белом, Аня – в синем. 27. Преступник на Таганке.
28. Кражу совершил Лось.
29. Преступник был на черном «Бьюике».
30. Смит – известный мошенник, Джон – уважаемый в городе старик, Браун – малоизвестный чиновник.
Обозначим буквами Б , Д и C высказывания: «Браун виновен», «Джонс виновен», «Смит виновен». Тогда утверждения, высказанные
81
задержанными, можно записать в виде конъюнкций: Б Д , Б С , Б С , из которых по условию задачи две ложны, а одна истинна. Следова-
тельно, должна быть истинной формула |
L = Б Д |
|
|
С Б С . Таблица |
|||||||||||||||||||
Б |
|||||||||||||||||||||||
истинности этой формулы имеет вид: |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
Б |
Д |
С |
Б |
|
|
|
|
С |
|
|
|
|
|
|
|
|
|
|
|
|
||
Д |
|
|
Б |
Б С |
|
L = Б |
Д |
|
Б |
С Б С |
|
|
|
||||||||||
|
0 |
0 |
0 |
0 |
|
0 |
0 |
|
0 |
|
|
|
|
|
|
1 |
|
||||||
|
0 |
0 |
1 |
0 |
|
1 |
0 |
|
1 |
|
|
|
|
|
|
2 |
|
||||||
|
0 |
1 |
0 |
1 |
|
0 |
0 |
|
1 |
|
|
|
|
|
|
3 |
|
||||||
|
0 |
1 |
1 |
1 |
|
1 |
0 |
|
1 |
|
|
|
|
|
|
4 |
|
||||||
|
1 |
0 |
0 |
0 |
|
0 |
1 |
|
1 |
|
|
|
|
|
|
5 |
|
||||||
|
1 |
0 |
1 |
0 |
|
0 |
0 |
|
0 |
|
|
|
|
|
|
6 |
|
||||||
|
1 |
1 |
0 |
0 |
|
0 |
1 |
|
1 |
|
|
|
|
|
|
7 |
|
||||||
|
1 |
1 |
1 |
0 |
|
0 |
0 |
|
0 |
|
|
|
|
|
|
8 |
|
||||||
Отсюда видно, что формула L истинна в пяти из восьми занумерован- ных случаев. Случай 4 не подходит, так как здесь истинны сразу две конъ- юнкции Б Д и Б С . В случаях 2, 3 и 6 оказываются истинными по два
высказывания Б и Д, Б и С, Д и С соответственно, что также противоречит условию задачи. Следовательно, справедлив случай 7, т.е. преступник – Смит. Он – известный мошенник, и оба его высказывания ложны: Б С = 0.
При этом высказывания Б и Д ложны. Значит, истинна пара высказы- ваний Джона, а у Брауна первое высказывание ложно, а второе истинно.
31. 1) Показания совместны.
2)Показания Смита следуют из показаний Брауна.
3)Браун и Смит.
4)Виновен Джонс.
5)Виновны Браун и Смит.
30. Миша – сын десантника – стал моряком, Гриша – сын ракетчика – летчиком, Игорь – сын моряка – ракетчиком.
33. Андрей – банкир, Борис – врач, Григорий – метрдотель, Дмитрий – актер, Виктор – учитель.
34. Варенье ел Вася.
35. У Ивановых 2 кролика, 3 белки, 1 хомяк, 4 ежа;
уПетровых 1 кролик, 4 белки, 2 хомяка, 3 ежа;
уСидоровых – 4 кролика, 2 белки, 3 хомяка, 1 еж;
уКузнецовых – 3 кролика, 1 белка, 4 хомяка и 2 ежа.
82
Исчисление предикатов
2. В данной модели
–истинные высказывания: xQ(x,b), xQ (x,b) , xQ (a, x) , xQ (b, x) ,x yQ(x, y), y xQ (x, y), x yQ(x, y) , y xQ (x, y) ;
–ложные высказывания: xQ(x,a) , xQ (x,a) , xQ(a, x) , xQ(b, x),x yQ(x, y), y xQ (x, y) , y xQ (x, y) , x yQ(x, y) .
5. В следующей таблице для одноместных предикатов используются обозначения:
ТИФ – тождественно истинная формула (тавтология, неопровержимая), ТЛФ – тождественно ложная формула (невыполнимая), УИФ – условно истинная формула (выполнимая, опровержимая).
|
1.а |
1.б |
2.а |
2.б |
2.в |
3.а |
3.б |
3.в |
5.а |
5.б |
5.в |
6.а |
6.б |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xQ(x, y) |
|
|
|
|
|
|
Т |
|
|
|
|
|
|
|
У |
У |
Т |
Т |
Т |
У |
Л |
Т |
Т |
Т |
Т |
У |
У |
||
|
Ф |
|||||||||||||
|
И |
И |
И |
Л |
Л |
И |
Л |
Л |
Л |
Л |
И |
И |
||
|
У |
|||||||||||||
yQ(x, y) |
Ф |
Ф |
Ф |
Ф |
Ф |
Ф |
Ф |
Ф |
Ф |
Ф |
Ф |
Ф |
||
И |
||||||||||||||
|
|
|
|
|
|
|
Ф |
|
|
|
|
|
|
|
xQ (x, y) |
У |
У |
|
|
|
|
Т |
|
|
Т |
|
|
|
|
И |
И |
Т |
У |
У |
Т |
И |
У |
У |
И |
Т |
Т |
Т |
||
|
Ф |
Ф |
Ф |
Ф |
||||||||||
|
И |
И |
И |
И |
И |
И |
И |
И |
И |
|||||
|
Т |
Т |
У |
У |
||||||||||
yQ (x, y) |
Ф |
Ф |
Ф |
Ф |
Ф |
Ф |
Ф |
Ф |
Ф |
|||||
И |
И |
И |
И |
|||||||||||
|
Ф |
Ф |
|
|
|
|
Ф |
|
|
Ф |
|
|
|
|
x yQ(x, y) |
Л |
Л |
И |
Л |
Л |
Л |
Л |
Л |
Л |
Л |
Л |
Л |
Л |
|
y xQ(x, y) |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x yQ(x, y) |
И |
И |
И |
И |
И |
И |
И |
И |
И |
И |
И |
И |
И |
|
y xQ(x, y) |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y xQ(x, y) |
И |
И |
И |
Л |
Л |
И |
Л |
Л |
Л |
Л |
Л |
И |
И |
|
x yQ(x, y) |
И |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||
x yQ(x, y) |
И |
И |
И |
Л |
Л |
И |
И |
Л |
Л |
Л |
Л |
И |
И |
|
y xQ(x, y) |
Л |
Л |
И |
И |
||||||||||
|
|
|
|
|
|
|
|
|
83
14. Истинные: 1, 2, 3 и 8; |
выполнимые: 1 – 4, 6 – 9; |
|
опровержимые: 4 – 7 и 9; |
ложные: 5. |
|
15. Выполнимы все, кроме 4. |
|
|
16. Общезначимы все, кроме 5. |
|
|
18. 1) x x% y (A(x, y) B(x%, y)); |
3) x% z y (¬ A(x%, z) B(z, y)); |
|
2) x y y%(A(x, y) B(x, y%)); |
4) x x% y (¬ A(x, y) B(x%, y)). |
|
5)x% y x (¬ A(x%, y) ¬ B (x%) C (x, y));
6)x y z (A(x, y) ¬ B ( y, z) ¬ C ( y, z));
7)x z y (A(x, z) B (x, y) ¬ C (z)).
19. Противоречащими являются 3), 5), 6), остальные – противопо-
ложные. |
|
|
20. Общеутвердительные: 1, 2; |
частноутвердительные: 4, 9, 10; |
|
общеотрицательные: 3; |
частноотрицательные: 5, 6, 7, 8. |
|
21. 2 и 4. |
22. 1 и 4. |
|
23. Противоречат друг другу попарно 1 и 3, 2 и 4, 5 и 7, 6 и 8. |
||
24. Одновременно истинными могут быть суждения 1 и 3. |
||
25. Да, нет. |
26. Никакие. |
|
28. |
|
|
1)
2)
84
3)
4)
человек с высшим образованием
5)
6)
85
30. Правильные: 1, 3, 4, 5, 8, 10, 11, 12, 13, 15, 17.
31. Обратные: 1 и 4; противоположные: 4 и 6;
противоположные обратной: 1 и 6, 3 и 5. Верны: 1, 6.
32. 1) Обратная: если дискриминант квадратного уравнения положите- лен, то квадратное уравнение имеет два различных действительных корня.
Противоположная: если квадратное уравнение не имеет двух различ- ных действительных корней, то дискриминант этого квадратного уравнения не положителен.
Противоположная обратной: если дискриминант квадратного уравне- ния не положителен, то квадратное уравнение не имеет двух различных действительных корней.
Верны:
1)прямая, обратная, противоположная, противоположная обратной;
2)прямая, обратная, противоположная, противоположная обратной;
3)прямая, противоположная обратной;
4)прямая, противоположная обратной.
33. 1) I фигура, Darii; |
9) II фигура, eoo – непр.; |
||
2) |
I фигура, Barbara; |
10) |
II фигура, Cesare; |
3) |
III фигура, oio – непр.; |
11) |
IV фигура, Calemes; |
4) |
II фигура, aaa – непр.; |
12) |
II фигура, Baroco; |
5) |
IV фигура, Dimatis; |
13) |
I фигура, aee – непр.; |
6) |
I фигура, oaa – непр.; |
14) |
IV фигура, Bamalip; |
7) |
II фигура, Camestres; |
15) |
I фигура, Ferio. |
35. 1) – первое для второго;
2)– никакое;
3)– второе для первого;
4)– оба;
5)– первое для второго.
86
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1.Андерсон Дж. А. Дискретная математика и комбинаторика: пер. с англ. – М.: Издательский дом «Вильямс», 2004.
2.Белоусов А.И., Ткачев С.Б. Дискретная математика: учеб. для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2004.
3.Брадис В.М., Минковский В.Л., Харчева А.К. Ошибки в матема-
тических рассуждениях. М.: Гос. учеб.-пед. изд-во Министерства просве- щения РСФСР, 1959.
4.Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной ма- тематике. – М.: Наука, 1977.
5.Гохман А.В., Спивак М.А., Розен В.В. и др. Сборник задач по мате-
матической логике и алгебре множеств. – Саратов: Саратовский ун-т, 1969.
6.Депман И.Я. Первое знакомство с математической логикой. –
Л.: Знание, 1963.
7.Ивин А.А. Практическая логика: Задачи и упражнения – М.: Про- свещение, 1996.
8.Кондаков Н. И. Введение в логику. – М.: Наука, 1967.
9.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, матема- тической логике и теории алгоритмов. – М.: Физматлит, 1995.
10.Лихтарников Л.М., Сукачева Т.Г. Математическая логика: курс лекций. Задачник-практикум и решения. – СПб.: Изд-во «Лань», 1999.
11.Москинова Г.Н. Дискретная математика. Математика для мене- джеров в примерах и упражнениях: учеб. пособие. – М.: Логос, 2000.
12.Нефедов В.Н., Осипова В.А. Курс дискретной математики: учеб. пособие. – М.: Изд-во МАИ, 1992.
13.Никитин В.В. Сборник логических упражнений: пособие для учи- телей математики. – М.: Просвещение, 1970.
14.Рояк М.Э. Рояк С.Х. Основы дискретной математики: учеб. посо- бие. – Новосибирск: Изд-во НГТУ, 2003.
15.Шоломов Л.Ф. Основы теории дискретных логических и вычис- лительных устройств. – М.: Наука, 1980.
16.Яшин Б.Л. Задачи и упражнения по логике. – М.: Гуманит. изд. центр ВЛАДОС. – 1996.
87
Рояк Светлана Хаимовна Рояк Михаил Эммануилович
СБОРНИК ЗАДАЧ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
Редактор И.Л. Кескевич
Выпускающий редактор И.П. Брованова Дизайн обложки А.В. Ладыжская Компьютерная верстка С.Х. Рояк
Подписано в печать 27.03.2013. Формат 60 × 84 1/16. Бумага офсетная Тираж 200 экз. Уч.-изд. л. 5,11. Печ. л. 5,5. Изд. 26. Заказ № 544
Цена договорная
Отпечатано в типографии Новосибирского государственного технического университета
630073, г. Новосибирск, пр. К. Маркса, 20