Понятие предиката; операции и отношения между предикатами

Лекция. Формулы логики предикатов 1. Понятие предиката. Операции и отношения между предикатами Вначале определим одноместный предикат. Определение 1. Пусть дано множество М. Одноместным предикатом на множестве М называется предложение, которое содержит одну переменную и превращается в высказывание, если переменной придать конкретное значение из М. Обозначение: Р(х). Здесь буква Р обозначает предикат, а х – переменную, от которой зависит Р. Чтобы акцентировать внимание на то, что предикат задан на множестве М, пишут х  М. Пример. Возьмем предложение Р(х): «х – четное число», х  Z. Имеем одноместный предикат, заданный на множестве целых чисел. Если х = 2, то Р(2) – истинное высказывание. Если х = –3, то Р(–3) – ложное высказывание. С каждым предикатом тесно связано понятие характеристической функции. Характеристической функцией предиката Р(х) называется отображение вида  : M  {0, 1}, заданное правилом 1, если 𝑃(𝑥) истина (𝑥) = { . 0, если 𝑃(𝑥) ложь Иногда под термином «предикат» понимают именно его характеристическую функцию, а само предложение с переменной называют «высказывательной формой». С математической точки зрения нет различия между предикатом как предложением и его характеристической функцией. Множество, на котором предикат принимает истинное значение, называется множеством истинности. Предикаты называются равносильными, если их множества истинности равны. Равносильность часто обозначают знаком ⇔. Предикат Q(x) называется следствием предиката Р(х), если множество истинности Р(х) включено во множество истинности Q(x). В этом случае говорят, что из Р(х) следует Q(x) и пишут Р(х)  Q(x). Все вышесказанное можно перенести на общее понятие п-местного предиката. Определение 2. Пусть даны п множеств М1, …, Мп. Тогда п-местным предикатом (или просто, предикатом), заданным на этих множествах, называется предложение, содержащее п переменных, и превращающееся в высказывание, если переменным придать конкретные значения из соответствующих множеств. Обозначение: Р(х1, …, хп), где переменная хi принимает значение из Мi. Если п = 1, то получаем определение одноместного предиката. Если п = 2, предикат называют двуместным, если п = 3, – трехместным. Пример. Рассмотрим предложение Р(х1, х2): «Точка х1 лежит на прямой х2». Здесь М1 – множество точек, М2 – множество прямых. Имеем двуместный предикат, заданный на множествах М1 и М2. Любой п-местный предикат Р(х1, …, хп), заданный на множествах М1, …, Мп, можно рассматривать как одноместный Р(х), который задан на прямом произведении этих множеств. В этом случае переменная х имеет вид вектора х = (х1, …, хп). Поэтому определения характеристической функции и множества истинности, данные выше для одноместного предиката, можно перенести на произвольный предикат. Напомним, что прямым произведением данных множеств называется множество всех упорядоченных п-ок, координаты которых лежат в соответствующих множествах: М1  …  Мп = {(х1, …, хп) : хi  Mi}. Если все множества М1, …, Мп равны одному множеству М, то говорят, что предикат задан на множестве М. Определение предиката удобно распространить на случай, когда переменна п равна 0. Нульместным предикатом называется произвольное высказывание, то есть предложение, не зависящее ни от одной переменной. Таким образом, понятие предиката является обобщением понятия высказывания. А высказывание можно считать частным случаем предиката (когда п = 0). 2. Определение формулы логики предикатов. Свободные и связанные вхождения предметных переменных Вначале вспомним определение формулы. Алфавит, необходимый для записи формул. 1) Буквы, обозначающие предикаты. Это предикатные переменные. В общем случае их будем обозначать Р1, Р2, …, возможно, с верхними индексами, например, Р(п). Верхний индекс п у переменной Р подчеркивает, что предикат является п-местным. Если п = 0, то Р(п) является высказывательной переменной. 2) Буквы, обозначающие переменные, от которых зависят предикаты. Это предметные (индивидные) переменные. В общем случае их будем обозначать х1, х2, … 3) Логические связки , , , ¬, кванторы , . 4) Знаки скобок (, ), и запятой «,». Замечание: на практике предикатные переменные часто обозначают разными буквами, что не указывать индексы (например, вместо Р1, Р2, пишут P, R). Аналогичная ситуация с предметными переменными: вместо х1, х2, х3, пишут х, у, z. Определение формулы носит конструктивный характер. Указываются правила, которые могут применяться при конструировании формулы. Правило 1. Если Р(п) – предикатная переменная (п  0), u1, …, un – какие-то предметные переменные, необязательно различные, то Р(u1, …, un) – формула. В частности, если п = 0, то высказывательная переменная Р(0) есть формула. Правило 2. Если 𝐴, 𝐵 – формулы, то формулами являются выражения вида (𝐴 ∧ 𝐵), (𝐴 ∨ 𝐵), (𝐴 → 𝐵), (¬𝐴). Правило 3. Если 𝐴 – формула, х – предметная переменная, то формулами являются выражения вида ∀𝑥𝐴, ∃𝑥𝐴. В полученных формулах 𝐴 называется областью действия соответствующего квантора (кванторной приставки). Других правил образования формул нет. То есть выражение называется формулой логики предикатов, если оно может быть получено только применение правил 1–3. Из данного определения следует, что формула логики высказываний является частным случаем формулы логики предикатов (в логике высказываний нет правила 3, а правило 1 соответствует случаю п = 0) Формулы, получаемые по правилу 1, называются элементарными (атомарными). Ряд скобок в формулах опускают, при условии, что их можно однозначно восстановить. Приоритет логических связок такой же, как в логике высказываний. Считается, что знаки кванторов имеют приоритет над остальными логическими связками. Пример. 𝑃(𝑥), 𝑄(𝑦) – атомарные формулы. Значит, (𝑃(𝑥) → 𝑄(𝑦)) – формула. Поэтому ∀𝑥(𝑃(𝑥) → 𝑄(𝑦)) – формула. Здесь скобки убрать нельзя. Иначе получится другая формула, при построении которой вначале к 𝑃(𝑥) будет приписана кванторная приставка, что даст формулу ∀𝑥𝑃(𝑥), а затем получится ∀𝑥𝑃(𝑥) → 𝑄(𝑦).  Выделяют два вида вхождений предметной переменной в формулу: свободное и связанное. Вхождение переменной называется связанным, если эта переменная находится в кванторной приставке или попадает в область действия соответствующей кванторной приставки. В противном случае, вхождение предметной переменной называется свободным. Одна и та же переменная может иметь в формуле и свободное и связанное вхождения. Примеры. В элементарной формуле 𝑃(𝑥, 𝑦) обе переменные х и у входят свободно. В формуле ∀𝑥𝑃(𝑥, 𝑦) переменная у входит свободно, а вхождение переменной х становится связанным. Возьмем еще элементарную формулу 𝑄(𝑥), в ней х – свободная. Вначале образуем формулу 𝑃(𝑥, 𝑦) → 𝑄(𝑥), в ней х и у входят свободно. Тогда в формуле ∀𝑥(𝑃(𝑥, 𝑦) → 𝑄(𝑥)) вхождение у остается свободным, а вхождение х будет связанным. Если же из двух формул ∀𝑥𝑃(𝑥, 𝑦) и 𝑄(𝑥) образовать новую формулу ∀𝑥𝑃(𝑥, 𝑦) → 𝑄(𝑥), то получим, что в ней имеет место и связанное вхождение переменной х (в ∀𝑥𝑃(𝑥, 𝑦)), и свободное вхождение этой же переменной (в 𝑄(𝑥)).  Формула, в которую все переменные входят связанно, называется замкнутой. Если есть хотя бы одно свободное вхождение какой-то переменной, формула называется открытой. 3. Интерпретация формул Определим, как задается логическое значение формулы логики предикатов. Пусть дана формула А. Зафиксируем непустое множество М. После этого определим предикаты, заданные на М, и каждой предикатной переменной формулы А сопоставим конкретный предикат. В этом случае формула превратится в предложение, зависящее от свободных предметных переменных. Говорят, что рассмотрена интерпретация формулы на множестве М. Если всем свободным переменным придать конкретные значения из М, формула превратится в высказывание, то есть будет принимать значение 1 или 0. Замкнутая формула в любой интерпретации сразу превращается в высказывание. Итак, логическое значение формулы зависит от значений двух видов переменных: а) значений входящих в формулу предикатных переменных; б) значений свободных предметных переменных из множества М. А от связанной переменной значение формулы не зависит. Пример. Возьмем формулу 𝐴 = (∃𝑧𝑃(𝑥, 𝑦, 𝑧)). Она содержит одну предикатную переменную Р и две свободные предметные переменные х и у. Приведем разные интерпретации этой формулы. 1) Рассмотрим множество целых чисел Z, на котором определим трехместный предикат: «Число х равно произведению чисел у и z». Подставим в формулу А этот предикат. Тогда А превратиться в двуместный предикат А1(х, у): «Существует целое число z, такое, что х = yz». Предикат А1(х, у) задает бинарное отношение делимости на множестве Z: «х делится на у». 2) Теперь рассмотрим множество натуральных чисел, на котором определим другой трехместный предикат: «Число х равно сумме чисел у и z». Тогда А превратиться в предикат А2(х, у): «Существует натуральное число z, такое, что х = y + z». Предикат А2(х, у) задает другое бинарное отношение, а именно, отношение «больше» для натуральных чисел (так как на множестве N равенство х = y + z для некоторого натурального числа z равносильно неравенству x > y).  Переименование связанной переменной Рассмотрим две формулы 𝐴 = ∀𝑥𝑃(𝑥, 𝑦) и 𝐵 = ∀𝑧𝑃(𝑧, 𝑦), отличающиеся только обозначением связанной переменной. Если взять любой двуместный предикат, и подставить его в эти формулы вместо Р, то мы получим два одинаковых высказывания, так как обозначение связанной переменной не влияет на логическое значение высказывания. Например, возьмем в качестве Р такое предложение: «Число х больше числа у», считая, что х  N, у  Z. Получим предложения: ∀𝑥𝑃(𝑥, 𝑦): «Любое натуральное число х больше целого числа у»; ∀𝑧𝑃(𝑧, 𝑦): «Любое натуральное число z больше целого числа у». Оба эти предложения можно сформулировать так, чтобы название связанной переменной отсутствовало в произношении: «Любое натуральное число больше целого числа у». Таким образом, обе формулы А и В определяют одно и то же предложение, которое является одноместным предикатом 𝑄(𝑦). При у = –1 имеем истинное высказывание, а при у = 2, – ложное. А от связанной переменной предикат не зависит. Связанное вхождение переменной можно заменить другой буквой, логический смысл формулы при этом никак не изменится. Однако при таком преобразовании надо соблюдать требование: ни одно свободное вхождение переменной в любой части формулы не должно превратиться в связанное вхождение. Например, в формуле ∀𝑥𝑃(𝑥, 𝑦) нельзя поменять х на у, так как после этого свободная переменная у станет связанной: ∀𝑦𝑃(𝑦, 𝑦). Свободная переменная исчезла. Говорят, что произошла коллизия переменных. Формулы, полученные друг из друга правильным переименованием связанной переменной (без коллизии), называются конгруэнтными, то есть одинаковыми, равными. Пишут А  В. Применяя операцию переименования связанной переменной, можно добиться того, чтобы все связанные переменные формулы были обозначены разными буквами, не совпадающими с обозначениями свободных переменных. Примеры. ∀𝑥𝑃(𝑥) ∧ ∃𝑥𝑄(𝑥) ≈ ∀𝑥𝑃(𝑥) ∧ ∃𝑦𝑄(𝑦), ∀𝑥𝑃(𝑥, 𝑦) → 𝑄(𝑥) ≈ ∀𝑧𝑃(𝑧, 𝑦) → 𝑄(𝑥).