Государственный комитет Российской Федерации
по высшему образованию
ГОСУДАРСТВЕННАЯ АКАДЕМИЯ УПРАВЛЕНИЯ
имени СЕРГО ОРДЖОНИКИДЗЕ
В. В. Годин, Золотарева Н. Л., Рыбалкина Н. В.
СБОРНИК ЗАДАЧ ПО КУРСУ
"МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ И МОДЕЛИРОВАНИЯ"
Москва - 1996
Государственный комитет Российской Федерации
по высшему образованию
ГОСУДАРСТВЕННАЯ АКАДЕМИЯ УПРАВЛЕНИЯ
имени СЕРГО ОРДЖОНИКИДЗЕ
Утверждаю
Первый проректор
В. В. Годин,
кандидат экономических наук, доцент
Н. Л. Золотарева,
кандидат экономических наук, доцент
Н. В. Рыбалкина,
кандидат экономических наук, доцент
СБОРНИК ЗАДАЧ ПО КУРСУ
"МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ И МОДЕЛИРОВАНИЯ"
для студентов специальности "Математические методы и исследование операций в экономике"
Москва - 1996
УДК [330.43+002] : 51
В. В. Годин, Золотарева Н. Л., Рыбалкина Н. В. Сборник задач по курсу “Математические основы информатики и моделирования: Учебное пособие/ ГАУ. М., 1996, 59.
В сборнике приводятся задачи по курсу "Математические основы информатики и моделирования", охватывающие некоторые разделы этой дисциплины для студентов, обучающихся по специальности "Исследование операций в экономике". Идеи отдельных задач, а также некоторые задачи целиком заимствованы из /1, 2/.
О т в е т с т в е н н ы й р е д а к т о р
Заведующий кафедрой экономической кибернетики,
доктор экономических наук, профессор
В.И.Дудорин
Р е ц е н з е н т ы:
Заместитель директора Института макроэкономических исследований (ИМЭИ)
при министерстве экономики России, доктор экономических наук
А.А.Водянов
Старший научный сотрудник Института проблем управления РАН, к.т.н.
Е.В.Умрихина
© Государственная академия управления имени Серго Орджоникидзе, 1996
Раздел 1. Исчисление высказываний.
Задача 1. 1
Запишите символически следующие сложные предложения, употребляя буквы для обозначения простых компонентов предложения (под простыми компонентами мы подразумеваем предложения, не содержащие связок), а также логические связки:
Идет дождь, или кто-то не выключил душ.
Если вечером будет туман, то Джон или останется дома, или должен будет взять такси.
Джон сядет, и он или Джордж будут ждать.
Джон сядет и будет ждать, или Джордж будет ждать.
Я поеду или на автобусе, или на такси.
Ни Север, ни Юг не победили в гражданской войне.
Хлеба уцелеют тогда и только тогда, когда будут вырыты ирригационные канавы; если хлеба не уцелеют, то фермеры обанкротятся и оставят фермы.
Если я устал или голоден, я не могу заниматься.
Если Джон встанет и пойдет в школу, он будет доволен, а если он не встанет, он не будет доволен.
Если мистер Джонс счастлив, то миссис Джонс несчастлива, и если мистер Джонс несчастлив, то миссис Джонс счастлива.
Я поеду на автобусе или на такси.
Или Сэм пойдет на вечеринку и Макс не пойдет на нее, или Сэм не пойдет на вечеринку и Алиса отлично проведет время.
Необходимое и достаточное условие счастья для студента Петрова состоит в том, чтобы выйти на сессию, сдать ее и поехать отдыхать на море.
Фиорелло ходит в кино только в том случае, когда там показывают комедию.
Необходимым условием сходимости последовательности S является ограниченность S.
Задача 1. 2
Для каждого из помещенных ниже высказываний определить, достаточно ли приведенных сведений, чтобы определить истинностное значение высказывания. Если достаточно, то указать это значение. Если недостаточно, то показать, что возможны и одно, и другое истинностные значения.
1. (P ® Q) ® R
и
2. P /\ (Q ® R)
и
3. P \/ (Q ® R)
и
4. ù(P \/ Q) ¬® ùP /\ ùQ
и
5. (P ® Q) ® (ùQ ® ùP)
и
6. (P /\ Q) ® (P \/ S)
и л
Задача 1. 3
Вставить пропущенные связки:
Если xy=0, то x= 0 [ ] y=0
Если x2-5x+6>0, то x>3 [ ] x<2
Если x2-5x+6<0, то x>2 [ ] x<3
Если x2+y2=0, то x=0 [ ] y=0
Если sin(x)*cos(x)=1, то sin(x)=1 [ ] cos(x)=1
Если sin(x)*cos(x)=0, то sin(x)=0 [ ] cos(x)=0
Если четырехугольник - ромб [ ] прямоугольник [ ] прямоугольник со взаимоперпендикулярными диагоналями, то он квадрат.
Если x>0 [ ] x<
[
] x>p
[ ] x<
, то tg(x)>0Если úxú>3, то x>3 [ ] x<3
Если úxú<3, то x<3 [ ] x>-3
Если неверно, что число кратно 2 и 3, то это число не кратно 2 [ ] не кратно 3.
Задача 1. 4
Составить таблицу истинности:
P ® (P ® Q)
P \/ Q ¨ Q \/ P
P ® ù (Q /\ P)
(P ® Q) ¬® ùP \/ Q
(P ® Q /\ R) \/ (ùP /\ Q)
P /\ Q ® (Q /\ ùQ ® R /\ Q)
(A ® B) ¬® (ùA \/ B)
(A ® B) \/ ùA
A ® (B /\ C)
A ® (B \/ C)
(A /\ B) ¬® (B /\ ùC)
(A /\ B) ¬® (C® (ùA \/ B))
Задача1. 5
Найти истинностные значения высказываний, если P=и, Q=л, R=л, S=и
P \/ Q \/ R
P \/ (Q \/ R)
R ® S /\ P
P ® (R ® S)
P ® R \/ S
P \/ R ¬® R /\ ùS
S ¬® P ® ( ùP \/ S)
Q /\ ùS® (P ¬® S)
R /\ S ® (P® ù Q \/ S)
(P \/ ùQ) \/ R ® (S /\ ùS)
Задача 1. 6
Если заданы исходно значения истинности некоторых высказываний, то что можно сказать о значениях более сложных
1. P ® Q = и ùP /\ Q ¬® P \/ Q?
2. P ¬® Q = и P ¬® Q? ùP ¬® Q?
3. P ¬® Q = л P ¬® Q? ùP ¬® Q?
Задача 1. 7
Установить, истинно или ложно высказывание
L \/ M ® (S ¬® G /\ ùR), если известно:
1. L /\ ùM = и, S=и, G /\ R = и
2. L /\ M = и, ùS=и, ùG /\ R = и
3. G ® R = и, R ® ùS =и, S=и, M=и
Задача 1. 8
1. Упростить высказывание ùA\/B\/C\/D, если известно, что высказывание (A ® B) ® (C \/ D) истинно.
2. Упростить высказывание (ùA\/B) /\ (C\/D), если известно, что высказывание (A ® B) ® (C \/ D) истинно.
Задача 1. 9
Является ли истинным высказывание?
1. ù(P \/ Q) ¬®ùP /\ ùQ /\ R, если R - истина
2. (C \/ D) ®(S \/ C /\ D), если S - истина
3. ùA \/ B \/ C \/ D, если (A®B) ®( ùC®D)-истина
4. (P®Q) /\ ( ùQ®ùP), если Q - истина
Задача 1. 10
Упростить выражение:
1. (A®B) ® ((B®ùC) ®( ùA®C))
2. (B®A)/\A/\(C® (A/\C))
3. (A/\B)¬®(C® (ùA \/ ùB))
4. (A®B)/\( ùB®ùA)
Задача 1. 11
Является ли формула тавтологией?
1. (P®Q) ®((Q®R) ®(P®R))
2. (A/\B)®(B\/(A/\C))
3. ((A®B)/\(B®C))®(A®C)
4. ((P/\Q)®(Q/\R))®(R/\P)
5. (A ¬® B) ¬® (A ® B) /\ (B ® A)
6. (A ¬® B) ¬® (ùA \/ B) /\ (ùB \/ A)
7. ù((A /\ B) \/ C) ¬® (ùA /\ ùB) /\ ùC
8. (ù(A /\ B) \/ ùC) ¬® (ùA \/ ùB) /\ ùC
9. A ® (B ® A)
10. (A /\ B) ® A
11. (A ® B) ® ((B ® C) ® (A® C))
12. ((A ® B) /\ B) /\ A
13. A /\ (ù(A \/ B))
14. ùA ® (A /\ B)
15. (A ® B) ¬® ù(A /\ ùB)
Задача 1. 12
Представить следующие высказывания в дизьюнктивной нормальной форме:
ù(P /\ ùS) ¬® ù(ùR ® ùP)
(F \/ù G) /\ F /\ (ùH \/ F /\ H)
((C \/ A \/ B) ® B) \/ (ùA /\ C)
ù(X /\ù Z) ¬® ù(ùX ® ùY)
X /\ Y ¬® ((C ® (ùX \/ Y))
((A ® B)\/( ùA /\ C))/\((A \/ B) ¬®(B/\C))
(X /\ Y) ¬® (ùY \/ X /\ Z)
F /\ G ¬® (H ® (ùF \/ ùG))
(X \/ ùY) /\ X /\ (ùZ \/ X /\ Z)
((P \/ Q \/ T) ® Q) \/ (ùP /\ T)
(A/\B) ¬®(C® (ùA\/B))
(A®B)\/( ùA/\C)
A¬® (B/\ùA)
Задача 1. 13
Представить следующие высказывания в коньюнктивной нормальной форме:
1. ((A ® B)\/(ùA /\ C))/\((A \/ B) ¬®B/\C))
2. (P \/ Q /\ S \/ P /\ S) ® (S \/ T /\ Q)
3. F /\ G ¬® (H ® (ùF \/ ùG))
4. (A \/ B /\ C \/ A /\ C) ® (C \/ D /\ B)
5. (P\/Q)®(S\/T)
6. ((D®E)/\(E®F)) ®(D®F)
7. (A/\B/\C)\/(D/\E)
8. (ùX/\ùY)\/( ùX/\Z)\/(Y/\Z)
Задача 1. 14
Доказать равносильность:
а. ((X /\ Y) /\ ùZ) \/ (X /\ Y) \/ (X /\ ùY) Û Y
б. (ù(ùX ®ùY) ® X) /\ (X ®ù (ùX ®ùY)) Û (X ® Y) /\ (Y ® X)/\ ùX
Задача 1. 15
Мы записали символически высказывание : "Если рабочие или администрация упорствуют, то забастовка будет урегулирована тогда и только тогда, когда правительство добьется судебного запрещения, но войска не будут посланы на завод" в следующем виде:
L \/ M®(S ¬® G /\ ùR).
Путем рассмотрения истиностных значений определить, истинно или ложно это высказывание при каждом из следующих предположений:
Рабочие упорствуют, а администрация нет, забастовка будет урегулирована, правительство добилось судебного запрещения, и войска посылаются на завод.
рабочие, и администрация упорствуют, забастовка не будет урегулирована, правительству не удалось добиться судебного запрещения, и войска посылаются на завод.
Задача 1. 16
Найти эквивалентные формулы, в которых "не" фигурирует только перед атомами
1. ù((P /\ùQ) \/ R \/ (S /\ ùP))
2. ù(P \/ ùQ ® (R /\ ù ùS) \/ Q)
3. ù(ù (P /\ Q)) ¬® P
Задача 1. 17
Преобразовать формулы, чтобы они содержали только указанные связки
1. "/\", "ù" (x ® ùy) ® (y \/ z)
2. "\/", "ù"
((x \/ y) /\ (ùx \/ù y)) ® (x ¬® y) /\ (ùx ¬® ùy)
3. "®", "ù" (x \/ y) \/ x
Задача 1. 18
Упростить высказывания:
1. (P /\ Q /\ ùR) \/ (P/\ ùQ /\ ùR) \/ ùP
2. (P \/ S ¬® ùQ)/\(R \/ Q)/\ ùS®((S ® R \/ Q) \/ P)
3. ù((P ® R)/\ S ¬® ùR \/ ù (R ® Q)/\(Q ® ùP)/\ P)
4. (P ® Q) /\ (ù(Q /\ R) \/ P) /\ ù (R /\ P)
Задача 1. 19
Доказать каждое утверждение о непротиворечивости множества посылок соответствующим распределением истинностных значений:
1. A ® ù (B /\ C)
D \/ E ® G
G ® ù (H \/ I)
ù C /\ E /\ H
2. A \/ B ® C /\ D
D \/ E ® G
A \/ ù G
3. (A ® B) /\ (C ® D)
(B ® D) /\ (ù C ® A)
(E® G) /\ (G ® ùD)
ùE ® E
4. (A ® B /\ C) /\ (D®B /\ E)
(G ® ùA) /\ H ® I
(H ® I) ® G /\ D
ù(ù C® E)
Задача 1. 20
Исследовать противоречивость помещенных ниже посылок :
Контракт будет выполнен тогда и только тогда, когда дом будет закончен в феврале. Если дом будет закончен в феврале, то мы можем переезжать 1-го марта. Eсли мы не сможем переехать 1-го марта, то мы должны внести квартирную плату за март. Если контракт не будет выполнен, то мы должны внести квартирную плату за март. Мы не будем вносить квартирную плату за март.
Задача 1. 21
Проверить на логичность рассуждения, построив формальное доказательство любым известным методом:
1. Если Джон ляжет сегодня поздно, то будет утром в отупении. Если он ляжет не поздно, то ему будет казаться, что не стоит жить. Следовательно, или Джон будет завтра в отупении, или ему будут казаться, что не стоит жить.
2. Заработная плата возрастет только, если будет инфляция. Если будет инфляция, то увеличится стоимость жизни. Заработная плата возрастет. Следовательно, увеличится стоимость жизни.
3. Если завтра будет холодно, я надену теплое пальто, если рукав будет починен. Завтра будет холодно, а рукав не будет починен. Следовательно, я не надену теплое пальто.
4. Я пойду домой или останусь здесь и выпью стаканчик. Я не пойду домой. Следовательно, я останусь и выпью.
5. Если 2 - простое число, то это наименьшее простое число. Если 2 - наименьшее простое число, то 1 не есть простое число. Число 1 не есть простое число. Следовательно, 2 - простое число.
6. Если 6 - составное число, то 12 - составное число. Если 12 - составное число, то существует простое число, большее чем 12. Если существует простое число больше 12, то существует составное число больше 12. Если 6 делится на 2, то 6 - составное число. Число 12 - составное. Следовательно, 6 - составное число.
7. Или Сэлли и Боб одного возраста, или Сэлли старше Боба. Если Сэлли и Боб одного возраста, то Нэнси и Боб не одного возраста. Если Сэлли старше Боба, то Боб старше Уолтера. Следовательно, или Нэнси и Боб не одного возраста, или Боб старше Уолтера.
8. Если Смит победит на выборах, он будет доволен, а если он будет доволен, то он плохой борец в предвыборной кампании. Но если он провалится на выборах, то потеряет доверие партии. Он плохой борец в предвыборной кампании, если он потеряет доверие партии. Если он плохой борец в предвыборной кампании, ему следует выйти из партии. Смит или победит на выборах, или провалится. Следовательно, ему нужно выйти из партии.
9. Если Доджеры выиграют, то Лос-Анджелес будет торжествовать, а если выиграет Уайт-Сокс, то торжествовать будет Чикаго. Выиграют или Доджеры, или Уайт-Сокс. Однако, если выиграют Доджеры, то Чикаго не будет торжествовать, а если выиграет Уайт-Сокс, то не будет торжествовать Лос-Анджелес. Итак, Чикаго будет торжествовать тогда и только тогда, когда не будет торжествовать Лос-Анджелес.
10. Если я поеду автобусом, а автобус опоздает, то я пропущу назначенное свидание. Если я пропущу назначенное свидание и начну огорчаться, то мне не следует ехать домой. Если я не получу эту работу, то я начну огорчаться и мне следует поехать домой. Следовательно, если я поеду автобусом и автобус опоздает, то я получу эту работу.
11. Либо я сдам зачет сегодня, либо, если поеду автобусом, то опоздаю в институт. Если я не сдам зачет сегодня, то не поеду автобусом. Следовательно, если я опоздаю в институт, то поеду автобусом.
12. Книга будет выпущена или в мае, или в июне. Если она выйдет в мае, то читатели получат ее в августе. Если книга выйдет в июне, то в магазинах появится в сентябре. Значит, или читатели получат книгу в августе, или она в сентябре появится в магазинах.
13. Если капиталовложения останутся постоянными, то возрастут правительственные расходы или возникнет безработица. Если правительственные расходы не возрастут, то налоги будут снижены. Если налоги будут снижены и капиталовложения останутся постоянными, то безработица не возникнет. Следовательно, правительственные расходы возрастут.
14. Если автомобиль не заводится, то неисправна либо система зажигания, либо система питания. Зажигание в порядке, а автомобиль не заводится. Следовательно, неисправна система питания.
15. Если вечер скучен, то или Алиса начинает плакать, или Анатоль рассказывает смешные истории. Если Сильвестр приходит на вечер, то или вечер скучен, или Алиса начинает плакать. Если Анатоль рассказывает смешные истории, то Алиса не начинает плакать. Сильвестр приходит на вечер тогда и только тогда, когда Анатоль не рассказывает смешные истории. Значит, если Алиса не начинает плакать, то Анатоль рассказывает смешные истории.
16. Если я пойду завтра на первое занятие, то должен буду встать рано, а если я пойду вечером на танцы, то лягу спать поздно. Если я лягу спать поздно, а встану рано, то буду вынужден довольствоваться пятью часами сна. Я просто не в состоянии обойтись пятью часами сна. Следовательно, я должен или пропустить завтра первое занятие, или не ходить на танцы.
17. Либо свидетель не был запуган, либо, если Генри покончил жизнь самоубийством, то записка была найдена. Если свидетель был запуган, то Генри не покончил жизнь самоубийством. Следовательно, если записка была найдена, то Генри покончил жизнь самоубийством.
18. Если исход скачек будет предрешен сговором или в игорных домах будут орудовать шулеры, то доходы от туризма упадут, и город пострадает. Если доходы от туризма упадут, полиция будет довольна. Полиция никогда не бывает довольна. Следовательно, исход скачек не предрешен сговором.
19. Алиса сказала, что Барбара и Клара говорят правду. А Клара сказала, что Элспет и Фиона или обе говорят правду, или обе лгут. Деби считает, что по крайней мере или Алиса, или Барбара говорят правду; тогда как Барбара утверждает, что только одна из двух - или Алиса, или Фиона - была правдивой. Элспет считает, что Алиса и Барбара всегда говорят правду, однако Фиона уверена, что Барбара и Клара обе не могли сказать правду. Кому следует верить?
20. Если строить противоатомные убежища, то другие государства будут чувствовать себя в опасности, а наш народ получит ложное представление о своей безопасности. Если другие страны будут чувствовать себя в опасности, то они смогут начать превентивную войну. Если наш народ получит ложное представление о своей безопасности, то он ослабит свои усилия, направленные на сохранение мира. Если же он не строит противоатомные убежища, то мы рискуем иметь колоссальные потери в случае войны. Следовательно, либо другие страны могут начать превентивную войну, и наш народ ослабит свои усилия, направленные на сохранение мира, либо мы рискуем иметь колоссальные потери в случае войны.
21. Организаторы международной конференции по компьютерам решили, что для того, чтобы на встрече не доминировали коммерческие интересы, будет только один магазин, которым будут пользоваться вместе все производители компьютеров. Сами производители будут ответственны за определение того, кто принимает участие в представительстве. 10 компаний - 5 европейских и 5 американских - дали знать, что они хотят принять участие в конференции. (Обозначим эти компании через A, B, C, D, E и F, G, H, I, J соответственно. ) Однако из-за обязательств по контрактам и торговой политики должны появиться различные ограничения. Европейские предписания требуют, чтобы G и I не могли одновременно принимать участие в конференции; аналогично не могут одновременно принять участие F, G и J. Ограничения американских производителей исключают участие A и D, пока G не примет участие; аналогично исключаются C и D. Если E присутствует на конференции, то должна присутствовать и J, однако если они принимают участие вдвоем, то B не может быть там. И наконец, B и C не могут вместе принимать участие в конференции. Может ли быть достигнуто соглашение, по которому по 3 компании из каждой группы могут собраться вместе, не нарушая условий? Если так, то кто именно примет участие?
22. В финал эстафеты вышли команды 6 стран: европейские команды A и B, африканские команды C и D и американские команды E и F. О результатах соревнований известно, что:
команда A одержала победу над командой B,
африканская команда получила золотые медали,
команда B победила команду D,
по всему было видно, что первое и второе места достанутся американским командам, и вдруг в последний момент между ними вклинилась европейская команда,
африканская команда отстала от всех остальных участников финала,
первыми финишировали 3 негритянских бегуна,
команда F победила команду B,
команда E одержала победу над командой F,
в составе европейских команд не было негритянских спортсменов. Известно, что ровно одна из 9 посылок является ложной. Как распределились места между 6 командами?