Лекция 8. Логика предикатов
Логика предикатов - логическая система, представляющая развитие логики высказываний. Исторически понятие о предикатах явилось следствием логического анализа высказываний, т. е. выяснения их логической структуры.
Предикаты
Рассмотрим пример: «x простое число». Это выражение не является высказыванием, но если в нем переменную x заменить на определенное число, то получим высказывание. Причем при замене x на число 3 получим истинное высказывание, тогда как при замене x на 8 получим ложное высказывание.
Таким образом, выражение: «x простое число» можно рассматривать как функцию Р(х), зависящую от переменной х. Область определения Р(х) - множество чисел, а область значения - высказывание.
Определение. Предикат - функция, значениями которой являются высказывания о п объектах, представляющих значения аргументов.
Чтобы задать n -местный предикат Р(x1, x2, ... , x п), следует указать множества Х1, Х2, ... , Хп - области изменения переменных x1, x2, ... , xп, причем чаще всего рассматривается случай, когда Х1 = Х2 = ... = Хп.
С теоретико-множественной точки зрения предикат определяется заданием подмножества М в декартовом произведении Х 1 ⨯ Х 2 ⨯ ... ⨯ Х п.
Переменные x1, x2, ... , xп называются предметными переменными.
Элементы множеств Х1, Х2, ... , Хп называются предметами. Множество М -множество кортежей длины п ‹x1, x2, ... , x п› называется полем предиката
Р(x1, x2,...,xп).
Будем обозначать предметные переменные малыми буквами конца латинского алфавита (иногда будем снабжать эти буквы индексами) x, у, z, ... ,x1, x2, ... , xп.
Предметы из множеств Х1, Х2, ... ,Хп - малыми буквами начала латинского алфавита а, b, с, ... , аl, а2, аз ....
Предикаты - большими буквами латинского алфавита с приписанными предметными переменными или без них А(х, х), В, F(x, у), Р(xl, ... , хп).
Число переменных будем указывать как верхний индекс у предиката: Pk(x1, x2, ... , xk) - k местный предикат, Q2(x, у) - двуместный предикат, Р(x) - одноместный предикат.
Итак, k-местный предикат - Pk(x1, x2, ... , xk) есть функция, предметные переменные которой принимают значения из некоторого множества Mk , а сама она принимает только два значения: истина (1) или ложь (0), т. е.
Например, если Х - множество действительных чисел, то х2 > 1 одноместный предикат.
Если Х, Y - множества действительных чисел, то ху = 5 - двуместный предикат.
Предикат называется разрешимым, если существуют такие кортежи, компоненты которых обращают предикат в истинное высказывание.
Если предикат при подстановке любых конкретных элементов из соответствующих множеств обращается в истинное высказывание, он называется тождественно истинным.
Если предикат при подстановке любых конкретных элементов из соответствующих множеств обращается в ложное высказывание, он называется тождественно ложным.
К предикатам, определенным на одном и том же множестве, можно применять операции алгебры высказываний: конъюнкцию, дизъюнкцию, импликацию, эквивалентность, отрицание и получать новые предикаты.
Например, если к предикатам «x = у» и «x < у» - обозначим их соответственно Р(x, у) и Q(x, у) - применить операцию конъюнкции, то получим новый предикат
Р(x, у) ˄ Q(x, у).