lec04
.pdf
Кафедра Прикладной математики Института информационных технологий РТУ МИРЭА
Дисциплина
«Математическая логика и теория алгоритмов»
2022-2023 уч.г.
Наполнение курса
Объем курса
16 лекционных и 8 практических занятий
Темы лекционных занятий
1.Элементы теории множеств. Булева алгебра
2.Булевы вектора и булевы функции
3.ДНФ, СДНФ, КНФ, СКНФ
4.Минимизация ДНФ
5.Метод Карно и метод Квайна
6.Двойственные функции
7.Функциональная полнота. Полные классы. Алгебра Жегалкина.
8.Замкнутые классы функций: монотонные, самодвойственные, сохраняющие const.
9.Теорема Поста
10.Исчисление высказываний
11.Исчисление предикатов. Основные положения. Кванторы
12.Нормальные формы. Доказательства
13.Конечные автоматы
14.Соединения и синтез автоматов
15.Машина Тьюринга
16.ЧРФ и НАМ
2
Лекция 4.
Минимизация ДНФ.
4.1.Задача минимизации ДНФ.
4.2.Тривиальный алгоритм минимизации ДНФ.
4.3.Интервалы булевой функции и покрытия.
4.4.Максимальные интервалы и сокращённая ДНФ.
Часть 1.
Задача минимизации ДНФ.
Пусть элементарная конъюнкция имеет вид:
σ1 |
σ2 |
… σ |
|
|
|
1 |
2 |
|
тогда ранг конъюнкции (r или rang) – количество сомножителей в ней. Рангом ДНФ называется сумма рангов ее слагаемых (конъюнкций).
Пример 4.1.
rang ( 1 2 4) = 2 + 1 = 3
Для заданной ненулевой функции (x1,x2, … xn) минимальной называется такая ДНФ, которая имеет наименьший ранг среди всех ДНФ для f.
Пример 4.2.
(x1,x2) = 1 2 1 2 = 1 (rmin=1).
Замечание 4.1. ! Совершенная ДНФ имеет максимальный ранг.
5
Часть 2.
Тривиальный алгоритм минимизации ДНФ.
Тривиальный алгоритм минимизации ДНФ.
Порядок нахождения ДНФmin для (x1,x2, … xn):
1) Перечислить все возможные ДНФ для от n переменных в порядке возрастания их рангов:
D1, D2, … D2n, … DN
2) Последовательно проверить равенство:
D1 ?, D2 ? … и т.д.
Завершаем при выполнении первого же равенства, т.к. просматриваемая Di = Dmin.
7
Количество ДНФ для БФ n переменных.
Найдем количество ДНФ для БФ n переменных: f (x1,x2, … xi, … xn). ДНФ задаем в виде (Kj - элементарная конъюнкция):
K1 K2 … Kj … KM
а) Сколько имеется элементарных конъюнкций?
Каждой элементарной конъюнкции К можно сопоставить вектор
1, если a=(a1, a2, … ai … an), где ai 0, если
−1, если
8
Для xi - 3 возможности: xi, входят в K либо xi K, т.е. литерал для xi отсутствуетразличных векторов такого типа
N=3n
Отбрасываем случай, когда вектор имеет вид (–1, –1, …, –1), т.е. когда элементарной конъюнкции не существует – остается: N=3n –1.
б) Каждая из Kj элементарных конъюнкций может входить или нет в ДНФ – т.е. всего возможностей:
2M
Отбрасываем случай, когда Kj не входит в ДНФ для всех j (1≤j≤M):
2M – 1 = 23n 1 1
Замечание 4.2. !
Недостаток алгоритма, что надо перебирать много ДНФ.
9
Пример 4.3.
(x,y) = x y.
По ТИ в СДНФ – 3 конъюнкта:
= (r=6)
x |
y |
f |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
a) = ( ) = ( ) = ; (r=3). б) = ( ) = ( ) = ; (r=3).
По ТИ в СКНФ – 1 дизъюнкт:
; (r=2).
10