Логические операции над предикатами примеры. Операции над предикатами. Описание математических понятий с помощью логики предикатов. Законы пронесения кванторов через дизъюнкцию

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

Отрицание предиката . Пусть предикат 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)="существует число, которое делится на какое-нибудь число" - истинное высказывание.

ОПРЕДЕЛЕНИЕ 5. ДИЗЪЮНКЦИЕЙ предикатов, заданных на множестве Х, называется предикат А(х) В(х), обращающийся в истинное высказывание при тех и только тех значениях х из множества Х (х Х), при которых хотя бы один из предикатов А(х) и В(х) обращается в истинное высказывание.

Width:="" auto="">

Можно заметить, что множеством истинности дизъюнкции предикатов является объединение множеств ТА и Т В, т. е. Т А В =ТА ТВ. Докажем это предположение.

1). Сначала докажем, что множество Т А В является подмножеством множества ТА ТВ (Т А В ТА ТВ). Пусть x = a – произвольный элемент из множества ТА В, т. е. а ТА В. Следовательно, А(а) В(а) – «и» высказывания. По определению, А(а) В(а) – «и» только тогда, когда А(а) – «и» или В(а) – «и. »

Если А(а) – и, то а ТА, если В(а) - и, то а ТВ. Т. к. А(а) В(а) – и, то а ТА или а ТВ –, это значит, что а ТА ТВ. а - произвольный элемент из ТА В, следовательно, все элементы множества ТА В принадлежат множеству ТА ТВ, т. е. ТА В ТА ТВ, ч. т. д.

2). Докажем, что множество ТА ТВ является подмножеством множества Т А В (ТА ТВ Т А В). Пусть х = в – произвольный элемент из ТА ТВ, в ТА ТВ, по определению, в ТА или в ТВ А(в) – «и» или В(в)- «и» А(в) В В(в)- «и» в ТА В.

Следовательно, если в ТА ТВ, то в ТА В. т. к. Т. К. в – произвольный элемент из ТА ТВ, то ТА ТВ Т А В, ч. т. д.

Из пунктов 1 и 2 по определению равных множеств следует справедливость равенства Т А В = ТА ТВ Заметим, что полученное правило справедливо и для предикатов, содержащих более одной переменной.

ПРИМЕР. Предикаты: А(х)- «х-делитель числа 15» и В(х) - «х –делитель числа 16» . Множество истинности А(х)- ТА ={1, 3, 5, 15 }, множество истинности В(х) -ТВ ={1, 2, 4, 8, 16}. Множество истинности дизъюнкции предикатов Т А В = {1, 2, 3, 4, 5, 8, 15, 16}.

ОПРЕДЕЛЕНИЕ 6. ОТРИЦАНИЕМ предиката А(х), заданного на множестве Х, называется предикат А(х) (« не А(х) »), определенный на том же множестве и истинный при тех и только тех значениях переменной х из множества Х (х Х), при которых предикат А(х) обращается в ложное высказывание.

ПРИМЕР. Предикат А(х)- « х - четное число » . Отрицание предиката: А(х) «х - нечетное число» . Пусть область определения предиката А(х) - Х={х, х N, х

Множество истинности предиката А(х) - все нечетные числа, меньшие 10: ТА = {1, 3, 5, 7, 9}. Из примера видно, что ТА = Х ТА = ТА т. е. множество истинности предиката « не А(х) » является дополнением к множеству истинности предиката А(х). Х = ТА

КВАНТОР – общее название для логических операций, которые по предикату Р(х) строят высказывание, характеризующее область истинности предиката Р(х). В математической логике наиболее употребительны квантор всеобщности (х), квантор существования (х) и квантор единственности существования (! х).

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

Высказывание, полученное из предиката Р(х) при помощи квантора общности, записывается в виде (х Х) Р(х) Высказывание, полученное из предиката Р(х) при помощи квантора существования, записывается в виде (х Х) Р(х) Высказывание «существует одно и только одно х X, для которого истинно Р(х) обозначают (!х X) Р(х)

Для того чтобы получить высказывание из многоместного предиката надо связать кванторами каждую переменную. Например, если Р (х, у) – двухместный предикат, то (х Х)(у Y) Р(х, у) – высказывание. ПРИМЕР. Задан предикат Р(х, у): «х>у» . Для получения высказывания надо связать кванторами обе переменные: например, (Х)(у) х>у или (у)(х) х>у.

ОПРЕДЕЛЕНИЕ ИСТИННОСТИ ВЫСКАЗЫВАНИЯ С КВАНТОРАМИ ИСТИННОСТЬ высказывания с квантором общности устанавливается путем доказательства. Чтобы убедиться в ложности таких высказываний (опровергнуть их) достаточно привести контрпример. .

Истинность высказывания с квантором существования устанавливается при помощи конкретного примера. Для опровержения такого высказывания необходимо провести доказательство. Для чего нужны кванторы?

ВЫВОД. ПРЕДИКАТ обращается в ВЫСКАЗЫВАНИЕ двумя способами: 1). По определению, подставив вместо переменных их конкретные значения из области определения предиката; 2). Связать кванторами переменные, содержащиеся в предикате. Если предикат содержит несколько переменных, необходимо связать квантором каждую переменную.

ПРИМЕР. Пусть дано высказывание А: « Любые четные числа кратны 3» . Высказывание А: « Не любые четные числа кратны 3» или высказывание А: «Неверно, что любые четные числа кратны 3» , другими словами это можно сказать так: «существуют (есть) четные числа не кратные 3» . 8, 10, …

Для построения отрицания высказываний с кванторами надо: 1) квантор общности заменить на квантор существования, а квантор существования на квантор общности; 2) предложение, стоящее после квантора, заменить его отрицанием. (х Х) А(х) = (х Х) А (х) (х Х) А(х) = (х Х)А (х). Таким образом, получаем две равносильности. Или перед данным высказыванием ставят слова: «неверно, что» .

Это правило сохраняется и в том случае, если высказывание содержит не один, а несколько кванторов, например: (х Х)(х Y) А(х, y) = (х Х) (х Y) А (х, y) Для построения отрицания полезны следующие формулы: А(х) В(х) = А(х) В(х) , А(х) В(х)=А(х) В(х)

Рассмотрим два предиката А (х) и В (х). Пусть А (х) – «х: 6» ; В (х) – «х: 3» . Образуем импликацию предикатов «Если х: 6, то х: 3» . Множества истинности предикатов А(х) – ТА= {6, 12, 18, …}; В(х) – ТВ = {3, 6, 9, 12, 15, 18, … }. Из того, что «х: 6» всегда следует, что «х: 3» .

В этом случае говорят, что предикат В(х) логически следует из предиката А(х), а предикаты А(х) и В(х) находятся в отношении логического следования.

В этом случае множество истинности импликации таких предикатов совпадает с ее областью определения Т А В = Х. Отношение логического следования обозначается всегда А(х) => В (х).

Предикат А(х) называют достаточным условием для В(х), а предикат В(х) называют необходимым условием для предиката А(х). Это возможно тогда и только тогда, когда ТА ТВ. .

Src="https://present5.com/presentation/3/-42558499_158059721.pdf-img/-42558499_158059721.pdf-32.jpg" alt="Пример. Предложение «х: 6» => «х: 3» в этом случае читают так: чтобы «х:"> Пример. Предложение «х: 6» => «х: 3» в этом случае читают так: чтобы «х: 3» – достаточно, чтобы «х: 6» , а чтобы «х: 6» необходимо, чтобы «х: 3» .

Src="https://present5.com/presentation/3/-42558499_158059721.pdf-img/-42558499_158059721.pdf-33.jpg" alt="Логическое следование: достат. необход. А(х) => B(x), TА ТВ "> Логическое следование: достат. необход. А(х) => B(x), TА ТВ

Src="https://present5.com/presentation/3/-42558499_158059721.pdf-img/-42558499_158059721.pdf-34.jpg" alt="Пример: Предложение «х: 4» => «х: 2» в этом случае читают так: чтобы «х:"> Пример: Предложение «х: 4» => «х: 2» в этом случае читают так: чтобы «х: 2» – достаточно, чтобы «х: 4» , а для того чтобы «х: 4» необходимо, чтобы «х: 2» .

Если из А(х) следует В(х) и из В(х) следует А(х), то предикаты А(х) и В(х) называют равносильными или эквивалентными и записывают А(х) В(х). Это возможно тогда и только тогда, когда ТА= ТВ.

В этом случае А(х) является необходимым и достаточным условием для В(х), а В(х) – необходимым и достаточным условием для А(х). При этом А(х) => В(х) и В(х) =>А (х). ПРИМЕР. А(х)- «число х делится на 9» , В(х)- «сумма цифр числа х делится на 9» . А(х) В(х)

Теорема –это предложение (утверждение), истинность которого может быть доказана. Теоремы часто формулируются в виде импликаций: если А(х), то В(х) для каждого х, т. е. (х х)А(х) => В(х).

Src="https://present5.com/presentation/3/-42558499_158059721.pdf-img/-42558499_158059721.pdf-39.jpg" alt="(х х)А(х) => В(х). Чаще всего ее записывают так А => В (1)"> (х х)А(х) => В(х). Чаще всего ее записывают так А => В (1) Для всякой теоремы (1) можно сформулировать предложение: «Если В, то А» - обратное данному. Но не всегда это предложение является теоремой.

Пример. «Если углы вертикальные, то они равные» . Обратное предложение: « Если углы равны, то они вертикальные» . или «Если четырехугольник – прямоугольник, то в нем диагонали равны» . Обратное: не верно. Какой пример?

Но если обратное предложение – истинно, то оно наз. обратной теоремой. Например: Т 1: « Если треугольник прямоуг. , то квадрат гипотенузы равен сумме квадратов катетов» Обратное: « Если в треугольнике квадрат одной стороны равен сумме квадратов двух других, то треуг. – прямоуг. » Это -истина, поэтому оно наз. Теоремой, обратной данной.

Если в теореме Для всякой теоремы « Если А, то В» можно сформулировать предложение: « Если не А, то не В» . (если А, то В) Это предложение наз. Противоположным данному. Всегда ли оно будет теоремой? Пример. В том случае, если предложение является теоремой, то его наз. теоремой, противоположной данной. Если

Итак, если для теоремы «Если А, то В» сформулировать предложение, обратное или противоположное ей, то их надо доказывать и только тогда они будут наз. теоремой, обратной или противоположной данной. , если их истинность будет доказана

Для всякой теоремы « Если А, то В» можно сформулировать предложение « Если не В, то не А» «Если В, то А» - обратным противоположному. «Если углы -вертикальные, то они равны» и « если углы не равны, то они и не вертикальные» . Эти предложения всегда истинны, т. е всегда теорема. (А В В А). Эту равносильность наз. законом контрапозиции

Примеры: 1. Если четырехугольник – ромб, то его диагонали взаимно перпедикулярны. 2. Если каждое слагаемое - четное число, то и сумма - четная.

Это предложение наз. Противоположным данному. Всегда ли оно будет теоремой? Пример. В том случае, если предложение является теоремой, то его наз. теоремой, противоположной данной. Итак, если для теоремы «Если А, то В» сформулировать предложение, обратное или противоположное ей, то их надо доказывать и только тогда они будут наз. теоремой, обратной или противоположной данной.

Предикаты так же, как высказывания, могут принимать два значения: “истина” (1) и “ложь” (0), поэтому к ним применимы все операции логики высказываний, в результате чего из элементарных предикатов формируются сложные предикаты (как и в логике высказываний, где из элементарных высказываний формировались сложные, составные). Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов. Эти операции в логике предикатов сохраняют тот же смысл, который был им присвоен в логике высказываний.

Пусть на некотором множестве M определены два предиката P(x) и Q(x).

Определение 1.

Конъюнкцией двух предикатов P(x) и Q(x) называется новый (сложный) предикат , который принимает значение “истина” при тех и только тех значениях , при которых каждый из предикатов принимает значение “истина”, и принимает значение “ложь” во всех остальных случаях.

Очевидно, что областью истинности предиката является общая часть области истинности предикатов P(x) и Q(x), т.е. пересечение .

Так, например, для предикатов P(x): “x – четное число” и Q(x): “x кратно 3” конъюнкцией является предикат “x – четное число и x кратно трем”, т.е. предикат “x делится на 6”.

Определение 2.

Дизъюнкцией двух предикатов P(x) и Q(x) называется новый предикат , который принимает значение “ложь” при тех и только тех значениях , при которых каждый из предикатов принимает значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Ясно, что областью истинности предиката является объединение области истинности предикатов P(x) и Q(x), т.е. .

Определение 3.

Отрицанием предиката P(x) называется новый предикат или , который принимает значение “истина” при всех значениях , при которых предикат P(x) принимает значение “ложь”, и принимает значение “ложь” при тех значениях , при которых предикат P(x) принимает значение “истина”.

Очевидно, что , т.е. множество истинности предиката является дополнением к множеству I P .

Определение 4.

Импликацией предикатов P(x) и Q(x) называется новый предикат , который является ложным при тех и только тех значениях , при которых одновременно P(x) принимает значение “истина”, а Q(x) – значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Поскольку при каждом фиксированном справедлива равносильность , то .

Определение 5.

Эквиваленцией предикатов P(x) и Q(x) называется новый предикат , который обращается в “истину” при всех тех и только тех , при которых P(x) и Q(x) обращаются оба в истинные или оба в ложные высказывания.

Для его множества истинности имеем:

Кванторные операции.

Рассмотрим операции, преобразующие предикаты в высказывания.

Пусть имеется предикат Р(х) определенный на множестве М. Если “а” – некоторый элемент из множества М, то подстановка его вместо х в предикат Р(х) превращает этот предикат в высказывание Р(а). Такое высказывание называют единичным . Например, r(x): “х – четное число” – предикат, а r (6)- истинное высказывание, r (3) – ложное высказывание.

Это же относится и к n – местным предикатам: если вместо всех предметных переменных х i , i= подставить их значения, то получим высказывание.

Наряду с образованием из предикатов высказываний в результате таких подстановок в логике предикатов рассматриваются еще две операции, которые превращают одноместный предикат в высказывание. Эти операции называются операциями квантификации (или просто квантификацией, или связыванием кванторами, или навешиванием кванторов). При этом рассматриваются, соответственно, два типа так называемых кванторов.

1.1 Квантор всеобщности.

Пусть Р(х) – предикат , определенный на множестве М. Под выражением понимают высказывание , истинное, когда Р(х) истинно для каждого элемента х из множества М, и ложное в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение звучит так: “Для всякого х Р(х) истинно ”.

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

1.2 Квантор существования.

Пусть P(x) -предикат определенный на множестве М. Под выражением понимают высказывание , которое является истинным, если существует элемент , для которого P(x) истинно, и ложным – в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение звучит так: “Существует x, при котором P(x) истинно.” Символ называют квантором существования. В высказывании переменная x связана этим квантором (на нее навешен квантор).

Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве М задан двухместный предикат P(x,y). Применение кванторной операции к предикату P(x,y) по переменной x ставит в соответствие двухместному предикату P(x,y) одноместный предикат (или одноместный предикат ), зависящий от переменной y и не зависящий от переменной x. К ним можно применить кванторные операции по переменной y, которые приведут уже к высказываниям следующих видов:

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

Если же хотя бы для одного элемента P(a k)окажется ложным, то ложными будут высказывание и конъюнкция . Следовательно, справедлива равносильность .

Численные кванторы.

В математике часто встречаются выражения вида “по меньшей мере n” (“хотя бы n”), “не более чем n”, “n и только n” (“ровно n”), где n – натуральное число.

Эти выражения, называемые численными кванторами , имеют чисто логический смысл; они могут быть заменены равнозначными выражениями, не содержащими числительных и состоящими только из логических терминов и знака или ~, означающего тождество (совпадение) объектов.

Пусть n=1. Предложение “По меньшей мере один объект обладает свойством P” имеет тот же смысл, что и предложение “Существует объект, обладающий свойством P”, т.е. (*)

Предложение “не более чем один объект обладает свойством P” равнозначно предложению “Если есть объекты, обладающие свойством P, то они совпадают”, т.е. (**) Предложение “один и только один объект обладает свойством P” равнозначно конъюнкции вышеуказанных предложений (*) и (**).

1.3 Отрицание предложений с кванторами.

Известно, что часто для отрицания некоторого предложения достаточно предпослать сказуемому этого предложения отрицательную частицу “не”. Например, отрицанием предложения “Река х впадает в Черное море.” является предложение “ Река х не впадает в Черное море ”. Годится ли этот прием для построения отрицаний предложений с кванторами? Рассмотрим пример.

Статья «Логика-predikatov.ru/logik/»

3.1. Понятие предиката

«Предикат » с английского переводится как сказуемое. Формально предикатом называется функция, аргументами которой могут быть произвольные объекты из некоторого множества, а значения функции «истина» или «ложь». Предикат можно рассматривать как расширение понятия высказывания.

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

3.2. Логика предикатов

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

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

Логика предикатов – это расширение логики высказываний за счет использования предикатов в роли логических функций.

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

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

Определение 1. Одноместным предикатом Р (х ) называется всякая функция одного переменного, в которой аргумент x пробегает значения из некоторого множества M , а функция при этом принимает одно из двух значений: истина или ложь.

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

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

Например, предикат P(x) - « x- простое число» определен на множестве натуральных чисел , а множество I P – это множество всех простых чисел.

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

Определение 3. Двухместным предикатом P (x, у ) называется функция двух переменных х и у , определённая на множестве М =М 1 ×М 2 и принимающая значения из множества {1,0}.

В качестве примеров двухместных предикатов можно назвать предикаты: Q (x, у ) – «х = у » предикат равенства, определённый на множестве R 2 =R ×R ; F (x, у ) – «х || у » прямая х параллельна прямой у , определённый на множестве прямых, лежащих на данной плоскости.

Говорят, что предикат Р (х ) является следствием предиката Q (х ) , если ; и предикаты Р (х ) и Q (х ) равносильны , если .

Пример 1. Среди следующих предложений выделить предикаты и для каждого из них указать область истинности:

х + 5 = 1
при х = 2 выполняется равенство х 2 – 1 = 0
х 2 – 2х + 1 = 0
существует такое число х , что х 3 – 2х + 1 = 0
х + 2 < Зх – 4
однозначное неотрицательное число х кратно 3
(х + 2) – (3х – 4)

Решение . 1) Предложение является одноместным предикатом Р (х ), I P = {– 4};
2) предложение не является предикатом. Это ложное высказывание;
3) предложение является одноместным предикатом Р (х ), I P = {1};
4) предложение не является предикатом. Это истинное высказывание;
5) предложение является одноместным предикатом Р (х ), I P = (3; +∞);
6) предложение является одноместным предикатом Р (х ), I P = {0; 3; 6; 9};
7) предложение не является предикатом;

Пример 2. Изобразить на декартовой плоскости область истинности предиката .

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

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

Предикаты, так же, как высказывания, принимают два значения и и л (1, 0), поэтому к ним применимы все операции логики высказываний.

Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов.

Пусть на некотором множестве М определены два предиката Р (х ) и Q (х ).

Определение 4. Конъюнкцией двух предикатов Р (х ) и Q (х ) называется новый предикат Р (х )&Q (х ), который принимает значение «истина» при тех и только тех значениях , при которых каждый из предикатов Р (х ) и Q (х ) принимает значение «истина» и принимает значение «ложь» во всех остальных случаях. Очевидно, что областью истинности предиката Р (х )&Q (х ) является общая часть областей истинности предикатов Р (х ) и Q (х ), т.е. пересечение .

Так, например, для предикатов Р (х ): «х – четное число» и Q (х ): « х кратно 3» конъюнкцией Р (х )&Q (х ) является предикат «х – четное число и х кратно 3», то есть предикат «х делится на 6».

Определение 5. Дизъюнкцией д вух предикатов Р (х ) и Q (х ) называется новый предикат , который принимает значение «ложь» при тех и только тех значениях , при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Ясно, что областью истинности предиката является объединение областей истинности предикатов Р (х ) и Q (х ), то есть объединение .

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

Определение 7. Импликацией предикатов Р (х ) и Q (х ) называется новый предикат , который является ложным при тех и только тех значениях , при которых одновременно Р (х ) принимает значение «истина», а Q (х ) – значение «ложь» и принимает значение «истина» во всех остальных случаях.

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

Пусть на некотором множестве M определены два предиката P(x) и Q(x).

Определение 1.

Определение 2.

Ясно, что областью истинности предиката является объединение области истинности предикатов P(x) и Q(x), т.е. .

Определение 3.

Очевидно, что , т.е. множество истинности предиката является дополнением к множеству I P .

Определение 4.

Поскольку при каждом фиксированном справедлива равносильность , то .

Определение 5.

Для его множества истинности имеем:

Свободные и связанные переменные. Кванторы всеобщности и существования, их взаимосвязь.

Ква́нтор - общее название для логических операций, ограничивающих область истинности какого-либо предиката и создающих выcказывание. Чаще всего упоминают:
Квантор всеобщности (обозначение: , читается: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…»).
Квантор существования (обозначение: , читается: «существует…» или «найдётся…»).
В математической логике приписывание квантора к формуле называется связыванием или квантификацией.
В многозначных логиках также вводятся и другие кванторы, например, квантор плюральности (квантор Решера) (обозначается перевёрнутой M, читается «для большинства …»).
Содержание [убрать]
1 Примеры
2 Введение в понятие
3 Кванторы в математической логике
3.1 Свободные и связанные переменные
3.2 Операции над кванторами
4 История появления
5 Литература
6 Ссылки
7 Примечания
Примеры[править | править исходный текст]

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

Пусть на множестве простых чисел задан предикат: «Простое число нечётно». Подставим перед этим предикатом слово «любое». Получим ложное высказывание «любое простое число нечётно» (это высказывание ложно, так как 2 - простое чётное число).
Подставив перед данным предикатом слово «существует», получим истинное выcказывание «Существует простое число, являющееся нечётным» (например,).
Таким образом, превратить предикат в высказывание можно, поставив перед предикатом слова («все», «существует» и другие), называемые в логике кванторами.
Кванторы в математической логике[править | править исходный текст]

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

Свободные и связанные переменные[править | править исходный текст]
Множество свободных переменных* формулы F определяется рекурсивно, следующим образом:
Свободные переменные.
Все переменные, входящие в атомарную формулу, являются свободными переменными этой формулы,
свободные переменные формулы F являются свободными переменными формулы F,
переменные, являющиеся свободными для хотя бы одной из формул F или G, являются свободными переменными формулы (F Д G),
все свободные переменные формулы F кроме v являются свободными переменными формулы Kv F.
Замкнутая формула.
Формула без свободных переменных называется замкнутой формулой, или предложением.
Связанная переменная.
Переменная v связана в формуле F, если F содержит вхождение Kv, где K - квантор.
Связанное переименованию
Квантор всеобщности (обозначения: , ∀) - это условие, которое верно для всех обозначенных элементов, в отличие от квантора существования, где условие верно только для каких-то отдельных элементов из указанного множества. Формально говоря, это квантор, используемый для обозначения того, что множество целиком лежит в области истинности указанного предиката. Читается как: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…».
Квантор всеобщности - это попытка формализации обозначения того, что нечто (логическое выражение) истинно для всего, или для любой относящейся к делу сущности. Применяется в предикатной логике и символической логике.
В предикатной логике, квантор существования (экзистенциальный квантификатор) - это предикат свойства или отношения для, по крайней мере, одного элемента области определения. Он обозначается как символ логического оператора ∃ (произносится как «существует» или «для некоторого»). Квантор существования отличается от квантора всеобщности, который утверждает, что свойство или отношение выполняется для всех элементов области.