О.Б. Лупанов - Курс лекций по математической логике (1109964), страница 7
Текст из файла (страница 7)
Такимnобразом, мы показали, что L(n) & 13 · 2n . Следовательно, оценку улучшить не удастся. Для КС можно показать, что S(n, h0 ) 6 (2n)h (2h)2h . Действительно, для каждого контакта есть 2n возможностей — xi и xi , способов их соединения — не более (2h)2h , потому что каждый из 2h концов рёбер можносоединить с каждым. Далее поступаем так же, как и в предыдущем утверждении про СФЭ.4. Автоматы4.1. Детерминированные функцииОпределение. Алфавит — произвольное конечное множество. Его элементы называются буквами.Рассмотрим два алфавита A = {a1 , a2 , .
. . , an }, B = {b1 , b2 , . . . , bm } и функции вида f : A∞ → B ∞ , т. е.функции, преобразующие бесконечные последовательности букв A в бесконечные последовательности букв B.Пример 1.1. Пусть f переводит последовательность, состоящую сплошь из нулей, в себя, а все остальные —в последовательность, состоящую сплошь из единиц. Для такой функции существует последовательность —состоящая лишь из нулей, для которой невозможно определить её образ, зная лишь конечное число членов. Этопричиняет неудобства при вычислении, поэтому введём понятие детерминированности.Определение. Функция f : A∞ → B ∞ называется детерминированной, если b(t) однозначно определяетсяпервыми t членами входной последовательности a(1), a(2), . .
. , a(t).Пример 1.2. Детерминированными функциями являются:• Функция 0, . . . , 0, 1, ?, . . . , ?, . . . 7→ 0, . . . , 0, 1, 1, . . . , 1, . . . . Здесь «?» — любой символ.tt• Функция чётности b(t) = a(1) ⊕ . . . ⊕ a(t);• Функция единичной задержки a(1), a(2), . .
. , a(t), . . . →70, a(1), a(2), . . . , a(t − 1), . . . ;(1, t = 2m ;• Функция b(t) =0, t 6= 2m .Детерминированные функции можно задавать на бесконечных деревьях. Рассмотрим бинарное дерево, т. е.такое, что из каждой вершины выходит 2 ребра, и во все вершины, кроме одной (начальной), входит одноребро. В начальную вершину рёбра не входят.
Каждой бесконечной двоичной последовательности поставим всоответствие определённый путь на дереве: движение начинается из начальной вершины, и если a(i) = 0, тоидём по левой ветке, а если a(i) = 1, то по правой. При этом очередному звену пути приписываем значениеb(i). Легко видеть, что такое соответствие осуществляет биекцию между деревьями и детерминированнымифункциями.Пример 1.3. Эти два дерева иллюстрируютпервые два примера детерминированных функций, приведённых выше.0 101 11 11101 10 111 0011 010 110014.2. АвтоматыОпределение. Ограниченно детерминированные функции (конечные автоматы) — детерминированныефункции, деревья которых содержат лишь конечное число различных поддеревьев.Пронумеруем различные поддеревья.
Номера будем писать в начальных вершинах поддеревьев.Пример 2.1. Рассмотрим снова функцию чётности. Её дерево содержит только 2 вида поддеревьев. Эту диаграмму надо понимать так: еслимы находимся в дереве №1 и на входе 0, то выход — 0 и мы остаёмся вдереве №1, а если на входе 1, то выход — 1 и мы переходим в дерево №0.Аналогично для дерева №0.181001101010В общем случае, если речь идёт о конечно детерминированных функциях, можно утверждать, что достаточнознание конечного числа конечных фрагментов дерева, чтобы найти образ любой последовательности.Определение.
Номера поддеревьев называются состояниями автомата.Фрагменты дерева могут задаваться диаграммами переходов (диаграммами Мура). Они представляют собойориентированные графы, вершины которых соответствуют состояниям, а каждому ребру приписывается парасимволов, первая компонента которой соответствует входу, а вторая — выходу. Направление ребра соответствуетпереходу из одного состояния в другое.Пример 2.2. Диаграмма Мура для функции чётности (см.
рисунок).(0, 0)Автомат можно задавать функциейпереходаq(t+1)=Ga(t),q(t)ифункцией выхода b(t) = F a(t), q(t) . Здесь q(t) — состояние в момент t.Удобно считать q(1) = 0. Эти три уравнения называются уравнениями автомата.Пример 2.3. Найдём уравнения автомата единичной задержки, т. е.функции с выходом b(1) = 0, b(t) = a(t − 1), t > 1. Построим диаграммуМура (см. рисунок). По ней видно, что q(t + 1) = a(t), а b(t) = q(t). Приэтом q(1) = 0.(1, 1)01(0, 1)1(1, 1)(1, 0)(1, 0)(0, 0)0(0, 1)Можно также задавать диаграммы функций таблицами.
Например, функцияa q F (a, q), G(a, q)единичной задержки задаётся следующей таблицей:0 0(0, 0)Теорема 4.1. Любой автомат можно реализовать СФЭ, используя элементы0 1(1, 0)4 видов: конъюнкцию, дизъюнкцию, отрицание и функцию единичной задержки.1 0(0, 1) Пусть даны два алфавита A и B. Положим n := log2 |A| , m := log2 |B| .1 1(1, 1)Занумеруем буквы A и B двоичными последовательностями длины n и m соответственно.
Состояния автомата q0 , . . . , qλ−1 также занумеруем двоичными последовательностями длины l :=:= log2 λ , причём q0 соответствует (0, . . . , 0). Введём новые функции перехода и выхода, определённые уже нанаборах из 0 и 1:(β1 (t), . . . , βm (t) = Fe α1 (t), . . . , αn (t), ω1 (t), . . . , ωl (t)e α1 (t), . . . , αn (t), ω1 (t), . . . , ωl (t)ω1 (t + 1), . . .
, ωl (t + 1) = GКаждая из компонент векторов βe и ωe реализуется некоторой булевой функцией α1 αnω1ωl(вообще говоря, не всюду определённой). Построим СФЭ, совместно реализующуювсе эти функции (обозначим их через f1 , . . . , fm и g1 , . . . , gl ).g1glСоединим выходы g1 , . . . , gl через элементы единичной задержки (они показаныf1fmна рисунке прямоугольниками) с входами ω1 .
. . ωl . Очевидно, что такая схема будетработать согласно приведённым выше уравнениям автомата (при условии, что элементы единичной задержкив первый момент времени выдают нули). Обратное также верно: любая СФЭ типа той, что была рассмотрена выше, моделирует некоторый автомат.Замечание. Если разрешить использовать в схеме вместо {¬ & ∨} любые автоматные функции, но запретитьориентированные циклы, то не существует такого конечного набора автоматных функций, схемой из которыхможно было бы реализовать любой автомат.
Иными словами, не существует конечной полной системы автоматов.5. Логика. Исчисления и предикаты5.1. Исчисление высказываний (ИВ)Определение. Высказывание — повествовательное сообщение, которое в силу своего смысла может бытьлибо истинным, либо ложным.Пример 1.1. «23.04.2001 — понедельник» — истинное высказывание, «23.04.2001 — вторник» — ложноевысказывание. «Среда ли 23.04.2001?» — не высказывание.Истинность высказывания будем обозначать 1, ложность — 0.
Встречаются обозначения И, Л (начальные буквы соответствующих слов), иногда ⊤ и ⊥. Будем рассматривать 4 булевы функции {¬ & ∨ →} и будем строитьнад ними тождественно истинные формулы, т. е. принимающие значение 1 при любых значениях аргументов.Рассмотрим систему аксиом ИВ:1. Аксиомы, содержащие только импликацию:а. A → (B → A)19б. A → (B → C) → (A → B) → (A → C)2. Аксиомы, содержащие конъюнкцию:а.б.в.(A&B) → A(A&B)→ BA → B → A → C → A → (B&C)3. Аксиомы, содержащие дизъюнкцию:а.б.в.A → (A ∨ B)B → (A∨ B)A → C → B → C → (A ∨ B) → C4.
Аксиомы, содержащие отрицание:а. (A → B) → (B → A)б. A → Aв. A → AСформулируем правило вывода, вытекающее из свойств импликации: A ≡ 1, (A → B) ≡ 1. Тогда B ≡ 1. Оноиногда записывается в виде A→B,A.BОпределение. Вывод — конечная последовательность формул {F1 , . . . , Fs }, причём любая её формула естьлибо аксиома, либо получается по правилу вывода из предыдущих формул этой последовательности. Формуланазывается выводимой, если существует вывод, содержащий эту формулу.Теорема 5.1.
Любая выводимая формула тождественно равна 1. Истинность аксиом легко проверяется путём полного перебора всех возможных наборов значений переменных, в них входящих, что предлагается сделать читателю в качестве полезного упражнения. Теперь утверждение теоремы вытекает из правила вывода. Пример 1.2. Выведем формулу A → A.
По 1.б имеемA → (A → A) → A → A → (A → A) → (A → A) .Эта формула имеет вид P → Q, где P = A → (A → A) → A . Но P истинна, т.к. она получается из 1.aподстановкой B = A → A. Значит, можно вывести Q = A → (A → A) → (A → A). Аналогично, она имеет видR → X, где R = A → (A → A), а X = A → A. Подставим в 1.a B = A, получим, что R истинна. Итак, истинныR и R → X. Следовательно, X = A → A выводимо.Теорема 5.2. Любая тождественно истинная формула выводима, т. е. наш набор аксиом полон. Мы не будем доказывать эту теорему, поскольку доказательство очень длинное, но не очень содержательное.
Идея доказательства состоит в том, что тождественно истинная формула приводится к СДНФ ипереписывается в терминах этой системы аксиом, откуда следует её выводимость. Определение. Исчисление — конечный набор аксиом A1 , . . . , Ar и правил вывода R1 , . . . , Rq , каждое изS 1 ,...,Stiкоторых устроено как Ri = i Si i .
Исчисление непротиворечиво, если не существует выводимой формулы,для которой выводимо и её отрицание.Пример 1.3. ИВ непротиворечиво, т. к. в нём формула выводима тогда и только тогда, когда она тождественно истинна. А отрицание тождественно истинной формулы тождественно ложно, значит, невыводимо.Определение. Система аксиом называется независимой, если в ней нет аксиомы, выводимой из остальных.5.2. ПредикатыОпределение. n-местный предикат — функция вида P : Mn → Ω, где M — некоторое множество, Ω —множество высказываний. Одноместные предикаты иногда называются свойствами.
При n > 1 предикатыиногда называются отношениями.Пример 2.1. P (x) = «x — чётное число» — предикат, определённый, скажем, на множестве N.Из предикатов можно составлять формулы, используя наши 4 булевы функции. При этом также получаютсяпредикаты.Пример 2.2. P (x, y, z, w) = Q(x)&R(y) ∨ S(z, w).20Определение. Полная система предикатов на конечном множестве M — такая система, что любой предикат над M выражается через предикаты этой системы.Очевидно, одноместных предикатов на конечном множестве M имеется 2|M| , поскольку одноместный предикат задаёт некоторое подмножество множества M.
Именно поэтому одноместные предикаты называют свойствами.Теорема 5.3. Система предикатов P = {P1 (x), . . . , Ps (x)} — полная ⇔ ∀ a, b ∈ M, a 6= b, найдётся предикат Pi ∈ P, такой, что Pi (a) 6= Pi (b). ⇒ Докажем от противного. Предположим, все предикаты из P принимают равные значения на a иb. Тогда любая формула над этой системой обладает тем же свойством, значит, нельзя получить, например,предикат, который равен 1 на a и 0 в остальных точках (в том числе b). Противоречие.⇐ Построим формулудля любого предиката над P. Пусть a ∈ M. Возьмём предикат Pi (x) ∈ P.
Сделаем(Pi (x), Pi (a) = 1;(a)(a)(a)(a)предикат Pi (x) :=Имеем Pi (a) = 1. Построим предикат P (a) (x) := P1 (x)& . . . &Ps (x).Pi (x), Pi (a) = 0.Он обладает двумя свойствами: P (a) (a) = 1 и P (a) (b) = 0, если b 6= a, поскольку по условию ∃ Pj ∈ P : Pj (a) 6=6= Pj (b), и он присутствует в выражении для P (a) (x). Таким образом, построен аналог функции xσ . Теперь длялюбого предиката построим аналог СДНФ.ПустьWP (x) — любой предикат.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
