и, значит,
a1(m) =b1, a2(m) =b2 , ... a(nm) =bn , ...
(т. к. (1.3.2) и (1.3.3) — одно и то же число). В частности am(m) =bm ,
что невозможно, поскольку мы выбирали bm так, чтобы bm ≠am(m).
Противоречие показывает, что любое «занумерование» чисел из (0; 1) не покрывает весь интервал, там остается еще что-то. Теорема доказана.
Мощность множества действительных чисел интервала (0; 1) называется мощностью континуума. Обозначение этой мощности — с. Это следующая за α0 мощность (есть ли множества мощности с*:
α0 < c* < c доказать пока не удалось). Существуют и более «сильные» мощности и их бесконечное количество.
ÉãÄÇÄ 2. ùгЦеЦзнх ДгЙЦЕкх гйЙада
§ 1. Высказывания и высказывательные формы
Предложением мы будем называть любое соединение слов, имеющее самостоятельный смысл. Например:
a) Стой!; b) Прекрасная погода, не так ли?; c) 3 > 1;
d) Всякий прямоугольник есть квадрат; e) Если a > b, то b < a.
Высказыванием называется предложение, относительно которого имеет смысл говорить, что оно истинно или ложно.
В примере, рассмотренном выше, первые два предложения высказываниями не являются.
Каждому высказыванию придадим значение истинности: И (истина), если это истинное высказывание, и Л (ложь), если это ложное высказывание. Ввиду того, что нас будет интересовать не содержание высказывания, а значение его истинности, высказывания
(c) и (e), хотя и различного содержания, для нас будут тождественны, т. к. каждое из них имеет значение И.
— 16 —
Часто встречаются предложения, содержащие одну или не-
сколько переменных:
a) x > 2; b) x2 + 3 = 4x; c) x + y2 = 20; d) x R и т. п.
Эти предложения становятся высказываниями, если вместо переменных подставить какие-нибудь значения. Например, если в (b) подставить x = 1 или x = 3, то получится истинное высказывание, во всех прочих случаях — высказывание ложное.
Предложение, содержащее хотя бы одну переменную и становящееся высказыванием при подстановке вместо переменной ее значения, называется высказывательной формой.
Каждая переменная, входящая в высказывательную форму, имеет некую область значений. Например, в приведенных выше примерах, область значений — множество R, а в высказывательной форме «x — столица России» буква x означает название населенного пункта.
§ 2. Виды высказываний
Высказывания § 1 рассматриваются как элементарные, т. е. не расчленяемые высказывания. Примерами сложных высказываний, расчленяющихся на элементарные, являются, к примеру, следующие:
a)это число целое и это число положительное;
b)данный четырехугольник — ромб или (данный четырехугольник) прямоугольник;
c)данное число является рациональным или (данное число) не является рациональным;
d)если треугольник равносторонний, то он равнобедренный;
e)если люди разумны и (они) сознают опасность войны, то они борются за мир;
f)ab = 0 тогда и только тогда, когда a = 0 или b = 0 и т. п.
Здесь простые высказывания определенным образом соединены
словами «и», «или», «не», «если..., то», «тогда и только тогда, когда». Эти слова обозначают логические операции (связки), которые производятся над простыми высказываниями. Совокупность и по-
— 17 —
рядок логических операций составляют логическую структуру сложного высказывания.
Высказывания различного содержания могут иметь одинаковую логическую структуру. К примеру, высказывание (a) и высказывание (h) «если число делится на 2 и делится на 3, то оно делится на 6», хотя и совершенно различного содержания, имеют одинаковую структуру. Если обозначить простые высказывания какими-нибудь буквами, то логическая структура сложного высказывания станет легко различимой.
Пусть p — «люди разумны», q — «люди сознают опасность войны», r — «люди борются за мир». Тогда (e) имеет вид «если
pи q, то r».
Сдругой стороны, часто встречаются сложные высказывания об одних и тех же вещах, но различной структуры. Рассмотрим вы-
сказывание (h) и высказывание (h') «если число делится на 2 и не
делится на 6, то оно не делится на 3». Структура высказывания (h') записывается так:
«если p и не r, то не q».
Структуры (h) и (h') различны, но они связаны так, что оба этих сложных высказывания имеют одно и то же значение истинности при любых наборах значений истинности составляющих высказываний p, q и r (в частности для конкретных значений, рассмотрен-
ных выше, значения (h) и (h') истинны).
Те же рассуждения можно провести для высказывания (e),
сконструировав высказывание (e').
Значит, если истинность (или ложность) высказывания типа (h) установлена, то тем самым установлена истинность (или ложность)
высказывания типа (h').
Важно уметь находить значение сложного высказывания по заданным значениям его элементарных составляющих. Для этого нужно точно знать определения логических операций (связок), с помощью которых сложное высказывание образовано из элементарных.
— 18 —
§ 3. Логические операции
Операции, выполняемые над высказываниями и порождающие новые высказывания, называются логическими операциями.
3.1.Отрицание
Вобыденной речи мы часто пользуемся словом «не», или словами «неверно, что», когда хотим что-то отрицать. Например, мы хотим отрицать, что
a) «Треугольник ABC — равнобедренный», мы говорим:
b) «Треугольник ABC — не равнобедренный» или «Неверно, что треугольник ABC — равнобедренный».
Легко видеть, что значения истинности высказываний (a) и (b) находятся в определенной связи: если (a) — И, то (b) — Л и наоборот. Операция, с помощью которой из (a) получено (b), и само высказывание (b) называется отрицанием высказывания (a). Исходя из этого обычного смысла отрицания, приходим к определению:
Отрицанием некоторого высказывания p называется такое высказывание, которое истинно, когда p ложно, и ложно, когда p истинно.
p |
¬ p |
И |
Л |
Л |
И |
Отрицание высказывания p обозначим ¬p (читается «не пэ»). Например, p: 2 R (два — действительное число) и ¬p: 2 R (два — не действительное число), или p: «Тюмень — столица деревень» и ¬p: «Тюмень — не столица деревень».
Определение отрицания (и не только его) может быть записано в виде так называемой таблицы истинности. В ней указано, какие значения истинности (И, Л) принимает отрицание ¬p в зависимости от значений истинности исходного высказывания p.
3.2. Конъюнкция
Если два высказывания соединены союзом «и», то полученное сложное высказывание истинно тогда и только тогда, когда истинны оба простых высказывания.
— 19 —
Примеры. «Число 2 простое и четное» — истинно, т. к. истинны высказывания «Число 2 простое» и «Число 2 четное». Высказывание «Число 2 простое и нечетное» ложно, т. к. ложно одно из составляющих его простых высказываний.
p |
q |
p q |
И |
И |
И |
И |
Л |
Л |
Л |
И |
Л |
ЛЛ Л
Конъюнкцией двух высказываний p и q называется такое высказывание, которое истинно тогда и только тогда, когда истинны оба высказывания p и q.
Конъюнкцию будем обозначать значком и писать p q
(пэ и ку). Часто этот знак опускается, и пишут pq. Определение конъюнкции также можно записать в виде таблицы истинности.
3.3.Дизъюнкция
Вобыденной речи союз «или» применяется в двух различных смыслах — соединительном и разделительном. В языке логики по разному обозначаются операции, соответствующие тому или другому смыслу союза, «или». Исходя из соединительного смысла союза «или» мы приходим к следующему определению:
p |
q |
p q |
|
|
И |
И |
И |
|
И |
Л |
И |
Л |
И |
И |
ЛЛ Л
Дизъюнкцией двух высказываний называется такое новое высказывание, которое истинно тогда и только тогда, когда истинно хотя бы одно из этих высказываний.
— 20 —
Обозначать дизъюнкцию мы будем значком и писать p q (пэ или ку), понимая под союз «или» в соединительном смысле. Определение дизъюнкции может быть записано в виде данной таблицы истинности.
3.4.Импликация
Внаших рассуждениях, в частности в математических доказательствах, мы весьма часто пользуемся сложными высказываниями, составленными из двух элементарных, соединенных словами «если..., то». Обычно это высказывание понимается в смысле следования, т. е. из p следует q, p влечет q, p достаточное условие для q и т. п. Однако эти речевые синонимы еще не раскрывают смысла высказывания и связи его значения истинности со значениями истинности составляющих p и q. Для выяснения этой связи рассмотрим конкретный пример.
Высказывание «Если каждое слагаемое делится на 3, то и сумма делится на 3 истинно, т. е. из p следует q. Выясним, какие наборы значений истинности составляющих p и q возможны, когда высказывание «Если p, то q» истинно.
1. Пусть p и q — истинны, т. е., например, 6 и 9 — слагаемые и каждое из них делится на 3, тогда и сумма 6 + 9 = 15 делится на 3.
2. Пусть слагаемыми служат числа 4 и 5, т. е. p — ложно. Но 4 + 5 = 9, а 9 делится на 3, значит q — истинно.
3. Рассмотрим сумму 4 + 7 = 11. Слагаемые не делятся на 3, т. е. p — ложно, сумма также не делится на 3, значит и q — ложно.
Четвертого набора не существует: мы не найдем двух таких чисел, чтобы каждое из них делилось на 3, а их сумма нет, другими словами, высказывание «Если p, то q» — ложно, когда p — истинно, а q — ложно.
p |
q |
p q |
И |
И |
И |
И |
Л |
Л |
Л |
И |
И |
Л |
Л |
И |
— 21 —
Отметим еще одну особенность. В любом высказывании типа «Если p, то q» основание p и следствие q связаны по содержанию. Если его составляющие не связаны по содержанию, то высказывание считается бессмысленным («В огороде калина, а в Киеве дядька»). Однако в определении логической операции мы отвлекаемся от содержания высказываний, учитывая лишь их значения истинности. Приходим к определению:
Импликацией p q называется высказывание, которое ложно
тогда и только тогда, когда p — истинно, а q — ложно.
Это определение, конечно, тоже может быть записано в виде соответствующей таблицы истинности.
3.5. Эквиваленция
Сложное высказывание «Четырехугольник — параллелограмм, если и только если его диагонали делятся точкой пересечения пополам» мы понимаем в том же смысле, что и высказывание «Если четырехугольник — параллелограмм, то его диагонали делятся в точке пересечения пополам и, если диагонали четырехугольника делятся в точке пересечения пополам, то этот четырехугольник — параллелограмм».
Отвлечемся от содержания этих высказываний. Обозначим элементарное высказывание «Четырехугольник — параллелограмм» через p, а высказывание «Диагонали четырехугольника делятся в точке пересечения пополам» через q.
Тогда всякое высказывание типа «p, если и только если q» (1) понимается в том же смысле, что и «Если p, то q и, если q, то p» (2). Перейдем к символической записи
(p q) (q p).
p |
q |
p q |
q p |
(p q) (q p) |
|
И |
|
|
|
И |
И |
И |
И |
|
И |
Л |
Л |
И |
Л |
Л |
И |
И |
Л |
Л |
Л |
Л |
И |
И |
И |
— 22 —