Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Топ:
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Дисциплины:
2018-01-29 | 445 |
5.00
из
|
Заказать работу |
|
|
Формула φ сигнатуры Σ называется бескванторной, если она не содержит кванторов. Говорят, что бескванторная формула φнаходится в дизъюнктивной (конъюнктивной) нормальной форме, если она получается из некоторой формулы ψ исчисления АВ, находящейся в ДНФ (КНФ) заменой всех пропозициональных переменных x1,…,xn на некоторые атомарные формулы φ1,…,φn сигнатуры Σ соответственно.
Говорят, что формула φ сигнатуры Σ находится в пренексной нормальной форме (ПНФ), если она имеет вид Q1x1…Qnxnψ, где Qi,‑ кванторы 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. Построим машину Тьюринга , вычисляющую функцию .Пусть , где , , программа Π состоит из команд:
|
|
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!