Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Кванторные операции над предикатами

Кванторные операции над предикатами


Рассмотренные в предыдущей лекции операции над предикатами в определенном смысле аналогичны соответствующим операциям над высказываниями. Специфика природы предикатов позволяет ввести такие операции над ними, которые не имеют аналогов среди операций над высказываниями. Имеются в виду две кванторные операции над предикатами (или операции квантификации) — квантор общности ∀ и квантор существования ∃, о которых и пойдет речь в настоящей лекции.


Квантор общности ∀


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


Определение 20.1. Операцией связывания квантором общности называется правило, по которому каждому одноместному предикату [math]P(x)[/math], определенному на множестве [math]M[/math], сопоставляется высказывание, обозначаемое [math](\forall x)(P(x))[/math] (читается: "для всякого [значения] [math]x\,P(x)[/math] [истинное высказывание]"), которое истинно в том и только в том случае, когда предикат [math]P(x)[/math] тождественно истинен, и ложно в противном случае,


[math]\lambda\bigl[(\forall x)(Px)\bigr]= \begin{cases}1,& \text{if}\quad P(x)~- ~\text{identically true predicate},\\ 0,& \text{if}\quad P(x)~- ~\text{refutable predicate}. \end{cases}[/math]

При чтении высказывания [math](\forall x)(P(x))[/math] слова в квадратных скобках могут опускаться. Высказывание [math](\forall x)(P(x))[/math] называется универсальным высказыванием для предиката [math]P(x)[/math]. Символ [math]\forall[/math] происходит от первой буквы англ. all — "все". Сам символ [math](\forall x)[/math] также называют квантором общности по переменной [math]x[/math].


Например, рассмотрим два одноместных предиката на множестве [math]\mathbb{N}:[/math] "[math]1 \leqslant x[/math]" и "[math]x\mid30[/math]". Первый предикат тождественно истинный, поэтому применение к нему операции связывания квантором общности дает истинное высказывание: [math](\forall x)(1 \leqslant x)[/math] — "для всякого [math]x[/math] число 1 не превосходит [math]x[/math]". Второй предикат опровержим, поэтому операция связывания квантором общности, примененная к нему, дает ложное высказывание: [math](\forall x)(x\mid30)[/math] — "для любого [math]x[/math] число [math]x[/math] является делителем числа 30".


В выражении [math](\forall x)(P(x))[/math] переменная [math]x[/math] уже перестает быть переменной в обычном смысле этого слова, т. е. вместо нее невозможно подставлять какие бы то ни было конкретные значения. Считают, что переменная [math]x[/math] связанная, кажущаяся или немая. Такая ситуация уже встречалась в математике: переменные могут быть связаны не только квантором. Так, связанными являются переменные в следующих выражениях:


[math]\int\limits_{0}^{2}x\,dx\,,\qquad \lim\limits_{n\to +\infty} \frac{1}{n}\,,\qquad \bigl\{x\colon\, x \geqslant 0\bigr\}.[/math]

Это означает, что каждое из приведенных выражений не зависит от связанных переменных, т. е. сущность выражения не изменится, если связанную переменную обозначить любой другой буквой. Так, первое из трех выражений вне зависимости от переменной равно 2, второе равно 0, а третье — действительная полупрямая [math][0;+\infty)[/math]. Аналогично, высказывание [math](\forall x)(1 \leqslant x)[/math] может быть прочитано так: "1 не превосходит всякое натуральное число" — и в таком виде оно вообще не содержит переменных.


Если одноместный предикат [math]P(x)[/math] задан на конечном множестве [math]M=\{a_1,a_2,\ldots,a_n\}[/math], то нетрудно понять, что высказывание [math](\forall x)(P(x))[/math] эквивалентно (имеет то же логическое значение) конъюнкции [math]P(a_1)\land P(a_2)\land \ldots\land P(a_n)[/math]. В самом деле, по определению 20.1 истинность высказывания [math](\forall x)(P(x))[/math] означает, что предикат тождественно истинен, т.е. каждое из высказываний [math]P(a_1), P(a_2), \ldots, P(a_n)[/math], в которые этот предикат превращается, истинно. Последнее равносильно истинности конъюнкции [math]P(a_1)\land P(a_2)\land \ldots\land P(a_n)[/math].


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


Можно подметить еще одну особенность операции связывания квантором общности по сравнению с операциями из предыдущей лекции. Те операции ставили в соответствие одному или двум предикатам новый предикат, а операция связывания квантором общности сопоставляет предикату высказывание. На это можно сказать следующее. Во-первых, каждое высказывание для достижения большей общности сейчас и в дальнейшем можно рассматривать как предикат, содержащий 0 предметных переменных, т. е. как нульместный предикат. Во-вторых, мы пока применяли квантор общности лишь к одноместным предикатам. Переходим к рассмотрению вопроса о применении операции связывания квантором общности к предикатам с любым числом предметных переменных; такая операция предстанет операцией в полном смысле слова: предикатам она будет сопоставлять предикаты.




Определение 20.2. Операцией связывания квантором общности по переменной [math]x_1[/math] называется правило, по которому каждому n-местному [math](n \geqslant 2)[/math] предикату [math]P(x,x_2,\ldots,x_n)[/math], определенному на множествах [math]M_1,M_2,\ldots,M_n[/math], ставится в соответствие новый (n-1)-местный предикат, обозначаемый [math](\forall x)\bigl(P(x,x_2,\ldots,x_n)\bigr)[/math] (читается: "для всех [math]x_1\, P(x,x_2,\ldots,x_n)[/math], который для любых предметов [math]a_2\in M_2,\ldots,a_n\in M_n[/math] превращается в высказывание [math](\forall x_1)\bigl(P(x,a_2,\ldots,a_n)\bigr)[/math], истинное в том и только в том случае, когда одноместный предикат [math]P(x,a_2,\ldots,a_n)[/math], определенный на множестве [math]M_1[/math] тождественно истинен, и ложное в противном случае. Другими словами:


[math]\lambda\bigl[(\forall x_1)\bigl(P(x,a_2,\ldots,a_n)\bigr)\bigr]= \begin{cases}1,& \text{if}\quad P(x,a_2,\ldots,a_n)~ - ~\text{identically true predicate from}~~ x_1,\\ 0,& \text{if}\quad P(x,a_2,\ldots,a_n)~ - ~\text{refutable predicate from}~~ x_1. \end{cases}[/math]

Например, рассмотрим двухместный предикат "[math]y \leqslant x[/math]", определенный на множестве [math]\mathbb{N}^2[/math]. Применим к нему квантор общности по переменной [math]x[/math]. Получим одноместный предикат [math](\forall x)(y \leqslant x)[/math], зависящий от переменной [math]y[/math]. Этот предикат может превратиться как в истинное высказывание (при [math]y=1[/math]), так и в ложное (при подстановке вместо [math]y[/math] любых натуральных чисел, кроме 1).


В другом примере двухместный предикат "[math](x+y)^2=x^2+ 2xy+ y^2[/math]", определенный на [math]\mathbb{R}^2[/math], тождественно истинен. Поэтому применение к нему квантора общности по любой переменной, например по у, дает одноместный предикат (по [math]x[/math]), который будет тождественно истинным [math](\forall y)\bigl((x+y)^2=x^2+2xy+y^2\bigr)[/math].


Заметим в заключение, что к (n-1)-местному предикату [math](\forall x_1)\bigl(P(x_1,x_2,\ldots,x_n)\bigr)[/math], зависящему от переменных [math]x_2,\ldots,x_n[/math], можно снова применить операцию связывания квантором общности по одной из свободных переменных. В результате получится (n-2)-местный предикат и т.д.


Например, применив к одноместному предикату [math](\forall x)(y \leqslant x)[/math], где [math]x,y\in \mathbb{R}[/math], квантор общности по переменной [math]y[/math], получим нуль-местный предикат, т. е. высказывание [math](\forall y)(\forall x)(y \leqslant x)[/math]. Ясно, что полученное высказывание ложно, потому что предикат [math](\forall x)(y \leqslant x)[/math] опровержим. Применив квантор общности по переменной [math]x[/math] к одноместному предикату из второго примера, получим истинное высказывание


[math](\forall y)(\forall x)\bigl((x+y)^2=x^2+2xy+y^2\bigr).[/math]



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


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


Определение 20.3. Операцией связывания квантором существования называется правило, по которому каждому одноместному предикату [math]P(x)[/math], определенному на множестве [math]M[/math], ставится в соответствие высказывание, обозначаемое [math](\exists x)(P(x))[/math] (читается: "существует [значение] [math]x[/math], такое, что [math]P(x)[/math] [истинное высказывание]"), которое ложно в том и только в том случае, когда [math]P(x)[/math] тождественно ложен, и истинно в противном случае, т.е.


[math]\lambda\bigl[(\exists x)(P(x))\bigr]= \begin{cases}0,& \text{if}\quad P(x)~- ~\text{identically true predicate},\\ 1,& \text{if}\quad P(x)~- ~\text{refutable predicate}. \end{cases}[/math]

При чтении высказывания [math](\exists x)(P(x))[/math] слова в квадратных скобках могут опускаться. Высказывание [math](\exists x)(P(x))[/math] называется экзистенциальным высказыванием для предиката [math]P(x)[/math]. Символ [math]\exists[/math] происходит от первой буквы англ. exist — "существовать". Сам символ [math]\exists x[/math] также называют квантором существования по переменной [math]x[/math].


Например, рассмотрим два одноместных предиката, определенных на множестве [math]\mathbb{N}:[/math] "[math]x=x+1[/math]" и "[math]x\mid 30[/math]". Первый предикат тождественно ложный, поэтому применение к нему операции связывания квантором существования дает ложное высказывание: [math](\exists x)(x=x+1)[/math] — "существует натуральное число, равное себе плюс 1". Второй предикат выполним, поэтому операция связывания квантором существования, примененная к нему, дает истинное высказывание: [math](\exists x)(x\mid 30)[/math] — "существует натуральное число, делящее число 30".


Подобно выражению [math](\forall x)(P(x))[/math], в выражении [math](\exists x)(P(x))[/math] переменная [math]x[/math] также перестает быть переменной в обычном смысле слова: это — связанная переменная.


Если одноместный предикат [math]P(x)[/math] задан на конечном множестве [math]M=\{a_1,a_2,\ldots,a_m\}[/math], то высказывание [math](\exists x)(P(x))[/math] эквивалентно (имеет то же логическое значение) дизъюнкции [math]P(a_1)\lor P(a_2)\lor \ldots\lor P(a_m)[/math]. В самом деле, по определению 20.3 ложность высказывания [math](\exists x)(P(x))[/math] означает, что предикат [math]P(x)[/math] тождественно ложен, т.е. каждое из высказываний [math]P(a_1), P(a_2), \ldots, P(a_m)[/math], в которые данный предикат может превратиться, ложно. Последнее равносильно ложности дизъюнкции [math]P(a_1)\lor P(a_2)\lor \ldots\lor P(a_m)[/math].


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


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




Определение 20.4. Операцией связывания квантором существования по переменной [math]x_1[/math] называется правило, по которому каждому n-местному [math](n \geqslant 2)[/math] предикату [math]P(x_1,x_2,\ldots,x_n)[/math], определенному на множествах [math]M_1,M_2,\ldots,M_n[/math], ставится в соответствие новый (n-1)-местный предикат, обозначаемый [math](\exists x_1)\bigl(P(x_1,x_2,\ldots,x_n)\bigr)[/math] (читается: "существует такой [math]x_1[/math] что [math]P(x_1,x_2,\ldots,x_n)[/math], который для любых предметов [math]a_2\in M_2,\ldots,a_n\in M_n[/math] превращается в высказывание [math](\exists x_1) \bigl(P(x_1, a_2, \ldots, a_n)\bigr)[/math], ложное в том и только в том случае, когда одноместный предикат [math]P(x_1, a_2, \ldots, a_n)[/math], определенный на множестве [math]M_1[/math] тождественно ложен, и истинное в противном случае, т.е.


[math]\lambda\bigl[(\exists x_1)\bigl(P(x,a_2,\ldots,a_n)\bigr)\bigr]= \begin{cases}0,& \text{if}\quad P(x,a_2,\ldots,a_n)~ - ~\text{identically true predicate from}~~ x_1,\\ 1,& \text{if}\quad P(x,a_2,\ldots,a_n)~ - ~\text{refutable predicate from}~~ x_1. \end{cases}[/math]

Например, рассмотрим двухместный предикат "[math]y \leqslant x[/math]", определенный на [math]\mathbb{R}^2[/math]. Применим к нему квантор существования по переменной [math]x[/math]. Получим одноместный предикат [math](\exists x)(y \leqslant x)[/math], зависящий от переменной [math]y[/math]. Этот предикат всегда превращается в истинное высказывание, если вместо у подставлять конкретные числа, т.е. он является тождественно истинным предикатом.


В другом примере двухместный предикат "[math]x^2+ y^2<0[/math]", определенный на [math]\mathbb{R}^2[/math], тождественно ложен. Поэтому применение к нему квантора существования по любой переменной, например по [math]x[/math], дает одноместный (по [math]y[/math]) предикат, который будет тождественно ложным: [math](\exists x)(x^2+y^2<0)[/math].


Заметим в заключение, что к (n-1)-местному предикату [math](\exists x_1)\bigl(P(x_1,x_2,\ldots,x_n)\bigr)[/math], зависящему от переменных [math]x_1,x_2,\ldots,x_n[/math], можно снова применить одну из операций квантификации — квантор общности или квантор существования по одной из свободных переменных. В результате получим (n-2)-местные предикаты, например


[math](\forall x_2)(\exists x_1)\big(P(x_1,x_2,\ldots,x_n)\bigr)[/math] и [math](\exists x_2)(\exists x_1)\bigl(P(x_1,x_2,\ldots,x_n)\bigr)[/math].

Так, применив к тождественно истинному одноместному предикату [math](\exists x)(y \leqslant x)[/math], заданному на [math]\mathbb{N}[/math], квантор общности, получим истинное высказывание: [math](\forall y)(\exists x)(y \leqslant x)[/math] — "Для всякого натурального числа существует большее него натуральное число". Применив к тому же одноместному предикату квантор существования, получим также истинное высказывание: [math](\exists y)(\exists x)(y \leqslant x)[/math] — "Существуют два натуральных числа, из которых одно не превосходит другое". Далее, применив к выполнимому одноместному предикату [math](\forall x)(y \leqslant x)[/math], заданному на [math]\mathbb{N}[/math], квантор существования, получим истинное высказывание [math](\exists x)(\forall x)(y \leqslant x)[/math] — "Существует наименьшее натуральное число". Наконец, применив квантор существования к одноместному тождественно ложному предикату [math](\exists x)(x^2+y^2<0)[/math], получим ложное высказывание: [math](\exist y)(\exists x)(x^2+y^2<0)[/math].




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


В математике часто встречаются выражения вида "по меньшей мере [math]n[/math]" ("хотя бы [math]n[/math]"), "не более чем [math]n[/math]", "[math]n[/math] и только [math]n[/math]" ("ровно [math]n[/math]", "точно [math]n[/math]"), где [math]n[/math] — натуральное число. Эти выражения называют численными кванторами. Они имеют чисто логический смысл, потому что их можно выразить без числительных на языке кванторов общности и существования, без логических операций над предикатами и знака [math]=[/math], обозначающего тождество (совпадение) объектов. Рассмотрим ряд случаев.


1) [math]n=1[/math]. Предложение "По меньшей мере один объект обладает свойством [math]P[/math]" имеет тот же смысл, что и предложение "Существует объект, обладающий свойством [math]P[/math]", т.е.


[math](\exists x)(P(x)).[/math]
(1)

Далее, предложение "Не более чем один объект обладает свойством [math]P[/math]" равнозначно по смыслу предложению "Если есть объекты, обладающие свойством [math]P[/math], то они совпадают", т.е.


[math](\forall x)(\forall y)\bigl[\bigl(P(x)\land P(y)\bigr)\to x=y\bigr].[/math]
(2)

Наконец, предложение "Один и только один объект обладает свойством [math]P[/math]" равнозначно конъюнкции высказываний (1) и (2):


[math](\exists x)(P(x))\land (\forall x)(\forall y)\bigl[\bigl(P(x)\land P(y)\bigr)\to x=y\bigr].[/math]
(3)

Сопоставление одноместному предикату [math]P(x)[/math] высказывания (3) носит название операции связывания квантором существования и единственности, а само высказывание (3) иногда обозначают так:


[math](\exists! x)(P(x)).[/math]
(4)

Символ [math]\exists![/math] называют квантором существования и единственности по переменной [math]x[/math].


Например, используя этот квантор, запишем высказывание: "Всякая сходящаяся последовательность имеет точно один предел":


[math]\bigl(\forall\{a_n\}\bigr)\bigl((\exists a)(a=\lim a_n)\to (\exists! a)(a=\lim a_n)\bigr).[/math]

2) [math]n=2[/math]. Предложение "По меньшей мере два объекта обладают свойством [math]P[/math]" означает то же, что и предложение "Существуют два различных объекта, обладающих свойством [math]P[/math]", т.е.


[math](\exists x)(\exists y)\bigl(P(x)\land P(y)\land x\ne y\bigr).[/math]
(5)

Далее, предложение "Не более чем два объекта обладают свойством [math]P[/math]" равнозначно по смыслу предложению "Каковы бы ни были объекты [math]x,y,z[/math], если все они обладают свойством [math]P[/math], то по меньшей мере два из них совпадают", которое символически записывается так:


[math](\forall x)(\forall y)(\forall y)\bigl[\bigl(P(x)\land P(y)\land P(z)\bigr)\to (x=y\lor x=z\lor y=z)\bigr][/math]
(6)

Наконец, предложение "Два и только два объекта обладают свойством [math]P[/math]" совпадает по смыслу с конъюнкцией высказываний (5) и (6).


Совершенно аналогично выражаются через обычные кванторы и логические операции численные кванторы при [math]n>2[/math]. Рекомендуется самостоятельно записать соответствующие выражения для [math]n=3[/math].




Ограниченные кванторы


Нередки в математической практике обороты следующего вида: "Всякий объект, обладающий свойством [math]P[/math], обладает также и свойством [math]Q[/math]" и "Среди объектов, обладающих свойством [math]P[/math], существует объект, обладающий также и свойством [math]Q[/math]". Первое высказывание равнозначно по смыслу высказыванию "Всякий объект, если он обладает свойством [math]P[/math], то он обладает и свойством [math]Q[/math]", которое на языке логики предикатов записывается так:


[math](\forall x)\bigl(P(x)\to Q(x)\bigr).[/math]
(7)

Сопоставление двум данным одноместным предикатам [math]P(x)[/math] и [math]Q(x)[/math] высказывания (7) носит название операции связывания [b]ограниченным квантором общности, а само высказывание (7) иногда обозначают


[math]\bigl(\forall P(x)\bigr)\bigl(Q(x)\bigr).[/math]
(8)

Символ [math]\forall P(x)[/math] также называют ограниченным квантором общности.


Например, высказывание "Для всякого [math]x>1[/math] справедливо [math]\ln{x}>0[/math]" на языке логики предикатов записывается как [math](\forall x)(x>1\to \ln{x}>0)[/math], а с использованием ограниченного квантора общности записывается в виде [math](\forall x>1)(\ln{x}>0)[/math].


Второе из приведенных в начале настоящего пункта высказываний равнозначно по смыслу высказыванию "Существует объект, обладающий свойством [math]P[/math] и обладающий свойством [math]Q[/math]", которое на языке логики предикатов записывается так:


[math](\exists x)\bigl(P(x)\land Q(x)\bigr).[/math]
(9)

Сопоставление двум данным одноместным предикатам [math]P(x)[/math] и [math]Q(x)[/math] высказывания (9) носит название операции связывания ограниченным квантором существования, а само высказывание (9) иногда обозначается


[math]\bigl(\exists P(x)\bigr)\bigl(Q(x)\bigr).[/math]
(8)

Символ [math]\exists P(x)[/math] также называют ограниченным квантором существования.


Например, (ложное) высказывание "Существует действительное число, квадрат которого равен –1" на языке логики предикатов запишется так: [math](\exists x)(x\in \mathbb{R}\land x^2=-1)[/math], или с использованием ограниченного квантора существования запишется в виде [math](\exists x\in \mathbb{R})(x^2=-1)[/math].




Логический квадрат


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


Универсальные высказывания [math](\forall x)\bigl(P(x)\bigr)[/math] и [math](\forall x)\bigl(\lnot P(x)\bigr)[/math], стоящие в двух верхних вершинах квадрата, не могут быть (ни для какого предиката [math]P(x)[/math]) одновременно истинными (хотя конечно же могут быть одновременно ложными). Говорят, что эти высказывания являются противными или контрарными. Экзистенциальные высказывания [math](\exists x)\bigl(P(x)\bigr)[/math] и [math](\exists x)\bigl(\lnot P(x)\bigr)[/math], стоящие в двух нижних вершинах квадрата, наоборот, не могут быть (ни для какого предиката [math]P(x)[/math]) одновременно ложными (хотя конечно же могут быть одновременно истинными). Говорят, что эти высказывания субпротивны (или субконтрарны). Высказывания, стоящие в вершинах каждой диагонали квадрата, противоречат одно другому, т.е. одно является отрицанием другого. Наконец, под каждым из универсальных высказываний, стоящих у верхних вершин, стоит высказывание у нижней вершины, следующее из него, т. е. такое, что импликация этих высказываний (для любого предиката [math]P(x)[/math]) является истинным высказыванием.


В заключение отметим, что кванторы в явном виде впервые были введены немецким математиком Готлобом Фреге в работе "Begriffsschrift" ("Исчисление понятий", 1879). В 1885 г. английский логик Чарльз Пирс ввел термины "квантор", "квантификация", происшедшие соответственно от лат. quantun — "сколько" и лат. quantun + facio — "делать". Это означает, что квантор показывает, о скольких (всех или некоторых) объектах говорится в том или ином предложении. Символику для кванторов в виде перевернутых латинских букв ввел итальянский математик Дж. Пеано в 90-е гг. XIX в. После использования кванторов математиками Пеано, Шредером, Расселом они стали широко использоваться.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved