Булева алгебра (1023551), страница 5
Текст из файла (страница 5)
, (10)
, 11)
. (12)
В выражении (9), записанном в СДНФ, пять слагаемых по три буквы в каждом, а всего 15 букв и три инвертора, в то время как в выражении (10) три слагаемых по две буквы в каждом, а всего 6 букв и три инвертора. Выражение (10) является минимальной дизъюнктивной формой данной ФАЛ.
| Таблица 5 | ||||
| № | x2 | x1 | x0 | y |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 1 |
| 4 | 1 | 0 | 0 | 1 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 1 | 0 | 1 |
| 7 | 1 | 1 | 1 | 0 |
В выражении (11), записанном в СКНФ, три сомножителя по три буквы в каждом, а всего 9 букв и три инвертора, в то время как в выражении (12) два сомножителя по две и три буквы, а всего 5 букв и три инвертора. Выражение (12) является минимальной конъюнктивной формой данной ФАЛ.
Применяя скобочные формы и формы с групповыми инверсиями, выражения (10) и (12) можно еще упростить:
(13)
где 5 букв и два инвертора.
(14)
где 5 букв и один инвертор.
В настоящее время в теории проектирования логических схем наиболее полно исследованы именно задачи минимизации дизъюнктивных и конъюнктивных нормальных форм, обеспечивающих рациональное решение при синтезе комбинационных схем, на входах которых доступны как переменные, так и их инверсии. Парафазное представление переменных легко обеспечивается, если они снимаются с выходов триггеров, используемых в качестве запоминающих ячеек разрабатываемых цифровых устройств.
Справедливости ради надо отметить, что сформулированная выше задача минимизации ФАЛ являлась чрезвычайно актуальной в тот период времени, когда разработка цифровых устройств велась на электромеханических переключательных элементах, дискретных радиокомпонентах и интегральных схемах малой степени интеграции.
Достигнутые в настоящее время схемотехнологические успехи в микроэлектронике, в частности, создание схем средней, большой и сверхбольшой интеграции, таких как мультиплексоры, постоянные запоминающие устройства (ПЗУ), программируемые логические матрицы (ПЛМ) и другие разновидности программируемых логических интегральных схем, позволяют реализовать очень сложные системы ФАЛ практически, используя один корпус, без каких-либо процедур минимизации.
Учитывая, что такие БИС дороги, требуют сложной аппаратно‑программной поддержки для их программирования, а очень часто в инженерной практике решаются более простые задачи, рассмотрим вопросы минимизации ФАЛ, остановившись на некоторых, нашедших наибольшее распространение, методах минимизации ФАЛ.
К настоящему времени разработаны и находят применение следующие методы минимизации:
1. Расчетный метод (метод непосредственных преобразований).
2. Расчетно-табличный метод (метод Квайна-МакКласки).
3. Метод Петрика (развитие метода Квайна-МакКласки).
4. Табличный метод (карты Карно).
5. Метод гиперкубов.
6. Метод факторизации.
7. Метод функциональной декомпозиции.
Первый метод применяется при числе переменных n <= 3 и основан на использовании операций склеивания, поглощения и развертывания (см. ниже).
Второй и третий методы используются при n ≤ 16 в профессиональных разработках и ориентированы на использование САПР с применением ЭВМ.
Четвертый метод является самым распространенным инженерным методом минимизации ФАЛ для n ≤ 6.
Пятый метод, основанный на геометрическом представлении, удобен только для n ≤ 3. При n = 4 геометрическое представление уже довольно сложное, поэтому применение этого метода весьма ограниченное.
Шестой метод не имеет каких-либо существенных достижений при решении общих задач, более простых, чем метод перебора всех формул ФАЛ даже для n = 3. Практически он используется для уменьшения сложности минимальных ДНФ и КНФ, полученных с использованием первого или четвертого методов. Он основан на использовании скобочных форм и форм с групповыми инверсиями.
Седьмой метод основан на представлении ФАЛ, зависящей от n переменных, в виде суперпозиций функций, зависящих от меньшего числа переменных, для которых можно применить перечисленные выше методы.
Исходной формой для большинства методов являются либо таблица истинности, либо одна из совершенных форм: СДНФ или СКНФ. Если ФАЛ задана в другом виде, то предполагается, что она сначала переводится в СДНФ или СКНФ с использованием основных законов булевой алгебры.
Далее будут рассмотрены первый и четвертый методы минимизации ФАЛ, представленной в СДНФ.
При выполнении процедур канонической минимизации большую роль играют понятия импликанты и простой импликанты ФАЛ.
Булева функция 
называется импликантой булевой функции 
, если на любом наборе значений переменных 
, на котором значение функции ‘Z’ равно 1, значение функции ‘Y’ также равно 1.
Простой импликантой функции ‘y’ называется всякое элементарное произведение 
, являющееся импликантой функции ‘Y’ и такое, что никакая его собственная часть (то есть произведение, полученное из произведения ‘Z’ выбрасыванием одного или нескольких сомножителей 
) уже не является импликантой функции ‘y’. Так как в дальнейшем будут использоваться только простые импликанты, опустим слово “простые”, то есть если в тексте встречается понятие “импликанта”, то надо помнить, что имеется в виду “простая импликанта”.
Прежде чем переходить к изложению методов минимизации ФАЛ, приведем правила склеивания, поглощения и развертывания, на которых, собственно, и основана минимизация ФАЛ.
Правила склеивания
Правило склеивания для элементарных произведений следует из распределительного закона первого рода, закона дополнительности и закона универсального множества:
логическую сумму двух соседних произведений ранга r можно заменить одним элементарным произведением ранга r-1, являющимся общей частью исходных слагаемых.
Пример: y = x2
1 0+x2 1x0 = x2 1( 0+x0) = x2 1.1 = x2 1.
Правило склеивания для элементарных сумм следует из распределительного закона второго рода, закона дополнительности и закона нулевого множества:
логическое произведение двух соседних сумм некоторого ранга r можно заменить одной элементарной суммой ранга r-1, являющейся общей частью исходных сомножителей.
Пример: y = ( 2+x1+ 0)(x2+x1+ 0) = (x1+ 0)+ 2x2 = (x1+ 0)+0 = x1+ 0.
Правило поглощения
Правило поглощения для суммы двух элементарных произведений следует из распределительного закона первого рода и законов универсального множества:
логическую сумму двух элементарных произведений разных рангов, из которых одно является составной частью другого, можно заменить произведением, имеющим меньший ранг.
Пример: y = x3 1+x3 2 1x0 = x3 1(1+ 2x0) = x3 1.1 = x3 1.
Правило поглощения для произведения элементарных сумм следует из распределительного закона второго рода и законов нулевого множества:
логическое произведение двух элементарных сумм разных рангов, из которых одна является составной частью другой, можно заменить элементарной суммой, имеющей меньший ранг.
Пример: y = ( 3+ 1)( 3+ 2+ 1+x0) =( 3+ 1+0)( 3+ 2+ 1+x0) =
( 3+ 1)+0( 2+x0) = ( 3+ 1)+0 = 3+ 1.
Правило развертывания
Это правило определяет действие обратное склеиванию.
Правило развертывания элементарного произведения в логическую сумму элементарных произведений большего ранга (в пределе до r = n, т.е. до конституент единицы, как и будет рассмотрено ниже) следует из законов универсального множества, распределительного закона первого рода и производится в три этапа:
- в развертываемое элементарное произведение ранга r вводится в качестве сомножителей n-r единиц, где n - ранг конституенты единицы;
- каждая единица заменяется логической суммой некоторой, не имеющейся в исходном элементарном произведении переменной и ее отрицания: xi+ i = 1;
- производится раскрытие всех скобок на основе распределительного закона первого рода, что приводит к развертыванию исходного элементарного произведения ранга r в логическую сумму 2n-r конституент единицы.
Пример: развернуть элементарное произведение x3 1 в логическую сумму конституент единицы, зависящих от 4-х переменных. Последнее следует из того, что максимальный индекс у переменной равен 3; отсутствуют переменные x2 и x0.
Решение: x3 1 = x3.1. 1.1 = x3(x2+ 2) 1(x0+ 0) =
(x3x2 1+x3 2 1)(x0+ 0) = x3x2 1x0+x3 2 1x0+x3x2 1 0+x3 2 1 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
