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

Формула φ сигнатуры Σ называется бескванторной, если она не содержит кванторов. Говорят, что бескванторная формула φнаходится в дизъюнктивной (конъюнктивной) нормальной форме, если она получается из некоторой формулы ψ исчисления АВ, находящейся в ДНФ (КНФ) заменой всех пропозициональных переменных 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. Построим машину Тьюринга , вычисляющую функцию .Пусть , где , , программа Π состоит из команд: