ВУЗ:
Составители:
33
2. Запишем кубические комплексы:
K
0
= (111, 101, 110, 100),
K
1
= (1-1, 1-0, 11-, 10-),
K
2
= (1--).
3. Выделим три покрытия и запишем соответствующие им ДНФ:
П
1
= (1-1, 1-0)
→
0202
)( xxxxxz
+
=
П
2
= (11-, 10-)
→
1212
)( xxxxxz
+
=
П3= (1--)
→
2
)( xxz =
Последнее покрытие является покрытием минимальной стоимости и ему
соответствует МДНФ. Легко видеть, что этому покрытию соответствует область из
четырех клеток, объединяющая единичные значения ФАЛ и расположенная в центре
карты Вейча.
При объединении нулевых значений функции максимальная область
соответствует 2-кубу (0--), для которого
2
)( xxz =
или
2
)( xxz
=
. В обоих случаях
для минимальной ФАЛ получено одно и то же выражение.
Пример 4.3. Минимизировать ФАЛ
012012012012012
)( xxxxxxxxxxxxxxxxz
+
++
+
=
.
Решение. 1. Составим карту Вейча.
1
x
1
x
1
x
1
x
0
x
1 1 1 1
0
x
0 0 1 0
2
x
2
x
2
x
2
x
2. Запишем покрытие минимальной стоимости для единичных значений ФАЛ:
П
1
= (--1, 10-) или
120
)( xxxxz
+
= .
3. Запишем покрытие минимальной стоимости для нулевых значений ФАЛ:
П
2
= (-10, 0-0) или
0201
)( xxxxxz
+
= .
4. Воспользовавшись теоремами Де-Моргана (2.9) и тождеством (2.5), найдем:
()()
(
)
(
)
0201120102010201
)( xxxxxxxxxxxxxxxxxz +⋅+=+⋅+=⋅=+=
.
Согласно второму закону дистрибутивности (2.8) получим ФАЛ вида
120
)( xxxxz += .
Очевидно, что обе функции
z(x) одинаковы.
Из последнего примера видно, что при минимизации по нулевым и
единичным значениям функции первоначально можно определить равносильные, но
не всегда одинаковые выражения. Различной будет и их техническая реализация.
Используя основные тождества и теоремы алгебры логики, их можно преобразовать к
единому виду. Однако такое преобразование не всегда очевидно и требует
достаточного навыка. Поэтому для нахождения наиболее простого технического
решения желательно проводить минимизацию как для нулевых, так и для единичных
значений ФАЛ и из полученных значений выбирать простейшее.
34
Следует еще раз отметить, что так как карты Вейча для ФАЛ трех и четырех
переменных являются объемными фигурами, то при формировании областей на
таких
картах могут объединятся крайние столбцы и строки, а на карте четырех переменных
также четыре угловых клетки (рис. 4.5).
4.2.2. Минимизация недоопределенной функции алгебры логики
Напомним, что недоопределенной называется ФАЛ, значения которой заданы не на
всех наборах входных переменных. Существуют факультативные (не обязательные)
значения функции на неоговоренных (запрещенных) входных кодах. Поэтому при
минимизации недоопределенной ФАЛ ее факультативные значения доопределяются
произвольно из условия получения на карте Вейча наименьшего числа максимально
больших областей, что приводит к получению покрытия минимальной стоимости и
простейшей технической реализации.
Пример 4.4. Минимизировать ФАЛ, заданную следующей таблицей истинности:
x
2
x
1
x
0
z(x)
0 0 0 -
0 0 1 0
0 1 0 1
0 1 1 -
1 0 0 1
1 0 1 -
1 1 0 -
1 1 1 1
Решение. 1. Составим исходную карту Вейча и выполним несколько возможных ее
доопределений. Карта исходной функции имеет вид:
1
x
1
x
1
x
1
x
0
x
- 1 - 0
0
x
1 - 1 -
2
x
2
x
2
x
2
x
2. Запишем выражения для единичных значений ФАЛ:
012012012
)( xxxxxxxxxxz
+
+
=
.
Допустим z(000) = 1 и z(110) = 1, тогда карта Вейча примет вид:
1
x
1
x
1
x
1
x
0
x
-
1 - 0
0
x
1 1 1 1
2
x
2
x
2
x
2
x
120
)( xxxxz
+
=
2. Запишем кубические комплексы: Следует еще раз отметить, что так как карты Вейча для ФАЛ трех и четырех
K0= (111, 101, 110, 100), переменных являются объемными фигурами, то при формировании областей на таких
K1= (1-1, 1-0, 11-, 10-), картах могут объединятся крайние столбцы и строки, а на карте четырех переменных
K2= (1--). также четыре угловых клетки (рис. 4.5).
3. Выделим три покрытия и запишем соответствующие им ДНФ: 4.2.2. Минимизация недоопределенной функции алгебры логики
П1= (1-1, 1-0) → z ( x) = x2 x0 + x2 x0 Напомним, что недоопределенной называется ФАЛ, значения которой заданы не на
всех наборах входных переменных. Существуют факультативные (не обязательные)
П2= (11-, 10-) → z ( x) = x2 x1 + x2 x1 значения функции на неоговоренных (запрещенных) входных кодах. Поэтому при
минимизации недоопределенной ФАЛ ее факультативные значения доопределяются
П3= (1--) → z ( x ) = x2 произвольно из условия получения на карте Вейча наименьшего числа максимально
Последнее покрытие является покрытием минимальной стоимости и ему больших областей, что приводит к получению покрытия минимальной стоимости и
соответствует МДНФ. Легко видеть, что этому покрытию соответствует область из простейшей технической реализации.
четырех клеток, объединяющая единичные значения ФАЛ и расположенная в центре
Пример 4.4. Минимизировать ФАЛ, заданную следующей таблицей истинности:
карты Вейча.
При объединении нулевых значений функции максимальная область x2 x1 x0 z(x)
соответствует 2-кубу (0--), для которого z ( x ) = x2 или z ( x) = x2 . В обоих случаях 0 0 0 -
для минимальной ФАЛ получено одно и то же выражение. 0 0 1 0
0 1 0 1
Пример 4.3. Минимизировать ФАЛ
0 1 1 -
z ( x) = x2 x1 x0 + x2 x1 x0 + x2 x1 x0 + x2 x1 x0 + x2 x1 x0 . 1 0 0 1
Решение. 1. Составим карту Вейча. 1 0 1 -
x1 x1 x1 x1 1 1 0 -
1 1 1 1
x0 1 1 1 1
Решение. 1. Составим исходную карту Вейча и выполним несколько возможных ее
x0 0 0 1 0
доопределений. Карта исходной функции имеет вид:
x2 x2 x2 x2
2. Запишем покрытие минимальной стоимости для единичных значений ФАЛ: x1 x1 x1 x1
П1= (--1, 10-) или z ( x) = x0 + x2 x1 . x0 - 1 - 0
3. Запишем покрытие минимальной стоимости для нулевых значений ФАЛ: x0 1 - 1 -
П2= (-10, 0-0) или z ( x) = x1 x0 + x2 x0 . x2 x2 x2 x2
4. Воспользовавшись теоремами Де-Моргана (2.9) и тождеством (2.5), найдем:
z ( x) = x1 x0 + x2 x0 = x1 x0 ⋅ x2 x0 = (x1 + x0 )⋅ (x2 + x1 ) = ( x1 + x0 ) ⋅ ( x2 + x0 ) . 2. Запишем выражения для единичных значений ФАЛ:
Согласно второму закону дистрибутивности (2.8) получим ФАЛ вида
z ( x) = x2 x1 x0 + x2 x1 x0 + x2 x1 x0 .
Допустим z(000) = 1 и z(110) = 1, тогда карта Вейча примет вид:
z ( x) = x0 + x2 x1 .
Очевидно, что обе функции z(x) одинаковы. x1 x1 x1 x1
Из последнего примера видно, что при минимизации по нулевым и -
x0 1 - 0
единичным значениям функции первоначально можно определить равносильные, но
не всегда одинаковые выражения. Различной будет и их техническая реализация.
Используя основные тождества и теоремы алгебры логики, их можно преобразовать к x0 1 1 1 1
единому виду. Однако такое преобразование не всегда очевидно и требует
достаточного навыка. Поэтому для нахождения наиболее простого технического
x2 x2 x2 x2
решения желательно проводить минимизацию как для нулевых, так и для единичных
значений ФАЛ и из полученных значений выбирать простейшее. z ( x) = x0 + x2 x1
33 34
Страницы
- « первая
- ‹ предыдущая
- …
- 15
- 16
- 17
- 18
- 19
- …
- следующая ›
- последняя »
