1. Постановка задачи

Используя язык высокого уровня Pascal, минимизируем функцию методом минимизирующих карт для трёх переменных.

2. Краткие теоретические сведения

Этот метод по существу представляет собой тот же метод неопределенных коэффициентов, только записанный в более удобной форме.

Рассмотрим следующую таблицу

(3)

Эта таблица служит более компактной записью системы уравнений (1) метода неопределенных коэффициентов, где вместо коэффициентов в соответствующей клетке записываются сами конъюнкции. Каждая строка таблицы (3) заменяет собою соответственно 1-ое, 2-ое, …… 8-ое уравнения системы (1). Дизъюнкция всех элементов строки таблицы есть значение функции в вершине, определяемой соответствующими переменными. Так, первая строка есть значение функции в вершине , четвертая в или в переводе на координаты соответственно в (1, 1, 1), (1, 0, 0).

Можно показать, что если в СДНФ данной функции не входит какая-либо из восьми конъюнкций последнего столбца, то в минимальную форму этой функции не может входить ни одна из конъюнкций соответствующей строки таблицы.

Пусть, например, в СДНФ не входит конъюнкция , тогда в минимальную форму не входит, например, член (аналогично и другие конъюнкции 3-ей строки):

Таким образом, если бы в минимальную форму входил член , то обязательно входил бы член , что противоречит предположению.

Таблица (3) называется минимизирующей картой.

Минимизация функции производится по следующим правилам:

1. Все строки таблицы, которые соответствуют конъюнкциям последнего столбца, отсутствующим в СДНФ данной функции, вычеркивают.

2. В столбцах оставшихся строк вычеркивают все элементы, попавшие в вычеркнутые строки.

3. В каждой из невычеркнутых строк выбирают незачеркнутую конъюнкцию, содержащую минимальное число знаков (желательно, чтобы выбранные конъюнкции встречались чаще во всех оставшихся строках).

4. Взяв по одной конъюнкции для всех незачеркнутых строк и записав их дизъюнкцию, получают минимальную форму.

Заметим, что нахождение МДНФ неоднозначно, ибо произволен выбор минимальных конъюнкций в строках. Однако, все получаемые по этому методу МДНФ будут “одинаково минимальны”.

3. Алгоритм (входные данные, выходные данные)

С клавиатуры вводятся значения функции.

Если значение первой функции равно нулю, то всем элементам функции присваиваем нули. И т.д. для всех функций.

Производим проверку. Если в первой строчке равен нулю, то во всех остальных строчках присваиваем значение нуля. И т.д. для всех строчек и всех элементов.

Выводим результат на экран.

4. Анализ результатов

Результаты получились верные. Правильность результатов проверена другими методами.

5. Вывод

Методы минимизирующих карт приводят к громоздким записям (число строк таблицы для функции переменных равно , а число столбцов ). Использование этих методов уже для порядка 8-10 становится затруднительным.

6. Приложение (листинг программы)

uses crt;

var a : array[1..256] of integer;

i,j,c: integer;

procedure zap(p,p1,p2:integer);

begin

if a[p]=1 then

for j:=p1 to p2 do

a[j]:=1;

end;

procedure x123(var c1,c2,c3,c4,c5,c6,c7,c8:integer);

begin

if (c1=0) or (c2=0) or (c3=0) or (c4=0) then

begin

c5:=0; c6:=0; c7:=0; c8:=0;

end;

end;

procedure x456(var c1,c2,c3,c4:integer);

begin

if (c1=0) or (c2=0) then

begin

c3:=0;

c4:=0;

end;

end;

procedure vvv;

begin

if c=1 then

write(' v ');

if c=0 then

inc(c);

end;

procedure vivod1(c1:integer;t:string);

begin

if c1=1 then

begin

vvv;

write(t);

inc(j);

end;

end;

procedure vivod2(c1:integer;t:string);

begin

if (j=1) and (c1=1) then

begin

vivod1(c1,t);

inc(j);

end;

end;

begin

clrscr;

writeln('Metod minimiziryushih kart:');

writeln;

for i:=1 to 8 do

begin

writeln('Vvedite rezultat funkcii ', i,':');

readln(a[i]);

end;

c:=a[8]; a[8]:=a[1]; a[1]:=c;

c:=a[7]; a[7]:=a[2]; a[2]:=c;

c:=a[6]; a[6]:=a[3]; a[3]:=c;

c:=a[5]; a[5]:=a[4]; a[4]:=c;

writeln;

writeln('f(x1,x2,x3) =');

if (a[1]=1) and (a[2]=1) and (a[3]=1) and (a[4]=1) and (a[5]=1) and

(a[6]=1) and (a[7]=1) and (a[8]=1) then

begin

write('1');

exit;

end;

zap(1,9,14);

zap(2,15,20);

zap(3,21,26);

zap(4,27,32);

zap(5,33,38);

zap(6,39,44);

zap(7,45,50);

zap(8,51,56);

j:=0;

c:=0;

x123(a[1],a[2],a[3],a[4],a[9],a[15],a[21],a[27]); {x1}

x123(a[5],a[6],a[7],a[8],a[33],a[39],a[45],a[51]); {notx1}

x123(a[1],a[2],a[5],a[6],a[10],a[16],a[34],a[40]); {x2}

x123(a[3],a[4],a[7],a[8],a[22],a[28],a[46],a[52]); {notx2}

x123(a[1],a[3],a[5],a[7],a[11],a[23],a[35],a[47]); {x3}

x123(a[2],a[4],a[6],a[8],a[17],a[29],a[41],a[53]); {notx3}

x456(a[1],a[2],a[12],a[18]); {x1,x2}

x456(a[3],a[4],a[24],a[30]); {x1,notx2}

x456(a[5],a[6],a[36],a[42]); {notx1,x2}

x456(a[7],a[8],a[48],a[54]); {notx1,notx2}

x456(a[1],a[3],a[13],a[25]); {x1,x3}

x456(a[2],a[4],a[19],a[31]); {x1,notx3}

x456(a[5],a[7],a[37],a[49]); {notx1,x3}

x456(a[6],a[8],a[43],a[55]); {notx1,notx3}

x456(a[1],a[5],a[14],a[38]); {x2,x3}

x456(a[2],a[6],a[20],a[44]); {x2,notx3}

x456(a[3],a[7],a[26],a[50]); {notx2,x3}

x456(a[4],a[8],a[32],a[56]); {notx2,notx3}

vivod1(a[9],'x1');

vivod1(a[33],'not(x1)');

vivod1(a[10],'x2');

vivod1(a[22],'not(x2)');

vivod1(a[11],'x3');

vivod1(a[17],'not(x3)');

vivod2(a[12],'x1x2');

vivod2(a[24],'(x1)not(x2)');

vivod2(a[36],'not(x1)x2');

vivod2(a[48],'not(x1)not(x2)');

vivod2(a[13],'x1x3');

vivod2(a[19],'(x1)not(x3)');

vivod2(a[37],'not(x1)x3');

vivod2(a[43],'not(x1)not(x3)');

vivod2(a[14],'x2x3');

vivod2(a[20],'(x2)not(x3)');

vivod2(a[26],'not(x2)x3');

vivod2(a[32],'not(x2)not(x3)');

vivod2(a[1],'x1x2x3');

vivod2(a[2],'x1x2notx3');

vivod2(a[3],'x1notx2x3');

vivod2(a[4],'x1notx2notx3');

vivod2(a[5],'notx1x2x3');

vivod2(a[6],'notx1x2notx3');

vivod2(a[7],'notx1notx2x3');

vivod2(a[8],'notx1notx2notx3');

readkey;

end.

25