О.Б. Лупанов - Курс лекций по математической логике (1109964)
Текст из файла
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М. В. ЛОМОНОСОВАМеханико-математический факультетКурс лекций поматематической логикеЛектор — Олег Борисович ЛупановI курс, 2 семестр, поток математиковМосква, 2004 г.Оглавление1.................................................................................................................................................................................................444556678.
. . . . . . . . . . . . . .. . . . . . . . . . . . . . .Слупецкого – Яблонского. . . . . . . . . . . . . . .. . . . . . . . . . . . . . ....................................................................................................................9910111414...................................................................................................................1414151616174.Автоматы4.1. Детерминированные функции . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.2. Автоматы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1818185.Логика. Исчисления и предикаты5.1.
Исчисление высказываний (ИВ) . . . . .5.2. Предикаты . . . . . . . . . . . . . . . . .5.3. Кванторы и формулы . . . . . . . . . . .5.4. Эквивалентные формулы и нормальный....1919202122Алгоритмы6.1. Машина Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . .6.2. Алгоритмически неразрешимые проблемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2222232.3.6.Булева алгебра1.1. Функции булевой алгебры . . . . . . . . . . .1.2. Существенные и несущественные переменные1.3.
Формулы . . . . . . . . . . . . . . . . . . . . .1.4. СДНФ . . . . . . . . . . . . . . . . . . . . . . .1.5. Полнота систем функций . . . . . . . . . . . .1.6. Полиномы Жегалкина . . . . . . . . . . . . .1.7. Замкнутые классы функций . . . . . . . . . .1.8. Критерий Поста полноты систем функций .k-значная логика2.1. Функции k-значной логики . . .
.2.2. Полнота систем функций в Pk . .2.3. Критерии полноты в Pk . Теорема2.4. Замкнутый класс без базиса . . .2.5. Класс, имеющий счётный базис .................Схемы из функциональных элементов3.1. Графы . . . . . . . . . . . . . . . . . . . . . . . .
.3.2. Схемы из функциональных элементов . . . . . .3.3. Контактные схемы . . . . . . . . . . . . . . . . .3.4. Метод каскадов для построения КС и СФЭ . . .3.5. Оценка сложности схем при построении методом................................. . . . . .. . . . . .. . . . . .. . . . . .каскадов. . . . . . . . .. . . . . . . .
.. . . . . . . . .вид формулы2........................................................................................................ПредисловиеДанный документ представляет собой курс лекций «Введение в математическую логику», читаемый деканоммеханико-математического факультета МГУ академиком РАН О. Б. Лупановым на I курсе мехмата во второмсеместре. Он наиболее соответствует лекциям, прочитанным в 2001 и 2003 годах, поскольку составлялся на ихоснове. В указанные годы в программу из-за недостатка времени не вошла теорема Кузнецова, поэтому здесьеё тоже нет, а всё остальное изложено в полном объёме.Надо сказать, что этот документ не является своего рода первоисточником. Основой для него послужилтот же курс лекций по логике, набранный в MS Word студентом мехмата с псевдонимом VILenin.
Но так какматематические тексты в Word’е выглядят не самым лучшим образом, мы решили улучшить VILenin’скийвариант. Лекции, свёрстанные заново в LATEX’е, выглядят гораздо красивее и имеют существенно меньшийобъём. Кроме того, мы исправили все замеченные опечатки, уточнили некоторые определения и доказательстванекоторых теорем. Насколько хорошо это получилось — пусть судит читатель, и любые обоснованные замечаниябудут приняты нами с благодарностью, равно как и любые сообщения о замеченных в нашем издании опечатках.То, что Вы читаете сейчас, условно можно назвать третьим изданием.
В нём заново сделаны иллюстрации,исправлены замеченные типографские погрешности, а также ещё несколько опечаток.В тексте мы старались не использовать нестандартных обозначений, символов и т. д. Начало и конец доказательства отмечаются значками и соответственно.Свои вопросы, комментарии, замечания и предложения направляйте на dmvn@mccme.ru, а обновления электронной версии документа находится на http://dmvn.mexmat.net.Остаётся пожелать читателю успехов при изучении математической логики, а также удачи на экзамене,ежели таковой придётся сдавать.Набор и вёрстка: DMVN CorporationПоследняя редакция: 27 января 2006 г.31. Булева алгебра1.1. Функции булевой алгебрыПусть B = {0, 1}. Рассмотрим функции вида f : Bn → B. Они называются булевыми функциями илифункциями алгебры логики.
Множество всех таких функций обозначается P2 . Любую такую функцию можнозадать таблицей:x100...1...............x200...1xn−100...1xn01...1f (x1 , . . . , xn )f (0, 0, . . . , 0, 0)f (0, 0, . . . , 0, 1)...f (1, 1, . . . , 1, 1)Слева расположены всевозможные наборы значений переменных (всего их 2n ), а справа значение функцииnна этом наборе (0 или 1). Всего функций от n переменных будет p2 (n) = 22 . Для экономии места иногда удобнофункцию n переменных задавать строкой из 2n чисел — значений функции, записанных в том порядке, в какомони были бы расположены в последнем столбце таблицы. Рассмотрим подробнее эти функции.• n = 1. Здесь всего будет 4 функции:x01000x01x10111Здесь 0, 1 — константы, x — тождественная функция, x — отрицание x.• n = 2. Здесь будет 16 функций. Выпишем некоторые:x10011x20101x1 &x20001x1 ∨ x20111x1 ⊕ x20110x1 → x21101x1 /x21110x1 ↓ x21000Здесь x1 &x2 — конъюнкция или логическое И, x1 ∨ x2 — дизъюнкция или логическое ИЛИ, x1 ⊕ x2 — суммапо модулю 2, x1 → x2 — импликация, x1 /x2 — штрих Шеффера, x1 ↓ x2 — стрелка Пирса.1.2.
Существенные и несущественные переменныеОпределение. Функция f (x1 , . . . , xn ) называется существенно зависящей от переменной xi , если существуют два набора значений переменных αe0 = (α1 , . . . , αi−1 , 0, αi+1 , . . . , αn ) и αe1 = (α1 , . . . , αi−1 , 1, αi+1 , . . . , αn ),отличающиеся только значением переменной xi , такие, что f (eα0 ) 6= f (eα1 ). В этом случае говорят, что xi — существенная переменная. Переменная xi называется несущественной, если она не является существенной, т. е.для любых двух наборов такого вида имеем f (eα0 ) = f (eα1 ).Пример 2.1. Конъюнкция существенно зависит от переменной x1 , так как (0&1) 6= (1&1).Если функция f (x1 , . .
. , xn ) несущественно зависит от xi , тоf (α1 , . . . , αi−1 , 0, αi+1 , . . . , αn ) = β,f (α1 , . . . , αi−1 , 1, αi+1 , . . . , αn ) = β.Её таблица имеет следующий вид:x1...xi−1α1...αi−1α1...αi−1xi...0...1...xi+1...xnαi+1...αnαi+1...αnf (x1 , . . . , xn )...β...β...Вычеркнем все наборы, у которых xi = 1, и i-й столбец, получим новую функцию g(x1 , . . . , xi−1 , xi+1 , .
. . , xn ),такую что g(α1 , . . . , αi−1 , αi+1 , . . . , αn ) = f (α1 , . . . , αi−1 , 0, αi+1 , . . . , αn ). Её таблица имеет видx1...α1...xi−1...αi−1...xi+1...αi+1......xn...αn4g(x1 , . . . , xi−1 , xi+1 , . . . , xn )...f (α1 , . . . , αi−1 , 0, αi+1 , . . . , αn )...Говорят, что функция g получилась из функции f отбрасыванием несущественной переменной xi .Аналогично можно и добавлять несущественные переменные. Пусть дана функция f (x1 , . .
. , xn ), построимновую функцию h(x1 , . . . , xn , xn+1 ) = f (x1 , . . . , xn ). Тогда xn+1 будет несущественной переменной функции h,действительно, h(α1 , . . . , αn , 0) = f (α1 , . . . , αn ) = h(α1 , . . . , αn , 1). Говорят, что функция h получилась из функции f добавлением несущественной переменной xn+1 .Определение. Функции h1 и h2 называются равными, если одна получена из другой в результате добавленияи отбрасывания несущественных переменных.Пример 2.2. Пусть дана функция h1 (x1 , x2 ), несущественно зависящая от переменной x1 , отбросим её,получим функцию g(x2 ), добавим несущественную переменную x3 , получим функцию h2 (x2 , x3 ).
Функции h1 иh2 равны, хотя таблицы у них разные!x10011x20101h1 (x1 , x2 )x20→ 01011x20011g(x2 )→01x30101h2 (x2 , x3 )00111.3. ФормулыОпределение. Пусть дано некоторое множество функций F = {f1 (x1 , . . . , xn1 ), . . . , fs (x1 , . . . , xns ), . . . }.Определим понятие формулы над множеством F индуктивно. Функции fi (x1 , .
. . , xni ) являются формуламинад F . Если A1 , . . . , Ani — переменные или формулы над F , то fi (A1 , . . . , Ani ) тоже является формулой над F .Пример 3.1. F = {ϕ(x1 , x2 )}, тогда ϕ(x1 , x2 ) и ϕ x2 , ϕ(x3 , x4 ) будут формулами над F , а ϕ(x1 , x2 , x3 ) —нет.Значение переменной xi на наборе R = (α1 , . .
. , αs ) равно αi . Пусть уже определены A1 , . . . , Ani . ТогдаRfi (A1 , . . . , Ani )= fi A1 , . . . , AniRRR(1).RОтсюда следует, что любая формула выражает некоторую функцию.Определение. Формулы называются эквивалентными (равными), если они выражают равные функции.Рассмотрим множество функций F = {x1 &x2 , x1 ∨ x2 , x1 , x1 }. Примеры равных формул над F :x1 &x2 = x2 &x1 ,x1 ∨ x1 = x1 ,x1 &x2 = x1 ∨ x2 ,Введём ещё одну полезную функцию:σx :=((x1 ∨ x2 )&x3 = (x1 &x3 ) ∨ (x2 &x3 ).x, σ = 1;x, σ = 0.(2)Заметим, что xσ = 1 ⇔ x = σ. В самом деле, x1 = 1 ⇔ x = 1, и x0 = x = 1 ⇔ x = 0.Введём соглашения по записи формул. Знак & можноумножениев алгебре. Для ассоциа не писать, кактивных операций внутренние скобки писать не будем: (x1 ∨ x2 ) ∨ x3 ∨ x4 ∨ x5 = (x1 ∨ x2 ∨ x3 ∨ x4 ∨ x5 ).Внешние скобки также можно опускать и писать x1 ⊕ x2 вместо (x1 ⊕ x2 ). Иногда будем использовать для записиотрицания знак ¬x = x, а для конъюнкции — знак «∧». Введём сокращения:nA1 & .
. . &An = & Ai ,i=1A1 ∨ · · · ∨ An =n_Ai ,i=1A1 ⊕ · · · ⊕ An =nXAi .i=11.4. СДНФРассмотрим формулу xσ1 1 . . . xσnn . Она равна единице только на одном наборе (σ1 , . . . , σn ).Теорема 1.1 (О разложении функции по переменным). Дана функция f (x1 , . . . , xn ) и число 1 6 k 6 n.Имеет место формула для f над множеством {∨, &, ¬, f (x1 , .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
