.php>
Содержание: "Методические указания и контрольные задания санкт-петербург удк 621. 396. 62"
Методические указания и контрольные задания санкт-петербург удк 621. 396. 62
СодержаниеБулевы функции и элементы теории графов
ЛР № от Подписано к печати
Логические (булевы) функции 5
Элементы теории графов 26
ЛОГИЧЕСКИЕ (БУЛЕВЫ) ФУНКЦИИ 1. Основные логические функции
Функции одной переменной y=f(x).
Функции двух переменных z = f(x,y).
2. Свойства конъюнкции, дизъюнкции и отрицания
Конъюнкцией n переменных f (x
Дизъюнкцией n переменных f (x
3. Днф, сднф, кнф, скнф
Дизъюнктивной нормальной формой
Совершенной дизъюнктивной нормальной формой
Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных
Конъюнктивной нормальной формой
4. Представление логических функций в виде СДНФ (СКНФ)
5. Нахождение сокращенной ДНФ по таблице истинности (карты Карно)
6. Полиномы Жегалкина
7. Суперпозиция функций. Замыкание набора функций.Замкнутые классы функций. Полные наборы. Базисы
K; вместо любой переменной можно поставить функцию из набора K
K называется замкнутым
Неизбыточный полный набор функций называется базисом
К является проверка того, что через функции из этого набора выражаются функции другого полного набора (можно проверить, что чере
Т0 – это набор всех тех логических функций, которые на нулевом наборе принимают значение 0 (Т
М – класс монотонных
S – класс самодвойственных
К входили в один из перечисленных классов, то и все суперпозиции, а значит, и замыкание набора входило бы в этот класс и класс К
8. Некоторые приложения теории булевых функций
8.1. Функциональные элементы и схемы
S также является схемой; в) если S
Соединение S конечного числа функциональных элементов является схемой тогда и только тогда, когда выполнены
1 при данных значениях переключателей, если через нее проходит ток, в противном случае мы считаем, что она принимает значение 0
8.2. Решение логических задач с помощью теории булевых функций
Элементы теории графов
9. Общие понятия теории графов
Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер). Контур –
Граф называется связным, если любые две его вершины можно соединить маршрутом (или путем).
10. Эйлеровы и полуэйлеровы графы
Доказательство леммы.
11. Матрицы и графы. Нахождение путей и сечений с помощью структурной матрицы
Матрица смежности
Матрица инциденций
Структурная матрица.
Сечением (разрезом)
12. Сети, потоки в сетях. Теорема Форда – Фалкерсона
Потоком в сети между вершиной t
А называется величиной
Y образуется следующим образом: источник t
Y закончено (к нему нельзя добавить новых вершин), возможны 2 случая. 1. Сток (т. е. вершина с номером s)
13. Раскраска графа
Задача. Раскрасить вершины графа так, чтобы любые две смежные вершины были раскрашены в разные
G, найдем в нем какую-либо МНС, которую обозначим S
14. Деревья и их простейшие свойства
15. Решение типовых задач
L (в соответствии с разд. 3) ставим над L
S, затем вычеркиваем из нее 4-ю строчку и 2-й столбец (тем самым получаем минор М
16. Индивидуальные задания
17. Дополнительные задачи
18. Вопросы для самопроверки
