Предикаты и операции над ними. Предикаты и кванторы Логические операции над предикатами примеры

25.

26.

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

Например, в рассуждении «Всякий ромб – параллелограмм; AВCD – ромб; следовательно, AВCD – параллелограмм» посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учета их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

В связи с этим возникает необходимость в расширении логики высказываний, в построении такой логической системы, средствами которой можно было бы исследовать и структуру тех высказываний, которые в рамках логики высказываний рассматриваются как элементарные.

Такой логической системой является логика предикатов, содержащая всю логику высказываний в качестве своей части.

Логика предикатов, как и традиционная формальная логика, расчленяет элементарное высказывание на субъект (буквально – подлежащее, хотя оно и может играть роль дополнения) и предикат (буквально – сказуемое, хотя оно может играть и роль определения).

Субъект – это то, о чем что-то утверждается в высказывании; предикат – это то, что утверждается о субъекте.

Например, в высказывании «7 – простое число», «7» – субъект, «простое число» – предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом»

Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х – простое число». При одних значениях х (например. х = 13, х = 17) эта форма дает истинные высказывания, а при других значениях х (например, х = 10, х = 18) эта форма дает ложные высказывания.

Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множестве N, и принимающую значения из множества {1,0}. Здесь предикат становится функцией субъекта и выpaжает свойство субъекта.

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

Множество М, на котором определен предикат Р(х), называется областью определения предиката.

Множество всех элементов, при которых предикат принимает значение «истина», называется множеством истинности предиката Р(х) , то есть множество истинности предиката Р(х) – это множество.

Так. предикат Р(х) – «х – простое число» определен на множестве N, а множество для нeгo есть множество всех простых чисел. Предикат Q(x) – «» определен на множествеR, а eгo множество истинности. Предикат F(x) «Диагoнали параллелогpамма х перпендикулярны» определен на множестве всех параллелограммов, а eгo множеством истинности является множество всех ромбов.

Приведенные при меры одноместных предикатов выражают свойства предметов.

Определение. Предикат Р(х), определенный на множестве М, называется тождественно истинным (тождественно ложным), если .

Естественным обобщением понятия одноместного предиката является понятие многоместного предиката, с помощью котopoгo выражаются отношения между предметами.

Примером бинарного отношения (отношения между двумя предметами) является отношение «меньше». Пусть это отношение введено на множестве Z целых чисел. Оно может быть охарактеризовано высказывательной формой «x<у », где, то есть является функцией двух переменных Р(х,у), определенной на множествес множеством значений {1,0}.

Определение. Двухместным предикатом Р(х, у) называется функция двух переменных х и y, определенная на множествеИ принимающая значения из множества {1,0}.

Аналогично определяется n-местный предикат.

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

Отрицание предиката . Пусть предикат P(x 1 , x 2 , ..., x n) задан на множествах M 1 , M 2 , ..., M n . Предикат R(x 1 , x 2 ,..., x n) называется отрицанием предиката P(x 1 , x 2 , ..., x n) тогда и только тогда, если при одних и тех же кортежах (a 1 , a 2 , ... , a n), где а 1 M 1 , а 2 M 2 , ..., аn M n , высказывание P(a 1 , a 2 , ..., a n) истинно, когда R(a 1 , a 2 , ..., a n) - ложно и наоборот. Обозначение

R(x 1 , x 2 , ..., x n) ù P(x 1 , x 2 , ..., x n)

Например, предикат "n - четное число" есть отрицание предиката "n - нечетное число" на множестве целых чисел.

Конъюнкция предикатов . Пусть на множествах M 1 , M 2 , ..., M n заданы два n - местных предиката P(x 1 , x 2 , ..., x n) и R(x 1 , x 2 , ..., x n). Конъюнкцией этих предикатов называется предикат

Q(x 1 , x 2 , ..., x n) P(x 1 , x 2 , ..., x n) R(x 1 , x 2 , ..., x n),

который истинен для одних и тех же кортежей только тогда, когда оба предиката и P(x 1 , x 2 , ..., x n) и Q(x 1 , x 2 , ..., x n) истинны.

Например, конъюнкция предикатов "x 2 + y 2 1" и "x 0", где x, y - вещественные числа определяет предикат "точки правой половины единичного круга" (см. рис.2.2).

Дизъюнкция предикатов P(x 1 , x 2 , ..., x n) и R(x 1 , x 2 , ..., x n), есть новый предикат S(x 1 , x 2 , ..., x n) = P(x 1 , x 2 , ..., x n) R(x 1 , x 2 , ..., x n), который имеет значение "ложь" для тех и только тех кортежей из M 1 M 2 ... M n , для которых оба предиката и P(x 1 , x 2 , ..., x n) и R(x 1 , x 2 , ..., x n) имеют значение "ложь". На рис.2.3 иллюстрируется дизъюнкция предиката "x 2 + y 2 1" и "x 0" - (заштрихованная область).

Импликация предикатов P(x 1 , x 2 , ..., x n) и R(x 1 , x 2 , ..., x n), есть новый предикат T(x 1 , x 2 , ..., x n) = P(x 1 , x 2 , ..., x n) R(x 1 , x 2 , ..., x n), который имеет значение "ложь" для тех и только тех кортежей из M 1 M 2 ... M n , для которых предикат P(x 1 , x 2 , ..., x n) имеет значение "истина", а предикат R(x 1 , x 2 , ..., x n) имеет значение "ложь". Например, импликация "n делится на 4" " n делится на 2" есть предикат: "если n делится на 4, то n делится на 2".

Эквивалентность предикатов P(x 1 , x 2 , ..., x n) и R(x 1 , x 2 , ..., x n), есть новый предикат V(x 1 , x 2 , ..., x n) = P(x 1 , x 2 , ..., x n) R(x 1 , x 2 , ..., x n), который имеет значение "истина" для тех и только тех кортежей из M 1 M 2 ... M n , для которых предикат P(x 1 , x 2 , ..., x n) и предикат R(x 1 , x 2 , ..., x n) имеют одинаковые значение или оба "истина" или оба "ложь". Два предиката заданных на одних и тех же множествах называются равносильными , если при всех наборах входящих в них предметных переменных эти предикаты принимают одинаковые значения. Равносильность называют также логической эквивалентностью . Например, эквивалентность предикатов P(n) = "n делится на 6" и R(n) = "n делится на 2 и n делится на 3" есть предикат V(n) = P(n) R(n): "если n делится на 6, то n делится на 2 и на 3". Предикаты P(n) и R(n) логически эквивалентны.

Наряду с логическими операциями важную роль играют операции, называемые кванторами.

Квантор всеобщности есть операция, которая предикат P(x) превращает в высказывание: "все x обладают свойством P(x)". Знак квантора всеобщности " ". Он заменяет фразы: "для всех", "каждый", "любой" и т.п. Обозначение x: P(x) читается так: "для всех x таких, что P от x". Например, “P(x) = x>0 , где x - вещественное число”, есть предикат "x - положительное число". Тогда x: P(x) есть высказывание "каждое число - положительно". Это ложное высказывание. Если же x - любое натуральное число (x N), то x: P(x) есть выражение: "каждое натуральное число - положительно" - истинное высказывание.

Квантор всеобщности можно рассматривать как обобщение серии конъюнкций единичных высказываний. Пусть M - множество очков, которое может выпасть при бросании игральной кости, т.е. M ={1,2,3,4,5,6} и P(x) - предикат: "при бросании игральной кости один раз выпадает x очков", где x M. Применение квантора всеобщности позволяет вместо сложного высказывания P(1) P(2) P(3) P(4) P(5) P(6) записать равносильное ему компактное высказывание x: P(x), x M: "при бросании игральной кости один раз может выпасть любое из шести первых натуральных чисел".

Квантор существования есть операция, которая предикат P(x) превращает в высказывание: "существует хотя бы один x из M, обладающий свойством P(x)". Знак квантора существования " ". Он заменяет фразы: "существует, хотя бы один", "найдется", "некоторый" и т.п. Обозначение x: P(x) читается так: "существует хотя бы один x такой, что P от x". Например, P(x) - предикат: "x - студент", где x - элемент множества жителей Москвы. Тогда выражение x: P(x) есть высказывание "хотя бы один житель Москвы является студентом".

Квантор существования можно рассматривать как обобщение серии дизъюнкций единичных высказываний. Если задано множество M={a 1 , a 2 , ..., a n } и на нем определен предикат P(x), то

P(а 1) P(а 2) ... P(а n) ( x M): P(x).

Кванторы обладают свойствами, являющимися аналогами законов де Моргана:

ù( x: P(х)) х:ù P(х),

ù( х: P(х)) х: ùP(х).

С помощью кванторов можно выражать ряд часто используемых на практике отношений между множествами. Например, высказывание "все объекты х из данного множества, обладающие свойством P(х), обладают также и свойством R(х)" формально можно записать так; х: (P(х) R(х)).

Переход от P(х) к х:P(х) или х:P(х) называется квантификацией или связыванием переменнойх . Связанная переменная фактически не является переменной, т.е. переход от х: P(х) к y:P(y) или от х:P(х) к y: P(y) не меняет истинности выражений. Навешивание переменной на многоместный предикат уменьшает в нем число свободных переменных и превращает его в предикат от меньшего числа переменных.

Рассмотрим пример. На множестве чисел задан двухместный предикат P(х,y)="число х делится на число y". Связывая одну переменную, можно получить следующие одноместные предикаты:

Х: P(х,y) = "каждое число делится на y" - ложь;

X: P(x,y) = "существует число, которое делится на y"- истина;

Y: P(х,y) = "число х делится на любое число" - ложь;

Y: P(х,y) = "существует число на которое делится х" - истина.

Связывая обе переменные данного предиката, получим высказывания:

Х, y:P(х,y)="каждое число делится на любое число" - ложное высказывание,

Х, y:P(х,y)="существует число, на которое делится любое число" - истина, т.к. такое число есть 1,

Х, y:P(х,y)="существует число, которое делится на любое число" - ложное высказывание,

Х, y: P(х,y)="существует число, которое делится на какое-нибудь число" - истинное высказывание.

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

Определение 1: Отрицанием - местного предиката
, определенного на множестве
, называется новый- местный предикат, определенный на том же множестве. Обозначается:
. Читается: «неверно, что
». Предикат
принимает значение «истина» только для тех аргументов, для которых значение предиката
есть «ложь» и наоборот. Другими словами предикат
удовлетворяется теми и только теми аргументами, которые не удовлетворяют данному предикату
.

Двуместный предикат
принимает значение «истина» для тех и только тех значений переменных
из области определения предиката, для которых предикат
принимает значение «ложь», т. е..

Определение 2: Конъюнкцией - местного предиката
, определенного на множестве
, и
- местного предиката
, определенного на множестве
, называется новый
- местный предикат, определенный на множестве
, обозначаемый. Читается: «
и
». Этот предикат принимает значение «истина» только для тех значений аргументов, для которых предикаты
и
одновременно принимают значение «истина».

Если, например,
- двуместный предикат, определённый на множестве
, а
- одноместный предикат, определённый на множестве, то конъюнкция этих предикатов
есть трёхместный предикат, определённый на множестве
. Этот новый предикат принимает значение «истина» для таких троек элементов
,
,
,
, для которых
и
.

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

Пусть
и
– два- местных предиката, зависящих от одних и тех же переменных. Тогда:

а) множество истинности конъюнкции равно пересечению множеств истинности ее членов;

б) множество истинности дизъюнкции равно объединению множеств истинности ее членов.

Не трудно показать, что конъюнкция двух предикатов тождественно истинна тогда и только тогда, когда оба данных предиката тождественно истинны. Дизъюнкция двух предикатов выполнима тогда и только тогда, когда, по крайней мере, один из них выполним. Дизъюнкция двух предикатов тождественно ложна тогда и только тогда, когда оба данных предиката тождественно ложны. Импликация двух - местных предикатов зависящих от одних и тех же аргументов, тождественно истинна тогда и только тогда, когда ее заключение является следствием посылки. Эквивалентность двух- местных предикатов, зависящих от одних и тех же переменных тождественно истинна тогда и только тогда, когда оба предиката равносильны.

Всякое уравнение (неравенство), содержащее переменные, является предикатом, определённым на том же множестве, на котором задано уравнение (неравенство). Множество решений уравнения (неравенства) есть ничто иное, как множество истинности предиката. Это означает, что при подстановке корней уравнения (или решений неравенства) вместо неизвестных будут получены истинные высказывания. Если же в уравнение (неравенство) вместо переменных подставлять числа, не являющиеся решениями, то будут получены ложные высказывания. Всякая система уравнений (неравенств) может быть рассмотрена, как конъюнкция предикатов. Решить систему – значит найти область истинности конъюнкции предикатов. Совокупность уравнений (неравенств) есть ничто иное, как дизъюнкция предикатов. Равносильность уравнений (неравенств) означает равносильность соответствующих предикатов.

Если
, то говорят, что аргумент
удовлетворяет данному предикату. Например, число 3 удовлетворяет предикату
, а число 1 ему не удовлетворяет.

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

Определение 3: Пусть
- одноместный предикат, определенный на непустом множестве

в высказывание:
(читается: «для любоговыполняется
»), называетсяквантором общности (или универсальным высказыванием). Высказывание
истинно тогда и только тогда, когда данный предикат
тождественно истинный (т. е. область истинности предиката
совпадает с множеством
).

Символ называется квантором общности по переменой, его читают: «для всех» или «для каждого». Говорят, что высказывание
есть результат применения квантора общности к предикату
. Символпроисходит от английского слова «All» (в переводе: «все»).

Например, для предикатов «
» и «
», определенных на множестве действительных чисел, соответствующие универсальные высказывания будут иметь вид:
– «каждое действительное число равно самому себе» (истинное) и
– «каждое действительное число больше 2» (ложное).

Теорема 1: Если
- одноместный предикат, определенный на конечном множестве, состоящем из
элементов,,…,, то соответствующее ему универсальное высказывание эквивалентно конъюнкции
высказываний:

Доказательство. В самом деле, согласно определению квантора общности, высказывание

тождественно истинный, т.е. когда истинны все
высказываний, получаемые из данного предиката при замене переменногоаргументами,,…,соответственно. Последнее замечание возможно в том и только том случае, когда истинна конъюнкция этих
высказываний. Т.е. члены эквивалентности одновременно истинны или ложны, а, следовательно, эквивалентность доказана.

Теорема показывает, что для предикатов, определенных на конечном множестве, операция применения квантора общности может быть выражена через конъюнкцию. Для предикатов, определенных на бесконечном множестве, это сделать невозможно, в этом случае операция применения квантора общности является абсолютно новой.

Определение 4: Пусть
- одноместный предикат, определенный на множестве
. Операция, превращающая предикат
в высказывание
(читается: «существует, удовлетворяющее предикату
»), называетсяквантором существования (или экзистенциональным высказыванием). Высказывание
будет истинным тогда и только тогда, когда предикат
выполнимый. Это высказывание будет ложным, если предикат
тождественно ложный.

Символ называется квантором существования по переменной. Его можно прочитать: «существуеттакой, что
», или «найдётся такой, что
». Символпроисходит от английского слова «Exist» (существует).

Теорема 2: Если
– одноместный предикат, определенный на конечном множестве из
элементов,,…,, то соответствующее ему экзистенциональное высказывание эквивалентно дизъюнкции
высказываний:

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

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

Следует запомнить, что для любого предиката
, определенного на множестве
выражения
и
– это высказывания, а не предикаты. Присутствие переменнойздесь чисто внешнее, связанное со способом обозначений. Поэтому переменная, входящая в выражения
и
, называетсясвязанной переменной, в отличие от переменной, входящей в предикат
, где переменная называетсясвободной. Если применить операцию «навешивания» кванторов двуместному предикату
по какой-нибудь переменной, то в результате двуместный предикат превратится в одноместный предикат с одной свободной переменной. Аналогичные рассуждения можно провести для второй переменной. Переменная, по которой был применён квантор, называетсясвязной переменной. Если применить кванторную операцию к - местному предикату по какой-нибудь переменной, то он превратится в
- местный предикат.

Если в любом предикате все переменные связаны, то этот предикат является высказыванием. Например, рассмотрим предикат
, определённый на некотором числовом множестве. Составим высказывание
. Это ложное высказывание, которое утверждает, что найдётся такое число, которое больше всякого числа(- единственное число для всех). Поменяв местами кванторы, получим новое высказывание:
. Это высказывание утверждает, что для любого числаможно подобрать такое число, что выполняется неравенство
(для каждогосуществует своё число). Это высказывание истинно. Видно, что при перестановке кванторов местами меняется смысл высказывания. Таким образом,перестановка разноимённых кванторов местами является недопустимой операцией. Одноимённые кванторы местами менять можно. Причем, одноимённые кванторы можно объединять в один, например: . Недопустимым является также применение нескольких кванторов по одной и той же переменной, например:
.

Определение 5: Универсальным высказыванием , соответствующим - местному предикату
, определенному на множестве

последовательным применениемкванторов общности по переменным
в любом порядке.

Обозначается такое высказывание и читается кратко так: «для всех
выполняется
».

Определение 6: Экзистенциональным высказыванием, соответствующим - местному предикату
, определенному на множестве
, называется высказывание, полученное из
последовательным применениемкванторов существования по переменным
в любом порядке.

Полученное экзистенциональное высказывание обозначают и читают так: «существует такой набор
, что выполняется
».

Например, для двуместного предиката «
» соответствующие высказывания имеют вид:
– «для любых двух действительных чисел: первое больше второго» (ложное), и
– «существуют два действительных числа, из которых первое больше второго» (истинное).

Теорема 3: (Условие тождественной истинности квантифицированного предиката).

‑местный предикат, полученный из ‑ местного предиката
, определенного на множестве
, применением квантора общности по какой–либо переменной является тождественно истинным тогда и только тогда, когда данный предикат
– тождественно истинный.

Доказательство: Действительно, пусть дан
- местный предикат
, определенный на множестве
. По определению, этот предикат будет тождественно истинным тогда и только тогда, когда его значение для произвольно взятых значений аргументов есть «истина». Это значит, что истинным является универсальное высказывание

, определенному на множестве
. Последнее замечание возможно тогда и только тогда, когда предикат
– тождественно истинный, но т.к. аргументы
выбирались произвольно, то это равносильно тождественной истинности данного- местного предиката
. Теорема доказана.

Теорема 4: (Условие тождественной ложности квантифицированного предиката).

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

Доказательство: Пусть имеем
- местный предикат
, определенный на множестве
. Он будет тождественно ложен тогда и только тогда, когда его значение для произвольно взятых аргументов
есть «ложь». Это значит, что ложно экзистенциональное высказывание
, соответствующее одноместному предикату
, определенному на множестве
. Последнее возможно в том и только в том случае, когда предикат
тождественно ложен, а т.к. аргументы
выбирались произвольно, то и данный- местный предикат
тождественно ложен. Что и требовалось доказать.

До сих пор мы противопоставляли предикаты высказываниям. Однако удобнее считать высказывания 0 ‑ местными предикатами. Тогда любые два истинные и любые два ложных высказывания следует считать равносильными между собой.