Булева алгебра и основы теории графов

Контрольная работа по ОЛУ для направления.151900
Тема1. Булева алгебра
1) Доказать тождество
___ _ _______ _ _ _
х1х2х3?х2(х1?х3)?х2=х1?х2?х3
2) Привести выражения к формам ДНФ и КНФ
_________
_ _ ________
а) х1?х2х3?х2? (х1?х3) х2
_____________
б) х1?х2?х3(х1?х2)?х3
с) .
3) Минимизировать функции по картам Карно-Вейча
х1х2х3х4 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 f1 1 1 0 1 0 0 1 0 1 1 0 0 0 1 1 0 f2 1 0 0 1 0 0 1 0 0 1 1 1 1 0 1 0 х1х2х3 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 f3 1 0 0 0 1 1 1 0 f4 0 1 1 0 1 0 0 1
4) Минимизировать функции, заданные конституентами единицы или нуля по методу Квайна - Мак Класки:
f1=(1,3,5,7,8,10,14,15)|1; f2=(0,2,4,5,6,7,13,15)|0
ВОПРОСЫ ДЛЯ ЗАЧЕТА по теме 1 1. Булева алгебра: булевы функции, определение, способы задания. 2. Основные законы алгебры логики
3. Нормальные формы булевых функций. Алгоритм приведения к нормальным
формам.
4. Совершенные формы булевых функций. Предельное разложение Шеннона
5. Минимизация булевых функций. Карты Карно-Вейча.
6. Метод Квайна – Мак Класки
Тема2. Основы теории графов
1. Построить на графике исходные множества
a. А={(x,y)|(x,y)?R2, x2 + y2?16
b. B={(x,y)|(x,y)?R2, y?x2 + 4
c. C={(x,y)|(x,y)?R2, y?-x - 4
Определить для этих множеств
i. A?B?C
ii. (A\C)?(C\B)
iii. A?B? A?C
iv. B\A\C
2.Что будет результатом декартова квадрата и куба множеств
A={0,1,2,3,4,5,6,7,8,9}, В={0,1,2}
Сколько в каждом из 4-х полученных множеств одно-, двух- и трехразрядных чисел.
3.Построить граф G1 по матрице смежности. Определить тип графа.
d. Построить на G минимальное покрывающее дерево G2.
e. Определить количество пустых подграфов в G1
f. Определить хроматическое число и количество полных подграфов в G1
g. Удалить из G1 вершину с максимальной локальной степенью для получения G3. Определить тип графа G3.
h. На вершинах 1, 2, 3,6 построить подграф G4. Построить для него матрицу кратчайших расстояний D, определить компоненту сильной связности
a b c
a d e f
b d
e k l
f m
l m
ВОПРОСЫ ДЛЯ ЗАЧЕТА по теме 2
1. Понятие множества. Способы задания множеств.
2. Основные операции на множествах.
3. Отношения строгого и не строгого включения
4. Декартово произведение множеств
5. Понятие графа как бинарного отношения на множестве
6. Матричные описания графа
7. Типы графов
8. Характеристические числа графа
9. Определение расстояний в графе
10. Определение компонент связности и сильной связности
11. Алгоритм построения минимального покрывающего дерева
12. Алгоритм определения пустого подграфа. Разрезы в графе
13. Алгоритмы определения полного подграфа
. СПИСОК ЛИТЕРАТУРЫ
Основная литература
1. Горбатов В.А. Фундаментальные основы дискретной м