FAQ, страница 2

x s .В силу нелинейности полинома внем найдется член, содержащий не менее двух переменных x1 и x2 c ненулевым коэффициентом.Тогда полином можно переписать следующим образом:f(x1, x2, ...,xn) = x1x2 f1(x3, ...,xn) + x1 f2(x3, ...,xn) + x2 f3(x3, ...,xn) + f4(x3, ...,xn), где f1(x3, ...,xn)  0.Имеется набор  = (a3, ..., an), такой, что f() = 1.Тогда положим h(x1, x2) = f(x1, x2, a3, ..., an) = x1x2 + x1b2 + x2 b3 + b4, где b2 , b3 , b4 - константы.Рассмотрим функцию g(x, y)= h(x+b3,y+b2)+b2b3+b4.

Очевидно, что g(x,y) = x&y.11. Теорема Поста о полноте системы булевых функций.Теорема. Для полноты системы G  P2 необходимо и достаточно, чтобы G не содержаласьни в одном из пяти классов T0, T1, S, M, L.Необходимость очевидна. В самом деле, если бы полная G содержалась бы в замкнутом классеR, то P2 = [G]  [R] = R, но все указанные классы замкнуты и не совпадают с P2.Достаточность. Пусть в G имеются функции f1, f2, f3, f4, f5, не лежащие соответственно в T0, T1,S, M, L.

Положим G’ = {f1, f2, f3, f4, f5} и будем считать, что эти функции зависят от одних и тех жепеременных (x1, x2, ...,xn).(1) С помощью f1, f2, f3 построим константы 0 и 1.Положим q(x) = f1(x, x, ...,x)  T0. Очевидно, q(0) = 1.(а) Если q(1) = 1, то q(x) есть константа 1. Тогда с помощью f2  T1 имеем вторую константуf2(1,1,...,1) = 0.(б) Если q(1) = 0, то q(x) есть x .

Тогда в силу соотв. леммы (See also п.8) из несамодвойственной f3 можем получить константу c, и, применяя отрицание, получаем вторую константу с.(2) С помощью констант 0,1 и немонотонной f4 по соотв. лемме (See also п.9) можно построитьотрицание x.(3) С помощью констант 0,1, отрицания и нелинейной f5, можно по соотв. лемме (See also п.10)получить конъюнкцию x&y.Таким образом, с помощью G выражается полная система {0,1,,&}, откуда G также полна (Seealso п.3).12. Теорема о максимальном числе функций в базисе системы булевых функций.Теорема.

Любой базис P2 содержит не более четырех функций, т.е. из всякой системы G полнойв P2, можно оставить не более четырех функций, образующих полную систему.Из G можно согласно 11 выделить полную подсистему, содержащую не более 5 функций - f1, f2,f3, f4, f5. Как видно из доказательства 11, пункт (1) функция f1 либо не самодвойственна (случай а),AlecSoft design © 1996либо не монотонна и не сохраняет 1 (случай б).

Поэтому полной подсистемой G будет также либо{f1, f2, f4, f5} либо {f1, f3, f4}Тот факт, что максимальное число функций в базисе в самом деле равно P2, следует из рассмотрения примера G = {0, 1, x & y, x  y  z}. В самом деле , G\{0}  T1, G\{1}  T0, G\{&}  L, G\{x y  z}  M.13. Теорема о предполных классах.Класс R  P2 называется предполным, если R не является полным (в P2), а для любой f из P2\Rкласс R  {f} является полным.Из определения следует, что любой предполный класс замкнут.Из 11 следует, что в алгебре логики существует только пять предполных классов: T0, T1, S, M, L.В самом деле, пусть G - предполный класс.

Тогда, поскольку G не полон, G  A , где А - один изпяти указанных выше классов. Предположим, что G  A. Тогда возьмем f  A\G. По определениюпредполного класса, система G’ = G  {f} полна. Но, с другой стороны, G’  A  G’ не может бытьполной (противоречие). Следовательно, G = A, т.е. совпадает с одним из T0, T1, S, M, L.14*. k-значные функции. Теорема о существовании полной конечнойсистемы в мн-ве k-значных функций.Ek = {0, 1, ..., k-1}.

Функции вида f(x1, x2, ..., xn), аргументы и значения которых принадлежат Ek,будем называть функциями k-значной логики.Через Pk обозначим множество всех таких функций над алфавитом переменных U. Число функций из Pk, зависящих от n аргументов равно pk ( n )  k k nЭлементарные функции:(1) ‘Циклический сдвиг’ x = x  1 (mod k) - обобщение отрицания.(2) min(x,y)  x & y и(3) xy (mod k) - два обобщения коньюнкции.(4) max(x,y)  x  y - обобщение дизьюнкции.(5) x + y (mod k)(6) I(x) = {k-1, если x = ; 0 если x  }Простейшие свойства:(1) функции min, max,  ассоциативны и коммутативны.(2) x = x.(3) min(x, y) = max(x, y)(4)f ( x1 ,..., xn )  max .( I1 ( x1 )&...& In ( xn )& f ( 1 ,...,n ))( 1 ,..., n )- аналог СДНФ в k - значной логике, доказывается прямой проверкой.Аналогично вводится понятие полноты системы k - значных функций (See also п.3).Как видно из (4), система функций, содержащая константы, функции I(x), min, max являетсяполной.15.

Основные понятия теории графов. Изоморфизм графов. Связность.Множество объектов-вершин V = {a1, ..., an,...} и множество пар объектов из V (ребер) W образуют граф =(V,W). Про ребро вида (ak, am) говорят, что оно соединяет вершины ak и am. Графназывается конечным, если множество V конечно.Если ребра считаются упорядоченными парами, т.е. (a,b)  (b,a) при b  a, то граф называетсяориентированным.AlecSoft design © 1996Если в W каждому ребру (a,b) приписана кратность kN, то говорят, что  допускает кратныеребра или, что вершины а и b соединяют k ребер.Граф Г=(V,W) называется полным, если любые две вершины ak, am  V соединены ребром (ak, am) W. Любое ребро вида (b,b) называется петлей.Степенью вершины называется число ребер, содержащих эту вершину.Набор ребер графа вида (b1,b2) (b2,b3)....

(bn-1,bn), где bi - какие-то вершины графа, называется путем из b1 в bn. Любой путь из b в b называется циклом.Граф называется связным, если для любых вершин ak и am существует путь, их соединяющий.Графы  = (V,W) и ’ = (V’,W’) называются изоморфными   ’, если существует взаимнооднозначное соответствие между вершинами f: V  V’ и взаимно-однозначное соответствие междуребрами g: W  W’ , причем g(a,b) = (fa,fb).Подразделением графа Г называется любой граф Г’, полученный из Г путем применения конечного числа раз операции подразделения ребер (т.е.

введения новой вершины с и замены подразделяемого ребра (a,b) на пару ребер (a,c) и (b,c)).Графы Г1 и Г2 называются гомеоморфными, если существуют такие их подразделения Г 1’ и Г2’,которые изоморфны.16. Деревья. Свойства деревьев.Деревом называется связный ациклический граф G.Имеет место соотношение: (G) = В - Р = 1, где В - число вершин и Р - число ребер дерева G (доказывается индукцией по Р).Для любого связного графа G существует остовное дерево - его подграф, содержащий все еговершины и являющийся деревом.17. Корневые деревья. Верхняя оценка их числа.Корневым называется любое дерево с выделенной вершиной, именуемой корнем.18. Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.Геометрической реализацией графа Г называется изоморфный ему граф Г’, вершинами которогоявляются точки в пространстве (на плоскости или другой поверхности), а ребрами - соединяющиеэти точки кривые, не пересекающиеся между собой.Теорема.

Любой конечный граф допускает правильную реализацию в трехмерном пространстве.19. Планарные (плоские) графы. Формула Эйлера.Планарным называется любой граф, допускающий реализацию на плоскости (или гомеоморфнойей поверхности).Гранями планарного графа называются связные области, на которые ребра графа разбиваютплоскость.Обозначения: В - число вершин графа; Г - число граней; Р - число ребер; Формула Эйлера: В + Г- Р = 2 для любого связного планарного графа G.Идея доказательства: (1) Рассмотрим G* - остовное (максимальное) дерево G. (2) В(G*) = В(G);Р(G*)  Р(G); и, очевидно, Г(G*)=1.AlecSoft design © 1996(3) Согласно 16, В(G*) - Р(G*)=1  для G* формула верна.

(4) Будем добавлять к G * перемычки ребра G, не принадлежащие G*. При этом добавление одной перемычки увеличивает число гранейна одну (поскольку перемычка не пересекает других ребер)  формула каждый раз остается верной.20. Доказательство непланарности графов К5 и К3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).Обозначения. Kn - полный граф с n вершинами.

Km,n - полный двудольный граф с m вершинами водной доле и n вершинами в другой.Теорема. Графы К5 и К3,3 непланарны (доказывается с помощью 19).(а) Пусть имеется плоская реализация К5. В = 5; Р = 10; Г  6  20/3 (т.к. минимальная длинацикла в К5 равна 3)  В + Г - Р  1 (противоречие).(б) Пусть имеется плоская реализация К3,3. В = 6; Р = 9; Г  4  18/4 (т.к.

минимальная длинацикла в К3,3 равна 3)  В + Г - Р  1 (противоречие).Теорема Понтрягина-Куратовского. G планарен  G не содержит подграфов, гомеоморфных К5и К3,3.21. Теорема о раскраске планарных графов в 5 цветов.Будем говорить, что граф правильно раскрашен в N цветов, если его вершинам приписаны числаот 1 до N (цвета), причем никаким соседним вершинам не приписан один цвет.Лемма. Пусть G - планарный граф без петель и кратных ребер. Тогда в G имеется хотя бы однавершина степени k  5 (доказывается от противного с помощью формулы Эйлера).Теорема.

Любой планарный граф G допускает раскраску в 5 цветов.Индукция по числу вершин В. Для B  5 очевидно.Пусть существует раскраска для B = 5,6,...,р. Рассмотрим граф с В = p+1. Выделим вершину №0степени k  5. (а) Если k < 5, то по предположению раскрасим G’=G\{№0} и №0 припишем цвет ,отличный от цветов всех ее соседей. (б) Если k = 5, то соседние вершины обозначим №1...№5 и проведем ребра №1№2, №2№3, ... , №5№1. При этом хотя бы одно из других ребер между этимисоседними вершинами отсутствует.

Для определенности, №2№5. Склеим вершины №0,№2 и №5и по предположению раскрасим полученный G’. Вершины №1, №3, №4, и {№0,№2,№5} оказалисьпокрашенными в какие-то четыре цвета. Припишем №0 цвет , отличный от этих четырех цветов, иостальную раскраску G’ перенесем на G. Граф G правильно раскрашен.22. Схемы из функциональных элементов.

Реализация функций алгебры логики схемами.Схемой из функциональных элементов (СФЭ) называется конечный ориентированный граф G безциклов, каждой вершине a которого приписан символ (или символ и *) в соответствии со следующими правилами:(1) Если в а ребра не входят, то а приписан символ переменной xi из фиксированного алфавита; вэтом случае a называется входом. (2) Если в а входит k ребер, то а может быть приписан толькосимвол k-арной логической связки. Используются функциональные элементы, соответствующиеэлементарным связкам ,&, (возможны и другие).

(3) Кроме того, любая вершина может быть помечена символом *; такая вершина называется выходом.Каждой вершине a приписывается булева функция fa(x1, x2, ...,xn) , равная (1) переменной xi (еслиа - вход); (2) f(f1, f2, ...,fk), где f1, f2, ...,fk - функции, приписанные началам входящих в а ребер, и f приписанная а k-арная связка (если а - ФЭ).Каждая СФЭ естественным образом реализует вычисление m n-арных булевых функций, где n иm - соотв.