Новая философская энциклопедия В 4 томах. Том 1 (1184478), страница 46
Текст из файла (страница 46)
Имеет место теорема, гласящая, что всякая функция алгебры логики может быть представлена через эти три операции, т.е. записана в виде выражения,содержащего лишь знаки этих операций и буквенные переменные.Именно, любую функцию можно записать как дизъюнкцию Ф Ц ,Аг ..., A J всех выражений видафункции, и значений ее аргументов). Если Φ двойственная Ψ, а Ψдвойственная X, то Ф=Х. Напр., конъюнкция и дизъюнкция двойственны между собой, отрицание двойственно самому себе, константа И (как функция) двойственна константе Л. Функция Ф Ц , А2,...,Ап) двойственна функции Ψ(Λ|; А,,..., Ап), если, и только если, вернотождество-пфц,4, -Л> = ? ( Ч -Ч. •· > -А)·Совершенную кнф и сокращенную кнф можно определить как такие кнф, что двойственные им выражения есть соответственно совершенная днф и сокращенная днф.
Совершенные и сокращенныеднф и кнф можно использовать для решения задачи обзора всех гипотез и вех следствий данного выражения алгебры логики. Причемпод гипотезой выражения А алгебры логики естественно пониматьтакое выражение В, что В—А тождественно истинно, а под следствием выражения А - такое выражение В, что А—В тождественноистинно.Еще один, часто употребляемый в алгебре логики шаг абстракции,состоит в отождествлении И с числом 1, а Л - с числом 0. Вводитсяоперация А+В, задаваемая таблицей: 0+0=0, 0+1=1,1+0=1,1+1=0.Она называется сложением (точнее сложением по модулю 2; другоеназвание: разделительная дизъюнкция; читается: «А плюс В», или «Лне эквивалентно В», или «Либо А, либо В»).Всякую функцию алгебры логики можно представить через умножение (т.
е. конъюнкцию), сложение и константу 1 (теорема Жегалкина). В частности, верны следующие тождества:VIII.IX.Ф(а,, а2,..., а)-{АГа) (А~а2)...(А~а),где а , а2,..., ап — набор из значений И, Л. Заменяя в этой дизъюнкции выражения А~Ш на Av а А~Л — на - Ц , а также стирая «коэффициенты» Ф(а | ; а„ ..., а), равные И (по закону И-А=А) и отбрасывая члены с «коэффициентами», равными Л (по законам (Л-А=Л,ΛνΑ = А), мы и получим (если функция не есть константа) то выражение, о котором говорится в теореме.Дизъюнктивной нормальной формой (днф) называется выражение,которое есть буква И или Л или имеет вид А^А^ ..., νΑα, где каждыйчлен А1 является либо буквенной переменной, либо ее отрицанием,либо конъюнкцией таковых, причем s не обязательно отлично от 1,т.е.
знаков «ν» может и не быть. Днф называется совершенной, еслиона есть И или Л или в каждом члене содержит ровно по одномуразу все имеющиеся в ней буквы (переменные) и не имеет одинаковых членов. Всякое выражение алгебры логики можно привестик днф. А всякую днф можно привести к совершенной днф, «домножая» члены на недостающие буквы (по закону Α=ΑΒνΑ^Β) и ликвидируя повторения букв в членах (по закону АА=А, А-А=- Л, Л-Л=Л,ΛνΑ=Α) И повторения членов (по закону AvA=A).Приведение к совершенной днф позволяет по любым двум даннымвыражениям А и В решить вопрос о том, одну ли и ту же функциюони выражают, т.е.
верно ли тождество А=В.Важную роль играет т. н. сокращенная днф. Последнюю можноопределить как такую днф, в к-рой 1) нет повторений букв нив одном члене, 2) нет таких пар членов А и Α., что всякий множитель из А. имеется и в А и 3) для всех двух таких членов, изк-рых один содержит множителем некоторую букву, а другой отрицание той же буквы (при условии, что другой буквы, длякоторой это имеет место, в данной паре членов нет), имеется(в этой же днф) член, равный конъюнкции остальных множителейэтих двух членов.Кроме днф, употребляются также конъюнктивные нормальныеформы (кнф). Это такие выражения, к-рые можно получить из днфпутем замены в них знаков «ν» на «•», а «•» на «ν».Преобразованием двойственности называется такое преобразованиевыражения алгебры логики, при котором в этом выражении знакивсех операций заменяются на знаки двойственных им операций, аконстанты: И на Л, Л на И; причем операция (или функция) Φ называется двойственной для операции Ψ, если таблица, задающая Ф,получается из таблицы, задающей Ψ, путем замены в ней всюду Ина Л, а Л на И (имеется в виду одновременная замена и значенийΑνΒ=ΑΒ+Α+Β,-Α=Α+\А-В=АВ+А+\,А~В=А+В+\.Обратные представления имеют видΧ.Α+Β= Α-ηΒν^ АВ, l=Av^A.Тождества VIII позволяют «переводить» выражения «языка» конъюнкции, дизъюнкции и отрицания (КДО) на «язык» умножения,сложения и единицы (УСЕ), а тождества X - осуществлять обратный «перевод».Тождественные преобразования можно производить и на «языке»УСЕ.
В основе их лежат следующие законы:XI. АВ=ВА, А+В+В+А (законы коммутативности);XII. (АВ)С=А(ВС), (А+В)+С=А+(В+С) (ассоциативности);XIII. А(В+С)=АВ+АС (закон дистрибутивности);XIV. АА=А, А+(В+В)=АXV. А 1 = АЭтих тождеств достаточно для того, чтобы из них можно было вывести любое (верное) тождество, обе части которого суть выражения«языка» УСЕ. А добавив к ним тождества VIII, мы сможем выводитьи все тождества «языка» КДО.Выражение «языка» УСЕ называется приведенным полиномом (п.п.), если оно есть 1+1 (т.
е. нуль) или имеет вид А{+А2+...+А^ гдекаждый член А есть либо 1, либо буквенная переменная, либо произведение последних, причем ни в одном члене нет никаких повторений букв, никакие два члена не одинаковы (в том же смысле,что и выше), a s не обязательно больше 1 (т.
е. знаков «+» может небыть). Всякое выражение алгебры логики можно привести к п. п.(теорема Жегалкина).Кроме «языков» КДО и УСЕ существуют и другие «языки», обладающие тем свойством, что через операции (и константы) этих «языков» можно представить всякую функцию алгебры логики. Такиесистемы называются (функционально) полными. Примеры полныхсистем: а) конъюнкция и отрицание, б) дизъюнкция и отрицание,в) импликация и отрицание, г) импликация и 0, д) умножение, эквиваленция и 0, е) штрих Шеффера А\В, ж) медиана [А, В, Q, [определение: (А, В, Q=ABvACvBC\, отрицание и 1, и) медиана, эквивал е н т ы и сложение.Иногда совершают еще один важный дальнейший шаг абстракции.Отвлекаются оттабличного задания операций и оттого, что значениями буквенных переменных являются высказывания.
Вместо этогодопускаются различные интерпретации рассматриваемого «языка»,состоящие из той или иной совокупности объектов (служащих значе-74АЛГЕБРА Л О Г И К Иниями буквенных переменных) и системы операций над объектамиэтого множества, удовлетворяющих тождествам из полной системытождеств этого «языка». «Язык» КДО в результате такого шага абстракции превращается в «язык» т.
н. булевой алгебры, «язык» УСЕ в «язык» т. н. дистрибутивной структуры.Важным примером булевой алгебры является алгебра классов,в которой роль элементов играют подмножества (классы) некоторого фиксированного множества (т. н. универсума) U, роль Оиграет пустое множество 0, роль 1 - само О, роль АВ, А\>Ви -А - теоретико-множеств.
операции пересечения, объединенияи дополнения соответственно. Связь между алгеброй классов, алгеброй предикатов и алгеброй высказываний, этими тремя важнейшими интерпретациями абстрактной алгебры логики как «языка»булевой алгебры, состоит в следующем: первая переходит во вторуюпутем замены множеств (классов) их т. н. характеристическимипредикатами (т.
е. множества А - предикатом χεΑ, гласящим: «хпринадлежит множеству А»), если при этом соответствующим образом преобразуются также операции и константы 0 и 1, а втораяпереходит в третью при подстановке во все предикаты на место ихаргументов некоторого фиксированного их значения. Вернее, притаком переходе от алгебры классов к алгебре предикатов получаетсяалгебра одноместных предикатов. Другим важным случаем являетсяалгебра двуместных предикатов, называемых чаще отношениями. Сней тесно связана алгебра отношений, отличающаяся от нее толькотем, что в последней, кроме трех операций булевой алгебры, имеются еще две.Всякую булеву алгебру можно «переделать» в булево кольцо, определив операцию А+В согласно закону X (и отбросив операцию Αν В).Напр., в случае алгебры множеств роль А+В играет т.
н. симметрическая разность множеств Aw В (состоящая из всех тех элементовуниверсума, которые принадлежат одному и только одному из множеств А или В). Обратно, всякое булево кольцо (с единицей) можно«переделать» в булеву алгебру. Понятия булевой алгебры и булевакольца связываются с именем Дж. Буля. Однако оформились этипонятия (не говоря уже о терминах) значительно позже.Первые работы по алгебре логики были посвящены задачам: а)выражения логических соотношений между объемами понятий(соответственно высказываниями) в виде уравнений (равенств), б)построения алгоритмов решения логических уравнений и системуравнений с целью автоматизировать способы извлечения из данных посылок содержащейся в них (неявно) информации (того илииного рода).В настоящее время алгебра логики развивается гл.
о. под влияниемзадач, встающих в области ее приложений. Она находит широкоеприменение в технике (особенно при решении задач, связанных спостроением автоматов) и, наоборот, развивается сама под влиянием запросов техники (задач автоматизации программирования,уменьшения числа элементов в устройствах релейного действияи др.). Важную роль играют приложения в теории электрическихсхем, включая первоначально, начиная с работ В. И.
Шестакова иК. Шеннона (30-40-е гг. 20 в.), теорию релейно-контактных схем.Вопросы, касающиеся понятий самой алгебры логики, приводят кпроникновению в алгебру логики неалгебраических методов (таких,как табличные, топологические, дескриптивные) и вследствие этого к постепенному выделению из алгебры логики самостоятельнойобласти - теории функций алгебры логики (или иначе, теории булевых функций).В случае более сложных схем, чем контактные, приходится часто отказываться от использования лишь обычной алгебры логики и рассматривать те или иные ее многозначные обобщения, отличные отбулевых алгебр и булевых колец (см. Многозначные логики). Другимнаправлением современного развития алгебры логики является алгебраическая логика.
Она интересна тем, что выдвигает и частичнорешает задачу построения алгебр неклассических логик, т.е. такихвариантов алгебры логики, которые соответствуют неклассическимисчислениям высказываний.Некоторые тенденции возможного дальнейшего развития алгебрылогики как совокупности алгебраических методов логики намечаются в связи с бурным развитием ряда областей как современнойалгебры, так и математической логики. Одна из них связана с мощным ростом теоретико-множественной алгебры, позволяя всякуюоперацию рассматривать как алгебраическую операцию. Такое рассмотрение дает возможность охватить алгебраическими методамизначительную часть современной математической логики (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
