Лекция 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.

Дата добавления: 2014-01-06