1. Постановка задачи
Используя язык высокого уровня Pascal, минимизируем функцию методом Квайна-Мак-Класки для трёх переменных.
2. Краткие теоретические сведения
Этот
метод является модернизацией метода
Квайна (его 1-го этапа). Мак-Класки
предложил записывать исходные импликанты
данной функции, заданной в СДНФ, в виде
их двоичных кодов (каждому члену ставится
в соответствие по известному правилу
его собственная вершина). Все множество
так записанных импликант разбивается
по числу единиц в их кодах на группы.
При этом в
-ю
группу войдут коды, имеющие в своей
записи
единиц. Попарное сравнение импликант
достаточно производить только между
соседними группами, т.к. только эти
группы отличаются одним знаком в кодах
входящих в них членов. Сравнивая коды
членов соседних групп, образуют члены
низшего ранга. На месте исключенного
знака пишут в них “тире”. Затем всю
совокупность членов низшего ранга снова
разбивают на группы по местоположению
знака “тире”.Снова сравнивают члены
соседних групп, но уже внутри групп,
образуя члены низшего ранга по тому же
правилу и т.д.
Далее все производится по методу Квайна, но в кодовых значениях импликант. Рассмотрим это на примере 6.
Заменим исходные импликанты их кодами в двоичных переменных: 0011, 0100, 0101, 0111, 1001, 1011, 1100, 1101.
Разобьем коды исходных импликант на группы, поместим их в таблицу. Далее применим закон склеивания к членам соседних групп, перебирая каждый член 1-й группы со всеми членами 2-й группы и т.д.
Можно все это сразу делать в таблице.
Данная функция |
Результаты 1-го склеивания |
Результаты 2-го склеивания |
|||||
Коды |
группы |
Коды |
группы |
Коды |
группы |
||
0011 |
0-я |
- |
0-11 |
1-я |
- |
- 10- |
|
0100 |
1-я |
0100 * |
-011 |
|
-100 * |
|
|
0101 |
2-я |
0011 * |
010- |
|
-101 * |
|
|
0111 |
|
0101 * |
100 |
2-я |
0 |
|
|
1001 |
|
1001 * |
01-1 |
|
1 |
|
|
1011 |
|
1100 * |
-101 |
3-я |
0 |
|
|
1100 |
3-я |
0111 * |
10-1 |
|
1 |
|
|
1101 |
|
1011 * |
1-01 |
4-я |
010- * |
|
|
|
|
1101 * |
110- |
|
110- * |
|
|
011
-11
-01
1-1
0-1
Далее строится таблица меток, но в нее вписываются исходные и первичные импликанты в виде двоичных кодов. Обратите внимание, что первичные импликанты записаны в другом порядке (согласно их группам), поэтому таблица меток выглядит иначе, чем в примере 6.
|
0100 |
0011 |
0101 |
1001 |
1100 |
0111 |
1011 |
1101 |
-011 |
|
v |
|
|
|
|
v |
|
0-11 |
|
v |
|
|
|
v |
|
|
1-01 |
|
|
|
v |
|
|
|
v |
01-1 |
|
|
v |
|
|
v |
|
|
10-1 |
|
|
|
v |
|
|
v |
|
-10- |
v |
|
v |
|
v |
|
|
v |
Обработка таблицы меток производится по методу Квайна.
Окончательно получаем минимальную форму данной функции
.
3. Алгоритм (входные данные, выходные данные)
С клавиатуры вводятся значения функции.
Присваиваются значения функции.
Производим склеивание.
Записываем результат.
4. Анализ результатов
Результаты получились верные. Правильность результатов проверена другими методами.
5. Вывод
Метод Квайна-Мак-Класки существенно упрощает использование метода для функций с большим количеством аргументов и значительно уменьшает вероятность появления ошибки на этапе выполнения преобразований.
6. Приложение (листинг программы)
uses crt;
var a : array[1..256] of integer;
i,k1,k2,k3:integer;
begin
clrscr;
writeln('Metod Kvaina-Mak-Klaski dl9 3-x peremennix:');
writeln;
for i:=1 to 8 do
begin
writeln('Vvedite rezultat funkcii ', i,':');
readln(a[i]);
end;
if a[1]=1 then
begin
a[9]:=0; a[10]:=0; a[11]:=0;
end;
if a[2]=1 then
begin
a[12]:=0; a[13]:=0; a[14]:=1;
end;
if a[3]=1 then
begin
a[15]:=0; a[16]:=1; a[17]:=0;
end;
if a[4]=1 then
begin
a[18]:=0; a[19]:=1; a[20]:=1;
end;
if a[5]=1 then
begin
a[21]:=1; a[22]:=0; a[23]:=0;
end;
if a[6]=1 then
begin
a[24]:=1; a[25]:=0; a[26]:=1;
end;
if a[7]=1 then
begin
a[27]:=1; a[28]:=1; a[29]:=0;
end;
if a[8]=1 then
begin
a[30]:=1; a[31]:=1; a[32]:=1;
end;
{-------vtoroi etap------------------}
if (a[1]=a[2]) and (a[1]=1) then
begin
a[33]:=0; a[34]:=0; a[35]:=7;
end;
if (a[1]=a[3]) and (a[1]=1) then
begin
a[36]:=0; a[37]:=7; a[38]:=0;
end;
if (a[1]=a[5]) and (a[1]=1) then
begin
a[39]:=7; a[40]:=0; a[41]:=0;
end; {a[2]}
if (a[2]=a[4]) and (a[2]=1) then
begin
a[42]:=0; a[43]:=7; a[44]:=1;
end;
if (a[2]=a[6]) and (a[2]=1) then
begin
a[45]:=7; a[46]:=0; a[47]:=1;
end; {a[3]}
if (a[3]=a[4]) and (a[3]=1) then
begin
a[48]:=0; a[49]:=1; a[50]:=7;
end;
if (a[3]=a[7]) and (a[3]=1) then
begin
a[51]:=7; a[52]:=1; a[53]:=0;
end; {a[5]}
if (a[5]=a[6]) and (a[5]=1) then
begin
a[54]:=1; a[55]:=0; a[56]:=7;
end;
if (a[5]=a[7]) and (a[5]=1) then
begin
a[57]:=1; a[58]:=7; a[59]:=0;
end; {a[4]}
if (a[4]=a[8]) and (a[4]=1) then
begin
a[60]:=7; a[61]:=1; a[62]:=1;
end; {a[6]}
if (a[6]=a[8]) and (a[6]=1) then
begin
a[63]:=1; a[64]:=7; a[65]:=1;
end; {a[7]}
if (a[7]=a[8]) and (a[7]=1) then
begin
a[66]:=1; a[67]:=1; a[68]:=7;
end;
{-------tretii etap------------------}
if (a[39]=7) and (a[45]=7) then
begin
a[69]:=7; a[70]:=0; a[71]:=7;
end;
if (a[39]=7) and (a[51]=7) then
begin
a[72]:=7; a[73]:=7; a[74]:=0;
end;
if (a[45]=7) and (a[60]=7) then
begin
a[75]:=7; a[76]:=7; a[77]:=1;
end;
if (a[51]=7) and (a[60]=7) then
begin
a[78]:=7; a[79]:=1; a[80]:=7;
end; {grup 2}
if (a[37]=7) and (a[43]=7) then
begin
a[81]:=0; a[82]:=7; a[83]:=7;
end;
if (a[37]=7) and (a[58]=7) then
begin
a[84]:=7; a[85]:=7; a[86]:=1;
end;
if (a[43]=7) and (a[64]=7) then
begin
a[87]:=7; a[88]:=7; a[89]:=1;
end;
if (a[58]=7) and (a[64]=7) then
begin
a[90]:=1; a[91]:=7; a[92]:=7;
end; {grup 3}
if (a[35]=7) and (a[50]=7) then
begin
a[93]:=0; a[94]:=7; a[95]:=7;
end;
if (a[35]=7) and (a[50]=7) then
begin
a[96]:=0; a[97]:=7; a[98]:=7;
end;
if (a[35]=7) and (a[56]=7) then
begin
a[99]:=7; a[100]:=0; a[101]:=7;
end;
if (a[50]=7) and (a[68]=7) then
begin
a[102]:=7; a[103]:=1; a[104]:=7;
end;
if (a[56]=7) and (a[68]=7) then
begin
a[105]:=1; a[106]:=7; a[107]:=7;
end;
{-------chetvertii etap------------------}
writeln('Rezultat: ');
i:=0;
if (a[69]=7) or (a[99]=7) then
begin
write('NOT(x2)');
inc(i);
end;
if (a[72]=7) or (a[84]=7) then
begin
if i=1 then
write(' v ');
if i=0 then
inc(i);
write('NOT(x3)');
end;
if (a[75]=7) or (a[87]=7) then
begin
if i=1 then
write(' v ');
if i=0 then
inc(i);
write('x3');
end;
if (a[78]=7) or (a[102]=7) then
begin
if i=1 then
write(' v ');
if i=0 then
inc(i);
write('x2');
end;
if (a[82]=7) or (a[94]=7) or (a[97]=7)then
begin
if i=1 then
write(' v ');
if i=0 then
inc(i);
write('NOT(x1)');
end;
if (a[91]=7) or (a[106]=7) then
begin
if i=1 then
write(' v ');
write('x1');
end;
{-------p9tii etap------------------}
i:=0; k1:=0; k2:=0; k3:=0;
if ((a[91]=7) or (a[106]=7)) and ((a[82]=7) or (a[94]=7) or (a[97]=7)) then
begin
write(' = 1');
inc(i);
inc(k1);
end;
if ((a[78]=7) or (a[102]=7)) and ((a[69]=7) or (a[99]=7)) then
begin
if i=1 then
write(' v ');
if i=0 then
begin
write(' = ');
inc(i);
end;
inc(k2);
write('1');
end;
if ((a[75]=7) or (a[87]=7)) and ((a[72]=7) or (a[84]=7)) then
begin
if i=1 then
write(' v ');
if i=0 then
begin
write(' = ');
inc(i);
end;
inc(k3);
write('1');
end;
{-------shestoi etap------------------}
if ((k1=1) and (k1=k2)) or ((k1=1) and (k1=k3)) or ((k2=1) and (k2=k3)) then
write(' = 1');
readkey;
end.
Метод минимизирующих карт