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

Назад Вперед
Назад Вперед

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

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

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

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

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

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

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

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

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

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

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

Свойство 16.5. 

Всякое высказывание является либо истинным, либо ложным (закон исключенного третьего).

Свойство 16.6. 

Никакое высказывание не может быть одновременно истинным и ложным (закон противоречия).

Свойство 16.7. 

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

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

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

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

Отрицанием высказывания A называется высказывание, которое истинно, когда A ложно, и ложно, если A истинно. Обозначение: Читается: «неверно, что A».

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

 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 И Л И Л

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

Свойство 16.9. 

Операции дизъюнкции и конъюнкции коммутативны.
 и .

Доказательство

Свойство 16.10. 

Операции дизъюнкции и конъюнкции ассоциативны.
  и 

Доказательство

Свойство 16.11. 

Для любых трех высказываний AB и C справедливы равенства

Доказательство

Свойство 16.12. 

Дизъюнкция любого высказывания A и его отрицания  – тождественно истинна. Обозначение:

Свойство 16.13. 

Для любых двух высказываний A и B справедливы формулы де Моргана:
 

Доказательство

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

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

A И И Л Л
B И Л И Л

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

Свойство 16.14. 

Для любых двух высказываний A и B справедливо

Доказательство

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

Импликацией, обратной данной импликации , называется импликация .

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

Импликацией, противоположной данной импликации , называется импликация .

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

Свойство 16.15. 

Справедливы равенства  и 

Доказательство

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

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

A И И Л Л
B И Л И Л

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

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

Пусть предложение содержит переменную, которая может принимать различные значения, причем подстановка любого из значений переменной превращает предложение в высказывание. Тогда это предложение называют одноместным предикатом. Множество X всех значений переменной x называют областью определения предиката. Обозначение предиката: A (x).

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

Множеством истинности предиката A (x), xX называется подмножество TX, на котором A (x) истинно.

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

A (a) A (b) A (c) A (d) A (e) A (f) A (g)
Л Л И И И Л Л

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

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

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

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

Квантором общности называют символ , означающий слово «все». Высказывание  читается: «для всех x из X справедливо P от x».
Квантором существования называют символ , означающий слово «существует». Высказывание  читается: «существует такое x из X, что справедливо P от x».

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

Доказательство

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

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

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

Отрицанием предиката A (x) называется предикат  множество истинности T которого является дополнением к множеству T1, то есть T = X \ T1.

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

Конъюнкцией предикатов A (x) и B (x) называется предикат   множество истинности которого определяется равенством

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

Дизъюнкцией предикатов A (x) и B (x) называется предикат   множество истинности которого определяется равенством

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

Импликацией предикатов 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 (xy) = {x < y}, B (xy) = {x + y = 10}, C (xy) = {x делится на y}, D (xy) = {x + y есть простое число}.

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

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


Назад Вперед
Наверх

Включить/Выключить фоновую музыкуВключить/Выключить звуки событий

 

Смотрите также: Математика, Английский язык, Химия, Биология, Физика, География, Астрономия.
А также: библиотека ЭОРов и образовательный онлайн-сервис с тысячами интерактивных работ "Облако знаний".