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

а) через функцию Шеффера: 1) отмечаем в таблице строки, где f=1; 2) каждому набору переменных поставим в соответствие терм Шеффера, причем нулю ставится в соответствие соответствующая переменная с отрицанием, а единице – без отрицания (111- x/y/z); 3) полученные термы берут в скобки и объединяют через /. (можно показать, то полученную форму можно привести к СДНФ).

б) через функцию Пирса: 1) находим троки, где f=0; 2) каждому набору переменных поставим в этих строках в соответствие терм пирса, причем переменной отрицанием соответствует 1, а без отрицания-0(000 - x¯y¯z) 3) полученные термы заключаем в скобки и объединяем стрелками Пирса (полученную форму можно привести к СКНФ).

Методы минимизации в этих базисах (монобазисах) разработаны очень слабо, поэтому минимизируют в классе ДНФ, а затем переходят к монобазису, по возможности сохраняя минимальность.

Основные понятия теории графов.

Возьмем два множества: V- множество точек(не пустое), E- множество линий (может быть пустое). Возьмем элемент e из множества E. Если существует пара элементов u,vV, что эти элементы являются концами линии е, то говорят, что элемент е инцидентен элементам u и v, и наоборот, элементы u и v инцидентные. Графом (G,G(u,v),V E) называется совокупность множеств V и E между элементами которых определено отношение инцидентности, причем для каждого элемента еÎЕ найдется пара элементов из множества V, что e инцидентно этим элементам. Обратное вообще говоря неверно: элементы V не инцидентны никаким элементам из множества Е.??? Элементы множества V называются вершинами графа, элементы множества Е- ребрами графа. Вершина, не инцидентная ни одному ребру, называется изолированной. Граф, состоящий только из изолированных вершин, называется нуль-графом. Вершины, инцидентные одному ребру, называются смежными. Два ребра, инцидентные одной вершине, называются смежными. Если вершина инцидентна только одному ребру, то она называется висячей. Если вершина инцидентна только двум ребрам, то она называется транзитивной. Если граф содержит петли, то он называется псевдографом. Если граф содержит кратные ребра, то его называют мультиграф. Если не никаких оговорок, то, говоря о графе, будем полагать, что он не содержит ни петель, ни кратных ребер. В некоторых случаях рассматриваются графы, вершины которого неравноправны, т.е. рассматриваются в определенном порядке, тогда ребру приписывается направление от начальной вершины к конечной. Направленное ребро называется дугой графа. Граф, содержащий только дуги, называется ориентированным графом, или ор-графом. Если граф содержит дуги и ребра, то он называется смешанным. Для неориентированных. графов (u,v)=(v,u), для ор-графов (u,v)≠(v,u).

Способы задания графов.

1) геометрический.

2) табличный а) назовем вершину vi непосредственно предшествующей вершине vj, если существует дуга (vi,vj). Множество вершин, непосредственно предшествующих вершине vj, обозначим B(j), тогда граф можно задать в виде таблицы, где в первой троке записываются вершины, а во второй строке под ними вершины, непосредственно предшествующие соответствующей вершине. Вершина vj называется непосредственно следующей за вершиной vi, если существует дуга (vi,vj). Множество вершин, непосредственно следующих за вершенной vi, обозначим как A(i). Таблица задается аналогично. Очевидно, ели граф не ориентирован, то множества А и В совпадают. б) таблица : в первой строке записываются ребра, а во второй строке – инцидентные им вершины. Причем если граф ориентирован, то на первом месте во второй строке ставится начальная, а на вором – конечная вершина. Если граф не ориентированный, то в любом порядке.

3) аналитический {V1,V2,V3,V4,(V2V3),(V4V2),(V4V3),(V3V2)}

4) матричный а) пусть имеем граф, содержащий n вершин и m ребер или дуг. Матрицей инцидентности называется матрица размера n x m(строки х столбцы), элемент которой Aij в случае не ориентированного графа равен 1, если вершина Vi инцидентна j-му ребру, и 0, в противном случае. Aij={1, Vi инц. j ребру; 0, если нет}. Если граф ориентированный, то Aij=-1, если вершина Vi начальная для j-й дуги, =1, если конечная, и 0, если вершина не инцидентна. Замечание: если мы имеем псевдограф(петлю), то в соответствующем месте Aij ставится любое число, отличное от 0 и +-1. б)матрица смежности. Матрицей смежности графа называется матрица n-го порядка(число вершин), элемент которой Aij=1, если есть дуга (vi,vj), и =0 в противном случае. Число единиц в матрице будет равно количеству дуг или удвоенному числу ребер.