Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Топ:
Оснащения врачебно-сестринской бригады.
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Интересное:
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2018-01-29 | 456 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!