blob: 5e65c0f1d585ccd1a772364ad289e4d2e8e80d6a (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
---
id: jxbgbq
date: 2026-07-20T15:20:55+0300
languages: [ru]
aliases:
reviews:
tags:
- draft
- knowledge
---
# Минимизация функций алгебры логики
Минимизация ФАЛ - это процесс преобразования логической функции к более простому виду с сохранением
её значений. Основная цель минимизации - уменьшить количество логических элементов, входов и
соединений в цифровой схеме.
В результате этих алгоритмов получаются ТДНФ или ТКНФ - тупиковые формы, которые не представляется
возможность минимизировать дальше. Для получения МДНФ или МКНФ (минимальных ДНФ и КНФ) необходимо
отсматривать все возможные ТДНФ и ТКНФ и сравнивать их с помощью матрицы покрытия.
Основные методы минимизации:
1. Алгебраический метод
Основан на применении законов булевой алгебры - логических эквивалентностей.
Основной сутью является "склеивание" термов - создание из двух термов одного засчёт логической
эквивалентности, убирающей необходимость в одной из переменных.
В ходе этого алгоритма получаются СкДНФ или СкКНФ - сокращённые ДНФ и КНФ - они содержат все простые
имкликанты данной булевой функции.
Пример:
$F = \overline{A}B + AB = B(\overline{A} + A) = B$
Недостатки:
- Много шагов для минимизации
- Часто можно не прийти к минимальной форме из-за различных вариантов склеивания
2. Карты Карно
Самый распространённый метод для функций до 5-6 переменных (при большем количестве переменных метод
становится слишком трудоёмким для человека).
На карту наносятся значения функции в определённом порядке. Далее однозначные соседние клетки
объединяются в группы размером степени 2 (1, 2, 4 и т.д.). Для получения ТДНФ склеивают единицы, для
ТКНФ склеивают нули и инвертируют переменные в термах.
Преимущества:
- Прост для использования человеком
3. Метод Квайна - Мак-Класки
Используется для большого числа переменных. Применяется в программах синтеза логических схем.
Алгоритм:
1. Записать все минтермы
2. Сгруппировать по числу единиц в терме
3. Объединить термы отличающиеся одной переменной
4. Перегруппировать по количеству склеенных переменных
5. Повторять шаги 3, 4 пока есть возможность
6. Выбрать минимальный набор импликант
Преимущества:
- Подходит для автоматизации процесса минимизации
## Up
- [Алгебра логики](c5oolf)
## Related
- [Карты Карно (диаграммы Вейча)](5t4nfg)
|
