Отрицание утверждений

Формальный язык

Для формализации математических текстов введём так называемые логические связки:

Название	Прочтение	Обозначение
Отрицание	не
Конъюнкция	и
Дизъюнкция	или
Импликация	если …, то …
Эквиваленция	тогда и только тогда, если и только если, в том и только том случае, согда

Вообще говоря, эти связки имеют больший смысл, чем просто сокращение слов разговорного языка. Интересующегося читателя мы обращаем к изучению математической логики и булевой алгебры — см. [1]–[5].

Все приведённые выше логические связки, за исключением одной, — «бинарные». Это означает, что они связывают два высказывания.

Пример 1.1.1.  Запись  означает, что  делится на  (к примеру, ). Тогда имеет место теорема, которую на формальном математическом языке можно выразить так:  В переводе на русский: «если число делится на ноль, то это число само есть ноль»^[1].

«Унарной» является связка , она применяется к одному высказыванию.

Пример 1.1.2.  Запись  означает .

Помимо логических связок нам также понадобятся так называемые кванторы:

Название	Прочтение	Обозначение
Квантор всеобщности	для любого …
Квантор существования	существует …
Квантор существования и единственности	существует и единственен

Слово квантор происходит от англ. quantity (количество); символ  — от англ. any (любой); символ   — от англ. exists (существует).

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

Если  — некоторое свойство, то  означает, что свойство  выполнено для всех объектов  (обычно ещё указывают, откуда эти объекты берутся);  означает, что хотя бы для одного объекта  выполнено свойство .

Пример 1.1.3.  Запись

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

читается так: «во множестве  существует такой элемент , что для любого элемента  множества  справедливо равенство »^[4].

Очень важно понимать, что нельзя менять в порядке различные кванторы:  означает принципиально иное, нежели .

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

Как и в примере 1.1.2 слово означает мы впредь будем заменять символом .

Символ  означает «равно по определению».

Пример 1.1.4.  Число  есть отношение длины окружности  к её диаметру :

Установим некоторые соотношения, необходимые нам для дальнейшей работы. Их доказательство требует более детального обсуждения формальной теории, которая выходит далеко за рамки курса математического анализа, поэтому мы вынесли его в упражнения. Важно помнить, что это всё-таки — теорема 1.1.1:

(1) Коммутативность конъюнкции
(2) Коммутативность дизъюнкции
(3) Ассоциативность конъюнкции
(4) Ассоциативность дизъюнкции
(5) Дистрибутивность конъюнкции относительно дизъюнкции (слева и справа)
(6) Дистрибутивность дизъюнкции относительно конъюнкции (слева и справа)
(7) Идемпотентность конъюнкции
(8) Идемпотентность дизъюнкции
(9) Снятие двойного отрицания
(10) Законы де Моргана

Заметим, что после установления коммутативности произвольной операции , из её дистрибутивности относительно другой операции  слева (или справа) следует её дистрибутивность относительно  справа (соответственно, слева).

В курсе алгебры доказывается так называемое свойство обобщённой ассоциативности, согласно которому в выражении , если операция  ассоциативна, расстановка скобок не играет роли, а потому все скобки можно опустить^[5]. А если операция  ещё и коммутативна, то не играет роли также порядок операндов. Примем это во внимание и для операций  и , коль скоро они и ассоциативны, и коммутативны. Таким образом, можно положить следующие определения:

Отрицание утверждений

Для примера возьмём (хоть мы его пока и не понимаем) определение интеграла Римана:

Общее правило отрицания какого-либо высказывания, как например, только что приведённого, состоит в следующем: заменяем все кванторы всеобщности кванторами существования, и наоборот, а последнее утверждение (в случае выше — выделенное лиловым цветом) заменяем его логическим отрицанием. Таким образом, отрицание утверждения выше выглядит так:

*Почему  — см. упражнения.

Упражнения

Формально к определению символов , ,  и т.д. можно подойти с двух сторон: с точки зрения синтаксиса и с точки зрения семантики. Первое подразумевает их рассмотрение как «лингвистических» объектов, связывающих между собой некоторые высказывания (примерно так и мы определили их); второе — определение их как символов операций над высказываниями. Развивая второй подход, приводят так называемые таблицы истинности, которые связывают истинность составного высказывания (например, ) с истинностью их составляющих (истинностью  и ). Вот эти таблицы
(1 — истина (true), 0 — ложь (false)):

0	1		0	0	0		0	0	0		0	0	1		0	0	1
1	0		0	1	0		0	1	1		0	1	1		0	1	0
			1	0	0		1	0	1		1	0	0		1	0	0
			1	1	1		1	1	1		1	1	1		1	1	1

Формула (как, например, выражение ) называется тождественно истинной, если при всех оценках её составляющих (,  и т.д.) она принимает значение 1.

№1.  Пользуясь таблицами истинности, докажите теорему 1.1.1.

№2.  Пользуясь таблицами истинности, докажите, что следующие формулы являются тождественно истинными:

1)  — закон контрапозиции;

2) ;

3) .

 

 

Рекомендуемая литература:

Для лучшего ознакомления:

[1] YouTube: «Введение в логику» / Хекслет https://www.youtube.com/playlist?list=PLf1RW50cnBYeWgx6zue1rCJTVVuz9VnIP

Для полноценного изучения темы:

[2] Учебник: «Дискретная математика» / Новиков Фёдор Александрович / 2017

[3] YouTube: «Математическая логика и теория алгоритмов» / МФТИ, лектор — Дашков Евгений Владимирович

https://www.youtube.com/playlist?list=PL4_hYwCyhAvYls1eX-LmnQsmO3IANGRZv

[4] YouTube: «Введение в математическую логику и теорию алгоритмов» / Механико-математический факультет МГУ, лектор — Шехтман Валентин Борисович https://www.youtube.com/playlist?list=PLcsjsqLLSfNBbcIq4kESL7053mAvaUuFf

[5] YouTube: «Математическая логика и теория алгоритмов» / МФТИ, лектор — Мусатов Даниил Владимирович https://www.youtube.com/playlist?list=PL4_hYwCyhAvZjAmC7XFESNgWbG6wMteVm

[1] На ноль делить можно, но только само число ноль. Частное в этом случае не определено.

[2] Что означает знак  — см. §2.

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

[4] Формулы  и  являются аксиомами так называемого моноида (или, как ещё говорят, «полугруппы с единицей»). Формула  выражает свойство «ассоциативности» операции .

[5] Мы докажем это свойство в следующих параграфах.