39. Понятие о функциях k-значной логики. Их особенности.

Функция f(х₁,х₂,…,х_n) аргументы которой определены на мн-ве E^k = {0, 1, 2, …, k – 1} назыв. функцией k-значной логики.

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

В этой таблице k_n – строк. Р_к – множество всех

х1	…	xn-1	xn	f (x1,…,xn-1,xn)
0	…	0	1	f (0,0,…,0)
0	…	0	1	f (0,0,…,1)
……	…	……	……	…….
0	…	0	k-1	……
……	…	….	……	…..
k-1	…….	k-1	k-1	f (k-1, k-1,…, k-1)

функций к-значной логики. Р_к(n) – множество функций из Р_к, зависящих от n-переменной.

Множество всех функций k-значной логики будем обозначать . В P_k часто употребляется задание таких функций, при помощи алгоритма вычислимости функций.

Следующие функции к-значной логики считаются элементарными:

1. Константы 0, 1, …, k-1

2. Отрицание Поста :=x+1 mod k.

3. Отрицание Лукашевича ~x = k-1-х;

4. Характеристическая функция 1^го рода ;

5. Характеристическая функция 2^го рода (возведение в степень);

6. xÙy = min{x,y}

7. xÚy=max{x,y}.

8. Сумма по модулю k x+y=(x+y) mod k;

9. Усеченная разность:

10. Импликация (x содержит в себе y) xy=

11. - функция Вебба.

12. Разность:

Пусть E будем говорить, что ф-ция f-сохраняет множество E, если "=(), таком, чтозначения ф-ции. Множество всех функций P_k ,сохраняющих мн-во E обозначим .и называется классом функций, сохраняющих множество Е. Очевидно, что класс Т_Е является замкнутым.

40.Графы. Изоморфизм графов.

Графом G называется совокупность двух мн-в G=(V, E), где V- мн-во вершин графа, а Е –мн-во ребер графа. Между вершинами и ребрами графа G устанавливают отношение инцидентности. Считают, что ребро инцидентно вершинам,если оно соединяет эти две вершины. При этом вершины,называются смежными.

Отношения инцидентности являются самым главным элементом графа, т.к. указывается способ объединении v и e в единый объект.

Ребра инцидентные одной и той же паре вершин назыв. кратными. Граф содер. Кратные ребра назыв. мультиграфом.

Ребро(дуга) концевые вершины которого совпадают назыв. узлом.

Вершина неинцидентная ни одному ребру назыв. изолированной.

Если граф состоит только из изолированных вершин, то он назыв. нульграфом.

Граф без петель и кратных ребер назыв. полным, если каждая его вершина соединена ребром.

Дополнением графа G называется граф имеющий те же вершины что и графG и содержащий только те ребра которые нужно добавить к G, что бы получался полный граф.

Локальной степенью вершины v n-графа G называется число равное кол-ву ребер инцидентных вершинеv. В n-графе сумма всех степеней равна удвоенному числу ребер графа, т.е.

,

Для вершин ор-графа определяют две локальные степени и, где-кол-во дуг исходящих из вершиныv, - кол-во дуг входящих в вершинуv.

Петля дает вклад 1 в обе эти степени. В ор-графе суммы этих степеней

Графы G=(V,E) и G'=(V',E') изоморфны (пишут G), если существует взаимно-однозначное соответствие между множествами V и V', сохраняющее смежность вершин (т.е. такое соответствие, при котором вершины v_i и v_j из множества V смежны тогда и только тогда, когда смежны соответствующие им вершины     и из множества V' )