Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Процедури разрешения для выражений логики предикатов.
|
|
В логике предикатов, в отличие от логики высказываний, не существует универсального способа решения проблемы разрешения для произвольных выражений этой логики. Но один из способов разрешения состоит в том, чтобы выражение логики предикатов свести к выражению логики высказываний и уже к нему применить процедуру разрешения. Подобным путем можно установить общезначимость достаточно большой группы выражений логики предикатов.
Основная идея в этом случае та же, что и при решении проблемы разрешения для формул логики высказываний. Сначала допускаем, что интересующая нас формула не является общезначимой, и осуществляем определенные действия, чтобы найти такое распределение значений (или интерпретацию), при котором исследуемая формула была бы ложной. Если обнаруживается, что подобного распределения значений (интерпретации) не существует, то формула признается общезначимой.
Например, рассмотрим формулу:
[" x (M(x) É Ø P(x)) & " x (S(x) É M(x))] É " x (S(x) É Ø P(x))
и проверим, является ли она общезначимой.
Применим закон 8, получим формулу:
[(" x M(x) É " xØ P(x)) & (" x S(x) É " x M(x))] É (" x S(x) É " x Ø P(x))
В результате консеквент нашей формулы приобрел вид импликации.
Теперь предположим, что данная формула необщезначима. Но это возможно только в том случае, если ее при некоторой интерпретации ее антецедент будет истинным, а консеквент – ложным.
Консеквентбудет ложным, когда формула " х S(x) – истинная, а формула Ø " х Р(х) - ложна. В таком случае в антецеденте эти подформулы должны принять те же значения:
[(" x M(x) É " x Ø P(x)) & (" x S(x) É " x M(x))]
¯ ¯
Л и
Поскольку антецедент должен быть истинной конъюнкцией, то оба конъюнкта должны быть истинными. Поэтому в первом конъюнкте подформула " х М(х) должна иметь значение «ложь», иначе подформула (" х М(х) É " хØ Р(х)) будет ложной, а во втором конъюнкте подформула " х М(х) должна иметь значение «истина», иначе подформула (" x S(x) É " x M(x)) – будет ложной. Ясно, что одной и той же подформуле сложной формулы нельзя одновременно приписывать оба истинностных значения. Следовательно, предположение, что исходная формула не является общезначимой, оказалось ошибочным.
Рассмотрим следующий пример:
[" x (P(x) É Ø M(x)) & $x (S(x) & M(x)] É $x (S(x) & Ø P(x)).
Воспользуемся, кроме закона 8, еще законом 5, получим формулу:
[(" x P(x) É " x Ø M(x)) & $x S(x) & $x M(x)] É ($x S(x) & $x Ø P(x)).
Попробуем найти интерпретацию, в которой антецедент формулы был бы истинным, а консеквент – ложным. Консеквент, представляющий собой конъюнкцию, будет ложным, если хотя бы один из конъюнктов будет ложным. Но невозможно, чтобы формула $х S(x) была ложной, так как в этом случае ложным будет антецедент нашей формулы. Остается предположить, что ложным будет конъюнкт $х Ø Р(х). Рассмотрим в таком случае импликацию в антецеденте формулы, в предположении, что подформула $хØ Р(х) – ложна. В соответствии с законом 12, эта подформулаэквивалентна формуле Ø " х Р(х), а тогда подформула " х Р(х) – истинна.
В таком случае подформула " х Ø М(х) тоже должна быть истинной, поскольку, по нашему предположению, импликация (" х Р(х) É " х Ø М(х)) как один из конъюнктов антецедента – истинна. Но формула " х Ø М(х) эквивалентна формуле Ø $х М(х). Так как формула $х М(x) как один из конъюнктов антецедента тоже должна быть истинной, мы получили противоречие.
Итак, не существует набора истинностных значений подформул, при котором данная импликация была бы ложной, значит, исходная формулаявляется общезначимой.
Рассмотрим еще одну формулу:
[" x (M(x) É Ø P(x)) & $x (S(x) & M(x))] É $x (S(x) & Ø P(x)).
Применим к ней законы 7 и 5:
[(" x M(x) É " x Ø P(x)) & $x S(x) & $x M(x)] É ($x S(x) & $x Ø P(x)).
Чтобы антецедент данной формулы был истинным, а консеквент – ложным, следует предположить, что обе подформулы с квантором существования в антецеденте являются истинными, а значит подформула $х S(x) истинна и в консеквенте. Следовательно, второй конъюнкт консеквента – подформула $х Ø Р(х) – должна быть ложной.
Из ложности $х Ø Р(х) вытекает ложность " х Ø Р(х). В то же время из сделанных предположений ничего не следует относительно истинностного значения подформулы " х М(х):
[(" x M(x) É " x Ø P(x)) & $x S(x) & $x M(x)]
¯ ¯ ¯ ¯
? л и и
С предположением об истинности $х М(х) совместима как истинность, так и ложность " х М(х). При истинности" х М(х) импликация в антецеденте будет ложной, а при ложности " х М(х) - она будет истинной. Следовательно, исходная формула необщезначима.
Процедуру разрешения, применявшуюся нами в отношении приведенных в качесвте примеров формул (обозначим ее буквой «А»), можно описать так:
|
|