Теорема 2.1.1 о минимальном допределении частично определенной функции.
Минимальная ДНФ ЧОФ f(хn) есть самая короткая дизъюнкция простых наборов единичного доопределения f1(хn), которые в совокупности покрываются всеми единицами нулевого доопределения f0(хn).
Смысл утверждения теоремы заключается в следующем:
1)наиболее короткие простые наборы {P}1 имеет функция f1(хn)(так как у неё в векторе истинности максимально возможное число единиц),
2) минимально возможное число единиц в векторе значений (которые характеризуются элементарными наборами {N}0) имеет функция f0(хn), поэтому
3) минимальную ДНФ следует выбирать из всех тупиковых ДНФ, у которых простые наборы {P}1 покрываются элементарными наборами {N}0 .
Из теоремы вытекает следующий алгоритм построения минимального дополнения частично определенной функции f(х n):
1. Определяем СДНФ, СкДНФ и простые наборы {P}1= {P1, ... , Pm }1 единичного доопределения функции f1(хn).
2. Строим элементарные наборы {N}0 = {N1, ..., Nk}0 нулевого доопределения функции f0(х n) .
3. Формируем матрицу покрытий А простых наборов {P}1 элементарными наборами {N}0 .
4. Строим по единичным элементам столбцов j = 1, …, k матрицы А дизьюнкции Dj и решеточное выражение В = D1 &…& Dk.
5. Раскрывая в В все скобки и производя сокращения, находим для заданной ЧОФ все ТДНФ аналогично обычным функциям.
6. Из множества всех ТДНФ выбираем МДНФ, которая будет равна искомому минимальному доопределению g. Неизвестные значения истинности исходной ЧОФ определяем непосредственной подстановкой соответствующих наборов переменных в полученную МДНФ либо по ее полной таблице истинности.
Пример. Найти минимальное доопределение частично определенной функции ¦=(1?10?1??) .
Решение.Переменные функции обозначим через x, y, z. Применим метод покрытий.
1. Вначале строим СДНФ единичного доопределения ¦1=(11101111):
f1= `x`y` z Ú `x`y z Ú `x y` z Ú x`y` z Ú x` y z Ú x y`z Ú x y z.
Применяя правила алгоритма Куайна, получаем СкДНФ:
f1= x`y Ú`x` z Ú `y` z Ú` y z Ú y`z Ú x`y Ú x` z Ú x z Ú x y = xÚ`y Ú`z .
Простые наборы единичного доопределения ¦1 следующие: P1= (х), P2=(y), P3= (z), m = 3.
2. Элементарные наборы функции нулевого доопределения f0= (10100100):
N1 = (x,`y,`z), N2 = (x, y,`z), N3 = (x,`y, z), k=3.
3. Матрица покрытий простых наборов Р1, Р2, Р3 функции ¦1элементарными наборами N1, N2, N3 функции ¦0 имеет вид:
| N1 | N2 | N3 | |
| Р1 | |||
| Р2 | |||
| Р3 |
4. Решеточное выражение, задающее все варианты вхождения простых наборов в элементарные: В = (2Ú 3)& 3 & (1Ú 2).
5. Раскрываем скобки: В=(23Ú33)&(1Ú 2)=3&(1Ú 2)=13Ú 23.
6. В итоге получим две тупиковых ДНФ. В первую входят простые наборы P1 и P3, во вторую – P2и P3:
¦ 1 = х Ú`z , ¦2 = `y Ú`z.
Поскольку первая функция имеет только одно отрицание, примем её в качестве искомого доопределения g. Столбец истинности ее имеет вид: g = (10101111). Таким образом, в минимальном доопределении на наборах с номерами 1, 4, 6, 7 должны стоять, соответственно, значения 0, 1, 1, 1.
Алгоритмы, аналогичные рассмотренному для ДНФ, могут быть применены и для других форм.
ЗАДАЧИ
1. Найти минимальное доопределение частично определенных функций:
а) (??1011?0); б)(10??011?); в)(?1?011?0); г)(?00??11?);д) (011??1??01??0?1?); е) (?1?110?1?001?10?); ж) (?0011?0?1?0?1?11).
КОНТРОЛЬНЫЕ ЗАДАНИЯ ПО ТЕМЕ
Дата добавления: 2015-10-05; просмотров: 893;