15. Пнф. Алгоритм приведения к пнф.

Для облегчения анализа сложных суждений формулы алгебры предикатов рекомендуется приводить к нормальной форме. Если в алгебре высказываний приняты две нормальные формы (ДНФ - дизъюнктивная и КНФ -конъюнктивная), то в алгебре предикатов - одна предваренная нормальная форма (ПНФ), суть которой сводится к разделению формулы на две части: кванторную и безкванторную. Для этого все кванторы формулы выносят влево, используя законы и правила алгебры предикатов.

В результате этих алгебраических преобразова­ний может быть получена формула вида: _x1 _x2 _xn(M), где {; } , а М – матрица формулы. Кванторную часть формулы _x1 _x2 _xn иногда называют префиксом ПНФ.

Шаг 1. Исключить всюду логические связки  и 

Шаг 2. Продвинуть отрицание до элементарной формулы

Шаг 3. Переименовать связанные переменные по правилу:

“найти самое левое вхождение предметной переменной такое, что это вхождение связано некоторым квантором, но существует еще одно вхождение этой же переменной; затем сделать замену связанного вхождения на вхождение новой переменной “, операцию повторять пока возможна замена связанных переменных;

Шаг 4. Вынести кванторы влево по законам алгебры логики.

Шаг 5. Преобразовать бескванторную матрицу к виду КНФ.

16. Ссф. Алгоритм скалема.

Для устранения кванторов существования из префикса формулы разработан алгоритм Сколема, вводящий сколемовскую функцию для связывания предметной переменной квантора существования с другими предметными переменными.

Шаг 1. Представить формулу F в виде ПНФ.

Шаг 2. Найти в префиксе самый левый квантор существования:

a) если квантор находится на первом месте префикса, то вместо переменной, связанной кван­тором существования, подставить всюду предметную по­стоянную a , отличную от встречающихся предметных постоянных в матрице формулы, а квантор существования удалить;

б) если квантор находится не на первом месте префикса, т.е. _x1_x2_xi-1_xi .., то выбрать (i-1)-местный функциональный символ, отлич­ный от функциональных символов матрицы М и выполнить замену предметной переменной x_i, связанной кванто­ром существования, на функцию f(x₁;x₂ ; x_i-1 ) и квантор существования удалить.

Шаг 3. Найти следующий справа квантор существования и перей­ти к исполнению шага 2, иначе конец.

Формулу ПНФ, полученную в результате введения сколемовской функции называют сколемовской стандартной формой формулы (ССФ).

17. Исчисление предикатов. Вводные замечания, интерпретация формул.

Все методы и результаты исчисления высказываний можно перенести на исчисление предикатов, т. е. каждая теорема и любой вывод исчисления высказываний становятся теоремой и выводом исчисления предикатов, если пропозициональные переменные заменить формулами языка предикатов, причем все вхождения одной и той же переменной везде заменить одной и той же формулой. Каждая схема теоремы и каждая схема вывода также сохраняются, если под знаками пропозициональных переменных принимать формулы языка предикатов.

Для того, чтобы формализовать процесс рассуждения в исчислении предикатов, необходимо выделить класс фор­мул, определяющих их эквивалентные преобразования при наличии кванторов, и класс отношений между формулами формирующих последователь­ную цепь формул от посылок до заключения. Следует отметить, что правила, аксиомы и законы исчисления высказываний есть подмножество правил, аксиом и законов исчисления предикатов. Дополнительные пра­вила, аксиомы и законы определяют возможности введения и удаления кванторов, подстановки и cмeны кванторов.

Под интерпретацией следует понимать систему, состоящую из не­пустого множества V, называемом универсумом, и однозначного отображения на двухэлементное множество {и; л}, кото­рое каждому предикатному символу Pⁿ (t₁; t₂; t_n ) ставит в соот­ветствие n - местное отношение на множестве V, каждому функциональному символу f ⁿ_i (t₁; t₂; t_n ) - n-местную операцию на множестве V, каждой предметной постоянной - элемент множе­ства V.

Формула, не содержащая свободных переменных, называется замк­нутой и представляет собой высказывание об элементах, функциях и отношениях, которое принимает значение и или л.

Формула, содержащая свободные переменные, называется открытой и представляет собой отношений, заданное на множестве V,

Это отношение может быть истинным для одних значений из области интепретации и ложным для других.

Тождественно истинные формулы (или тавтологии) -это особый класс формул исчисления предикатов, которые принимают значение “истины” для всех интерпретаций входящих в нее предметных постоянных, функциональных и предикатных символов; эти формулы иг­рают роль законов и аксиом исчисления предикатов; любые подстановки и замещения в тождественно истинной формуле не изменяют ее значения.

Тождественно ложные формулы (или противоречие)-это особый класс формул исчисления предикатов, которые принимают значение “ложь” для всех интерпретаций входящих в нее предметных постоянных, функциональных и предикатных символов; любые подстановки и замещения в тождественно ложной формуле не изменяют ее значения.

Выполнимые формулы - это особый класс формул исчисления преди­катов, которые принимают значение “истина”в некоторой области, т.е. не для всех интерпретаций входящих в нее предметных постоянных, функциональных и предикатных символов.