Основные равносильности логики предикатов

Пусть А(х) и В(х) – переменные предикаты, а с – переменное высказывание.

Вопрос 3. Предваренная нормальная форма представления формул логики

предикатов

В алгебре высказываний были введены ДНФ и КНФ, которые позволяют упрощать многие доказательства в алгебре высказываний. Проблемы, возникающие в логике предикатов при оперировании с кванторами и областями действия кванторов, бывают достаточно сложными. В частности, к некоторым трудностям может привести наличие в формуле одновременно связанной и свободной одной и той же переменной. Поэтому в логике предикатов путем тождественных преобразований данную формулу так же приводят к более простому или стандартному виду – к нормальной форме.

О.3.1. Говорят, что формула логики предикатов имеет нормальную форму, если она содержит только операции конъюнкции, дизъюнкции и кванторные операции, а операция отрицания отнесена к элементарным формулам.

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

Пример 4.

Приведем к нормальной форме формулу ($х Р(х) ®"уQ(у))®R(z).

Решение

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

О.3.2. Предваренной нормальной формой (ПНФ) формулы логики предикатов называется формула вида

(К₁х₁) (К₂х₂) … (К_nх_n) R(х₁,х₂,…,х_m),

где n ≤ m; К_i – один из двух кванторов (" или $); х_i – переменные, входящие в формулу

(i = 1,2,..,n); R(х₁,х₂,…,х_m) – формула, не содержащая кванторов.

Выражение (К₁х₁) (К₂х₂) … (К_nх_n) называется префиксом данной формулы, а формула R(х₁,х₂,…,х_m) – ее матрицей.

Если все К_i равны ", то ПНФ называется "-формулой или универсальной формулой.

Если существует i (0 ≤ i ≤ n) такое, что К₁, К₂, …, К_i суть $, а К_i+1, К_i+2,…, К_n суть ", то такая ПНФ называется скулемовской нормальной формой или $"-формулой.

Альберт Торальф Скулем (1887-1963) – норвежский математик.

Т.3.2. Всякая формула логики предикатов может быть приведена к предваренной нормальной форме.

Пример 5. Привести к ПНФ формулу

Решение

Проводя равносильные преобразования, получим

Вопрос 4. Общезначимость и выполнимость формул логики предикатов

О.4.1. Формула А называется выполнимой в области М, если существуют значения переменных из области М, входящих в эту формулу, при которых формула А принимает истинные значения.

О.4.2. Формула А называется выполнимой, если существует область, на которой эта формула выполнима.

Из О.4.2. следует, что если формула выполнима, то это еще не означает, что она выполнима в любой области.

О.4.3. Формула А называется тождественно истинной (тождественно ложной) в области М, если она принимает истинные (ложные) значения при всех значениях переменных из области М, входящих в эту формулу.

О.4.4. Формула А называется общезначимой, если она тождественно истинная на всякой области.

Общезначимая формула называется логическим законом.

Из приведенных определений следует:

1. Если формула А общезначима, то она и выполнима на всякой области.

2. Если формула А тождественно истинная в области М, то она и выполнима в этой области.

3. Если формула А тождественно ложная в области М, то она и не выполнима в этой области.

4. Если формула А не выполнима, то она тождественно ложная на всякой области.

Пример 6.

Формула "х$у Р(х,у) выполнима. Она является тождественно истинной, а, следовательно, и выполнимой в области М = N₀ ´ N₀, где N₀ = {0,1,2,..}, Р(х,у) – предикат «х < у». Однако если предикат «х < у» рассматривается в конечной области М₁ = Е₁ ´ Е₁, где Е₁ = {0,1,2,…,k}, то формула "х$у Р(х,у) будет тождественно ложной (не выполнимой) в области М₁. Очевидно, что формула "х$у Р(х,у) не общезначима.

Пример 7.

Формула тождественно истинная в любой области М, следовательно, она общезначима, т.е. является законом логики (закон исключенного третьего).

Пример 8.

Формула тождественно ложная в любой области М, следовательно, она не выполнима.

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

Т.4.1. Для того чтобы формула А была общезначима, необходимо и достаточно, чтобы ее отрицание Ā было не выполнимо.

Т.4.2. Для того чтобы формула А была выполнима, необходимо и достаточно, чтобы ее отрицание Ā была не общезначимо.

Вопрос 5. Проблема разрешимости для общезначимости и выполнимости формул логики

предикатов

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

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

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

Алонзо Черч (1903 - 1995) – американский математик и логик.

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

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