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

а) Упростить формулы (привести их к сокращенной ДНФ).

11. Проверить, что наборы следующих функций являются базисами и выразить через них конъюнкцию, дизъюнкцию и отрицание: а) импликация и константа 0; б) импликация и сложение по модулю 2; в) функция трех переменных, заданная таблицей истинности (при естественном порядке наборов переменных: 10011110).

Следующие логические задачи требуется решить методами теории булевых функций:

12. Определите, кто из четырех студентов сдал экзамен, если известно:

а) если первый сдал, то и второй сдал;

б) если второй сдал, то третий сдал или первый не сдал;

в) если четвертый не сдал, то первый сдал, а третий не сдал;

г) если четвертый сдал, то и первый сдал.

13. Известно следующее: если Петя не видел Колю на улице, то либо Коля ходил в кино, либо Петя сказал правду; если Коля не ходил в кино, то Петя не видел Колю на улице, и Коля сказал правду; если Коля сказал правду, то либо он ходил в кино, либо Петя солгал. Выясните, ходил ли Коля в кино.

14. В школе, перешедшей на самообслуживание, четырем старшеклассникам Андрееву, Костину, Савельеву и Давыдову поручили убрать 7, 8, 9 и 10-й классы. При проверке выяснили, что десятый класс убран плохо. Не ушедшие домой ученики сообщили о следующем:

а) Андреев: “Я убирал 9-й класс, а Савельев 7-й”;

б) Костин: “Я убирал 9-й класс, а Андреев 8-й”;

в) Савельев: “Я убирал 8-й класс, а Костин -10-й”.

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

15. Пять школьников из пяти различных городов Брянской области прибыли в Брянск для участия в областной олимпиаде по математике. На вопрос: “Откуда вы?” каждый дал ответ:

а) Иванов: “Я приехал из Клинцов, а Дмитриев – из Новозыбкова”;

б) Сидоров: “Я приехал из Клинцов, а Петров – из Трубчевска”;

в) Петров: “Я приехал из Клинцов, а Дмитриев из Дятькова”;

г) Дмитриев: “Я приехал из Новозыбкова, а Ефимов – из Жуковки”;

д) Ефимов: “Я приехал из Жуковки, а Иванов живет в Дятькове”.

Откуда приехал каждый из школьников, если одно его утверждение верно, а другое ложно?

16. На вопрос: кто из трех студентов изучал логику, получен верный ответ: “Если изучал первый, то изучал и третий, но неверно, что если изучал второй, то изучал и третий”. Кто изучал логику?

17. Однажды следователю пришлось допрашивать трех свидетелей: Клода, Жака и Дика. Их показания противоречили друг другу, и каждый из них обвинял кого-то во лжи:

а) Клод утверждал, что Жак лжет;

б) Жак обвинял во лжи Дика;

в) Дик уговаривал следователя не верить ни Клоду, ни Жаку.

Но следователь быстро вывел их на чистую воду, не задав им ни одного вопроса. Кто из свидетелей говорил правду?

18. Нарисовать функциональную схему для функции

(x¯ y) ~ (xy | z).

19. Нарисовать РКС для ДНФ:

а также сократить её по правилу Блейка и нарисовать РКС для полученной сокращённой ДНФ.

20. Найти хроматическое число и реберно-хроматическое число для графов из заданий 61 и 70.

21. Выяснить являются ли графы из заданий 61и 70 эйлеровыми, полуэйлеровыми, гамильтоновыми или полугамильтоновыми. (Объясните свой ответ). Если ответ на какой-нибудь из этих четырех вопросов является положительным, то укажите соответствующий путь.

22. Нарисовать все возможные деревья, содержащие 5 вершин (и значит 4 ребра).

23. Для графа на рис. 16 определите, является ли он эйлеровым, и если да, то найдите эйлеров путь в соответствии с алгоритмом Флери.

24. Является ли граф на рис.16 гамильтоновым, а если нет, то сколько вершин надо добавить, чтобы он стал таковым.

25. Граф на рис.17 не является плоским. Является ли он планарным? Если да, то нарисуйте этот граф плоским.

Cодержание:

Введение

Логические (булевы) функции

1. Основные логические функции.

2. Свойства конъюнкции, дизъюнкции и отрицания

3. ДНФ, СДНФ, КНФ, СКНФ

4. Представление логических функций в виде СДНФ (СКНФ)

5. Нахождение сокращенной ДНФ по таблице истинности (карты Карно)

6. Полиномы Жегалкина

7. Суперпозиция функций. Замыкание набора функции.Замкнутые классы функций. Полные наборы. Базисы

8. Некоторые приложения теории булевых функций. Элементы теории графов

9. Общие понятия теории графов

10. Эйлеровы и полуэйлеровы графы

11. Матрицы и графы. Нахождение путей и сечений с помощью структурной матрицы

12. Сети, потоки в сетях. Теорема Форда – Фалкерсона

13. Раскраска графа

14. Деревья и их простейшие свойства

15. Решение типовых задач

16. Индивидуальные задания

17. Дополнительные задачи