Пренексная нормальная форма для формул ИП

Формула φсигнатуры Σ называется бескванторной, если она не содержит кванторов. Говорят, что бескванторная формула φнаходится в дизъюнктивной (конъюнктивной) нормальной форме, если она получается из некоторой формулы ψисчисления АВ, находящейся в ДНФ (КНФ) заменой всех пропозициональных переменных x₁,…,x_nна некоторые атомарные формулы φ₁,…,φ_nсигнатуры Σ соответственно.

Говорят, что формула φсигнатуры Σ находится в пренексной нормальной форме (ПНФ), если она имеет вид Q₁x₁…Q_nx_nψ, где Q_i,‑кванторы1≤i≤n, а ψ‑бескванторная формула, находящаяся в ДНФ.

Теорема 1. Для любой формулы φсигнатуры Σ существует формула ψсигнатуры Σ, находящаяся в ПНФ и эквивалентная формуле φ.

Пример 1.Формулу χ = x yφ(x,y)→ x yψ(x,y)привести к пренексной нормальной форме. считая формулы φи ψатомарными.

Решение.Избавившись от импликации, получаем χ≡( x yφ(x,y))∨ x yψ(x,y). Используя утверждение 3, пп. а, б утверждения 4 и теорему о замене, получаем χ≡ x yφ(x,y)∨ x yψ(x,y). Так как в формуле x yψ(x,y)переменные х, у являются связанными, то по пп. д, е утверждения 4 имеем χ≡ x y(φ(x,y)∨ x yψ(x,y)). Пусть u, ∨‑некоторые новые переменные. Тогда по пунктам ж, з утверждения 4 получаем χ≡ x y(φ(x,y)∨ u vψ(u,v)),откуда по пунктам ж, з утверждения 4 χ≡ x y u v(φ(x,y)∨ψ(u,v)). Формула φ(x,y)∨ψ(u,v)находится в ДНФ, а значит, формула x y u v(φ(x,y)∨ψ(u,v)) находится в ПНФ.

Теорема 2. Все доказуемые в ИП^Σ формулы являются тождественно истинными.

Доказательство проводим индукцией по длине вывода формулы. Очевидно, что аксиомы ИП^Σ являются тождественно истинными. Проверку того, что правила вывода 1-3 сохраняют тождественную истинность, мы оставляем читателю в качестве упражнения.

Следствие 1. Исчисление ИП^Σнепротиворечиво, т.е. не все формулы ИП^Σ доказуемы в ИП^Σ.

В ИП^Σ справедлив аналог теоремы о полноте в исчислении высказываний:

Теорема 3(теорема Геделя о полноте). Формула φисчисления ИП^Σ доказуема тогда и только тогда, когда φтождественно истинна.

Таким образом, проверка доказуемости формулы φсводится к проверке ее тождественной истинности. Однако в отличие от ИВ в общем случае не существует алгоритма распознавания доказуемости формул ИП^Σ, т. е. ИП^Σ неразрешимо. Тем не менее если в формуле φ"записать", что каждая переменная может принимать конечное число значений, то перебором всех возможных систем можно установить, является ли формула тождественно истинной или нет.

Машины Тьюринга

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

конечная лента,разбитая на конечное число ячеек.В каждый момент времени в ячейках записаны буквы из некоторого алфавита (где , ), называемого внешним алфавитом машины.Ячейка, в которой записан символ , называется пустой.Если в какой–то момент времени лента имеет ячеек, то состояние ленты полностью описывается словом , где ­– состояние первой (слева) ячейки, – состояние второй ячейки и т.д.

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

ПрограммаΠ, т.е. совокупность выражений (где ), называемых командами, каждое из которых имеет один из следующих видов:

сдвиг головки, находящейся в состоянии напротив ячейки с буквой , на одну ячейку влево с заменой состояния на ;

сдвиг головки, находящейся в состоянии напротив ячейки с буквой , на одну ячейку вправо с заменой состояния на ;

замена буквы в текущей ячейке на букву , а также замена состояния головки на состояние

Замечание 1.1) Команды не могут начинаться со слов .

2) .

Таким образом, машина Тьюринга– это пятерка .

Машинным словом называется слово , где – состояние ленты, – состояние головки, находящейся напротив ячейки с состоянием , занимающей то же положение среди других ячеек, что и буква в слове .

Пустое слово обозначим через .

Опишем преобразование машинного слова в машинное слово за один шаг работы машины :

если , то при и при ;

если , то при и при ;

если , то .

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

Пусть – множество натуральных чисел с нулем, .

Частичная функция – это отображение , где .Если , то частичная функция называется всюду определенной. Если , то частичная функция называется нигде ен определенной.

Для любого числа через обозначим слово, состоящее из числа единиц: .Для любой –ки слово называется записью этой –ки.

Частичная функция , где , называется вычислимой по Тьюрингу, если существует машина Тьюринга такая, что

1) ;

2)машина применима к записи –ки ;

3) для и .

Пример 1.Построим машину Тьюринга , вычисляющую функцию .Пусть , где , , программа Π состоит из команд: