- •Ахметова Наиля Абдулхамитовна
- •Введение
- •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(x1, …,xn) есть функция алгебры логики.
1. Построим СДНФ функции f, и пустьP1,P2, …,Pnесть ее коституенты единицы).
2. Построим сокращенную ДНФ функции, fи пустьK1,K2, …,Km– ее простые импликанты.
3. Построим матрицу покрытий простых импликант функции fее конституентами единицы (табл. 3.4), полагая, что
+, если каждый множитель в Kiявляется множителем вPj; (Pjестьaij= часть дляKi);
в противном случае.
Таблица 3.4
-
N
P1P2…Pj …Pn
K1
K2
Ki
Km
a11 a12 … a1j …a1n
a21 a22 … a2j … a2n
ai1 ai2 … aij … ain
am1 am2… amj … amn
4. Для каждого столбца j( 1j n) найдем множествоEj всех тех номеровIстрок, для которыхaij = 1. Пусть Составим выражение Назовем его решеточным выражением. Это выражение можно рассматривать как формулу, построенную в свободной дистрибутивной решетке с образующими 1, 2, …,mи с операциями & и.
5. В выражении Aраскроем скобки , приведя выражениеAк равносильному выражению где перечислены все конъюнкции элементы которой взяты из скобок 1,2,…,nсоответственно в выраженииA.
6. В выражении Bпроведем все операции удаления дублирующих членов и все операции поглощения. В результате получим дизъюнкцию элементарных конъюнкцийC.
Утверждение. Каждая элементарная конъюнкцияi1&i2&…&irвСдает ТДНФ дляf. Все ТДНФ для функцииfисчерпываются элементарными конъюнкциями в выраженииС.
Пример 5.Сокращенная ДНФ для функцииf= (1111010010101111) имеет вид
Для функции fпостроим все минимальные ДНФ.
1. Строим матрицу покрытий (таблица 3.5).
Таблица 3.5
-
Конституенты единицы функции f
N
ПИ
x xx x x x x x x x x
y y y y y y y y y y y
z z z z z z z z z z z
t t t t t t t t t t t
1
2
3
4
5
6
x y
xy
yt
xt
xz t
yz t
+ + + +
+ + + +
+ + + +
+ + + +
+ +
+ +
2. Строим решеточное выражение (по столбцам таблицы).
E= (23)(25)(23)2(56)(34)(34)(14)(16)(14)(1) = (23)(25)(56)(34)(14)(16)12 = (56)(34)(1)(2) = 1235124512361246.
3. Строим все тупиковые ДНФ функции f:
простые импликанты 1,2,3,5;
простые импликанты 1,2,4,5;
простые импликанты 1,2,3,6;
простые импликанты 1,2,4,6.
4. Все найденные ТДНФ являются минимальными ДНФ.
Алгоритм минимизации функций в классе днф
1. Строим СДНФ функции f.
2. Строим сокращенную ДНФ функции f.
3. С помощью матрицы покрытий и решеточного выражения строим все ТДНФ функции f.
4. Среди построенных ТДНФ выбираем все минимальные дизъюнктивные нормальные формы функции f.