Похожие презентации:
Минимизация логических функций. Вычислительная техника
1. Минимизация логических функций
Вычислительная техника2. Минимизация
упрощение формы записисхема реализуется с наименьшим
числом элементов
3. Минимальная нормальная форма
Нормальная форма логическойфункции, содержащая наименьшее
число элементов
Минимальная ДНФ = МДНФ
Минимальная КНФ = МКНФ
Логическая функция может иметь
несколько МДНФ или МКНФ
одинаковой сложности
4.
Методыминимизации
Непосредственных
преобразований
Карно-Вейча
Квайна и
Мак-Класки
5. Метод непосредственных преобразований
Минимизация логических функцийМЕТОД
НЕПОСРЕДСТВЕННЫХ
ПРЕОБРАЗОВАНИЙ
6. Метод непосредственных преобразований
Применение законов алгебры логикиРезультат тупиковая форма
логической функции
7. Тупиковая форма
Логическое выражение, к слагаемымкоторого больше не могут быть
применены операции склеивания
Для одной функции может существовать
несколько тупиковых форм
Минимальная форма тупиковая
форма логической функции
минимальной длины
8.
Функции a и b называютсяравносильными, если при
одинаковых входных данных
они принимают одинаковые
значения
a b
9. Законы логики
ЗАКОНЫЛОГИКИ
10. 1. Идемпотентность
a & a aa a a
11. 2. Коммутативность
a & b b &aa b b a
12. 3. Ассоциативность
a & (b & с) (a & b) & сa (b с) (a b) с
13. 4. Дистрибутивность
a & (b с) (a & b) (a & с)a (b & с) (a b) & (a с)
14. 5. Закон двойного отрицания
( a) a15. 6. Законы поглощения
a & (a b) aa (a & b) a
16. 7. Законы де Моргана
(a b) a & b(a & b) a b
17. 8. Закон исключённого третьего
a a 118. 9. Закон противоречия
a & a 019. 10. Свойства тавтологии и противоречия
1 & a a 1 a 10 & a 0 0 a a
0 1 1 0
20. 11. Законы склеивания
(a & b) (a & b) a(a b) & (a b) a
21. 12. Законы поглощения
a & (a b) aa (a & b) a
22. Пример
Минимизировать СДНФ( А В С)
(А В С)
(А В С)
23. Пример
( А В С) (А В С)(А В С)
24. Пример
( А В С) (А В С)(А В С)
25. Пример
( А В С) (А В С)(А В С)
26. Пример
( А В С) (А В С)(А В С)
( А В С) (А В С)
(А В С) (А В С)
27. Пример
( А В С) (А В С)(А В С)
( А В С) (А В С)
(А В С) (А В С)
( В С) (А С)
С (А В)
28.
AB
C
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
f
29.
AB
C
f
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
30. Проблема
Определить, какие элементарныеконъюнкции / дизъюнкции надо
склеивать
31. Карты Вейча-карно
Минимизация логических функцийКАРТЫ ВЕЙЧА-КАРНО
32. Эдвард Вестбрук Вейч
Американскийфизик
1924 — 2013
1952
«Метод диаграмм
для минимизации
логических
функций»
33. Морис Карно
Американскийфизик
1953
Усовершенствовал
метод Вейча
род. 1924
34. Карта Карно
Графическое представлениетаблицы истинности
логических функций
n
Таблица, содержащая по 2
прямоугольных ячеек,
где n — число логических
переменных
35. Код Грея
система счисления, в которой двасоседних значения различаются
только в одном разряде
36. Пример
X1X2
F
0
0
1
1
0
1
0
1
1
0
1
1
X2
X1
0
1
0
1
0
1
1
1
37. Пример
AB
C
F
0
0
0
0
0
0
0
1
1
0
1
0
0
1
1
0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
38. Пример
B0
0
1
1
C
0
1
1
0
0
0
1
0
0
1
0
1
1
0
A
39. Пример
BC00
01
11
10
0
0
1
0
0
1
0
1
1
0
A
40.
АB
C
D
F
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
0
1
0
1
0
0
1
1
0
1
0
1
1
1
0
1
0
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
1
1
0
1
1
0
0
1
1
1
0
1
0
1
1
1
0
0
1
1
1
1
0
41. Пример
00
1
1
A
0
1
1
0
B
0
0
0
0
1
0
0
1
1
0
0
0
1
1
0
0
0
0
1
0
0
1
0
0
C
D
42. Пример
ABCD
00
01
11
10
00
0
0
1
0
01
1
0
0
0
11
0
0
0
0
10
0
1
0
0
43. Пример
E0
AB
1
00
01
11
10
10
11
01
00
00
0
0
1
0
0
1
0
1
CD 01
1
0
0
0
0
0
0
0
11
0
0
0
0
0
0
0
1
10
0
1
0
0
1
0
0
0
44. Правила
ДНФ КНФ1. Объединяем смежные клетки с
единицами (нулями) в максимально
возможные области, содержащие 2n
клеток
2. В области НЕ должно находиться
клеток, содержащих нули (единицы)
3. Области могут пересекаться
4. Возможно несколько вариантов
покрытия
45. Правила
5. Крайние строки и столбцы являютсясоседними между собой
46. Правила
6.Несмежные области, расположенныесимметрично оси(ей), могут
объединяться в одну
E
0
AB
1
00
01
11
10
10
11
01
00
00
0
1
1
0
0
1
1
1
CD 01
1
0
0
0
0
0
0
0
11
0
0
0
0
0
0
0
1
10
0
1
0
0
1
0
0
0
47. Правила
7. Для каждой области записываемконъюнкцию (дизъюнкцию)
переменных, не изменяющих своё
значение
Если неизменная переменная равна
нулю (единице) инвертируем
8.Конъюнкции (дизъюнкции) областей
объединяем дизъюнкцией
(конъюнкцией).
48. Пример
X1X2
F
0
0
1
1
0
1
0
1
1
0
1
1
F = X2 X1
X2
X1
0
1
0
1
0
1
1
1
49. Пример ‒ МДНФ
X1X2
F
0
0
1
1
0
1
0
1
0
1
1
0
X2
X1
0
1
0
0
1
1
1
0
F = X1 X2 X1 X2
50. Пример ‒ МКНФ
X1X2
F
0
0
1
1
0
1
0
1
0
1
1
0
X2
X1
0
1
0
0
1
1
1
0
F = (X1 X2) ( X1 X2)
51. Пример
AB
C
F
0
0
0
0
0
0
0
1
1
0
1
0
0
1
1
0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
52. Формула
( А В С)(А В С)
(А В С)
Совершенная дизъюнктивная
нормальная форма (СДНФ)
53.
(А В С)(А В С)
(А В С)
( А В С)
( А В С)
Совершенная конъюнктивная
нормальная форма (СКНФ)
54. Пример
B0
0
1
1
C
0
1
1
0
0
0
1
0
0
1
0
1
1
0
A
55. Пример
AB
0
0
1
1
C
0
1
1
0
0
0
1
0
0
1
0
1
1
0
F = В С A C
МДНФ
56. Пример
AB
0
0
1
1
C
0
1
1
0
0
0
1
0
0
1
0
1
1
0
F = С (A В)
МКНФ
57.
AB
C
f
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
58. Недостатки
Применим для функций до 7переменных
Выбор областей ‒ визуально
Нет алгоритма, обеспечивающего
оптимальное решение
59. Метод Квайна и Мак-Класки
Минимизация логических функцийМЕТОД КВАЙНА И
МАК-КЛАСКИ
60. Виллард ван Орман Куайн
Американскийфилософ, логик и
математик
1908 — 2000
1993
премия Рольфа
Шока в области
логики и
философии
61. Эдвард Дж. Мак-Класки
Почётный профессорСтэнфордского
университета.
Пионер в области
электротехники
1908 — 2000
Первый алгоритм
проектирования
комбинационных
схем
62. Метод Квайна и Мак-Класки
целесообразно, когда число входныхпеременных превышает 6 – 7