Русская вероятностная логика (стр. 5 )

Проверим достоверность прямоугольника Карно А на вышеприведённом рисунке. Прямоугольник А размещается по обе стороны от горизонтальной оси 4-го ранга. Симметричность его очевидна. Верхняя половина фигуры А симметрична относительно горизонтальной оси симметрии 1-го ранга. Так как ППК охватывает одну единственную ось симметрии, то проверка фигуры покрытия А на соответствие принципу симметрии относительно горизонтальных осей закончена.

Приступаем к проверке принципа симметрии относительно вертикальных осей симметрии. Фигура покрытия А размещается по обе стороны от вертикальной оси симметрии 4-го ранга и симметрична относительно этой оси. Левая половина фигуры А симметрична относительно оси симметрии 3-го ранга. После повторного деления левая половина фигуры покрытия оказалась симметричной относительно оси симметрии 2-го ранга. После 3-го деления ППК не охватывает ни одной оси симметрии, на этом проверка достоверности прямоугольника Карно заканчивается. Таким образом, фигура покрытия А действительно является прямоугольником Карно. Аналогично доказывается, что фигура покрытия В также является прямоугольником Карно. В результате минимизации прямоугольники А и В будут описаны следующими формулами:

a = x7x6’x1’

b = x7’x6x2.

На рисунке даны примеры фигур, не являющихся прямоугольниками Карно. Фигуры k, m и n не являются прямоугольниками Карно в силу нарушения принципа симметрии. Фигура n не симметрична относительно горизонтальной оси симметрии 2-го ранга, фигура m не симметрична относительно вертикальной оси симметрии 3-го ранга. Фигура k симметрична относительно оси симметрии 3-го ранга, но её половина не симметрична относительно оси 2-го ранга.

Поразително, что за 30 лет никто из преподавателей и «учёных» так и не освоил моего алгоритма. До сих пор плодятся неграмотные методы работы с картами Карно, в которых утверждается, что достаточно убедиться, что в фигуре покрытия 2n клеточек, чтобы считать её ПК. Фигура m содержит 8 клеточек, но не является прямоугольником Карно.

Алгоритм «НИИРТА» графической минимизации булевых функций.

1. Заполнить карту Карно нулями и единицами в соответствии с таблицей истинности или заданным алгебраическим выражением.

2. Покрыть все элементарные квадраты Карно, в которых записаны единицы, минимальным количеством фигур покрытия, каждая из которых имеет максимальную площадь.

3. Проверить каждую фигуру покрытия на соответствие принципу симметрии. В противном случае изменить контур фигуры покрытия в соответствии с принципом симметрии так, чтобы она превратилась в прямоугольник Карно.

4. Каждому прямоугольнику Карно соответствует одна импликанта, причём если в границах прямоугольника Карно какая-либо переменная принимает значения как 0 , так и 1 , то эта переменная не войдёт в импликанту.

Применим карту Карно для решения задачи 1. На рисунке дан единственный минимальный вариант решения(иногда их бывает несколько).

f = x4x1 + x4x2 + x4x3 + x3x2x1

Эти выражения представляют собой пример дизъюнктивной нормальной формы (ДНФ).

В некоторых случаях приведение результата минимизации к скобочной форме позволяет уменьшить количество интегральных схем (ИС) , необходимых для реализации булевой функции. Скобочная форма получается после вынесения общих множителей за скобки и для f имеет вид:

f = x4(x1 + x2 + x3) + x3x2x1

Кстати, полученный результат f = x4(x1 + x2 + x3) + x3x2x1 наводит на печальные размышления. На русский язык эта формула переводится так: «Абитуриент будет принят в учебное заведение, если за него проголосуют 3 члена комиссии или председатель вместе хотя бы с одним членом комиссии». Но ведь этот ответ мы могли бы получить и эвристически, на основе здравого смысла, просто немного подумав. Не пришлось бы рисовать таблицу истинности, заполнять карту Карно и т. д. Формальное решение логических задач иногда превращает нас в «мартышек с арифмометром», отвращает от мышления. Аналогичная опасность грозит и программистам, и микропрограммистам, т. е. схемотехникам.

В алгебре множеств также возможна минимизация логических функций. На рисунке представлены скалярные диаграммы, каждый столбец которых помечен соседними кодами. Фактически эти диаграммы представляют собой одномерную карту Карно, поэтому здесь применимы все вышеприведенные алгоритмы минимизации.

Вполне естественно, что результат минимизации не изменился:

f = x4(x1 + x2 + x3) + x3x2x1

1.6.Оценка сложности реализации булевых функций

Приблизительную оценку реализации логической функции можно дать по ДНФ, подсчитав коэффициент сложности Кс, равный общему количеству переменных, входящих в ДНФ, плюс количество импликант. Например, для СДНФ к задаче 1 Кс = 32+8=40, а для отминимизированной функции Кс = 9+4=13.

Для того, чтобы перейти от логической функции (ЛФ) к электронной схеме, построенной на интегральных микросхемах (ИМС) типа И-НЕ, достаточно преобразовать ЛФ по правилу де Моргана. Например:

f = x4x1 + x4x2 + x4x3 + x3x2x1 = [(x4x1)’ & (x4x2)’ & (x4x3)’ & (x3x2x1)’]’.

Из полученного уравнения видно, что для реализации его в виде электронной схемы необходимы только элементы типа И-НЕ: 3 двухвходовых элемента(2И-НЕ), один трёхвходовой элемент(3И-НЕ) и один четырёхвходовой элемент(4И-НЕ). При этом нужно иметь в виду, что в одном корпусе ИМС могут быть размещены 4 элемента И-НЕ, 3 элемента 3И-НЕ, 2 элемента 4И-НЕ или 1 элемент 8И-НЕ. В наше время отпала необходимость в реализации ЛФ на элементах типа И-НЕ, поэтому можно сразу рисовать схему на элементах И и ИЛИ. Кроме того, применение программируемых интегральных схем (ПЛИС) вообще снимает проблему реализации: достаточно представить лишь готовую формулу ЛФ. Минимизация по таблицам истинности в САПР для ПЛИС зачастую оказывается неэффективной, поэтому советую иногда проверять результаты минимизации при работе в САПР.

При использовании базиса И-НЕ обе функции примут вид, представленный на рисунке. Из рисунка видно, что реализация функции по СДНФ потребовала 5 корпусов ИС, по минимальной форме - 1,58 корпуса ИС, по скобочной форме - 1,16 корпуса. Таким образом, минимизация по карте Карно дала нам трёхкратный выигрыш по корпусам ИС относительно реализации по СДНФ. Реализация по скобочной форме уменьшила объём оборудования ещё на 30%. Кстати, оценка экономии по Кс даёт приблизительно такой же результат: 40/13 = 3,08.

1.8. Формы задания булевых функций.

Об одной форме задания булевых функций мы уже говорили - это таблица истинности. Иногда применяется более компактная запись, использующая восьмеричные, десятичные или шестнадцатеричные эквиваленты наборов. Например, набор x4x3x2’x1’ может быть представлен обобщённым кодом 1100 , десятичным эквивалентом которого является число 12. Удобнее всего 8-чные и 16-чные коды.

Ниже приведена Паскаль-программа синтеза псевдослучайных кодов для задания произвольных булевых функций.

program nabor;

uses crt;

type stroka = string[4];

txt = file of stroka;

var f1:txt;

x, y,i, j,n, m,b:integer;

st:stroka;

-----------------------------------------------------------

function intchar(m:integer):char;

var

ch:char;

begin

case m of

0..9: ch:=chr(m+ord('0'));

10..35: ch:=chr(ord('A')+m-10);

else

begin

writeln('Ошибка ввода');

halt;

end;

end{case};

intchar:=ch;

end;

------------------------------------------------------------

function int10(a:longint;b:integer):string;

{Пеpевод целого 10-ичного числа в (2..36)-ичные системы}

{a, b - исх. 10-ичн. число и основание сист. счисл. соотв-енно}

var s:string;

m, i,j:integer;

chrarr:array[0..30] of string;

begin

i:=0;

for j:=0 to 30 do chrarr[j]:=' ';

repeat

m:=(a mod b);

chrarr[i]:=intchar(m);

a:=a div b;

i:=i+1;

until (a=0);

s:=chrarr[i];

for j:=i-1 downto 0 do

s:=s + chrarr[j];

int10:=s;

end;

{=================================================}

begin

{$I-} {Внутр. проверка правильности операции с файлом отключена}

writeln('**************************************************************');

writeln('* Фоpмиpование файла случайных *');

writeln('* 2-pазpядных 4,8,16-ичных чисел для каpт Каpно *');

writeln('* Pезультиpующий файл - rnd. txt *');

writeln('* 16-09-1997 *');

writeln('**************************************************************');

writeln;

write('Введите длину файла n и количество пеpеменных m(4,6,8) ');

readln(n, m);

assign(f1,'rnd. txt');{Связь f1 с pезультиpующим файлом }

{$I+} {Включить внутр. проверку}

rewrite(f1); {Открыть файл для записи}

case m of

4: begin b:=4; x:=15; end;

6: begin b:=8; x:=63; end;

8: begin b:=16;x:=255; end;

end;{case}

randomize;

for i:=1 to n do

begin

y:=random(x);

st:=int10(y, b);

write(st:8);

write(f1,st);

end;

close(f1);

writeln;

writeln('Файл rnd. txt сфоpмиpован');

writeln('Нажмите клавишу пpобела');

repeat until keypressed;

end.

Задача 3.

Полностью определённая булева функция от 4-х переменных задана десятичными рабочими наборами : РН(4) = 5, 6, 7, 8, 9, 10, 11.Число в скобках указывает количество переменных. Найти минимальную форму этой функции.

Решение.

Так как функция является полностью определённой, то запрещёнными наборами ЗН(4) являются наборы 0 - 4, 12 - 15. Исходя из этой информации, составляем таблицу истинности и осуществляем минимизацию по карте Карно.

Таблица 4.

РН(4)	x4 x3 x2 x1	f
5	0 1 0 1	1
6	0 1 1 0	1
7	0 1 1 1	1
8	1 0 0 0	1
9	1 0 0 1	1
10	1 0 1 0	1
11	1 0 1 1	1

ЗН(4)	x4 x3 x2 x1	f
0	0 0 0 0	0
1	0 0 0 1	0
2	0 0 1 0	0
3	0 0 1 1	0
4	0 1 0 0	0
12	1 1 0 0	0
13	1 1 0 1	0
14	1 1 1 0	0
15	1 1 1 1	0

По карте Карно получаем результат: