Записать формулу функции 𝑓(x1,x2,x3) и минимизировать её геометрическим методом, методами неопределённых коэффициентов, минимизирующих карт, Квайна, Квайна – Мак-Класки, карт Карно. Сравнить результаты.
x1 x2 x3 f(x1,x2,x3)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Решение
Геометрический метод минимизации.
Записываем СДНФ заданной функции:
fx1,x2,x3СДНФ=x1x2x3⋁x1x2x3⋁x1x2x3⋁x1x2x3⋁x1x2x3.
Строим единичный трехмерный куб, в котором выделяем вершины, соответствующие единичным наборам функции.
221170518415022345651841502211705178435224980522415522498052241551663065216535 111
28670253175022117058509016097253175000160972548895286702516510221170585090160972531750286702533655221170586995160972533655224980510985516859251022351678305102235225742586995293560594615167068594615 011 101 110
2867025256540
221170562230160972562230`
00`
1609725717552265045641352257425102235167068594615 001 010 100
2211705172720002211705174625
000
Четыре вершины 010,011,110 и 111 образуют грань куба, которая соответствует переменной x2. Две другие вершины с вершинами, образующими грань, лежат на ребре куба 101,111, которым соответствуют конъюнкции и x1x3.
Записываем минимальную ДНФ функции:
fx1,x2,x3МДНФ=x2⋁x1x3.
Метод неопределенных коэффициентов.
Составим систему равнений.
f0,0,0=K10⋁K20⋁K30⋁K1200⋁K1300⋁K2300⋁K123000=0;
f0,0,1=K10⋁K20⋁K31⋁K1200⋁K1301⋁K2301⋁K123001=0;
f0,1,0=K10⋁K21⋁K30⋁K1201⋁K1300⋁K2310⋁K123010=1;
f0,1,1=K10⋁K21⋁K31⋁K1201⋁K1301⋁K2311⋁K123011=1;
f1,0,0=K11⋁K20⋁K30⋁K1210⋁K1310⋁K2300⋁K123100=0;
f1,0,1=K11⋁K20⋁K31⋁K1210⋁K1311⋁K2301⋁K123101=1;
f1,1,0=K11⋁K21⋁K30⋁K1211⋁K1310⋁K2310⋁K123110=1;
f1,1,1=K11⋁K21⋁K31⋁K1211⋁K1311⋁K2311⋁K123111=1.
Ясно, что коэффициенты в равнениях, равных нулю, также равны нулю
. Поэтому, удаляем такие коэффициенты из всех уравнений. Получаем систему:
K21⋁K1201⋁K1300⋁K2310⋁K123010=1;
K21⋁K1201⋁K2311⋁K123011=1;
K1311⋁K123101=1;
K21⋁K1211⋁K2310⋁K123110=1;K21⋁K1211⋁K1311⋁K2311⋁K123111=1.
В новой системе выбираем K21, K1311. Все остальные коэффициенты приравняем к нулю. Отсюда минимальная форма заданной функции имеет вид:
fx1,x2,x3МДНФ=x2⋁x1x3.
Метод минимизирующих карт.
Этот метод по существу представляет собой тот же метод неопределённых коэффициентов, только записанный в более удобной форме.
Для функции трёх переменных составляется следующая таблица.
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
Минимизация функции производится по следующим правилам:
Все строки таблицы, которые соответствуют конъюнкциям последнего столбца, отсутствующим в СДНФ данной функции, вычеркивают.
В столбцах оставшихся строк вычеркивают все элементы, попавшие в вычеркнутые строки.
В каждой из невычеркнутых строк выбирают незачеркнутую конъюнкцию, содержащую минимальное число знаков (желательно, чтобы выбранные конъюнкции встречались чаще во всех оставшихся строках).
Взяв по одной конъюнкции для всех незачеркнутых строк и записав их дизъюнкцию, получают минимальную форму.
Выполняем вычёркивания.
794385-4445x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
x1
x2
x3
x1x2
-64135-10160 x1x3
x2x3
x1x2x3
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
7943850x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
Последовательно выбираем x2, x1x3 и получаем:
fx1,x2,x3МДНФ=x2⋁x1x3.
Все ответы, полученные ранее, одинаковы.
Метод Квайна.
Имеем:
fx1,x2,x3СДНФ=x1x2x3⋁x1x2x3⋁x1x2x3⋁x1x2x3⋁x1x2x3.
Составляем таблицу склеиваний.
1 x1x2x3* x1x2(1,2)* x2
2 x1x2x3* x2x32,3*
3 x1x2x3* x1x3(3,5)
4 x1x2x3* x1x2(4,5)*
5 x1x2x3* x2x3(1,4)*
Повторно получаемые конъюнкции не записываем.
Звездочкой помечены конъюнкции, которые участвовали в склеивании