Кванторы

 Кроме известных нам логических операций для предикатов  вводятся две новые: операция навешивания кванторов существования и общности.

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

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

Высказывание «существует одно и только одно х» (для единственного значения х) называется квантором единственности : ! х.

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

Для того чтобы получить высказывание из многоместного предиката, надо связать кванторами каждую переменную. Например, если Р(х; у) – двухместный предикат, то (хХ) (уY) Р(х; у) – высказывание.

Если не каждая переменная связывается квантором, то получается не высказывание, а предикат, зависящий от той переменой, которая не связана квантором. Так, если перед предикатом Р(х; у) поставить квантор у, то получим предикат (уY) Р(х; у), зависящий от переменной х.

Выясним, какие из следующих предложений являются высказываниями, а какие предикатами: а) найдется такое х, что х+ у = 2;

b)  для любых х и у имеет место равенство х + у = у + х.

Решение:  Выявим логическую структуру данных предложений.

а) Предложение «Найдется такое х, что х + у = 2» можно записать в виде (хR) х + у = 2. Так как квантором связана только переменная х, то рассматриваемое предложение с двумя переменными является предикатом.

b) Предложение «для любых х и у имеет место х + у = у + х» можно записать в виде: (хR) (уR) х + у = у + х, где обе переменные являются связанными. Следовательно, данное предложение является высказыванием.

Если какое-либо предметное переменное в формуле не связано квантором, то его называют свободным переменным.

Например: (х) ху=ух. Здесь переменное у не связано каким-либо квантором, поэтому оно свободно. От него не зависит истинность данного высказывания.

Кванторы   (х) (х) называются двойственными друг другу.

Одноименные кванторы можно менять местами, что не влияет на истинность высказывания.

Например: (у) (х) х + у = 5. Это утверждение имеет тот же смысл, что и (х) (у) х + у = 5.

Для разноименных кванторов изменение порядка может привести к изменению истинности высказывания.

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

Поменяем местами кванторы: (х) (у)  x<y – cуществует число у большее любого числа х – ложное высказывание.

В связи с введением кванторов необходимо учесть следующее:

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

2. Одно и то же переменное не может находиться в области двойственных друг другу кванторов.

Нарушение этих условий называют коллизией переменных.

Как устанавливается значение истинности высказывания с квантором?

Для доказательства утверждения с квантором общности необходимо убедиться в том, что при подстановке каждого из значений х в предикат Р(х) последний обращается в истинное высказывание. Если множество  Х конечно, то это можно сделать путем перебора всех случаев; если же множество Х бесконечно, то необходимо провести рассуждения в общем виде.

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

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

Для того чтобы убедиться в ложности высказывания с квантором существования (х) Р(х), необходимо убедиться в ложности каждого высказывания Р(х), Р(х), …, Р(х). Если множество Х конечно, то это можно сделать перебором. Если же множество Х бесконечно, то необходимо провести рассуждения в общем виде.

Примеры.

1. Найти значение истинности высказывания «среди чисел  1, 2, 3, 4 найдется простое число».

Решение: Высказывание содержит квантор существования и поэтому может быть представлено в виде дизъюнкции высказываний: «1 – простое  число» или «2 – простое число» или «3 – простое число» или «4 – простое число». Для доказательства истинности дизъюнкции достаточно истинности хотя бы одного высказывания, например, «3 – простое число», которое истинно. Следовательно, истинно и исходное высказывание.

2. Докажем, что любой квадрат является прямоугольником.

Решение: Высказывание содержит квантор общности. Поэтому оно может быть представлено в виде конъюнкции: «квадрат – прямоугольник» и «квадрат – прямоугольник» и «квадрат – прямоугольник» и т.д. Так как все эти высказывания истинны, то истинна конъюнкция этих высказываний, следовательно, истинно и исходное предложение.

3. «Любой треугольник равнобедренный». Это ложное высказывание. Чтобы убедиться в этом, достаточно начертить треугольник, не являющийся равнобедренным.

       Таким образом, мы

опровергли высказывание                                                                  

контрпримером.                                                                               

4. Определим истинность высказывания «Существуют равносторонние прямоугольные треугольники».

Решение:  Высказывание ложно. Действительно, в прямоугольном треугольнике один угол равен 90º. А в равностороннем треугольнике все углы по 60º. Следовательно, среди равносторонних треугольников нет прямоугольных.

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

Отрицанием высказывания с квантором общности (х) Р(х) является высказывание (х) , а отрицанием высказывания с квантором существования (х) Р(х) – высказывание (х) .

Для отрицания высказывания с двумя переменными (х)(у)
 Р(х; у)используется следующая формула: (х)(у)

Для построения отрицания высказывания с кванторами надо:

1)    квантор общности заменить квантором существования, а квантор существования – квантором общности;

2)    предикат заменить его отрицанием.

Пример. Сформулируем отрицание для следующих высказываний:

а) все элементы множества Z четные; b) некоторые глаголы отвечают на вопрос «что делать?».

Решение: а) Заменим квантор общности  квантором существования, а высказывание его отрицанием: некоторые элементы множества Z нечетные.

b) Заменим квантор существования квантором общности, а выражение его отрицанием: все глаголы не отвечают на вопрос «что делать?».