42

1.2 Основы логики предикатов и логического вывода

1.2.1 Предикаты.

Логика предикатов изобретена Готлобом Фреге. На латыни слово «предикат» (praedicatum) означает «сказуемое», то есть то, что в элементарном суждении утверждается о субъекте этого суждения, свойства этого субъекта. Например, высказывание «Собака имеет хвост» истинно, «Лошадь имеет хвост» истинно, а «Человек имеет хвост» ложно. Если заменить субъект в суждении переменной х, получим некую форму «х имеет хвост», которая является функцией от х и принимает значения истинно для одних субъектов-аргументов этой функции и ложно для других. Формализация подобной высказывательной формы и называется предикатом.

Предикат — предложение, похожее на высказывание, но все же им не являющееся: о нем нельзя судить, истинно оно или ложно.

Дадим точное определение.

Определение 1.. Определенным на множествах п-местным предикатом называется предложение, содержащее п переменных , превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств соответственно.

Для п-местного предиката будем использовать обозначение . Переменные называют предметными, а элементы множеств , которые эти переменные пробегают, — конкретными предметами. Всякий п-местный предикат , определенный на множествах представляет собой функцию п аргументов, заданную на указанных множествах и принимающую значения в множестве всех высказываний. Поэтому предикат называют также функцией-высказыванием.

Высказывание – не что иное, как предикат без аргумента, или предикат с нулевым числом мест.

Предложение ‑ одноместный предикат, определенный на множестве действительных чисел X. Предложения , , ‑ двуместные (бинарные) предикаты, заданные над множествами действительных чисел X, Y.

Отметим еще один подход к понятию предиката. Как говорилось, предикат , определенный на множествах , превращается в конкретное высказывание , если вместо предметных переменных подставить в него конкретные предметы (элементы ) из множеств соответственно. Это высказывание может быть либо истинным, либо ложным, т. е. его логическое значение равно 1 или 0. Следовательно, данный предикат определяет функцию п аргументов, заданную на множествах и принимающую значение в двухэлементном множестве {0, 1}.

С теоретико-множественной точки зрения предикат определяется заданием подмножества М в декартовом произведении . Множество М ‑ множество кортежей длины п ‑ называется предметной областью предиката .

Таким образом, п-местный предикат ‑ это функция, предметные переменные которой принимают значения из некоторого множества М, а сама она принимает только два значения: истина (1) или ложь (0), т.е. .

Классификация предикатов.

Определение2. Пусть – некоторый n-местный предикат на некотором множестве M. Этот предикат называется:

а) тождественно истинным (общезначимым), если , он превращается в истинное высказывание, т.е. ;

б) тождественно ложным, если , его значение равно ложь, т.е. ;

в) выполнимым (разрешимым), если существует хотя бы один кортеж , на котором ;

г) опровержимым, если существует хотя бы один кортеж , на котором .

Например, предикат P(x) = «x – нечетное число» ‑ выполним на множестве M = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Если в качестве предметной области для предиката P(x) выбрать множество , то P(x) на будет тождественно истинным предикатом, так как при подстановке вместо х любой из предметных констант, он превращается в истинное высказывание. Если в качестве предметной области для P(x) выбрать множество , то P(x) на будет тождественно ложным предикатом, так как при подстановке вместо х любой из предметных констант, он превращается в ложное высказывание.

Множество истинности предиката.

Определение 3. Множеством истинности предиката , заданного на множестве М, называется совокупность кортежей из М, таких, что обращается в истинное высказывание, т.е. . Это множество будем обозначать .

Таким образом,

.

Множество истинности является подмножеством множества М: .

Например, для предиката P(x) = «x – нечетное число» с предметной областью M = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} множеством истинности будет . Множеством истинности двухместного предиката с предметной областью (R ‑ множество действительных чисел) будет множество всех пар действительных чисел, которые являются координатами точек плоскости, образующих окружность с центром в начале координат и радиуса 3. Для одноместного предиката над множество истинности будет .

В терминах множества истинности легко выразить понятия, связанные с классификацией предикатов. В самом деле n-местный предикат , заданный на М, будет:

а) тождественно истинным тогда и только тогда, когда ;

б) тождественно ложным тогда и только тогда, когда ;

в) выполнимым тогда и только тогда, когда ;

г) опровержимым тогда и только тогда, когда .

Равносильность и следование предикатов.

Определение 4. Предикаты и , заданные на одной и той же предметной области М, равносильны тогда и только тогда, когда их множества истинности совпадают . Утверждение о равносильности двух предикатов Р и Q символически будем записывать так: или .

Отношение равносильности предикатов является отношением эквивалентности, так что совокупность всех п-местных предикатов, определенных на М, распадается на непересекающиеся классы равносильных предикатов (все они определяют одну и ту же функцию, заданную на М и принимающую значения в двухэлементном множестве {0, 1}). Переход от предиката к равносильному ему предикату называется равносильным преобразованием первого. Это понятие очень важно для математики, потому что изучаемые в ней уравнения и неравенства представляют собой частные виды предикатов. Решение уравнения и неравенства есть поиск их множеств истинности. При таком поиске мы проделываем над уравнением и неравенством различные преобразования, и здесь важно, чтобы эти преобразования были равносильными, т. е. чтобы найденное множество оказалось бы множеством истинности именно исходного уравнения или неравенства. Аналогична ситуация при решении систем уравнений или неравенств.

Определение 5. Пусть и – два n-местных предиката от одних и тех же переменных, заданных на одном и том же множестве М. Предикат называется следствием предиката , если для любого набора переменных, на которых предикат является истинным, предикат также истинен. Следствие обозначается как

.

Другими словами (в терминах множеств истинности), можно сказать, что предикат является следствием предиката Р тогда и только тогда, когда .

Пример. Если и , , то но не наоборот.

Теорема. Предикаты и равносильны тогда и только тогда, когда каждый из них есть следствие другого.

Доказательство. Необходимость. , тогда , т.е. и . Из вытекает, что , а из вытекает, что .

Достаточность. Пусть и . Тогда из первого утверждения следует, что , а из второго ‑ . Из этих двух соотношений вытекает, что и .