Раздел 3. Логика предикатов
3.1. Недостаточность логики высказываний. Понятие предиката.

В алгебре логики высказывания рассматриваются как нераздельные целые и только с точки зрения их истинности или ложности.

Ни структура высказываний, ни, тем более, их содержание не затрагиваются. В то же время и в науке, и в практике используются заключения, существенным образом зависящие как от структуры, так и от содержания используемых в них высказываний.
Например, в рассуждении «Всякий ромб — параллелограмм; АВСБ — ромб; следовательно, АВСБ — параллелограмм » посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учета их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.
В связи с этим возникает необходимость в расширении логики высказываний, в построении такой логической системы, средствами которой можно было бы исследовать структуру тех высказываний, которые в рамках логики высказываний рассматриваются как элементарные.
Такой логической системой является логика предикатов, содержащая всю логику высказываний в качестве своей части.
Логика предикатов, как и традиционная формальная логика, расчленяет элементарное высказывание на субъект (буквально — подлежащее, хотя оно может играть и роль дополнения) и предикат (буквально — сказуемое, хотя оно может играть и роль определения).
Субъект — это то, о чем что-то утверждается в высказывании;
предикат — это то, что утверждается о субъекте.
Например, в высказывании «7 — простое число», «7» — субъект, «простое число» -предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом».
Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х — простое число». При одних значения х (например, х=1 3, х=1 7) эта форма дает истинные высказывания, а при других значениях х (например, х=10, х=18) эта форма дает ложные высказывания.
Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множестве К, и принимающую значения из множества {1;0}. Здесь предикат становится функцией субъекта и выражает свойство субъекта.
Дадим несколько определений, относящихся к предикатам.
Определение: Одноместным предикатом Р(х) называется произвольная функция переменного х, определенная на множестве М и принимающая значение из множества {1; 0}.
Множество М, на котором определен предикат Р(х), называется областью определения предиката Р(х).
Множество всех элементов х е М , при которых предикат принимает значения «истина» (1), называется множеством (областью) истинности предиката Р(х), т.е. множество истинности предиката Р(х)- это множествоI ={х : хе М,Р(х) = 1}, или иначе: М[р] или так:

М[Р(х)] Так, например, предикат Р(х) — «х — простое число» определен на множестве К, а
х
множество истинности 1Р для него есть множество всех простых чисел.
Предикат 0(х) — «8тх=0» определен на множестве Я, а его множеством истинности является 1д = {кп, к е 2}
Предикат Б(х) — «диагонали параллелограмма х взаимно перпендикулярны» определен на множестве всех параллелограммов, а его множеством истинности является множество всех ромбов.
Из приведенных примеров видим, что одноместные предикаты выражают свойства предметов (субъектов).
Определение: Предикат Р(х), определенный на множестве М, называется тождественно истинным, если его множество истинности совпадает с областью определения, т. е. 1Р=М.
Определение: Предикат Р(х), определенный на множестве М, называется тождественно ложным^ если его множество истинности является пустым множеством, т. е. 1р=0.
Естественным обобщением понятия одноместного предиката является понятие многоместного предиката, с помощью которого выражаются отношения между предметами.
Примером бинарного отношения, т. е. отношения между двумя предметами, является отношение «меньше «. Пусть это отношение введено на множестве Ъ целых чисел. Оно может быть охарактеризовано высказывательной формой «х<у», где х, у е 2, то-есть является функцией двух переменных Р(х,у), определенной на множестве упорядоченных пар целых чисел ЪхЪ=Ъ с множеством значений {1 ;0}.
Определение: Двухместным предикатом Р(х,у) называется функция двух переменных х и у, определенная на множестве М=М1хМ 2 и принимающая значения из множества {1 ;0}.
В числе примеров двухместных предикатов можно назвать такие предикаты: 0^(х, у) -«х=у» — предикат равенства, определенный на множестве ЯхЯ=Я ; Б(х,у) — «х параллелен у»,
«прямая х параллельна прямой у», определенный на множестве прямых, лежащих на данной плоскости.
Совершенно аналогично вводится понятие трехместного предиката. Приведем пример трехместного предиката (функции трех переменных): 8(х,у,2) — «х+у=2». Подстановка в него х=3 превращает его в двухместный предикат: 8(у,2) — «3+у=2», а подстановка х=3, 2=2 — в одноместный предикат 8(у) — «3+у=2».Подстановка же 8(2,3,5) превращает его в истинное высказывание, а 8(1,7,4)- в ложное.
Аналогично определяется и п-местный предикат (функция п переменных). Пример п-местного предиката:
Я(хь Х2,…,хп): аіхі+…+апХп=0, который, как видим, представляет собой алгебраическое уравнение с п неизвестными.
При п=0 будем иметь нульместный предикат — это логическая (пропозициональная) переменная, принимающая значения из множества {1;0}.

3.2. Логические операции над предикатами.

Предикаты так же, как высказывания, могут принимать два значения: «истина» (1 ) и «ложь» (0), поэтому к ним применимы все операции логики высказываний, в результате чего из элементарных предикатов формируются сложные предикаты (как и в логике высказываний, где из элементарных высказываний формировались сложные, составные). Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов. Эти операции в логике предикатов сохраняют тот же смысл, который был им присвоен в логике высказываний.
Пусть на некотором множестве М определены два предиката Р(х) и О(х). Определение: Конъюнкцией двух предикатов Р(х) и О(х) называется новый
(сложный) предикат Р(х) А ^(х), который принимает значение «истина» при тех и только тех
значениях х є м, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях.
Очевидно, что областью истинности предиката Р(х) А ^(х) является общая часть
области истинности предикатов Р(х) и О(х), т.е. пересечение ^ р П ^в.
Так, например, для предикатов Р(х): «х — четное число» и О(х): «х кратно 3»
конъюнкцией Р(х) А б(х) является предикат «х — четное число и х кратно трем», т.е. предикат «х делится на 6».
Определение: Дизъюнкцией двух предикатов Р(х) и О(х) называется новый предикат р(х) у (2Іх), который принимает значение «ложь» при тех и только тех значениях х є м , при
которых каждый из предикатов принимает значение «ложь», и принимает значение «истина» во всех остальных случаях.
Ясно, что областью истинности предиката Р(х) у ^(х) является объединение области
истинности предикатов Р(х) и <3(х), т.е. ^ р и ^в.
Р( X)
Определение: Отрицанием предиката Р(х) называется новый предикат
илиР(х), который принимает значение «истина» при всех значениях х е М, при которых предикат Р(х) принимает значение «ложь», и принимает значение «ложь» при тех значениях
хе М , при которых предикат Р(х) принимает значение «истина».
I- = I Р( х)
Очевидно, что р р , т.е. множество истинности предиката ^ ‘ является
дополнением к множеству ГР.
Определение: Импликацией предикатов Р(х) и Q(x) называется новый предикат
р(х) -— —(х) , который является ложным при тех и только тех значениях х е М , при которых одновременно Р(х) принимает значение «истина», а Q(x) — значение «ложь», и принимает значение «истина» во всех остальных случаях.
Поскольку при каждом фиксированном хе М справедлива равносильность
Р(х) — б(х) I8Р(х) V 0(х), то 1Р= 1р и 1в.
Определение: Эквиваленцией предикатов Р(х) и Q(x) называется новый предикат
р(х) —(х) , который обращается в «истину» при всех тех и только тех х е М , при которых Р(х) и Q(x) обращаются оба в истинные или оба в ложные высказывания.

Для его множества истинности имеем: р —

3.3. Кванторные операции.

Рассмотрим операции, преобразующие предикаты в высказывания.
Пусть имеется предикат Р(х) определенный на множестве М. Если «а» — некоторый элемент из множества М, то подстановка его вместо х в предикат Р(х) превращает этот предикат в высказывание Р(а). Такое высказывание называют единичным. Например, г(х): «х -четное число» — предикат, а г (6)- истинное высказывание, г (3) — ложное высказывание.
хі, і=1, п
Это же относится и к п- местным предикатам: если вместо всех предметных
переменных х1, 1= ‘ подставить их значения, то получим высказывание.
Наряду с образованием из предикатов высказываний в результате таких подстановок в логике предикатов рассматриваются еще две операции, которые превращают одноместный предикат в высказывание. Эти операции называются операциями квантификации (или просто квантификацией, или связыванием кванторами, или навешиванием кванторов). При этом рассматриваются, соответственно, два типа так называемых кванторов.
1.1. Квантор всеобщности.
Пусть Р(х) — предикат, определенный на множестве М. Под выражением /хР(х) понимают высказывание, истинное, когда Р(х) истинно для каждого элемента х из множества М, и ложное в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение звучит так: «Для всякого х Р(х) истинно «.
Символ ^ называют квантором всеобщности (общности). Переменную х в предикате Р(х) называют свободной (ей можно придавать различные значения из М), в высказывании же
Ухр(х) х называют связанной квантором всеобщности.
1.2. Квантор существования.
Пусть Р(х) -предикат определенный на множестве М. Под выражением 3хР(х) понимают высказывание, которое является истинным, если существует элемент х є М, для которого Р(х) истинно, и ложным — в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение звучит так: «Существует х, при котором Р(х) истинно.» Символ 3 называют квантором существования^ В высказывании 3хР(х) переменная х связана этим квантором (на нее навешен квантор).
Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве М задан двухместный предикат Р(х,у). Применение кванторной операции к предикату Р(х,у) по переменной х ставит в соответствие двухместному предикату Р(х,у) одноместный предикат //хР(х,у) (или одноместный предикат 3хР(х,у)), зависящий от переменной у и не зависящий от переменной х. К ним можно применить кванторные операции по переменной у, которые приведут уже к высказываниям следующих видов: //у//хР( х, у), 3у//хР( х, у), //у3хР( х, у), 3у3хР( х, у).
Рассмотрим предикат Р(х) определенный на множестве М={аь…,ап}, содержащем конечное число элементов. Если предикат Р(х) является тождественно — истинным, то истинными будут высказывания Р(а1),Р(а2),^,Р(ап). При этом истинными будут высказывания //хР(х) и конъюнкция Р(а1) л Р(а2) л… л Р(ап) .
Если же хотя бы для одного элемента ак є М Р(ак)окажется ложным, то ложными будут
п
высказывание //хР(х) и конъюнкция л Р(аі). Следовательно, справедлива равносильность /хР(х) = Р(а1) л Р(а2) л … л Р(ап) = Л Р(аг) .
і =1
1.3. Численные кванторы.
В математике часто встречаются выражения вида «по меньшей мере п» («хотя бы п»), «не более чем п», «п и только п» («ровно п»), где п — натуральное число.
Эти выражения, называемые численными кванторами, имеют чисто логический смысл; они могут быть заменены равнозначными выражениями, не содержащими числительных и состоящими только из логических терминов и знака = или ~, означающего тождество (совпадение) объектов.
Пусть п=1 . Предложение «По меньшей мере один объект обладает свойством Р» имеет тот же смысл, что и предложение «Существует объект, обладающий свойством Р», т.е. Зх( Р( х)).(*)
Предложение «не более чем один объект обладает свойством Р» равнозначно предложению «Если есть объекты, обладающие свойством Р, то они совпадают», т.е. УхУу(Р(х) А Р(у) = х = у). (**) Предложение «один и только один объект обладает свойством Р» равнозначно конъюнкции вышеуказанных предложений (*) и (**).
1.4. Отрицание предложений с кванторами.
Известно, что часто для отрицания некоторого предложения достаточно предпослать сказуемому этого предложения отрицательную частицу «не». Например, отрицанием предложения «Река х впадает в Черное море.» является предложение » Река х не впадает в Черное море «. Годится ли этот прием для построения отрицаний предложений с кванторами? Рассмотрим пример.
Предложения «Все птицы летают » и «Все птицы не летают » не являются отрицаниями друг друга, т. к. они оба ложны. Предложения » Некоторые птицы летают » и » Некоторые птицы не летают » не являются отрицанием друг друга, т. к. они оба истинны. Таким образом , предложения , полученные добавлением частицы «не» к сказуемому предложений «Все х суть Р» и «Некоторые х суть Р» не являются отрицаниями этих предложений. Универсальным способом построения отрицания данного предложения является добавление
словосочетания «неверно, что» в начале предложения. Таким образом, отрицанием
предложения «Все птицы летают» является предложение «Неверно, что все птицы летают»; но это предложение имеет тот же смысл, что и предложение «Некоторые птицы не летают». Отрицанием предложения «Некоторые птицы летают» является предложение «Неверно, что некоторые птицы летают», которое имеет тот же смысл, что и предложение «Все птицы не летают».
Условимся отрицание предложения Ух(Р(х)) записывать как Ух(Р(х)), а отрицание предложения Эх(Р(х)) — как Зх(Р(х)). Очевидно, что предложение Ух(Р(х)) имеет тот же смысл, а следовательно, то же значение истинности, что и предложение Эх(Р(х)), а
предложение Зх(Р(х))- тот же смысл, что Ух(Р(х)). Иначе говоря, Ух(Р(х)) равносильно

Зх(Р(х)) ; Зх(Р(х)) равносильно Ух(Р(х)).
Кванторы общности и существования называют двойственными относительно друг друга. Выясним теперь, как строить отрицание предложения, начинающегося с нескольких кванторов, например, такого: УхЗуУг(Р( х, у, г)).
Последовательно применяя сформулированное выше правило, получим: УхЗуУг(Р(х,у,г))равносильно Зх(ЗуУг(Р(х,у,г)), что равносильно ЗхУу(Уг(Р(х,у,г))), что
равносильно ЗхУуЗг(Р(х, у, г)) .

3.4. Понятие формулы логики предикатов.

В логике предикатов будем пользоваться следующей символикой :
1. Символы р, г, переменные высказывания, принимающие два значения: 1-истина , 0 — ложь.
2. Предметные переменные — х, у, ъ, … , которые пробегают значения из некоторого множества М;
0 0 0 ч
х , у , ъ — предметные константы, т. е. значения предметных переменных.
3. Р(-), СО), Б(-), … — одноместные предикатные переменные^ СХу,. ,•), …,■) — п — местные предикатные переменные. Р°(0, С°(у, . ,•) — символы постоянных предикатов.
4. Символы логических операций: Л,У, ,-.
5. Символы кванторных операций: Ух, Зх.
6. Вспомогательные символы: скобки, запятые.

Определение формулы логики предикатов:
1. Каждое высказывание как переменное, так и постоянное, является формулой (элементарной).
2. Если Б(у, …,■) — п-местная предикатная переменная или постоянный предикат, а х1, х2,., хп- предметные переменные или предметные постоянные (не обязательно все различные), то Б(х1, х2,…, хп) есть формула. Такая формула называется элементарной, в ней предметные переменные являются свободными, не связанными кванторами.
3. Если А и В — формулы, причем, такие, что одна и та же предметная переменная не является в одной из них связанной, а в другой — свободной, то слова А V В, А А В, А — В есть формулы. В этих формулах те переменные, которые в исходных формулах были свободны, являются свободными, а те, которые были связанными, являются связанными.
4. Если А — формула, то ^ — формула, и характер предметных переменных при
переходе от формулы А к формуле А не меняется.
5. Если А(х) — формула, в которую предметная переменная х входит свободно, то слова //хА( х) и ЗхА( х) являются формулами, причем, предметная переменная входит в них связанно.
6. Всякое слово, отличное от тех, которые названы формулами в пунктах 1 — 5, не является формулой.
Например, если Р(х) и Q(x,y) — одноместный и двухместный предикаты, а я,г-переменные высказывания, то формулами будут, например, слова (выражения):
д, Р(х), Р(х) л -(х0, у), /хР(х) — Зх-(х, у), (-(х, у) V д) — г .
Не является формулой, например, слово: //х—(х, у) — Р(х) . Здесь нарушено условие п.3, так как формулу //х—(х, у) переменная х входит связанно, а в формулу Р(х) переменная х входит свободно.
Из определения формулы логики предикатов ясно, что всякая формула алгебры высказываний является формулой логики предикатов.

3.5. Значение формулы логики предикатов

О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество М, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики предикатов зависит от значений трех видов переменных: 1) значений входящих в формулу переменных высказываний, 2) значений свободных предметных переменных из множества М, 3) значений предикатных переменных.
При конкретных значениях каждого из трех видов переменных формула логики предикатов становится высказыванием, имеющим истинное или ложное значение.
В качестве примера рассмотрим формулу Зy\/z(P(х, у) — Р(у, I)), (1) в которой
двухместный предикат Р(х, у) определен на множестве МхМ, где М={0,1,2,…,п,…}, т.е. МхМ=ШК
В формулу (1) входит переменный предикат Р(х,у), предметные переменные х,у,ъ, две из которых у и ъ — связанные кванторами, а х — свободная.
Возьмем за конкретное значение предиката Р(х,у) фиксированный предикат Р0(х,у): «х<у», а свободной переменной х придадим значение х0 = 5 е М. Тогда при значениях у, меньших х0=5, предикат Р0(х0,у) принимает значение «ложь», а импликация Р( х, у) — Р(у, I) при всех г е М принимает значение «истина», т.е. высказывание ЗуУг(Р (х, у) — Р (у, г)) имеет значение «истина». 3.6. Равносильные формулы логики предикатов Определение: Две формулы логики предикатов А и В называются равносильными на области М, если они принимают одинаковые логические значения при всех значениях входящих в них переменных, отнесенных к области М. Определение: Две формулы логики предикатов А и В называются равносильными, если они равносильны на всякой области. Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Рассмотрим основные из этих равносильностей. Пусть А(х) и В(х) — переменные предикаты, а С — переменное высказывание (или формула, не содержащая х). Тогда имеют место равносильности: 1. УхА( х) = ЗхА( х). 2. ЗхА( х) = УхА( х). 3. УхА( х) = ЗхА( х). 4. ЗхА( х) = УхА( х). 5. УхА(х) Л УхВ(х) = Ух[А(х) Л В(х)] 6. С Л УхВ(х) = Ух[С Л В(х)]. 7. С уУхВ(х) = Ух[С V В(х)] 8. С — УхВ( х) = Ух[С — В( х)] 9. Ух[В( х) — С ] = ЗхВ( х) — С. 10. Зх[А(х) V В(х)] = ЗхА(х) V ЗхВ(х). 11. Зх[С V В(х)] = С V ЗхВ(х). 12. Зх[С Л В(х)] = С Л ЗхВ(х). 13. ЗхА(х) Л ЗуВ(у) = ЗхЗу[А(х) Л В(у)]. 14. Зх[С — В( х)] = С — ЗхВ( х). 15. Зх[ В( х) — С ] = УхВ( х) — С. Равносильность 1 означает тот простой факт, что, если не для всех х истинно А(х), то существует х, при котором будет истиной А( х). Равносильность 2 означает тот простой факт, что, если не существует х, при котором истинно А(х), то для всех х будет истиной А( х). Равносильности 3 и 4 получаются из равносильностей 1 и 2, соответственно, если от обеих их частей взять отрицания и воспользоваться законом двойного отрицания. ЗАКОНЫ ЛОГИЧЕСКИХ ОПЕРАЦИЙ (общезначимые формулы логики предикатов) 1. //хР( х) = ЗхР( х). 2. ЗхР( х) = УхР( х). 3. /хР( х) = 1хР( х). 4. ЗхР( х) = ЧхР( х). 5. /х[Р(х) л (((х)] = /хР(х) л /х-(х). 6. Зх[Р(х) V -(х)] = ЗхР(х) V Зх-(х). 7. /х/уР( х, у) = /у/хР( х, у). 8. ЗхЗуР( х, у) = ЗуЗхР( х, у). 9. Зх/уР( х, у) ^УуЗхР( х, у). 10. /хР(х) V /х-(х) => /х[Р(х) V -(х)].
11. Зх[Р(х) л -(х)] ЗхР(х) л Зх-(х).
12. /х[Р(х) -(х)] [/хР(х) /х-(х) .
13. /хР(х) =^ЗхР(х).
14. /х[Р(х) Р(у)] = ЗхР(х) => Р(у) .
15. /х[Р(х) С] = ЗхР(х) С .
16. Р(у) => ЗхР(х) ЕЕ Зх[Р(у) => Р(х)].
17. С ЗхР(х) = Зх[С Р(х)].
18. С л /хР(х) = /х[С л Р(х)].
19. С V /хР(х) = /х[С V Р(х)].
20. С /хР(х) = /х[С Р(х)].
21. Зх[С V Р(х)] = С V ЗхР(х).
22. Зх[С л Р(х)] = С л ЗхР(х) .
23. ЗхР(х) л Зу-(у) ЕЕ ЗхЗу[Р(х) л -(у)].
24. Зх[Р(х) С] = /хР(х) С .
25.
/хР(х) V /х-(х) = /хР(х) V /у-(у) ЕЕ ЕЕ /х[Р(х) V Уу-(у)] ЕЕ /х/у[Р(х) V -(у)].
26.
ЗхР(х) л Зх-(х) = ЗхР(х) л Зу-(у) = ЕЕ Зх[Р(х) л Зу-(у)] ЕЕ ЗхЗу[Р(х) л -(у)].

3.7. Нормальные формы формул логики предикатов.

В логике предикатов, как и в логике высказываний, формулы могут иметь нормальную форму, т.е. существуют эквивалентные нормальные формы представления любых предикатных формул. При этом, используя равносильности алгебры высказываний и логики предикатов, каждую формулу логики предикатов можно привести к нормальной форме. В логике предикатов различают два вида нормальных форм: приведенную и предваренную.
Определение: Говорят, что формула логики предикатов имеет приведенную нормальную форму, если она содержит только операции конъюнкции, дизъюнкции и кванторные операции, а операция отрицания отнесена к элементарным формулам.
Пример 1:
(ЗхР( х) — /у-( у)) — Я( I) = ЗхР( х) vVye( у) V Я( I) = ЗхР( х) л /у-( у) V Я( I) ‘= ‘=ЗхР( х) лЗу-(у) V Я( I)
Получили приведенную нормальную форму исходной формулы.
Среди нормальных форм формул логики предикатов выделяют так называемую предваренную (префиксную, префиксную) нормальную форму (ПНФ). В ней кванторные операции либо полностью отсутствуют, либо они используются после всех операций алгебры логики, т.е. ПНФ формулы логике предикатов имеет вид
(Тх1 )(Тх 2)…((Гх„ ) А( Х1 , Х 2 — Хт X П ^ т ,
где под символом (Т^ понимается один из кванторов Ух^ или Зхг., а формула А
кванторов не содержит.
Алгоритм получения (приведения) ПНФ. Состоит в следующем:
1. Используя формулы 18, 19 (отнесенные к предикатам), заменить операции — и ~ на
2. Используя формулы логики предикатов 31, 32, а также формулы логики высказываний 1, 16, 17, представить предикатную формулу таким образом, чтобы символы отрицания относились непосредственно к символам предикатов (и, таким образом, мы приводим исходную формулу к приведенной форме).
3. Для формул, содержащих подформулы вида УхР(х) V Ух(((х), ЗхР(х) Л Зх(((х), вести новые переменные, позволяющие использовать соотношения 46, 47, 49, 50 или 53, 54.
4. С помощью формул 35 — 38, 46, 47, 49, 50, 53, 54 получить формулу в виде ПНФ.
Пример 2.
36
ЗхУуР(х, у) V УхЗу(((х, у) = ЗхУуР(х, у) V ЗхУу(((х, у) = Зх[УуР(х, у) V Уу(((х, у)] = | обозначим в предикате 0 переменную у через ъ
ЕЕ Зх[УуР(х, у) V У2((х, 2)] ЕЕ ЗхУуУ2(Р(х, у) V ((х, 2)) Пример 3.
1 6 31 ,32
(ЗхУуР(х, у) Л ЗхУу((х, у)) ЕЕ ЗхУуР(х, у) V ЗхУу((х, у) = УхЗуР(х, у) V УхЗу((х, у) = |
обозначим в предикате 0 переменную х через ъ
53 36
ЕЕ УхЗуР(х, у) V УгЗу((2, у)] ЕУхУ2(ЗуР(х, у) V Зу((2, у)) Е УхУгУу(Р(х, у) V ((2, у)) — ПНФ. Пример 4.
18 32
УхУу(Зг(Р(х, 2) Л ((у, 2)) — ЗиЯ(х, у, и)) = УхУу(З2(Р(х, 2) Л ((у, 2)) V ЗиЯ(х, у, и) =
16
ЕЕ УхУу(У2(Р(х, 2) Л ((у, 2) V ЗиЯ(х, у, и) 2УхУу(У2(Р(х, 2) V ((у, 2)) V ЗиЯ(х, у, и) ЕЕ ЕЕ I последний предикат не зависит от переменной ъ I ЕЕ
47
= \/x\/y\/z(P(x, z) v Q(y, z) v3uR(x, y, u)) = | два первых предиката не зависят от
49
переменной u | = //x//y//z3u(P(x, z) v Q(y, z) v R(x, y, u)) — ПНФ. Пример 5.
18 1
(3uP(u) ->//y//uQ(y,u)J —VxR(x) = (3uP(u) v//y//uQ(y,u)) —VxR(x) =
1 18 16
=3uP(u) v/y//uQ(y,u) —>//xR(x) = 3uP(u) v/y//uQ(y,u) v//xR(x) =
16 1 32
= 3uP(u) A//y//uQ(y,u) v //xR(x) =3uP(u) A//y//uQ(y,u) v //xR(x) =
32 35 46
= //uP(u) A//y//uQ(y,u) v//xR(x) = //u(P(u) A//yQ(y,u)) v//xR(x) =
46 47 37
= //u//y(P(u) AQ(y,u)) v//xR(x) =//u//y//x(P(u) AQ(y,u) vR(x)) =
37
= //x//y//u(P(u) A Q(y,u) v R(x)) — ПНФ.

3.8. Общезначимость и выполнимость формул. Проблема разрешимости.

Определение: Формула А логики предикатов называется выполнимой в области М,
если существуют значения переменных входящих в эту формулу и отнесенных к области М (иначе — существует модель), при которых формула А принимает истинные значения.
Определение: Формула А логики предикатов называется выполнимой, если существует область, на которой эта формула выполнима.
Определение: Формула А логики предикатов называется тождественно-истинной в области М (выполнимой), если она принимает истинные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.
Определение: Формула А логики предикатов называется общезначимой, если она тождественна истинна на всякой области (на любой модели).
Если две равносильные формулы логики предикатов соединить знаком эквиваленции <=>, то полученная формула будет принимать значение И для любого набора переменных в любой области, т. е. будет общезначимой.
Это понятие является обобщением понятия тождественной истинности формулы логики высказываний. Все логические законы, представленный в логике высказываний формулами (1 -30) являются общезначимыми формулами логики предикатов и выражают, как и другие общезначимые формулы, законы логики на языке логике предикатов.
Наиболее употребительные специфические законы логики предикатов, как было отмечено выше, представлены формулами (31 -54).
Общезначимость формулы логики предикатов, например, Б обозначается |- Б. Все общезначимые формулы могут быть источниками новых \- формул. Например, подставляя в
(14) — закон исключенного третьего х V х — вместо х предикат Р(х1,_,хп), получаем
общезначимую формулу Р(х1,_,хп)VР(х1,_,хп). При п=1 имеем общезначимую формулу
Р(х) V Р(х), и, таким образом , /х[Р(х) V Р(х)] — общезначимая формула логики предикатов.
Из тождественно истинной формулы логики высказываний (2) х V у = у V х
подстановкой вместо х предиката Р(х, у), а вместо у- предиката Q(x,y) получаем общезначимую формулу Р(х, у) V -(х, у) = -(х, у) V Р(х, у) и т. д.
Определение: Формула А логики предикатов называется тождественно ложной в области М, если она принимает ложные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области (иными словами, на данной модели).
Определение: Формула А логики предикатов называется тождественно ложной (невыполнимой)^ если она тождественно ложна на всякой области (на всякой модели).
Например, формула /х[Р(х) л Р(х)] является тождественно ложной (невыполнимой) формулой логики предикатов.
Из приведенных определений с очевидностью следует:
1 . Если формула А общезначима, то она и выполнима на всякой области (модели).
2. Если формула А тождественно истинна в области М, то она и выполнима в этой области .
3. Если формула А тождественно ложна в области М , то она не выполнима в этой области .
4. Если формула А не выполнима, то она тождественно ложна на всякой области (на всякой модели).
5. Для того, чтобы формула А логики предикатов была общезначима, необходимо и достаточно, чтобы ее отрицание было не выполнимо.
6. Для того, чтобы формула А логики предикатов была выполнимой, необходимо и
достаточно, чтобы формула А была не общезначима. Рассмотрим пример
Пример 1: Доказать равносильность (логическое тождество):
(Зх/уР( х, у) V ЗгЛЛР(у, и)) л (/УЗМР(У, и) л Зу/хР( х, у)) = Зх/уР(у, х) л /ЫЗУР(Ы, V) Заметив, что в каждой из кванторных подформул обе предметные переменные связаны и что, таким образом, они являются высказываниями, введем обозначения:
А= /хЗуР( х, у) = /уЗиР(у, и) = /иЗуР(и, V),
В= 3uVvP(v, u) = 3yVxP( x, y) = 3xVyP(y, x), или обозначив первую и вторую предметные переменные через nl и n2, соответственно:
А= Vn13n2 P(n1, n2), В= 3n2Vn1 P(n2, n1).
В этих обозначениях заданное для рассмотрения тождество будет выглядеть так: (A v B) л (A л B) = B л A .
Произведя равносильные преобразования, можем убедиться в справедливости этого
тождества: (A v B) AB і AAB v BAB Ї ЛБ v BAіBA
Если охарактеризовать рассматриваемое выражение в целом, то видим, что это общезначимая формула.
Пример 2 Определить тип формулы 3x3y[P(x) л P(y)] = F.. Пусть Р(х) : » Число х — четно -» предикат, определенный в M=N .
Таким образом, рассматриваемая формула на данной модели представляет собой следующее утверждение: » Среди натуральных чисел существуют как четные, так и нечетные «. Очевидно, что это высказывание истинно и, таким образом, на данной модели формула F тождественно истинна.
Однако, если этот же предикат задать на множестве М=№^где N — множество четных чисел, то формула F на такой модели окажется тождественно ложной.
Учитывая изложенное, заключаем, что рассматриваемая формула F выполнима (но не общезначима).
Пример 3: Для формулы 3yP(x, y, z) подобрать модель, на которой она является тождественно истинной (и, таким образом, в целом выполнимой).
Пусть Р(х, x, y): «x-x=y», или иначе «x2=y» — предикат, определенный на множестве натуральных чисел, т. е. M=N. Тогда рассматриваемая формула выражает утверждение о существовании натурального квадрата натурального числа, что, очевидно, является истиной, т. е. на данной модели формула тождественно истинна, что и требовалось доказать.
Пример 4: Рассмотрим формулу VxP(x, y, x) . Это выполнимая формула. Действительно, если Р(х, y, x): «x+y=x» — предикат суммы, то на M=N существует подстановка вместо y соответствующего значения, дающего значение истинности данной формуле. Очевидно, это y=0, поскольку в этом случае получаем «х=х».
Если же P(x, y, x): «xy=x» — предикат произведения, то таким значением y является y=1, так как при нем получаем истинное высказывание Vx( x • 1 = x).
Но это единственные подстановки, приводящие к верным утверждениям, что и говорит именно о выполнимости данной формулы (но не об ее общезначимости).
Пример 5: Является ли общезначимой формула: 3xP(x, y) — VxP(x, y) ?
Пусть Р(х, у) — предикат порядка (бинарного отношения ) » x < У «, определенный на конечном множестве натуральных чисел М1. Тогда при подстановке в формулу вместо свободной переменной у величины у = aтах е M1 мы получим истинное утверждение, а при
подстановке любой другой константы из множества М1 — ложное. Таким образом, рассматриваемая формула не является общезначимой.
Пример 6: Рассмотрим формулу A(y) л VzA(z) . Покажем, что она невыполнима. Допустим противное, т.е. что она выполнима. Это означает, что существует такое множество М и такой конкретный предикат A0 в нем, что когда у, z е M , то данная формула
превращается в такой конкретный предикат B( у) = A °(у) лVzA °(z), который, в свою очередь, превращается в истинное высказывание при всякой подстановке вместо у элементов из
множества М. Возьмем любое у0 е M . Тогда высказывание B(у0) = A0 (у0) л VzA0 (z) истинно,

как мы только что установили. Следовательно, истинны высказывания A0 (у0) и VzA0 (z) .
Из истинности второго высказывания заключаем, что высказывание A0 (у °) истинно (поскольку «для всех предметных переменных», как бы они ни обозначались). Но это
противоречит истинности первого высказывания A°(у°) .
Таким образом, наше предположение о выполнимости формулы неверно.
Проблема разрешимости в логике предикатов ставится так же, как и в алгебре логики: существуют ли алгоритмы, позволяющие для любой формулы А логики предикатов установить, к какому типу (классу) она относится, т. е. является ли она общезначимой, выполнимой или тождественно ложной (невыполнимой). Если бы такой алгоритм существовал, то, как и в алгебре высказываний, он сводился бы к критерию тождественной истинности любой формулы логики предикатов. Отметим, что, в отличие от алгебры логики, в логике предикатов не применим метод перебора всех вариантов значений переменных, входящих в формулу, так как таких вариантов может быть бесконечное множество.

3.9. Применение языка логики предикатов для записи математических предложений, определений, построения отрицания предложений

3.9.1 Запись математических предложений и определений в виде формул логики предикатов.

Язык логики предикатов удобен для записи математических предложений и определений. Он дает возможность выражать логические связи между понятиями, записывать определения, теоремы, доказательства. Приведем несколько примеров таких записей.
Пример 1: Определение предела » b » функции /(х), определенной в области E, в точке xo: b = lim f (x) <=>Ve> 038 > 0Vxe E(0 < Ix — x0|

предикат P(e, 8, x), запишем: b = lim f (x) <=> Ve > 035 > OVxe E(P(e, 5, x)),

где P(e, 8, x) = (0 < |x — x01 < 8 — |f (x) — b < e). Пример 2: Определение непрерывности функции в точке. Функция f (x), определенная на множестве E, непрерывна в точке x0 e E, если Ve > 038 > 0Vx e E(P(e, 8, x)), где P(e, 8, x) = (0 < |x — x01 < 8 — | f (x) — f (x0) < e). Пример 3: Определение возрастающей функции.
Функция f (x), определенная на множестве E возрастает на этом множестве, если Vx1 e EVx2 e E(x1 < x2 = f (x1) < f (x2)) .
Здесь использован двуместный предикат W(x1, x2) : (x1 < x2 = f (x1) < f (x2)) .

3.9.2. Построение противоположный утверждений.

Пусть дано некоторое математическое утверждение А. Ему будет противоположным будет утверждение A .
Логика предикатов позволяет путем равносильных преобразований формулы A придать ей хорошо обозримый вид.
Определение неограниченной функции мы получим, беря отрицание этой формулы и проводя равносильные преобразования:
3Me R+Vxe E(f (x) <M) = VMe R+Vxe E(f (x) <M)’=VMe R+3xe E(f (x) <M) = = VM e R+3xe E(f (x) > M)
Последняя формула дает не негативное, а положительное определение неограниченной функции.
Из приведенного определения видно, что для построения противоположного утверждения к утверждению, заданному формулой логики предикатов, содержащей все кванторы впереди, необходимо заменить все кванторы на противоположные и взять отрицание от предиката, стоящего под знаком кванторов.
Особый интерес представляет построение утверждения, отрицающего справедливость некоторой теоремы: Vx e E(P(x) ! Q(x)). Это будет утверждение:
Vxe E(P(x) -> Q(x))^3xe E(P(x) ! Q(x)) = 3xe E(P(x) л Q(x)). 3.9.3 Прямая, обратная и противоположная теоремы.
Рассмотрим четыре теоремы:
Vх е Е(р(х) —Q(x)), (1) ух е E(Р(х) — 0(х)), (3)
Vх е Е(Q(х) — р(x)), (2) ух е Е(ё(х) — Р(х)). (4)
Пара теорем, у которых условие одной является заключением второй, а условие второй является заключением первой, называются взаимно обратными друг другу.
Так, теоремы (1)и (2), а также (3) и (4)- взаимно обратные теоремы. При этом, если одну из них называют прямой теоремой, то вторая называется обратной.
Пара теорем, у которых условие и заключение одной являются отрицанием соответственно условия и заключения другой, называются взаимно противоположными.
Так, теоремы (1 ) и (3), а также (2) и (4) являются взаимно противоположными теоремами.
Например, для теоремы «Если в четырехугольнике диагонали равны, то четырехугольник является прямоугольником » (1) обратной является теорема «Если четырехугольник является прямоугольником, то его диагонали равны» (2). Для теоремы (1) противоположной является теорема «Если в четырехугольнике диагонали не равны, то четырехугольник не является прямоугольником » (3), а для теоремы (2) противоположной является теорема «Если четырехугольник не является прямоугольником, то его диагонали не равны » (4).
В рассмотренном примере теоремы (1 ) и (4) являются одновременно ложными, а теоремы (2) и (3) одновременно истинными. Контрпримером к теореме (1) является равнобочная трапеция.
Ясно, что прямая и обратная теоремы , вообще говоря, не равносильны, т. е. одна из них может быть истинной, а другая — ложной. Однако легко показать, что теоремы (1 ) и (4), а также (2) и (3) всегда равносильны.
Действительно:
Ух е Е(Р(х) — Q(х)) = Ух е Е(Р(х) V Q(х)) = Ух е Е(£(х) V Р(х)) = Ух е Е(£(х) — Р(х)) .
Из этих равносильностей следует, что, если доказана теорема (1 ), то доказана и теорема (4), а если доказана теорема (2), то доказана и теорема (3).

3.9.4. Необходимые и достаточные условия.

Рассмотрим теорему Ух е Е(Р(х) — Q(х))

Как отмечалось, множество истинности предиката Р(х) — 0(х) есть множество 1р и 1д. Но тогда множеством ложности этого предиката будет I- и 10 = 1Р п I- . Последнее множество будет пустым лишь в случае, когда 1Р а 10 (см. рисунок).

Итак, предикат Р(х) — 0(х) является истинным для всех х е Е том и в только в том случае, когда множество истинности предиката Р(х) содержится в множестве истинности предиката (((х). При этом говорят, что предикат (((х) логически следует из предиката Р(х), и предикат (((х) называют необходимым условием для предиката Р(х), а предикат Р(х) -достаточным условием для (((х).
Так, в теореме «Если х — число натуральное, то оно целое » предикат (((х): » х — число целое » логически следует из предиката Р(х): «х — число натуральное» , а предикат «х- число натуральное» является достаточным условием для предиката » х -целое число».
Рис. 1. Часто встречается ситуация, при которой истинны взаимно
обратные теоремы Ух е Е(Р(х) — 0(х)) (1)
Ух е Е(0(х) — Р(х)) (2)
Это, очевидно, возможно при условии, что IР = 10 .
В таком случае из теоремы (1)следует, что условия Р(х)являются достаточными для (((х), а из теоремы (2) следует, что условие Р(х)является необходимым для (((х).
Таким образом, если истинны теоремы (1 ) и (2), то условие Р(х) является и необходимым, и достаточным для (((х). Аналогично в этом случае условие (((х)является необходимым и достаточным для Р(х).
Иногда вместо логической связки «необходимо и достаточно » употребляют логическую связку «тогда и только тогда».
Так как здесь истинны высказывания (1 ) и (2), то истинно высказывание
Ух е Е(Р(х) — 0(х)) л Ух е Е(0(х) — Р(х)) Т Ух е Е(Р(х) о 0(х)).

3.9.5. Доказательство теорем методом от противного.

Доказательство теорем методом от противного обычно проводится по следующей схеме: предполагается, что теорема
Ух є Е[Р(х) -> б(х)] (1)
не верна, т. е. , существует такой объект х, что условие Р(х) истинно, а заключение <3(х) -ложно. Если из этих предложений путем логических рассуждений приходят к противоречивому утверждению, то делают вывод о том, что исходное предположение неверно, и верна теорема (1).
Покажем, что такой подход дает доказательство истинности теоремы (1). Действительно, предположение о том, что теорема (1) не справедлива , означает
истинность ее отрицания, т. е. формулы Vx е E[P(x) — Q(x)]. Можно показать, что противоречивое утверждение, которое получается из допущенного предположения, как мы видели из ранее рассмотренных примеров, может быть записано как конъюнкция C л C = A, где С — некоторое высказывание.

Скачать: