сборник задач по дискретке другой вариант

4.ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

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

1)Я бы заплатил за работу по ремонту телевизора, только если бы он стал работать. Он же не работает. Поэтому я платить не буду.

2)Он сказал, что придет, если не будет дождя. Но идет дождь. Значит, он не придет.

3)Если он принадлежит к нашей компании, то он храбр и на него можно положиться. Он не принадлежит к нашей компании. Значит, он не храбр или же на него нельзя положиться.

4)Намеченная атака удастся, только если захватить противника врасплох или же если позиции его плохо защищены. Захватить его врасплох можно только, если он беспечен. Он не будет беспечен, если его позиции плохо защищены. Значит, атака не удастся.

5)Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей, либо Джонс лжет. Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство имело место после полуночи. Если убийство было совершено после полуночи, то либо Смит был убийцей, либо Джонс лжет. Следовательно, Смит был убийцей.

6)Если x + 3 = 3 − x , то x2 + 6x + 9 = 3 − x . Но x2 + 6x + 9 = 3 − x

тогда и только тогда, когда (x + 6)(x +1) = 0 , что имеет место в том и только в том случае, когда x = −6 или x = −1. Значит, только −6 и

−1 могут быть корнями уравнения x + 3 = 3 − x , т.е. x + 3 = 3 − x влечёт x = −6 или x = −1.

7)Если 2 – простое число, то это наименьшее простое число. Если 2 – наименьшее простое число, то 1 не есть простое число. Число

1не есть простое число. Следовательно, 2 – простое число.

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

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

31

лятся в точке пересечения пополам. Противоположные стороны четырехугольника попарно равны. Следовательно, его диагонали точкой пересечения делятся пополам.

10)Иванов не сделает эту работу, если ее сделает Петров. Петров и Сидоров сделают эту работу в том и только том случае, если

еесделает Иванов. Сидоров, эту работу сделает, а Иванов нет. Следовательно, Петров не сделает эту работу.

11)Если Петров поедет в Москву, то Иванов поедет в Киев. Петров поедет в Москву или в Кострому. Если Петров поедет в Москву, то Семенов останется в Москве. Но Семенов не останется в Москве. Значит, Иванов поедет в Киев.

12)Если будет сильный ветер, мы не пойдем на каток, а отправимся в музей. Если мы пойдем на каток, то встретим много знакомых. Если мы отправимся в музей, то увидим много интересного. Мы не встретим многих знакомых и не увидим много интересного. Значит, завтра не будет сильного ветра.

2.Сформулируйте в виде импликаций следующие предложения.

1)Диагонали квадрата взаимно перпендикулярны.

2)Всякий человек должен быть откровенен на исповеди.

3)Сумма углов треугольника равна 180°.

4)Все новое – только хорошо забытое старое.

5)Он кентавр, только если он имеет шесть ног.

6)Чтобы быть преуспевающим политиком, нужно быть избранным.

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

8)Необходимо иметь шлем, чтобы играть в американский футбол.

9)Только если я читаю Шекспира, я литературно образован.

3.Покажите с помощью конкретных примеров, что следующие схемы умозаключений не являются правильными (вместо слов «первое» и «второе» должны подставляться высказывания):

1)Если первое, то второе. Следовательно, если второе, то первое.

2)Либо первое, либо второе. Значит, если есть первое, то есть и второе.

3)Если первое, то второе. Но первое неверно. Значит, второе тоже неверно.

4)Если первое, то второе. Верно второе. Значит, верно также и первое.

5)Первое или второе. Следовательно, и первое, и второе.

32

4. Пусть N, P, D обозначают следующие высказывания N =”Ему нравятся фиолетовые галстуки“,

P =”Он популярен“, D =”У него странные друзья“

5. Пусть U, P, B обозначают следующие высказывания

4)|-¬(A Ú¬ A) É (A Ú¬ A),

7.Выводами (доказательствами) из каких формул являются следующие последовательности формул:

1)A É (B É C), A, B É C, C ;

2)A É A Ú B, A, A Ú B, A;

3)A É (B É C), A, B É C, B, C ;

4)A É (B É A), (A É (B É A)) É B, B ;

5)(A ɬ¬ B) É (¬ B ɬ A), A ɬ¬ B, ¬B ɬ A, ¬ B, ¬ A;

6)A É A Ú B ;

7)A É A Ú B, ( A É A Ú B) É (B É ( A É A Ú B)), B É ( A É A Ú B);

8)A Ù B É B, A Ù B, B, C, B É (C É B Ù C), C É B Ù C, B Ù C ;

9) A Ù B, A Ù B É B, A, A É (C É A), C É A, A É (D É A), D É A, (C É A) É ((D É A) É (C Ú D É A)),

(D É A) É (C Ú D É A), C Ú D É A?

33

8. Построить в исчислении высказываний следующие выводы:

9. Построить в исчислении высказываний следующие выводы:

34

10.«Позавчера мне было 20 лет, – сказал Андрей, – а в будущем году мне исполнится 23 года». Может ли это утверждение быть верным?

11.Студент Лентяев, встретив в конце зачетной недели своих товарищей по группе, спросил их о том, какие экзамены и в какой очередности им придется сдавать? Ребята решили пошутить над Лентяевым и дали ему такие ответы:

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

Федор : Все-таки вторым мы сдаем математический анализ, а четвертым геометрию.

Леони д : Первым экзаменом у нас – физика, а геометрия, действительно, четвертая.

Всвоих ответах каждый из ребят лишь наполовину сказал

правду, в чем они честно признались Лентяеву. После этого Лентяев, поразмыслив, установил точное расписание экзаменов. Попытайтесь сделать это и Вы.

12. Четыре подруги Маша, Полина, Ольга и Наташа участвовали в соревнованиях по бегу и заняли первые четыре места. Установите, кто какое место из них занял, если известно, что в каждом из приведенных ниже ответов, которые дали лукавые девушки опоздавшему к финишу корреспонденту, верной является лишь его половина.

На та ша : Ольга была второй, а Полина – третьей.

М аш а : Нет, Наташа. Ольга была первой, а второй была ты.

Ольг а : Да, что вы, девочки! Второй была Маша, а Полина прибежала четвертой.

13. Перед судом стоят три человека, из которых только один может быть преступником.

Известно, что преступник, отвечая на вопросы, всегда лжет. А тот, кто не принимал участия в преступлении, всегда говорит правду.

Получив ответ одного из них на вопрос: «Виновны ли Вы?», судья задал двум оставшимся один и тот же вопрос: «Прав ли первый?» На этот вопрос он получил следующие ответы:

Второй : Первый прав. Третий : Первый солгал. Кто же преступник?

35

14.(Задача Кислера) Браун, Джонс и Смит обвиняются в подделке сведений о подлежащих налоговому обложению доходах. Они дают под присягой такие показания:

Браун : Джонс виновен, а Смит невиновен. Джонс: Если Браун виновен, то виновен и Смит.

Смит : Я невиновен, но хотя бы один из них двоих виновен. Обозначим через Б, Д и С высказывания: «Браун невиновен»,

«Джонс невиновен», «Смит невиновен». Выразите показания каждого из обвиняемых формулой. Постройте для этих формул таблицы истинности. Затем ответьте на следующие вопросы:

1)Совместимы ли показания всех троих заподозренных (т.е. могут ли они быть верны одновременно)?

2)Показания одного из обвиняемых следуют из показаний другого;

очьих показаниях идет речь?

3)Если все трое невиновны, то кто совершил лжесвидетельство?

4)Предполагая, что показания всех обвиняемых верны, укажите, кто невиновен, а кто виновен?

5)Если невиновный говорит истину, а виновный лжет, то кто невиновен, а кто виновен?

15.Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. Похитители скрылись на ожидавшем их автомобиле. На следствии они дали следующие показания:

Браун : Преступники были на синем «Бьюике». Джонс: Преступники были на черном «Крайслере».

Смит : Это был Форд Мустанг и ни в коем случае не синий. Каждый из них указал правильно либо марку машины, либо ее

цвет. Какого цвета был автомобиль и какой марки?

16.Инспектор Борисов точно знал, что преступник скрывается в одном из трех мест: на даче в Переделкино, у своего знакомого в Марьиной роще или же на квартире у перекупщика краденого на Таганке. В одном из этих же мест могла быть и жена преступника, которая была нужна инспектору для уточнения некоторых деталей следствия. Близкие преступника на вопрос о месте его пребывания дали различные ответы. Его мать сказала, что он наверняка, в Переделкино, откуда о н уже целую неделю не выезжает. Сестра преступника указала на Марьину рощу. Брат же утверждал, что на Таганке находится жена преступника, которая может быть знает, где его искать.

Зная, что все родственники при ответе на вопрос солгали, инспектор Борисов без труда выяснил, где скрывается преступник.

36

17.Инспектору Борисову стало известно, что совершена кража в ювелирном магазине. «Кто же «взял» магазин?» – задумался инспектор. Он знал, что это мог сделать либо вышедший недавно на свободу матерый уголовник по кличке «Лось», либо появившийся в городе Аполлон Рубашкин, которого знали в уголовном мире как «Артиста», либо «начинающий», но уже поднаторевший в преступном промысле Павел Смышляев.

Вскоре инспектору Борисову поступила информация: а) ювелирный магазин ограбил не Аполлон, б) магазин «взял» Смышляев.

Спустя некоторое время выяснилось, что только одно из этих сообщений соответствует действительности. Этого оказалось достаточным для того, чтобы инспектор Борисов установил, кто совершил кражу. Как он это сделал?

18.Гриша, Миша и Игорь – сыновья военнослужащих. У одного из них отец – офицер флота, у второго – ракетчик, а у третьего – десантник.

Юноши приняли решение тоже стать военными. Один из них попал на флот, другой стал ракетчиком, а третий – десантником.

Михаил по состоянию здоровья не попал в десантники, а Игорь не попал на флот. Не попал на флот и сын моряка.

Если сын десантника не стал десантником, то им стал сын ракетчика, а если Игорь – десантник, то сын моряка не ракетчик.

19.Пятеро выпускников школы заговорили однажды о том, кто кем станет.

Андрей считал, что банкиром может стать любой из них, но только не Дмитрий. Виктор утверждал, что ему нравится профессия метрдотеля. А Дмитрий полагал, что самым подходящим кандидатом в метрдотели является Григорий. Борис говорил, что он никогда не будет врачом, утверждая при этом, что Андрей может стать учителем. Григорий же утверждал, что Борис может быть блистательным актером.

Жизнь у ребят сложилась по-разному. Оказалось, что те, кто стали учителем и метрдотелем, ошибались в своих суждениях. А актер и банкир оказались целиком правы. Установите, кто из них какую профессию выбрал.

20.Найдется ли такой день недели, когда

1)«Если сегодня понедельник, то завтра четверг»=И;

2)«Если сегодня понедельник, то завтра вторник»=И;

3)«Если сегодня понедельник, то завтра среда»=Л?

37

21.На столе три одинаковых ящика. В одном из них два белых шара, в другом – белый и черный, а в третьем – два черных. Аналогичные надписи сделаны на крышках ящика, но ни одна из них не соответствует действительности. Как, вынув только один шар, определить, в каком ящике какие лежат шары?

22.Петя, Вася и Маша остались дома одни. Кто-то из них ел варенье. На вопрос мамы, кто это сделал, они сказали:

Петя : Я не ел. Маша тоже не ела.

Вася : Маша действительно не ела. Это сделал Петя. Маша : Вася врет. Это он съел.

Выясните, кто ел варенье, если известно, что двое из них оба раза сказали правду, а третий один раз соврал, а один раз сказал правду.

23.Четыре семьи, дружившие между собой, держали по 10 различных животных. Их питомцами были белки, кролики, хомяки и ежи. Каждая семья держала разное число разных животных – от одного до четырех, и ин в одной семье не было одинакового количества одних и тех же зверушек. Определите, сколько и каких животных было в каждой семье, если известно, что:

а) у Ивановых, Сидоровых и Петровых ежей было не два; б) у Ивановых и Петровых кроликов, а у Кузнецовых кроликов и

хомяков было не по одному; в) в семьях Сидоровых, Петровых и Кузнецовых жили не по три

белки; г) в семьях Ивановых и Петровых хомяков было не по два и не

по четыре.

24.На столе в одном ряду лежат четыре карты, каждая из которых туз или десятка. Установите их последовательность, если известно, что:

а) справа от десятки по меньшей мере лежит один туз; б) справа от туза лежит по крайней мере одна десятка; в) справа от туза лежит хотя бы один туз;

г) справа от карты пиковой масти лежит хотя бы одна карта той же масти;

д) справа от карты бубновой масти лежит по меньшей мере одна карта пиковой масти.

25.Ручаюсь, сказал продавец в зоомагазине, – что этот попугай будет повторять любое услышанное слово.

Обрадованный покупатель приобрел чудо-птицу, но, вернувшись домой, обнаружил, что попугай нем как рыба. Тем не менее, продавец не лгал.

38

5.ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

1.Будут ли следующие выражения формулами, и если это формулы, то какие переменные в них являются свободными, а какие связанными:

1)"x1 $x2 "x3 P(x1, x2 , x3 , x4 ) ;

2)"x1 P(x1, x2 ) É $x2 P(x1, x2 );

3)x1 x2 (P(x1, x2 ) Q(x1, x2 ))?

Q(x), высказываний "xQ(x), $xQ(x) в модели M = ¢+ ; S(3) , P(3) .

словесную формулировку и определить истинность следующих вы-

39

10)x делит y ;

11)z наименьшее общее кратное x и y ;

12)z наибольший общий делитель x и y ;

13)коммутативность сложения;

14)ассоциативность сложения;

15)коммутативность умножения;

16)ассоциативность умножения;

17)дистрибутивность сложения относительно умножения;

18)бесконечность множества простых чисел.

5.Рассмотреть в модели M = A; Q(2) все варианты квантифи-

кации переменных предиката Q . Определить истинность получаемых выражений, если

1)A = {0,1,2,3,4,5,6,7,8,9}, Q(x, y) "x делится на y";

2)A = ¥, Q(x, y) "x делится на y";

3)A = {0,1,2,3,4,5,6,7,8,9},

Q(x, y) "x имеет общий делитель с y";

4)A = {0,1,2,3,4,5,6,7,8,9}, Q(x, y) "x, y делятся на 3";

5)A = {0,1,2,3,4,5,6,7,8,9}, Q(x, y) "x, y − четные числа";

6)A = {0,1,2,3,4,5,6,7,8,9}, Q(x, y) "x ≤ y";

7)A = ¥, Q(x, y) "x ≤ y";

8)A = Z , Q(x, y) "x ≤ y";

9)A = P (B), B – непустое множество,

Q(x, y) "x y";

10)A = P (B), B – непустое множество, Q(x, y) "x пересекается с y";

11)A – множество студентов одной группы, Q(x, y) "x знаком с y";

12)A – множество людей, Q(x, y) "x знаком с y";

40