Мои статьи [9]
html-учебник [0]
css [0]
JavaScript [0]
jQuery [0]
uCoz [1]
html и css, вёрстка [0]
Другое [0]
Главная » Статьи » Мои статьи

Логика [1]
Приветики. Вы читаете материал, который не готов. Черновик. Причём тут очень даже черновик. Который будет, наверное, переписываться, переделываться и передумываться. Не раз. И да, всё это пишется не только на основе материала из моей головы, иной раз я беру кажущуюся мне подходящей структуру из других мест. Также из других мест целиком воруются целые главы, примеры, теоремы, доказательства и вообще всё. Здешняя библиография: - Первые главы Зорича. - Шень, Верещагин. - А.К. Гуц "Матлогика и теория алгоритмов". - Записки MIT "Mathematics for computer science". Главы: - Высказывания. - Множества. - Мощности множеств. Такое чувство, что никто ещё не назвал это бредом лишь потому что никто этого не видел) Начнёём.

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

Определение. Высказывание -- это утверждение, являющееся верным или ложным. Конечно, звучит очень обще, но, по крайней мере, исключает фразы вроде "Дай мне книгу" или "Что курил автор?". Высказывания бывают не только математические, например, "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 = \style{color:darkblue}{\text{На улице тепло}}$$ $$P = \style{color:darkblue}{\text{На улице зима}}$$ $$W = \style{color:darkblue}{\text{На улице снег}}$$ Помимо этого, можно конструировать новые высказывания:
  • Не (`\neg`): `(\neg \color{darkblue}{\text{На улице тепло}}) = \color{darkblue}{\text{На улице }} \color{red}{\text{не}} \color{darkblue}{\text{ тепло}}`.
  • И (`\wedge`, `&`): `(\color{darkblue}{\text{На улице зима}} \wedge \color{darkblue}{\text{На улице снег}}) = \color{darkblue}{\text{На улице зима }}\color{green}{\text{и}}\color{darkblue}{\text{ снег}}`.
  • Или (`\vee`, `|`): `(\color{darkblue}{\text{На улице зима}} \vee \color{darkblue}{\text{На улице снег}}) = \color{darkblue}{\text{На улице зима }}\color{green}{\text{или}}\color{darkblue}{\text{ снег}}`.
  • Следует (`\Rightarrow`): `(\color{darkblue}{\text{На улице зима}} \Rightarrow \color{darkblue}{\text{На улице снег}}) = \color{purple}{\text{Из того, что на улице зима, следует, что там снег}}`.
  • Равносильно (`\Leftrightarrow`): `(\color{darkblue}{\text{На улице зима}} \Leftrightarrow \color{darkblue}{\text{На улице снег}}) = \color{purple}{\text{На улице зима тогда и только тогда, когда там снег}}` (или наоборот)).
Знаки `&` и `|` больше приняты в программировании (их проще найти на клавиатуре), но в логике встречаются также. Чтобы не злоупотреблять скобками, следующий приоритет (более важное -- левее): $$ \neg,\quad \wedge \, \text{и} \, \vee,\quad \Rightarrow,\quad \Leftrightarrow$$ Не нужно это заучивать, просто дело привычки х). Отдельно стоит сказать про равносильность: это значит, что высказывания одновременно истинны или же одновременно ложны. Её часто обозначают словами "тогда и только тогда", "необходимо и достаточно", "если и только если".
Математик дарит жене (тоже математику) букет красных роз и говорит ей: "Я люблю тебя!". Жена обижается. Почему? Он должен был сказать: "Я люблю тебя и только тебя!".
Определение. Предикат -- высказывание, чья истинность зависит от какого-либо объекта. Например: Предикат. `n\text{ -- целое число}`. Очевидно, истинен для `n = 2; 3; 4` и ложен для `n = 2 \/ 5; \pi; 0.1`. Их тоже можно обозначать буквами: $$P(x) = \style{color:darkblue}{x\text{ -- положительное число}}$$ Тогда `P(2)` -- правда, а `P(-1)` -- ложь.

Множества

Теория множеств создана во второй половине XIX века немецким математиком Георгом Кантором. В конечном итоге благодаря этому он сошёл с ума, что, несомненно, повлияло на мой выбор тем для 1 рассказа о логике.
Под множеством мы понимаем объединение в одно целое определённых, вполне различимых объектов нашей интуиции или нашей мысли.
Георг Кантор
Это совсем не определение, конечно же. А если и определение, то философское, а не математическое. Явно что-то не то. Проще показать: - Пустое множество. - Множество `{1, 2, 3}`. - Множество букв русского алфавита. - Множество всех ошибок в этой статье. - Множество всех факторов, влияющих на упоротость автора. - Множество целых чисел, делящихся без остатка на 5. - Множество всех математиков. - Множество всех множеств. Существует очень распространённое мнение, что у множества нет определения, т.к. это -- изначальное понятие математики. Однако стоит отметить, что наряду с наивной теорией множеств существует и аксиоматическая, пытающаяся устранить многие парадоксы и дать определение. Надеюсь, у нас будет возможность это обсудить. - Запись `x \in A` обозначает, что `x` принадлежит множеству `A`. Например, `1 \in {1, 2, 3}`. - О значении значка `\notin` догадайтесь сами. Я в вас верю. - Запись `A \subset B` обозначает, что множество `A` является подмножеством `B`, т.е. все элементы `A` также принадлежат `B`. Например: $$\{1, 3\} \subset \{1, 2, 3\}$$ $$\varnothing \subset \{1, 2, 3\}$$ - Множества `A` и `B` равны, если они содержат одни и те же элементы. Иными словами, `A \subset B` и `B \subset A`. - Иногда вводят значок `\subseteq`, обозначающий, что множества могут быть равны, в таком случае `\subset` становится строгим подмножеством (т.е. запрещающим равенство). Но в нашем курсе это очень несущественно, так что `\subset` у нас является нестрогим. - Такая запись: $$ A \subsetneq B$$ значит, что `A` -- подмножество `B`, и они не равны. Также можно сказать, что `A` -- собственное подмножество `B`, но подобные названия применяются очень редко. - Пустое множество не содержит ни одного элемента, является подмножеством любого множества и обозначается таким знаком: $$ \varnothing $$
О нечёткой логике
Как правило, мы можем чётко сказать, принадлежит ли наш (точно заданный) объект какому-либо множеству. Фиолетовый крокодил принадлежит множеству всех фиолетовых крокодилов, а число 5 -- множеству всех целых чисел. Давайте введём функцию `\in(\text{элемент}, \text{множество})`, которая принимает значение `1`, когда элемент принадлежит множеству и `0` -- когда не принадлежит. Например: $$ \in \! (1, \{1, 2, 3\}) = 1 $$ $$ \in (10, \{1, 2, 3\}) = 0 $$ В 1965 году американский математик азербайджанского происхождения Лотфи Заде придумал так называемую нечёткую логику (англ. fuzzy logic), в которой используются нечёткие множества. Нечёткое множество -- такое, что функция `\in(\text{элемент}, \text{множество})` принимает дробное значение от `0` до `1`, т.е. элементы могут частично принадлежать множеству. Это даёт возможность рассуждать о том, о чём мы не уверены. Таким же образом, утверждения могут принимать не только значения "истина" / "ложь", как в классической логике, но и "возможно", "иногда", "не помню" ("как бы да", "почему бы и нет", "ещё не решил", "не скажу"...). Использовать такое можно, например, в искусственном интеллекте и нейросетях.
... ... Построение теории множеств, данное здесь, называется наивной теорией множеств. Есть также другое -- аксиоматическое, когда мы задаём некие правила (аксиомы) и утверждаем, что объект, им подчиняющийся, и есть множество. Наивная теория множеств содержит ряд парадоксов, например, парадокс Рассела. Пусть `M` -- множество всех множеств, которые не содержат сами себя: $$ M = \{ B \; | \; B \notin B \}$$ В этом случае возникает вопрос: а содержит ли множество `M` само себя? Если содержит, следовательно... не содержит. А если не содержит, следовательно -- содержит. Красота! Не менее известен он и как парадокс брадобрея. В некоей деревне вышел приказ: брадобрей должен брить всех, кто не бреется сам и не брить всех остальных. Кто должен брить брадобрея?.. Примечание: очень увлекательно о парадоксе Рассела, а также о жизни и биографии Бертрана Рассела, о теории множеств, о логике и ряде знаменитых логиков и прочих рассказывает Логикомикс. ...

Мощности

Определение. Под страшным словом мощность множества скрывается всего лишь количество его элементов. Мощность множества `A` обозначается `|A|` или `#A`. Например: $$ |\{1, 2, 3\}| = 3 $$ $$ |\varnothing| = 0 $$ $$ |\{\varnothing\}| = 1$$ Отдельно упомяну про последнее, это множество, содержащее пустое множество, т.е. 1 элемент. Теория множеств породила новый вид чисел: кардинальные числа. Мощность множества `A` также нередко называется кардинальным числом множества `A` и обозначается: $$ \operatorname{card} A $$ Просто другое название, не больше. Определение. Множества называются равномощными, если каждому элементу одного множества можно поставить в соответствие каждый элемент другого множества. Пример: $$ |\{1, 2, 3\}| = |\{\varnothing, |\varnothing |, 50\}| $$ Соответствие, например, такое: `1 -> ∅`, `2 -> |∅|`, `3 -> 50`. Можно поставить любое другое соответствие, не суть. Важно, чтобы разные объекты соответствовали разным. Вот, например, неравномощные: $$ |\{1,2,3\}| \ne |\{8, 9\}| $$ Пробуем поставить соответствие: `1 -> 8`, `2 -> 9`, `3->???`. Тройка не досчиталась друга. Можно подружить её с восьмёркой или девяткой, но тогда не досчитается друга кто-то другой. Фишка в том, что существуют бесконечные множества, причём разной длины. Следовательно, нам нужны какие-то новые числа, позволяющие меряться бесконечностями. И они есть. Кардинальные числа! $$ |\mathbb{N}| = \aleph_0 $$ Страшная буква `aleph` читается "алеф" и принадлежит множеству всех букв алфавита иврита. Бесконечности! О да. Именно исследование бесконечных множеств позволяет нам исследовать бесконечности. Кажется, именно бесконечные множества привели Кантора к. Вы ещё в своём уме? Не волнуйтесь! Будет ещё много шансов это исправить.
Категория: Мои статьи | Добавил: Кейтен (29 Январь 2016)
Просмотров: 87 | Рейтинг: 0.0/0
Всего комментариев: 0
Имя *:
Email:
Код *: