lec05
.pdf
Кафедра Прикладной математики Института информационных технологий РТУ МИРЭА
Дисциплина
«Математическая логика и теория алгоритмов»
2022-2023 уч.г.
Наполнение курса
Объем курса
16 лекционных и 8 практических занятий
Темы лекционных занятий
1.Элементы теории множеств. Булева алгебра
2.Булевы вектора и булевы функции
3.ДНФ, СДНФ, КНФ, СКНФ
4.Минимизация ДНФ
5.Метод Карно и метод Квайна
6.Двойственные функции
7.Функциональная полнота. Полные классы. Алгебра Жегалкина.
8.Замкнутые классы функций: монотонные, самодвойственные, сохраняющие const.
9.Теорема Поста
10.Исчисление высказываний
11.Исчисление предикатов. Основные положения. Кванторы
12.Нормальные формы. Доказательства
13.Конечные автоматы
14.Соединения и синтез автоматов
15.Машина Тьюринга
16.ЧРФ и НАМ
2
Лекция 5.
Метод Карно и метод Квайна.
5.1.Метод Карно.
5.2.Метод Квайна.
Часть 1.
Метод Карно.
Основные принципы.
Карта Карно - ТИ в формате для наглядной ручной минимизации. Работа по минимизации - ДНФ (либо КНФ) ведётся с клетками карты, где находятся единицы (или нули), соответственно. Каждая единица соответствует одному конъюнкту СДНФ, а каждый ноль — одному дизъюнкту СКНФ.
Карты Карно - развертка Bn на плоскость, где вершина гиперкуба взаимно однозначно соответствует одной клетке карты. Графически карта Карно - прямоугольник или квадрат из ячеек, число которых равно 2n, причем любые две соседние ячейки по вертикали или горизонтали описывают термы, различающиеся только по одной переменной — с логическим отрицанием и без логического отрицания (расстояние Хэмминга между термами соседних ячеек равно 1). Также соседним являются первая и последняя строки, крайний левый и крайний правый столбцы таблицы.
5
Развертка карты Карно на тороид.
Развертка логического гиперкуба B4 на поверхность тороида.
6
Алгоритм минимизации ДНФ картой Карно.
Алгоритм минимизации ДНФ без изменений.
Образовывать макс интервалы покрытия (склеивать) можно только прямоугольные области с числом 1 (нулей), являющимся целой степенью двойки (1, 2, 4, 8, 16, 32… клетки).
В общем случае 2n термов, принадлежащие одной n-мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются n переменных.
7
Минимизация ДНФ в B2 картой Карно.
Пример 5.1.
БФ из примера 4.3: (x,y) = (1101)
x |
y |
f |
|
0 |
1 |
|
|
0 |
0 |
1 |
x\y |
|
|||
0 |
1 |
1 |
|
||||
0 |
1 |
1 |
|||||
1 |
0 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
||||
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
ДНФmin = . r=2.
8
Минимизация ДНФ в B3 картой Карно.
Пример 5.2.
БФ из примера 4.6: (x1,x2,x3) = (0000 1111)
x1\x2x3 |
00 |
01 |
11 |
10 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1
ДНФmin = 1. r=1.
9
Минимизация ДНФ в B4 картой Карно.
Найти min ДНФ (x1,x2,x3,x4), n = 4.
Пример 5.3.
Найти min ДНФ БФ.
(x1,x2,x3,x4) задает γ = (1011 0101 0010 0101).
Составление карты Карно:
10