Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
В) невыполнимые формулы классической логики предикатов. .
|
|
Как известно, законами в логической теории являются формулы, истинные при любых принятых в данной теории интерпретациях нелогических символов, входящих в алфавит данной теории. В классической логике предикатов интерпретация нелогических символов осуществляется путем выбора некоторой модели < U, I>.
Определение логического закона. Формула А является законом классической логики предикатов, если и только если она принимает значение «истина» в каждой модели (и, разумеется, при любом приписывании значений предметным переменным).
Законы логики еще называют общезначимымиформулами. Общезначимость формулы A символически выражается как |=А. С учетом принятых нами обозначений ее можно выразить еще как Ž AŽ = и.
Примером общезначимой формулы может служить выражение
" х Р(х) É $х Р(х).
Обоснуем общезначимость данной формулы, используя метод рассуждения от противного. ПредположимЮ что " х Р(х) É $х Р(х) не является общезначимой формулой. А это будет означать, что существут такая модель < U, I>, в которой
Ž " х Р(х) É $х Р(х) Ž M = л.
Другими словами, исходя из семантики импликации, Ž " х Р (х) Ž M = и и Ž $х Р(х) |M = л.
Истинность " х Р(х) означает, что | Р(х) |M = и при приписывании переменной х любого индивида из U. Ложность $х Р(х) означает, что | Р(х) |M = л при приписывании переменной х любого индивида из U. Возьмем теперь произвольный элемент d из U. Согласно вышесказанному, | Р(х) |M = и при приписывании переменной х индивида d и одновременно | Р(х) |M = л при этом же приписывании. Итак, мы пришли к противоречию. Значит, формула
" х Р(х) É $х Р(х)
является общезначимой.
Определение необщезначимой формулы. Формула А не является законом логики предикатов тогда и только тогда, когда существует модель M = < U, I>, в которой формула А принимает значение «ложь».
Чтобы показать необщезначимость формулы, нужно найти модель M = < U, I>, в которой эта формула примет значение «ложь».
Возьмем для примера формулу:
$х Р(х) É " х Р(х)
и покажем ее необщезначимость. В качестве области интерпретации U возьмем множество химических элементов. Пусть интерпретационная фнкция I сопоставляет предикаторной константе Р множество металлов. Если переменной х приписать значение «Медь», то в модели < U, I> формула Р(х) будет истинной. Если же переменной х приписать значение «Кислород», то Р(х) окажется ложной формулой. Следовательно, существует приписывание значения переменной х, при котором
| Р(х) |M = и ,
и отсюда вытекает, что
| $х Р(х) |M = и.
Вместе с тем, существет и другое приписывание значения переменной х, при котором
| Р(х) |M = л ,
а это означает, что
| " х Р(х) |M = л.
Истинность $х Р(х) и ложность " х Р(х) в M = < U, I> свидетельствует о том, что формула Ž $х Р(х) É " х Р(х) |M = л.
Следовательно, данная формула необщезначима.
Определение выполнимой формулы. Формула А языка логики предикатов является выполнимой, если и только если существет модель M = < U, I>, в которой А принимает значение «истина».
Обратимся к примеру.
Мы установили, что формула $х Р(х) É " х Р(х) является необщезначимой. Теперь покажем, что она является выполнимой.
Для этого найдем модель M = < U, I>, в которойданнаяформулабудет истинной. Пусть U представляет собой множество людей, а функция І сопоставляет предикаторной константе Р пустое множество (например, множество людей, являющихся жителями Луны). Тогда | Р(х) |M = л при приписывании переменной х любого индивида из U, а отсюда следует, что | $х Р(х) |M = л. Но если антецедент нашей формулы ложный, то вся формула в данной модели мудет истинной:
| $х Р(х) É " х Р(х) |M = и.
Следовательно, она яляется выполнимой.
Определение невыполнимой формулы. Формула является невыпонимой тогда и только тогда, когда она принимает значение «ложь» в каждой модели (при любом приписывании значений предметным переменным).
Рассмотрим такую формулу:
Ø $х Р(х) & Р(а).
Воспользуемся рассуждением от противного и предположим, что данная формула является выполнимой. Тогда должна существовать модель M = < U, I>, в которой она истинна. Наша формула является конъюнкцией. А это означает, что | Ø $х Р(х) |M = и и | Р(а) |M = и, то есть оба конъюнкта должны быть истинными.
Істинність Р(а) свидетельствует о том, что І (а) Î І (Р). Истинность Ø $х Р(х) означает ложность $х Р(х). Признание последнего факта означает, что | Р(х) |M = л для любого индивида из U, выбранного в качестве значения предметной переменной x, в том числе и для индивида І (а). Но тогда нам следует признать, что І(а) Ï І(Р). Но подобное заключение противоречит принятому ранее предположению, что І(а) Î І(Р).
Итак, предположение о выполнимости формулы Ø $х Р(х) & Р(а) оказалось ошибочным. Даная формула не является выполнимой.
5. Логические отношения между формулами в S4.
К фундаментальным отношениям в классической логике предикатов относят: