Формальная арифметика. Система аксиом

Пусть - теория первого порядка, в число предикатных букв которой входит . Будем сокращенно писать вместо ; и вместо .

Определение 1: Теория называется теорией первого порядка с равенством, если следующие формулы являются теоремами теории :

1) - рефлексивность равенства,

2) - подстановочность равенства, где и - предметные переменные, - произвольная формула, а получается из заменой каких-нибудь (не обязательно всех) свободных вхождений буквой .

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

Арифметика, наряду с геометрией, является интуитивной областью математики. Поэтому будет естественным начинать процесс формализации и строгого обоснования математики именно с арифметики. Первое полуаксиоматическое построение арифметики было предложено Дедекиндом в 1901 году. Оно известно под названием «система аксиом Пеано». Эту систему можно сформулировать следующим образом:

(Р1) Число 0 – натуральное число.

(Р2) Для любого натурального числа существует число , непосредственно следующее за .

(Р3) для любого натурального числа .

(Р4) Если , то .

(Р5) Пусть есть свойство, которым обладают одни натуральные числа, и которым могут не обладать другие числа. Если 1) натуральное число 0 обладает свойством ; 2) для всякого натурального числа , обладающего свойством , число также обладает свойством ; тогда свойством обладают все натуральные числа (принцип индукции).

Этих аксиом, вместе с некоторым фрагментом теории множеств, достаточно для построения не только арифметики, но и теории рациональных, вещественных и комплексных чисел (это было сделано немецким математиком Ландау в 1930 году). Однако в этих аксиомах содержатся интуитивные понятия, такие, например, как «свойство». Это мешает всей системе быть строгой формализацией. Поэтому далее будет построена теория первого порядка , основанная на системе аксиом Пеано, которая окажется достаточной для вывода всех основных результатов элементарной арифметики. Эта теория первого порядка будет иметь единственную предикатную букву , единственную предметную константу и три функциональные буквы . Впрочем, чтобы не порывать с привычными по неформальной арифметике обозначениями, в дальнейшем мы будем писать вместо , вместо и вместо, соответственно, , где и - термы.

Собственные аксиомы теории S:

(S1) ;

(S2) ;

(S3) ;

(S4) ;

(S5) ;

(S6) ;

(S7) ;

(S8) ;

(S9) , где - произвольная формула теории .

Замечание 1: Если натуральное число, которое не следует ни за каким другим натуральным числом, называть ни нулём, а единицей (обозначать: 1), то аксиомы (S3), (S5) и (S7) необходимо заменить соответственно на следующие аксиомы:

(S3^*) (число 1 не следует ни за каким другим натуральным числом);

(S5^*) ;

(S7^*) .

А также в аксиоме (S9) следует заменить на .

Замечание 2: Аксиомы (S1) – (S8) являются конкретными формулами, в то время как (S9) представляет собой схему аксиом, т. к. формула - произвольная. При этом схема аксиом (S9), которую будем называть принципом математической индукции, не соответствует полностью аксиоме (Р5) системы аксиом Пеано. Это происходит потому, что в аксиоме Пеано интуитивно предполагается, что число различных свойств натуральных чисел несчетно (т. е. имеет мощность ), а схема аксиом (S9) счётна, множество всех формул теории счётно.

Замечание 3: Аксиомы (S3) и (S4) соответствуют аксиомам (Р3) и (Р4) системы аксиом Пеано. Аксиомы (Р1) и (Р2) системы Пеано обеспечивают существование и операции «непосредственно следующий», которым в теории соответствует предметная константа и функциональная буква . Аксиомы (S1) и (S2) обеспечивают необходимые свойства равенства, которые Дедекиндом и Пеано предполагались интуитивно очевидными. Аксиомы (S5) - (S8) представляют собой рекурсивные равенства, служащие определением операций сложения и умножения.

С помощью правила modus ponens и схемы аксиом (S9) можно получить правило индукции: из и выводимо .

Следующая лемма является очевидным и непосредственным следствием аксиом.

Лемма 1: Для любых термов , и теории следующие формулы являются теоремами в :

(S1^*) ;

(S2^*) ;

(S3^*) ;

(S4^*) ;

(S5^*) ;

(S6^*) ;

(S7^*) ;

(S8^*) .

Доказательство: Все свойства (S1^*) – (S8^*) доказываются одинаково. Сначала необходимо образовать замыкание для аксиом (S1) - (S8) по правилу обобщения (), а затем применить аксиому (А4) (логическая аксиома логики предикатов: , где - терм, свободный для в с подходящими термами , , ).

Далее будут рассмотрены обычные свойства равенства (для теории первого порядка с равенством).

Теорема 1: Для любых формул , и теории следующие свойства являются теоремами этой теории.

(a) ;

(b) ;

(с) ;

(d) ;

(е) ;

(f) ;

(g) ;

(h) ;

(i) ;

(j) ;

(l) ;

(m) ;

(n) ;

(о) .

Доказательство: Докажем некоторые свойства для примера.

(a) 1. (по аксиоме (S5^*));

2. (по аксиоме (S1^*));

3. (из пунктов 1 и 2 по правилу );

4. (из пунктов 1 и 3 по правилу ).

(d) 1. (свойство (с));

2. (1, тавтология);

3. (свойство (b));

4. (из 2,3, тавтология);

5. (4, тавтология).

(е) Применим правило индукции к формуле: .

Остальные свойства можно доказать аналогично.

Теорема 2: Для любых термов , и следующие формулы являются теоремами теории :

(a) (дистрибутивность слева);

(b) (дистрибутивность слева);

(с) (ассоциативность умножения);

(d) .

Доказательство:

(a) Доказательство можно провести индукцией по ├ .

(b) Следует из пункта (a) и коммутативности умножения (см. теорему 1, пункт (n)).

(с) Можно доказать индукцией по z: ├ .

(d) Доказывается индукцией по z с использованием аксиомы (S4^*). Можно показать, что ├ .

В дальнейшем термы мы будем называть цифрами, и обозначать, как обычно, 0, 1, 2, 3,.... Для любого неотрицательного соответствующая цифра – это 0 с штрихами.

Натуральные числа можно определить рекурсивно: 0 – есть число; если - натуральное число, то и также натуральное число.

Теорема 3:

(a) ├ ;

(b) ├ ;

(с) ├ ; (и т. д. для 3, 4,...);

(d) ├ ;

(е) ├ ;

(f) ├ ;

(g) ├ ;

(h) ├ ;

(i) ├ ;

(j) ├ .

Доказательство:

(a) 1. (S6^*);

2. (S5^*);

3. (S2^*);

4. (1, 3, теорема 1);

5. (4, определение цифры ).

(с) 1. (S8^*);

2. (b);

3. (2, теорема 1, (е));

4. (1, 3, теорема 1, (с));

5. (4, определение цифры 2).

(d) Обозначим через формулу . Тогда видно, что ├ . Из аксиомы (S3^*) ├ . Отсюда на основании аксиомы (S6^*) получаем: ├ . Следовательно, в силу тавтологии , имеем: ├ . Далее, в силу тавтологии , получаем: ├ . Применяя правило индукции, имеем: ├ . Затем, с помощью правил обобщения и логической аксиомы (А4), получаем требуемое утверждение (d).

Остальные свойства доказываются аналогично.

Определение 2: а) означает, что ;

б) означает, что ;

в) означает, что ;

г) означает, что ;

д) означает, что .

Теорема 4: Каковы бы ни были термы , и , следующие формулы выводимы в теории :

(a) ;

(b) ;

(с) ;

(d) ;

(е) .

Доказательство:

(a) Следует из того, что . Индукцией по z можно доказать, что ├ .

(b) - (е) предлагается доказать самостоятельно.

Определение 3: Будем говорить, что делится на , если существует такое, что .

Теорема 5: Следующие формулы выводимы в теории :

(a) ;

(b) ;

(с) ;

(d) ;

(е) ;

(f) .

Доказательство: (a), (b): .

Аналогично доказываются остальные свойства делимости.

Теорема 6: (Полная индукция).

Пусть свойство таково, что для любого натурального числа , из того, что этим свойством обладают все натуральные числа, меньшие , вытекает, что им обладает и число . Тогда свойством обладают все натуральные числа, т. е.: ├ .

Доказательство: По условию, свойством обладают все натуральные числа, меньшие . Значит, в частности, свойством обладает и число 0, и число, за которым следует . Следовательно, по аксиоме индукции, выполнено . По правилу обобщения (аксиома (А4), ) имеем: . Что и требовалось доказать.

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

Булевы функции. Основные понятия и определения. Реализация булевых функций формулами.

С точки зрения алгебры высказываний логические операции полностью характеризуются истинностными таблицами. При этом можно забыть о том, что мы рассматриваем какие-то операции над высказываниями, и иметь дело лишь с самими таблицами. Таблицу можно рассматривать, как способ задания некоторой функции. Таким образом, мы приходим к понятию функции алгебры логики, которое и будем исследовать в дальнейшем. Однако полезно не забывать об указанных интерпретациях логических связок.

В отличие от алгебры высказываний мы будем дальше употреблять следующие обозначения: 1 и 0 вместо привычных символов и – «истина», л – «ложь». При этом если нет никакой оговорки, мы не будем вкладывать «арифметический смысл» в эти символы.

Будем исходить из счетного алфавита переменных .

Определение 1: Пусть обозначает множество всех функций , переменные которых определены на множестве и таких, что , если . Функции из множества будем называть функциями алгебры логики (или булевыми функциями).

Таким образом, все булевы функции принимают свои значения из множества , т. е. могут быть истинными или ложными.

Замечание: В общем случае логические переменные могут принимать одно из значений. Такая логика называется - значной логикой. Перечень всех символов составляет алфавит, а сами символы - буквы алфавита.

Определение 2: Функция полностью определена, если задана таблица, содержащая всевозможные варианты значений переменных (наборы) и соответствующие им значения функции.

Число всех функций, зависящих от переменных, конечно и равно . Поэтому, для выяснения свойств данной функции достаточно просмотреть её таблицу. Однако с ростом числа аргументов таблица сильно усложняется. Для устранения этого недостатка введем следующее определение.

Определение 3: Будем говорить, что функция существенно зависит от переменной, если найдутся два набора, отличающиеся только - й переменной: и такие, что. Переменная называется существенной для функции. Все переменные, от которых функция не зависит существенно, называются фиктивными.

Определение 4: Число всех переменных, от которых функция зависит существенно, называется порядком функции.

Определение 5: Две функции называются равными, если одна из них может быть получена из другой путем добавления или изъятия некоторых фиктивных переменных.

Замечание: Из сказанного следует, что если задана конечная система функций из множества , то можно считать, что все эти функции зависят от одних и тех же переменных. С другой стороны, если дана функция, отличная от константы, то путем отождествления переменных из неё можно получить равную ей функцию, все переменные которой являются существенными.

Для дальнейшего изложения введём в рассмотрение следующие элементарные функции: , , , , , , , , (сложение по модулю 2), (штрих Шеффера). Определение и логическое значение каждой из этих функций было приведено выше. Отметим только, что функция равна отрицанию эквивалентности, а функция равна отрицанию конъюнкции. Функции и называются константами. Константы не зависят от переменных.

Замечание: Далее вместо символа будем употреблять символ умножения или, как в обычной алгебре, знак этой операции будем опускать. Символы и в дальнейшем будут употребляться для обозначения сложения по , при этом, исходя из определения: . Можно также отметить, что константы и не зависят ни от одной переменной, следовательно, имеют нулевой порядок.

Как и в элементарной алгебре, исходя из «элементарных» функций, можно строить формулы.

Пусть имеется счетное множество переменных , где . Рассмотрим конечную или счетную систему функций алгебры логики над этим множеством:

. (*)

Введем понятие формулы над этой системой функций.

Определение 6 (интуитивное):

1. Выражение называется формулой над рассматриваемой системой функций.

2. Выражение называется формулой над системой функций (*), если – формула или переменная из множества , а – произвольная функция из системы (*).

Сопоставим каждой формуле функцию алгебры логики.

Определение 7 (индуктивное):

1. Формуле , где сопоставим функцию , где .

2. Формуле , где выражения при являются либо формулами, либо переменными из множества , а – функция системы (*), поставим в соответствие функцию . Здесь, если – переменная, то совпадает с ; если – формула, то – функция, сопоставленная этой формуле.

Полученные в соответствии с этим определением функции называются суперпозициями функций системы (*). Примеры формул: , , .

Будем говорить, что функция получена из функции путем переименования переменных.

Например, функция получена из функции путем переименования переменных.

Нетрудно видеть, что при переименовании переменных возможно появление новых переменных, исчезновение старых переменных, перестановка переменных местами и отождествление переменных.

Если функция соответствует формуле , то говорят, что формула реализует функцию . Поскольку функции рассматриваются с точностью до фиктивных переменных, то будем считать, что формула реализует и любую функцию, равную . Функция , соответствующая формуле , и есть суперпозиция.

Пусть формула построена из функций . Можно считать, что функции зависят от одних и тех же переменных.

Определение 8: Две формулы называются эквивалентными, если им сопоставлены равные функции.

Эквивалентные формулы будем соединять знаком равенства.

Например, формулы и реализуют каждая функцию . Поэтому . Аналогично: .

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

Теорема 1 (о разложении): Пусть – произвольная функция алгебры логики. Тогда ее можно представить в следующей форме:

. (**)

(Здесь мы употребляем сокращенную запись ).

Доказательство: Заметим сначала, что и что тогда и только тогда, когда , ,..., . Рассмотрим теперь произвольные и пусть . Тогда в левой части соотношения получим . Правая часть в силу сделанного замечания также дает . Теорема доказана.

Большое практическое значение имеют следствия из этой теоремы.

Следствие 1: Если , то представление (**) принимает следующий вид: .

Следствие 2: Если , то представление (**) превращается в следующее равенство:

.

Это разложение называется совершенной дизъюнктивной нормальной формой (С.Д.Н.Ф.) функции . Оно определено для любой функции из множества булевых функций , не равной константе .