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

Размещено на http://www.allbest.ru/

Реферат

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

Введение

В данном реферате я попробую раскрыть, некие аспекты булевой алгебры. Математическая логика является современной формой, так называемой формальной логики, применяющей математические способы для исследования собственного предмета. (Остальные её наименования: символическая логика, теоретическая логика, логистика.) В формальной логике и, соответственно, в математической логике, собраны результаты законов структуры правильных выводов. Вывод является таковым мыслительным действием, в итоге которого возникают новейшие открытия на основании уже имеющихся (которые предполагаются правильными), без практических исследований. В реальности, новое открытие, полученное в результате вывода, (так называемый окончательный вывод) в скрытой форме находится в предварительно имеющихся знаниях, в так называемых предпосылках.

Предмет математической логики

Простые закономерности выводов раскрывались человечеством эмпирическим методом в ходе публичного производства (к примеру, простейшие соотношения арифметики и геометрии). Открытие более сложных законов связано с плодами науки формальной логики. Первое крупное обобщение формальной логики принадлежит Аристотелю. В формальной логике с самого начала применялись (в единичных вариантах) математические способы, но развитие логики не успевало за применением таковых способов по сравнению с другими областями математики. Поэтому формальная логика отстала от потребностей науки (в первую очередь от требований математики); отставание оказалось в особенности естественным в новенькую эру. Главными недостатками формальной логики являлись следующие .

1. Она не смогла привести законы выводов к небольшому количеству надежных логических законов; поэтому подтвердила правильность некоторых выводов на базе экспериментов, которые позднее были опровергнуты примерами, доказывающими обратное.

2. Она была неспособна анализировать значительную часть выводов, применяемых в повседневной и научной жизни; доказать правильность либо неправильность таковых выводов. (К примеру, не могла доказать, что из правильности предложения «Каждая трапеция является четырехугольником» вытекает правильность предложения «Кто рисует трапецию, тот рисует четырехугольник).

Задачка математизации формальной логики была поставлена и осуществлена Лейбницем. Его работу продолжили математики XIX века. На рубеже столетия с открытием противоречий в теории множеств (см. Гл. «Теория множеств») развитие математической логики получило широкий размах. В настоящее время результаты математической логики используются во всех обычных областях формальной логики; открыты совсем новейшие области. В настоящее время «традиционная» формальная логика по сравнению с математической логикой имеет значение лишь для истории науки.

Математическая логика не претендует на открытие законов мышления вообще, либо еще в меньшей степени на анализ философских заморочек, связанных с человеческим мышлением. Эти вопросы больше относятся к «логике» (в более общем смысле слова) и к философии. (В дальнейшем под словом «логика» будем подразумевать математическую логику.)

Что такое вывод?

Для более чёткого определения предмета математической логики следовало бы уточнить, что предполагается под термином логически правильного вывода. Чтоб сконструировать хотя бы одно временное определение, рассмотрим пример вывода. (В согласовании с традиционной формой записывания, предпосылки отделяются от окончательного вывода горизонтальной чертой):

1. (Предпосылки) Если будет раздача премии, то мы выполнили план.

Будет раздача премии.

(Окончательный вывод) Мы выполнили план.

Если принять правильность предпосылок, то следует принять и правильность окончательного вывода. Другой, аналогичный пример :

Если мне выпадет туз, то я иду ва-банк.

Мне выпал туз.

Я иду ва-банк.

Традиционно за место предложений (мне выпал туз) и (я иду ва-банк) могут быть записаны любые такие изъявительные предложения, значения которых может быть верно либо ложно; следует бросить постоянными лишь размещение слов «если» и «то» и размещение догадок, то есть структуру вывода. Пусть А и В обозначает любые заменяющие предложения. Структуру вывода можно выразить следующей схемой;

Если А, то В

А

В

Под определением, что данная схема представляет собой (логически правильную) схему выводов, предполагается следующее. Если за место А и В подставить такие предложения, что предпосылки, полученные в итоге замены, будут правильными, то и окончательный вывод будет правильным. Хоть какой человек, который соображает значение союзов «если . . . то», поймет, что это верная схема вывода. В схеме вывода фигурируют несколько слов с неизменным значением, далее несколько символов (букв) с меняющимся значением. Знаки с меняющимся значением могут быть переменными различных типов. В согласовании с их типом за место знаков могут быть подставлены различные грамматические формации (например : изъявительные предложения, слова, выражающие характеристики, наименования предметов и т. Д.). В прошлом примере переменные А и В заменяются лишь изъявительными предложениями. На базе «регулярной» замены переменных некой (правильной) схемы вывода обязан возникать верный вывод.

Но определение «регулярной замены» значит не лишь соблюдение грамматических правил. В предшествующей схеме А и В могут означать лишь такие изъявительные предложения, правильность либо ложность которых может быть решена однозначно. Такие изъявительные предложения будем именовать высказываниями.

На базе хоть какой схемы вывода может быть получен верный вывод лишь при соблюдении условий подобного характера. Методом конфигурации условий могут быть построены разные теории логики.

Важнейшими главами математической логики являются калькуляция высказываний и калькуляция предикатов. В рамках данных глав может быть изучена схема вывода в самом общем случае при наименьшем числе условий.

В остальных главах логики рассматриваются особые схемы вывода, являющиеся менее общими.

Предметом калькуляции высказываний является анализ таковых схем вывода, при которых с заменой переменных на высказывания, получаются правильные выводы.

Под термином высказывания предполагается такое изъявительное предложение, которое является однозначно либо правильным, либо ложным ; итак:

а) оно не может сразу быть и правильным, и ложным (принцип непротиворечивости);

б) исключено, чтоб оно было и неверным, и неложным (принцип исключения третьей способности).

Характеристики «правильное» и «ложное» предполагаются в их обычном смысле; они не нуждаются в дальнейшем анализе.

При данных обстоятельствах приведенные выше изъявительные предложения удовлетворяют (с «хорошим приближением») этим двум условиям; их можно считать высказываниями. Поэтому логика, построенная на этих двух условиях, может получить очень обширное применение. Естественно, есть такие «тонкие обстоятельства», при которых неких изъявительных предложений нельзя считать высказываниями (к примеру, если дано предложение : «Иван просыпается», вряд ли можно сомневаться в правильности либо ложности предложения «Иван спит»). Математические определения определяются таковым образом, что предложения, выражающие соотношения меж ними, постоянно числятся высказываниями; такое положение существует во всех чётких науках.

Понятие «высказывание» время от времени обозначается словами «утверждение», «суждение».

В выводах могут фигурировать высказывания (или в виде предпосылок, или как окончательный вывод), возникшие из одного либо нескольких высказываний, методом внедрения некого грамматического метода; они именуются сложными высказываниями. Во многих вариантах правильность вывода зависит от вида формирования сложного высказывания. Поэтому нужно заниматься видом формирования сложных высказываний неких типов.

Под термином калькуляции высказываний предполагается таковой способ, с помощью которого из одного либо нескольких высказываний (членов операции калькуляции высказываний) выходит такое высказывание (итог операции), правильность либо ложность которого однозначно определяется правильностью либо ложностью членов.

Отрицание и конъюнкция

Двумя простейшими примерами вышеприведенной операции являются отрицание и конъюнкция. (Операция и итог операции тут обозначается одним и тем же заглавием.)

Под отрицанием высказывания А предполагается высказывание «Неправильно, что А» (либо некая грамматически преобразованная форма данного высказывания).

По значению выражения «неправильно» отрицание А верно тогда и лишь тогда, если самое А неправильно; следовательно, отрицание вправду есть операция калькуляции высказываний (в согласовании с вышеприведенным определением).

Пример: Отрицанием предложения «мотор работает» является предложение «неправда, что мотор работает» либо, по-другому: «мотор не работает».

Отрицание является одночленной операцией. Отрицание «А» обозначается эмблемой «~А» (читается : «не А»). используются также и обозначения «~ А», «-- А», «А».

Под конъюнкцией двух высказываний А и В предполагается высказывание «А и В» (либо некая грамматически измененная форма данного высказывания). По значению союза «и» конъюнкция является правильной тогда и лишь тогда, если оба её члена правильны.

Таковым образом, конъюнкция также является операцией калькуляции высказываний. Операция конъюнкции «А и В» представляет собой двучленную операцию; её обозначают, «А & В», «АВ». При возникновении конъюнкции альянс «и» время от времени заменяется иным союзом (например, «Анатолий тут, но Бориса нет» либо «Анатолий тут, хотя Борис ушел» и т. Д.). Это не влияет на правильность либо ложность результата, имеет лишь эмоциональное значение. Время от времени альянс вообще пропускается. Если сказуемые двух предложений, связанных меж собой методом конъюнкции, совпадают, то общее сказуемое представлено лишь в одном из предложений. К примеру, конъюнкция «я питаюсь хлебом и питаюсь водой» после преобразования имеет следующий вид: «я питаюсь хлебом и водой».

Исследование других операций калькуляции высказываний уточняется и облегчается с помощью следующего рассуждения.

Пусть характеристики высказываний «правильное» и «ложное» именуются логическими значениями и обозначаются знаками пил. Правильность (либо ложность) некого высказывания А выражается и в таковой форме, что логическим значением высказывания А является п (либо л).

Если задаются логические значения отдельных членов в некой операции калькуляции высказываний, то данной операцией логическое значение результата определяется однозначно. Это дозволяет определение таковых операций для логических значений (не считая вышеприведенного определения для высказываний) следующим образом: На место и членов и результата подставляются логические значения; причем, заместо результата подставляется логическое значение высказывания, образующееся данной операцией из высказываний с соответствующими членам логическими значениями.

К примеру, отрицания логических значений определяются так:

 (так как отрицание правильного высказывания является ложным),

(так как отрицание ложного высказывания является правильным);

а конъюнкции логических значений так:

(так как конъюнкция двух правильных высказываний является правильной),

(так как если одно либо оба из двух высказываний являются ложными, то и их конъюнкция будет ложной)

На базе вышеприведенного рассуждения исследование операций, проведенных на высказываниях, может быть заменено исследованием операций, проведенных на логических значениях. Этого довольно для исследования выводов (на уровне калькуляции высказываний).

Алгебра логических значений

Операции, проводимые на логических значениях, именуются логическими операциями. Для выражения всех логических значении вводятся логические переменные; они обозначаются знаками p, q, r, ..., р, р, … Итак, логические переменные могут воспринимать два «значения»:

п либо л.

При использовании нескольких операций последовательно порядок выполнения отдельных операции обозначается скобками; к примеру, ~(р) А q) (время от времени скобки опускаются). к примеру, за место выражения (7p)/q пишется 7р / q при предварительном пояснении, что в случае появления выражения без скобок символ относится лишь к следующему знаку.

В общем смысле слова n-членной логической операцией именуется любая таковая функция, областью существования которой является упорядоченное множество всех выражений, образуемых из логических значений пиле длиной выражения n, а значением её является одно из двух логических значений п и л.

неважно, какая логическая операция может быть выражена через операции отрицания и конъюнкции.

некие остальные ЛОГИЧЕСКИЕ ОПЕРАЦИИ

В области операций на логических переменных кроме отрицания и конъюнкции оказываются полезными некие остальные операции.

В области одномерных логических операций фактический энтузиазм представляет лишь отрицание.

дизъюнкция

Операция именуется дизъюнкцией и обозначается эмблемой «p/q» (по другому её называют альтернацией, адъюнкцией, логическим сложением), либо «р + q». Дизъюнкция выражается с помощью операций конъюнкции и отрицания. математическая логика булева алгебра

Связь, созданная меж двумя высказываниями при помощи уступительного союза «или», является таковой операцией, которой в области логических значений соответствует операция дизъюнкции: высказывание является ложным тогда и лишь тогда, если оба высказывания ложны.

(альянс «или» в таком случае применяется в значении допущения, если допускается правильность обоих высказываний). к примеру: «выпал дождь либо полили парк». Поэтому такое соединение двух высказываний также именуется дизъюнкцией. (Знак «V» читается также как «или»).

Операция конъюнкция выражается с помощью операций дизъюнкции.

Таким образом, руководствуясь теоремой, что любая логическая операция может быть выражена с помощью лишь операций дизъюнкции и отрицания «ни-ни»

Импликация

Операция «р влечёт q» и именуется импликацией (с предварительным членом р и с последующим членом q).

Допустим, что если р = п, то значение выражения р влечёт q будет либо п, либо л в зависимости от того, является ли значение q п, либо л. Это аналогично тому, что высказывание типа «если А, то В», в котором первый член А является правильным, считается либо правильным, либо ложным в зависимости от того, верный либо ложный второй его член В. Поэтому соединению типа «если А, то В» соответствует импликация в области логических значений. Но в то же время при ложном высказывании А предложение типа «если А, то В» может вообще не считаться высказыванием к примеру: если горит лампочка, то лифт работает.

Если высказывание «горит лампочка» верно, то правильностью высказывания «лифт работает» однозначно решается правильность вышеприведенного предложения. Но если высказывание «горит лампочка» ложно, то ничего нельзя сказать о правильности вышеприведенного предложения. Можно сказать : нужно подождать, пока лампочка зажжётся. Приведем пример, в котором не будет даже способности «подождать»:

Если 2 * 2 = 5, то Дунай является европейской рекой. Если принять то, что соединение типа «если . . .то» соответствует операции импликации, при соблюдении последнего тождества высказывание «если А, то В» выражалось бы с помощью операций конъюнкции и отрицания в следующем виде : «неправильно, что : А и не В» (тут находится выражение «не В» вместо выражения «неправильно, что В»; таковым образом, ясно, что выражение «неправильно, что», расположенное в начале высказывания, относится не лишь к Л, но и к выражению «А и не В»). В согласовании с этим приведенные выше два предложения в примере могут быть переформулированы следующим образом:

а) Неправильно, что горит лампочка, и лифт не работает.

б) Неправильно, что 2 * 2 = 5 и Дунай не является европейской рекой. Если выражение «горит лампочка» ложно, то ложно и выражение «лампочка горит и лифт не работает», а отрицание его -- по а) -- является правильным. Выражение. «2 * 2 = 5» ложно, ложно также и выражение «Дунай не является европейской рекой»; их конъюнкция -- также ложна, а отрицание данной конъюнкции -- по б) -- является правильным. Тут нет противоречия по сравнению с обыденным пониманием вещей, так как традиционно не обращают внимание на правильность сложного предложения типа «если . . . то» в том случае, когда первый член соединения является ложным.

Выражения вида «если А, то В» можно считать синонимами выражений вида «неправильно, что: «А и не В»; они именуются импликациями (с предварительным членом А, с последующим членом В); для их обозначения применяется знак А влечёт В.

Представленное в области логических значений понятие импликации типа р влечёт q соответствует понятию вышеприведенной операции высказывания.

Операции на высказываниях, выражаемые с помощью союзов и частиц, сформулированы недостаточно точно ; в большинстве случаев, они до некой степени двусмысленны. По всей вероятности распознавание операций конъюнкции и отрицания наименее проблематично в их грамматической форме представления. Поэтому огромное значение имеет возможность выражения хоть, какой логической операции через операции конъюнкции и отрицания. Как было показано выше, это позволило нам истолковать образование сложного предложения вида «если . . . то» как операцию.

Упоминаются еще некие грамматические синонимы операции «А влечёт В»: «В, если лишь Л», «Только тогда А, если В», «Достаточным условием В является А», «Необходимым условием А является В», «В если не А».

И конъюнкция, и дизъюнкция выражаются с помощью операций импликации и отрицания.

Поэтому неважно, какая логическая операция может быть выражена с помощью операций отрицания и импликации.

Эквивалентность

Последний вид выражения операции эквивалентности.

Так как высказывание p эквивалентно q = n тогда и лишь тогда, когда p = q, то данная логическая операция соответствует образованию сложного предложения вида «А тогда и лишь тогда, когда В». Понимание и логическое значение предложения такового характера, образованного из двух всех высказываний, время от времени затруднительно для восприятия человека, как и понимание предложения вида «если . . . то». К примеру, «2 < 3 тогда и лишь тогда, если светит солнце».

Поэтому данное предложение понимается операцией калькуляции высказываний только в том случае, если считать его синонимом высказываний вида «неправильно, что А и не В, и, неправильно, что не А и В». В этом случае данная операция «А влечёт В» и именуется эквивалентностью.

Частенько встречаются следующие синонимы данной операции: «Для А нужно и довольно б», «А конкретно тогда, когда В».

Заключение

Булеву алгебру образуют все подмножества некого множества. То, что они образуют решетчатую структуру, разумеется. Нетрудно доказать и выполнение дистрибутивности. Нулевым элементом является пустое множество, а единичным -- все основное множество. Для каждого подмножества существует дополнительный элемент -- дополнение к множеству в теоретико-множественном смысле. Булевы алгебры находят применение основным образом в теории множеств, в математической логике, в теории вероятностей и в функциональном анализе.

Библиография

1. Малая математическая энциклопедия. Э. Фрид., И. Пастор., И. Рейман., П. Ревес., И. Ружа. Издательство академии наук Венгрии. Будапешт 1976 г.

2. Математический анализ. Часть III. В.А. Зоричь. Москва «наука». 1984 г.

3. Пособие по математика для поступающих в университеты. Под редакцией Г. Н. Яковлева Москва «наука» 1988 г.

Размещено на Allbest.ru