2Дискретка / Задачники / 3.ИВ ИП

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)Если противоположные стороны четырехугольника попарно равны, то он является параллелограммом. Четырехугольник являет- ся параллелограммом тогда и только тогда, когда его диагонали де-

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	N =”Ему нравятся фиолетовые галстуки“,
P =”Он популярен“,		D =”У него странные друзья“
Запишите	символические	выражения N É (P Ú D) , P É ¬D ,
(N Ù P) É D ,	(N É ¬ P)Ù (P É D) в виде высказываний.

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

U =”Он удачлив“,	P =”Он популярен“, B =”Он богат“
Запишите символические выражения		¬(U É P) , (U Ú B) É P,
P É (U Ù B), (U É P) Ú (¬B É (¬U Ú ¬P)) в виде высказываний.
6. Существуют ли в ИВ следующие выводы:
1) |- A Ù B É A Ù C ,	5)	A |-¬(A ɬ A),
2) |- (( A É B) É B) É A ,	6)	A É B |- B É A,
3) |-¬ A É A,	7) A É B,¬B |-¬ A?

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?

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

1)A |- A ,

2)A É D, A Ù B |- D ,

3)|- A Ú A É A,

4)A Ù D, B Ú D É C, A É B |- C ,

5)A É B, B É C |- A É C ,

6)A É B, ¬ B |- ¬ A,

7)A É B |- ¬ B ɬ A ,

8)A |-¬¬ A ,

9)|- A ɬ¬ A ,

10)|- (¬¬ A É A) Ù (A ɬ¬ A).

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

1)A É (B É C) |- B É (A É C) ,

2)A É (B É C) |- A Ù B É C ,

3)A Ù B É C |- A É (B É C),

4)A É B |- (B É C) É (A É C) ,

5)A É B |- (C É A) É (C É B) ,

6)A É B |- C Ù A É C Ù B ,

7)A É B |- A Ù C É B Ù C ,

8)A É B |- A Ú C É B Ú C ,

9)A É B |- C Ú A É C Ú B ,

10)¬ A |- A É B ,

11)A |- ¬ A É B ,

12)A É B |- ¬ B É ¬ A,

13)A É ¬ B |- B É ¬ A ,

14)¬ A É B |- ¬ B É A ,

15)¬ A ɬ B |- B É A,

16)|- A Ú A Ù B É A,

17)|- A É A Ù (A Ú B),

18)|- A Ù B Ù C É A Ù (B Ù C),

19)|- (A Ú B) Ú C É A Ú (B Ú C),

20)A Ù (B Ú C) |- A Ù B Ú A Ù C ,

21)A Ù B Ú A Ù C |- A Ù (B Ú C),

22)A Ú B Ù C |- (A Ú B) Ù (A Ú C),

23)(A Ú B) Ù (A Ú C) |- A Ú B Ù C ,

24)|- A Ú¬ A,

25)|- ¬(A Ù¬ A),

26)	¬ (A Ú B)|- ¬ A Ù ¬B ,
27)	|- ¬ A Ù ¬ B É ¬(A Ú B) ,
28)	¬(A Ù B) |- ¬ A Ú ¬B
29)	|- ¬ A Ú ¬ B É ¬(A Ù B) ,

30)A Ù ¬B |- ¬(A É B) ,

31)¬( A É B) |- A Ù ¬ B ,

32)|- A Ú B ɬ( ¬ A Ù ¬ B),

33)¬( ¬ A Ù ¬ B) |- A Ú B ,

34)|- A É B É ¬(A Ù ¬B),

35)¬(A Ù ¬ B) |- A É B ,

36)|- A Ù B É ¬(A É ¬ B),

37)¬(A É ¬B) |- A Ù B ,

38)	A Ù B |- ¬( ¬ A Ú ¬ B),
39)	¬( ¬ A Ú ¬ B) |- A Ù B ,
40)	A É B |- ¬ A Ú B,
41)	|- ¬ A Ú B É (A É B) ,

42)|- A Ú B É ( ¬ A É B),

43)¬ A É B |- A Ú B.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

кто невиновен, а кто виновен?

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

15.Брауну, Джонсу и Смиту предъявлено обвинение в соучастии

вограблении банка. Похитители скрылись на ожидавшем их авто- мобиле. На следствии они дали следующие показания:

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

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

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

16. Инспектор Борисов точно знал, что преступник скрывается в одном из трех мест: на даче в Переделкино, у своего знакомого в

Марьиной роще или же на квартире у перекупщика краденого на Таганке. В одном из этих же мест могла быть и жена преступника,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

по четыре.

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

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

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

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

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

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

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 ))?

2. Пусть	S (x, y, z) Û "x + y = z", P(x, y, z) Û "xy = z". Дать
словесную	формулировку и определить истинность предиката

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

1) Q(x) = $y S ( y, y, x);	3) Q(x) = "y S (y, y, x);
2) Q(x) = $y P(y, y, x);	4) Q(x) = "y P(y, y, x).
3. Пусть S (x, y, z) Û "x + y = z",	P(x, y, z) Û "xy = z". Дать

словесную формулировку и определить истинность следующих вы- сказываний в моделях M1 = ¢+ ; S(3) , P(3) и M2 = ¡+ ; S(3) , P(3) .

	1)	$y "x S (y, y, x);	3) "x$y S (y, y, x);
	2)	$y"x P( y, y, x);	4) "x$y P( y, y, x)?
	4. Пусть M = ¢+ ; S(3) , P(3)		, где
		S (x, y, z) Û "x + y = z", P(x, y, z) Û "xy = z".
	Записать формулы, выражающие следующие утверждения:
	1)	x = 0;	6)	x – простое число;
	2)	x =1;	7)	x = y ;
	3)	x = 2 ;	8)	x ≤ y;
	4)	x – четное число;	9)	x < y;
	5)	x – нечетное число;

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";