Записать формулу функции 𝑓(x1,x2,x3) и минимизировать её геометрическим методом, методами неопределённых коэффициентов, минимизирующих карт, Квайна, Квайна – Мак-Класки, карт Карно. Сравнить результаты.
x1 x2 x3 f(x1,x2,x3)
0 0 0 1
0 0 1 1
0 1 0 0
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⋁x1x2x3.
Строим единичный трехмерный куб, в котором выделяем вершины, соответствующие единичным наборам функции.
2211705178435224980522415522498052241551663065216535 111
286702533655221170586995160972533655224980510985516859251022351678305102235225742586995293560594615167068594615 011 101 110
1609725717552265045641352257425102235167068594615 001 010 100
2211705174625
000
Четыре вершины 001,011,101 и 111 образуют грань куба, которая соответствует переменной x3. Две другие вершины с вершинами, образующими грань, лежат на ребре куба 000,001 и 110,111, которым соответствуют конъюнкции x1x2 и x1x2.
Записываем минимальную ДНФ функции:
fx1,x2,x3МДНФ=x1x2⋁x3⋁x1x2.
Метод неопределенных коэффициентов.
Составим систему равнений.
f0,0,0=K10⋁K20⋁K30⋁K1200⋁K1300⋁K2300⋁K123000=1;
f0,0,1=K10⋁K20⋁K31⋁K1200⋁K1301⋁K2301⋁K123001=1;
f0,1,0=K10⋁K21⋁K30⋁K1201⋁K1300⋁K2310⋁K123010=0;
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.
Ясно, что коэффициенты в равенствах, равных нулю, также равны нулю
. Поэтому, удаляем такие коэффициенты из всех уравнений, а именно, K10=K21=K30=K1201=K1300=K2310=K123010=K11=K20=K1210=K1310=K2300=K123100=0. Получаем систему:
K1200⋁K123000=1;
K31⋁K1200⋁K1301⋁K2301⋁K123001=1;
K31⋁K1301⋁K2311⋁K123011=1;
K31⋁K1311⋁K2301⋁K123101=1;
K1211⋁K123110=1;
K31⋁K1211⋁K1311⋁K2311⋁K123111=1.
В новой системе выбираем K1200, K31 и K1211. Все остальные коэффициенты приравняем к нулю. Отсюда минимальная форма заданной функции имеет вид:
fx1,x2,x3МДНФ=x1x2⋁x3⋁x1x2.
Метод минимизирующих карт.
Этот метод по существу представляет собой тот же метод неопределённых, только записанный в более удобной форме.
Для функции трёх переменных составляется следующая таблица.
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
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
Последовательно выбираем x3, x1x2 и x1x2 и получаем:
fx1,x2,x3МДНФ=x1x2⋁x3⋁x1x2.
Все ответы, полученные ранее, одинаковы.
Метод Квайна.
Имеем:
fx1,x2,x3СДНФ=x1x2x3⋁x1x2x3⋁x1x2x3⋁x1x2x3⋁x1x2x3⋁x1x2x3.
Составляем таблицу склеиваний.
1 659130-5080x1x2x3* x1x2(1,2)
-48895-5080x3
2 x1x2x3* x1x3(2,3)*
3 x1x2x3* x2x3(2,4)*
4 x1x2x3* x2x3(3,6)*
5 x1x2x3* x1x3(4,6)*
6 65913010795x1x2x3* x1x2(5,6)
Звездочкой помечены конъюнкции, которые участвовали в склеивании
Задать вопрос
на новый заказ в Автор24.
