Предикаты

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

Предикаты.

Логика предикатов изобретена Готлобом Фреге. На латыни слово «предикат» (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 -местный предикат , заданный на М, будет:

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

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

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

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