Лекция 7. Высказывания с кванторами

План:

1. Высказывания с кванторами

2. Отрицание высказываний и высказывательных форм

1. Высказывания с кванторами

В формулировках математических предложений часто встречаются слова: «каждый», «все», «некоторые», «хотя бы один». Например, свойство противоположных сторон прямоугольника формулируется так: «В любом прямоугольнике противоположные стороны равны», а о свойстве натуральных чисел мы говорили, что «некоторые натуральные числа кратны 3». Выясним, каков смысл этих слов и как они используются в математике.

Если задана высказывательная форма, то, чтобы превратить ее в высказывание, достаточно вместо каждой из переменных, входящих в форму, подставить ее значение. Например, если на множестве N натуральных чисел задана высказывательная форма А(х) – «число х кратно 5», то, подставив в нее вместо х число 20, мы получим истинное высказывание «число 20 кратно 5». Если же в эту высказывательную форму подставить вместо х число 17, мы получим ложное высказывание «число 17 кратно 5».

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

Если перед высказывательной формой «число х кратно 5» поставить слово «всякое», то получится предложение «всякое число х кратно 5».Относительно этого предложения можно задать вопрос, истинно оно или ложно. Значит, оно является высказыванием, причем ложным.

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

Запись (∀х.) А(х) означает: «для всякого значения х предложение А(х) – истинное высказывание.». Иногда эту запись дополняют обозначением множества Х, на котором задана высказывательная форма А(х), и тогда предложение можно читать:

а) для всякого х из множества Х истинно А(х);

б) всякий элемент из множества Х обладает свойством А.

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

Запись (∃х) А(х) означает: «существует такое значение х, что А(х) – истинное высказывание». Иногда эту запись дополняют обозначением множества Х, на котором задана высказывательная форма А(х), и тогда предложение (∃х) А(х) можно читать:

а) существует такое х из множества Х, что истинно А(х);

б) хотя бы один элемент х из множества Х обладает свойством А.

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

Итак, если задана одноместная высказывательная форма А(х), то чтобы превратить ее в высказывание, достаточно связать квантором общности или существования содержащуюся в ней переменную. Если же высказывательная форма содержит несколько переменных, то перевести ее в высказывание можно, если связать квантором каждую переменную. Например, если дана высказывательная форма «х > у», то для получения высказывания надо связать квантором обе переменные: например, (∀х) (∃у) х > у или (∃х) (∃у) х > у.

Однако важно уметь не только переходить от высказывательной формы к высказыванию с помощью кванторов, но и распознавать их логическую структуру. Дело в том, что кванторы содержатся в формулировках определений, теорем и других математических предложений, хотя часто только подразумеваются. Например, в формулировке теоремы «Вертикальные углы равны» квантора в явном виде нет, но предполагается, что данное утверждение справедливо для всех вертикальных углов. Записывая коммутативное свойство сложения в виде а + b = b + а, подразумевают, что оно справедливо для любых чисел а и b.

Задача 1. Выявить логическую структуру следующих высказываний:

а) Некоторые нечетные числа делятся на 5.

б) Произведение двух любых последовательных натуральных чисел кратно 2.

в) В прямоугольнике диагонали равны.

Решение: а) (∃х∈Х) х ⋮5; б) (∀х∈ N) х(х+1) ⋮2; в) (∀х∈ Х) А(х).

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

Рассмотрим высказывание с квантором общности - (∀х∈ Х) А(х). Чтобы убедиться в истинности этого высказывания, надо показать, что множество истинности ТА высказывательной формы А(х) совпадает с множеством Х (ТА = Х). Чтобы убедиться в ложности высказывания (∀х∈ Х) А(х), достаточно показать, что ТА ≠ Х, т.е. показать, что существует такое значение х ∈ Х, при котором высказывательная форма обращается в ложное высказывание.

Задача 2. Установить, истинны или ложны следующие высказывания:

а) Для каждого х из множества {0, 1, 4} значение выражения (4 –х):( 2х + 1) есть число целое.

б) Произведение двух любых последовательных натуральных чисел кратно 2.

в) Всякое натуральное число делится на 5.

Решение.

а) Путем перебора всех возможных случаев установлено, что при заданных значениях х выражение принимает целое значение, т.е. высказывание истинное.

б) Высказывание истинно.

в) Высказывание ложно. Для этого достаточно привести хотя бы один пример.

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

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

Задача 3. Установить, истинны или ложны следующие высказывания:

а) Среди треугольников есть прямоугольные.

б) Некоторые прямоугольные треугольники являются равносторонними.

а) Высказывание истинное.

б) Высказывание ложное.

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

1. Отрицание высказываний и высказывательных форм

Пусть предложение А – высказывание. Если перед сказуемым данного предложения поставить частицу «не» либо перед всем предложением поставить слова «неверно, что», то получится новое предложение, которое называется отрицанием данного и обозначается Ā (читают: «не А» или «неверно, что А).

Определение. Отрицанием высказывания А называется высказывание Ā, которое ложно, когда высказывание А истинно, и истинно, когда высказывание А – ложно.

Таблица истинности отрицания имеет вид:

Из данного определения следует, что предложение и его отрицание не могут быть ни одновременно истинны, ни одновременно ложны.

Построим отрицание ложного высказывания «число 28 делится на 9:

А) Число 28 не делится на 9.

Б) Неверно, что число 28 делится на 9.

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

Рассмотрим теперь правила построения отрицания конъюнкции и дизъюнкции высказываний. Если перед всем составным высказыванием поставим слова «неверно, что», то, безусловно, получим его отрицание. А как быть с частицей «не»? Можно ли поставить перед сказуемым составного предложения и получить его отрицание? На примере можно показать, что нельзя.

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

А	В	А∧В	А∧В	А	В	А∨ В
и	и	и	л	л	л	л
и	л	л	и	л	и	и
л	и	л	и	и	л	и
л	л	л	и	и	и	и

Про высказывания вида А∧В и А∨ В говорят, что они равносильны, и пишут

А∧В ⇔ А ∨ В.

Аналогично можно доказать, что имеет место равносильность

А∨В ⇔ А ∧ В.

Эти равносильности носят название законов де Моргана.

Из них вытекает следующее правило построения отрицания конъюнкции и дизъюнкции: чтобы построить отрицание конъюнкции (дизъюнкции), достаточно заменить отрицаниями составляющие ее высказывания, а союз «и» («или») заменить союзом «или» («и).

Задача 1. Построить отрицание высказывания «число 28 делится на 9 или на 6».

1 способ: «неверно, что число 28 делится на 9 или на 6».

2 способ: воспользуемся законом де Моргана: «число 28 не делится на 9 и не делится на 6».

Как быть, если высказывания содержат кванторы? Строить отрицания высказываний при помощи частицы «не» перед сказуемым нельзя. Остается другой путь – перед всем предложением ставим слова «неверно, что». Например, дано высказывание всякий прямоугольный треугольник является равнобедренным». Его отрицанием будет высказывание «неверно, что всякий прямоугольный треугольник является равнобедренным». Это предложение имеет тот же смысл, что и предложение «некоторые прямоугольные треугольники не являются равнобедренными».

Отрицанием высказывания «некоторые прямоугольные треугольники не являются равнобедренными» является высказывание «неверно, что некоторые прямоугольные треугольники не являются равнобедренными», которое имеет тот же смысл, что и предложение «все прямоугольные треугольники не являются равнобедренными».

Вообще, если дано предложение ∀(х) А(х), то его отрицанием будут предложения

(∀х) А(х) и (∃х) А(х), имеющие один и тот же смысл (и одно и то же значение истинности).

Если дано предложение (∃х) А(х), то его отрицанием будут предложения (∃х) А(х) и

(∀х) А(х), также имеющие один и тот же смысл (и одно и то же значение истинности).

Получаем две равносильности:

(∀х) А(х) ⇔ (∃х) А(х);

(∃х) А(х) ⇔ (∀х) А(х),

Из них вытекает правило: для того чтобы построить отрицание высказывания, начинающегося с квантора общности (существования), достаточно заменить его кантором существования (общности) и построить отрицание предложения, стоящего после квантора.

Задача 2. Построить отрицание высказывания «некоторые однозначные числа делятся на 10».

1) «неверно, что некоторые однозначные числа делятся на 10»

2) «все однозначные числа не делятся на 10».

Последнее, о чем пойдет речь, - это отрицание высказывательных форм.

Пусть на множестве Х задана высказывательная форма А(х). Ее отрицание

обозначим А(х) (читают: «не А(х) или неверно, что А(х)». Предложение А(х) будет обращаться в истинное высказывание лишь при тех значениях х из множества Х, при которых А(х) – ложно. Таким образом, Т Ā = Т´ А – множество истинности предложения

А(х), а Т ´ А – дополнение множества Т А до множества Х.

Доказательство этого равенства мы опускаем.

Пусть, например, на множестве натуральных чисел задана высказывательная форма А(х) – «число х кратно 5». Тогда ее отрицанием будет предложение «число х не кратно 5» (или «неверно, что число х кратно 5»), истинное при всех значениях х, которые не кратны 5.

Лекция 8. Теоремы

План:

1. Отношения следования и равносильности между предложениями

2. Структура теоремы. Виды теорем

3. Необходимые и достаточные условия. Рассуждения от противного. Правильные и неправильные рассуждения.

4. Основные выводы

1. Отношения следования и равносильности между предложениями

Рассмотрим две высказывательные формы: «число х кратно 4» и «число х кратно 2», заданные на множестве N натуральных чисел.

Как связаны между собой эти два предложения?

Можно сказать так: из того, что число х кратно 4, следует, что х кратно 2. Это мы можем утверждать, потому что знаем – при всех значениях х, при которых истинно предложение «число х кратно 4», будет истинно и предложение «число х кратно 2». В этом случае говорят, что данные предложения находятся в отношении логического следования.

Определение. Высказывательная форма В(х) следует из высказывательной формы А(х), если В(х) обращается в истинное высказывание при всех тех значениях х, при которых А(х) истинна.

Если А и В – высказывания, тогда говорят, что из А следует В, если всякий раз, когда А истинно, истинно и В.

Для обозначения отношения логического следования используется знак ⇒. Соединяя две высказывательные формы А(х) и В(х) таким знаком, мы получаем высказывание А(х) ⇒ В(х), прочитать которое можно по разному:

1) Из А(х) следует В(х).

2) Всякое А(х) есть В(х).

3) Если А(х), то В(х).

4) В(х) есть следствие А(х).

5) А(х) есть достаточное условие для В(х).

6) В(х) есть необходимое условие для А(х).

Например, утверждение о том, что из предложения «число х кратно 4», следует предложение «число х кратно 2», можно сформулировать еще так:

- Всякое число, которое кратно 4, кратно и 2.

- Если число кратно 4, то оно кратно и 2.

- Кратность число 2 есть следствие кратности его 4.

- Кратность числа 4 есть достаточное условие для его кратности 2.

- Кратность числа 2 есть необходимое условие для его кратности 4.

Последние два предложения часто формулируют в следующей форме:

- Для того чтобы число было кратно 2, достаточно, чтобы оно было кратно 4.

- Для того чтобы число было кратно 4, необходимо, чтобы оно было кратно 2

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

Задача 1. Данные предложения переформулируйте, используя различные способы прочтения утверждения А(х) ⇒ В(х):

Всякий квадрат является прямоугольником.

Решение.

А(х) – «четырехугольник – квадрат» и В(х) – «четырехугольник – прямоугольник».

1) Из того, что четырехугольник – квадрат, следует, что он прямоугольник.

2) Если четырехугольник – квадрат, то он прямоугольник

3) Четырехугольник является прямоугольником – это следствие того, что четырехугольник – квадрат.

4) Для того чтобы четырехугольник был прямоугольником, достаточно, чтобы он был квадратом.

5) Для того чтобы четырехугольник был квадратом, необходимо, чтобы он был прямоугольником.

Как и любое высказывание, предложение А(х) ⇒ В(х) может быть истинным или ложным. Но так как оно может быть сформулировано в виде «всякое А(х) есть В(х)», то его истинность устанавливается путем доказательства, а с помощью контрпримера – что оно ложно.

Определение. Предложения А(х) и В(х) равносильны, если из предложения А(х) следует предложение В(х), а из предложения В(х) следует предложение А(х).

Для обозначения отношения равносильности используется знак ⇔. Соединяя две высказывательные формы А(х) и В(х) таким знаком, мы получаем высказывание А(х) ⇔ В(х), прочитать которое можно по-разному:

1) А(х) равносильно В(х).

2) А(х) тогда и только тогда, когда В(х).

3) А(х) – необходимо и достаточное условие для В(х).

4) В(х) - необходимое и достаточное условие для А(х).

Например, утверждение о том, что предложение «число делится на 3» и «сумма цифр в записи числа делится на 3» равносильны, можно сформулировать еще так:

- Число делится на 3 тогда и только тогда, когда сумма цифр в его записи делится на 3.

- Для того чтобы число делилось на 3, необходимо и достаточно, чтобы сумма цифр в его записи делилась на 3.

С теоретико-множественной точки зрения высказывание А(х) ⇔ В(х) означает, что если ТА – множество истинности высказывательной формы А(х), а ТВ – множество истинности высказывательной формы В(х), то ТА = ТВ.

Например, уравнения 3х(х-2) = 0 и 3х(х-2)(х+3) = 0 равносильны на множестве целых неотрицательных чисел, потому что множество их решений {0, 2}.

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

Отметим также, что знак ⇔ мы использовали раньше, в частности, рассматривая логическую структуру явных определений понятий. Мы установили, что ее можно представить в виде а⇔ в. Определение порождает два равносильных предложения.

Знак ⇔ используют в записи правил построения отрицания высказываний. Например, А∧В⇔ А∨В. В этом случае речь идет о равносильности высказываний определенной формы. При этом считают, что предложения равносильны, если они одновременно истинны, либо одновременно ложны. Другими словами, если их значения истинности совпадают при одинаковых наборах значений высказываний А и В.

1. Структура теоремы. Виды теорем.

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

Теорема– это высказывание, истинность которого устанавливается посредством рассуждения (доказательства).

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

Например, условием теоремы «если четырехугольник является прямоугольником, то в нем диагонали раны» является предложение «четырехугольник – прямоугольник, а заключением – предложение «в таком четырехугольнике диагонали равны».

В рассмотренном примере теорема была сформулирована с помощью слов «если …, то …». Но, как нам известно, утверждение А ⇒ В можно сформулировать и по-другому. Например, рассмотренную теорему можно сформулировать так: «во всяком прямоугольнике диагонали равны» или «для того, чтобы четырехугольник был прямоугольником, необходимо, чтобы его диагонали были равны». Есть и другие способы, но удобнее теорему формулировать в виде «если …, то …», поскольку сразу видно ее условие (что дано) и заключение (что надо доказать).

В математике кроме теорем используются предложения, называемые правилами и формулами. Выясним, чем они отличаются от теоремы.

Рассмотрим, например, такую теорему из школьного курса алгебры: «если а – любое число и k, n – натуральные число, то справедливо равенство аⁿ•аʰ = аⁿ⁺ʰ». Для того чтобы этой теоремой удобнее было пользоваться, при выполнении различных преобразований ее формулируют в виде правила: «при умножении степеней с одинаковыми основаниями показатели складываются» или записывают только формулу.

Учитель должен уметь разворачивать изучаемые в начальной школе правила (формулы) и формулировать соответствующие им теоремы. Например, правило деления суммы на число: «для того чтобы разделить сумму на число, можно разделить на это число каждое из слагаемых и полученные результаты сложить». К этой формулировке иногда добавляют формулу: (а + b): с = а : с + b: с. Так как этот материал изучают в начальной школе, то надо отчетливо понимать, что числа могут быть только целыми неотрицательными, причем с ≠ 0. Кроме того, воспользоваться правой частью этого равенства можно при условии, что а кратно с и b кратно с.

Для всякой теоремы вида «если А, то В» можно сформулировать предложение «если В, то А», которое называют обратным данному. Однако не всегда это предложение является теоремой. Рассмотрим, например, теорему: «если четырехугольник является прямоугольником, то в нем диагонали равны». Построим предложение, обратное данному: «если в четырехугольнике диагонали равны, то четырехугольник является прямоугольником». Это высказывание ложное, в чем можно убедиться, приведя контрпример: в равнобедренной трапеции диагонали равны, но трапеция не является прямоугольником.

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

Для всякой теоремы вида «если А, то В» можно сформулировать предложение «если не А, то не В», которое называют противоположным. Но не всегда это предложение является теоремой. Например, предложение, противоположное теореме «если четырехугольник является прямоугольником, то в нем диагонали равны», будет ложным: «если четырехугольник не является прямоугольником, то в нем диагонали не равны».

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

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

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

Вообще для какой бы теоремы мы ни формулировали предложение, обратное противоположному, оно всегда будет теоремой, потому что имеется следующая равносильность: (А ⇒ В) ⇔ (В ⇒А).

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

Кроме того, из закона контрапозиции следует, что предложение, обратное данному, и предложение, противоположное данному, одновременно истинны либо одновременно ложны. Поэтому, рассматривая их, достаточно доказать (или опровергнуть) какое-нибудь одно; тем самым будет доказано (опровергнуто) другое.

Заметим, что если для данной теоремы А ⇒ В существует обратная В ⇒А, то их можно соединить в одну А ⇔ В, и тогда в формулировке будут использованы слова «необходимо и достаточно», «тогда и только тогда, когда». Например: «треугольник будет равнобедренным тогда и только тогда, когда в нем углы при основании равны».

С другой стороны, если теорема имеет вид А ⇔ В, то это значит, что она состоит из двух взаимно обратных теорем А ⇒ В и В ⇒А и, следовательно, ее доказательство сводится к доказательству двух указанных теорем.

Заметим также, что если условие или заключение данной теоремы представляет собой конъюнкцию или дизъюнкцию, то, чтобы получить предложение, противоположное данному, нужно учитывать правила построения отрицания конъюнкции или дизъюнкции. Например, дана теорема «если число делится на 3 и 4, то оно делится на 12». Предложение, противоположное данному, можно сформулировать так: «если число не делится на 12, то оно не делится на 3 или не делится на 4».

1. Основные выводы

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