Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
А) выражение, содержащееся в квадратных скобках, при каждом наборе значений свободных предметных переменных превращается в истинное высказывание для любых предикатных констант;
|
|
б) при связывании свободных предметных переменных квантором " х также получают истинное высказывание.
Следовательно, каждая тавтология логики высказываний может быть превращена в общезначимую формулу логики предикатов. И если свести формулу логики предикатов к формуле логики высказываний, то тем самым можно облегчить решение проблемы разрешения для логики предикатов.
Но не всякой общезначимой формуле логики предикатов можно сопоставить тавтологию логики высказываний, иначе логика предикатов оказалась бы разрешимой. Более того, не существует взаимнооднозначного соответствия между выполнимыми формулами логики высказываний и предикатов. В частности, в результате подстановки из выполнимой формулы логики высказываний можно получить формулу-противоречие логики предикатов.
Например, возьмем формулу логики высказываний:
p & q.
Подставим вместо р формулу $х (Р(х) & Ø Р(х)), а вместо q - " x Q(x). В результате получим противоречие:
$х (Р(х) & Ø Р(х)) & " х Q(x).
То, что данная формула будет ложной при любом значении предметных переменных и для любого предиката, обусловлено формулой, подставляемой на место р.
Но та же самая подстановка в закон логики высказываний снова приводит нас к закону.
Если в формулу р Ú Ø р вместо р подставить формулу
$х (Р(х) & Ø Р(х)),
то получим тавтологию:
$х (Р(х) & Ø Р(х)) Ú Ø $х (Р(х) & Ø (х)).
Общезначимость данной формулы обусловливается общезначимостью формулы Ø $х (Р(х) & Ø Р(х)).
Что же касается такой характеристики формул, как «невыполнимость», то каждая невыполнимая формула логики высказываний остается невыполнимой и при трансфор- мации ее в результате подстановок и использования кванторов в формулу логики предикатов. Но невыполнимая формула является противоречием. Это обстоятельство позволяет (как и в случае с тавтологиями) осуществлять разрешение таких формул средствами логики высказываний.
Однако в логике предикатов существует и группа специфических законов, не сводимых к законам логики высказываний. К их рассмотрению мы сейчас и перейдем.
1. Закон устранения квантора общности:
" х Р(х) É Р(t).
где P(t) - результат замены всех свободных вхождений переменной х на замкнутый терм t.
Данный закон утверждает, что если каждый индивид из области значений переменной х обладает свойством Р, то и конкретно выбранный индивид t обладает данным свойством.
2. Закон введения квантора существования:
Р(t) É $x P(x).
Данным законом фиксируется тот факт, что если некоторый конкретный индивид t из предметной областиобладает свойством Р, то существует по крайней мере один индивид из предметной области в качестве значения переменной x, обладающий данным свойством.
3. Закон подчинения:
" х Р(х) É $х Р(х).
Его можно получить, используя оба приведенных закона в качестве посылок и свойство транзитивности импликации:
" х Р(х) É Р(t)
P(t) É $x P(x)
" x P(x) É $x P(x)
4. Закон введения квантора общности для конъюнкции:
" х [(P(x) & Q(x)] º [" x P(x) & " x Q(x)].
Согласно этому закону, каждый индивид из области значений переменной x обладает свойствами Р и Q тогда и только тогда, когда каждый индивид обладает свойством Р и каждый индивид обладает свойством Q.
Например, каждый квадрат имеет равные стороны и равные углы тогда и только тогда, когда каждый квадрат имеет равные стороны и каждый кадрат имеет равные углы.
5. Закон пронесения квантора существования через конъюнкцию:
$х [P(x) & Q(x)] É [$x P(x) & $x Q(x)].
Если существуют объекты, обладающие свойствами Р и Q, то существуют объекты, которые обладают свойством Р, и объекты, которые обладают свойством Q.
Например, если существуют учебники по физике, то существуют учебники и книги по физике.
Очевидно, что в законе (4) главным знаком является знак эквивалентности (º), а это означает, что левую и правую сторону эевивалентности можно менять местами. В законе (5) главным знаком является знак материальной импликации (É), следовательно, правую и левую части данного закона нельзя поменять местами – иначе получим необщезначимое высказывание. Например, существуют художественные книги и словари. Однако не существует ни одной книги, которая одновременно была бы художественной и словарем.
6. Закон вынесения квантора общности для дизъюнкции:
[" x P(x) Ú " x Q(x)] É " x [P(x) Ú Q(x)].
Если все индивиды обладают свойством Р, либо все индивиды обладают свойством Q, то все индивиды обладают свойством Р либо свойством Q.
Данный закон, как и закон (5), необратим, то есть перестановка местами членов импликации приведет к необщезначимой формуле
Например, верно, что каждый депутат является либо сторонником, либо противником реформ, но неверно ни то, что каждый депутат является сторонником реформ, ни то, что каждый депутат является противником реформ.
7. Закон пронесения квантора существования через дизъюнкцию:
$х [P(x) Ú Q(x)] º [$x P(x) Ú $x Q(x)]
Из данного закона вытекает, что индивиды со свойством Р или Q существуют тогда и только тогда, когда существуют индивиды сосвойством Р либо индивиды со свойством Q. Поскольку дизъюнкция истинна, когда истинный один их дизъюнктов, то для истинности формулы $х [Р(х) Ú Q(х)] не имеет значения, будет истинным $х Р(х), или $х Q(x), либо оба члена дизъюнкции..
8.Закон пронесения квантора общности через импликацию:
" х [Р(х) É Q(x)] É [" x P(x) É " x Q(x)].
Конкретизировать данное высказывание можно так: «Если для каждого студента истинно, что если он успешно сдаст сессию, то получит стипендию, то истинно, что если каждый студент успешно сдаст сессию, то каждый студент получит стипендию».
В законах 1-8 использовались только одноместные предикаторы. Но, по аналогии с ранее полученными с помощью подстановки законами логики одноместных предикатов из законов логики высказываний, можно получить законы многоместной логики предикатов.
Для этого необходимо вместо одноместных предикатов подставить многоместные и ввести такое количество кванторов, которое потребуется, чтобы связать все предметные переменные формулы.
Например, из 8- гозакона можно получить закон 8¢:
8¢." х " у [K(x, y) É S(x, y)] É [" x " y K(x, y) É " x " y S(x, y)].
Законы перестановки кванторов:
9. " x " y R(x, y) º " y " x R(x, y)
10. $x $y R(x, y) º $y $x R(x, y)
11. $x " y R(x, y) É " y $x R(x, y)
Законы отрицания кванторов:
13. Ø [ Р(х) º $х Ø Р(х)
14. Ø $ Р(х) º " х Ø Р(х)
Законы взаимовыражаемости канторов:
15. " х Р(х) º Ø $х Ø Р(х)
16. $х Р(х) º Ø " х Ø Р(х)
Перечисленные законы используются для построения доказательств в логике предикатов, а также в процедцрах разрешения для выражений логики предикатов.
Одна из процедур разрешения рассматривалась выше. Она сводилась к применению метода аналитических таблиц. Остановимся теперь на других процедурах.
|
|