Кванторы


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


Высказывания «для всех х» (для любого х, для каждого х) называется квантором общности и обозначается Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage618.gifх.


Высказывание «существует х» (для некоторых х, хотя бы для одного х, найдется такое х) называется квантором существования и обозначается Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifх.


Высказывание «существует одно и только одно х» (для единственного значения х) называется квантором единственности : Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gif! х.


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


Для того чтобы получить высказывание из многоместного предиката, надо связать кванторами каждую переменную. Например, если Р(х; у) – двухместный предикат, то (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage618.gifхОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage002.gifХ) (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifуОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage620.gifY) Р(х; у) – высказывание.


Если не каждая переменная связывается квантором, то получается не высказывание, а предикат, зависящий от той переменой, которая не связана квантором. Так, если перед предикатом Р(х; у) поставить квантор Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage618.gifу, то получим предикат (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage618.gifуОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage620.gifY) Р(х; у), зависящий от переменной х.


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


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


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


а) Предложение «Найдется такое х, что х + у = 2» можно записать в виде (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifхОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage002.gifR) х + у = 2. Так как квантором связана только переменная х, то рассматриваемое предложение с двумя переменными является предикатом.


b) Предложение «для любых х и у имеет место х + у = у + х» можно записать в виде: (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage618.gifхОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage002.gifR) (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage618.gifуОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage620.gifR) х + у = у + х, где обе переменные являются связанными. Следовательно, данное предложение является высказыванием.


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


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


Кванторы   (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage618.gifх) (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifх) называются двойственными друг другу.


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


Например: (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifу) (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifх) х + у = 5. Это утверждение имеет тот же смысл, что и (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifх) (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifу) х + у = 5.


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


Например: (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage618.gifх) (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifу)  х<у, т.е. для всякого числа х существует большее число у – истинное высказывание.


Поменяем местами кванторы: (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifх) (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage618.gifу)  x<y – cуществует число у большее любого числа х – ложное высказывание.


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


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


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


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


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


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


Высказывание (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage618.gifх) Р(х) ложно, если можно указать такое значение  аОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage002.gifХ, при котором  Р(х) обращается в ложное высказывание Р(а). Поэтому, для опровержения высказывания с квантором общности достаточно привести пример.


Высказывание (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifх) Р(х) истинно, если можно указать такое значение аОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage002.gifХ, при котором Р(х) обращается в истинное высказывание Р(а). Поэтому, чтобы убедиться в истинности высказывания с квантором существования, достаточно привести пример и таким образом доказать.


Для того чтобы убедиться в ложности высказывания с квантором существования (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifх) Р(х), необходимо убедиться в ложности каждого высказывания Р(хОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage453.gif), Р(хОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage454.gif), …, Р(хОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage621.gif). Если множество Х конечно, то это можно сделать перебором. Если же множество Х бесконечно, то необходимо провести рассуждения в общем виде.


Примеры.


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


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


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


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


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


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


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


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


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


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


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


Отрицанием высказывания с квантором общности (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage618.gifх) Р(х) является высказывание (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifх) Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage590.gif, а отрицанием высказывания с квантором существования (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifх) Р(х) – высказывание (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage618.gifх) Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage590.gif.


Для отрицания высказывания с двумя переменными (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage618.gifх)(Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifу)
 Р(х; у)
используется следующая формула: (Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage619.gifх)(Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage618.gifу) Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage624.gif


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


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


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


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


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


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


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





Просмотров 23418 Комментариев 0
Познавательно:
Скажи свое мнение:
Добавить комментарий
Имя:* E-Mail:*

Вопрос:
1+1=
Ответ:*
Введите два слова, показанных на изображении: *