Приветствую!
Все, кто когда-либо интересовались трёхзначной логикой, троичной системой счисления или архитектурой троичных компьютеров, рано или поздно натыкались на труды Брусенцова Николая Петровича, в особенности три его самые известные книги:
Брусенцов Н.П. Начала информатики, 1994.
Брусенцов Н.П. Искусство достоверного рассуждения. Неформальная реконструкция аристотелевой силогистики и булевой математики мысли, 1998.
Брусенцов Н.П. Блуждание в трёх соснах (Приключения диалектики в информатике), 2000.
Для тех, кто не в курсе, Брусенцов Николай Петрович - главный конструктор первой в мире и Советском Союзе троичной ЭВМ "Сетунь". Об этом хорошем человеке можно найти достаточно много информации в открытых источниках. Но сейчас речь не о нём, а о разработанной им алгебре совокупностей (алгебре дизъюнктов), которая фигурирует в качестве фундамента во всех 3-х упомянутых выше книгах. К слову сказать, сами книги не являются учебниками по чистой математике или информатике. Они освещают проблемы злоупотребления формализмом в современной математической логике, а также содержат пути к возрождению и развитию аристотелевой силогистики. Мотивацией к написанию данной статьи послужило то, что каждую книгу пришлось прочитать раза по три, прежде чем в голове сложилась более или менее цельная картина. Этому также поспособствовало обилие терминологии, более присущей философским трактатам, нежели учебникам по математике. Поэтому цель данной статьи - получить представление об этой алгебре и облегчить чтение вышеуказанных книг. Статья носит обзорный характер, знакомит читателя с некоторыми понятиями (акценты расставлены жирным шрифтом) и пытается ответить на вопросы, неосвещённые в книгах явно. Начну издалека...
Аннотация
Любой студент, который начинал изучать дискретную математику, замечал некоторое сходство теории множеств (алгебры множеств) с булевой алгеброй (алгеброй логики). Самый яркий пример сходства - законы де Моргана.
- в теории множеств;
- в булевой алгебре;
(
и
- дополнение подмножества до множества и булево отрицание)
Строгое включение подмножества в большее множество по смыслу схоже с булевой импликацией, которую повсеместно используют в матлогике в качестве вывода следствий. Действиетельно, при
можно сказать, что если элемент принадлежит множеству A, то он однозначно принадлежит и множеству B (здесь намеренно указано строгое включение, а не обычное
).
Сюда также можно отнести и законы поглощения для 0 в булевой алгебре и
, которые в алгебре множеств выглядят идентично для пустого множества
и
.
Само же булево отрицание используется как отрицание-дополнение, наподобие дополнения подмножества до множества, которое его включает.
Глядя на всё это студент думает, что хорошо бы эти 2 алгебры как-нибудь объединить. Дальнейшее изучение предмета приводит его к теореме Стоуна об изоморфизме булевых алгебр. Мы не будем останавливаться на этой теореме, ведь для её понимания нужно на множестве вводить отношение порядка, точные верхнюю и нижнюю границу, понятие решётки, и др.. Смысл в том, что при некоторой иерархии вложенных друг в друга множеств, операции для этих множеств мы можем трактовать как
и
для 0 и 1, потому что свойства (или аксиомы алгебры) сохраняются. Мы получаем из алгебры множеств любую изоморфную алгебру логики. Любознательный студент в очередной раз убедится, что всё уже открыто до него, и на этом успокоится.
Но можно ли назвать такое объединение удовлетворительным? Ведь мы не получили ни каких новых выразительных средств в алгебре от замены одних операций другими. Давайте рассмотрим обе фундаментальные теории подробнее.
Булева алгебра
Любая законченная математическая теория имеет 2 составляющие: синтаксис и семантику. Читая учебники по булевой алгебере, авторы в первую очередь ставят акцент на основные тождества:
- коммутативность коньюнкции;
- коммутативность дизъюнкции;
- идемпотентность коньюнкции;
- идемпотентность дизъюнкции;
- законы поглощения для 0 и 1;
На основе них можно доказать:
- закон противоречия;
- закон исключённого третьего;
- закон двойного отрицания;
законы поглощения;
законы ассоциативности;
законы дистрибутивности;
законы де Моргана;
и т.д.
Всё это относится лишь к синтаксису, т.е. к правильному построению формул внутри данной теории. Семантике же, смыслу (зачастую физическому), трактовке выражений булевой алгебры уделяется крайне мало текста почти во всей современной литературе. Часто можно встретить указания на то, что связки и
трактуются как разговорные "и", "или" и "не", либо их воспринимают как функции минимума и максимума для значений 0 и 1. И в том и в другом случае акцент делается на таблицах истинности.
Но успешное использование логики предполагает отчётливое и верное понимание смысла связок, которое не равносильно механическому запоминанию таблиц истинности или формальному знанию тождеств-законов алгебры.
Брусенцов Н.П.
Т.е. ни таблицы истинности, ни свойства коммутативности или идемпотентности не являются смыслом теории.
На самом деле семантика основных булевых связок достаточно проста и элегантна.
Коньюнкция (от латинского conjunctio - соединение) наиболее точно раскрывается словами "совмещение", "сочетание", причём это такое совмещение или сочетание критериев и атрибутов, что они совместно характеризуют нечто, образуя составной критерий или атрибут. Т.е. совместность и
- это образование совмещённого атрибута
. Если мы провозгласим данность атрибута
через равенство
, это значит, что первоначальные атрибуты
и
даны с необходимостью совместно. Т.е. не может быть такого, что один дан, а второй исключён, или исключены оба. Пример: если дан квадрат, то с необходимостью даны его атрибуты - равноугольность и равносторонность.
Дизъюнкция (от латинского disjunctio - разобщение, разделение, разъединение) - такая же связка, как и коньюнкция, но менее строгая. Она означает, что при её данности первоначальные атрибуты не могут быть исключены совместно. Т.е. если дана дизъюнкция , то по меньшей мере один из атрибутов дан, но не может быть такого, что исключены оба. Пример: если дана хорошая погода, которая солнечная или безветренная, то это значит, что для данности такой погоды нет необходимости в совместной данности обоих атрибутов (она может быть, а может и не быть), но не может быть так, чтобы погода была несолнечная и ветреная одновременно.
Отрицание же, как было сказано выше, рассматривается как отрицание-дополнение до той части универсума, которая не совместна с отрицаемым выражением. Поясню на примере. Не друг - это любой человек, который не является другом. По правилам булевой алгебры мы не можем однозначно сказать, что этот человек именно недруг (враг) или просто хороший знакомый, который не входит в круг друзей. Такое отрицание передаёт суть законов де Моргана (синтаксис позволяет опускать значокнаподобие умножения в арифметике):
Как мы видим, атрибут не совместим c составным атрибутом в правой части равенства. Такое отрицание называют контрадикцией или противоположностью по противоречию. В общепринятом понимании противоречие - это как раз та самая несовместимость атрибутов. Противоречивый атрибут
не присущ ни какой вещи. Но Аристотель подразумевал частный случай такого противоречия, а именно противоположность без промежуточного третьего. Действительно, либо
, либо
, третьего не дано. Такие противоположности не могут быть в отношении соисключённости.
Что интересно, отрицание-дополнение каждого одиночного атрибута в составе правой части равенства имеет смысл простой инверсии (побуквенного отрицания, inv() или ' ) этого атрибута, как если бы предмет рассуждений имел строго один критерий.
Т.е. при одиночных атрибутах мы можем сделать такую замену , а вот при составном уже нет
.
Если, например, друг - это человек, которого мы знаем и с которым хорошо общаемся, то инверсия такой коньюнкции даст нам человека, которого мы не знаем и с которым точно не общаемся:
При таком отрицании-инвертировании у нас есть некое третье . Это отрицание называют контрарностью или противоположностью с промежуточным третьим. Как и в случае с контрадикторностью, у нас выполняется закон противоречия, т.е.
и
не совместны. Но для составных атрибутов при инвертировании не работает закон исключённого третьего. Действительно, если мы составим его как
, то мы не можем написать, что это тождественно равно единице, ведь в универсуме также может быть
. Такие противоположности способны находиться в отношении соисключённости. С другой стороны, если универсум однокритериальный, т.е. погода может быть либо хорошей, либо плохой, третьего не дано, то отрицание-инверсия и отрицание-дополнение суть одно и то же (
можно заменить на ' ), и закон исключённого третьего снова работает. И так у нас есть:
Данность:
Исключённость:
Совместность:
Несовместность:
Соисключённость:
Несоисключённость:
Можно заметить, что инверсия переводит совместность в соисключённость, а несоисключенность в несовместность:
Отрицание, дуал и инверсия
В булевой алгебре для связок коньюнкции и дизъюнкции работает так называемый принцип двойственности.
Двойственность понимается в том смысле, что произвольное выражение булевой алгебры, если в нём заменить коньюнкции дизъюнкциями, а дизъюнкции коньюнкциями, будет представлять ту же взаимосвязь при условии, что значение 1 истолковывается как 0, а значение 0 - как 1.
Брусенцов Н.П.
Т.е. объявляет совместность данности
и
, а
- совместность их исключённости. То же самое
провозглашает несоисключённость единиц, а
несоисключённость нулей. Двойственное булево выражение Николай Петрович также называет дополнением, наподобие дополнения в теории множеств, или дуалом. Его получение выделим в отдельную операцию
или
, как мы это сделали с инверсией. Например
Дуал булева выражения двойственен его инверсии. Действительно, если - это совместность данности
и
, то
- это такая же совместность исключённости
и
, как и совместность исключённости в двойственном
, ведь в инверсии мы не истолковываем 1 как 0 и наоборот.
Не нужно путать смену истолкования и смену значения на противоположное. Если и
, то
и
.
Легко заметить, что отрицание-дополнение получается поочерёдным применением и
к булеву выражению.
Как итог можно сказать: коньюнкция и дизъюнкция двойственны относительно отрицания-дополнеия.
Ещё одна разговорная взаимосвязь - это подчинённость термину термина
, состоящая в том, что термин
не может быть не дан в случае данности
. Говорят, что термин
влечёт или имплицирует
. Также говорят "если, то", "из чего-то следует что-то", наличие свойства
является необходимым условием для свойства
, наличие свойства
является достаточным условием для свойства
. Например, быть млекопитающим - это необходимое условие, чтобы быть человеком, а быть человеком - это достаточное условие для того, чтобы быть млекопитающим. Здесь
называют антецедентом (от латинского antecedens - предшествующее) или логическим подлежащим, а
консеквкентом (от латинского consequens — следствие, вывод) логическим сказуемым. Когда говорят, что сущность подчинённого полностью содержится в сущности подчиняющего ("всё X есть суть Y"), такую трактовку называют содержательной или интенсиональной. Например, в понятие «Сократ» входят все свойства, которыми обладает Сократ: человек, мужчина, грек, философ и т.д. (входят как члены коньюнкции). Также наряду с ней широко распространена объёмная или экстенсиональная трактовка, где объём понятия "человек" больше, чем понятия "Сократ", ведь в объём "человек" входит не только Сократ, но и все люди на планете.
На роль этой взаимосвязи была выбрана материальная импликация. И это по сути первый камень в огород не столько булевой алгебры, сколько матлогиков, которые продолжают её использовать в качестве связи между предпосылкой и выводом, между причиной и следствием. Давно известно, что она полна парадоксов. Давайте взглянем на таблицу истинности:
X | Y | |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
Если истинно, то истинность импликации не зависит от истинности посылки
.
Если ложно, то истинность импликации не зависит от вывода
.
Другими словами, истинное следует из чего-угодно, из ложного следует что-угодно (следование выполняется тогда, когда в третьей колонке стоит 1).
Также, посылка может быть противоречива (подставим в качестве посылки закон противоречия, противоречивый атрибут). В экстенсиональном смысле это значит, что понятие
не имеет объёма. Т.е. не существует таких вещей, которые попадали бы под данное понятие. Здесь истинность импликации не зависит от
. Из противоречия следует что угодно.
может быть тавтологией (подставим в качестве вывода закон исключённого третьего, общезначимый атрибут). В экстенсиональном смысле это значит, что
по объёму - это целый универсум, т.е. все существующие вещи попадают под данное понятие. Здесь истинность импликации не зависит от
. Логические законы следуют из любых утверждений.
Ещё одна распространённая взаимосвязь - эквивалентность, совместность прямой и обратной подчинённости терминов или же
. Звучит как "что-то есть то-то", "что-то является чем-то",
необходимое и достаточное условие для
,
необходимое и достаточное условие для
. Когда в учебниках по математике в ходе доказательств мы встречаем фразу "тогда и только тогда", это тоже имеет смысл эквивалентности. Утверждения, построенные на эквивалентности, считаются более сильными, чем те, что базируются на подчинённости. Например, есть теоремы, которые доказываются лишь в одну сторону. Они считаются более слабыми. Благодаря связке эквивалентности можно строить такие формальные конструкции, как булевы уравнения.
Мы ещё вернёмся к разгрому импликации и булевым уравнениям. А пока обратим внимание на другой аспект булевой алгебры - замкнутость. Булева алгебра считается замкнутой относительно своих базисных операций коньюнкции, дизъюнкции и отрицания. Это значит, что при исполнении данных операций над 0 и 1 мы получим всё те же 0 и 1. Все 16 бинарных булевых функций можно выразить через 2 базисные операции (коньнктивный и дизъюнктивный базисы Буля: { } и {
}). Это якобы подтверждает то, что алгебра действительно замкнута. Но на деле же стоит взять обратную функцию от коньюнкции или дизъюнкции, как мы получаем выход за пределы множества состояний 0 и 1. По такому же принципу происходит выход в область отрицательных чисел при взятии операции вычитания на множестве натуральных чисел, либо в область комплексных чисел при взятии корня на отрицательных числах.
Рассмотрим функцию коньюнкции :
x | y | |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Теперь сделаем функцией от
и
:
. Относительно
обратная функция будет той же с точностью до обозначения, т.к. коньюнкция коммутативна.
z | x | |
0 | 0 | |
0 | 1 | 0 |
1 | 0 | |
1 | 1 | 1 |
По поводу или 1 вопросов нет. Если
, а
, то
с необходимостью равен 0. Если
, и
, то
с необходимостью равен 1. Вопрос в том, каким должен быть
при
и
равными 0? В данном случае нет ни какой необходимости в том, чтобы
был строго 0 или 1. Такой статус термина называют неопределённым или привходящим. Обозначим его греческой буквой
. Тот же вопрос про статус
при
и
. Оказывается, при таких значениях термин
невозможен, его не существует как понятия, которым можно оперировать. Он как противоречивый атрибут, который не описывает ни какую вещь. Обозначим его греческой буквой
. Как видите, булева алгебра в расширенном своём варианте уже четырёхзначна.
Более того, даже не используя обратные функции, можно поймать третье привходящее значение в выражениях вида Такие выражения можно подвергнуть минимизации, склейки дизъюнкции по термину
. Получаем равенство
. Термин
здесь подвергся элиминации. Данность или исключённость такого выражения не зависит от данности или исключённости термина
в двухтерминном универсуме. Если вещь в двухтерминном универсуме описывается такой дизъюнкций, то термин
называют общезначимым.
Мысли вслух
Предполагаю, что Ян Лукасевич, увидев такой достаточно простой слом замкнутости булевой алгебры, решил развить свою знаменитую трёхзначную, а затем и четырёхзначную логику. Проблема четырёхзначных логик в том, каким образом в таблицах истинности должны выражаться коньюнкция и дизъюкция привходимости и невозможности. Должны ли такие операции производить некое пятое значение, порождая тем самым дурную бесконечность? Должна ли логика быть действительно замкнутой, где обратные операции с двумя новыми состояниями не будут давать новых значений? Логик с соответствующими таблицами истинности можно построить очень много, и какая из них будет адекватна реальности, это вопрос. Ясно одно, такие неопределённости никогда не переходят обратно в чёткие состояния 0 и 1 посредством булевых операций. Если, например, совместность каких-то свойств и критериев легко измыслить, то из совместности привходимости и невозможности нельзя вывести что-то определённое.
Теория множеств
Можно заметить, что булева алгебра моделирует одну единственную вещь посредством составного атрибута, содержащего булевы связи. Теория множеств напротив рассматривает несколько вещей, объединённых в такую структуру, как множество. Любое множество мы измышляем просто как мешок с вещами. Набор этих вещей не является графом, между ними нет ни какой взаимосвязи, кроме той, что все они лежат в одном мешке. Такую теорию множеств называют наивной, и она также оказалась полна парадоксов. Конечно, проблемы пытались решать, вводя различные аксиоматики. В какой-то момент даже пришлось изобрести понятие класса для совокупности множеств, а после вести рассуждения о том, какие классы являются множествами, а какие нет. Всё это не особо помогает тому самому достоверному рассуждению, в котором хочется задействовать математический аппарат, оперирующий множеством вещей.
Простой пример. Объединим в множество предметы, лежащие на столе. Это будет множество:
{ ключи, кошелёк, банан }
Оно порождено простым перечислением предметов и помещении их в в фигурные скобки. Точно также оно порождено высказыванием "все предметы, лежащие в данную минуту на столе". Вроде всё понятно и красиво. Но что если мы зададим вопрос: "А что в данное множество не входит?" И здесь мы не находим чёткого ответа. Во-первых, мы не знаем, каким образом должно быть порождено множество, дополнение до которого мы хотим получить. Сама операция дополнения в теории множеств рассматривается в системе множество-подмножество, а не на абстрактном единственном множестве. Если включающее множество будет тем же самым "предметы, лежащие на столе", то дополнение пусто. Не существует таких вещей, которые не входят в данное множество. Другая крайность - мы пытаемся применить аксиоматику, где существует некое универсальное множество, которое вмещает в себя все существующие отдельные друг от друга объекты во Вселенной, в том числе и другие множества. Такое множество является подмножеством самого себя и плодит тем самым парадоксы. Эту проблему пытались решить в аксиоматике фон Неймана — Бернайса — Гёделя. В ней постулировали существование универсального класса, который содержит в себе все существующие множества, но сам множеством при этом не является. Т.е. объявить некую структуру, которая не может быть подмножеством чего-либо - шаг хороший, но скорее искусственный, чем содержательный, ведь, у того же Аристотеля не было понятие класса. Он оперировал такими понятиями, как роды и виды вещей (но об этом чуть позже).
В теории множеств существует закон двойного дополнения:
Он похож на закон двойного отрицания в булевой алгебре. Но если в булевой алгебре работают, как отрицание-дополнеие, так и инверсия, то справедливость двойного дополнения очевидна, только когда мы берём дополнение до универсума . Действительно, такое поведение очень похоже на закон исключённого третьего: существуют либо элементы множества , либо всё, что не является элементом
, третьего не дано. Если мы попытаемся взять вот такую систему из трёх вложенных множеств
, то мы не сможем сказать, что
, и
, ведь тогда уже
, и
.
![](https://webcf.waybackmachine.org/web/20231201090033/https://habrastorage.org/getpro/habr/upload_files/893/1a8/e60/8931a8e601b60fe988087d1d6fb39f0d.png)
Т.е каждое следующее дополнение будет выводит нас во всё более широкое множество. Если дополнение происходит не до универсума, то при двойном дополнении мы имеем некое промежуточное третье в виде более широкого множества . Поэтому мы приходим к вопросу выше. Дополнение до чего мы должны рассматривать, если отказываемся от универсума?
или
? Ответа мы не получим.
Из плюсов теории множеств можно отметить, что она хорошо передаёт экстенсиональную трактовку разговорных связок.
![X строго включено в Y X строго включено в Y](https://webcf.waybackmachine.org/web/20231201090033/https://habrastorage.org/getpro/habr/upload_files/875/fc7/99d/875fc799da81d6405fe26b76a3be024d.png)
При строгом включении множеств чётко видна подчинённость областей на диаграмме Эйлера-Венна, как если бы эти области были тeрминами или понятиями в разговоре. Нахождение в области является достаточным условием для нахождения в области
. Нахождение в области
является необходимым условием для нахождения в области
. При таком объёмном представлении хорошо видно такое свойство следования, как контрапозитивность.
Если из следует
, то из
следует
. То же самое справедливо и в обратном направлении. Эти суждения эквивалентны:
. Действительно, если мы находимся в области
, то мы с необходимостью находимся и в области
. Если мы находимся в области
, то мы с необходимостью находимся и в области
. Положение справедливо и для материальной импликации. У нас есть 3 области, которые могут существовать. Это
,
и
, если идти от самой внешней, к самой внутренней, а сами
и
считать булевыми терминами, эти 3 составных термина соответствуют единицам в таблице истинности ипликации. Нулю соответствует
, потому что область
полностью содержится в области
(в экстенсиональном смысле). Такой неизменяемый рисунок, где области нельзя варьировать, устраняет парадоксы противоречивого антецедента и общезначимого консеквента, т.к.
не пусто, а
не универсум. Но, что занимательно, это всего лишь картинка. В наивной теории множеств нет инструментов, чтобы как-то контролировать границы этих множеств. А классическая математическая логика, где это возможно, нам неинтересна.
Алгебра совокупностей
Вот мы и добрались до самого вкусного. Сразу определимся, какие требования к новому матаппарату мы хотим предъявить, чтобы он был полноценным гибридом булевой алгебры и теории множеств?
к выражениям алгебры можно применять операции коньюнкции, дизъюнкции, отрицания и извлекать из них естественно-языковой смысл, как из полноценных булевых выражений (трактовать интенсионально);
к выражениям алгебры можно применять операции пересечения, объединения, дополнения и трактовать при этом как объёмы или множества (экстенсионально);
устранить парадоксы (импликации в первую очередь);
Как выше было показано, булева алгебра имеет естественно-языковой смысл. В ней есть одна из самых полезных форм записи выражения - СДНФ (Соверншенная дизъюнктивная нормальная форма). С помощью неё представима любая n-арная булева функция. Она представляет из себя дизъюнкцию полных элементарных коньюнкций.
Пусть, например, универсум рассмотрения двухкритериальный с терминами и
. Полной элементарной коньюнкцией будет коньюнкция обоих терминов со штрихами или без, т.е. одна из 4-х:
. Как можно видеть, числом всех сочетаний таких коньюнкций будет
. Т.е. каждое из 16-ти СДНФ соответствует одной из 16-ти бинарных булевых функций.
Занимательная комбинаторика
- количество размещений с повторениями. Размещения с повторениями - упорядоченные множества по
элементов, взятых из
неповторяющихся элементов. А ещё это объём n-мерного гиперкуба со стороной
. Но к делу это не относится.
- мощность множества всех подмножеств.
- биномиальные коэффициенты - количества сочетаний без повторений. Сочетания без повторений - неупорядоченные множества по
элементов из
неповторяющихся элементов.
| {1, 0} | {a, b, c} | |
(1, 1, 1) | (a, b, c) | | |
(1, 1, 0) | (a, b) | | |
(1, 0, 1) | (a, c) | ||
| (1, 0, 0) | (b, c) | |
| (0, 1, 1) | (a) | |
(0, 1, 0) | (b) | ||
(0, 0, 1) | (c) | ||
(0, 0, 0) | ( ) | |
Вторая слева колонка упорядочена в порядке декремента двоичного числа 111. Стрелки в первой слева колонке предлагают мысленно переставить местами 2 значения в ячейках второй слева колонки, чтобы они соответствовали множествам в третьей колонке (соответствие числа единиц числу элементов). Те в свою очередь сгруппированы по своим биномиальным коэффициентам. Таблица может пригодиться для представления совокупностей в голове.
Давайте вспомним факт про дизъюнкцию. В качестве примера возьмём материальную импликацию. Данность несоисключённости говорит нам, что дан, либо
, либо
, либо оба сразу. В СДНФ это не так. Раскроем выражение:
А можно ли наоборот?
Да. Обратным образом происходит процесс минимизации булева выражения. Необходимо произвести максимальное число склеек (элиминаций) на минимальном количестве элементарных коньюнкций. Выбирается член, отличающийся от других штрихом только над одним из терминов. При чём выбирается так, чтобы тех "других" было максимальное число из возможных. Размножим выбранный член на все связанные с ним члены, используя закон идемпотентности , объединим в скобки
и произведём элиминацию общезначимых атрибутов.
Каждый из членов в правой части по прежнему находятся в несоисключённости. Но они теперь попарно не совместны! Коньюнкция любых двух составных атрибутов даст противоречие. Это значит, что если дан, какой-то из членов, например , то остальные будут с необходимостью исключены. Всё это доказывает факт, из предыдущей главы. Булева алгебра описывает одну единственную вещь в пространстве терминов.
Описываемая вещь может оказаться , а может одной из двух оставшихся, может
, а может одной из двух оставшихся,
или одной из двух оставшихся. Но она точно не окажется вещью
. Это важно запомнить! Члены СДНФ несоискючимы, попарно не совместны, каждый из членов равновероятен, а умалчиваемый член с необходимостью исключён. По правилам булевой алгебры правую часть мы можем расписать так:
Теперь становится понятен смысл материальной импликации, так же как и её таблицы истинности, в рамках СДНФ. Каждая из элементарных коньюнкций может быть, а может и не быть. Но необходимости нет ни в одном из членов. Импликация - это чисто потенциальное следование, лишь то, каким оно может быть. К содержательному Аристотелеву следованию она не имеет ни какого отношения и непригодна для выводов и рассуждений. Здесь сразу можно судить об ущербности логики высказываний, где по частоте использования импликация стоит на первом месте. Но вернёмся к теме.
Понятие класса в теории множеств имеет довольно размытое определение и может вызывать споры на тему, а является ли класс множеством. Но класс на самом деле это просто формализация в естественном языке того, какой может быть вещь. Например: формально можно утверждать: "Погода относится к классу холодных". Смысл выражения чёток, понятен и не вызывает вопросов. Но на деле ни кто так не говорит. Скажут просто: "Погода холодная". В двухтерминном ниверсуме погода уже может быть "тёплая и солнечная" и т.д. С учётом всего этого булеву алгебру можно назвать булевой алгеброй классов, потому что она она описывает то, к какому классу принадлежит одна единственная вещь.
Лучше всего алгебру совокупностей можно понять на такой структуре, как урна Лукасевича. Представьте себе мешок со стальными шарами. Также есть только 3 краски, в которые можно выкрасить каждый шар. Абсолютно неважно, как производится покраска. Если на шаре есть хоть одна цветная точка, шар считается выкрашенным. Вопрос. Сколькими способами можно выкрасить шары, чтобы варианты покраски не повторялись? Очевидно, способами. Урна Лукасевича отличается от обычного мешка тем, что одинаково покрашенные шары в ней неразличимы. Это значит, что вместимость урны всегда строго фиксирована и равна
элементов.
здесь, это число красок или же свойств-критериев. Соответственно, урна содержит 1 шар покрашенный во все 3 цвета, 3 шара покрашенных в 2 цвета, 3 шара, покрашенных в 1 цвет, и шар, не покрашенный ни в один цвет. Всего 8.
Алгебра совокупностей иерархична. Нулевым уровнем можно назвать множество тех самых свойств, критериев, терминов или, как мы его называли в булевой алгебере, универсум рассмотрения, а сами критерии индивидами. У этих индивидов есть одно важное свойство. Они дихотомические. Это значит, что по аналогии с крашенными шарами их цвета, во-первых, строго различимы друг от друга, во-вторых, покрашенный шар строго отличим от шара непокрашенного. Такой подход очень напоминает физический эксперимент, где мы способны чётко провести черту, грань, различие. Это также значит, что мы не можем какому-то критерию дать неопределённый статус, сказать, что он возможно присущ вещи, а возможно и не присущ. Урна не содержит шара, про который не ясно, крашеный он или нет. Также же не бывает шара, который крашеный, но цвет которого не ясен. Если про него можно сказать, что он вроде красный, а вроде и нет, то этот "вроде" мы выделяем в отдельный цвет, например в розовый, и заносим в универсум рассмотрения в качестве ещё одного критерия наряду с красным цветом.
На следующем первом уровне у нас есть полные элементарные коньюнкции критериев нулевого уровня - строительные кирпичики для СДНФ в булевой алгебре. Они же вне СДНФ являются теми самыми крашенными шарами в урне Лукасевича. Например, в однокритериальном универсуме элементы первого уровня, это множество
. Оно говорит о том, каким вообще может быть потенциальный шар (красный или не красный). Об этом же говорит и СДНФ
который в однокритериальном универсуме является законом исключённого третьего. При 2-х критериях мы уже имеем 4 коньюнкции
- 4 составных свойства потенциального шара, или же 4 варианта различных шаров. Эти коньюнкции называют индивидными. Число индивидных коньюнкций на 1-м уровне растёт как
. Таким образом, термины-критерии являют собой рода объектов-вещей, а полные коньюнкции родов - это их виды. Например, шар из рода
может оказаться вида
или
. Либо же в однокритериальном случае рода
, а вида
или
.
Чтобы составить совокупность 2-го уровня нам потребуется такой инструмент, как дизъюнкт, префиксная дизъюнкция или интегральная дизъюнкция. Обозначается как . Если мы имеем
, то это дизъюнкция всех вхождений критерия
(без штриха) в вещах совокупности. Т.е. мы итерируемся по всем элементам совокупности и составляем дизъюнкций каждого вхождения элемента в подынтегральном выражении
Если в урне присутствует хотя бы один шар покрашенный в цвет
, то
. Выражение окажется равным 0, только если в дизъюнкции не окажется ни одного
. Как и в значках интегральной суммы и произведения можно писать диапазон ячеек в урне, но нужды в этом особой нет. Дизъюнкт без диапазона говорит о том, что он распространяется на всю совокупность.
со штрихом обозначает, что в совокупности нет ни одной вещи
. Это значит, что совокупность либо содержит только вещи
, либо она пуста. Также мы можем производить коньюнкцию дизъюнктов
- такое выражение говорит нам о том, что в совокупности содержится вещь
и вещь
.
Совокупности 2-го уровня - это и есть те самые совокупности, с алгеброй которых мы знакомимся. Они же урны Лукасевича.
Возьмём однокритериальный универсум. Размер совокупности будет . Составим возможные совокупности в данном пространстве критериев:
Такие совокупности называют строгими, потому что включённость или исключённость вещи строго определена. Именно их можно считать обычными множествами из теории множеств. Число таких сосвокупностей . Может показаться, что все возможные ситуации исчерпываются данным набором. Но это не так. Из строгих совокупностей можно составлять комбинации посредством дизъюнкций. Например,
представляет из себя атрибут нестрогой или нечёткой совокупности. Как и в обычной булевой алгебре, атрибут
мы можем подвергнуть элиминации и получить
. И самое интересное. Нечёткость такой совокупности выражается в том, что при неполной коньюнкции умалчиваемый атрибут не дан и не исключён. Вещь
по отношении к совокупности
носит привходящий характер. Нет необходимости, чтобы вещь была в совокупности, и чтобы её там не было. Именно поэтому пара
является контрарной. Также есть нечёткие совокупности, которые нельзя сократить
. Всего нечётких совокупностей можно составить
.
Нечёткие множества Заде
Да, мы называем совокупности нестрогими или нечёткими, как в теории нечётких множеств Заде. Но концепция нечётких совокупностей в корне отличается от множеств Заде тем, что нечёткость в совокупностях проявляется только в контексте связанности вещей и терминов друг с другом. В теории Заде ключевым инструментом является функция принадлежности, которая каждому элементу множества ставит в соответствие некую степень принадлежности этому множеству. Эта степень может принимать значения из некоторого непрерывного диапазона и быть вероятностной. Но описывать ситуации вида и
теория Заде неспособна. Для этого потребовался бы целый зоопарк функций принадлежности, зависящих друг от друга.
UPD. Чуть позже нашёл заметку об отображении обычных булевых выражений на множества Заде. Но там для самих индивидов рассчитываются степени принадлежности к некоему отдельному множеству, которое с нашими совокупностями ни как не связано.
Если подойти более детально к трактовке таких совокупностей, то, они очень похожи на Кота Шрёдингера. Например, совокупность может оказаться либо первой коньюнкцией, либо второй, но необходимости нет ни в той, ни в другой. Но стоит из совокупности извлечь вещь
, как она с необходимостью окажется совокупностью
. Тоже самое будет, если мы из нечёткой совокупности извлечём вещь
. Мгновенно возникает определённость.
И так, самый общий атрибут совокупности:
- потенциальная совершенно неопределённая совокупность;
Атрибуты, составленные из 3-х чётких совокупностей:
Атрибуты, составленные из 2-х чётких совокупностей (и того в сумме 11 вместе с двумя верхними):
Чёткие совокупности:
Противоречивая невозможная совокупность (не путать с пустой из множества чётких):
- по сути заменяет сочетания по нулевому числу элементов.
Определённость атрибута совокупности возрастает в каждой следующей строке сверху вниз, от самой неопределённой к невозможной. Как можно заметить, самая верхняя совокупность безусловно дана и является отрицанием-дополнением самой нижней противоречивой. Также относительно центра третьей строки (составленные из 2-х чётких) некоторые из совокупностей связаны друг с другом отношением инверсии, а другие через отрицание-дополнение.
Также наряду с дизъюнктом можно пользоваться интегральной префиксной коньюнкцией, или же коньюнктом. Запись говорит нам о том, что все принадлежащие совокупности вещи наделены свойством
, и других не имеется. Это по сути логическое произведение всех вхождений
с той лишь разницей, что оно выполняется, даже если в произведении нет ни одного
, когда совокупность пуста. Например,
удовлетворяет совокупностям
но не удовлетворяет . Запись
говорит о том, что в совокупности присутствует хотя бы одна вещь
, и пустота совокупности недопустима.
Дизъюнкт и коньюнкт - это интегральные сумма и произведение. Только логические, а не числовые. Как уже многие поняли, они являются аналогами квантора существования и квантора всеобщности
в логике предикатов. Только это существование и всеобщность не чего-то сферического в вакууме, а вещи определённого класса в конкретной совокупности. К ним полностью применимы все связки и аксиомы булевой алгебры.
Единственным исключением являются тождества вида
где и
- произвольные выражения булевой алгебры классов. Например
Это выражение можно расширить до полной совокупностной СДНФ, но даже в текущем варианте есть наглядность. Булево выражение - это класс одной единственной вещи. Но когда мы объявляем существование класса посредством дизъюнкта, мы получаем класс совокупностей, в котором из каждой потенциальной совокупности мы можем извлечь одну вещь, удовлетворяющую изначальному классу. Ещё мы можем сказать, какие вещи помимо содержатся или не содержатся в данной совокупности. В примере выше это чётко видно. Дизъюнкция совокупностей описывает класс совокупностей, где совокупность может оказаться одной из трёх попарно несовместимых. Т.е. класс - это просто ярлык, этикетка на урне Лукасевича.
Класс и совокупность относятся также, как подинтегральная функция и интеграл. Поэтому класс вещей ни в коем случае не может быть совокупностью этих вещей и вообще какой-либо совокупностью. Так, например, класс неотождествим со своей одноэлементной совокупностью
. Отсюда следует, что ни какое множество не может быть подмножеством самого себя, ведь это множества разной природы, или, как сказали бы программисты, разных типов. Такое положение вещей устраняет многие парадоксы наивной теории множеств.
Давайте теперь возьмём пример наивного множества из предыдущей главы: { ключи, кошелёк, банан }. Переведём его на язык алгебры совокупностей. Создадим на основе этого множества индивиды нулевого уровня: - быть ключами,
- быть кошельком,
- быть бананом. Тогда совокупность, описывающая ситуацию { ключи, кошелёк, банан }, будет выглядеть так (в дальнейшем для удобства восприятия в строгих совокупностях с 2 критериями и более будем использовать цветовое разделение присущих и антиприсущих компонент, чтобы читателю не выискивать штрихи над дизъюнктами):
Что не входит в множество предметов на столе? Туда не входят вещи, которые являются ключами, кошельком и бананом одновременно. Также все комбинации из 2-х таких свойств. Также не входят вещи, которые не являются ни ключами, ни кошельком, ни бананом. Дополнение такого множества создаётся инверсией дизъюнктов. Все вышеперечисленные вещи становятся включёнными в множество, и наоборот.
Закон двойного дополнения идеально выполняется, и не потребуются ни какие всеобъемлющие и противоречивые универсальные множества.
Кстати, о противоречивости. Противоречивые конструкции стоят особняком. Атрибут противоречив. Он не описывает ни одну вещь. Совокупность
, содержащая противоречивый атрибут, противоречива, но формально не пуста. А вот совокупность
формально пуста, потому что в ней могут быть только противоречивые вещи, а это невозможно.
Также противоречива совокупность, утверждающая и одновременно отрицающая принадлежность какого-либо атрибута (последняя среди чётких и нечётких). Про такую можно сказать, что она невозможна.
Ну и последний вопрос. Могут ли нам понадобиться трихотомические термины вместо дихотомических?
Представим ситауцию: нам нужно описать угол, который может быть только прямой, тупой и острый. Казалось бы логичным иметь один термин для угла, и его три состояния, которые инверсией мы можем переключать друг в друга по кругу. Но, что же нам теперь, любой набор состояний пихать в один термин? С архитекрурной точки зрения это каждый раз начинать строить дом с основания, когда, в одной из комнат нам всего лишь требуется добавить дополнительный выключатель. Любые новые состояния прекрасно моделируются добавлением нового дихотомического термина. Быть прямым - не быть прямым углом, быть тупым - не быть тупым углом, быть острым - не быть острым углом.
Теоретико-множественные операции
Такие операции называют покомпонентными.
Дополнение множества мы только что рассмотрели. Оно является ни чем иным, как покомпонентной инверсией дизъюнктов в составе коньюнкции. Интерес представляет то, как дополнение поступает с умалчиваемыми членами совокупности. Как мы помним, если коньюнкция дизъюнктов неполная, то умалчиваемые дизъюнкты привходящи, нет необходимости как в их принадлежности, так и в антипринадлежности. Найдём дополнение привходящей вещи в однокритериальном универсуме.
Здесь, как видим, инверсия неопределённости даёт нам ту же самую неопределённость.
Для полноты картины рассмотрим дополнение в применении к первому уровню совокупностей. Там дополнение множества, это всё та же инверсия булева выражения . В сокращённой форме мы видим ту же картину
. Да, подход здесь немного необычный. Мы рассматриваем булево выражение (а именно коньюнкцию) не как класс вещи, а как множество присущих ей атрибутов. Коньюнкция
- это множество
, а коньюнкция
- это множество
. Соответственно инверсия переводит
в пустое множество, а
в
. Если брать выражение в целом, то класс
стал классом
, а
так и остался привходящим.
Пересечение и объединение также обладают наглядным смыслом. Если рассматривать только строгие совокупности, то смысл полностью идентичен смыслу в теории множеств. Пересечение - это множество, которому причастны все элементы, принадлежащие обоим множествам, и только они. Объединение - это множество всех элементов, которые причастны хотя бы одному из множеств.
Отличия снова начинаются на нестрогих случаях. Посмотрим на пересечение нестрогих однокритериальных совокупностей:
Для сравнения возьмём коньюнкции тех же совокупностей:
Как можно заметить, в основе пересечения лежит покомпоненнтная коньюнкция, но не самих компонент, а их принадлежности/антипринадлежности множеству. Операции объединения множеств находятся в таком же отношении к дизъюнкции. Здесь идёт покомпонентная дизъюнкция принадлежности/искючённости вещи:
и
Теперь опираясь на эти выражения, возьмём пересечение и объединение с привходящими компонентами.
Что мы здесь видим? Во-первых, имеет место быть дистрибутивность коньюнкции и дизъюнкции относительно пересечения и объединения. И наоборот, дистрибутивность пересечения и объединения относительно коньюнкции и дизъюнкции. Это вполне логично, т.к. любая совокупность - это булево выражение, а любое булево выражение - это в некотором смысле совокупность.
В данных выражениях пересечение предпочитает неопределённость его существованию, и несуществование
его неопределённости. Наоборот же, объединение из существования и неопределённости выбирает существование, а из неопределённости и несуществования выбирает неопределённость. Это как функции минимума и максимума для значений
. Подобным образом работают коньюнкция и дизъюнкция в трёхзначной логике Лукасевича, выбирают минимальное и максимальное из двух.
Если взглянуть на первый уровень совокупностей, выражение означает пересечение нестрогих совокупностей первичных терминов
И то же самое для объединения
Представляя индивидные коньюнкции как множества терминов, пересечение стремится выбрать отсутствие термина, а объединение его наличие.
На примерах первого уровня видно, что выражения могут быть с неиндивидными компонентами, например совокупности и
в двухтерминном случае. Давайте взглянем, как работает здесь операция пересечения для совокупностей второго уровня. В книге "Начала информатики" есть замечательный пример на это счёт, который хочется привести.
Среди четырёхугольников ромб обладает попарной параллельностью сторон (- параллелограмность) и перпендикулярностью диагоналей (
- дельтоидность). Множеством, которое содержит только ромбы и ничего, кроме них, будет
.
Теперь возьмём пересечение множества параллелограммов с множеством дельтоидов (заметим, что оба множества неиндивидные):
Здесь для работы с неиндивидными атрибутами совокупность потребовалось привести в индивидную форму, пускай и нечёткую. Это вопросов не вызывает. Сам же результат оказался контринтуитивным. Действительно, по логике это пересечение должно дать множество ромбов. Но такая логика упускает возможность случая, в котором пересечение может оказаться пустым. Например, совокупность может оказаться совокупностью
. Т.е. всегда есть возможность, что в множестве параллелограммов нет ни одного с перпендикулярными диагоналями, и в множестве дельтоидов ни одного с параллельными сторонами. Если же наложить условие непустоты (об этом в следующей главе), то получим изначально предполагаемый результат
.
В теории множеств, как и в булевой алгебере справедлив принцип двойственности. Но если коньюнкция и дизъюнкция двойственны относительно отрицания-дополнения, то пересечение и объединение двойственны относительно инверсии. Т.е. отношение пересечения множеств мы можем трактовать как объединение при условии, что сами множества будут инвертированными. Имеют места тождества, аналогичные законам де-Моргана:
где и
- произвольные совокупности любого уровня.
Чем же оказываются полезны теоретико-множественные операции помимо примера с содержательным рассуждением выше? Если булев контекст совокупностей позволяет использовать естественно-языковой смысл, то множественный контекст позволят компьютеризировать получившуюся алгебру. Действительно, дочитав статью до данного момента многие уже поняли, что буквы в булевых выражениях - это не переменные, которые мы можем проинициализировать нулём и единицей или искать сочетания нулей и единиц, которые этим переменным удовлетворяют. Буквы - это термины, классы или вещи, обладающие критериями. Закодировать булево выражение в самом общем смысле, значит обозначить единицами и нулями принадлежность/антипринадлежность атрибутов (1 - атрибут без штриха, 0 - атрибут со штрихом). Для минимальных форм очень полезна окажется троичность набора состояний, где отдельным состоянием мы можем закодировать привходимость.
Универсумы
Рассмотрим строгие совокупности в 2-х критериальном универсуме. Разделим их на ключевые группы, которые можно считать логическими универсумами, и по тем же группам распределим однокритериальные множества.
Универсум Аристотеля:
Однокритериальный случай:
Универсум Хризиппа-Буля:
Однокритериальный случай:
Смешанный универсум:
Однокритериальный аналог отсутствует.
Пустой универсум:
Однокритериальный случай:
И того строгих совокупностей в 2-х критериальном универсуме. Всего же чётких и нечётких совокупностей вместе с противоречивой будет
. Нужно помнить, что они являются всеми возможными дизъюнктивными сочетаниями из 16-ти строгих. Представляете, какое число ситуаций можно описать, имея всего 2 термина? Двухаргументными булевыми функциями описывается лишь 16 ситуаций, и они не идут ни в какое сравнение с тем разнообразием, что дарит алгебра совокупностей.
Дизъюнкцией в различных комбинациях этих 4-х универсумов можно составить нечёткие универсумы, в которых работают те или иные логики. Приведём примеры с их минимальными формами.
Общий универсум (УО):
Для 2-х критериев:
Интуиционистский (непустой) универсум (УИ):
Для 2-х критериев:
Трёхзначный универсум Поста (УП):
Для 2-х критериев:
А также покажем минимальные формы для одного и дву-критериальных чётких универсумов.
Универсум Хризиппа-Буля (УБ):
Универсум Аристотеля (УА):
Пустой универсум:
И отдельно от всех противоречивые атрибуты:
и
Здесь можно заметить, что интуиционистский универсум - это общий с невозможностью пустого множества. Он также включает в себя смешанный универсум, возникающий при 2-х терминах и более. Трёхзначный универсум Поста - это универсум Хризиппа-Буля с возможностью пустого множества.
Для каждого из универсумов существуют атрибуты других универсумов, которые не значат ничего. Для УО ничего не обозначающим является противоречивый атрибут. Они связаны друг с другом отрицанием-дополнением:
Таким же отрицанием-дополнением связаны пустой и интуиционистский универсумы
Атрибуты всех универсумов (а именно их минимальные формы) можно назвать тавтологиями. Эти утверждения безусловно истинны для своих универсумов. В пределах своего универсума тавтология общезначима. Ещё Бертран Рассел подчёркивал важность тавтологий для логических исчислений. Но если те же аксиомы булевой алгебры, которые тоже являются тавтологиями, определяют по большей части синтаксис формул, то тавтологии универсумов алгебры совокупностей отвечают за семантику.
Наиболее интересными универсумами, на мой взгляд, оказались универсумы Буля и Аристотеля. Взглянем на первый из них. Каждая из строгих совокупностей УБ содержит ровно одну вещь, а остальные с необходимостью исключены. Если мы возьмём дизъюнкцию любых двух множеств в УБ, например
то она нам говорит о том, что из получившейся нечёткой совокупности мы можем извлечь либо вещь , либо вещь
. Если извлечём одну, то второй в совокупности точно не окажется. Что нам это напоминает? Булево выражение класса одной единственной вещи
. УБ полностью повторяет функциональность булевой алгебры классов с той лишь разницей, что каждая индивидная коньюнкция находится в своей собственной упаковке - одноэлементном множестве. Николай Петрович называет УБ островом Рыцарей и Лжецов по аналогии с детской логической задачей, где на острове могут жить лишь те, кто говорят только правду (Рыцари), и те, кто всегда врут (Лжецы). Такая постановка даёт ситуацию, когда не данность атрибута
влечёт данность атрибута
. Каждый, кто на острове, либо Рыцарь, либо Лжец, третьего не дано. Это чётко соответствует семантики булевой алгебры.
Домножив выражение в УО на атрибут тавтологии УБ, мы по сути отфильтруем все возможные совокупности по универсуму Хризиппа-Буля или, по-другому, подчиним результат атрибуту УБ.
Универсум Аристотеля полностью противоположен УБ. В отличии от одноэлементных множеств УБ, чёткие совокупности УА содержат минимум 2 вещи таким образом, что, например, для 2-х критериального случая выполняется тавтология . Это значит, что если в универсуме присутствует критерий
, то в совокупности с необходимостью существуют как вещи
, так и вещи
. Это единственный универсум, логика в котором по праву называется диалектической. То, что Гегель называл единством и борьбой противоположностей, в книгах Николая Петровича называется просто сосуществованием противоположностей и выражает принцип Гераклита. Действительно, гениальность данного принципа сложно переоценить. Представьте, вы физик-экспериментатор и предполагаете, что обнаружили некое новое свойство вещества. Но объявить, что свойство действительно существует, вы можете лишь тогда, когда у вас есть вещи или материалы, которые этим свойством обладают, и материалы, которые этим свойством точно не обладают. Если вы предсказываете существование нового свойства, но, помимо лабораторных образцов, им обладают все остальные вещи во Вселенной, то такое свойство было бы общезначимым, и о его существовании объявлять бессмысленно. То же самое, когда вы говорите о свойстве, но ни одна вещь во Вселенной им не обладает. В универсуме Аристотеля не может быть общезначимых свойств. А вот в интуиционизме такое допустимо, особенно когда действие происходит в УБ или в смешанном универсуме. Смешанный универсум, как можно заметить, по одним терминам аристотелев, а по другим булев.
Теперь в УА на нашем острове живут люди, которые иногда врут, а иногда говорят правду (нет абсолютно правых и абсолютно виноватых). Домножение на атрибут УА также подчиняет и фильтрует общий результат по универсуму Аристотеля. Подобным же образом работает каждая из тавтологий выделенных универсумов. Например, наложение условия непустоты - это домножение на атрибут УИ.
Булевы уравнения. Часть 1
Одним из прикладных аспектов алгебры совокупностей становятся булевы уравнения.
В условиях заданной взаимосвязи двух терминов данность или исключённость одного из них зависит от данности/исключённости другого. Но только в двух случаях эта зависимость окажется взаимно однозначной: 1) когда термины эквивалентны
, 2) когда они антиэквивалентны
.
Брусенцов Н.П.
Наиболее общая проблема логики может быть сформулирована так: задано логическое уравнение, содержащее символы
. Требуется найти логически интерпретируемое выражение для выяснения отношения класса, обозначенного через
, к классам, обозначенным через
.
Дж. Буль
Давайте составим простое уравнение: быть квадратом, это быть равносторонним
и иметь прямые углы
.
Решить это уравнение относительно термина , значит найти обратную функцию
. Полное решение этого уравнения даёт метод Буля-Порецкого. Отношение эквивалентности в булевой алгебре имеет вид
Применим это отношение к уравнению, чтобы привести его к СДНФ:
Для большей наглядности распишем изначальную СДНФ следующим образом:
Далее мы попарно склеиваем по все коньюнкции, допускающие такое склеивание, а остальные группируем на содержащие
и содержащие
. Также разобьём выражение на два отдельных уравнения по членам с единицами и нулями.
В таком разложении по рассматриваемая взаимосвязь выражена как зависимость термина
от остальных
и
. Очевидно, что при данности
нам необходимо дан
и необходимо исключён
. При
необходимо дан
и необходимо исключён
. При
нет необходимости ни в
, ни в
,
является привходящим. При
является невозможным как понятие.
Полное решение можно записать как .
В общем решить булево уравнение - это сделать все возможные выводы про какому-то из терминов относительно остальных терминов. Наши выводы следующие:
иметь прямые углы, значит быть квадратом и быть равносторонним;
не иметь прямые углы, значит быть равносторонним, но не быть квадратом;
не известно, имеем ли мы прямые углы, если это не квадрат и не равносторонняя фигура;
прямоугольность невозможна как понятие, если мы имеем неравносторонний квадрат;
Мысли вслух
Ранее упоминал, что из привходимости и невозможности невозможно вывести что-то определённое в виде данности и исключённости. Но я уверен, что результат можно привести обратно к виду
, который идентичен изначальному уравнению, хотя у Николая Петровича и не высказывалось подобных мыслей.
Здесь всё красиво и замечательно. Но нас интересует вопрос: как этот результат будет выглядеть в совокупностной форме? Чтобы на него ответить, давайте применим метод Буля-Порецкого к различным СДНФ. Начнём с однокритериального. Объявим данность
Эта данность строго булева, т.к. исключённость влечёт данность
. Но если мы объявим существование класса
, то то мы лишь получим потенциальную совокупность, из которой можем извлечь вещь
Здесь может как присутствовать, так и не присутствовать. Представим нашу однокритериальную СДНФ следующим образом
Да, мы помним, что в алгебре совокупностей справедливы преобразования , но делать следующим образом некорркектно
, потому что смысл такого класса совокупностей в том, что совокупность может быть и пустой, но обязательно такой, которая не содержит
. Но разве нам такое необходимо? При объявлении существования булева класса смысл именно в вещи, которую мы можем извлечь из совокупности, а не в том, что в совокупности чего-то может не оказаться. Содержание таких совокупностей не будет иметь смысла, связанного с изначальным СДНФ.
Получившийся выше класс совокупностей подчиним условию для придания совокупности булева смысла
А теперь возьмём отрицание-дополнение у изначальной СДНФ и у его совокупностной формы
и
Во втором случае вместо одной ситуации мы видим целых три:
данность первого члена дизъюнкции утверждает принадлежность совокупности вещей обоих классов
и
, соответствует принципу сосуществования противоположностей и невыразима в булевой алгебре. Термин оказывается привходящим;
данность второго члена утверждает принадлежность совокупности только вещи
;
данность третьего члена утверждает пустоту совокупности и невозможность
как понятия;
В форме равенств это выглядит как
Результат справедлив в УО, но у него можно отсечь пустое значение, домножив на атрибут интуиционистского универсума и получить .
Важно подчеркнуть, что каждая из чётких совокупностей однокритериального универсума отображается на одно из 4-х состояний: . Здесь тоже вопросов не возникает. Интересное начинается с 2-х критериального универсума.
Рассмотрим отношение эквивалентности . Как бы это нелепо ни звучало, выразим термин
через термин
методом Буля-Порецкого
Объявим существование данного класса, а также несуществование членов, не входящих в СДНФ, и преобразуем в строгие совокупности
Теперь попробуем отобразить решение на разные универсумы. Здесь их два:
Универсум Хризиппа-Буля:
Тут начинаются различия с однокритериальным случаем. Находя в совокупностях пары и
, мы получаем случаи
и
. Здесь важно отметить то, что находя пару
, мы в той же совокупности с необходимостью находим пару
. Но мы не трактуем её как
, ведь в этом случае решение превратилось бы по закону поглощения в
а это не соответствует изначальной взаимосвязи.
А есть ли варианты СДНФ, которые утилизируют все пары дизъюнктов в совокупности УБ?
Да, в 2-х терминном универсуме их всего 4. Это . Например
что соответствует
Но это решение целиком и полностью содержится в УБ. В универсуме Аристотеля не сформировалось ни одной совокупности.
Универсум Аристоеля:
Здесь мы имеем замечательный результат. Одна единственная совокупность, подчинённая принципу Гераклита. В этом универсуме и
также отображаются в пары
и
, только теперь обе содержатся в одной единственной совокупности. Отсюда можно предположить, что всё, что находится в совокупности, находящейся в УА, отображается в решении Буля-Порецкого.
Попробуем продолжить такое рассуждение. Починим наконец-то нашу многострадальную импликацию и сделаем из неё содержательное аристотелево следование. Попробуем применить метод Буля-Порецкого к СДНФ импликации и выразить термин через
.
В совокупностной форме:
В УБ мы имеем три совокупности:
и три разные пары ,
и
, которые соответствуют решениям
,
и
. Последние два равенства намекают что
. Но в УБ мы такой результат получить не можем.
Содержательное аристотелево следование
Теперь немного отвлечёмся и подумаем, какие требования нужно предъявить к импликации, чтобы она стала содержательным следованием. Смотря на общее решение в совокупностной форме, мы видим, что должно быть необходимое несуществование вещи . Но для следования этого явно мало. Требования можно сформулировать достаточно просто: пусть это будет материальная импликация, но без парадоксов.
В интенсиональном смысле:
определение понятия
содержит атрибут понятия
как член коньюнкции;
понятие
непротиворечиво;
понятие
нетавтологично;
В экстенсиональном смысле:
класс
содержится в классе
;
класс
не пуст;
класс
не универсум;
Первое есть ни что иное, как сама материальная импликация, которую мы расписали в совокупностной форме. А второе и третье - это простое подчинение атрибуту УА . Отфильтруем полученный выше класс совокупностей по этому атрибуту. Исчезнут потенциальные совокупности из УБ и смешанного универсумов. То, что остаётся, это
Что мы здесь видим? Член является отображением решения
. В первой и второй паре дизъюнктов видны
и
. Это выражение материальной импликации в УА. Член
, как было показано ранее, является эквивалентностью в УА. Т.е. следование - это класс совокупности, которая может оказаться либо импликацией, либо эквивалентностью.
![Несоисключённость импликации и эквивалентности Несоисключённость импликации и эквивалентности](https://webcf.waybackmachine.org/web/20231201090033/https://habrastorage.org/getpro/habr/upload_files/f84/557/431/f84557431d34a028902ce1f41db24d60.png)
Представьте ситуацию, что компьютер хочет вычислить выражение Сократ — Человек. У него в базе данных содержалось множество объектов, обладающих свойством Человек, среди них был один единственный объект, обладающий свойством Сократ. Если для вычисления он использует строгую импликацию , то получит правильный вывод: Сократ — Человек. Но случилась беда. После вычислений на Земле произошла катастрофа, все люди исчезли, выжил один Сократ. Компьютер обновляет данные, вносит уточнение, и член
оказывается ложным и делает ложным всё выражение импликации. После обновления данных компьютер не может сделать вывод, что Сократ — Человек. Но это неверно. Даже то, что случилась катастрофа, и Сократ остался последним представителем своего вида, не должно влиять на результат следования. Член
говорит о том, что существуют другие люди, помимо Сократа, и это соответствует левому объёму на рисунке.
соответствует правому объёму. Необходимость
обязывает существовать другим представителям человеческого рода. Необходимость
вырождает выражение в эквивалентность. Но и в том и в другом случае следование обязано выполняться. И возможно такое лишь в совокупностной форме в УА.
Ну и минимальная форма данного атрибута:
Минимизация совокупностной формы
Помимо минимизации классов вещей и классов совокупностей как булевых выражений, можно производить минимизацию совокупностного атрибута. Например, в совокупности составляем пары, используя идемпотентность коньюнкции. Это будут
и
. В первой паре не существует вещь
, но существует
. Можно сделать предположение, что существует класс
, т.к. оба члена коньюнктивно содержат атрибут
. Но если при этом не существует вещь
, то с необходимостью обязана существовать вещь
, ведь класс
не пуст. Это мы и видим. Минимизируем:
То же самое проделываем для второй пары. Предполагаем, что существует класс . Но т.к. вещи
не существует, с необходимостью должна существовать вещь
. Это подтверждается. Следовательно, мы можем записать
Ну и конечная форма
Более наглядно такие операции показаны на диаграммах Кэрролла у Николая Петровича.
Именно поэтому в теории множеств нестрогое включение более похоже на содержательное следование, а строгое
на импликацию. В строгом включении лишь обозначаются 3 потенциальные области, а в нестрогом видна их варьируемость, когда области
и
могут быть эквивалентны.
Такое логическое следование теперь полностью избавлено от парадоксов или, как бы сказал Аристотель, избавлено от химер. Оно продолжает быть полностью контрапозитивным. Если для составить СДНФ и совокупностную форму в УА, они будут выглядеть абсолютно идентично формам изначального следования
.
Теперь мы можем понять, почему в булевой алгебре классов невыразимо естественно-языковое следование! В ней можно выразить привходимость атрибута, но не целой вещи. Для этого нужна множественность, а смысл булевой алгебры в единичности.
Булевы уравнения. Часть 2
Мы немного отвлеклись, поэтому вернёмся к уравнениям. У нас есть решение . Как мы можем его отобразить на нечёткую совокупность
? В примере с эквивалентностью
однозначно ложилась на совокупность
в универсуме Аристотеля. По этой логике
чётко ложится на совокупность
, которая является выражением материальной импликации в универсуме Аристотеля (она же строгая импликация у Кэрролла и Лукасевича), но ни как не следованием. С другой стороны если для выражения
мы получили одну единственнуйю чёткую совокупность и работали с этим, то для выражения
мы имеем уже класс совокупностей
В книгах нет объяснений, почему так происходит. Могу лишь предположить, что в универсуме Аристотеля привходящий при
это не вещь с неопознанным вторым параметром, а привходимость вещи
внутри самой совокупности. Почему именно
? Это будет казаться более логичным, если мы наоборот выразим термин
через термин
. Действительно
Член уже выражается парой
. Но вещь
так и остаётся привходящей в УА. Она как бы агрегирует в себе все возможные сигмы в решениях булевых уравнениий для
относительно всех терминов через остальные, коих здесь всего два.
Теперь разберёмся с нашим изначальным уравнением . Запишем его в совокупностной форме
Там образуется дизъюнкция 15-ти строгих совокупностей. А после усечения по универсуму Аристотеля выходит
Результат преинтереснейший. Пять строгих совокупностей. Пять различных ситуаций (сверху вниз):
Первая:
Вторая:
Третья:
Четвёртая:
Пятая:
(серым выделил отличия от первой ситуации)
Важно подчеркнуть! Эти ситуации создаются только для решения уравнения относительно термина . Если мы захотим найти решение относительно термина
, то те же ситуации пойдут в порядке: первая, вторая, четвёртая, третья, пятая.
Первая совокупность чётко ложится на основное решение Буля-Порецкого. Вторая и третья ситуации в сочетании с первой дают привходимость вещи . Больше вопросов возникает про четвёртую и пятую совокупности. Какие взаимосвязи они могут представлять? В голову пришла идея рассмотреть изначальную данность других условий
и
и получить для каждого из них свои 5 совокупностей в УА, ведь совокупности, как таковые - это не решения булевых уравнений, а объявление взаимосвязей вещей и терминов. Идём по тем же шагам: расписываем СДНФ, объявляем его существование и несуществование членов, в него не входящих, фильтруем результат по УА.
Для данности это
Для данности это
Вырисовывается интересная картина. Если образовать коньюнкцию всех трёх случаев
то результатом станет одна единственная совокупность
Это пятая ситуация в каждом из 3-х уравнений.
Если мы мы образуем коньюнкцию только 2-х уравнений
то результатом будет дизъюнкция 4-й и 5-й ситуаций
Либо при
это будет дизъюнкция 3-й и 5-й ситуации
Каким-то образом совокупностная характеристическая функция уравнения в универсуме Аристотеля, помимо привходимости некоторых вещей, автоматом учитывает и совместность с другими подобными уравнеиями
и
.
Минимальная форма совокупности будет выглядеть так
Опять же важно заметить. Если для выражения термина через остальные достаточно сосуществования всех вещей, атрибуты которых участвуют в СДНФ
(идёт чёткое отображение на решение Буля-Порецкого), то полное же совокупностное решение содержит гораздо больше смысловых взаимосвязей наподобие того, как мы это увидели в примере с теоретико-множественными операциями. Если переводить минимальную форму на естественный язык, то звучит она так:
"Существует квадрат, который равносторонний и с прямыми углами. Существует не квадрат, который непрямоугольный или неравносторонний. Не существует квадрат непрямоугольный и неравносторонний или не квадрат, который прямоугольный и равносторонний".
Итоги
Знаю, все любят короткие и лаконичные статьи. Но из песни слов не выкинешь. Поэтому надеюсь, что связанность повествования искупила её длину. Да, в отличии от разжёвывания импликации и её парадоксов, тема парадоксов теории множеств была затронута мной лишь вскользь. Но в книгах осталось ещё много нераскрытых здесь тем. Это и диаграммы Кэрролла, и логический квадрат, который на самом деле куб, и про успешную выразимость модальностей в алгебре совокупностей. Получился своего рода тот самый конспект по страницам всех трёх книг, который может написать каждый, и добавить что-то от себя.
Любой любознательный школьник, изучивший на уроках по математике сложение, умножение и возведение в степень, может задать вопрос: а существуют ли операции после возведения в степень? Тот же вопрос можно задать алгебере совокупностей. Не смотря на отсутствие в ней бесконечных множеств, она по сути бесконечно расширяема. Алгебра не ограничивается вторым уровнем совокупностей. Подобно тому, как после возведения в степень существует тетрация и другие гипероперации, уровни совокупностей могут быть выше второй. Аргументами дизъюнктов могут быть строгие и нестрогие совокупности второго уровня. Например:
Это нечёткая неиндивидная совокупность третьего уровня, где индивыдами выступают 16 чётких совокупностей 2-го уровня. Да, объём памяти под совокупность каждого следующего уровня растёт как степенная башня двойки. Но, во-первых, трудно представить, что описывает логика более высоких уровней совокупностей, во-вторых, логика второго уровня на столько разнообразна по сравнению со скудной булевой алгеброй, что её потенциал ещё до конца не раскрыт.
Булевы уравнения являются прикладным аспектом алгебры совокупностей. Но наиболее важная и нужная прикладная область - это компьютеризация аристотелевой силогистики, которую за пару последних веков (вот же удивительно, но на самом деле нет) так и не смогли нормально формализовать.
Почему это важно? Сейчас на острие мэйнстрима активно развиваются системы автоматического доказательства. Но вряд хотя бы одна из них может похвастаться тем, что целиком и полностью работает в универсуме Аристотеля и соблюдает принцип сосуществования противоположностей. Я специально не касался силогистики, потому что это широкая тема для отдельной большой статьи, которую планирую написать по трудам Николая Петровича.
Небольшой спойлер
Содержательное аристотелево следование является ни чем иным, как общеутвердительным суждением силогистики
.
Очень жалко, что с 2014 года невозможно задать многие интересующие вопросы Николаю Петровичу лично. Но его наследие живо.
Поэтому выражаю огромную благодарность Владимировой Юлии Сергеевне, кандидату физ.-мат. наук и старшему научному сотруднику "Лаборатории дискретных управляющих систем и приложений" в МГУ за помощь и ответы на вопросы касательно алгебры совокупностей. Также благодарю за неоспоримый вклад в поддержку и развитие идей Николая Петровича Брусенцова.
Также много интересных материалов можно найти на сайте в разделе "Троичная логика".
Всем приятного чтения книг!