О.Б. Лупанов - Курс лекций по математической логике (1109964), страница 5

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

Текст из файла (страница 5)

. . , hn ) = f βi(eσ )1 , . . . , βi(eσ )n . Такимобразом, мы можем получить любую функцию, принимающую значения {ε1 , . . . , εl }, и шаг индукции доказан.Завершим доказательство теоремы построением произвольной функции g, принимающей любые l значений{ξ1 , . . . , ξl }. Рассмотрим функцию θ(x) : θ(εi ) = ξi . Чтобы θ принимала не более l различных значений, положимθ(x) = ξ1 , x ∈/ {ε1 , . . . , εl }. Так можно сделать, поскольку значения функции θ не на εi нас не интересуют. У насуже есть функция h : h(eσ ) = εi , если g(eσ ) = ξi . Тогда функция g выражается так: g = θ(h).

Определение. Функция f называется шефферовой, если {f } = Pk .Теорема 2.9. f — шефферова ⇔ f порождает все функции из Pk (1), принимающие не более k − 1 значения.⇒ Тривиально: эта функция порождает все функции.⇐ Покажем, что эта функция существенна. Обозначим E := {0, 1, . . . , k − 1}. Если Im f 6= E, то из неенельзя получить функцию, принимающую отсутствующее значение, а среди функций от одной переменной такаяобязательно найдется.

Значит, f должна принимать все k значений. Если она существенно зависит только отодной переменной, то, следовательно, является перестановкой, а композиция перестановок — тоже перестановка,значит, константу из неё получить нельзя. Значит, она существеннозависит не менее чем от 2 переменных, ипо определению существенна. По теореме Яблонского {f } = Pk . Далее речь пойдет об алгебраической системе функций в Pk . Сложение и умножение, естественно, подразумеваются по модулю k.Утверждение 2.10.

Система E ∪ {× +} полная ⇔ k — простое число. Пусть k — простое число. Положим ϕ(x) := 1−xk−1 . Имеем ϕ(0) = 1, а по малой теореме Ферма ϕ(a) ≡ 0(mod k), если a 6= 0. Следовательно, ϕ = j0 . Легко видеть, что jα (x) = j0 (x − α). Но так как для любой функцииf мы имеем полиномиальное выражение над E ∪ {× + j0 (x), . . . , jk−1 (x)} видаXf (x1 , . .

. , xn ) =jσ1 (x1 ) × · · · × jσn (xn ) × f (σ1 , . . . , σn ),(σ1 ,...,σn )то система полная.Предположим теперь, что k — составное число, т. е. k = mn и m, n > 1, и докажем, что наша системанеполная. Покажем, что j0 (x) не представляется в виде полинома j0 (x) = c0 + c1 x + c2 x2 + · · · + cp xp .

Т.к.j0 (0) = 1, то c0 = 1. Но в силу того, что m 6= 0, имеем 0 = j0 (m) = 1 + c1 m + · · · + cp mp . Домножим это13равенство на n, тогда почти все слагаемые поубиваются (mn ≡ 0 (mod k)), и останется неверное равенство0 = n. Противоречие. 2.4. Замкнутый класс без базисаУтверждение 2.11. Если k > 3, то в Pk существует замкнутый класс, не имеющий базиса. Рассмотрим класс функций вида ϕi (x1 , . .

. , xi ), равных 1 на наборах из одних двоек, и 0 в противномслучае. Он, очевидно, замкнут, поскольку при подстановке функции ϕi в функцию ϕj мы получаем нуль. Действительно, функция ϕi никогда не принимает значение 2, стало быть, аргументы ϕj — не есть набор сплошьиз двоек.

Отсюда следует, что из функции с меньшим номером нельзя получить функцию с большим номером.Значит, с одной стороны, базис должен содержать все функции ϕi , а с другой стороны, отождествлением переменных можно из функции с большим номером получить все функции с меньшими номерами. Значит, этоткласс базиса не имеет. 2.5. Класс, имеющий счётный базисРассмотрим множество функций вида ψi (x1 , . . .

, xi ), равных 1, если среди аргументов ровно 1 единица, аостальные — двойки, и равных 0 во всех остальных случаях. Оно, очевидно, замкнуто.Утверждение 2.12. Любая из функций ψi не выражается через остальные. Докажем, что ψi не может получиться из ψj путём отождествления переменных. В самом деле, положимотождествлённую переменную равной 1, остальные — 2. Тогда функция с меньшим числом переменных будетравна 1, а другая — 0, т.к. среди её аргументов более одной единицы. Теперь докажем, что одна функцияне получается из другой при помощи подстановки.

Рассмотрим два случая. 1◦ Среди аргументов функции ψiесть ровно 1 подформула на s-м месте. Тогда подставим набор с единицей на любом месте, кроме s-го. Тогдафункция с подформулой примет значение 0 (аналогично случаю отождествления), а без подформулы — 1.Значит, эти две функции не равны.

2◦ Среди аргументов есть хотя бы 2 подформулы. Подставим любой наборвида (2, . . . , 2, 1, 2, . . . , 2). Очевидно, функция с подформулами на нём обнулится, а без подформул — нет. Отсюда следует, что любое подмножество данного класса замкнуто, и каждая функция, в свою очередь,является базисной. Значит, в Pk континуум замкнутых классов, ибо их столько же, сколько бесконечных последовательностей из нулей и единиц. Действительно, можно установить биекцию между любым подмножествомэтого класса и множеством последовательностей: на i-том месте в последовательности ставим 0, если ψi нележит в данном подмножестве, и 1 в противном случае. Каждая последовательность — бесконечная двоичнаядробь без разделительной точки.

Значит, классов столько же, сколько и всех действительных чисел.3. Схемы из функциональных элементов3.1. ГрафыОпределение. Граф — это упорядоченная пара (V, E), где V — не более чем счётное множество, элементыкоторого называются вершинами, а E ⊆ V × V — множество пар вершин {(vi , vj )}, называемых рёбрами графа.Концами ребра называются элементы пары, образующей ребро. Если концы совпадают, то ребро называетсяпетлёй.

Вершина называется изолированной, если она не является концом никакого ребра. Вершина называетсяконцевой, если она является концом ровно одного ребра.Определение. Подграф графа (V, E) — такой граф (W, F ), что W ⊆ V и F ⊆ W × W .Определение. Геометрическая реализация графа. Рассмотрим Rn . Отметим в нём столько точек, скольковершин у нашего графа. Каждому ребру поставим в соответствие кривую, соединяющую концы этого ребра.Эту кривую мы тоже будем называть ребром. То, что получится, и будет геометрической реализацией.

Геометрическая реализация называется правильной, если у рёбер нет общих точек, кроме, быть может, вершин.Утверждение 3.1. В R3 для любого графа имеется правильная геометрическая реализация. Сперва расставим вершины произвольно. Очевидно, путём малых шевелений можно сделать так, чтоникакие 4 не будут лежать в одной плоскости. Теперь для любых трёх вершин есть своя плоскость, а плоскийграф из трёх вершин, очевидно, допускает правильную реализацию. Определение. Путь — конечная последовательность рёбер графа (vi1 , vi2 ), (vi2 , vi3 ), .

. . , (vin−1 , vin ). Говорят,что путь соединяет вершины vi1 и vin . Простой путь (цепь) — путь, все вершины которого различны. Цикл —путь, у которого vi1 = vin . Простой цикл — цикл, у которого все рёбра и все вершины, кроме концов, различны.Граф называется связным, если любые 2 его вершины можно соединить путём. Деревом называется связныйграф без простых циклов.14Утверждение 3.2.

Из каждого конечного связного графа можно выделить подграф, содержащий все вершины исходного графа и являющийся деревом. Если в графе есть простой цикл, то можно убрать из цикла одно ребро, не нарушив связности. Будемубирать рёбра, пока простых циклов не станет. Определение. Назовём граф ориентированным, если каждому его ребру приписано направление.Определение. Ориентированный цикл — цикл, в которомвсе рёбра направлены в одну сторону, т. е. ко→, где первая вершина совпадает с последней.нечная последовательность ориентированных рёбер −vi−,−v−i+1Лемма 3.3. В любом конечном ориентированном графе без ориентированных циклов есть вершина, изкоторой рёбра не выходят.

От противного: выберем любую вершину и, исходя из неё, будем двигаться по рёбрам в направлении,приписанном данному ребру. Если из каждой вершины выходит хотя бы одно ребро, то рано или поздно мывернёмся туда, где уже были, поскольку граф конечен. Но это будет ориентированный цикл. Противоречие. Теорема 3.4. В любом конечном ориентированном графе без ориентированных циклов можно занумеровать вершины первыми натуральными числами так, что каждое ребро будет направлено от вершины сменьшим номером в вершину с большим номером. Докажем индукцией по числу вершин p.

При p = 1 утверждение очевидно. Пусть p > 1. Предположим,что это верно для всех графов с числом вершин, меньшим p. Рассмотрим граф с p вершинами. По лемме у негоесть вершина, из которой рёбра не выходят. Уберём из графа эту вершину и все входящие в неё рёбра, получимграф с числом вершин, меньшим p. По предположению индукции такой граф допускает искомую нумерациювершин числами 1, 2, .

. . , p − 1. Тогда присвоим выкинутой вершине номер p. 3.2. Схемы из функциональных элементовx1x22Определение. Схема из функциональных элементов (СФЭ) — это конечный ориентиро- 1ванный граф без ориентированных циклов, в каждую вершину которого входит не более 2 3 &∨ 4рёбер. При этом каждой вершине приписывается символ: переменная xi , если в эту вершину 5 ¬рёбра не входят; отрицание, если в вершину входит одно ребро; конъюнкция или дизъюнкция,&6∗если в вершину входит 2 ребра.

Некоторым вершинам приписывается ∗. Элементами схемыназываются вершины, помеченные логическими операциями.Занумеруем вершины графа согласно предыдущей теореме. Каждой вершине СФЭ можно сопоставить некоторую булеву функцию по следующему индуктивному правилу. Пусть всем вершинам с номерами меньше n ужесопоставлены функции.

Характеристики

Список файлов лекций