Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

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




Определение 1.

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

Определение 2.

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

Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Рассмотрим основные из этих равносильностей.

Пусть А(х) и В(х) – переменные предикаты, а С – переменное высказывание (или формула, не содержащая х). Тогда имеют место равносильности:

1.

2.

3.

4.

5.

6. .

7.

8.

9.

10.

11.

12.

13.

14.

15.

Равносильность 1 означает тот простой факт, что, если не для всех х истинно А(х), то существует х, при котором будет истиной .

Равносильность 2 означает тот простой факт, что, если не существует х, при котором истинно А(х), то для всех х будет истиной .

Равносильности 3 и 4 получаются из равносильностей 1 и 2, соответственно, если от обеих их частей взять отрицания и воспользоваться законом двойного отрицания.

 

Предваренная нормальная форма (ПНФ)

Формула логики предикатов имеет нормальную форму если она содержит только операции. ()

ПНФ – это такая форма где кванторные операции отсутствуют, либо используются после всех операция. Т.е.

Теорема: все формулы логики предикатов (ЛП) м/б приведены к ПНФ

Доказательство: пусть формула имеет нормальную форму.

Если формула элементарная => она квадратов не содержит => она сама по себе является в ПНФ.

1. Пусть формула A содержит k+1 операцию и , где L(x) – cодержит к-операций изходя из условия L(x) находиться в пнф. Поскольку кванторы записаны впереди данной формулы то A находиться в пнф.

2. Пусть A=L где L находиться в ПНФ тогда с помощью равносильностей

1 и 2 отрицание можно внести под знак кванторов, тогда А будет в пнф

3. Пусть А=L1 V L2; где L1 L2 в пнф. Переименуем в L2 связанные предметные переменные так, чтобы они были различными.

Используя равносильности 7 и 1

Запишем формула А используя формулу L2 под знаки квантора:

Получается что

Далее ведем под знаки кванторов

формулу L1.

Получаем:

Т.о А находиться в ПНФ

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

Формула А называется выполняемой области М если существует значения переменных при которых А принимает истинное значение.

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

А называется ТИ в области М если принимает истинные значения для всех значений переменного (т е на все А называется общезначимой если она ТИ на всякой области.

А ТЛ в области М если она принимает логичные значения для всех переменных.

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

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

Логический квадрат

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

Высказывание и - не могут быть не для какого предиката Р(х) одновременно истинными (хотя могут быть одновременно ложными). Их называют контрарными.

Высказывание и не могут быть не для какого предиката Р(х) одновременно ложными (но могут быть одновременно истинными). Их называют субконтрарными.

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

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

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...