Logic. 1. Propositions & Sets

Высказывания

Определение. Высказывание – это утверждение, являющееся верным или ложным.
Конечно, звучит очень обще, но, по крайней мере, исключает фразы вроде "Дай мне книгу" или "Что курил автор?". Высказывания бывают не только математические, например, "42 – смысл жизни" – тоже высказывание (правдивости которого мы, правда, не знаем).

Математические же высказывания обычно выражаются о хорошо известных нам объектах, таких как числа, множества, функции и т.п. Проиллюстрируем:

Высказывание. $2+2=5$.

Высказывание. Нет таких положительных целых $a$, $b$, $c$, $d$ что $a^4+b^4+c^4=d^4$.
Это частный случай гипотезы Эйлера, сформулированной Леонардом Эйлером в 1769.
Этот случай опроверг Ноам Элкис в 1986, найдя решение: $2682440^4+15365639^4+18796760^4=20615673^4$.
В 1988 Роджер Фрай нашёл наименьшее: $95800^4+217519^4+414560^4=422481^4$.

Также эта же гипотеза распространяется на иные размерности:
$$a^3+b^3=c^3$$ $$a^5+b^5+c^5+d^5=e^5$$ Последнее опровергнуто в 1966 году: $27^5+84^5+110^5+133^5=144^5$.

Высказывание. Нет таких положительных целых $x$, $y$, $z$, что $313(x^3+y^3)=z^3$.
Оно также неверно, но в самом маленьком из контрпримеров – овер 1000 цифр.

К слову, на английском высказывание – proposition, откуда ведёт своё название "пропозициальная логика" – логика, основанная на высказываниях.

По аналогии с числами, функциями и остальным, будем обозначать высказывания буквами. $$Z = \color{darkblue}{\text{На улице тепло}}$$ $$P = \color{darkblue}{\text{На улице зима}}$$ $$W = \color{darkblue}{\text{На улице снег}}$$ Помимо этого, можно конструировать новые высказывания:

• Не ($¬$): $(\neg \color{darkblue}{\text{На улице тепло}}) = \color{darkblue}{\text{На улице }} \color{red}{\text{не}} \color{darkblue}{\text{ тепло}}$.
• И ($∧$, $\&$): $(\color{darkblue}{\text{На улице зима}} \wedge \color{darkblue}{\text{На улице снег}}) = \color{darkblue}{\text{На улице зима }}\color{green}{\text{и}}\color{darkblue}{\text{ снег}}$.
• Или ($∨$, $∣$): $(\color{darkblue}{\text{На улице зима}} \vee \color{darkblue}{\text{На улице снег}}) = \color{darkblue}{\text{На улице зима }}\color{green}{\text{или}}\color{darkblue}{\text{ снег}}$.
• Следует ($⇒$): $(\color{darkblue}{\text{На улице зима}} \Rightarrow \color{darkblue}{\text{На улице снег}}) = \color{purple}{\text{Из того, что на улице зима, следует, что там снег}}$.
• Равносильно ($⇔$): $(\color{darkblue}{\text{На улице зима}} \Leftrightarrow \color{darkblue}{\text{На улице снег}}) = \color{purple}{\text{На улице зима тогда и только тогда, когда там снег}}$ (или наоборот).

Знаки $\&$ и $|$ больше приняты в программировании (их проще найти на клавиатуре ┐('～';)┌ ), но в логике также встречаются.

Чтобы не злоупотреблять скобками, выбираем следующий приоритет (более важное – левее): $$\neg,\quad \wedge \, \text{и} \, \vee,\quad \Rightarrow,\quad \Leftrightarrow$$ Не нужно это заучивать, просто дело привычки x).

Отдельно стоит сказать про равносильность: это значит, что высказывания одновременно истинны или же одновременно ложны. Её часто обозначают словами "тогда и только тогда", "необходимо и достаточно", "если и только если".

Математик дарит жене (тоже математику) букет красных роз и говорит ей: "Я люблю тебя!". Жена обижается. Почему?
Он должен был сказать: "Я люблю тебя и только тебя!".

Умные слова:

• Не – отрицание (negation).
• И – конъюнкция (conjunction).
• Или – дизъюнкция (disjunction).
• Следует – импликация (implication, от implies – следует).
• Равносильно – эквиваленция (equivalence).

Вы же обратили внимание на надпись XOR на картинке? Это eXclusive OR ("исключающее или"), когда мы требуем, чтобы было верно хотя бы одно из двух утверждений, но не оба сразу. Общепринятого обозначения нет, но встречаются такие: $A⊕B$; $A⊕_2 B$; $A +_2 B$; $A\; XOR\; B$; $A {\large\text{^}}\!B$; и, самое забавное, $A \ne B$. Используется XOR, в основном, в программировании и всякой криптографии.

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

Определение. Предикат – высказывание, чья истинность зависит от какого-либо объекта (или нескольких объектов).
Например:

Предикат. $n\text{ – целое число}$.
Очевидно, истинен для $n = 2;\; 3;\; 4$ и ложен для $n = {\large\frac{2}{5}};\; \pi;\; 0.1$.

Их тоже можно обозначать буквами: $$P(x) = \color{darkblue}{x\text{ – положительное число}}$$ Тогда $P(2)$ – правда, а $P(-1)$ – ложь.

Определение. Предикат, зависящий от $n$ объектов, называется $n$-местным предикатом.

Вот пример трёхместного предиката: $$Q(x,y,z) = [x^2 + y^2 = z^2]$$ Тогда, например, $Q(3,4,5)$ -- это высказывание $3^2+4^2=5^2$, очевидно, верное.

Отдельно можно отметить значки $\forall$ и $\exists$, называемые кванторами (квантор всеобщности и квантор существования) -- они удобно сокращают запись высказываний. Означают "для любого" и "существует" (сами значки $\forall$ и $\exists$ произошли от англ. All и Exists). $$\forall P: ¬¬P = P\qquad=\quad\text{для любого P верно }¬¬P=P \\ \exists P: ¬P = P\qquad=\quad\text{существует P такое, что }¬P=P$$ Двоеточие ($:$) нередко читается как "такое, что" или т.п.

Множества

Теория множеств создана во второй половине XIX века немецким математиком Георгом Кантором. В конечном итоге благодаря этому он сошёл с ума, поэтому математики решили построить на теории множеств всю остальную математику.

Под множеством мы понимаем объединение в одно целое определённых, вполне различимых объектов нашей интуиции или нашей мысли.
Георг Кантор

Это совсем не определение, конечно же. А если и определение, то философское, а не математическое. Явно что-то не то.

Множество – это любая совокупность объектов, например:

• Пустое множество.
• Множество $\{1,2,3 \}$.
• Множество букв русского алфавита.
• Множество всех ошибок в этой статье.
• Множество всех факторов, влияющих на упоротость автора.
• Множество целых чисел, делящихся без остатка на 5.
• Множество всех математиков.
• Множество всех множеств.

Множества бывают конечные, бесконечные, разной длины и т.п.

Здесь я остановлюсь и сделаю важное примечание: на самом деле нет. Математика и логика придумала такие совокупности объектов, которые ну никак не могут быть множествами. Так что определение множества как любой совокупности - неверно. Но к этому мы вернёмся слегка позже.

/ Я слегка соврал. На самом деле существует несколько теорий множеств, и мы сейчас знакомимся с так называемой наивной теорией множеств. Это именно та, что придумана Кантором, в ней множеством считается любая совокупность объектов, и, кроме того, говорят, что множество нельзя строго определить. /

• Множества состоят из элементов. Запись $x∈A$ обозначает, что $x$ принадлежит множеству $A$. Например, $1 ∈ \{ 1,2,3 \}$.
• О значении значка $∉$ догадайтесь сами. Я в вас верю.
• Порядок элементов не важен, т.е. $\{1, 2, 3\}$, $\{3, 1, 2\}$ и $\{3, 2, 1\}$ – одно и то же множество. Каждый элемент входит лишь один раз, т.е. $\{1,1,1\}$ и $\{1\}$ – тоже одно и то же множество.
• Множество $A$ называется подмножеством $B$, если все элементы $A$ также содержатся в $B$. Записывается $A ⊂ B$. Например: $$\{1,3\}⊂\{1,2,3\}$$ $$\varnothing⊂\{1,2,3\}$$ - Пустое множество не содержит ни одного элемента, является подмножеством любого множества и обозначается знаком $\varnothing$.
• Множества $A$ и $B$ равны, если они содержат одни и те же элементы. Иными словами, если $A⊂B$ и $B⊂A$.
• В разных теориях и учебниках предполагается, что значок $⊂$ позволяет или не позволяет быть равными. В таком случае вводят значок $⊆$, либо $⊊$.
  Мы же будем полагать, что $A⊂B$ позволяет множествам $A$ и $B$ быть равными, а запрещение их равенства отдельно оговаривать словами.
• Можно задать множество напрямую перечислением его элементов ($\{1,2,3\}$); либо же условием, которому они соответствуют, например: $\{ x \in A \; | \; P(x) \}$ – множество всех элементов $A$, удовлетворяющих условию $P(x)$ (условие задаётся предикатом). Более живой пример: $$\mathbb{N} = \{1, 2, 3, 4, 5, 6\ldots\}$$ $$A = \{x \in \mathbb{N}\;|\;x<4\}$$ $$\Downarrow$$ $$A = \{1, 2, 3 \}$$ <!– этот комментарий здесь временно, чтобы вёрстка в wysiwyg не ехала –>

Примечание: запись $\{x\in A\;|\;P(x)\}$ читается как "множество всех $x$ таких, что $P(x)$".

Определение. Возьмём некоторое множество $X$. Множество всех его подмножеств называется булеаном $X$ (впрочем, чаще так и говорят "множество всех подмножеств") и обозначается $2^X$. Например: $$2^{\{a,b,c\}}=\{\varnothing, \{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{a,b,c\}\}$$ Также иногда булеан $X$ обозначается $Sub(X)$ или $\mathcal P (X)$.

Считая множеством любую совокупность элементов (такое называется наивной теорией множеств), мы неизбежно приходим к некоторым парадоксам, таким, как, например, парадокс Бурали-Форти, парадокс Ришара или наиболее известный парадокс Рассела. Поскольку первый пока для нас слишком взрослый, рассмотрим два последних:

Парадокс Ришара

Некоторые числа могут быть заданы словами или фразами (например, "двадцать" или "число пи"). Пусть $M$ – множество всех чисел, которые могут быть заданы фразами (на русском языке), каждая из которых содержит не более 20 слов из не более 20 букв.

Это множество конечно, кстати (в нём не более, чем $31 + 31^2 + \color{gray}{\cdots} + 31^{20}$ чисел).

А теперь рассмотрим число, задаваемое фразой "Наименьшее из чисел, которое не может быть описано фразой из 20 слов из не более 20 букв". Вуаля!

Мы только что задали соответствующей фразой число, которое нельзя задать соответствующей фразой. Более того, согласно определению самого числа, оно явно не принадлежит множеству $M$. Однако принадлежит ему, согласно определению множества $M$. Σ(O_O)

Парадокс Рассела

Более всего он известен как парадокс брадобрея. А именно: В некоей деревне вышел приказ: брадобрей должен брить всех, кто не бреется сам и не брить всех остальных. Кто должен брить брадобрея?..

Пусть $M$ – множество всех множеств, которые не содержат сами себя: $$M = \{ B \; | \; B \notin B \}$$ В этом случае возникает вопрос: а содержит ли множество $M$ само себя? Если содержит, следовательно... не содержит. А если не содержит, следовательно – содержит.
Красота!

Примечание: очень увлекательно о парадоксе Рассела, а также о жизни и биографии Бертрана Рассела, о теории множеств, о логике и ряде знаменитых логиков и математиков рассказывает Логикомикс.

Аксиоматика

Чтобы избавиться от парадоксов, была придумана иная идея: ввести некие правила (называемые аксиомами), по которым можно конструировать множества. Тогда любое, не сконструированное по этим правилам множество (множество Рассела, например, или множество всех множеств) будет не иметь прав считаться множеством, то есть, мы избавимся от утверждения о его существовании и, как следствие, парадокса.

Одной из самых известных систем аксиом является система ZFC (Zermelo–Fraenkel set theory with axiom of Choice) – система Цермело-Френкеля с аксиомой выбора. Чуть позже мы её тоже рассмотрим.

О нечёткой логике

Как правило, мы можем чётко сказать, принадлежит ли наш (точно заданный) объект какому-либо множеству. Фиолетовый крокодил принадлежит множеству всех фиолетовых крокодилов, а число 5 – множеству всех целых чисел.

Давайте перейдём к чуть иной записи: $$1 ∈ \{1,2,3\}\qquad\rightarrow\qquad ∈(1,\{1,2,3\})=1$$ $$10 \notin \{1,2,3\} \qquad \rightarrow \qquad ∈(10,\{1,2,3\})=0 $ Однако не о всём можно сказать точно. Фиолетовый цвет - на 50% красный, а я не полностью уверен, что брошенный игральный кубик выпадет шестёркой вверх (вернее, я уверен в этом на$$ \frac16$). В 1965 году американский математик азербайджанского происхождения Лотфи Заде придумал так называемую нечёткую логику (англ. fuzzy logic), в которой используются нечёткие множества. Нечёткое множество – такое, что$\in(\text{элемент}, \text{множество})$принимает дробное значение от$0$до$1$, т.е. элементы могут частично принадлежать множеству. Это даёт возможность рассуждать о том, о чём мы не уверены. Таким же образом, утверждения могут принимать не только значения "*истина*" / "*ложь*", как в классической логике, но и "*возможно*", "*иногда*", "*не помню*" ("*как бы да*", "*почему бы и нет*", "*ещё не решил*", "*не скажу*"...). Использовать такое можно, например, в искусственном интеллекте и нейросетях. ## Операции над множествами Итаак, множества можно объединять, пересекать и прочее-прочее. Объединение:$ {\color{green}{1},\,\color{green}{2},\,\color{green}{3}}\,\, \cup\,\, {\color{blue}{10},\,\color{blue}{12}} = {\color{green}{1},\,\color{green}{2},\,\color{green}{3},\,\,\color{blue}{10},\,\color{blue}{12}} $Пересечение:$ {\color{green}{1},\,\color{green}{2},\,\color{green}{3},\,\color{rgb(0,150,150)}{4},\,\color{rgb(0,150,150)}{5},\,\color{rgb(0,150,150)}{6}}\,\, \cap \,\, {\color{rgb(0,150,150)}{4},\,\color{rgb(0,150,150)}{5},\,\color{rgb(0,150,150)}{6},\,\color{blue}{7},\,\color{blue}{8},\,\color{blue}{9}} = {\color{rgb(0,150,150)}{4},\,\color{rgb(0,150,150)}{5},\,\color{rgb(0,150,150)}{6}} $Разность:$ {\color{green}{1},\,\color{green}{2},\,\color{green}{3},\,\color{red}{4},\,\color{red}{5},\,\color{red}{6}}\,\, {\small\setminus} \,\, {\color{red}{4},\,\color{red}{5},\,\color{red}{6},\,\color{red}{7}} = {\color{green}{1},\,\color{green}{2},\,\color{green}{3}} $Симметрическая разность:$ {\color{green}{1},\,\color{green}{2},\,\color{green}{3},\,\color{red}{4},\,\color{red}{5},\,\color{red}{6}}\,\, {\small\triangle} \,\, {\color{red}{4},\,\color{red}{5},\,\color{red}{6},\,\color{blue}{7},\,\color{blue}{8},\,\color{blue}{9}} = {\color{green}{1},\,\color{green}{2},\,\color{green}{3},\,\,\color{blue}{7},\,\color{blue}{8},\,\color{blue}{9}} $$Отдельный вопрос вызывает дизъюнктное объединение (disjoint union). Ну и последнее: *декартово произведение множеств* (оно же *прямое произведение*)$$ A$и$B$это множество всех **упорядоченных** пар элементов из$A$и из$B$.$ {\color{red}{1},\,\color{blue}{2}} \times {3,\,4} = {\color{red}{(1,3)},\,\color{red}{(1,4)},\,\color{blue}{(2,3)},\,\color{blue}{(2,4)}} $Обращаю внимание на 2 важных момента: - Пары **упорядочены**, т.е.$(1,2)$и$(2,1)$– это 2 разные пары. - В общем случае$A !\times! B\, \ne\, B !\times! A$. Чему равно${\color{green}{3},\,\color{rgb(190,150,0)}{4}} \times {1,\,2}$? Кроме этого, есть также декартов квадрат множества, декартова степень множества и т.п.:$ X^1 = X $$$ X^2 = X \times X$ $$X^n = \underbrace{X \times X \times \cdots \times X}_{n}$$ Обратим внимание на важное соглашение: считается, что
$\{1,2\}\times\{3\}\times\{5\} = \{\,((1,3),5),\;((2,3),5)\,\}$ – неверно.
$\{1,2\}\times\{3\}\times\{5\} = \{\,(1,3,5),\;(2,3,5)\,\}$ – верно.

Формально должно быть верно первое (потому что $A\times B\times C = (A\times B)\times C$), но договорились о верности второго, чисто для удобства. Иными словами, $A\times B\times C$ -- это множество троек элементов, а не множество пар из пары и элемента.

Мощности

Определение. Под страшным словом мощность множества скрывается всего лишь количество его элементов.
Мощность множества $A$ обозначается $|A|$ или $\# A$.
Например: $$|\{1,2,3\}|=3$$ $$|\varnothing|=0$$ $$|\{\varnothing\}|=1$$ На всякий случай, последнее – это множество, содержащее пустое множество, т.е. 1 элемент, поэтому его мощность – 1. Иногда новичкам кажется это странным.

Также, если нужно указать, что множество $A$ конечно, иногда пишут так: $$|A| < \infty$$ Мощности бесконечных множеств – совершенно отдельная тема, которую мы непременно затронем чуть дальше.

Утверждение. Если есть конечное множество $X$, и $|X| = a$, то у него $2^a$ подмножеств. Или проще: $$|2^X| = 2^{|X|}$$ А попробуйте догадаться сами. Это было бы очень полезно.
Подсказка: рассмотрите мощность булеана пустого множества, а затем подумайте, что происходит с ней при добавлении 1 элемента, и почему?

.
.
.
.
.
.
.
.
.
.
.

А я приведу сразу 2 доказательства (читать только после своей попытки!):
$\triangleright_1$ Давайте рассмотрим множество $X = \{x_1,\,x_2,\,\color{gray}{\dots},\,x_n\}$ (очевидно, в нём $n$ элементов). А теперь скажем, что каждому его подмножеству $M$ соответствует набор из $n$ единичек и ноликов, где на соответствующем элементу месте стоит 1, если элемент принадлежит подмножеству, и 0, если не принадлежит. Называется этот набор характеристическим вектором подмножества и обозначается $\mu(M)$.
Ой, да что я рассказываю, вот пример: $$X = \{\color{red}{a},\,\color{red}{b},\,c,\,d,\,e,\,\color{red}{f}\}$$ $$M = \{\color{red}{a},\,\color{red}{b},\,\color{red}{f}\}$$ $$\mu(M)=(\color{red}{1},\color{red}{1},0,0,0,\color{red}{1})$$ Очевидно, каждому набору строго соответствует одно подмножество, для разных наборов подмножества разные – следовательно, сколько наборов, столько и подмножеств. Наборов, очевидно, $2^n$. $\triangleleft_1$

Или более простой способ:
$\triangleright_2$ Очевидно, $|2^\varnothing| = 1$ (поскольку пустое множество само является своим подмножеством).

Теперь рассмотрим какое-нибудь множество $X$. Добавим туда какой-нибудь новый элемент. Количество его подмножеств возрастёт вдвое: ведь его подмножествами останутся все предыдущие, а также станут новые, уже содержащие новый элемент! Ээм... непонятно, да? Пример: $$2^{\{a,b\}} = \color{rgb(0,100,100)}{\{\varnothing,\,\{a\},\,\{b\},\,\{a,b\}\}}$$ $$2^{\{a,b\}\cup\{c\}} = \color{rgb(0,100,100)}{\{\varnothing,\,\{a\},\,\{b\},\,\{a,b\}\}}\,\,\cup\,\,\color{rgb(100,0,100)}{\{\{c\},\,\{a,c\},\,\{b,c\},\,\{a,b,c\}\}}$$ Обратите внимание: второе множество из объединения – это первое, но только везде добавлен новый элемент.

Вроде бы наглядно, да? Такой метод рассуждения называется индукцией: чтобы доказать, что мы можем подняться на лестницу, надо доказать, что мы можем подняться на первую ступеньку, а, поднявшись на ступеньку n, можем и на n+1. И мы его чуть подробнее рассмотрим позже, да.

Поскольку мощность булеана пустого множества равна 1, а, добавляя в множество 1 элемент, мы увеличиваем мощность его булеана вдвое – следовательно, мощность булеана множества из 1 элемента равна 1, из 2 – 4, из 3 – 8, из 4 – 16... и так далее, а из $n$ – $2^n$. $\triangleleft_2$

Подумайте. Чему равна мощность $A\times B$?
.
.
.
.
.
.
.
.
.
.

Очевидно же, что $|A\times B| = |A| \times |B|$.

Вы ещё в своём уме? Не волнуйтесь! Будет ещё много шансов это исправить. Бесконечности, которые свели с ума Кантора (вроде бы, но я не уверен) – дальше. Муахаха.

Словарик

• Множество – set, элементы – elements, пустое – the empty set.
• Высказывание – proposition, квантор – quantifier (the existential quantifier and the universal quantifier).
• Объединение – union; пересечение – intersection; разность – difference; disjoint union; декартово произведение – Cartesian product, дополнение – complement.
• Нечёткая логика – Fuzzy logic.

Библиография

• Первые главы Зорича.
• Первые главы Решетняка.
• Шень, Верещагин.
• А.К. Гуц "Матлогика и теория алгоритмов".
• MIT Notes "Mathematics for computer science".
• Листок 57 школы: http://www.mccme.ru/~merzon/v14/pscache/01-sets.pdf