Записать формулу функции 𝑓(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 1
1 0 1 1
1 1 0 1
1 1 1 1
Решение
Геометрический метод минимизации.
Записываем СДНФ заданной функции:
fx1,x2,x3СДНФ=x1x2x3⋁x1x2x3⋁x1x2x3⋁x1x2x3⋁x1x2x3⋁x1x2x3.
Строим единичный трехмерный куб, в котором выделяем вершины, соответствующие единичным наборам функции.
221170518415022345651841502211705178435224980522415522498052241551663065216535 111
28670253175022117058509016097253175000160972548895286702516510221170585090160972531750286702533655221170586995160972533655224980510985516859251022351678305102235225742586995293560594615167068594615 011 101 110
2867025256540
2893695000221170562230160972562230`
00`
1609725717552265045641352257425102235167068594615 001 010 100
2211705172720002211705174625
000
Четыре вершины 010, 011, 110 и 111 образуют грань куба, которая соответствует переменной x2. Другие четыре вершины 111, 110, 100 и 101 образуют грань куба, которая соответствует переменной x1.
Записываем минимальную ДНФ функции:
fx1,x2,x3МДНФ=x1⋁x2.
Метод неопределенных коэффициентов.
Составим систему равнений.
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=1;
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⋁K2310⋁K123010=1;
K21⋁K1201⋁K2311⋁K123011=1;
K11⋁K1210⋁K1310⋁K123100=1;
K11⋁K1210⋁K1311⋁K123101=1;
K11⋁K21⋁K1211⋁K1310⋁K2310⋁K123110=1;
K11⋁K21⋁K1211⋁K1311⋁K2311⋁K123111=1.
Выбираем K21 и K11. Все остальные коэффициенты приравняем к нулю. Отсюда минимальная форма заданной функции имеет вид:
fx1,x2,x3МДНФ=x2⋁x1.
Метод минимизирующих карт.
Этот метод по существу представляет собой тот же метод неопределённых коэффициентов, только записанный в более удобной форме.
Для функции трёх переменных составляется следующая таблица.
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
Минимизация функции производится по следующим правилам:
Все строки таблицы, которые соответствуют конъюнкциям последнего столбца, отсутствующим в СДНФ данной функции, вычеркивают.
В столбцах оставшихся строк вычеркивают все элементы, попавшие в вычеркнутые строки.
В каждой из невычеркнутых строк выбирают незачеркнутую конъюнкцию, содержащую минимальное число знаков (желательно, чтобы выбранные конъюнкции встречались чаще во всех оставшихся строках).
Взяв по одной конъюнкции для всех незачеркнутых строк и записав их дизъюнкцию, получают минимальную форму.
Выполняем вычёркивания.
x1
-68580847 x2
x3
x1x2
x1x3
x2x3
x1x2x3
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
-64135-1693x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
x1
x2
x3
x1x2
x1x3
x2x3
x1x2x3
x1
-685803598x2
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, x1 и получаем:
fx1,x2,x3МДНФ=x2⋁x1.
Все ответы, полученные ранее, одинаковы.
Метод Квайна.
Имеем:
fx1,x2,x3СДНФ=x1x2x3⋁x1x2x3⋁x1x2x3⋁x1x2x3⋁x1x2x3⋁x1x2x3.
Составляем таблицу склеиваний.
1 x1x2x3* x1x2(1,2)* x2
2 x1x2x3* x2x32,6* x1
3 x1x2x3
x1x23,4*
4 x1x2x3* x1x34,6*
5 x1x2x3* x1x2(5,6)*
6 x1x2x3* x2x3(1,5)*
Повторно получаемые конъюнкции не записываем.
Звездочкой помечены конъюнкции, которые участвовали в склеивании
Задать вопрос
на новый заказ в Автор24.
