Основные понятия и определения дисциплины

Истинность и выполнимость формул.

Если задача записывается в виде формулы, то выполнимость формулы означает существование решения задачи, а модель, в которой эта формула истинна, дает решение задачи. Рассматриваемая в настоящей работе логика ветвящегося времени (Computational tree logic – Ctl), является одной из модальных логик, ориентированных на изучение процессов, происходящих во времени. В этой логике к пропозициональным связкам добавляются следующие временные: ○ – ''в следующий момент'', □ – ''во всякий момент'', ◊ – ''в некоторый момент'', U – ``до тех пор, пока'', а также кванторы " и $, стоящие перед каждой временной связкой (и только перед ней).
Истинность формулы определяется в модели: в вершинах связного ориентированного графа, в котором каждой вершине приписаны истинностные значения пропозициональных переменных. Формула называется выполнимой, если существует модель, в начальной вершине которой эта формула истинна. Формула называется общезначимой, если она истинна во всякой модели. Определим понятие модели и истинности формулы в модели.

12. 
    Нормальные алгоритмы Маркова.
    

А.А. Марков разработал строгую теорию определенного класса алгоритмов, которые называются нормальными алгорифмами Маркова. Для них исходными данными и результатами являются высказывания, записанные в виде слов, принадлежащих некоторому алгоритму А.
Если алфавит А входит во множество В, но АВ, то говорят, что В – расширение алфавита А.
Пусть RA и существует некоторое PR, в этом случае говорят, что Р – это вхождение подстроки в высказывание R.
Марковская подстановка – это замена первого вхождения подслова Р в слове R на слово Q: (P, Q)=PQ.
Если PR, то говорят, что Марковская подстановка не применима к слову R. Частными случаями Марковских подстановок являются пустые вхождения:
( ,Q), (P, ), ( , ). Здесь пустые слова в скобках эквивалентны .
Пример 1:
Если R=192375923A, тогда
(923, 0000)R=1000075923
Пример 2:
Пусть R=слово, тогда
(ра, да) (не применимо)
Пример 3:
R=паровоз
(овоз, _)R=пар_
Пример 4:
R=книга
( , ) R=книга
Большинство алгоритмов не являются нормальными алгорифмами. Однако, т. к. нормальные алгорифмы описаны с полной математической строгостью и точностью, то они могут служить средством обоснования математики и использоваться при исследовании алгоритмически неразрешимых проблем на основе гипотезы, называемой принципом нормализации. Он заключается в следующем: каков бы ни был алгоритм, для которого допустимыми исходными данными и соответствующими им результатами являются слова некоторого алфавита А, всегда существует эквивалентный ему нормальный алгоритм.

13.