Глава 16. Введение в математическую логику

16.3. Утверждения в математике

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

A ≡ {число 100 делится на 4};
B ≡ {через две точки можно провести две прямые};
C ≡ {число 0,00000001 очень мало}.

Относительно одних утверждений можно сказать, что в них говорится нечто правильное, относительно других – утверждается нечто неверное. Например, утверждение A – верное, утверждение B – неверное. Относительно утверждения C нельзя сказать, является оно верным или нет, так как оно не имеет точного смысла.

Из определения 16.14 вытекает

На множестве высказываний можно ввести операции, позволяющие образовывать новые высказывания. Например, если заданы два высказывания A{сейчас солнечно} и B{сейчас ветрено}, то с помощью связок «и», «или», «если..., то...», «либо..., либо...», «тогда и только тогда, когда», «неверно, что» можно образовать новые высказывания вида: {сейчас солнечно и ветрено}, {сейчас солнечно или ветрено}, {если сейчас солнечно, то сейчас ветрено} и т.д. Такие высказывания называют составными, а входящие в них высказывания A и B – элементарными.

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

Данное определение записывают с помощью таблицы истинности, в которой буква «И» означает истинное высказывание, а буква «Л» – ложное.

A	И	Л

Например: отрицанием высказывания {через две точки можно провести две прямые} является высказывание {через две точки нельзя провести две прямые}. Отрицанием высказывания {число 37 не делится на 2} будет высказывание {число 37 делится на 2}.

Определение 16.16. 

Конъюнкцией двух высказываний A и B называется высказывание, которое истинно в том и только в том случае, если истинны оба высказывания. Обозначение: , читается: «A и B». Таблица истинности имеет вид:

A	И	И	Л	Л
B	И	Л	И	Л

Например: конъюнкцией высказываний {3 < 8} и {8 < 11} является высказывание {3 < 8 < 11}. Или, конъюнкцией высказываний {точка A лежит на прямой a} и {точка A лежит на прямой b} является высказывание {точка A лежит на прямой a и на прямой b}.

Определение 16.17. 

Дизъюнкцией двух высказываний A и B называется высказывание, которое ложно тогда и только тогда, когда ложны оба высказывания. Обозначение: , читается: «A или B». Таблица истинности имеет вид:

A	И	И	Л	Л
B	И	Л	И	Л

Примеры: дизъюнкцией высказываний

• {3 < 8} и {3 = 8} является высказывание {3 < 8 < 11};
• {точка A лежит на прямой a} и {точка A лежит на прямой b} является высказывание {точка A лежит на прямой a или на прямой b}, где связка "или" не имеет разделительного смысла. То есть точка A может лежать либо только на прямой a, либо только на прямой b, либо же на прямой a и прямой b одновременно.

Для доказательства достаточно сравнить таблицы истинности высказываний и ( и Покажем для и . A И И Л Л B И Л И Л B И И Л Л A И Л И Л

Определение 16.18. 

Высказывание «если A, то B» называют импликацией высказываний A и B, если оно ложно лишь в случае, когда A – истинно, а B – ложно. Обозначение: Таблица истинности имеет вид:

A	И	И	Л	Л
B	И	Л	И	Л

Высказывание A называют условием, а B – заключением импликации.

Например: импликацией высказываний {100 делится на 4} и {100 – четное число} является высказывание {если 100 делится на 4, то 100 – четное число}. Импликация обратная данной будет тогда такой: {если 100 – четное число, то 100 делится на 4}. Как мы видим, если импликация истинна, то обратная к ней не всегда будет истинна. Противоположной к исходной будет импликация {если 100 не делится на 4, то 100 не является четным числом}.

Определение 16.21. 

Эквиваленцией высказываний A и B называется высказывание, которое истинно, когда оба высказывания A и B истинны или оба ложны. Обозначение: Таблица истинности имеет вид:

A	И	И	Л	Л
B	И	Л	И	Л

Например: эквиваленцией двух высказываний {точки A и B лежат в разных полуплоскостях от прямой a} и {отрезок AB пересекает прямую a} является высказывание {точки A и B лежат в разных полуплоскостях от прямой a тогда и только тогда, когда отрезок AB пересекает прямую a}.

Например: на рис. 16.3.2 изображены точки, соединенные несколькими отрезками. На множестве X, состоящем из точек a, b, c, d, e, f, g (X = {a, b, c, d, e, f, g}), задан одноместный предикат A (x) = {к точке x в рассматриваемой фигуре примыкают три отрезка}.

1

Рисунок 16.3.1

Ниже приведена таблица истинности этого предиката:

Множеством истинности данного предиката, соответственно, будет множество точек T = {c, d, e}.

Справедливо а)  б) 

Так же, как и для высказываний, на множестве предикатов можно ввести операции отрицания, конъюнкции, дизъюнкции, импликации и эквиваленции. Для этого устанавливают правила, которые позволяют находить множество истинности составного предиката, если известны множества истинности составляющих его элементарных предикатов.

Пусть на множестве X заданы предикаты A (x) и B (x), множества истинности которых соответственно и

В том случае, когда импликация  истинна при всех значениях из множества X, говорят, что предикат B (x) логически следует из предиката A (x), и предикат B (x) называют необходимым условием для предиката A (x), а предикат A (x) – достаточным условием для B (x).

Если предикаты A (x) и B (x) на множестве X эквивалентны, то каждый из них называют необходимым и достаточным условием для второго.

Например, в импликации {если x – число натуральное, то оно целое} предикат B (x) = {x – число целое} логически следует из предиката A (x) = {x – число натуральное}. Следовательно, предикат B (x) является необходимым условием для предиката A (x), а предикат A (x) – достаточным для B (x). Используя эти термины, импликацию {если число x натуральное, то оно целое} можно выразить так:

1. Для того чтобы число x было натуральным, необходимо, чтобы оно было целым.
2. Для того чтобы число x было целым, достаточно, чтобы оно было натуральным.

Часто приходится рассматривать предикаты, в которые входит не одна, а две и больше переменных. Они называются в зависимости от числа переменных двухместными, трехместными, ..., n-местными. Рассмотрим, например, следующие предложения, в которых под x и y понимают произвольные натуральные числа:

A (x, y) = {x < y}, B (x, y) = {x + y = 10}, C (x, y) = {x делится на y}, D (x, y) = {x + y есть простое число}.

Мы ничего не можем сказать об истинности или ложности этих утверждений, пока не сказано, какие значения принимают x и y. Но если точно указано, чему равны x и y, каждое из сформулированных утверждений превращается в высказывание – для одних пар (x, y) истинное, для других ложное. Множество всех пар чисел (x, y), для которых данный двухместный предикат есть истинное высказывание, называется множеством его истинности.

Приведем примеры высказываний, получающихся из указанных предложений при конкретных значениях x и y:

• A (1; 3) = {1 < 3} – истинное высказывание,
• A (2; 2) = {2 < 2} – ложное высказывание,
• A (5; 4) = {5 < 4} – ложное высказывание,
• B (1; 3) = {1 + 3 = 10} – ложное высказывание,
• B (8; 2) = {8 + 2 = 10} – истинное высказывание и т.д.