Равносильные формулы логики предикатов.
⇐ ПредыдущаяСтр 2 из 2 Определение 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 Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|