Рассмотрим предложение
Это предложение не является высказыванием, так как о нем нельзя сказать, истинно оно или ложно. Оно называется предикатом или условием (на х и у). Приведем другие примеры предложений с переменными:
Есть простое число;
Есть четное число;
Меньше у,
Есть общий делитель у, z.
Будем считать, что допустимыми значениями переменных у и z являются натуральные числа. Если в предложениях заменить переменные их допустимыми значениями, то получатся высказывания, которые могут быть как истинными, так и ложными. Например,
2 есть простое число;
3 есть четное число;
5 меньше 7;
3 есть общий делитель 6 и 12.
ОПРЕДЕЛЕНИЕ. Предложения с переменными, дающие высказывания в результате замены свободных переменных их допустимыми значениями, называются предикатами.
Предложения могут служить примерами предикатов.
По числу входящих свободных переменных различают предикаты одноместные, двухместные, трехместные и т. д. Предикаты (2) и (3) - одноместные, предикаты (1) и (4) - двухместные, предикат (5) - трехместный. Высказывания будем считать нульместными предикатами.
Заменяя в одноместном предикате (2) переменную натуральными числами, будем получать высказывания:
0 есть простое число;
1 есть простое число;
2 есть простое число;
3 есть простое число и т. д.
Некоторые из них являются истинными. Таким образом, данный одноместный предикат выделяет среди натуральных чисел те, при подстановке которых вместо переменной получается истинное высказывание, и его можно рассматривать как условие на значения свободной переменной, входящей в предикат. В данном случае числа, удовлетворяющие этому условию, - простые.
Одноместный предикат можно рассматривать как условие на объекты данного вида; двухместный - как условие на пары объектов данного вида и т. д.
Предикаты можно задавать различными способами. В алгебре часто рассматривают предикаты, заданные с помощью уравнений, неравенств, а также систем уравнений или неравенств. Например, неравенство задает одноместный предикат, уравнение - двухместный, а система уравнений - трехместный у, z - рациональные переменные).
Обозначать предикаты будем большими буквами латинского алфавита (возможно, с нижними индексами) с указанием в скобках всех свободных переменных, входящих в этот предикат. Например, - обозначение двухместного предиката, - трехместного и - обозначение -местного предиката.
В дальнейшем мы будем говорить об истинностном значении произвольного предиката на том или ином наборе входящих в него свободных переменных, понимая под этим истинностное значение высказывания, которое получается в результате замены свободных переменных соответствующими им значениями из рассматриваемого набора.
Высказывание, которое получается при подстановке в предикат набора допустимых значений вместо его переменных, будем обозначать Если это высказывание истинное (ложное), говорят, что набор значений удовлетворяет (не удовлетворяет) предикату
п-местный предикат - это функция Р(х 1 х 2 , х п) от п переменных, принимающих значения из некоторых заданных предметных областей, так что,a функция P принимает два логических значения – «истинно» или «ложно».
Таким образом, предикат Р(х 1, х 2, ..., х п) является функцией типа , где множества, называются предметными областями предиката; х 1, х 2, ..., х п -предметными переменными предиката; В = {1,0}.
Соответствия между предикатами, отношениями и функциями:
1. Для любых М и п существует взаимно однозначное соответствие между n -местными отношениями u n-местными предикатами Р(х 1, х 2, ..., х п), :
Каждому n -местному отношению R соответствует предикат Р(х 1, х 2, ..., х п), такой, что Р(a 1, a 2, ...,a п) = 1, если и только если (a 1, a 2, ..., a п) Î R;
Всякий предикат Р(х 1, х 2, ..., х п) определяет отношение R такое, что (a 1, a 2, ..., a п) Î R, если и только если Р(a 1, a 2, ...,a п) = 1.
При этом R задает область истинности предиката Р.
2. Всякой функции f (х 1, х 2, ..., х п) , соответствует предикат Р(х 1, х 2, ..., х п, х п+1)=1такой, что Р(a 1, a 2, ..., a п, a п+1)=1, если и только если f (a 1, a 2, ..., a п)=a n +1 .
Обратное соответствие (от (n+1 )-местного предиката (рис. 2.17) к n -местной функции) возможно не всегда, а только для таких предикатов Р ’ для которых выполняется условие (связанное с требованием однозначности функции): Р(a 1, a 2, ...,a п, a п+1) = 1, то для любого
a ’ п +1 ≠a п +1 Р(a 1, a 2, ...,a п, a ’ п +1) = 0 {1}
Аналогичное соответствие (взаимно однозначное) имеется между подмножеством отношений {R"}{R} и множеством функций {f }.
Для этого класса отношений выполняется аналогичное условие: если (a 1, a 2, ..., a п, a п+1) Î R ’ то для любого a ’ п+1 ≠a п+1 , (a 1, a 2, ..., a п, a п+1)R ’
Выражение Р(a 1, a 2, ...,a п) будем понимать как высказывание «Р(a 1, a 2, ...,a п)=1», а выражение Р(х 1, х 2, ..., х п) - как переменное высказывание, истинность которого определяется подстановкой элементов множества М вместо переменных (х 1, х 2, ..., х п).
Для обозначения двухместных предикатов помимо префиксной записи Р(х 1, х 2) используется нередко инфиксная запись х 1 Рх 2
Каким отношениям и функциям соответствуют следующие предикаты, определенные на множестве натуральных чисел:
1. Предикат тождества E:N 2 →В: Е(а ], а 2) = 1 тогда и только тогда, когда а ]= а 2
Двухместному предикату тождества Е – «x ]= x 2 » взаимно однозначно соответствуют:
а) двухместное отношение R 1 , - «быть равным», , тогда и только тогда, когда Е (a 1 , а 2) = 1;
б) одноместная функция (операция) тождества f 1 (x 1 )=х 2 , а именно:.
2. Предикат делимости D: N 2 →В: D (а ], а 2) = 1 тогда и только тогда, когда а ] делится на а 2:
Двухместному предикату делимости D – «х 1 делится на х 2 » взаимно однозначно соответствует двухместное отношение R 2 – «делиться», тогда и только тогда, когда D (a 1 , а 2) = 1. Однако функции f 1 (x 1 )=х2 для предиката делимости D (x 1 , x 2) не существует, так как не выполнено условие (1), например D(6, 2) = 1 и D(6, 3) = 1, однако 2≠3.
3. Предикат суммы S:N 3 →В: S(а 1, а 2, а 3) = 1 тогда и только тогда, когда а 1 +a 2 = a 3 .
Трехместному предикату суммы S – «x 1 +x 2 =x 3 » взаимно однозначно соответствуют:
а) трехместное отношение: тогда и только тогда, когда S(а 1, а 2, а 3) = 1;
б) двухместная функция (операция арифметики) - сложение f(х 1 , х 2) = х 3 , а именно: х 1 + х 2 = х 3 .
При задании частичного порядка, если пара элементов (a ,b ) принадлежит U , то говорят, что a предшествует b . Если никакой из этих двух элементов другому не предшествует, но говорят, что они не сравнимы.
Условие антисимметричности здесь необходимо для того, чтобы исключить возможность эквивалентных элементов. Условие транзитивности нужно для построения цепочек.
Во многих задачах выбора наилучшего решения нет возможности выбрать решение, которое превосходило бы остальные по всем показателям. В этом случае, мы изучаем частичный порядок, заданный на множестве приемлемых вариантов A , и ограничиваем свой выбор теми вариантами, для которых не существует доминирующего их варианта.
Итальянский экономист Вильфредо Парето (1848-1923) предложил использовать в таких задачах конструкцию, которая в его честь называется границей Парето (Pareto frontier). Мы ее сейчас опишем.
Подмножество PF
множества A
называется его
границей Парето для частичного порядка U
, если
любые два элемента PF
не сравнимы, а любому другому элементу
из A
предшествует какой-либо элемент из PF
.
На рисунке множество A состоит из жирно нарисованных точек на плоскости. Одна точка предшествует другой, если обе ее координаты не меньше соответствующих координат другой, а хотя бы одна из координат строго больше. В этом случае граница Парето состоит из точек, выкрашенных в красный цвет.
Цель семинара:
Рассмотреть практическое применение логики предикатов.
План занятия:
Рассматривается тема логика предикатов на которую отводится 2 часа семинарских занятий.
Задача 1. Каким отношениям и функциям соответствуют следующие предикаты, определённые на множестве натуральных чисел:
1. Предикат тождества Е:N 2 →B:
E(a 1 ,a 2)=1 тогда и только тогда, когда a 1 =a 2 .
2. Предикат порядка Q:N 2 →B:
Q(a 1 ,a 2)=1 тогда и только тогда, когда a 1 ≤ a 2.
3. Предикат делимости D:N 2 →B:
D(a 1 ,a 2)=1 тогда и только тогда, когда a 1 делится на а 2 .
4. Предикат суммы S:N 3 →B:
S(a 1 ,a 2 ,a 3)=1 тогда и только тогда, когда a 1 +a 2 =a 3.
5. Предикат произведения П:N 3 →B:
П(a 1 ,a 2 ,a 3)=1 тогда и только тогда, когда a 1 *a 2 =a 3 .
Решение .
1. Двухместному предикату тождества Е-“x 1 ”=”x 2 ” взаимно однозначно соответствуют:
а) двухместное отношение R 1 – «быть равным», R 1 N 2:(a 1 ,a 2) R 1 тогда и только тогда, когда E(a 1 ,a 2)=1;
б) одноместная функция (операция) тождества f 1 (x 1)=x 2 , а именно: f 1 (x)=x, f:N→N.
2. Двухместному предикату порядка Q-“x 1 ≤ x 2 ” взаимно однозначно соответствует двухместное отношение R 2 - «быть не больше», R 2 N 2:(a 1 ,a 2) R 2 тогда и только тогда, когда Q(a 1 ,a 2)=1.
Однако функции f(x 1)=x 2 для предиката порядка Q(x 1 ,x 2) не существует, так как не выполнено условие Р"(а 1 ,а 2 ,…а n ,а n +1)=0 при одинаковых значениях переменной x 1 существует не единственно значение переменной x 2 , при котором предикат Q истинен. Например, Q(2,4)=1 и Q(2,6)=1, однако 4≠6.
3. Двухместному предикату делимости D-“x 1 делится на х 2 ” взаимно однозначно соответствует двухместное отношение R 3 - “делится”, R 3 N 2:(a 1 ,a 2) R 3 тогда и только тогда, когда D(a 1 ,a 2)=1.
Однако функции f(x 1)=x 2 для предиката делимости D(x 1 ,x 2) не существует, так как не выполнено условие Р"(а 1 ,а 2 ,…а n ,а n +1)=0, например D(6,2)=1 и D(6,3)=1, однако 2≠3.
4. Трехместному предикату суммы S- “х 1 +х 2 =х 3 ” взаимно однозначно соответствуют:
а) трёхместное отношение R 4 N 3: (a 1 ,a 2, a 3) R 4 тогда и только тогда, когда S(a 1 ,a 2 ,a 3)=1;
б) двухместная функция (операция арифметики)- сложение f 2 (x 1 ,x 2), а именно х 1 +х 2 =х 3 .
5. Трёхместному предикату произведения П- “x 1 *x 2 =x 3 ” взаимно однозначно соответствуют:
а) трёхместное отношение R 3 N 3: (a 1 ,a 2, a 3) R 5 тогда и только тогда, когда П (х 1 ,х 2 ,х 3)=1;
б) двухместная функция (операция арифметики)- умножение f 3 (x 1 ,x 2)=x 3 , а именно х 1 *х 2 =х 3.
Взаимная однозначность соответствия между S и f 2 (П и f 3), обусловлена выполнением для предиката S(П) условия Р"(а 1 ,а 2 ,…а n ,а n +1)=0 для каждой системы элементов a 1 ,a 2 N существует единственный элемент а 3 N такой, что S(a 1 ,a 2 ,a 3)=1 (соответственно для П(a 1 ,a 2 ,a 3)=1).
Задача 2. Проиллюстрировать на примере предиката делимости, определённого в задаче 1, понятия переменного высказывания, истинного высказывания, ложного высказывания.
Решение .
Предикат делимости D(x 1 ,x 2)- это переменное (двухместное) высказывание, предметной областью которого могут служить любые множества действительных чисел, например множество N.
D(6,2)- высказывание, значение которого есть истина, т.е. истинное высказывание.
D(5,2)- ложное высказывание.
D(3,х), D(х,2)- переменные (одноместные) высказывания, истинность которых зависит от того, каким числом будет замещён символ x, но D(а,1)- истинное высказывание, так как для любого элемента а N имеет место: D(а,1)=1 (любое натуральное число делится на единицу).
Задача 3. Записать формулой логики предикатов предложение, отражающее транзитивное свойство делимости целых чисел.
Решение .
Составное высказывание (предложении), являющееся формулировкой свойства транзитивности отношения делимости целых чисел.
«если а делится на b и b делится на с, то а делится на с», состоит из трёх простых высказываний D(a,b), D(b,c) и D(a,c). Следовательно, транзитивное свойство делимости можно записать в виде составного высказывания (логической формулы):
«если D(a,b) и D(b,c), то D(a,с) или (D(a,b) & D(b,c)) → D(a,c).
Задача 4. Дать словесные формулировки следующих составных высказываний (предложений):
1. S(a,b,c) & D(a,d) & D(b,d)→D(c,d), где S и D- предикаты суммы и делимости соответственно (см.пример 1);
2. D(a,b) & S(a,b,c);
3. S(a,b,c) ~ S(b,a,c);
4. P 1 ~ P 2 , где P 1 – предикат «число 3n является чётным»; Р 2 - предикат «число n является чётным».
Решение .
1. «Если каждое слагаемое a,b суммы целых чисел делится на некоторое число d, то и сумма с делится на это число»:
S(a,b,c) & D(a,d) & D(b,d)→D(c,d).
2. «Число а не делится на число b, и неверно, что их сумма равна с»: D(a,b) & S(a,b,c).
3. «От перестановки мест слагаемых a и b сумма с не меняется»- свойство коммутативности арифметической операции сложения: S(a,b,c) ~ S(b,a,c).
4. «Число 3n является чётным тогда и только тогда, когда n является чётным»: P 1 ~ P 2.
Эквивалентность может быть выражена и другими словесными формулировками, в том числе:
· «из того, что Р 1 , следует то, что Р 2 , и обратно»;
· «из того, что Р 2 , следует то, что Р 1 , и обратно»;
· «условия Р 1 необходимо и достаточно для того, чтобы Р 2 »;
· «Р 2 необходимо и достаточно, чтобы Р 1 »;
· «Р 1 , если и только если Р 2 »;
· «Р 2 , если и только если Р 1 »;
· «условия Р 1 и Р 2 эквивалентны»;
· «Р 2 тогда и только тогда, когда Р 1 » и др.
Задача 5. Пусть х определён на множестве людей М, а Р(х)- предикат «х-смертен». Дать словесную формулировку предикатной формулы
Решение .
Выражение означает «все люди смертны». Оно не зависит от переменной х, а характеризует всех людей в целом, т.е. выражает суждение относительно всех х множества М.
Задача 6. Пусть Р(х)- предикат «х-чётное число», определённый на множестве М. Дать словесную формулировку высказывания определить его истинность.
Решение .
Исходный предикат Р(х)- «х- чётное число» является переменным высказыванием: при подстановке конкретного числа вместо переменной х он превращается в простое высказывание, являющееся истинным или ложным, например при подстановке числа 5 превращается в высказывание «5-чётное число», являющееся ложным. Высказывание означает «в М существует четное число». Поскольку множество М, на котором задан предикат Р(х), не определено в условии (в таком случае говорят, что задача сформулирована не вполне корректно), доопределим М.
Пусть предикат Р(х) определён на множестве натуральных чисел N, т.е. , тогда высказывание - истинно. В общем случае высказывание истинно на любом множестве М, содержащем хотя бы одно чётное число, и ложно на любом множестве нечетных чисел.
Задача 7. Пусть N(х)- предикат «х-натуральное число». Рассмотреть варианты навешивания кванторов. Проинтерпретировать полученные высказывания и определить их истинность.
Решение .
Высказывание «все числа- натуральные» истинно на любом множестве натуральных чисел и ложно, если М содержит хотя бы одно ненатуральное число, например целое отрицательное;
Высказывание «существует натурально х» истинно на любом множестве М, содержащем хотя бы одно натуральное число, и ложно- в противном случае.
Задача 8. Записать предикатной формулой предложение «Любой человек имеет отца».
Решение .
Для построения предикатной формулы используем два предиката «х- человек» и «у- отец х» и для удобства восприятия обозначим их соответственно: ЧЕЛОВЕК (х) и ОТЕЦ (у). Тогда предложение «Любой человек имеет отца» в предикатной форме имеет вид:
Заметим, что если предикат ОТЕЦ(у,х) определён на множестве людей, то выражение «любой человек имеет отца» можно записать проще:
Задача 9. Пусть предикат Р(х,у) описывает отношение «х любит у» на множестве людей. Рассмотреть все варианты навешивания кванторов на обе переменные. Дать словесную интерпретацию полученных высказываний.
Решение .
Обозначим предикат «х любит у» через ЛЮБИТ (х,у). Предложения, соответствующие различным вариантам навешивания
ЛЮБИТ(х,у)- «для любого человека х существует человек у, которого он любит» или «всякий человек кого-нибудь любит» (рис. а);
ЛЮБИТ (х,у)- «существует такой человек у, что его любят все х» (рис. б)ж
ЛЮБИТ (х,у)- «все люди любят всех людей» (рис. в);
ЛЮБИТ (х,у)- «существует человек, который кого- то любит» (рис. г);
ЛЮБИТ (х,у)- «существует человек, который любит всех людей» (рис. д);
ЛЮБИТ (х,у)- «для всякого человека существует человек, который его любит» (рис. е).
Из приведенного выше можно сделать вывод о том, что перестановка кванторов общности и существования меняет смысл высказывания, т.е. кванторы общности и существования не обладают в общем случае свойством коммутативности.
Задача 10. Пусть Q(x,y)- предикат порядка «х≤у». Рассмотреть различные варианты квантификации его переменных. Определить истинность получаемых выражений для разных случаев интерпретации области определения М предиката, х, у М.
Решение .
Одноместный предикат от у: « для любого х имеет место х≤у». Если М- бесконечное множество неотрицательных целых чисел, то этот предикат ложен; на любом конечном множестве натуральных чисел предикат истинен в единственной точке, представляющей наибольшее число в М. При подстановке любого другого у из М этот предикат обращается в ложное высказывание;
Одноместный предикат от х: «для любого у имеет место х≤у». Если М-множество неотрицательных целых чисел, то этот предикат истинен в единственной точке х=0 и ложен при подстановке вместо х любого числа из М;
Одноместный предикат от у: «существует число в М, которое не больше у». Если М- любое непустое множество чисел, то данный предикат превращается в истинное высказывание при подстановке какого- либо у из М.
Одноместный предикат от х: « существует число в М, которое не меньше х». На любом непустом множестве М чисел данный предикат превращается в истинное высказывание при подстановке какого- либо х из М.
Высказывание « для любых х и у выполняется х≤у» ложно на любом множестве, состоящем более, чем из одного элемента, и истинно на множестве с одним элементом;
Высказывание «существуют такие х и у, что х≤у» истинно на любом непустом множестве;
Высказывание «для любого числа х существует число у, не меньше чем х» истинно на любом непустом множестве;
Высказывание «существует у такой, что для любого х х≤у»утверждает, что в М имеется единственный максимальный элемент;
Высказывание «существует х такой, что он не больше любого у» утверждает, что в М имеется единственный минимальный элемент.
Высказывание «для любого числа у существует число х, не больше, чем у» истинно на любом непустом множестве
Задача 11. Рассмотреть все возможные варианты навешивания кванторов на предикат D(х,у)- «х делится на у», определенный на множестве натуральных чисел N. Дать словесные формулировки полученных высказываний и определить их исьтинность.
Решение .
Операции навешивания кванторов приводят к следующим формулам:
Одноместный предикат «всякое натуральное число из N делится на натуральное число у из N»; истинный только для одного значения свободной переменной у=1;
Переменное высказывание «существует натуральное число, которое делится на у», истинное для любого значения свободной переменной у, взятой из множества N;
Переменное высказывание «натуральное число х делится на всякое натуральное число у», ложное для любого значения свободной переменной х, взятой из N;
Переменное высказывание «существует натуральное число, которое делит натуральное число х», истинное для любого значения свободной переменной х;
Высказывания «для любых двух натуральных чисел имеет место делимость одного на другое» ложные;
Высказывания «существуют такие два натуральных числа, что первое делится на второе», истинны;
Высказывание «существует натуральное число, которое делится на любое натуральное», ложное;
Высказывание « для всякого натурального числа найдется такое натуральное, которое делится на первое», истинное;
Окончательно получим префиксную нормальную форму для исходной предикатной формулы.
Понятие предиката
Определение 1
Предикат - утверждение, которое содержит переменные, принимающие значение $1$ или $0$ (истинно или ложно) в зависимости от значений переменных.
Пример 1
Например, выражение $x=x^5$ является предикатом, т.к. оно является истинным при $x=0$ или $x=1$ и ложным при всех остальных значениях $x$.
Определение 2
Множество, на котором предикат принимает только истинные значения, называется множеством истинности предиката $I_p$.
Предикат называется тождественно-истинным , если на любом наборе аргументов он принимает истинное значение:
$P (x_1, \dots, x_n)=1$
Предикат называется тождественно-ложным , если на любом наборе аргументов он принимает ложное значение:
$P (x_1, \dots, x_0)=0$
Предикат называется выполнимым , если хотя бы на одном наборе аргументов он принимает истинное значение.
Т.к. предикаты могут принимать только два значения (истинно/ложно или $0/1$), то к ним можно применять все операции алгебры логики: отрицание, конъюнкция, дизъюнкция и т.д.
Примеры предикатов
Пусть предикат $R(x, y)$: $«x = y»$ обозначает отношение равенства, где $x$ и $y$ принадлежат множеству целых чисел. В этом случае предикат R будет принимать истинное значение для всех равных $x$ и $y$.
Другой пример предиката -- РАБОТАЕТ($x, y, z$) для отношения «$x$ работает в городе y в компании $z$».
Еще один пример предиката -- НРАВИТСЯ($x, y$) для «x нравится y» для $x$ и $y$, которые принадлежат $M$ -- множеству всех людей.
Таким образом, предикатом является все то, что утверждается или отрицается о субъекте суждения.
Операции над предикатами
Рассмотрим применение операций алгебры логики к предикатам.
Логические операции:
Определение 3
Конъюнкция двух предикатов $A(x)$ и $B(x)$ -- предикат, который принимает истинное значение при тех и только тех значениях $x$ из $T$, при которых каждый из предикатов принимает истинное значение, а ложное значение -- во всех остальных случаях. Множество истинности $T$ предиката -- пересечение множеств истинности предикатов $A(x)$ и $B(x)$. Например: предикат $A(x)$: «$x$ -- чётное число», предикат $B(x)$: «$x$ делится на $5$». Таким образом, предикатом будет выражение «$x$ -- чётное число и делится на $5$» или «$x$ делится на $10$».
Определение 4
Дизъюнкция двух предикатов $A(x)$ и $B(x)$ -- предикат, который принимает ложное значение при тех и только тех значениях $x$ из $T$, при которых каждый из предикатов принимает ложное значение и принимает истинное значение во всех остальных случаях. Множество истинности предиката -- объединение областей истинности предикатов $A(x)$ и $B(x)$.
Определение 5
Отрицание предиката $A(x)$ -- предикат, который принимает истинное значение при всех значениях $x$ из $T$, при которых предикат $A(x)$ принимает ложное значение и наоборот. Множество истинности предиката $A(x)$ -- дополнение $T"$ к множеству $T$ в множестве $x$.
Определение 6
Импликация предикатов $A(x)$ и $B(x)$ -- предикат, который является ложным при тех и только тех значениях $x$ из $T$, при которых $A(x)$ -- истинно, а $B(x)$ -- ложно, и принимает истинное значение во всех остальных случаях. Читается: «Если $A(x)$, то $B(x)$».
Пример 2
Пусть $A(x)$: «Натуральное число $x$ делится на $3$»;
$B(x)$: «Натуральное число $x$ делится на $4$».
Составим предикат: «Если натуральное число $x$ делится на $3$, то оно делится и на $4$».
Множество истинности предиката -- объединение множества истинности предиката $B(x)$ и дополнения к множеству истинности предиката $A(x)$.
Над предикатами помимо логических операций можно выполнять квантовые операции: применение квантора всеобщности, квантора существования и т.д.
Кванторы
Определение 7
Кванторы -- логические операторы, применение которых к предикатам превращает их в ложные или истинные высказывания.
Определение 8
Квантор -- логические операции, которые ограничивают область истинности предиката и создают высказывание.
Чаще всего используют кванторы:
квантор всеобщности (обозначается символом $\forall x$) -- выражение «для всех $x$» («для любого $x$»);
квантор существования (обозначается символом $\exists x$) -- выражение «существует $x$ такое, что... »;
квантор единственности и существования (обозначается $\exists !x$) -- выражение «существует точно одно такое $x$, что... ».
В математической логике существует понятие связывание или квантификация , которые обозначают приписывание квантора к формуле.
Примеры применения кванторов
Пусть -- предикат «$x$ кратно $7$».
С помощью квантора всеобщности можно записать следующие ложные высказывания:
любое натуральное число делится на $7$;
каждое натуральное число делится на $7$;
все натуральные числа делятся на $7$;
который будет иметь вид:
Рисунок 1.
Для записи истинных высказываний используем квантор существования :
существуют натуральные числа, которые делятся на $7$;
найдётся натуральное число, которое делится на $7$;
хотя бы одно натуральное число делится на $7$.
Запись будет иметь вид:
Рисунок 2.
Пусть на множестве $x$ простых чисел задан предикат: «Простое число является нечетным». Поставив перед предикатом слово «любое», получим ложное высказывание: «Любое простое число является нечетным» (например, $2$ является простым четным числом).
Поставим перед предикатом слово «существует» и получим истинное высказывание: «Существует простое число, которое является нечетным» (например, $x=3$).
Таким образом, предикат можно превратить в высказывание, если поставить перед предикатом квантор.
Операции над кванторами
Для построения отрицания высказываний, которые содержат кванторы, применяется правило отрицания кванторов :
Рисунок 3.
Рассмотрим предложения и выделим среди них предикаты, указав область истинности каждого из них.