Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
84
Курс лекций по математической логине
ГЛАВА III
ЛОГИКА ПРЕДИКАТОВ
§ 1. Понятие предиката
В алгебре логики высказывания рассматриваются как нераздельные целые и только с точки зрения их истинности или ложности. Ни структура высказываний, ни, тем более, их содержание не затрагиваются. В то же время и в науке, и в практике используются заключения, существенным образом зависящие как от структуры, так и от содержания используемых в них высказываний^/
Например, в рассуждении «Всякий ромб—^параллелограмм; АВСП - ромб; следовательно, АВСО - параллелограмм» посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учета их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.
В связи с этим возникает необходимость в расширении логики высказываний, в построении такой логической системы, средствами которой можно было бы исследовать и структуру тех высказываний, которые в рамках логики высказываний рассматриваются как элементарные.
Такой логической системой является логика предикатов, содержащая всю логику высказываний в качестве своей части.
' Логика предикатов, как и традиционная формальная логика, расчленяет элементарное высказывание на субъект (буквально - подлежащее, хотя оно и может играть роль дополнения) и предикат (буквально - сказуемое, хотя оно может играть и роль определения).
Субъект — это то, о чем что-то утверждается в высказывании; предикат — это то, что утверждается о субъекте.
Например, в высказывании «7 — простое число», «7» — субъект, «простое число» — предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом».
Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывателъную форму «х - простое число». При одних значениях х (например, х = 13, х = 17) эта форма дает истинные высказывания, а при других значениях х (например, х = 10, х = 18 ) эта форма дает ложные высказывания.
Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множестве М, и принимающую значения из множества {1.0}.
Здесь предикат становится функцией субъекта и выражает свойство субъекта.
Определение. Одноместным предикатом р(х) называется произвольная функция переменного х, определенная на множестве М и принимающая значения из
множества {1,0}.
Множество М, на котором определен предикат р(х) , называется областью определения предиката.
Множество всех элементов х е М , при которых предикат принимает значение «истина», называется множеством
истинности предиката р(х) , то есть множество истинности предиката р(х) - это множество 1р = {*: х е М, р(дс) = 1}. Так, предикат р(х) - «л: - простое число» определен на множестве N. а множество 1р для него есть множество всех простых чисел. Предикат ф(#) - « зш х = 0 » определен на множестве К, а его множество истинности /ф = \Ня, Н е2|. Предикат р(х) - «Диагонали параллелограмма х перпендикулярны» определен на множестве всех параллелограммов, а его множеством истинности является множество всех ромбов.
ЛОГИКА ПРЕДИКАТОВ
85
Курс лекций по математической логике
Приведенные примеры одноместных предикатов выражают свойства предметов.
Определение. Предикат р(х) , определенный на множестве М, называется тождественно истинным (тождественно ложным), если 1р = М \1р = 0) „
Естественным обобщением понятия одноместного предиката является понятие многоместного предиката, с помощью которого выражаются отношения между предметами.
Примером бинарного отношения (отношения между двумя предметами) является отношение «меньше». Пусть это отношение введено на множестве 2 целых чисел. Оно может быть охарактеризовано высказывательной формой «лг<#» , где х,уе2, то есть является функцией двух переменных р(х, у), определенной на множестве 2 х 2 с множеством значений |1»0} •
Определение. Двухместным предикатом Р(х,у) называется функция двух переменных х та у, определенная
на множестве М = М1 х М2 и принимающая значения
из множества {1,0}.
В числе примеров двухместных предикатов можно назвать предикаты: ()(х, у} — « х = у » предикат равенства, определенный на множестве К = К х К ; Р(х,у) - *х//у*
прямая х параллельна прямой у, определенный на множестве прямых, лежащих на данной плоскости.
Аналогично определяется п-местный предикат.
§ 2. Логические операции над предикатами
Предикаты, так же, как высказывания, принимают два значения а и л (1, 0), поэтому к ним применимы все операции логики высказываний.
Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов.
Пусть на некотором множестве М определены два
предиката р(х) и ^(*)•
Определение 1. Конъюнкцией двух предикатов р(зг)
и Я(х) называется новый предикат р(ж)& ф(*) , который принимает значение «истина» при тех и только тех значениях х е М , при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях.
Очевидно, что областью истинности предиката
является общая часть областей истинности предикатов р(*) и ф(я) , то есть пересечение IрГ\I^ . Так, например, для предикатов р(х)'- «* ~ четное
число» и 9(ж): «х кратно 3» конъюнкцией Р(#)&(2(лг)
является предикат «.г — четное число и х кратно 3», то есть предикат «х делится на 6».
Определение 2. Дизъюнкцией двух предикатов р(х}
и ^(я:) называется новый предикат р(х] v 0(х) , который
принимает значение «ложь» при тех и только тех значениях х еМ, при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях.
Ясно, что областью истинности предиката р(х) v Ф(х) является объединение областей истинности предикатов р(зс) и ^(x) , то есть объединение 1р У /д .
Определение 3. Отрицанием предиката ^Р(*) назы-
вается новый предикат р(х) , который принимает значение «истина» при всех значениях х еМ, при которых предикат р(лг) принимает значение «ложь», и принимает значение «ложь» при тех значениях х е М , при которых предикат р(х) принимает значение «истина».
Из этого определения следует, что 1р = М \ 1р ~ С1Р .
ЛОГИКА ПРЕДИКАТОВ
87
88
Курс лекций по математической логике
Определение 4. Импликацией предикатов р(х) и
ф(#) называется новый предикат Р(х) -> Я(х\, который является ложным при тех и только тех значениях х с М , при которых одновременно р(#) принимает значение
«истина», а ^(x) ~ значение «ложь» и принимает значение «истина» во всех остальных случаях.
Так как при каждом фиксированном х е М спра
ведлива равносильность р(х) -» ^(*) = р(х) v ®(х)» то
1р^ = 1р У I^ - С1р У I^. ^"
§ 3. Кванторные операции
Пусть имеется предикат р(ж) , определенный на множестве М. Если а — некоторый элемент из множества М, то подстановка его вместо х в предикат Р(х) превращает
этот предикат в высказывание р(о). Такое высказывание называется единичным. Наряду с образованием из предикатов единичных высказываний в логике предикатов рассматривается еще две операции, которые превращают одноместный предикат в высказывание.
1. Квантор всеобщности. Пусть р(х) - предикат, определенный на множестве М. Под выражением V* р(я)
понимают высказывание, истинное, когда р(я) истинно
для каждого элемента х из множества М и ложное в противном случае. Это высказывание уже не зависит от ж. Соответствующее ему словесное выражение будет «Для
всякого х р(х\ истинно». Символ V называют квантором всеобщности.
Переменную х в предикате р(х) называют свободной (ей можно придавать различные значения из М), в высказывании V* р(х) переменную ж называют связанной, квантором V.
2. Квантор существования. Пусть р(х) - предикат,
определенный на множестве М. Под выражением Эх Р(х) понимают высказывание, которое является истинным, если существует элемент х е М, для которого Р(х) истинно, и ложным в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение будет:
«Существует х, при котором Р(дс) истинно». Символ 3 называют квантором существования. В высказывании Зх р(лг) переменная х связана квантором 3.
Приведем пример употребления кванторов. Пусть ни
множестве N натуральных чисел задан предикат р(*): «Число х кратно 5». Используя кванторы, из данного предиката можно получить высказывания: Ух е N Р(х) —
«Все натуральные числа кратны 5»; Эх еN р(х) - «Существует натуральное число, кратное 5». Очевидно, первое из этих высказываний ложно, а второе истинно.
Ясно, что высказывание V* р(лг) истинно только в том единственном случае, когда р(#) ~ тождественно истинный предикат, а высказывание Вх р(лг) ложно только в том единственном случае, когда р(х) ~ тождественно ложный предикат:
Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве М задан двухместный предикат р(х,у). Применение квантор-
ной операции к предикату Р[х,у) по переменной х ставит в соответствие двухместному предикату р(х,у) одноместный предикат Ух Р\х,у) (или одноместный предикат Эх р(х,у)\, зависящий от переменной у и не зависящий от переменной х. К ним можно применить кван-торные операции по переменной у, которые приведут уже к высказываниям следующих видов:
ЛОГИКА ПРЕДИКАТОВ
89
Курс лекций по математической логике
(х,у), ЗуЗхР(х,у). Например, рассмотрим предикат р(х,у): «х':у», определенный на множестве N. Применение кванторных операций к предикату Р(х,у) приводит к восьми возможным высказываниям:
Легко видеть, что высказывания 1, 5 и 8 ложны, а высказывания 2, 3, 4, 6 и 7 истинны.
Из рассмотренных примеров видно, что в общем случае изменение порядка следования кванторов изменяет смысл высказывания, а значит, и его логическое значение (например, высказывания 3 и 8).
Рассмотрим предикат р(х) , определенный на множестве М = (а1,а2,..-,ал} , содержащем конечное число элементов. Если предикат Р\х) является тождественно
истинным, то истинными будут высказывания
р(оз) , ..., Р(ап). При этом истинными будут высказыва-
ние УхР(х) и конъюнкция Р(а1]&.Р(а2)&...&Р(ап).
Если же хотя бы для одного элемента аА 6 М Р(ал) окажется ложным, то ложными будут высказывание УхР(лг) и конъюнкция Р(а1)&Р^а2)&...&Р(ап). Следовательно, справедлива равносильность
ЧхР(Х) = Р(и1)&Р(а2)&...&Р(ап).
Нетрудно показать, что справедлива и равносильность
Зх Р(х) = Р(а1) v Р(а2)ч...чр(ап}.
Отсюда видно, что кванторные операции можно рассматривать как обобщение операций конъюнкции и дизъюнкции на случай бесконечных областей.
§ 4. Понятие формулы логики предикатов
В логике предикатов будем пользоваться следующей символикой:
3. Р(-), ^"('} ~~ одноместные предикатные перемен
ные; (?(•,•,...,•), Л(•,-,...,•) - и-местные предикатные
переменные.
'*(')» 9 ('»•»•••>•) ~ символы постоянных предикатов.
6. Вспомогательные символы: скобки, запятые.
Определение формулы логики предикатов.
ЛОГИКА ПРЕДИКАТОВ
91
_ Курс лекций по математической лоаиме
Такая формула называется элементарной, в ней предметные переменные являются свободными, не связанными кванторами.
формуле А не меняется.
5. Если А(х) - формула, в которую предметная пере
менная х входит свободно, то слова ЧхА(х} и ЭхА(ж) яв
ляются формулами, причем предметная переменная
входит в них связанно.
6. Всякое слово, отличное от тех, которые названы
формулами в пунктах 1-5, не является формулой.
Например, если р(х) и (}(х,у) - одноместный и двухместный предикаты, а д, г - переменные высказывания, то
формулами будут слова: д, р(х], Р(*)&Ф(*°,{П, УхР(х\ ->•
^ / \ / '
->• Эx^(x, у), Ю(х, у) v д\ -+ г .
Не является формулой слово: Ух()(х, у) -» р(х} . Здесь нарушено условие п.З, так как в формулу Ух()(х,у} переменная х входит связано, а в формулу р(х] переменная х входит свободно.^--"'
Из определения формулы 'логики предикатов ясно, что всякая формула алгебры высказываний является формулой логики предикатов.
* § 5. Значение формулы логики предикатов
О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество М, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики предикатов зависит от значений трех видов переменных: 1) значений входящих в формулу переменных высказываний, 2) значений свободных предметных переменных из множества М, 3) значений предикатных переменных.
При конкретных значениях каждого из трех видов переменных формула логики предикатов становится высказыванием, имеющим истинное или ложное значение.
В качестве примера рассмотрим формулу
(1)
в которой двухместный предикат Р\х,у) определен на множестве М х М , где М = {0,1,2,...,га,...} .
В формулу (1) входит переменный предикат Р(х,у),
предметные переменные х, у, г, две из которых у и г -связанные кванторами, а х — свободная.
Возьмем за конкретное значение предиката р(х, у) фиксированный предикат Р°(х,у}: «х<у», а свободной переменной х придадим значение х° - 5 е М . Тогда при значениях у, меньших х° = 5 предикат Р0(*0>у) принимает значение ложь, а импликация р(х, у) -> р(у, г) при всех г е М принимают значение истина, то есть
высказывание Зу Уг1р°(х,у)-+ Рй(у,г)\ имеет значение «истина».