Минимизация логических функций
Минимизация
Минимальная нормальная форма
Метод непосредственных преобразований
Метод непосредственных преобразований
Тупиковая форма
Законы логики
1. Идемпотентность
2. Коммутативность
3. Ассоциативность
4. Дистрибутивность
5. Закон двойного отрицания
6. Законы поглощения
7. Законы де Моргана
8. Закон исключённого третьего
9. Закон противоречия
10. Свойства тавтологии и противоречия
11. Законы склеивания
12. Законы поглощения
Пример
Пример
Пример
Пример
Пример
Пример
Проблема
Карты Вейча-карно
Эдвард Вестбрук Вейч
Морис Карно
Карта Карно
Код Грея
Пример
Пример
Пример
Пример
Пример
Пример
Пример
Правила
Правила
Правила
Правила
Пример
Пример ‒ МДНФ
Пример ‒ МКНФ
Пример
Формула
Пример
Пример
Пример
Недостатки
Метод Квайна и Мак-Класки
Виллард ван Орман Куайн
Эдвард Дж. Мак-Класки
Метод Квайна и Мак-Класки
450.79K
Категория: МатематикаМатематика

Минимизация логических функций. Вычислительная техника

1. Минимизация логических функций

Вычислительная техника

2. Минимизация

упрощение формы записи
схема реализуется с наименьшим
числом элементов

3. Минимальная нормальная форма

Нормальная форма логической
функции, содержащая наименьшее
число элементов
Минимальная ДНФ = МДНФ
Минимальная КНФ = МКНФ
Логическая функция может иметь
несколько МДНФ или МКНФ
одинаковой сложности

4.

Методы
минимизации
Непосредственных
преобразований
Карно-Вейча
Квайна и
Мак-Класки

5. Метод непосредственных преобразований

Минимизация логических функций
МЕТОД
НЕПОСРЕДСТВЕННЫХ
ПРЕОБРАЗОВАНИЙ

6. Метод непосредственных преобразований

Применение законов алгебры логики
Результат тупиковая форма
логической функции

7. Тупиковая форма

Логическое выражение, к слагаемым
которого больше не могут быть
применены операции склеивания
Для одной функции может существовать
несколько тупиковых форм
Минимальная форма тупиковая
форма логической функции
минимальной длины

8.

Функции a и b называются
равносильными, если при
одинаковых входных данных
они принимают одинаковые
значения
a b

9. Законы логики

ЗАКОНЫ
ЛОГИКИ

10. 1. Идемпотентность

a & a a
a a a

11. 2. Коммутативность

a & b b &a
a 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) a

15. 6. Законы поглощения

a & (a b) a
a (a & b) a

16. 7. Законы де Моргана

(a b) a & b
(a & b) a b

17. 8. Закон исключённого третьего

a a 1

18. 9. Закон противоречия

a & a 0

19. 10. Свойства тавтологии и противоречия

1 & a a 1 a 1
0 & 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) a
a (a & b) a

22. Пример

Минимизировать СДНФ
( А В С)
(А В С)
(А В С)

23. Пример

( А В С) (А В С)
(А В С)

24. Пример

( А В С) (А В С)
(А В С)

25. Пример

( А В С) (А В С)
(А В С)

26. Пример

( А В С) (А В С)
(А В С)
( А В С) (А В С)
(А В С) (А В С)

27. Пример

( А В С) (А В С)
(А В С)
( А В С) (А В С)
(А В С) (А В С)
( В С) (А С)
С (А В)

28.

A
B
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.

A
B
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. Пример

X1
X2
F
0
0
1
1
0
1
0
1
1
0
1
1
X2
X1
0
1
0
1
0
1
1
1

37. Пример

A
B
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. Пример

B
0
0
1
1
C
0
1
1
0
0
0
1
0
0
1
0
1
1
0
A

39. Пример

BC
00
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. Пример

0
0
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. Пример

AB
CD
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. Пример

E
0
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. Пример

X1
X2
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. Пример ‒ МДНФ

X1
X2
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. Пример ‒ МКНФ

X1
X2
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. Пример

A
B
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. Пример

B
0
0
1
1
C
0
1
1
0
0
0
1
0
0
1
0
1
1
0
A

55. Пример

A
B
0
0
1
1
C
0
1
1
0
0
0
1
0
0
1
0
1
1
0
F = В С A C
МДНФ

56. Пример

A
B
0
0
1
1
C
0
1
1
0
0
0
1
0
0
1
0
1
1
0
F = С (A В)
МКНФ

57.

A
B
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
English     Русский Правила