Задачи и упражнения

1. Дано высказывание А: «Существуют четные простые числа». Определите, истинно оно или ложно. Укажите среди следующих высказываний отрицание высказывания А: а) «Существуют нечетные простые числа»; б) «Неверно, что существуют четные простые числа»; в) «Любое простое число нечетно».

2. Для высказывания А: «Любые два треугольника подобны» сформулируйте отрицание и двойное отрицание. Какие из этих трех высказываний истинны?

3. Даны высказывания «Я купил велосипед» (А); «Я путешествовал по России» (В) и «Я участвовал в соревнованиях по велосипеду» (С). Сформулируйте высказывания, соответствующие формулам: А ٨ В, А ٨ В ٨ С, А ٨`С, А ٨ В, `В ٨`С.

4. Даны высказывания «Четырехугольник MNPQ – параллелограмм» (А) и «Диагонали четырехугольника MNPQ в точке пересечения делятся пополам» (В). Сформулируйте высказывания, соответствующие формулам А ® В, В ® А, `А, `В, `А ® В, `В ® А.

5. Составьте таблицы истинности для следующих формул: X ® (Y ٧ Z), (X ® Y) ٧ (X ® Z).

6. Покажите, что формулы X ٨Y ~ Y ٨ X, X ٧Y~Y ٧X, ((X ® Y) ٨ X) ® Y являются тавтологиями.

7. Докажите равносильность формул: а) X ٨ (Y ٧ Z) и (X ٨ Y) ٧ (X ٨ Z); б) X ٧ (Y ٨ Z) и (X ٧ Y) ٨ (X ٧ Z); в) X ٧ Y и`X ٨`Y; г) X ٨ Y и`X ٧`Y; д) X ® (Y ® Z) и (X ٨ Y) ® Z; е) (X ® Y) ٨ (X ® Z) и X ® (Y ٨ Z).

8. Постройте совершенные ДНФ и КНФ функций: x1 Å x2, x1 ¯ x2, x1 ® x2, x1 ~ x2.

9. Запишите в совершенных ДНФ и КНФ булеву функцию f1 (x1, x2, x3), принимающую значение 1 на наборах с номерами 0, 3, 7. Определите, к каким классам функций относится эта функция.

10. Проверьте справедливость равенств: x =`x Å 1, x1 ® x2 = `x1 ٧ x2.

11. Составьте таблицу свойств булевых функций двух переменных. Из таблицы выпишите все полные системы булевых функций.

12. Проверьте линейность булевой функции f2 (x1, x2, x3), принимающей значение 1 на наборах с номерами 0, 1, 5, 6.

13. Синтезируйте логические схемы булевых функций из задач № 9, 12 в базисах: а) { ٧,` }; б) { ٨,` }.

14. Найдите минимальную ДНФ функции f (x1, x2, x3, x4), принимающей значение 1 на наборах с номерами 0, 1, 2, 5, 6. 7, 8, 12, 13.

15. Приведите примеры: а) монотонной функции, которая одновременно была бы линейной; б) самодвойственной функции, которая одновременно была бы линейной; в) линейной и монотонной функций.

16. Покажите, что функции Шеффера и Вебба не являются ни линейными, ни монотонными, ни самодвойственными.

17. Докажите полноту системы булевых функций, состоящей из дизъюнкции, константы 0 и эквивалентности.

18. Путешественник попал к людоедам. Они разрешают ему произнести какое-нибудь высказывание и ставят условие, что если его высказывание будет истинным, то его сварят, а если ложным, то зажарят. Какое высказывание следует произнести путешественнику, чтобы избежать гибели?

Список литературы

1. Кориков А.М., Сафьянова Е.Н. Основы системного анализа и теории систем: Учебное пособие. – Томск: изд-во Том. ун-та, 1989. – 207 с.

2. Оре О. Теория графов. – М.: Наука, 1980. – 352 с.

3. Основы кибернетики. Математические основы кибернетики / Под. ред. К.А. Пупкова. – М.: Высш. школа, 1974. – 416 с.

4. Горбатов В.А. Основы дискретной математики. – М.: Высш. школа, 1986. – 312 с.

5. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 с.

6. Кузин Л.Т. Основы кибернетики.: В 2 т. Т.2. Основы кибернетических моделей. – М.: Энергия, 1979. – 584 с.

7. Шевелев Ю.П. Высшая математика 5. Дискретная математика. Ч.1: Теория множеств. Булева алгебра (для автоматизированной технологии обучения): Учебное пособие. – Томск: Том. гос. ун-т систем управления и радиоэлектроники, 1998. – 114 с.

 

[Ò1]

[Ò2]