Лекция 8. Логика предикатов

Логика предикатов - логическая система, представляющая развитие логики высказываний. Исторически понятие о предикатах яви­лось следствием логического анализа высказываний, т. е. выяснения их логической структуры.

Предикаты

Рассмотрим пример: «x простое число». Это выражение не является высказыванием, но если в нем переменную x заменить на определенное число, то получим высказывание. Причем при замене x на число 3 полу­чим истинное высказывание, тогда как при замене x на 8 получим ложное высказывание.

Таким образом, выражение: «x простое число» можно рассматривать как функцию Р(х), зависящую от переменной х. Область определения Р(х) - множество чисел, а область значения - высказывание.

Определение. Предикат - функция, значениями которой являются выска­зывания о п объектах, представляющих значения аргументов.

Чтобы задать n -местный предикат Р(x₁, x₂, ... , x _п), следует указать множества Х₁, Х₂, ... , Х_п - области изменения переменных x₁, x₂, ... , x_п, причем чаще всего рассматривается случай, когда Х₁ = Х₂ = ... = Х_п.

С теоретико-множественной точки зрения предикат определяется за­данием подмножества М в декартовом произведении Х ₁ ⨯ Х ₂ ⨯ ... ⨯ Х п.

Переменные x₁, x₂, ... , x_п называются предметными переменными.

Элементы множеств Х₁, Х₂, ... , Х_п называются предметами. Множество М -множество кортежей длины п ‹x₁, x₂, ... , x _п› называется полем пре­диката

Р(x₁, x₂,...,x_п).

Будем обозначать предметные переменные малыми буквами кон­ца латинского алфавита (иногда будем снабжать эти буквы индексами) x, у, z, ... ,x₁, x₂, ... , x_п.

Предметы из множеств Х₁, Х₂, ... ,Х_п - малыми буквами начала ла­тинского алфавита а, b, с, ... , а_l, а₂, а_з ....

Предикаты - большими буквами латинского алфавита с припи­санными предметными переменными или без них А(х, х), В, F(x, у), Р(x_l, ... , х_п).

Число переменных будем указывать как верхний индекс у предиката: P^k(x₁, x₂, ... , x_k) - k местный предикат, Q²(x, у) - двуместный предикат, Р(x) - одноместный предикат.

Итак, k-местный предикат - P^k(x₁, x₂, ... , x_k) есть функция, предмет­ные переменные которой принимают значения из некоторого множества M_k , а сама она принимает только два значения: истина (1) или ложь (0), т. е.

Например, если Х - множество действительных чисел, то х² > 1 ­одноместный предикат.

Если Х, Y - множества действительных чисел, то ху = 5 - двумест­ный предикат.

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

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

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

К предикатам, определенным на одном и том же множестве, мож­но применять операции алгебры высказываний: конъюнкцию, дизъюнк­цию, импликацию, эквивалентность, отрицание и получать новые предикаты.

Например, если к предикатам «x = у» и «x < у» - обозначим их соответственно Р(x, у) и Q(x, у) - применить операцию конъюнкции, то получим новый предикат

Р(x, у) ˄ Q(x, у).