АЛГЕБРА ЛОГИКИ

одна из осн. частей математич. логики, основанная на применении алгебраич. методов к логике. Возникнув в сер. 19 в. в трудах Буля и развиваясь затем в работах Джевонса, Шредера;, Пирса, Порецкого и др., А. л. имела своим предметом классы (как объемы понятий), соотношения между ними по объему и связанные с этим операции над ними. Само создание А. л. представляло собой попытку решать традиц. логич. задачи алгебраич. (т.е. характерными для алгебры) методами. В связи с появлением в 70-х гг. 19 в. теории множеств (см. Множеств теория), поглотившей часть прежнего предмета А. л. (теоретико-множеств. операции), и дальнейшим развитием математич. логики в трудах Фреге, Рассела, Гильберта и др. (последняя четверть 19 в. и 1-я пол. 20 в.; для развития А. л. большое значение имели труды И. И. Жегалкина) предмет А. л. значительно изменился. Основным ее предметом, особенно в работах сов. ученых, являются высказывания (объекты, родств. предложениям, суждения и т.п.), рассматриваемые со стороны их логич. значений (истина, ложь, бессмыслица и т.п.), и те логич. операции над ними, для изучения к-рых достаточно иметь дело лишь с этой стороной высказываний. Наличие у А. л. этого предмета, изучаемого не только алгебраич. методами, а также связь самих алгебраич. методов с иными математич. методами порождают многочисл. связи А. л. с другими разделами математич. логики (исчисления высказываний, исчисления классов, исчисления предикатов, теория функций алгебры логики, логико-математич. теория релейно-контактных схем и др.). Этим же обусловливается и нек-рое проникновение в А. л. таких методов, как аксиоматич. метод, методы теории алгоритмов, теории множеств (см. Теоретико-множественная логика), топологии и др. Роль спец. методов в логике (в частности, математич. методов, без к-рых нет и не может быть математич. логики), как и в др. науках, состоит в том, что они позволяют найти новые способы подхода к изучаемому предмету, выявить новые стороны его, важность к-рых подтверждается практикой. Так, в частности, А. л., использующая в своей основе далеко идущие абстракции, огрубление и формализацию, находит все более широкое применение в технике (особенно при решении задач, связанных с построением автоматов) и, наоборот, развивается сама под влиянием запросов техники (задач автоматизации программирования, уменьшения числа элементов в устройствах релейного действия и др.). В основе обычной, т.н. классич. А. л. лежит абстракция высказывания как величины, имеющей одно (и только одно!) из двух значений: "истина" или "ложь" (короче: И, Л), или могущей принимать оба эти значения (но не одновременно). В первом из этих случаев имеем индивидуальное высказывание (высказывание в узком, наиболее принятом смысле этого слова), во втором – высказывание-функцию. Примеры высказываний: "2 · 2 = 4", "0 ? 0", "Сократ – человек", "0 = 1", "2 · 2 = 5", "х? = у", "z – человек", "Если х = у, то у = 0", "Если х = 2, то х? = 4", "х равняется у или х не равняется у". Первые три высказывания имеют значение И (т.е. истинны), 4-е и 5-е – значение Л (т.е. ложны), 6-е, 7-е, 8-е – высказывания-функции (если, напр., значениями буквенных переменных х и у могут быть целые числа, а переменной z – живые существа), 9-е и 10-е имеют значение И (при всех возможных значениях переменных х и у). Последние три из этих высказываний являются сложными, в отличие от предшествующих им простых. При этом высказывание наз. сложным, если в нем есть хотя бы одна из связок "и", "или", "если..., то", "эквивалентно" и т.п. или частица "не". Абстракция в А. л. идет дальше рассмотрения значений высказываний. Именно, все истинные высказывания отождествляются между собой, т.к. истинное высказывание не отличается от другого истинного высказывания по значению (от других сторон высказываний в А. л. отвлекаются). Ложные высказывания между собой тоже отождествляются. При рассмотрении же высказываний-функций в А. л. обычно отвлекаются от рассмотрения зависимости их от иных переменных, кроме таких, значениями к-рых являются тоже высказывания, вводя для их рассмотрения буквенные переменные, к-рые мы будем называть переменными высказываниями (точнее, переменными для высказываний). Таковыми являются буквы А, В, С,..., А1, А2, А3,... и т.п. (не обязательно именно заглавные латинские; выбор последних – вопрос не существа А. л., а соглашения) при условии, что они играют роль переменных, значениями к-рых могут быть всевозможные индивидуальные высказывания, т.е., в силу упомянутых абстракций, "константы" И и Л. Буквенные обозначения высказываний вообще характерны для А. л. подобно тому, как для обычной школьной алгебры характерны буквенные обозначения чисел. Так, не только переменные высказывания, но и индивидуальные часто обозначаются буквами А, В, С и т.п. (но играющими при этом роль констант). Кроме простых высказываний, обозначаемых отд. буквами А, В... или И, Л, рассматриваются также сложные высказывания – результат соединения высказываний связками или отрицания их (соответствующего частице "не"). Сложные высказывания рассматривают как функции от входящих в них буквенных переменных А, В, С и т.д. Так появляется понятие функции А. л. - функции от аргументов, являющихся переменными высказываниями, т.е. принимающих значения И, Л, к-рая (функция) может принимать тоже лишь эти значения. Для сложных высказываний в связи с этим часто употребляются функциональные обозначения ? (A), D (В), ? (А, В, С), ? (А1, А2,...,An) и т.п. Однако более систематич. употребление находят в А. л. другие обозначения - обозначения алгебраич. операций над высказываниями. Эти операции, играющие в А. л. роль, аналогичную той, к-рую в обычной школьной алгебре играют операции сложения, вычитания, умножения и др. операции над числами, соответствуют в А. л. упомянутым выше связкам и частице "не". Так вводятся операции: конъюнкция А В (читается "А и В"; другие обозначения: AB, A & B, А / В; другие названия: логическое умножение, булево умножение), дизъюнкция A / B (чит. "А или В"; другие обозначения: А + В, АВ; другие названия: логическое сложение, булево сложение), импликация А ? В (чит.: "Если А, то В" или "А влечет В", или "А имплицирует В", или "Из А следует В"; другие обозначения: A з B; другое название: логическое следование), эквиваленция А А?ЛГЕБРА ЛО?ГИКИ В (чит.: "А эквивалентно В" или "А равнозначно В", или "А, если и только если В"; другие обозначения: А =В, А < — > В, А Z В, А = В; другие названия: эквивалентность, равнозначность, равносильность), отрицание ? (чит.: "не А", или "А ложно", или "не верно, что А", или "отрицание А"; другие обозначения: ? А, А?ЛГЕБРА ЛО?ГИКИ А, А´; другое название: инверсия), а также иногда и др. операции. Одной из важных сторон формализации, принимаемой в А. л., является то, что знаками этих операции (т.е. по смыслу, соответствующими им связками) можно соединять любые высказывания, без ограничения, в т.ч. и те, к-рые сами являются сложными. Так возникают такие выражения (символич. высказывания), как и т.п., а также, вместе с ними, такие, казалось бы, противоестественные конструкции, как высказывания "Если 2 · 2 = 5, то все люди верблюды", "Если 0 = 1, то: если 0 = 1, то 1 = 1 и 1 < 3" и т.п. Нек-рые из получающихся выражений, как, напр., (((А / В) С / D) E / AF) (AB / EF), даже трудно словесно высказать и приходится читать путем перечисления всех знаков, включая скобки. Зато при этом удается точно и строго описать класс всех рассматриваемых выражений А. л. В данном случае он состоит из констант И и Л, переменных А, В... и всех тех выражений, к-рые получаются из них путем конечного числа соединений знаками "·", "/", "?" и "А?ЛГЕБРА ЛО?ГИКИ" и отрицаний. В др. случаях рассматриваются др. классы выражений, содержащие др. знаки операций или же только эти, но не все из них. Такие же неудобочитаемые выражения, как вышеприведенное, вовсе не являются "мертвым грузом" в А. л. Они могут наряду с др. выражениями получаться, напр., при анализе релейно-контактных схем или в результате преобразований других, более удобочитаемых, но громоздких выражений, что применяется, напр., при синтезе контактных схем. Да и необычность приведенных выше "противоестественных" высказываний можно усмотреть, лишь выйдя за рамки А. л., в к-рой они, наоборот, приобретают вполне определ. смысл и, не отличаясь ничем от высказываний, соответственно, А ? В и С ? (С ? DE) при А = В = С = Л и D = Е = И, являются даже истинными. Это связано с др. важной стороной формализации в А. л. – требованием, чтобы операции задавались таблично как функции, т.е. чтобы значение сложного высказывания зависело только от значений составляющих его простых высказываний. Так, конъюнкция задается таблицей: И · И = И, И · Л = Л, Л · Л = Л, Л · Л = Л; дизъюнкция – таблицей: И / И = И, И / Л = И, Л / И = И, Л / Л = Л; импликация – таблицей: И ? И = И, И ? Л = Л, Л ? И = И, Л ? Л = И (эта таблица вытекает из требования табличное операции и естеств. требований, чтобы были такие случаи, когда А ? В ложно, но чтобы все частные случаи такого высказывания, как "Если х = 2, то х2 = 4", были истинны; случаи, когда х принимает одно из значений 2,–2,1, как раз и дают три из четырех равенств таблицы); эквиваленция – таблицей: И А?ЛГЕБРА ЛО?ГИКИ И = И, И А?ЛГЕБРА ЛО?ГИКИ Л = Л, Л А?ЛГЕБРА ЛО?ГИКИ И = Л, Л А?ЛГЕБРА ЛО?ГИКИ Л = И; отрицание – таблицей: И = Л, Л = И. Эти таблицы позволяют вычислять значения сложных высказываний, зная значения простых. Осн. суть А. л. как системы методов состоит в использовании преобразований высказываний на основе тех алгебраич. законов, к-рые имеют место для операций над высказываниями. Эти законы чаще всего имеют вид тождеств, т.е. равенств, верных при всех значениях переменных. Важную роль играют следующие тождества: I. AB = ??, ? / В = В / А (законы коммутативности); II. (АВ)С = А (ВС), (А / В) / С = А / (В / С) (законы ассоциативности); III. А(А / В) = А, А / AB = А (законы поглощения); IV. А (В / С) = AB / АС (закон дистрибутивности); V. А? = Л (закон противоречия); VI. А / ? = И (закон исключенного третьего). Эти тождества, устанавливаемые, напр., с помощью таблиц, позволяют уже без помощи таблиц получать др. тождества. При этом методом получения последних является метод тождеств. преобразований (т.е. преобразований, к-рые, изменяя выражение, не изменяют при этом функцию, выражаемую последним), совершенно аналогичных тем, которые изучаются в школьном курсе алгебры (но основанных уже на новых тождествах). Так получим, напр., законы идемпотентности; АА = А, А / А = А [последний доказывается так: А / А = А / А (А / B) = A, т.е. с использованием лишь (обоих) законов поглощения]; 2-й закон дистрибутивности A / BC = (А / B) (А / C) [доказательство: A / ВС = А / АС / ВС = А / СА / СВ = А(А / B) / C(A / B) = (A / B)A / (A / B)C = (A / B) (A /C)]; двойного отрицания закон законы де Моргана: законы зачеркивания: законы выявления: Вообще тождеств I-VI достаточно для того, чтобы из них по методу тождеств. преобразований можно было вывести всякое (верное, конечно) тождество, левая и правая части к-рого – выражения А. л., состоящие из переменных А, В,..., констант И, Л и знаков"·", "/", "–" (не обязательно включая все из них). Добавление же тождеств VII A ? B = ? / B, А А?ЛГЕБРА ЛО?ГИКИ В = АВ / ?В дает возможность выводить и любые тождества, содержащие также знаки "?", "А?ЛГЕБРА ЛО?ГИКИ". Напр., такие: А ? (В ? С) = АВ ? С (закон объединения посылок), А (А ? В) = AB (закон зачеркивания посылки), ? ? В = В ?А (закон контрапозиции) ? А?ЛГЕБРА ЛО?ГИКИ В = А А?ЛГЕБРА ЛО?ГИКИ В (закон четности эквиваленции), А ? А= И, А А?ЛГЕБРА ЛО?ГИКИ А = И, А ? ? = ?, А А?ЛГЕБРА ЛО?ГИКИ ? = Л, А А?ЛГЕБРА ЛО?ГИКИ В = (А ? В). (В ? А), А / (В А?ЛГЕБРА ЛО?ГИКИ С) = (A / B) А?ЛГЕБРА ЛО?ГИКИ (A / C) и др. Использование перечисл. тождеств позволяет уже без большого труда выводить и многочисл. гораздо более сложные тождества, например (A ?(B ?(C ?(D ? E)))) ? (A ?(B ?(C ?(D ? F)))) = (A ?(B ?(C ?(E ? F)))), (? А?ЛГЕБРА ЛО?ГИКИ B) ?((C А?ЛГЕБРА ЛО?ГИКИ D) ?(E А?ЛГЕБРА ЛО?ГИКИ (F А?ЛГЕБРА ЛО?ГИКИ G))) = (A А?ЛГЕБРА ЛО?ГИКИ B)(C А?ЛГЕБРА ЛО?ГИКИ D) ? (E А?ЛГЕБРА ЛО?ГИКИ (F А?ЛГЕБРА ЛО?ГИКИ G)), AB / AC / BC / DE / DF / EF / ?D / B? / CF = И, проверять к-рые непосредственно по таблицам было бы уже довольно трудно. В записи последнего из этих тождеств существ. роль играет использование закона ассоциативности дизъюнкции, к-рый позволяет обходиться без скобок при записи выражения, к-рое можно понимать как дизъюнкцию неск. выражений (членов), т.е. такую же роль, какую в обычной школьной алгебре играет закон ассоциативности сложения (сочетательный закон) при записи суммы неск. слагаемых. Аналогичное можно сказать и о законе ассоциативности конъюнкции. Можно вывести также закон ассоциативности эквивалентности. Однако связанное с ним понятие эквиваленции нескольких переменных надо не путать с (попарной) эквивалентностью их. Так, А А?ЛГЕБРА ЛО?ГИКИ В А?ЛГЕБРА ЛО?ГИКИ С [т.е. (А А?ЛГЕБРА ЛО?ГИКИ В) А?ЛГЕБРА ЛО?ГИКИ С] и (А А?ЛГЕБРА ЛО?ГИКИ В) (В А?ЛГЕБРА ЛО?ГИКИ С) [т.е. попарная эквивалентность] выражают различные функции [напр., Л А?ЛГЕБРА ЛО?ГИКИ Л А?ЛГЕБРА ЛО?ГИКИ Л = (Л А?ЛГЕБРА ЛО?ГИКИ Л) А?ЛГЕБРА ЛО?ГИКИ Л = И А?ЛГЕБРА ЛО?ГИКИ Л = Л, но (Л А?ЛГЕБРА ЛО?ГИКИ Л) (Л А?ЛГЕБРА ЛО?ГИКИ Л) = И · И = И]. Здесь сказывается различие между операцией эквиваленции и отношением эквивалентности, хотя это, казалось бы, и одно и то же. Тем более следует соблюдать осторожность при сопоставлении эквиваленции неск. выражений, напр. U А?ЛГЕБРА ЛО?ГИКИ B А?ЛГЕБРА ЛО?ГИКИ G,с их равенством U = B = G, т.к. последнее означает именно попарное равенство (U = B и B = G); необходимо либо строго различать эквиваленцию и равенство, либо, в случае их отождествления, избегать, напр., опускания скобок по ассоциативности. Тождества V, VI, VII показывают, что константы И и Л, импликацию и эквиваленцию, рассматривая их как функции, можно выразить через конъюнкцию, дизъюнкцию и отрицание. Более того, имеет место теорема, гласящая, что всякая функция А. л. может быть представлена через эти три операции, т.е. записана в виде выражения, содержащего лишь знаки этих операций и буквенные переменные. Именно, любую функцию ? (А1, А2,...,An) можно записать как дизъюнкцию всех выражений вида Ф (а1, а2,..., аn) · (А1 А?ЛГЕБРА ЛО?ГИКИ а2) (А2 А?ЛГЕБРА ЛО?ГИКИ а2)(Аn А?ЛГЕБРА ЛО?ГИКИ аn), где а1, а2,..., аn – набор из значений И, Л. Заменяя в этой дизъюнкции выражения Аi А?ЛГЕБРА ЛО?ГИКИ И на Аi, а Аi А?ЛГЕБРА ЛО?ГИКИ Л – на Аi, a также стирая "коэффициенты" Ф(а1, а2,..., аn), равные И (по закону И · А = А) и отбрасывая члены с "коэффициентами", равными Л (по законам (Л · А = Л, Л / А = А), мы и получим (если функция не есть константа) то выражение, о к-ром говорится в теореме. Последнее наз. совершенной дизъюнктивной нормальной формой функции Ф(А1,...,An). Дизъюнктивной нормальной формой (короче, днф) наз. выражение, к-рое есть буква И или Л или имеет вид U1 / U2 /.../ Us где каждый член Ui является либо буквенной переменной, либо ее отрицанием, либо конъюнкцией таковых, причем s не обязательно отлично от 1, т.е. знаков "/" может и не быть. Примеры днф: А, B, ?BC, AB / С, А? / СС, АВАС / BСВ, ?BCD / A / D / CE, ABCD / ABCD / ?BCD, И, Л. Последние из этих днф являются т.н. совершенными. Днф наз. совершенной, если она есть И или Л или в каждом члене содержит ровно по одному разу все имеющиеся в ней буквы (переменные) и не имеет одинаковых членов. (Два выражения наз. одинаковыми, если одно из другого можно получить с помощью одних лишь законов коммутативности и ассоциативности). Всякое выражение А. л. можно привести (преобразовать) к днф. Для этого достаточно элиминировать (т.е. исключить) константы и знаки операций, отличных от конъюнкции, дизъюнкции и отрицания, выразив их через эти операции (напр., по V, VI, VII), а затем "спустить внутрь" (по законам де Моргана) все знаки отрицания, стоящие над сложными высказываниями, ликвидировать кратные отрицания (по закону А = А) и, наконец, раскрыть все скобки по закону дистрибутивности (при использовании также законов ассоциативности и коммутативности). А всякую днф можно привести к совершенной днф, "домножая" члены на недостающие буквы (по закону А = АВ / АB) и ликвидируя повторения букв в членах (по законам АА = А, А? = Л, Л · А = Л Л / А = А) и повторения членов (по закону А / А=А). Приведение к совершенной днф лежит в основе одного из алгоритмов для решения по любым двум данным выражениям U и B вопроса о том, одну ли и ту же функцию они выражают, т.е. верно ли тождество U = B. Алгоритм этот состоит в следующем: приводим U и B к совершенным днф, содержащим все те переменные, к-рые есть в U, и все те, к-рые есть в U, и смотрим, одинаковы ли эти две совершенные днф; если одинаковы, то ответ положителен, если нет – отрицателен. Однако совершенная днф, находя применение и к др. задачам, является все же часто весьма громоздкой. Поэтому приходится нередко пользоваться др. нормальными формами. Из них важную роль играет т.н. сокращенная днф. Последнюю можно определить как такую днф, в к-рой 1) нет повторений букв ни в одном члене, 2) нет таких пар членов Ui; и Uj, что всякий множитель из Ui имеется и в Uj, и 3) для всяких двух таких членов, из к-рых один содержит множителем нек-рую букву, а другой – отрицание той же буквы (при условии, что другой буквы, для к-рой это же имеет место, в данной паре членов нет), имеется (в этой же днф) член, равный конъюнкции остальных множителей этих двух членов. Всякую днф можно привести к сокращенной днф путем конечного числа выбрасываний членов по закону поглощения (ср. с условием 2) и добавлений членов по закону выявления (ср. с условием 3) с использованием также нек-рых более простых законов (коммутативность, ассоциативность, А = А · И) и ликвидацией повторений букв в членах и повторений членов. Пример приведения выражения к сокращенной днф: Тождество U = B верно, если, и только если, получаемые из U и B сокращенные днф одинаковы. Кроме днф, употребляются также конъюнктивные нормальные формы (кнф). Это такие выражения, к-рые можно получить из днф путем замены в них знаков "/" на "·", а "·" на "/". [Пример кнф А(В / C / D)(A / D)]. Конечно, такое преобразование не является тождественным, т.е. может изменить функцию, выражаемую данной днф. Оно есть преобразование двойственности. Преобразованием двойственности наз. такое преобразование выражения А. л., при к-ром в этом выражении знаки всех операций заменяются на знаки двойственных им операций, а константы: И на Л, Л на И; причем операция (или функция) Ф наз. двойственной для операции ?, если таблица, задающая Ф, получается из таблицы, задающей ?, путем замены в ней всюду И на Л, а Л на И (имеется в виду одновременная замена и значений функции, и значений ее аргументов). Если ? двойственная ?, a ? двойственная ?, то ? = ?. Напр., конъюнкция и дизъюнкция двойственны между собой, отрицание двойственно самому себе, константа И (как функция) двойственна константе Л. Функция Ф(А1, Аn) двойственна функции ? (А1, Аn), если, и только если, верно тождество Если верно тождество U = B и U* двойственно U, а B* двойственно B, то верно и тождество U* = B*, называемое двойственным предыдущему тождеству. Это – т.н. принцип двойственности. Примерами двойственных тождеств являются пары законов ?, ?I, III и др.; тождество V двойственно тождеству VI. Совершенную кнф и сокращенную кнф можно определить как такие кнф, что двойственные им выражения есть, соответственно, совершенная днф и сокращенная днф. Совершенные и сокращенные днф и кнф можно использовать для решения задачи обзора всех гипотез и всех следствий данного выражения А. л. Причем под гипотезой выражения U А. л., т.е. в условиях принятых в ней абстракций, естественно понимать такое выражение B, что B ? U тождественно истинно, т.е. истинно при всех значениях переменных высказываний; а под следствием выражения U – такое выражение B, что U ? B тождественно истинно. Гипотеза выражения U наз. простой, если она есть конъюнкция буквенных переменных или их отрицаний и после отбрасывания какого бы то ни было из этих ее множителей перестает быть гипотезой выражения U. Аналогично, следствие выражения U наз. простым, если оно есть дизъюнкция букв или их отрицаний и после отбрасывания какого бы то ни было из ее членов перестает быть следствием выражения U. Решение задач обзора гипотез и следствий основано на следующих теоремах. 1°. Если U = B, то у U и у B одни и те же гипотезы и одни и те же следствия. 2°. Каждый член днф является гипотезой этой днф. 3°. Каждый множитель кнф есть следствие этой кнф. 4°. Если B – гипотеза выражения U, то BG – тоже гипотеза выражения U. 5°. Если B – следствие выражения U, то B / G – тоже следствие выражения U. 6°. Если B и G – гипотезы выражения B, то B / G – тоже гипотеза выражения U. 7°. Если B и G – следствия выражения U, то BG – тоже следствие выражения U. 8°. У совершенной днф нет других гипотез (не содержащих букв, не входящих в эту днф), кроме дизъюнкций (нек-рых) ее членов или тождественно равных им (т.е. равных при всех значениях переменных) выражений. 9°. У совершенной кнф нет других следствий, кроме конъюнкций (нек-рых) ее множителей или тождественно равных им выражений. 10°. Сокращенная днф есть дизъюнкция всех своих простых гипотез. 11°. Сокращенная кнф есть конъюнкция всех своих простых следствий. Из обзора же простых гипотез и следствий нетрудно получить (пользуясь 2°–7°) и обзор всех остальных гипотез и следствий. Такие уже встречавшиеся выше словесные выражения, как "множитель члена днф", "множители совершенной кнф" и т.п., становятся еще более понятными и оправданными после совершения еще одного, часто употребляемого в А. л. шага абстракции. Последний состоит в отождествлении И с числом 1, а Л – с числом 0. Это еще больше сближает А. л. с обычной школьной алгеброй и арифметикой. Таблица конъюнкции при этом приобретает следующий вид; 0 · 0 = 0, 0 · 1 = 0, 1 · 0 = 0, 1 · 1 = 1, т.е. конъюнкция становится обычным умножением в области чисел 0 и 1. Вводится еще одна операция А + В, задаваемая таблицей: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0. Она наз. сложением (точнее сложением по модулю 2; др. назв.: разделительная дизъюнкция; читается: "А плюс В", или "А не эквивалентно В", или "Либо А, либо В"). Всякую функцию А. л. можно представить через умножение (т.е. конъюнкцию), сложение и константу 1 (теорема Жегалкина). В частности, верны следующие тождества: VIII. А / В = AB + А + В, ? = А + 1 IX. А ? В = AB + А + 1, А А?ЛГЕБРА ЛО?ГИКИ В = А + В + 1. Обратные представления имеют вид: X. A + B = AВ / ?B, l = A / ?. Тождества VIII позволяют "переводить" выражения "языка" конъюнкции, дизъюнкции и отрицания (КДО) на "язык" умножения, сложения и единицы (УСЕ), а тождества X – осуществлять обратный "перевод". Только "переводы" эти таковы, что "переведя" по этим тождествам выражение с первого языка на второй, а то, что получится, обратно на первый, мы, как правило, получим не то выражение, из к-рого исходили, а более сложное, хотя, во всяком случае, и тождественно равное ему; пример: Тождеств. преобразования можно производить и на "языке" УСЕ, что даже гораздо удобнее, чем на "языке" КДО, т.к. они при этом гораздо более похожи на те, к-рые привычны для всех, знающих школьную алгебру. В основе их лежат следующие тождества: I. АВ =ВА, А + В = В + А (законы коммутативности); XII. (AB)С = А(ВС), (А + В) + С = А + (В + С) (законы ассоциативности); XIII. А (В + С) = AB + AC (закон дистрибутивности); XIV. АА = А, А + (В + В) = А XV. А · 1 = А. Этих тождеств достаточно для того, чтобы из них по методу тождеств, преобразований можно было вывести любое (верное) тождество, обе части к-рого суть выражения "языка" УСЕ. А добавив к ним тождества VIII, мы сможем выводить и все тождества "языка" КДО. Выражение "языка" УСЕ наз. приведенным полиномом (п.п.), если оно есть 1 + 1 (т.е. нуль) или имеет вид U1 + U2 +...+ Us где каждый член Ui есть либо 1, либо буквенная переменная, либо произведение последних, причем ни в одном члене нет никаких повторений букв, никакие два члена не одинаковы (в том же смысле, что и выше), a s не обязательно больше 1 (т.е. знаков "+"может не быть). Примеры п.п.: 1, 1 + 1, А, В, А + В + 1, ABC, А + АВ + В + ВСD, ABD + BCD + CD + CE + 1. Всякое выражение А. л. можно привести к п. п. (теорема Жегалкина). Для этого достаточно элиминировать в данном выражении 0 и знаки операций, отличные от "·" и "+", "переводя" их на "язык" УСЕ, а затем раскрыть скобки (по закону дистрибутивности, с использованием также, здесь и дальше, законов коммутативности и ассоциативности) и ликвидировать повторения букв в членах (по закону АА = А) и повторения членов (по законам А + В + В = А, А + А = 1 + 1). Тождество U = B верно, если, и только если, U и B приводятся к одинаковым п.п. Кроме "языков" КДО и УСЕ, существуют и др. "языки", равносильные им в том смысле, что всякое выражение первых переводимо на последние и обратно (в этом смысле КДО и УСЕ тоже равносильны между собой). В основу такого "языка" достаточно положить любую систему операций (и констант), обладающую тем свойством, что через операции (и константы) этой системы можно представить всякую функцию А. л. Такие системы наз. (функционально) полными (см. Полнота функциональная). Примеры полных систем: а) конъюнкция и отрицание (примеры представлений: б) дизъюнкция и отрицание (примеры представлений – тождества, двойственные предыдущим); в) импликация и отрицание [примеры представлений: АВ = А ? В, A / B = A ? B, А + В = (А ? В) ? В ? А, 0 = A ? A, 1 = A ? A); г) импликация и 0 [примеры представлений: АВ = (A ? (B ?0)) ? 0, A / B = (A ? B) ? B, A = A ? 0, 1 = 0 ? 0]; д) умножение, эквиваленция и 0 [примеры представлений: А / В = AB А?ЛГЕБРА ЛО?ГИКИ A А?ЛГЕБРА ЛО?ГИКИ B, А ? В = АВ А?ЛГЕБРА ЛО?ГИКИ А, А = А А?ЛГЕБРА ЛО?ГИКИ 0, 1 = 0 А?ЛГЕБРА ЛО?ГИКИ 0]; е) штрих Шеффера А|В [определение: A|B = AB; примеры представлений: АВ = (A|B)|(A|B), A / B = (A|A)|(B|B), A ? B = (A|B)|A, A=A|A, A + B = ((А|В)|А)|(A|В)|В), 1 = (А|А)|А)]; ж) медиана (А, В, С), отрицание и 1 [определение: (А, В, С) = АВ / АС / ВС; примеры представлений: АВ = (А, В, 1), А / B = (А, В, 1), А ? В = (А, В, 1), А А?ЛГЕБРА ЛО?ГИКИ В = (A, B, 1),(A, B, 1),1) 0 = 1]; и) медиана, эквиваленция и сложение [примеры представлений: 0 = А + А, 1 = А А?ЛГЕБРА ЛО?ГИКИ А, А = А А?ЛГЕБРА ЛО?ГИКИ (А + A) АВ = (А, В, А + А), A / B = (A, В, А А?ЛГЕБРА ЛО?ГИКИ А)]. Заметим, что для медианы имеет место ряд своеобразных тождеств; например (А, А, В) = А, (А, A, В) = В, (А, B, С) = (А, В, С) (закон самодвойственности), (А, В, С) = (В, С, А) = (А, С, В) (законы симметричности). (А, В, С) + D = (A + D, B + D, С + D) (закон дистрибутивности сложения относительно медианы), ((А, В , С), D, E) = ((A, D, E), (B, D, E), (С, D, E)) (закон самодистрибутивности). ((А, В, С), D, А) = (А, В, (С, D, А)) (закон частичной ассоциативности) и др. Можно, очевидно, строить и такие "языки", в основе к-рых лежат системы операции, не являющиеся полными (напр. конъюнкция и дизъюнкция, сложение и отрицание, медиана и отрицание, медиана и сложение, импликация и конъюнкция, отрицание и константы). Если рассматривать не только те операции, к-рые встречались выше, но вообще всевозможные операции А. л., допускающие табличное задание (т.е., по существу, всевозможные функции А. л.), то таких "языков" можно построить бесконечно много. Среди них даже найдется бесконечно много попарно неравносильных "языков" (в смысле отсутствия взаимной "переводимости" с одного "языка" на другой). Однако для всякого "языка", построенного на основе тех или иных операций А. л., существует такая конечная система тождеств этого "языка", что всякое тождество этого "языка" выводимо по методу тождеств. преобразований из тождеств этой системы (теорема Линдона). Такая система тождеств наз. (дедуктивно) полной системой тождеств (п.с.т.) данного "языка" (см. Полнота дедуктивная). Напр., тождества I–VI составляют п. с. т. "языка" КДО (если считать, что константы И и Л тоже входят в этот "язык"); тождества XI–XV – п.с.т. "языка" УСЕ, тождества I–IV – п.с.т. "языка" конъюнкции и дизъюнкции, тождества XI–XIV – п.с.т. "языка" умножения и сложения, тождества I–VII – п.с. т. "языка" конъюнкции, дизъюнкции, отрицания, импликации и эквиваленции. Впрочем, последний "язык" мало отличается от "языка" КДО из-за того, что импликация и эквиваленции могут быть в нем элиминированы (по тождествам VII). Иногда совершают еще один важный дальнейший шаг абстракции. Он состоит в том, что, рассматривая тот или иной из упомянутых выше "языков" вместе с нек-рой п. с. т. этого "языка" отвлекаются от табличного задания операций, лежащих в основе этого "языка", и от того, что значениями его буквенных переменных являются высказывания. Вместо этого допускаются различные интерпретации рассматриваемого "языка", состоящие из той или иной совокупности объектов (служащих значениями буквенных переменных) и системы операций над объектами этого множества, удовлетворяющих тождествам из п. с. т. этого "языка". "Язык" КДО в результате такого шага абстракции превращается в "язык" т.н. булевой алгебры, "язык" УСЕ – в "язык" т.н. булева кольца (с единицей), "язык" конъюнкции и дизъюнкции – в "язык" т.н. дистрибутивной структуры. Булевой алгеброй наз. любая совокупность элементов (объектов), среди к-рых выделены два элемента, обозначенные соответственно: 0 и 1, и в применение к любым элементам к-рой определены операции AB, A / B и ?, удовлетворяющие тождествам I–VI (если Л в V заменить на 0, а И в VI – на 1; вместо знака "/" в "языке" булевой алгебры чаще употребляют знак "+"). Аналогично определяются понятия булева кольца, дистрибутивной структуры, структуры (последнее связывается с тождествами I–III). Важным примером булевой алгебры является алгебра классов, в к-рой роль элементов играют подмножества (классы) нек-рого фиксированного множества (т. н. универсума) U, роль 0 – пустое множество ?, роль 1 – само U, роль AB, A / B и ? – теоретико-множеств. операции пересечения, объединения и дополнения, соответственно. Пересечением множеств А и В наз. их общая часть, т.е. множество всех элементов, принадлежащих и А и В одновременно; объединением множеств А и В наз. множество всех элементов, принадлежащих А или В; дополнением множества А наз. множество всех элементов универсума, не принадлежащих А. Другим примером булевой алгебры является алгебра предикатов (определенных на нек-рой области предметов, тоже играющей роль универсума), в к-рой роль 0 играет тождественно ложный предикат (т.е. ложный при всех значениях своих аргументов), роль 1 – тождественно истинный предикат, роль AB, A / B и ? – так же, как и в случае обычной алгебры высказываний, – конъюнкция, дизъюнкция и отрицание, соответственно. Связь между алгеброй классов, алгеброй предикатов и алгеброй высказываний, этими тремя важнейшими интерпретациями абстрактной А. л. – "языка" булевой алгебры, состоит в следующем: первая переходит во вторую путем замены множеств (классов) их т.н. характеристическими предикатами (т.е. множества А – предикатом (х?А, гласящим: "х принадлежит множеству А"), если при этом соответствующим образом преобразуются также операции и константы 0 и 1, а вторая переходит в третью при подстановке во все предикаты на место их аргументов нек-рого фиксированного их значения. Вернее, при таком переходе от алгебры классов к алгебре предикатов получается алгебра не всех предикатов (определенных на универсуме), а лишь алгебра одноместных предикатов – частный случай алгебры предикатов. Другим важным частным случаем последней является алгебра двуместных предикатов, называемых чаще отношениями. С ней тесно связана т.н. алгебра отношений, отличающаяся от нее только тем, что в последней, кроме трех операций булевой алгебры, имеются еще две операции. Всякую булеву алгебру можно "переделать" в булево кольцо, определив операцию А + В согласно X (и отбросив операцию A / B). Напр., в случае алгебры множеств роль А + В играет т.н. симметрическая разность множеств А и В (состоящая из всех тех элементов универсума, к-рые принадлежат одному и только одному из множеств А или В). Обратно, всякое булево кольцо (с единицей) можно "переделать" в булеву алгебру. Т.о., теория булевых алгебр и теория булевых колец (с единицей) – лишь разные варианты одной и той же, по существу, теории. Терминологически понятия булевой алгебры и булева кольца связываются с именем Дж. Буля. Однако оформились эти понятия (не говоря уже о терминах) значительно позже. В 17 в., когда проблема создания общих методов для решения возможно более широких классов задач была в центре внимания ученых и когда в качестве одного из таких методов (для решения математич. задач) возникла буквенная алгебра. Лейбниц первым предпринял попытку создания аналогичных общих методов (алгоритмов) и для решения задач логики. Однако решить эту задачу ему не удалось. Параллелизм между нек-рыми логич. и алгебраич. операциями подметили также ученики Лейбница, братья Якоб и Иоганн Бернулли (1685). К идеям Лейбница возвращались в дальнейшем Плуке (1763), Ламберт (1764–65), Кастийон (1805) и др. Однако первую А. л. создали (в 1847) только Дж. Буль и А. де Морган. При этом А. л. у Буля носила форму скорее не булевой алгебры, а булева кольца (т.е. была ближе к "языку" УСЕ, чем к "языку" КДО). А. л. в виде булевой алгебры разработали в дальнейшем Джевонс (1864), Пирс (начиная с 1867), Шредер (начиная с 1877), П. С. Порецкий (начиная с 1880). Пирсу и Шредеру принадлежит также разработка начал алгебры отношений. С более общей т. зр., связывающей А. л. с теорией групп, А. л. занимался также в своих первых работах Уайтхед (1898–1903). Строгое построение А. л. как кольца вычетов по модулю 2 (арифметики четного и нечетного, в виде "языка" УСЕ) осуществил (в 1927–1928) И. И. Жегалкин. Первые работы по А. л. были посвящены задачам: а) выражения логических соотношений между объемами понятий (соответственно, высказываниями) в виде уравнений (равенств), 6) построения алгоритмов решения логич. уравнении и систем уравнений с целью автоматизировать способы извлечения из данных посылок (или систем посылок) содержащейся в них (неявно) информации (того или иного рода). Для обоснования правомерности и практич. целесообразности разработанных ими методов А. л. авторы этих работ нередко предлагали для решения различные логич. задачи. В их числе можно указать, напр., следующую простую задачу, сохранившуюся в истории математич. логики под назв. задачи Венна (1876): известно, что члены (а) правления одной страховой компании суть либо владельцы облигаций (в), либо владельцы акций (с), но не те и другие одновременно. Случайно оказалось, что все владельцы облигаций компании входят в состав ее правления. Что можно сказать на основании этих сведений о соотношении между владельцами акций и владельцами облигаций этой компании? – Естественно, сказать можно, что ни один, вообще, владелец акций не есть, владелец облигаций (в·с=0). Однако, по свидетельству Венна, когда он предложил эту задачу в двух разных классах: обычных студентов-логиков и студентов, изучающих А. л., последние справились с ней значительно лучше. В наст. время А. л. развивается гл. обр. под влиянием задач, встающих в области ее приложений. Из них самую важную роль играют приложен