Логика предикатов

Вид материала

Документы

Содержание Равносильность в логике предикатов. Нормальные формы в логике предикатов. Проблема разрешения в логике предикатов.

Подобный материал:

• Математическая логика, 1012.22kb.
• Логика в образовании, 153.37kb.
• Концепция языка Пролог и сферы его применения. Процедурная и декларативная трактовка, 31.15kb.
• Математическая логика Лектор 2010/11 уч года: к ф-м наук Носов В. А. Аннотация, 34.32kb.
• Лекции по математической логике и теории алгоритмов для студентов 2 курса специальности, 769.24kb.
• Программа курса и темы практических занятий; Логика в таблицах и схемах. Логика как, 1722.34kb.
• «Искусственный интеллект.», 86.69kb.
• 6. Исчисление предикатов и теории первого порядка, 101.56kb.
• Логика высказываний. Основные понятия и определения. Логические функции одной и двух, 6.36kb.
• Классическая логика предикатов, 30.55kb.

Логика предикатов.

Рассмотренной нами алгебре высказываний оказывается недостаточно даже для изучения простых заключений, тем более для доказательства теорем и т.д. Это объясняется тем, что алгебра высказываний интересуется лишь истинностью или логичностью исходных высказываний, отвлекаясь от их последовательности и строения. В отличие от алгебры высказываний логика предикатов интересуется истинностью или логичностью высказываний в зависимости от их структуры и последовательности.

Пусть М – множество элементов произвольной природы, элементы x, y, z, которого обозначаются малыми латинскими буквами и называются предметными переменными (предметами). n - местным предикатом F(x₁,...,x_n) называется функция от n переменных определенная на множестве М и принимающая значение И и Л. Примером одноместного предиката F(x) является предикат – свойство. Например, предикат: «х есть простое число», в зависимости от х может быть И или Л. Предикаты задаются своими таблицами (матрицами) истинности. Например, для предиката «х есть простое число» матрица истинности имеет вид:

х	1	2	3	4	5	6	7	8	...
F(x)	И	И	И	Л	И	Л	И	Л	…

Здесь М есть множество натуральных чисел.

Примером 2 – местного предиката является предикат – отношение: x ≥ y,

x = y, х делить на у и т.д. Примером 3 – местного предиката является, например, такой «z есть НОД х и у».

Если в n – местном предикате зафиксировать m переменных, то получится (n - m) – местный предикат. Например, х > y – 2 – местный предикат. Если положить х = 5, то 5 > у – одноместный предикат. Положив у = 3, получим 5 > 3 – простое высказывание или 0 – местный предикат.

Можно сказать, что алгебра высказываний есть логика 0 – местных предикатов. В этом смысле алгебра высказываний есть частный случай логики предикатов. Поэтому все положения, справедливы в алгебре высказываний, справедливы и в логике предикатов, но логика предикатов не исчерпывается ими.

Таким образом, в логике предикатов фигурируют следующие величины: нелогические величины – это переменные и постоянные предметы x, y, z, ... a, b, c, переменные и постоянные высказывания А, В, С, … И, Л, которые мы будем называть элементарными высказываниями, и наконец, элементарные предикаты F(x₁,...,x_n), f(x,y).

Элементарные высказывания и предикаты называются элементарными формулами. Из этих формул с помощью операций алгебры высказываний ~, - получаются формулы, не являющимися элементарными.

Кроме этих операций в логике предикатов можно определить и такие операции, которые нельзя ввести в алгебре высказываний. Это кванторы.

1. Квантор всеобщности – это операция, которая сопоставляет предикату P(х) высказывание х P(х) – все хМ обладают свойством P(х). Очевидно что предикат G = х P(х) имеет значение Л во всех случаях, кроме одного, когда P(х) есть тождественно истинный на М предикат. Поэтому х P(х) еще можно сформулировать так: для всех хМ P(х) – истинен. Квантор всеобщности обобщает операцию конъюнкции на бесконечное множество значений:
   

х P(х) = P(а₁) P(а₂) …

2. Квантор существования является двойственным для . Это операция, которая сопоставима предикату P(х) высказывание х P(х) – существует хМ, обладающее свойством P(х). Предикат G = х P(х) имеет значение И, когда P(х) имеет значение И хотя бы для одного хМ. Квантор существования обобщает операцию дизъюнкции:
   

х P(х) = P(а₁) P(а₂) …

Если А(х,у) – двуместный предикат, определенный на множестве М, то кванторы ,можно применять как для переменой х, так и для у.

х А(х,у); у А(х,у); х А(х,у); у А(х,у).

Переменная, к которой был применен квантор, называется связанной, а другая переменная свободной. Двуместный предикат после связывания одной из переменных квантором, становится одноместным, т.е.

F(y) = х А(х,у) есть одноместный предикат от переменной у.

Замечание!

1) Операции ~, - над одноместными предикатами соответствуют операциям над множеством. Если предикат P(х) определен на множестве М, то на множестве Можно выделить подмножество P, в каждой точке которого P(х) = И. Это подмножество называется характеристическим множеством предиката P(х).

2) Пусть P(х) и Q(х) два предиката, определенные на одном и том же множестве М, а P и Q их характеристические множества. Тогда характеристическим множеством предиката P(х)Q(х) является PQ, для предиката P(х)Q(х) – пересечение PQ, а для предиката - характеристическое множество есть .

3) Можно показать, что условие(х) [P(х) → Q(x)] эквивалентно PQ.

Действительно, пусть справедливох [P(х) → Q(x)], т.е. P(х) → Q(x) есть тождественно истинный предикат. Выберем хP, т.е. P(х) = И. Т.к. P(х) → Q(x)И, то в этом случае

Q(х) = И и хQ. Следовательно PQ.

Установим обратное. Пусть PQ. Выберем хP, т.е. P(х) = И. Т.к.PQ, то хQ и Q(х)=И. Следовательно P(х) → Q(x) = И, если хP. Если же хP, т.е. P(х) = Л, то P(х) → Q(x) = И независимо от Q(х). Следовательно, P(х) → Q(x) = И для всех х или справедливо: х [P(х) → Q(x)].

4) Показать, что условие х [P(х) ~ Q(x)] эквивалентно P = Q.


Равносильность в логике предикатов.


Если две формулы W и V, определенные на некоторой области М, принимают одинаковые значения при всех значениях входящих в них переменных предикатов, переменных высказываниях и предметных переменных из М, то они равносильны на М.

Формулы, равносильные на любых областях, называются просто равносильными и могут заменять друг друга. Все равносильности, имеющее место в алгебре высказываний переносятся и в логику предикатов. В частности, как и ранее



Кроме равносильности алгебры высказываний в логике предикатов существуют равносильности, связанные с кванторами. Это формулы Де Моргана для кванторов:



Эти формулы отражают следующее правило: знак отрицания можно вносить под знак квантора, меняя квантор на двойственный.

В алгебре высказываний было установлено, что для любой формулы существует равносильная ей формула, содержащая только V,Λ, −. В логике предикатов для каждой формулы можно найти равносильную формулу, содержащую только знаки операций V,Λ, −, причем знак − относится только к элементарным высказываниям и элементарным предикатам. Такая формула называется приведенной формой данной формулы.

Пример:




Нормальные формы в логике предикатов.

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

Теорема:

Каждая формула логики предикатов имеет нормальную формулу.

Доказательство:

Прежде чем доказывать теорему, установим 4 равносильности, которые необходимы нам в дальнейшем. В них предполагается, что формула Н не содержит свободной переменной х:



Установим первую из этих равносильностей. Остальные аналогично.



Пусть истинна для некоторой области М. Тогда на М истинно или или . В первом случае есть тождественно истинный на М предикат и т.к. не содержит х, тоже тождественно истинный на М предикат и, следовательно - истинно. Во втором случае, если истинно, то истинно и независимо от х, а значитиз М.

Пусть теперь ложно. Тогда иложны. Следовательно, существует х₀М, такой что= Л. Но тогда ложно, т.е.ложно.

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



Тогда формуле равносильна формула , которая может быть всегда приведена к нормальной форме с использованием равносильностей 1 – 2:



Таким образом, получена нормальная форма формулы . Аналогично, с помощью равносильностей 3,4 показывается, что можно построить нормальную форму и для . Наконец, если известна нормальная форма формулы , то нормальная форма имеет следующий вид:



Таким образом установлено, что любая формула логики предикатов имеет нормальную форму.

Для приведения формулы к нормальной форме нужно сделать следующие операции:

1. исключить знаки , ~, если они есть.
   
2. уменьшить область знаков отрицания.
   
3. переименовать переменные так, чтобы можно было вынести кванторы в начало формулы.
   

Пример:




Проблема разрешения в логике предикатов.


Формула называется ложной (тождественно ложной), если она имеет значение Л на любой области при любых значениях предикатов. Формула называется тождественно истинной на М, если она имеет значение И при всех значениях предикатов, определенных на М. Формула называется выполнимой, если истинна для некоторых предикатов, определенных на М.

Проблема разрешения ставится такая, как и в алгебре высказываний: указать единый способ для определения по произвольной формуле, выполнима она или нет. Если проблема разрешения в алгебре высказываний легко решается с помощью нормальных форм, то для логики предикатов показано, что эта проблема не разрешима. Однако для некоторых частных типов формул эта проблема решается, т.е. она неразрешима в общем случае, для любой формулы.