Булева алгебра

Кишинёв 1999
г. 2) В данном реферате я попытаюсь раскрыть,
некоторые аспекты булевой алгебры. Математическая логика является современной
формой, так называемойформальной логики, применяющей математические методы для
исследо­вания своего предмета. (Другие ее названия: символическая логика,
теоретическая логика,логистика.) В формальной логике и, соответственно, в
математической логике, собраны результаты законов структуры пра­вильных выводов.
Вывод является такиммыслительным процессом, в результате которого появляются
новые открытия на основании уже имеющихся (которые предполагаются правильными),
без практическихисследований. В действительности, новое открытие, полученное в
резуль­тате вывода, (так называемый окончательный вывод) в скрытой форме
находится впредварительно имеющихся знаниях, в так называемых
предпосылках. Простейшие закономерности выводов
открывались человечеством эмпи­рическим путем в ходеобщественного производства
(например, простей­шие соотношения арифметики и геометрии). Открытие более
сложных законов связано с результатами наукиформальной логики. Первое круп­ное
обобщение формальной логики принадлежит Аристотелю. В фор­мальной логике с
самого начала применялись (в единичныхслучаях) математические методы, но
развитие логики не успевало за применением таких методов по сравнению с другими
областями математики. Поэтому формальнаялогика отстала от потребностей науки (в
первую очередь от требований математики); отставание оказалось особенно
очевидным в новую эру. Главныминедостатками формальной логики являлись
сле­дующие . 1. Она не сумела привести законы выводов к небольшому
количеству надежных логических законов; поэтому подтвердила правильность
не­которых выводов наоснове экспериментов, которые позже были опро­вергнуты
примерами, доказывающими обратное. 2. Она была неспособна анализировать
значительную часть выводов, применяемых вповседневной и научной жизни; доказать
правильность или неправильность таких выводов. (Например, не могла доказать, что
из правильности предложения «Каждаятрапеция является четырех­угольником»
вытекает правильность предложения «Кто рисует трапецию, тот рисует
четырехугольник). Задача математизации формальной логики была поставлена и
осущест­влена Лейбницем. Егоработу продолжили математики XIX века. На рубеже
столетия с открытием противоречий в теории множеств (см. гл. «Теория множеств»)
развитие математическойлогики получило широкий размах. В настоящее время
результаты математической логики исполь­зуются во всех традиционных областях
формальной логики;открыты совершенно новые области. В
настоящее время «традиционная» формаль­ная логика по сравнениюс математической
логикой имеет значение только для истории науки. Математическая логика не
претендует на открытие законов мышления вообще, или еще в меньшейстепени на
анализ философских проблем, связанных с человеческим мышлением. Эти вопросы
больше относятся к «логике» (в более общем смысле слова) и к философии.
(Вдальнейшем под словом «логика» будем подразумевать математическую
логику.) Для более точного определения
предмета математической логики сле­довало бы уточнить,что подразумевается под
термином логически пра­вильного вывода.Чтобы сформулировать хотя бы одно
временное опре­деление, рассмотрим пример вывода. (В соответствии с традиционной
формой записывания, предпосылкиотделяются от окончательного вы­вода
горизонтальной чертой): Будет раздача
премии.
Если принять правильность предпосылок, то следует принять и
пра­вильность окончательного вывода. Другой, аналогичный пример
: Обычно вместо предложений (мне выпал туз)
и (я иду ва-банк) могут быть записаны любые такие изъявительные предложения,
значения кото­рых может быть правильноили ложно; следует оставить неизменными
только расположение слов «если» и «то» и расположение предположений, то есть
структуру вывода. Пусть А и В обозначаетлюбые заменяющие предложения.
Под определением, что данная схема представляет собой
(логически правильную) схемувыводов, подразумевается следующее. Если вместо А и
В подставить такие предложения, что предпосылки, полученные в результате замены,
будутправильными, то и окончательный вывод будет правильным. Любой человек,
который понимает значение союзов «если . . . то», поймет, что это правильная
схемавывода. В схеме вывода фигу­рируют несколько слов с постоянным значением,
далее несколько сим­волов (букв) с меняющимся значением. Символы с
меняющимсязначением могут быть переменными разных типов. В соответствии с их
типом вместо символов могут быть подставлены разные грамматические формации
(на­пример :изъявительные предложения, слова, выражающие свойства, названия
предметов и т. д.). В предыдущем примере переменные А и В заменяются только
изъявительнымипредложениями. На основе «регуляр­ной» замены переменных некоторой
(правильной) схемы вывода должен возникать правильный вывод. Но
определение «регулярной замены» означает не только соблюдение
грамматическихправил. В предыдущей схеме А и В могут означать только такие
изъявительные предложения, правильность или ложность которых может быть решена
однозначно.Такие изъявительные предложения будем называть
высказываниями. На основе любой схемы вывода может быть получен правильный
вывод только при соблюдении условий подобного характера. Путем изменения условий
могут бытьпостроены различные теории логики. Важнейшими главами
математической логики являются калькуляция высказываний и калькуляцияпредикатов.
В рамках данных глав может быть исследована схема вывода в самом общем случае
при наименьшем числе условий. КАЛЬКУЛЯЦИЯВЫСКАЗЫВАНИЙ Предметом калькуляции
высказываний является анализ таких схем вывода, при которых с заменой переменных
на высказывания, получаются правильные выводы. Под термином высказывания
подразумевается такое изъявительное предложение, котороеявляется однозначно или
правильным, или лож­ным ; итак: б) исключено, чтобы
оно было и неправильным, и неложным (принцип исключения третьей
возможности). При данных
обстоятельствах приведенные выше изъявительные пред­ложения удовлетворяют (с
«хорошим приближением») этим двум условиям; их можно считать
высказываниями. Поэтому логика, построенная на этих двух условиях, может
получить весьма широкое применение. Естественно, существуюттакие «тонкие
обстоятельства», при которых некоторых изъявительных предложений нельзя считать
высказываниями (например, если дано предложение : «Иван просыпается»,вряд ли
можно сомневаться в правильности или ложности предложения «Иван спит»).
Математические термины определяются таким образом, что предложения,
выражающиесоотношения между ними, всегда считаются высказываниями; такое
по­ложение существует во всех точных науках. В выводах могут
фигурировать высказывания (либо в виде предпосы­лок, либо какокончательный
вывод), возникшие из одного или несколь­ких высказываний, путем применения
некоторого грамматического ме­тода; они называются сложнымивысказываниями. Во
многих случаях правильность вывода зависит от вида формирования сложного
высказы­вания. Поэтому необходимо заниматься видомформирования сложных
высказываний некоторых типов. Под термином калькуляции высказываний
подразумевается такой метод, с помощью которого из одного или нескольких
высказываний (членов операции калькуляциивысказываний) получается такое
выска­зывание (результат операции), правильность или ложность которого
однозначно определяется правильностью или ложностьючленов. Двумя простейшими примерами вышеприведенной операции являются
отрицание и конъюнкция. (Операция и результат операции здесь обозна­чается одним
и тем женазванием.) Под отрицанием высказывания А подразумевается
высказывание «Не­правильно, что А»(или некоторая грамматически преобразованная
форма данного высказывания). По значению выражения «неправильно» отрицание
А правильно тогда и только тогда,если самое А неправильно; следовательно,
отрицание действительно есть операция калькуляции высказываний (в соответствии с
вышеприведенным определением). Отрицанием предложения
«мотор работает» является пред­ложение «неправда, что моторработает» или, иначе:
«мотор не работает». Отрицание является одночленной операцией. Отрицание
«А» обозна­чается символом «~А»(читается : «не А»). Применяются также и
обозна­чения «~ А», «— А», «А». Под конъюнкцией двух высказываний А и В
подразумевается высказы­вание «А и В» (илинекоторая грамматически измененная
форма данного высказывания). По значению союза «и» конъюнкция является
правильной тогда и только тогда, если оба еечлена правильны. Таким
образом, конъюнкция также является операцией калькуляции высказываний.
Операцияконъюнкции «А и В» представляет собой двучленную операцию; ее
обозначают, «А & В», «АВ». При возник­новении конъюнкции союз «и» иногда
заменяется другимсоюзом (напри­мер, «Анатолий здесь, но Бориса нет» или
«Анатолий здесь, хотя Борис ушел» и т. д.). Это не влияет на правильность или
ложность результата,имеет только эмоциональное значение. Иногда союз вообще
пропускается. Если сказуемые двух предложений, связанных между собой путем
конъ­юнкции, совпадают,то общее сказуемое представлено только в одном из
предложений. Например, конъюнкция «я питаюсь хлебом и питаюсь водой» после
преобразования имеетследующий вид: «я питаюсь хлебом и водой». Изучение
остальных операций калькуляции высказываний уточняется и облегчается с
помощьюследующего рассуждения. Пусть свойства высказываний «правильное» и
«ложное» называются логическими значениямии обозначаются знаками пил.
Правильность (или ложность) некоторого высказывания А выражается и в такой
форме, что логическим значением высказывания А являетсяп (или л). Если
задаются логические значения отдельных членов в некоторой операции
калькуляциивысказываний, то данной операцией логическое значение результата
определяется однозначно. Это позволяет определе­ние таких операций для
логических значений(кромевышеприведенного определения для высказываний)
следующим образом: На место и членов и результата подставляются логические
значения; причем, вместоре­зультата подставляется логическое значение
высказывания, образую­щееся данной операцией из высказываний с соответствующими
членам логическимизначениями. (так как отрицание правильного выска­зывания является
ложным), (так как
если одно или оба из двух высказываний являются ложными, то и их конъюнкция
будет ложной) На основе вышеприведенного рассуждения изучение операций,
про­веденных на высказываниях, может быть заменено изучением операций,
проведенных налогических значениях. Этого достаточно для исследо­вания выводов
(на уровне калькуляции высказываний). Операции, проводимые на логических значениях, называются
логи­ческими операциями. Для выражения любых логических значении вво­дятся
логическиепеременные; они обозначаются символами . При использовании нескольких операций последовательно порядок
выполнения отдельныхоперации обозначается скобками; например, ~(р) А q) (иногда
скобки опускаются). Например, вместо выражения (7p)/\q пишется 7р /\ q при
предварительном пояснении, что вслучае появления выражения без скобок знак
относится только к следующему знаку. -
членной логической операцией называется каждая такая функция, областью
существованиякоторой является упо­рядоченное множество всех выражений,
образуемых из логических зна­чений пиле длиной выражения Любая логическая
операция может быть выражена через операции от­рицания и
конъюнкции. В области операций
на логических переменных помимо отрицания и конъюнкции оказываются полезными
некоторые другие операции. дизъюнкция Операция называется дизъюнкцией и обозначается символом
«p\/q» (иначе ее называют альтернацией, адъюнкцией,логическим сложением), или «р
+ q». Дизъюнкция выражается с помощью операций конъюнкции и
отрицания. Связь, созданная между двумя высказываниями при помощи
уступитель­ного союза «или»,является такой операцией, которой в области
логиче­ских значений соответствует операция дизъюнкции: высказываниеявляется
ложным тогда и только тогда, если оба высказывания ложны. (Союз «или» в
таком случае применяется в значении допущения, если допускаетсяправильность
обоих высказываний). Например: «выпал дождь или полили парк». Поэтому такое
соединение двух высказываний также называется дизъюнкцией.(Символ «V» читается
также как «или»). Таким образом, руководствуясь теоремой, что каждая логическая
операция может быть выражена с помощью только операцийдизъюнкции и
отрицания р Допустим, что если р = п, то значение выражения р
влечёт q будет или п, или л в зависимости от того, является ли значение q п, или
л. Это анало­гичнотому, что высказывание типа «если А, то В», в котором первый
член А является правильным, считается или правильным, или ложным в за­висимости
от того,правильный или ложный второй его член В. Поэтому соединению типа «если
А, то В» соответствует импликация в области ло­гических значений. Но в то же
время приложном высказывании А пред­ложение типа «если А, то В» может вообще не
считаться высказыванием Например: если горит лампочка, то лифт
работает. Если высказывание «горит лампочка» правильно, то правильностью
высказывания «лифтработает» однозначно решается правильность выше­приведенного
предложения. Но если высказывание «горит лампочка» ложно, то ничего нельзя
сказать оправильности вышеприведенного предложения. Можно сказать : надо
подождать, пока лампочка загорится Приведем пример, в котором не будет даже
возможности«подождать»: Если 2 * 2 = 5, то Дунай является европейской
рекой. Если принять то, что соединениетипа «если . . .то» соответствует операции
импликации, при соблюдении последнего тождества высказывание «если А, то В»
вы­ражалось бы с помощьюопераций конъюнкции и отрицания в следующем виде :
«неправильно, что : А и не В» (здесь присутствует выражение «не В» вместо
выражения «неправильно, что В»;таким образом, ясно, что выражение «неправильно,
что», расположенное в начале высказывания, относится не только к Л, но и к
выражению «А и не В»). Всоответствии с этим приведенные выше два предложения в
примере могут быть пере­формулированыследующим образом: б) Неправильно, что 2 * 2 = 5 и
Дунай не является европейской рекой. Если выражение «горит лампочка» ложно, то
ложно и выражение «лампочка горит и лифтне работает», а отрицание его — по а) —
является правильным. Выражение. «2 * 2 = 5» ложно, ложно также и выражение
«Дунай не является европейской рекой»; ихконъюнкция — также ложна, а отрицание
этой конъюнкции — по б) — является правильным. Здесь нет противоречия по
сравнению с обычным пониманием вещей, таккак обычно не обращают внимание на
правильность сложного пред­ложения типа «если . . . то» в том случае, когда
первый член соединения является ложным. Выражения вида «если А, то В»
можно считать синонимами выражений вида «неправильно, что:«А и не В»; они
называются импликациями (с предварительным членом А, с последующим членом В);
для их обо­значения применяется символ А влечёт В.
соответствует понятию вышеприведенной операциивысказы­вания. Операции на
высказываниях, выражаемые с помощью союзов и частиц, сформулированынедостаточно
точно ; в большинстве случаев, они до некоторой степени двусмысленны. По всей
вероятности распознавание операций конъюнкции и отрицаниянаименее проблематично
в их грамма­тической форме представления. Поэтому большое значение имеет
воз­можность выражения любой логической операции черезоперации конъ­юнкции и
отрицания. Как было показано выше, это позволило нам истолковать образование
сложного предложения вида «если . . . то» как операцию. Упоминаются еще
некоторые грамматические синонимы операции «А влечёт В»: «В, если толькоЛ»,
«Только тогда А, если В», «Достаточным условием В является А», «Необходимым
условием А является В», «В если не А». Поэтому любая
логическая операция может быть выражена с помощью операций отрицания
иимпликации. Так как высказывание p эквивалентно q = n тогда и только
тогда, когда p = q, то данная логическая операция соответствуетобразованию
сложного предложения вида «А тогда и только тогда, когда В». Понимание и
логи­ческое значение предложения такого характера, образованного издвух любых
высказываний, иногда затруднительно для восприятия человека, как и понимание
предложения вида «если . . . то». Например, «2 < 3 тогда и толькотогда, если
светит солнце». Поэтому данное предложение понимается операцией
калькуляции высказываний исключительнов том случае, если считать его синонимом
высказываний вида «неправильно, что А и не В, и, неправильно, что не А и В». В
этом случае данная операция «А влечётВ» и называется
эквивалентностью. Часто встречаются следующие синонимы данной операции:
«Для А необходимо и достаточноб», «А именно тогда, когда
В». Булеву алгебру образуют все подмножества некоторого
множества. То, что они образуютрешетчатую структуру, очевидно. Не­трудно
доказать и выполнение дистрибутивности. Нулевым элементом является пустое
множество, а единичным —все основное множество. Для каждого подмножества
существует дополнительный элемент — дополнение к множеству в теоретико-
множественном смысле. Булевыалгебры находят применение главным образом в теории
мно­жеств, в математической логике, в теории вероятностей и в функциональ­ном
анализе. 1. Малая
математическая энциклопедия. Э. Фрид., И. Пастор., И. Рейман., П. Ревес.,
И. Ружа. Издательсво академии наук Венгрии. Будапешт 1976 г. 3. Пособие по математика для поступающих в ВУЗЫ. Под редакцией Г. Н.
Яковлева Москва «наука» 1988 г.