Сборник задач по дискретке

17.Для всех переключательных функций двух переменных определить принадлежность их классам Поста. Составить все возможные базисы из этих функций.

18.Для функций из задания 9 определить принадлежность их классам Поста. Составить все возможные базисы из этих функций.

19.Проверить полноту заданной системы функций. Для функциональ- но полной системы выделить все возможные базисы.

20. По заданной схеме найти функцию проводимости и условия работы: x y x y

31

22.Построить схемы по заданным условиям работы:

1)f (110) = f (111) =1;

2)f (101) = f (110) =1;

3)f (010) = f (101) = f (111) = 1;

4)f (001) = f (100) = f (101) = 1;

5)f (001) = f (011) = f (101) = f (111) =1;

6)f (001) = f (010) = f (011) = f (101) =1.

23.Проверить равносильность схем:

32

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

1.Определить истинность следующих высказываний.

1)Две прямые параллельны или имеют общие точки.

2)Две прямые на плоскости параллельны или имеют общие точки.

3)Эйфелева башня находится в Париже или в Нью-Йорке.

4)Либо Эйфелева башня находится в Париже, либо она Нью-Йорке.

5)Если 17 делится на 2, то оно делится на 4.

6)Если 18 делится на 2, то оно делится на 4.

7)Если Солнце всходит на востоке, то оно заходит на западе.

8)Если Солнце всходит на юге, то оно заходит на западе.

9)Если Солнце всходит на востоке, то оно заходит на севере.

10) Если Солнце всходит на севере, то оно заходит на юге.

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

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

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

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

3.Показать, что следующие рассуждения не являются правильными, подставляя вместо A и B конкретные примеры.

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

2)Если A, то B . Но ¬ A. Значит, ¬B .

3)Если A, то B . Верно B . Значит, верно также и A.

4)A или B . Следовательно, и A, и B .

4.Сформулировать предложение в виде условного утверждения

«Если … , то … ».

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

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

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

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

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

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

34

5. Установить, являются ли эквивалентными высказывания в каждой из следующих пар.

1)Мой отец работает в университете, а брат учится в школе. Невер- но, что мой отец не работает в университете, а брат в школе не учится.

2)Водород бесцветен и не имеет запаха. Неверно, что водород имеет цвет или запах.

3)Число кратно трем тогда и только тогда, когда сумма его цифр кратна трем. Неверно, что либо число не делится на три, либо сумма его цифр не является кратной трем.

4)Если Петр – ровесник Ивана, то и Иван – ровесник Петра. Если Петр не является ровесником Ивана, то и Иван не может быть ровесником Петра.

5)Кирилл виноват. Кирилл не может быть невиноватым.

6)Если он опоздал, то пришел не вовремя. Если он пришел не вовремя, то опоздал.

6.Из приведенных высказываний выбрать эквивалентные высказыванию

«A есть необходимый признак B ».

7)B и A выполняются одновременно.

8)B и A не выполняются одновременно.

7.Решить предыдущую задачу для высказывания

«A является достаточным признаком B ».

8.Равносильны ли следующие предложения:

1)A есть достаточный признак B ,

2)B есть необходимый признак A?

9.Сформулировать достаточный признак для отрицания B , если A есть необходимый признак B .

10.Будет ли C необходимым (достаточным) признаком A, если:

1)C – необходимый признак B , B – необходимый признак A;

2)C – необходимый признак B , B – достаточный признак A;

3)C – достаточный признак B , B – необходимый признак A;

4)C – достаточный признак B , B – достаточный признак A?

35

11. Заменить многоточия словами:

«необходимо и достаточно», «необходимо, но недостаточно», «достаточно, но не необходимо»

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

1)Для того чтобы три числа a, b, c были равны между собой, …, чтобы выполнялось уравнение (a − b)2 + (b − c)2 = 0.

2)Для того чтобы сумма двух чисел была числом рациональным, …, чтобы каждое слагаемое было рациональным числом.

3)Для того чтобы сумма 5 положительных чисел была меньше 100, …, чтобы хоть одно число было меньше 20.

4)Для того чтобы число делилось на 12, …, чтобы оно делилось на 3.

5)Для того чтобы число делилось на 5, …, чтобы оно оканчивалось 0.

6)Для того чтобы корни уравнения x2 + px + q = 0 имели одинаковые знаки, …, чтобы q было больше 0.

7)Для того чтобы основание треугольника равнялось 20 см, а высота – 10 см, …, чтобы площадь треугольника равнялась 100 см2.

8)Для того чтобы площадь треугольника равнялась 50 см2 , …, чтобы основание треугольника равнялось 20 см, а высота – 5 см.

9)Для того чтобы четырехугольник был ромбом, …,

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

10)Для того чтобы скалярное произведение векторов было неотрица- тельным, …, чтобы угол между векторами был острый.

11)Для того чтобы определитель матрицы был равен нулю, …,

чтобы ее строки (столбцы) были линейно зависимы.

12)Для того чтобы монотонная последовательность сходилась, …, чтобы она была ограничена снизу.

13)Для того чтобы последовательность расходилась, …,

чтобы она была не ограничена.

14)Для того чтобы последовательность сходилась, …, чтобы она была ограничена.

15)Для того чтобы программа завершилась, …,

чтобы она не содержала циклов и операторов перехода. 16) Для того чтобы войти в самолет, …, иметь посадочный талон.

36

12. Переформулировать следующие утверждения в виде «Для того чтобы …, необходимо, чтобы …».

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

2)В прямоугольнике диагонали равны.

3)В ромбе диагонали взаимно перепендикулярны.

13.Переформулировать следующие утверждения в виде

«Для того чтобы …, достаточно, чтобы …».

1)Если две прямые перпендикулярны одной и той же прямой, то они параллельны.

2)Если в выпуклом четырехугольнике сумма противоположных

углов равна 180o , то вокруг него можно описать окружность.

3)Если треугольник равнобедренный, то он имеет ось симметрии.

14.Записать приведенные сложные высказывания с помощью логиче- ской символики, выделив в них простые высказывания.

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

2)Для того чтобы число делилось на три, необходимо, чтобы оно делилось на шесть.

3)Сумма чисел делится на три тогда и только тогда, когда все слага- емые делятся на три.

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

инаоборот.

15.В следующих предложениях вместо многоточия поставить либо «тогда», либо «тогда и только тогда» так, чтобы получилось справедливое утверждение. Переформулировать утверждения со словом «тогда» в виде

«Из A следует B »1:

1)x2 − 4x + 2 = 0 …, когда x = 2 ;

2)x2 − 5x + 6 = 0 …, когда x = 2 ;

3)ex (x − 2) = 0 …, когда x = 2 ;

4)сумма четырех чисел четна …, когда каждое слагаемое нечетно;

5)сумма пяти чисел больше 100 …, когда каждое слагаемое больше 20.

1 Слово «тогда» и в математике, и в разговорной речи часто подразумевает значение «тогда и только тогда», то же можно сказать и об оборотах «если» и «если и только если». Эту двусмысленность можно

исключить, переформулировав предложение в виде «Из A следует B ».

37

17. Указать формулы, которые должны быть посылками, чтобы задан- ная последовательность формул была выводом:

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 .

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

38

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

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

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

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

40