Формулы алгебры предикатов

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

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

Понятие формулы алгебры предикатов определяется кроме этого как и формулы алгебры предикатов сигнатуры z. Число всех знаков операций, входящих в запись формулы U, именуется её рангом и обозначается . Формула именуется атомарной, она может записываться , её ранг = 0.

Формула алгебры предикатов сигнатуры s есть либо высказыванием либо некоторым предикатом на модели M. Формула алгебры предикатов есть лишь в некотором роде выстроенной последовательностью знаков. Из одной и той же формулы алгебры предикатов возможно образовать разные формулы сигнатуры z и формулы разных сигнатур, по окончании чего возможно будет сказать об истинностных значениях формулы алгебры предикатов.

Определение.Пускай U — формула алгебры предикатов и

(2)

комплект предикатных переменных, входящих в U. Сигнатуру z, и класс моделей Kz и модель M I Kz назовем допустимыми для формулы U, в случае если z содержит хотя бы один предикат арности ni для любого , т.е. существует отображение .

Такое отображение назовем сигнатурным. Формула, полученная заменой каждой предикатной переменной её образом S( ), есть формулой сигнатуры z и обозначается sU.

К примеру, для формулы алгебры предикатов

модель математики натуральных чисел N = N; E, S, P есть допустимой, поскольку возможно выстроить сигнатурное отображение множества предикатных переменных формулы в сигнатуру модели z = E(2), S(3), P(3). Вариантов для того чтобы отображения два:

1) , ;

2) , .

Обозначим через sU формулу, взятую подстановкой в формулу U предикатов сигнатурного отображения a.

Определение.Пускай для формулы алгебры предикатов U модель M есть допустимой. Тогда:

a) формула U именуется выполнимой на модели M, в случае если формула sU выполнима на модели M при некоем сигнатурном отображении S;

b) формула U именуется выполнимой, в случае если существует допустимая модель, на которой она выполнима;

c) формула U именуется невыполнимой либо фальшивой на модели M, в случае если формула sU невыполнима на модели M при любом сигнатурном отображении S;

d) формула U именуется невыполнимой, в случае если на любой допустимой модели она не выполнима;

e) формула U именуется тождественно подлинной на модели M, в случае если формула sU подлинна на модели M при любом сигнатурном отображении S;

f) формула U именуется общезначимой, если она тождественно подлинна на любой допустимой модели.

Примеры.

Формула алгебры предикатов на допустимой модели математики натуральных чисел N = семь дней; E, S, P есть фальшивой, поскольку для любых не существует такое натуральное x2, что либо .

Формула алгебры предикатов общезначима.

Главные общезначимости алгебры предикатов

1.

2.

3.

4.

5.

Докажем формулу .

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

Пускай , тогда по определению операции утверждения существования для некоего a из M. Следовательно, , где M. Воспользовавшись опять определением операции утверждения существования, возьмём, что либо , а, следовательно, подлинна и их дизъюнкция .

Пускай сейчас , тогда либо . В первом случае возьмём, что M, , во втором – M, . Но и в том и другом случае существует таковой элемент M, что , в первом случае , во втором – . А это указывает, что .

На множестве формул алгебры предикатов возможно ввести отношение эквиваленции.

Определение.Формула алгебры предикатов U именуется эквивалентной формуле V (обозначается UºV), в случае если их эквиваленция общезначима.

Множество формул алгебры предикатов возможно разбить на классы эквивалентности, включив в один класс эквивалентные между собой формулы. Каждой формуле U соответствует класс эквивалентности, что обозначается [U].

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

Теорема 3.1. Любой класс эквивалентности [U] возможно представлен приведенной формулой, т.е. для любой формулы U существует эквивалентная ей приведенная формула V.

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

Определение.Предваренной обычной формой (ПНФ) формулы алгебры предикатов именуется формула, имеющая вид

,

где – кое-какие кванторы, а U – бескванторная приведенная формула. Выражение именуется префиксом, а U – матрицей обычной формы.

Будем говорить, что бескванторная формула U находится в ДНФ (КНФ), в случае если U получается из формулы алгебры высказываний, находящейся в ДНФ (КНФ), подстановкой вместо пропозициональных переменных некоторых атомарных формул.

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

Выстроим ПН-форму для формулы

.

Преобразуем формулу к приведенному виду

º

º º

º .

Так как для квантора и операции U нет соответствующей эквивалентности, то переименуем связанную переменную y второго операнда дизъюнкции и вынесем кванторы по переменным, от которых не зависит второй операнд вперёд

º

º º

º .

В первом операнде конъюнкции последней формулы переменные x и y – связанные, а z – свободная, а во втором – напротив. Переобозначив опять связанные переменные, возьмём

º

º º

º .

Полученная предваренная обычная форма есть предклазуальной.

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

1) ? ;

2) ? .

Возможность удаления кванторов всеобщности следует из определения операции, поскольку для произвольного x.

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

Так клазуальная обычная форма для формулы прошлого примера имеет форму

.

Лекция 13: Логика предикатов


Также читать:

Понравилась статья? Поделиться с друзьями: