- •Ахметова Наиля Абдулхамитовна
- •Введение
- •1. Элементы комбинаторики
- •1.1. Перестановки. Размещения. Сочетания
- •Теорема.
- •1.2. Задачи по комбинаторике
- •2. Функции алгебры логики
- •2.1. Элементарные функции алгебры логики
- •Пример 2.
- •2.2. Формульное задание функций алгебры логики
- •Упрощение записи формул:
- •Теорема о замене подформул на эквивалентные
- •Некоторые свойства элементарных функций
- •Следствия из свойств элементарных функций
- •Пример 3:
- •2.3 Принцип двойственности
- •Пример 1. Покажем с помощью таблицы истинности, что константа 0 двойственна к 1:
- •Пример 3. Покажем, что функция х1х2 двойственна к x1&x2, функция х1х2 двойственна к функции x1|x2.
- •Принцип двойственности
- •Лемма о несамодвойственной функции
- •2.4 Разложение булевой функции по переменным
- •Теорема о разложении функции по переменным
- •2.5. Полнота, примеры полных систем
- •Полные системы
- •Представление функции в виде полинома Жегалкина
- •Теорема Жегалкина
- •2.6. Замыкание и замкнутые классы
- •Важнейшие замкнутые классы в р2
- •Теорема Поста о полноте
- •Примеры использования теоремы Поста.
- •3. Составим критериальную таблицу для другой полной системы функций из р2: {0, 1,x1x2,x1x2}.
- •Теорема о достаточности четырех функций.
- •2.7. Функции k - значной логики
- •Теорема о полной в Рk системе функций
- •2.8. Задачи и упражнения по функциям алгебры логики
- •1. Построить таблицы соответствующих функций, выяснить, эквивалентны ли формулы и :
- •2. Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей:
- •3. Минимизация булевых функций
- •3.1. Минимизация нормальных форм
- •Алгоритм Квайна построения сокращенной днф.
- •Метод Блейка
- •Алгоритм построения сокращенной днф с помощью кнф (метод Нельсона)
- •Построение всех тупиковых днф.
- •Алгоритм минимизации функций в классе днф
- •Алгоритм минимизации функций в классе кнф
- •Алгоритм минимизации функций в классе нормальных форм
- •3.2 Минимизация частично определенных функций
- •Алгоритм минимизации частично определенных функций в классе днф
- •Алгоритм минимизации частично определенных функций в классе кнф
- •Метод минимизирующих карт Карно
- •3.3 Задачи по минимизации и доопределению булевых функций
- •4. Логика высказываний
- •4.1. Введение в логику высказываний
- •4.2. Задачи по алгебре высказываний
- •Список литературы
Алгоритм минимизации функций в классе кнф
Чтобы построить все минимальные КНФ (МКНФ) функцииf, следует построить все МДНФ функцииfи взять от каждой из них отрицание, для чего заменить знаки & на, ана & ( сохранив первоначальное распределение скобок) и над каждой буквой поставить знак отрицания. Полученные КНФ для функцииfбудут минимальными. В самом деле, если бы дляfсуществовала КНФ с меньшим числом букв, то ее отрицание дало бы дляf ДНФ с меньшим числом букв, чем в любой из минимальных ДНФ дляf. Противоречие с их минимальностью.
Алгоритм минимизации функций в классе нормальных форм
Пусть f– функция алгебры логики.
1. Строим все МДНФ функции f.
2. Строим все МКНФ функции f.
3. Из построенных минимальных форм выбираем простейшие ( по числу букв).
Пример 6. В классе нормальных форм минимизировать функциюf=(01011110).
1. Строим СДНФ для функции f:
2. Строим сокращенную ДНФ функции f:
3. Строим матрицу покрытий (таблица 3.6).
Таблица 3.6
-
N
ПИ
xy z x y z xyz xy z x yz
1
2
3
4
x z
y z
xy
xz
+ +
+ +
+ +
+ +
Решеточное выражение E= ( 12 ) 1 (34 ) 4 = 134124.
4. Строим все тупиковые ДНФ функции f:
5. Обе построенные ТДНФ являются минимальными.
6. Повторяем эти этапы для функции f.
СДНФ :
Сокращенная ДНФ :
Строим матрицу покрытий (таблица 3.7).
Таблица 3.7
-
N
ПИ
xyz x yz x y z
1
2
xz
x y z
+ +
+
Решеточный многочлен E= 112 = 12. Единственная тупиковая ДНФ (она же минимальная) для функции Минимальная КНФ функции Из построенных МДНФ и МКНФ выбираем простейшую
Пример 7.В классе нормальных форм минимизировать функциюf=(11011011).
1. СДНФ:
2. Сокращенная ДНФ : =
3. Строим матрицу покрытий (таблица 3.8).
Таблица 3.8
-
N
ПИ
xyz xy z x y z xyz x yz x y z
1
2
3
4
5
6
x y
xz
yz
x z
y z
xy
+ +
+ +
+ +
+ +
+ +
+ +
E= ( 36 ) ( 46 ) ( 45 ) ( 23 ) ( 12 ) ( 15 ) = 124613561342562345.
4. Тупиковые ДНФ функции f:
5. Минимальные ДНФ функции f:
6. Повторяем указанные выше этапы для функции f.
СДНФ :
Сокращенная ДНФ :
Построенная сокращенная ДНФ функции fявляется для нее тупиковой и минимальной .
Минимальная КНФ функции
Построенные МДНФ и МКНФ имеют одно и то же число букв; все они составляют минимальные формы для f: