Лекция «аксиоматическая Теория Гильберта-Аккермана» По Дискретной Математике (Сабуров М. А

Аксиоматическая система Гильберта-Аккермана

Исчисление предикатов

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

f)кванторы , .

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

Правила образования формул также расширим:

a)Все простые высказывания суть формулы.

b)Если Fn – n-местная предикатная переменная, а x1,…, xn суть предметные переменные, то Fn (x1,…, xn) – формула; при этом предметные переменные x1,…, xn называют свободными.

c)Если A(x) есть формула, в которой предметная переменная x либо является свободной, либо вовсе не встречается, то xA(x) и xA(x) также суть

формулы, причем предметная переменная x в этих новых формулах называется

связанной, а формула A(x) – областью действия квантора.

d)Если A и B – формулы, такие, что одна и та же предметная переменная не встречается связанной в одной формуле и свободной в другой, то (A B) –

формула.

e)Если A – формула, то A – формула.

Как и в исчислении высказываний, для сокращения записи введем новые символы операций: &, , , а также правила для экономии скобок. Как и раньше, будем опускать внешние скобки и скобки под чертой отрицания. Будем считать, что кванторы связывают сильнее, чем конъюнкция, конъюнкция связывает сильнее, чем дизъюнкция, а дизъюнкция, в свою очередь, сильнее, чем импликация и эквивалентность. Также будем опускать верхний индекс при предикатных переменных, так как его можно легко восстановить, пересчитав использованные места.

К прежним аксиомам добавим еще две: A5: xF (x) F ( y)

A6: F ( y) xF (x)

Правила вывода включают правило подстановки (α), правило заключения (β), схемы для кванторов (γ) и правило переименования связанных переменных (δ).

Правило подстановки:

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

α2: в тезисе можно заменить любую свободную предметную переменную, всюду, где она встречается в нем, любой другой предметной переменной, не являющейся связанной в исходном тезисе.

Аксиоматическая система Гильберта-Аккермана

α3: в тезисе можно заменить любую n-местную предикатную переменную,

всюду, где она встречается в нем, любой формулой A, содержащей по меньшей мере n свободных переменных (обозначим их x1,…, xn), при условии, что ни одна из прочих свободных переменных, возможно, входящих в A, не является связанной в исходном тезисе, и после подстановки снова получается формула. При замене каждого вхождения заменяемой предикатной переменной вместо каждой предметной переменной xi в формулу A подставляется переменная, стоящая на i-том месте при данном вхождении заменяемой предикатной переменной; при этом заменяются обязательно все вхождения xi в A.

Правило заключения сохраняется в неизменном виде:

β: A B , A |– B.

Схемы для кванторов предполагают, что предметная переменная x является свободной в формуле B(x) и не встречается в формуле A:

γ1: A B(x) |– A xB(x) .

γ2: B(x) A |– xB(x) A .

Правило переименования связанных переменных:

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