Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
выполнимость и общезначимость, Равносильность формул логики предикатов. Основные законы и тождества логики предикатов. Нормальные формы.
1. Выполнимость и общезначимость
Одной из основных задач логики предикатов является установление истинности или ложности конкретных формул логики предикатов. Как только определены интерпретации могут быть определены общезначимость, противоречивость, выполнимость и опровержимость. Введём необходимые определения.
Определение. Предикат Р: Mn{И;Л} называется выполнимым на множестве М, если Р(х)=и для некоторого .
Определение. Предикат Р: Mn{И;Л} называется опровержимым на множестве М, если Р(х)=л для некоторого .
Определение. Предикат Р: Mn{И;Л} называется тождественно истинным на множестве М, если Р(х)=и для всех .
Определение. Предикат Р: Mn{И;Л} называется тождественно ложным на множестве М, если Р(х)=л для всех.
Определение. Формула А выполнима в данной интерпретации, если существует такой набор значений свободных переменных x1,…,xn формулы A, для которого формула истинна в данной интерпретации.
Определение. Формула А опровержима в данной интерпретации, если существует такой набор значений свободных переменных x1,…,xn формулы A, для которого формула ложна в данной интерпретации.
Определение. Формула А истинна в данной интерпретации, если она истинна для любого набора значений свободных переменных x1,…,xn в данной интерпретации.
Определение. Формула А ложна в данной интерпретации, если она ложна для любого набора значений свободных переменных x1,…,xn в данной интерпретации.
Определение. Формула А общезначима (в логике предикатов), если она истинна в любой интерпретации.
Определение. Формула А противоречие (в логике предикатов), если она ложна в любой интерпретации.
Данная интерпретация называется моделью для данного множества формул Г, если каждая формула из Г истинна в данной интерпретации.
Всякая замкнутая формула истинна или ложна в данной интерпретации. Открытая (то есть не замкнутая) формула A(x1,…,xn) истинна в данной интерпретации тогда и только тогда, когда её замыкание x1… xn A(a1,…,an) истинно в данной интерпретации.
Из приведённых определений и определений связок непосредственно вытекают следующие утверждения:
Важные примеры общезначимых формул логики предикатов даются теоремой
Теорема 1. Формулы и , где y не входит в формулу A(x), являются общезначимыми.
Доказательство:
1) Пусть - некоторая интерпретация. Обозначим - все свободные переменные формулы , и x, - все свободные переменные формулы А(х) и .
Тогда на наборе .
Если , то -тождественно истинный, значит F1 – тавтология. (так как |А(m)|=и для любого х, но нашлось такое m0, что |А(m0)|=л).
2) Пусть - некоторая интерпретация. Обозначим - все свободные переменные формулы , и x, - все свободные переменные формулы А(х) и .
Тогда на наборе .
Рассмотрим два случая
То есть предикат - тождественно истинный. Значит F2 – тавтология. .
Обозначим для любых формул А и В.
Задача распознавания общезначимости формул, называемая проблемой разрешимости, для логики предикатов существенно сложнее, чем для формул логики высказываний. Как будет ясно из дальнейшего, в логике предикатов не существует алгоритма распознавания общезначимости формул.
2. Равносильность формул.
Определение. Две формулы F1 и F2 в алфавите называются равносильными в интерпретации , если для любого .
F1F2.
Определение. Две формулы F1 и F2 в алфавите называются конгруэнтными, когда F1 и F2 отличаются друг от друга лишь правильным (то есть без коллизий) переименованием переменных.
F1F2.
Теорема 2 (Основные равносильности логики предикатов).
.
Доказательство: Проведем для закона 1.
Пусть I произвольная интерпретация с областью D.
Если - истинна в I, то - ложна в I. Это означает, что существует такой элемент х0 в D, что А(х0)- ложна, то есть - истинна. Следовательно - истинна в I.
Если - ложна в I, то - истинна в I. Это означает, что для всех элементов из D, что А(х)- истинна, то есть - ложна для всех элементов из D. Следовательно - ложна в I.
Так как и принимают одинаковые значения в произвольной интерпретации, то по определению данные формулы равносильны.
Замечание. Квантор всеобщности и квантор существования можно распределять по конъюнкции и дизъюнкции соответственно, но нельзя распределять по дизъюнкции и конъюнкции соответственно.
≠.
≠.
В случаях подобных этим, необходимо поступать специальным образом. Так как каждая связанная переменная может рассматриваться как место для подстановки какой угодно переменной, то каждую связанную переменную х можно переименовать в переменную z, тогда
.
.
Теорема 3. Пусть . A и B - формулы алгебры высказываний, все высказывательные переменные которых, содержатся в списке . Тогда, если вместо этих переменных подставить в A и B некоторые формулы логики предикатов, то .
Пример.
Если, то
.
3. Нормальные формы формул логики предикатов.
Определение. Функция , где Q – кванторы и формула A не содержит кванторов, называется предваренной формулой.
Пример.
- предваренная.
- не является предваренной.
Определение. Формула F логики предикатов называется приведенной, если она не содержит импликаций и все знаки (отрицания) стоят перед атомарными формулами.
Пример.
- приведенная.
- не является приведенной.
Определение. Формула F логики предикатов называется нормальной, если она является предварительной и приведенной.
Лемма 1. (О чистоте переменных) Пусть А- формула и S- конечное множество переменных. Тогда может быть построена формула В со свойством чистоты переменных, конгруэнтная А. И всякая связанная переменная из В отлична от переменных из множества S.
Теорема 4. (О нормальных формах) Для любой формулы логики предикатов существует равносильная ей нормальная формула.
Доказательство: Проводится в два этапа.
Во-первых, доказывается, что для всякой формулы А существует предваренная формула В, равносильная А. По лемме 1 найдется формула С, конгруэнтная А со свойством чистоты переменных. Следовательно, АС. Затем, используя пронесение кванторов приводим С к предваренной форме. При этом мы пользуемся тем, что можно внутри С заменять эквивалентные формулы. Возможность одностороннего пронесения кванторов обеспечивается именно свойством чистоты переменных.
Во-вторых, необходимо доказать, что всякая бескванторная формула А логически эквивалентна некоторой ДНФ и КНФ.
Пример.
,
- приведенная
- нормальная.
4. Построение теории К.
Так же, как и в случае логики высказываний дальнейшим развитием логики предикатов является построение формальной аксиоматической теории K, обобщающей логику предикатов в рамках которой теоремы и только они являются общезначимыми формулами, где теоремы определяются аналогично тому, как это делалось в исчислении высказываний. Для построения исчисления предикатов необходимо, как указывалось выше задать 4 следующие составляющие модели
Исчисления, в которых кванторы могут связывать только предметные переменные, но не функторы и не предикаты, называется исчислением первого порядка. Исчисления, в которых кванторы могут связывать функторы и предикаты называются исчислениями высших порядков.
Логические аксиомы исчисления высказываний:
A1: (A(BA));
A2: ((A(BC)) ((AB) (AC)));
A3: ((BA) ((BA) B)
A1:xA(x)A(y), где A(x) не содержит переменной y
A2:A(y) xA(x), где A(x) не содержит переменной y
Собственные аксиомы не могут быть сформулированы в общем случае, так как могут различаться для различных теорий.
1) A,AB - правило Modus ponens (MP)
2) BA(x), BxA(x) – правило связывания квантором общности
3) A(x) B, xA(x) B – правило связывания квантором существования, где формула A содержит свободные вхождения переменной x, а B их не содержит
4) Правило переименования связанной переменной
Описанная формализованная модель называется прикладным исчислением предикатов.
Исчисление предикатов, которое не содержит предметных констант, функторов, предикатов и собственных аксиом, называется чистым. Практика показывает, что для формализации содержательных теорий во всех разумных случаях достаточно прикладного исчисления предикатов первого порядка.