Александр Соловьев
ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ
Автор выражает благодарность Ворду (или Уорду) – 2000, который отбил у него желание писать формулы. Напрочь.
ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ
Лекции без доски
(Для тех, кто терпеть не может формулы, но имеет воображение)
ЛИРИЧЕСКОЕ ОТСТУПЛЕНИЕ
Формулы в математике были придуманы, как это не странно, чтобы облегчить занятия этой самой математикой. Школьники не могут в это поверить до сих пор.
В древней, например, Индии хорошо обходились без формул: брали обезьяну, кувшин, банан, женщину и другие конкретные предметы… И, как сейчас говорят, конкретно строили логические выводы. И египтяне вместо формул, которые еще не были придуманы, высекали у себя в пустынях, на формульном безрыбьи, красивые барельефы. И арабы когда-то занимались математикой без формул – в стихотворной форме они ею занимались. Сладкозвучные поэмы писали про квадрат суммы…
Но потом пошло-поехало…
Виноват конкретно Пифагор, который сказал, что \"ВСЕ ЕСТЬ ЧИСЛО\"!… БОлшую неправду для математики трудно придумать и сегодня! Хотя к пифагоровым штанам претензий нет… Скроены на века.
Сегодня математику не любят многие. Подавляющее большинство мирного населения. Не любят прежде всего из-за формул. И правильно делают. Поскольку еще в школе несчастных предупредили, что математика – это формулы, так же как стихи – это рифмы. (Поэтому они не занимаются математикой, а наоборот, целыми днями шлют на радио поздравления в стихах всем своим знакомым, чтобы поразить художественными откровениями весь мир: «поздравляю желаю», «без бед – до ста лет». Не правда ли, очень удачно!?…).
Каково же было мое удивление, когда, читая книги по основам (основаниям) математики, я там, практически, не обнаружил формул.
Формулы, конечно, создают для математика великое облегчение, но это надо понять добровольно, а не подвергаться принудительной формулизации – истязаниям, мол, стерпится – слюбится…
Все наши гуманитарные проблемы в математике не только из-за тяги некоторых отморозков к абстракции. Тут есть еще более коварное слово СЕМАНТИКА, что на человеческом языке означает обычно СМЫСЛ. Так вот, прежде всего со смыслом обычно и борется математика всеми доступными ей средствами, в том числе и формулами… Разумеется, во имя достижения ВЫСШЕГО СМЫСЛА. Как это всегда у нас бывает!
Чем более «высшая\" математика – тем меньше в ней СЕМАНТИКИ и больше СИНТАКСИСА. Синтаксис все в школе тоже проходили и он до сих пор мало кому доставляет радость!… Может и права Т. Толстая, когда в романе «КЫСЬ» называет «синтаксис» словом матерным.
Но это еще пока не лекция, а лирическое отступление.
П.С. В интернете, с момента его возникновения, много появляется очень умных людей, порой с законченным физ-мат образованием. Это хорошо, но иногда достает… поскольку от большого ума не все сохраняют способны судить «по законам жанра\". Так что к ним отдельная просьба, не подозревать автора в попытке написать учебник по „основаниям математики“, или „монографию“. А главная просьба – вообще не читать ниженаписанное. Не для вас это. Идите с миром откуда пришли…
Лекция 1. МНОЖЕСТВА
Что такое «множество» – ясно из самого слова без всякого определения. Тем более, что дать этому фундаментальному математическому понятию определение невозможно. И не пробуйте.
Лучше потратить свою энергию на вечный двигатель или на что-то другое конкретное…
Множеством может быть множество деревьев в лесу, множество студентов в университете или даже множество бедных родственников в Америке, которые могут выслать вам приглашение… Есть, конечно, специальная очень серьезная игра под названием \"АКСИОМАТИЧЕСКАЯ теория множеств\". Понять ее правила дано немногим, а найти практическое применение никому… Но это развлечение для очень замкнутого круга любителей, коль скоро и сама эта теория очень замкнута.
Множество состоит из элементов – деревьев, студентов, бедных родственников… При этом никакой роли не играет, рассматриваем ли мы тех же студентов в порядке алфавита или по успеваемости.
Недопустимы только двойники или студенты, у которых отсутствуют отличительные свойства. Будьте хоть китайскими студентами, но должны друг от друга отличаться… Могут даже быть множества, состоящее из чисел. Но мы, как договорились, от математики вообще, и от чисел в частности, шарахаемся, как черт от ладана… Поэтому можно и без них. Или можно с ними. Или будем использовать только те числа, которые хорошо знакомы с детства…
Однако мы не будем считать множеством «множество мыслей в голове». И не из-за их количества, а из-за того, что эти мысли-элементы невозможно четко разделить в общей каше, разложить по полочкам и разметить. Множество мыслей, разложенных по полочкам, в голове просто не поместится из-за устаревшего устройства типовой головы.
Кстати, поскольку «множество» ( set ) в русском языке как бы намекает на «много». А понятие «много» ( many ) у каждого из нас свое, то, во избежания спора между русскоязычными, мы будем слово «множество» использовать для любого количества элементов, как и англоязычный Запад. Даже для одного элемента. Даже в случаях, когда в множестве нет ни одного элемента – такое множество называется пустым! Это, в частности, позволит рассказывать своим друзьям корректный, с точки зрения теории множеств, анекдот про «множество нуждающихся ветеранов Куликовской битвы»…
Кроме понятия множества есть еще лишь одно исходное базовое понятие – и все. Остальное в этой теории производно. Так вот, второе базовое понятие – это ПРИНАДЛЕЖНОСТЬ (или «отношение принадлежности»). То есть «элемент принадлежит множеству». Тут, тем более, нечего определять, имея в виду что слово «принадлежит» в обыденной речи можно заменять, с учетом контекста, многими синонимами, вроде:
– Та березка «находится» в этом лесу,
– Сидоров «числится» в студентах,
– Мистер Х «входит» в число ваших бедных американских родственников.
Примечание. Чтобы избежать синонимов, которые могут нас запутать, можно бы было ввести специальный маленький значок, напоминающий греческую букву эпсилон. Но мы этого делать не будем, поскольку от этого значка до формул уже рукой подать…
Важное предостережение. Вопросы, вроде: «Принадлежит ли студент Сидоров множеству лысеющих людей?» уводят нас в сторону от теории множеств и мы такие вопросы будем просто игнорировать, справедливо считая, что классическая теория множеств лысеющими просто не занимается, коль скоро нет об\'ективных оценок лысости. А значит вопрос принадлежности – непринадлежности можно утрясти неформально, например за вознаграждение. Выход здесь очень простой. Сначала определиться четко с лысиной где-то в другом официальном месте, а потом привлекать теорию множеств.
То есть предполагается, что мы всегда четко знаем, что принадлежит данному множеству, а что нет! Остальное считаем несуществующим вообще!!!
Далее, если мы хотим сказать, что все березки (березка, не то что лысеющий человек – она и в Африке березка), находящиеся в данном лесу, принадлежат и всему лесному богатству нашей страны, а все студенты, которые числятся в университете, числятся и студентами России, то для сокращения фраз используются термины ПОДМНОЖЕСТВО или ВКЛЮЧЕНО.
Здесь тоже могут быть очевидные синонимы. Но чтобы в них не запутаться и попросту не перепутать с «принадлежит», нужно помнить одну простую вещь: «принадлежит» относится к случаю, когда \"ЭЛЕМЕНТ принадлежит МНОЖЕСТВУ\", а «включено» – когда \"МНОЖЕСТВО включено в МНОЖЕСТВО\". Потому-то второй вариант для обозначения «включено» – «подмножество» – то есть какая-то часть множества.
Множество студентов университета «включено» в множество студентов страны. То есть множество студентов университета «есть подмножество» множества студентов страны.
Тем, кто не сломал при этом язык, ясно, что множество студентов страны «включено» во всемирное множество студентов.
Можно продолжить эту цепочку включений, прихватив галактику. Но тогда следует, что множество студентов университета есть подмножество множества студентов галактики.
Это свойство цепочек просто и строго(!) доказывается прямо на основании того, как мы определили отношение включения.
У отношения включения есть ряд любопытных свойств. Не нами придуманных. Они могут быть обнаружены любым исследователем, если он «поиграет» с этим отношением.
Например, можно сказать, что множество студентов группы ух-001 включено в множество студентов университета, поскольку такая группа в университете числится. То, что из группы отчислены все студенты, для математики никакой роли не играет. Поскольку, НЕТ ни одного студента, числящегося в этой группе, который бы не числился в университете. Такого рода рассуждения совершенно корректно можно применить к любым пустым множества и сделать обобщающий вывод, что пустое множество включено в любое множество, в том числе и в себя.
Оцените математическую красоту фразы:
Любой элемент, принадлежащий множеству, не содержащему ни одного элемента, принадлежит и любому другому множеству, которое не содержит ни одного элемента.
Чуть менее красива фраза:
Любое множество является собственным подмножеством.
Или то же самое, но более жестоко:
Любое множество включено само в себя.
Действительно, группа ух-002 (в которой, вполне возможно, есть студенты) включена в группу ух-002, поскольку все студенты, которые в ней числятся по-прежнему числятся в ней, даже если ее название ух-002 упоминается несколько раз.
Из последнего примера можно сделать важный вывод. Если два множества (возможно на первый взгляд различные, вроде множества чиновников и множества слуг народа) включены друг в друга, то эти множества равны – то есть состоят из одних и тех же элементов.
Можно сказать чуть иначе: Если два множества являются подмножествами друг друга, то они состоят из одних и тех же элементов.
А как же иначе?!…
Правда, есть математики-диссиденты, которые это не признают. Но это скорее уже вопрос веры… другой математической конфессии…
А теперь следует признать, что математики сродни той категории больных людей, которых называют «правдоискателями». Как правило искатели (социальной) правды правы. Но их правота или бессмысленна, или нереальна, а главное, никому кроме них не нужна… Так вот и в теории множеств часто можно найти правду, которая для посторонних людей может выглядеть, мягко выражаясь, странной и вредной.
Например, студент Хведоров не может быть подмножеством студентов университета, поскольку он сам не множество, а элемент. Поэтому он, как элемент, может быть лишь элементом множества студентов университета. А вот группа ух-003, как множество студентов, есть полноправное подмножество множества студентов университета. Но группа ух-003 состоит всего лишь из одного неотчисленного студента. Того самого Хведорова! Вот и получается, что сам Хведоров не может быть подмножеством, но группа, состоящая из него одного, может.
С другой стороны, если вдруг ректор решит рассматривать университет, как множество студенческих групп, то группа ух-003 станет элементом множества студенческих групп университета. Тут ничего страшного, если понимать, что множество студентов университета и множество студенческих групп университета – два разных множества.
Впрочем, нас бюрократическими закорючками не удивишь мы и не такое в жизни видим каждый день…
Но, все-таки, теории множеств есть чем удивить даже нас. Это, так называемые парадоксы теории множеств – одно из потрясений первого года прошлого столетия для узкого круга людей.
Поясним на знаменитом примере про брадобрея.
Правитель (вроде Петра I) повелел единственному брадобрею в своем царстве-государстве брить всех тех и только тех, кто не бреется сам. А наказание за ослушание – казнь. Вот брадобрей и бросился брить всех небритых. В конце-концов дошло до того, что он сам зарос бородой… Он взял бритву. Но если он начнет бриться, значит он бреется сам, а таких он брить не имеет права.
Отложив бритву, он понял, что он сам не бреется. Значит он должен взять бритву и… И что?! А ничего хорошего! Казнят бедолагу за нарушение приказа в любом случае!
С точки зрения теории множеств брадобрей в данном случае не смог определиться с (фундаментальным!) отношением принадлежности: включать или не включать себя самого в множество тех, кто не бреется сам.
То есть в основе теории множеств, которая претендует на роль фундамента ВСЕЙ математики, начальное базовое отношение принадлежности выкидывает такие фортеля, которые просто не позволяют создать некоторые из множеств!… Математики приняли единственное разумное решение: Договорились не создавать в рамках теории множеств такие множества, которые нельзя создать!
То есть теория множеств оперирует со всеми множествами, кроме тех, которые нельзя создать. Все эти множества, об\'единенные в одно множество, называются УНИВЕРСУМОМ.
Лекция 2. БЕСКОНЕЧНОСТЬ БЫВАЕТ РАЗНАЯ
Самое интересное в теории множеств то, что она рассматривает не только конечные множества – множества, содержащие конечное число элементов, но и бесконечные, для которых даже понятие числа бессмысленно. То есть, теория множеств может рассматривать не только множество студентов в группе и множество березок в лесу, но и множество точек на прямой, и множество звезд на небе…
Основоположник теории множеств Георг Кантор именно из-за бесконечности попортил себе много крови, да так крепко попортил, что пришлось подключаться врачам-психиатрам. Хотя с бесконечностью математики до него уже давным-давно работали. Взять то же бесконечно большое множество точек на прямой или наоборот, бесконечно малые величины из высшей математики…
Но вся беда в том, что ни один живой человек не видел, не слышал, не щупал бесконечности! Поэтому до Кантора математики признавали и использовали так называемую ПОТЕНЦИАЛЬНУЮ бесконечность. Самый кондовый пример – это понятие бесконечно большого числа в высшей математике. Бесконечно большое число это число, которое больше любого наперед заданного. Если человек не понимает, о чем речь, то его просят назвать самое большое число в мире!… Образованный человек обычно называет число миллиардмиллиардов. А ему об\'ясняют, что бесконечно большое число больше этого числа – «даже больше чем на еще миллиардмиллиардов».
То есть у нас с вами всегда в запасе есть число потенциально(!) большее, чем придумает эрудит…
Кантор же позволил себе в математике АКТУАЛЬНУЮ бесконечность. То есть то, что до этого могли позволить себе лишь поэты, с которых, как известно, никто строго не спросит… «звездам числа нет, бездне дна». Поэты не любят, чтобы по крохам, по каплям… Любят, чтоб сразу! \"Вот она, ВСЯ бездна вашего падения!… Дарю тебе ВСЕ звезды – такой ничтожной малости, для тебя моя, бесценная-единственная, не жалко!\"… То есть по Кантору бесконечность существует сразу вся. А раз бесконечные множества есть, и сразу целиком, то с ними можно производить математические манипуляции. Их даже можно сравнивать на больше-меньше.
Поэтому Кантор начал задавать себе «поэтические» вопросы и искать на них математические ответы. Один из ключевых вопросов: \"БЕСКОНЕЧНО МНОГО – это всегда ОДИНАКОВО БЕСКОНЕЧНО МНОГО? Или могут быть большие и меньшие бесконечности?\"
Чего больше, звезд на небе или точек на прямой?…
Кантор доказал великую теорему, из которой следует, что бесконечности могут быть разные по величине. Поскольку «число» и «количество» – слова в этом случае неуместные, то он ввел термин «мощность». Мощность – это то что остается, когда нас не интересует сущность элементов множества и порядок, в котором они располагаются. То есть, он определил понятие мощности строго, хотя определение и кажется на первый взгляд странным. На второй взгляд этого, обычно, так уже не кажется. От множества студентов останется только мощность, если мы перестанем их различать и будем воспринимать их вне всякого порядка (в естественных условиях).
Увы, приводить примеры множеств, имеющих бесконечную мощность, используя березки и студентов, не получится вообще, а звезды далеки и видны только ночью. Поэтому обратимся для наглядности к находящимся рядом с нами числам.
Пересчитывая что-то мы используем целые (положительные) числа 1, 2, 3… Их еще называют «натуральными». Странные американцы любят начинать этот ряд с нуля (и заразили этим, например, всю вычислительную технику). Их не смущает, что «3-блок» на самом деле 4-ый по счету… Впрочем, нам сейчас все равно! При добавлении или удалении нуля ничего не меняется.
Главное, мы знаем, что чисел нам хватит для пересчета чего угодно. Мы также знаем, что это множество бесконечное. Кантор назвал это множество СЧЕТНЫМ и его мощность – мощностью счетного множества.
Мощность этого множества Кантор взял за эталон и стал сравнивать ее с мощностями других множеств.
Во-первых, он установил, что эта мощность больше мощности любого конечного множества (студентов, березок и т.п.).
Во-вторых, и это любопытно, он доказал, что многие бесконечные множества имеют ту же мощность (то же «количество» элементов), что и счетное. Один из самых поразительных примеров – это то, что множество целых положительных чисел имеет столько же элементов, сколько и множество целых четных положительных чисел! То есть они равномощны!
Действительно, запишем друг под другом:
1 2 3 4…
2 4 6 8…
Ясно, что обе последовательности имеют одинаковое количество элементов, поскольку любому числу первой, ВСЕГДА соответствует строго одно число второй последовательности. Так что вторая последовательность не может исчерпаться раньше первой. И наоборот!
Следовательно, эти множества равномощны!
Следовательно, здесь ЧАСТЬ РАВНА ЦЕЛОМУ!!!
Поскольку это доказано строго, то на последний спасительный аргумент – «так в жизни не бывает», можно еще раз, но уже более сурово ответить: «Вы просто жизни не видели! Точнее, вы никогда не видели в жизни бесконечность! И не увидите!». За свою непростую долгую жизнь человек может столкнуться даже с паровозом, а с бесконечностью – никогда! Даже в темноте.
Поэтому, что может быть и чего не может быть в мире бесконечностей не нам судить, основываясь лишь на житейском опыте!
Из бесконечного множества звезд (мощность которого тоже счетна) мы видим лишь их ограниченное конечное множество. На нарисованном отрезке прямой, содержащем бесконечное множество точек, мы видим конечное множество зерен грифеля, которым отрезок нарисован. Кстати, мы видим все это и многое другое сетчаткой глаза, содержащей конечное число палочек-колбочек. Конечным числом палочек-колбочек своего глаза никогда ничего бесконечного вы не увидите!…
Так что бесконечности вокруг нас существуют в «параллельном мире» по своим законам, которые теория множеств помогает изучать.
Мы уже сказали «во-вторых», но есть еще и «в-третьих» – и это в-третьих\" – самое главное: великая теорема Кантора, которая уже упоминалась.
Дело в том, что если построить множество всех подмножеств конкретного множества, то всегда получите множество БОЛЬШЕ исходного.
Например, возьмем множество из 2-х элементов: РАЗ, ДВА (и обчелся). Подмножествами этого множества будут 4 множества(!):
1) РАЗ, ДВА – (любое множество подмножество самого себя)
2) РАЗ
3) ДВА
4) пустое – (т.е. «обчелся»).
Другой пример: А И Б (сидели на трубе)
Подмножествами этого множества из трех элементов будет 8 множеств:
1) А, И, Б
2) А, И
3) А, Б
4) И, Б
5) А
6) И
7) Б
8) пустое
Из четырех элементов получилось бы 16 элементов. И этот ряд можно бесконечно продолжить, как ряд степеней числа 2.
Так вот, Кантор и доказал, что если взять бесконечное множества счетной мощности, например, множество целых положительных чисел и построить (разумеется, умозрительно) множество, содержащее в качестве элементов все подмножества этого множества, то получим мощность БОЛЬШУЮ, чем счетная мощность. В принципе не существует способа пересчитать (пусть в бесконечности) такое множество. В нем всегда больше элементов. Эта новая большая мощность называется мощностью КОНТИНУУМА.
И снова житейский парадокс. Мощность континуума имеет, например, множество точек прямой или множество действительных чисел, что то же самое. Более того, любой отрезок числовой оси, даже такой малюсенький отрезок, как отрезок от 0 до 1, имеет мощность континуума, то есть на нем больше чисел, чем найдется чисел в счетном множестве. А раз этот отрезок имеет мощность континуума, как и вся (бесконечная) прямая и, естественно, любой ее отрезок, то можно сказать, что на отрезке от 0 до 1 ровно столько же точек, сколько на отрезке прямой от Земли до Юпитера.
Здесь тоже часть равна целому, если и часть, и целое имеют мощность континуума. И все они одинаково больше числа звезд на небе или числа всевозможных алгоритмов…
Для бесконечностей существует очень простая арифметика, которая логически следует из предыдущих разговоров. Сложение двух счетных мощностей дает счетную мощность, а для континуумов – мощность континуума. При вычитании из мощности континуума счетной – в остатке мощность континуума. Но вот если вычитать из континуума континуум или из счетной мощности счетную – всякое может получиться в каждом конкретном случае. Тут запросто можно напрячься и придумать свои иллюстрации.
Однако, не все так просто. Бесконечность остается одной из ключевых категорий философии. И математика здесь подливает масла в огонь, показывая все новые грани этой проблемы. Тем более, если говорить не только о бесконечных, но и о бесконечных упорядоченных множествах. Впрочем, желающие могут почитать книжки об очень красивых вещах с немение красивыми романтическими названиями: «кардиналы и ординалы».
Лекция 3. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ
Говорят операции НАД множествами не потому, что они расположены «над» множествами, а просто так принято. Если НАД вашими волосами колдует парикмахер, это не значит, что результат его манипуляций окажется выше вашей прически. (Но берегитесь хирурга, который проводит операции над больными).
Основных операций всего три. Это меньше, чем в школьной арифметике. Хотя даже это множество операций несколько избыточное. Операции называются ОБ\'ЕДИНЕНИЕ, ПЕРЕСЕЧЕНИЕ и ДОПОЛНЕНИЕ. Чем-то они напоминают школьные операции сложения, умножения и изменения знака. Но эта аналогия приблизительна и опасна, на то она и аналогия.
Начнем с исторической байки.
Аксель Иванович Берг – адмирал и академик, человек со взрывным характером, был одним из первых пропагандистов кибернетики в СССР, когда она еще официально считалась «продажной девкой капитализма». Дискретную математику тогда в технических вузах не изучали из-за полной ее практической бесполезности, а кибернетика уже начинала ею робко пользоваться.
Во время беседы с одним «журналистом по научной тематике», который утверждал, что теория множеств не только не нужна, но и не понятна простому советскому инженеру, Берг прервал беседу и приказал своему шоферу отвести их в ближайший детский садик.
В детском садике дети играли в большом песочнике. Других развлечений в послевоенных садиках было мало. Берг нарисовал в песочнике два больших частично пересекавшихся круга, как это делают со свадебными кольцами на открытках и машинах. (Для тех, кто со свадьбами в жизни не сталкивался, скажем, что с похожим перехлестом рисуют олимпийские кольца).
Далее он сказал: «Пусть в левый круг встанут все, кто любит манную кашу, а в правый – все, кто любит сливовый кисель!». Дети были горазды поесть (послевоенное время голодное), поэтому никто не остался равнодушно стоять в стороне и все забежали в нарисованные круги. Об\'единение всех этих маленьких сладкоежек и есть операция об\'единения теории множеств.
Но, поскольку почти все дети встали в то место, где круги наложились друг на друга, из-за любви к каше и киселю одновременно, то тем самым продемонстрировали понимание физического смысла операции пересечения двух множеств.
«Ну вот! Не знаю как инженеры, а дети понимают смысл операций над множествами!»,– сказал Берг…
Кстати, здесь роль универсума играл весь песочник.
То, что нарисовал на песке Берг, называют сейчас диаграммами Эйлера-Венна. А то, что находилось на песке за пределами каждого из кругов, было дополнением соответствующего множества, то есть множеством элементов универсума, не принадлежащих к числу любителей данного кушанья (там находились Берг с журналистом).
Если рассмотреть внимательно студенческую группу ух-004, то об\'единение множества отличников и спортсменов даст множество под названием «слава группы ух-004». Принципиальное отличие об\'единения множеств от школьного сложения не только в том, что студенты – это не числа и мы их не пересчитываем(!), но и в том, что студенты, которые одновременно отличники и спортсмены, будут учтены один раз. Так что запросто может оказаться, что отличников четыре, а спортсменов двадцать, но их об\'единение под названием «слава группы ух-004» будет содержать всего двадцать два студента.
Ясно, что пересечение этих множеств даст двух студентов, которые одновременно и отличники и спортсмены. Они, скорее всего, девушки, да еще и красавицы, но красота не использовалась здесь в качестве характеристики, по которой выделялись элементы этих множеств…
Когда у математиков появляются в руках об\'екты, а у нас здесь раздолье – любые об\'екты можно брать, и операции – а мы основную тройку тоже обозначили, то математики начинают говорить об АЛГЕБРЕ.
Алгебра множеств как небо и земля отличается от школьной, хотя есть некоторые аналогии. В алгебре множеств есть те же названия законов: КОММУТАТИВНЫЙ, АССОЦИАТИВНЫЙ и ДИСТРИБУТИВНЫЙ (перестановочный, сочетательный и распределительный). Первые два похожи как две капли воды, упавшие с неба на землю. А вот дистрибутивный закон имеет и аналог в школьной алгебре (выражаясь «по-школьному» произведение суммы есть сумма произведений), но имеет и уникальную версию. В теории множеств, если тоже сказать кратко, то пересечение с об\'единением равно об\'единению пересечений и (!) об\'единение с пересечением равно пересечению об\'единений. Второе не имеет аналогии в школьной алгебре:\"Сумма с произведением не равна произведению сумм\".
Проиллюстрируем сказанное:
Коммутативный закон: Об\'единение (пересечение) отличников и спортсменов равно об\'единеию (пересечению) спортсменов и отличников.
Ассоциативный закон: От изменения порядка об\'единения (пересечения) спортсменов, отличников и красавцев результат не меняется.
Дистрибутивный закон (только экзотическая версия): Об\'единение красавцев с пересечением спортсменов и отличников равно множеству, в котором пересекаются об\'единения красавцев и спортсменов с об\'единеием красавцев с отличниками. (В условных обозначениях это было бы гораздо короче и нагляднее, но мы зареклись насчет формул).
Сложновато воспринимается на слух закон поглощения, который, однако, в ряде случаев позволяет упрощать теоретико-множественные конструкции. Пересечение отличников с об\'единением отличников и спортсменов дает множество отличников. Или второй вариант. Об\'единение отличников с пересечением отличников и спортсменов дает множество отличников. Тем не мение, если обдумать сказанное, и поразмахивать руками, то справедливость результатов очевидна.
Есть еще закон, название которого почему-то студентов забавляет – он им, видимо, что то-напоминает. А закон этот смело можно отнести к самым важным законам (свойствам). Это закон ИДЕМПОТЕНТНОСТИ. Об\'единение (пересечение) множества спортсменов с множеством спортсменов дает множество спортсменов.
Очень по-французски звучит ЗАКОН Де Моргана: Дополнение об\'единения отличников со спортсменами равно пересечению дополнения множества спортсменов с дополнением множества отличников. И второй вариант. Дополнение пересечения отличников со спортсменами равно об\'единению дополнения множества спортсменов с дополнением множества отличников. За универсум (для дополнения) можно взять множество студентов группы (или университета, или мира – роли не играет). Возьмите реальных спортсменов с отличниками и убедитесь в справедливости закона.
Очень прост закон ДВОЙНОГО ДОПОЛНЕНИЯ. Дополнение дополнения множества спортсменов есть само множество спортсменов. Персонально для тех, кто успешно продирается через всю нашу словесную казуистику, можем сформулировать ближайшее следствие из этого закона. Дополнение дополнения дополнения множества спортсменов есть дополнение множества спортсменов.
Самыми экзотическими являются два закона: ПРОТИВОРЕЧИЯ и ИСКЛЮЧЕННОГО ТРЕТЬЕГО.
Противоречия: Пересечение множества спортсменов с дополнением множества спортсменов пусто. Действительно, коль скоро в дополнение множества спортсменов входят все остальные студенты неспортсмены, то у этого пересечения не может быть общих элементов.
Исключенного третьего: Об\'единение множества спортсменов с дополнением множества спортсменов совпадает с рассматриваемым универсумом. Действительно, коль скоро в дополнение множества спортсменов входят все остальные студенты неспортсмены из универсума, то это об\'единение как раз и составляет весь универсум.
Остается только высказать сожаление, что не все математики согласны с этими законами. Еще большее сожаление вызывает то, что у них на это есть весьма веские основания… Не менее веские, чем у сторонников законов.
Несогласные себя называют КОНСТРУКТИВИСТАМИ или ИНТУИЦИОНИСТАМИ.
Согласным же ничего не осталось, как назвать самих себя КЛАССИКАМИ… С чем не согласны несогласные.
Лекция 4. СООТВЕТСТВИЯ, ОТОБРАЖЕНИЯ, ОТНОШЕНИЯ
Алгеброй далеко не исчерпывается все то, что можно сделать с множествами…
В математике, как и в жизни, различные об\'екты могут чему-то соответствовать или не соответствовать. Находиться меж собой в определенных отношениях или наоборот – не находится. И основой формализации, если угодно – математизации, здесь также служат множества.
То есть между множествами могут устанавливаться различные СООТВЕТСТВИЯ и ОТНОШЕНИЯ. Более того (а серьезные математики может быть даже сказали бы «прежде всего»), множества нередко могут ОТОБРАЖАТЬСЯ друг в друг друга и даже в самих себя…
Человек может соответствовать профессии, зарплата соответствовать должности, наказание – преступлению, оценка – знаниям.
Глядя на многочисленные примеры вокруг мы замечаем, что для определения конкретного соответствия надо определить два множества: множество (область) определения и множество (область) значений. А также определить «пары соответствий». Например, область определения – группа ух-005, сдающая экзамен; область значений – отл, хор, уд, неуд – множество оценок. И множество пар Иванов – отл, Петров – хор, Сидоров – отл. А Хведоров – не явился. Вот вам и готовое соответствие.
Соответствия обладают свойствами.
1. В данном случае соответствие НЕ-ВСЮДУ-ОПРЕДЕЛЕННОЕ, поскольку для Хведорова в этом соответствии нет пары. (Даже если бы мы написали в ведомости Хведоров – н/я, то это все равно бы не попало в соответствие, поскольку «н/я» нет в множестве допустимых значений!). Если бы деканат своевременно исключил из ведомости Хведорова, как отчисленного, то это соответствие стало бы ВСЮДУ-ОПРЕДЕЛЕННЫМ
2. Соответствие ФУНКЦИОНАЛЬНО, поскольку каждому студенту соответствует не более одной оценки. Такое соответствие называют по-простому, ФУНКЦИЕЙ. В данном случае из-за Хведорова это не всюду определенная функция. Никакой разницы со школьной функцией кроме той принципиальной, что здесь аргументами и значениями могут быть не только числа, а любые об\'екты. Кстати, не всем математикам нравится такое определение функции, хотя оно абсолютно строгое. Просто сказывается ревность к множествам с позиций некоторых других разделов математики.
Если бы за один экзамен студенты могли получать несколько оценок, то соответствие было бы НЕФУНКЦИОНАЛЬНЫМ. То есть не было бы функцией. (Оно было бы «многозначной [недетерминированной] функцией», но это уже другая математика). Да и в жизни так не бывает.
3. Данное соответствие НЕИН\'ЕКТИВНО, поскольку отл получил более, чем один студент. Если бы Сидоров, из-за фатальной предрасположенности к несчастьям, получил не отл, а уд (или неуд), то соответствие было бы ИН\'ЕКТИВНЫМ… Получение студентами олимпийских медалей за победу в беге на 100 метров было бы примером ин\'ективного соответствия.
4. Данное соответствие НЕСЮР\'ЕКТИВНО, поскольку на экзамене были использованы не все возможные оценки. На реальных экзаменах обычно бывает задействован весь возможный спектр оценок, поэтому это соответствие бывает «по жизни» СЮР\'ЕКТИВНЫМ. Естественно, сюр\'ективно в даный момент приобретение билетов на Витаса.
5. Соответствие, которое одновременно ВСЮДУ-ОПРЕДЕЛЕНО, ФУНКЦИОНАЛЬНО, ИН\'ЕКТИВНО и СЮР\'ЕКТИВНО называется БИЕКТИВНЫМ. Еще его называют ВЗАИМНО-ОДНОЗНАЧНЫМ, но так звучит менее красиво. Говорят, что самый убедительный пример биективного соответствия головы на плечах. Возьмите множество голов, множество плеч и убедитесь во всех четырех свойствах. Криминальные варианты не предлагать!
Выделение соответствий в отдельную категорию предложили европейцы, а точнее французы, а еще точнее, Николя Бурбаки (это французский Козьма Прутков, состоявший из математиков интеллектуалов). Американская школа считает соответствия частным случаем отношений. А у нас разговор про отношения отдельный – так легче разложить все по полочкам. Так что пришла пора поговорить об отношениях.
В математике, как и в жизни, различные об\'екты могут иметь какое-то отношение к другим об\'ектам или не иметь.
Родственные отношения, дружеские отношения, дипломатические отношения, равноправные отношения.
Глядя на многочисленные примеры вокруг, мы замечаем, что отношения отличаются от соответствий тем, что определяются на одном множестве. Бессмысленно бы было говорить об отношениях между студентами и оценками. О дипломатических, родственных или любых других отношениях между должностью и зарплатой. Для определения конкретного отношения надо определить множество, и пары, для которых имеет место данное отношение.
Например, на множестве людей отношения «быть братом», «учиться в одной группе» или «быть выше ростом».
Отношения, в силу специфики, характеризуются иным перечнем свойств, нежели соответствия.
1. РЕФЛЕКСИВНОСТЬ. Это когда отношение обращено на себя. Ранее уже рассматривалось отношение включения. Поскольку любое множество включено само в себя, то отношение включения обладает свойством рефлексивности. Если верить народной мудрости, то и отношение «спасения» на множестве утопающих – рефлексивно.
2. АНИТИРЕФЛЕКСИВНОСТЬ. Это когда отношение к самому об\'екту (всегда) неприменимо. Например, «перпендикулярность» на множестве прямых. Прямая не может быть перпендикулярна самой себе.
3. СИММЕТРИЧНОСТЬ. Если Иванов «учится в одной группе» с Петровым, то и обратное справедливо. Если прямая А «перпендикулярна» прямой B, то и обратное справедливо.
4. АНТИСИММЕТРИЧНОСТЬ. Если тысячу рублей можно «разменять» сотнями, то обратное не под силу даже фокуснику. Мрачноватый, но очень точный пример: «носить траур по кому-то»…
5. ПОЛНОТА. Это самое сложное свойство, поскольку, в отличие от всех остальных, оно прежде всего «направлено» на само множество. Полнотой обладает отношение, которое для любой пары разных элементов данного множества выполнимо хотя бы «в одну сторону». Например, полнотой обладает отношение «больше» для множества действительных чисел, ибо для двух разных действительных чисел одно обязательно больше другого. Но если мы к действительным числам добавим комплексные, то свойство полноты исчезнет. Если хотя бы одно из сравниваемых чисел будет комплексным, сравнение на «больше»-\"меньше\" теряет смысл.
6. ТРАНЗИТИВНОСТЬ. Если Иванов «учится в одной группе» с Петровым, а Петров с Сидоровым, то Иванов «учится в одной группе» с Сидоровым. Отношение включения тоже транзитивно. Если группа «включена» в множество студентов университета, а это множество «включено» в множество студентов страны. То множество студентов группы «включено» в множество студентов страны. Можно продолжить эту цепочку включений, прихватив галактику. И вот тут опять подводный камень казуистики!
Если студенческую группу рассматривать как элемент университета – множества, состоящего из групп, а университет элемент высшей школы – множества, состоящего из университетов, то группа не является элементом высшей школы (там элементы университеты). То есть отношение «принадлежности» нетранзитивно. «Вассал моего вассала -…»
Вернемся к функциональному соответствию (то есть к функции). Если это соответствие к тому же еще и всюду-определено, то оно называется ОТОБРАЖЕНИЕМ.
Если отобразить множество студентов в группе, на множество фамилий в группе, То это скорее всего будет ОТОБРАЖЕНИЕ множества студентов НА множество фамилий. То есть сюр\'ективное соответствие. Если же отобразить множество студентов группы на множество фамилий студентов университета, то говорят, что имеет место ОТОБРАЖЕНИЕ множества студентов В множество фамилий. То есть в области значений будут и «незадействованные фамилии».
Мы подошли к одному из самых фундаментальных, может потому и неблагозвучных, понятий и теории множеств, и математики вообще, мы подошли к ГОМОМОРФИЗМУ.
Пример. Отобразим множество точек участка земной поверхности на множество точек карты. Сейчас оставим в стороне то, что некое множество точек земной поверхности отобразится в одну точку на карте, в таких случаях неин\'ективность – обычное дело. Для нас существенно то что, чем выше точки земной поверхности над уровнем моря, тем в более коричневые точки карты они отображаются.
Таким образом, мы рассматриваем не просто множества элементов. В первом случае здесь между элементами множества существует отношение «выше», а во втором – «коричневее». Где выше в первом – там коричневее во втором. «Выше» и «коричневее» – это отношения заданные на своих множествах.
Отображение земной поверхности НА карту не просто ставит всем элементам одного множества элементы другого. Но, кроме того, если между двумя элементами первого множества существует отношение «выше», то между их образами во втором множестве имеет место отношение «коричневее». Естественно, если точки земной поверхности лежат на одной высоте, то они отобразятся в точки карты с одинаковой коричневостью.
Такое отображение называется ГОМОМОРФНЫМ. Или говорят, что между этими множествами существует ГОМОМОРФИЗМ.
Вернемся к тому, что слово не очень благозвучное, а по американским меркам и громоздкое. Поэтому последнее время все чаше используется более короткий (усеченный) термин – МОРФИЗМ.
Морфизмы играют в математике исключительную роль. Коль скоро математику не без оснований часто отождествляют с математическим моделированием, то приведем афоризм из одной умной философской книжки: ХОРОШАЯ МОДЕЛЬ ВСЕГДА ГОМОМОРФНА.
Афоризм в конце лекции провоцирует размышления. Чего бы и хотелось добиться…
Лекция 5. ОСОБЫЕ ОТНОШЕНИЯ
Каждое конкретное отношение обладает сразу совокупностью свойств. Полезно исследовать группы отношений, у которых совокупности свойств одинаковые.
Прежде всего к таковым относятся отношения ЭКВИВАЛЕНТНОСТИ. Это отношения, которые одновременно обладают свойствами рефлексивности, симметричности и транзитивности. Отношение «равенства» чисел – самый простой пример эквивалентности. Или «учиться в одной студенческой группе».
Интересно, что каждый об\'ект эквивалентен сам себе хотя бы потому, что для самого невероятного об\'екта, который ни на что не похож, по отношении к самому себе выполняются рефлексивность, симметричность и транзитивность. Обычно же об\'екты не столь уникальны и имеют место множества (любят говорить КЛАССЫ) эквивалентных между собой об\'ектов.
Самое важное свойство отношения эквивалентности (то есть свойство отношения, которое само определено с помощью трех вышеупомянутых свойств) покажем на примере. Если взять первозданный хаос, то есть все множество студентов университета, которые болтаются по коридорам, сидят в буфете или в аудиториях, а еще лучше дома или вообще неизвестно где, то отношение «учиться в одной группе» РАЗБИВАЕТ это множество на подмножества-группы. Каждый студент принадлежит какой-то группе и не может принадлежать сразу двум. (В реальной жизни возможны исключения из этих очевидных свойств, но мы по умолчанию рассматриваем лишь нормальных студентов).
В качестве лабораторной работы по разбиению рекомендуется разбить тарелку. Желательно, из китайского фарфора. А потом созерцать осколки, каждый из которых будет для фарфоринок классом эквивалентности применительно к отношению «принадлежать одному и тому же осколку»… Это лучше, чем разбивать группы, тем более, что ортодоксальные алгебраисты под «группой» понимают не кучу студентов, а нечто фундаментальное математическое… Но это уже начало другой романтической истории про молоденького французского гения и (увы) дуэлянта – Эвариста Галуа.
Заметную роль в математике играют и отношения ПОРЯДКА, обладающие свойствами транзитивности и антисимметричности. Нарушение любого из них нарушает порядок не только с точки зрения математики, но и здравого смысла.
Примеры. «Быть больше» на множестве чисел, «быть после» в очереди, «быть старше по званию» в армии.
Дополнительно, если порядки обладают свойством полноты, то их называют СОВЕРШЕННЫМИ. Например, «больше», на множестве действительных чисел.
Если отношение еще и рефлексивно, то порядок называют НЕСТРОГИМ (ЧАСТИЧНЫМ). Например, «выть выше или равного роста». А предыдущие три примера – это отношения СТРОГОГО (ЛИНЕЙНОГО) порядка, поскольку в них имеет место антирефлексивность.
Отрадно то, что теоретико-множественные отношения порядка как правило совпадают с житейским представлением об упорядочении. Но не всегда. Знаменитое отношение «быть братом» с одной стороны очень похоже на отношение порядка. Иван брат Марьи, но Марья не брат Петра – вроде(!) антирефлексивность. Если Иван брат Петра, а Петр брат Марьи, то Иван брат Марьи. Вроде бы(!) транзитивность. Но, если Иван брат Петра, то и Петр брать Ивана – то есть с анитисимметричностью все-таки не получается. Хуже того, если Иван брат Петра, а Петр брать Ивана, то по свойству транзитивности придем к заключению, что Иван брат Ивана. А чтобы не возникал такой абсурдный результат, отношение «быть братом» признается нетранзитивным.
Более интересными являются другие отношения, очень похожие на отношения порядка. Например, «быть немного выше ростом». Это антисимметричное, но нетранзитивное отношение. Иван немного выше ростом Петра, Петро немного выше ростом Егора. Но Иван намного выше ростом Егора. Отношения, похожие на отношения порядка, но не обладающие свойством транзитивности, называют отношениями ТОЛЕРАНТНОСТИ. Хорошей иллюстрацией этого отношения служат многие известные картинки Эшера, где, например, ящерицы «плавно» превращаются в птиц и т.п.
Отношения частичного порядка, то есть рефлексивные, антисимметричные и транзитивные, на которые накладывают ряд дополнительных свойств, изучаются в рамках раздела математики с экзотическим названием ТЕОРИЯ РЕШЕТОК. Это название пугает, поэтому в нашей стране первоначально слово lattice переводили как \"структура\". Но когда в математике все шире стал употребляться термин structure, то пришлось ему отдать русское слово структура, а решетки стали и у нас в стране решетками.
Можно предположить, что название «решетки» возникло в связи с использованием так называемых диаграмм Хассе, которые может и напоминают экстравагантные решетки для окон… Но мы договорились без формул, а тем более без рисунков. Рисунки, в отличие от формул, народ любит. Но рисовать картинки в Ворде еще противнее, чем формулы, поэтому постараемся, насколько, конечно, возможно, компенсировать и их красноречием…
Начнем с примеров решеток.
Возьмем слова: о, ор, вор, ворот, кол, олово, коловорот, и упорядочим их по вхождению одних слов в другие (не забывая, что каждое слово входит в само себя). Это будет наша первая решетка.
Можно убедиться, что здесь выполняются все свойства частичного порядка. А о дополнительных свойствах поговорим позже.
Числа: 1, 2, 3, 4, 6, 9, 12, 18, 36 с отношением делить нацело, так же образуют решетку.
Обычные действительные числа с отношением «больше или равно» дают одну из самых распространенных решеток. Хотя для нас она менее экзотическая. Можно сказать, простая как бревно…
Множество всех подмножеств какого-то множества с отношением включения также дает решетку, причем, с рядом замечательных свойств.
Для определения решетки договоримся называть элемент НАИБОЛЬШИМ (НАИМЕНЬШИМ), если он больше (меньше) любого другого элемента частично-упорядоченного множества – кратко ЧУМ. За математиками иногда можно заметить педантичность до занудства, а иногда непонятную приблизительность. Строже и точнее было бы здесь и далее, вопреки сложившейся традиции, применительно к ЧУМ, обладающим свойством рефлексивности, говорить «больше или равно» \"НАИБОЛЬШИЙ ИЛИ РАВНЫЙ\" и т.п. Но мы тоже будем говорить кратко «больше», подразумевая эти более длинные и точные словосочетания. Наибольший элемент, если таковой существует – единственный. На то он и наибольший. С наименьшим все аналогично.
МАКСИМАЛЬНЫМ (МИНИМАЛЬНЫМ) называется элемент ЧУМ, больше (меньше) которого в этом множестве нет элементов. На первый взгляд это определение повторяет предыдущее. Но максимальных элементов в ЧУМ может быть и несколько. Если рассматривать современный мир, упорядоченный по этажам власти, то все главы государств «максимальны», но каждый в своей стране, поскольку главнее его нет. Но каждый из них не главнее другого главы. Главы всей планеты не существует и даже Генсек ООН его не заменит. Если бы, следуя фантастическим романам, существовал глава Земли, то он был бы и максимальным и наибольшим элементом.
Если, далее, возьмем множество студентов потока и наведем в нем частичный порядок. Имеется в виду не «всеми доступными средствами», а лишь отношением «учится лучше (или одинаково)», считая, что ради такого дела можно для любых двух студентов решить, который лучше… Из этого множества выделим группу ух-005 и найдем студентов потока, которые учатся лучше всех студентов группы ух-005. То есть найдем на потоке студентов, «наибольших» для этой группы. Таких студентов может оказаться несколько, если только «наибольший» студент группы не является одновременно наибольшим элементом всего потока. Такое множество наибольших элементов называется множеством МАЖОРАНТ. Рассматривая наименьших студентов, получим множество МИНОРАНТ. А теперь в самом множестве мажорант (минорант) найдем наименьший (наибольший) элемент [это не опечатка!]. Для данного примера это будут лучший и худший студенты самой группы ух-005. Такие элементы называются соответственно СУПРЕМУМ и ИНФИМУМ. Или кратко, sup и inf.
Для множества чисел 1, 2, 3, 4, 6, 9, 12, 18, 36 с отношением делить, возьмем подмножество чисел 3, 6, 9. Для него множество мажорант будет 12, 36. Множество минорант – 3, 1. супремум – 12, инфимум – 3.
РЕШЕТКОЙ называется ЧУМ, в котором для любого непустого подмножества существуют супремум и инфимум.
Решетки, которые получаются как множества подмножеств данного конечного множества, с отношением включения, относятся к БУЛЕВЫМ РЕШЕТКАМ. Для тех, кто знают про булеву алгебру, добавим, что традиционная булева алгебра есть решетка из двух элементов: «истина», «ложь», с отношением порядка «более истинный».
Определить решетку можно и «алгебраически». Если для элементов множества с отношением частичного порядка (частично-упорядоченным множеством) выполняются законы коммутативный, ассоциативный, поглощения и идемпотентности, то такое частично-упорядоченное множество называется решеткой.
Если, кроме того, выполняется дистрибутивный закон – то решетка называется дистрибутивной.
Тут уж поверьте на слово – с помощью решеток решен ряд важных проблем. В том числе и теоретического программирования.
Лекция 6. МАТЕМАТИЧЕСКАЯ ЛОГИКА (БЕССМЫСЛЕННАЯ ЛОГИКА)
Обычно, настоящие математики не приспособлены к жизни. Посмотрите на них, если имеете возможность. Они где-то витают… Казалось бы, следует сделать исключение для логиков. Хотя бы потому, что поступки логиков должны быть наиболее логичны. Как бы не так! Все как раз наоборот! На самом-то деле логика строго оговаривает свои «правила игры» и действует пунктуально до беспощадности, граничащей с идиотизмом, в рамках этих правил. При этом их логика с «логикой жизни» имеет не больше общего, чем вы найдете общего в шахматной и Бородинской битвах… Но все-таки есть что-то похожее… Когда страсти с обеих противоборствующих сторон накаляются и дело доходит до рукопашной!…
Кстати, основной клоунский прием: с фанатичным исступлением совершать некие формально логичные, но с точки зрения жизненной реальности абсурдные до идиотизма, действия. Всем, прежде всего детям, очевиден полный идиотизм происходящего, но клоун продолжает поступать ЛОГИЧНО! И ничто не в силах свернуть его с этого пути.
Вообще-то всяких разных логик много. Выражаясь более конкретно – бесконечно много. Поэтому будем говорить не о логике вообще, как это любят делать в некоторых учебниках для юристов, а о математической логике. Тем более, что логики у юристов часто даже меньше, чем у политиков… А от политики предпочтительно держаться подальше… Математическая логика понятие тоже достаточно неконкретное, из-за того, что математических логик также бесконечно много. Здесь будем обсуждать некоторые из них, отдавая больше дань традиции, чем здравому смыслу. Поскольку, весьма возможно, в этом и заключен здравый смысл… Логично?
Математическая логика учит логично рассуждать не больше, чем любой другой раздел математики. Это связано с тем, что «логичность» рассуждений в логике определяется самой логикой и корректно может использоваться только в самой логике. В жизни же мы, размышляя логически, как правило используем разные логики и разные методы логических рассуждений, безбожно перемешивая дедукцию с индукцией… Более того, в жизни мы строим свои рассуждения исходя из противоречивых посылок, например, «Не откладывай на завтра, что можно сделать сегодня» и «Поспешишь людей насмешишь». Нередко бывает, что непонравившийся нам логический вывод приводит к пересмотру исходных посылок (аксиом).
Пожалуй, настало время сказать про логику, возможно, самое главное: классическая логика не занимается смыслом. Ни здравым, ни каким другим! Для изучения здравого смысла, между прочим, существует психиатрия. Но в психиатрии логика скорее вредна. Хотя, например, так называемые репертуарные решетки и говорят о некоторых успехах в этом направлении…
Разумеется, размежевывая логику со смыслом, имеем в виду прежде всего классическую логику и житейское понимание здравого смысла. Нет запретных направлений в математике, поэтому исследование логикой смысла, и наоборот, в различных видах присутствует в ряде современных ответвлений логической науки. (Хорошо сложилось последнее предложение, хотя определить термин «логическая наука» не возьмусь даже приблизительно).
Смыслом, если угодно – семантикой, занимается, например, теория моделей. Да и вообще, термин семантика часто заменяют термином интерпретация. И если мы согласимся с философами, что интерпретация (отображение!) об\'екта есть осмысление его в некотором данном аспекте, то пограничные сферы математики, которые могут привлекаться для наступления на смысл в логике, становятся неохватными!
В практическом плане семантикой вынуждено интересоваться теоретическое программирование. А в нем, кроме просто семантики, есть и операционная, и денотационная, и процедуральная и т.д. и т.п. семантики…
Еще лишь упомянем апофеоз – ТЕОРИЮ КАТЕГОРИЙ, которая довела семантику до формального малопонятного синтаксиса, где смысл уже настолько простой – разложенный по полочкам, что до него простому смертному совсем невозможно докопаться… Это для избранных.
Так чем же занимается логика? Хотя бы в самой классической ее части? Логика занимается только тем, чем она занимается. (А это она определяет предельно строго). Главное в логике – это строго определиться! Задать аксиоматику. А дальше логические выводы должны быть(!) в значительной степени автоматическими… Другое дело рассуждения по поводу этих выводов! Но эти рассуждения уже вне рамок логики! Поэтому в них требуется строгий математический смысл!
Может показаться, что это простая словесная эквилибристика. НЕТ! В качестве примера некоторой логической (аксиоматической) системы возьмем известную игру 15. Зададим (перемешаем) начальное расположение квадратных фишек. Далее игрой (логическим выводом!), а конкретно – перемещением фишек на свободное место, может заниматься некое механическое устройство, а вы можете терпеливо смотреть и радоваться, когда в результате возможных передвижек в коробочке сложится последовательность от 1 до 15. Но никто не запрещает контролировать механическое устройство и подсказывать ему, ИСХОДЯ ИЗ здравого СМЫСЛА правильные перемещения фишек, чтобы ускорить процесс. А может быть даже доказать, используя для логических рассуждений, например, такой раздел математики, как КОМБИНАТОРИКА, что при данном начальном расположении фишек получить требуемую финальную комбинацию невозможно вообще!
Не больше здравого смысла присутствует и в той части логики, которую называют ЛОГИЧЕСКОЙ АЛГЕБРОЙ. Здесь вводятся ЛОГИЧЕСКИЕ ОПЕРАЦИИ и определяются их свойства. Как показала практика, в некоторых случаях законы этой алгебры могут соответствовать логике жизни, а в некоторых нет. Из за такого непостоянства законы логики нельзя считать законами с точки зрения практики жизни. Их знание и механическое использование может не только помогать, но и вредить. Особенно психологам и юристам. Ситуация осложняется тем, что наряду с законами алгебры логики, которые то соответствуют, то не соответствуют жизненным рассуждениям, есть логические законы, которые часть логиков категорически не признают. Это относится прежде всего к так называемым законам ИСКЛЮЧЕННОГО ТРЕТЬЕГО и ПРОТИВОРЕЧИЯ. Более подробно о них поговорим потом.
Лекция 7. ОПЕРАЦИИ НАД ВЫСКАЗЫВАНИЯМИ
Обычно математическую логику начинают изучать с АЛГЕБРЫ ВЫСКАЗЫВАНИЙ и вспоминают при этом Дж. Буля, отца Лилиан Войнич, написавшей роман «Овод». А сам Буль, как незакомлексованный математической эрудицией любитель, пытался придумать математику, которая бы описывала мыслительные процессы. Собственно, с его «алгебры» и ведут историю современной математической логики.
Кстати, многие математики эту алгебру не считают логикой.
Под ВЫСКАЗЫВАНИЕМ понимают повествовательное предложение, относительно которого можно сказать, истинно оно или ложно. Например, «Волга впадает в Каспийское море», «Квадрат гипотенузы равен сумме квадратов катетов», «Наполеон родился в Кудымкаре». Здесь два первых высказывания истинны, а третье – ложно. Разумеется, жизнь и тут иногда создает проблемы. Так, про высказывание насчет Волги можно сказать, что оно истинное, если ЗНАТЬ этот факт из географии. Мне, например, пришлось как-то в Америке рассказывать одному бизнесмену, что далеко от США есть такая большая река – Волга… Да и про квадрат гипотенузы не все могут высказаться определенно… Но договоримся, недоучек не принимать в расчет. Или еще проще, чтобы не утонуть в несущественных для данного обсуждения мелочах, будем считать высказываниями повествовательные предложения, истинность которых может установить «высший разум».
Но этим проблема не исчерпывается. Повествовательное предложение «Я лгу» не является высказыванием, поскольку если оно истинно (то есть я действительно лгу) – значит я не лгу, а говорю правду! И наоборот… Это пример ЛОГИЧЕСКОГО ПАРАДОКСА.
Логические парадоксы не относятся к высказываниям. К высказываниям не относятся также вопросительные и восклицательные (т.е. неповествовательные) предложения и определения. Говорить об истинности или ложности определений бессмысленно. Определение есть соглашение о названии. Например, «Назовем эту музыку гимном». И все тут!…
Для того, чтобы не писать \"истина\" и \"ложь\" (\"true\" и \"false\") часто используют лишь начальные буквы этих слов. А еще чаще просто \"1\" и \"0\".
А теперь вернемся к самому существенному. Логика высказываний не занимается (и даже не интересуется) СМЫСЛОМ высказываний. Так что в этом смысле логику можно считать БЕССМЫСЛИЦЕЙ! Один из логиков-классиков уподобил алгебру логики рентгену, который, просвечивая высказывание, оставляет математику для рассмотрения только его истинность.
В алгебре высказываний можно обойтись двумя-тремя операциями, хотя обычно рассматривают больше. Операцию ДИЗ\'ЮНКЦИЯ называют еще \"логическим или\". Если два высказывания соединить диз\'юнкцией, то получится сложное высказывание которое истинно, если истинно хотя бы одно из входящих в него высказываний. То есть следует уточнить, что это \"неисключающее или\". Например, «Мы любим пиво или мы любим мороженое» истинное сложное высказывание, поскольку хотя бы одно из входящих в него элементарных высказываний истинно. А возможно, и оба. Представить же себе живое существо, которое не любит и пиво, и мороженое, не позволяет фантазия.
Операцию КОН\'ЮНКЦИЯ называют еще \"логическим и\". Сложное высказывание будет истинно, если истинны оба входящих в него высказывания.
Операция ОТРИЦАНИЕ – \"логическое не\" – истинное высказывание превращает в ложное и наоборот.
Пожалуй, самая интригующая операция – это ИМПЛИКАЦИЯ или \"логическое если…, то\". Например, «Если Наполеон родился в Кудымкаре, то газ при нагревании сужается». Это, кстати, истинное высказывание! Нет причин считать его ложным. Единственная ситуация, когда импликация ложна, это когда посылка (часть «если») истинна, а следствие (часть «то») ложна.
Еще интереснее с точки зрения здравого смысла то, что импликацию иногда (не совсем корректно по иным причинам!) называют операцией логического следования, хотя наш пример показывает, что высказывания могут логически не следовать одно из другого, более того, могут не иметь между собой никакой логической связи. Напомним, импликация, как и другие операции, берет в расчет только истинность входящих в нее высказываний.
«Если Волга впадает в Каспийское море, то 2 + 2 = 4» истинное высказывание.
«Если Волга впадает в Каспийское море, то 2 + 2 = 5» ложное высказывание.
Хотя оба эти «логические рассуждения» с точки зрения здравого рассуждения одинаково бессмысленны.
Есть также ЛОГИЧЕСКАЯ ЭКВИВАЛЕНТНОСТЬ или \"тогда и только тогда« (кстати, воспользовавшись»американским приемом\", можно записать короче – \"ттогда\"). Результирующее сложное высказывание истинно, если одновременно истинны или ложны оба входящих в него высказывания.
Назовем еще одну операцию, ШТРИХ ШЕФФЕРА или логическое \"и-не\". Результат этой операции равносилен последовательному применению операций кон\'юнкции и отрицания. Соответственно, результирующее высказывание будет ложным, только если входящие в него высказывания одновременно истинны. Штрих Шеффера – это операция замечательная тем, что ее одной (необходимое количество раз примененной) достаточно, чтобы записать любое сложное высказывание.
При использовании логики для проектирования логических схем, например отдельных фрагментов процессора, первоначально эксплуатировали аналогию с релейными схемами. Операция диз\'юнкции (\"или\") соответствует параллельному подключению контактов реле, кон\'юнкции (\"и\") – последовательному. Операция отрицания (\"не\") моделируется нормально замкнутым контактом реле. То есть контакт размыкается при срабатывании реле. Разумеется, все это реализовывалось в полупроводниковом «модульном» варианте. Тогда достаточно было выпустить, например, модули типа «и-не», чтобы на них реализовать любую схему. (А сам процессор был размером со шкаф, но не по вине логики).
Лекция 8. АЛГЕБРА ВЫСКАЗЫВАНИЙ
В этой алгебре об\'ектами служат высказывания, о которых мы уже поговорили. Операции над высказываниями также обсудили. Осталось поговорить об их свойствах или законах, чтобы определится наконец с алгеброй.
Если использовать только три первых логических операции: диз\'юнкцию, кон\'юнкцию и отрицание, то алгебра высказываний аналогична алгебре множеств. Аналог диз\'юнкции – об\'единение, кон\'юнкции – пересечение, а отрицания – дополнение. Эти аналогии можно использовать для одного из возможных об\'яснений смысла логических операций (это, так называемая, теоретико-множественная интерпретация – и она достаточно «естественна»). Но мы ограничимся формальным подходом. А в связи с этим напомним, что нами были названы еще импликация, эквивалентность и штрих Шеффера, аналогов которым в теории множеств мы не стали искать.
Однако эти операции можно выразить через первые три.
Импликацию можно представить иначе, если взять диз\'юнкцию отрицания первого высказывания со вторым. То есть с точки зрения формальной логики равносильны высказывания:
\"ЕСЛИ стоит хорошая погода, ТО мы купаемся\" и
\"НЕВЕРНО, что стоит хорошая погода, ИЛИ мы купаемся\".