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

Реферат: Булева алгебра

План.

1.Введение в булеву алгебру

2.Булевы высказывания

3.Таблицы истинности

4.Сложные формулы

5.Заключение

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

 

Учебник рассчитан на уровень школьника  старших классов или студента ВУЗ-а.

 

Для чтения "off-line" можно скачать весь учебник целиком в виде архива. После разархивации для начала просмотра запустите файл "boo.bat" или откройте в браузере файл "boo/boo.htm".

 

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

 

К каждой главе даются вопросы и  задания для самостоятельной  работы. Если вы ранее не изучали  булеву алгебру, то рекомендуется выполнять  эти задания (и отвечать на вопросы). Задания относительно легкие и ставят целью проверить самого себя: понято ли содержание очередной главы или  же всего лишь создана иллюзия  понимания.

 

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

Обычная школьная алгебра работает с натуральными, целыми, рациональными  и действительными числами. Таких  чисел бесконечно много. А что, если взять всего лишь пару объектов и выдумать для них разные операции вроде того же сложения или умножения? Тогда мы получим новую разновидность алгебры, а при желании - много новых разновидностей, поскольку операции можно определять разными способами. Одна такая алгебра получила название "булевой" по имени ее изобретателя Дж. Буля. Операции в булевой алгебре продуманы таким образом, чтобы ее можно было использовать в логических рассуждениях.

 

 Мы привыкли к тому, что  числа применяются для обозначения  количества - большего или меньшего. Но если чисел всего два,  то может быть только два  варианта количества,.. тогда это странно было бы называть "количеством". Поэтому те два объекта, с которыми оперирует булева алгебра, числами называть некорректно. Просто два каких-то объекта. Какие именно - зависит от области применения булевой алгебры или, как говорят математики, от интерпретации.

 

 Булева алгебра может применяться  в компьютерной технике. Здесь  интерпретация заключается в  том, что значок 0 означает одно  напряжение между какими-нибудь  контактами какой-нибудь схемы  (скажем, 0 вольт), а значок 1 - другое (скажем, +5 вольт).

 

 Второй вариант применения  булевой алгебры - логические  рассуждения. Здесь два объекта  интерпретируются как истина (будем  обозначать как true) и ложь (будем обозначать как false). Далее мы будем называть символы true и false булевыми величинами, а переменные, которые их обозначают - булевыми переменными.

 

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

 

 Что называть истиной, а  что - ложью,- это вопрос, как говорится, "тонкий". Есть разные критерии  истины, о которых можно долго  говорить. Математическая логика  подобных разговоров избегает, как  говорят "абстрагируется" от  них. Предполагается, что кто-то  каким-то образом выяснил, что  некое утверждение истинно (true), а другое - ложно (false). Неважно, как он это делает, пусть хоть Афродите молится - лишь бы выяснил. Дальше уже можно применять булеву алгебру для различных операций с этими true и false. Результат будет получен, опять же, в виде true и false. Теперь тот, кто применял булеву алгебру к откровениям Афродиты, должен сам истолковать, что же будет означать для него такая "истина" и такая "ложь".

 

 Вот вам более привычный  пример - из арифметики. В ней есть  абстрактные числа, для которых  заданы правила сложения, вычитания  и так далее. Мы можем сложить  13 + 12 и получить 25. А вот что  означают эти самые 13, 12 и 25 - это уже дело того, кто применяет  арифметику. Может, это 13 килограммов  картошки и 12 килограммов картошки, которые свалили в одну кучу  и получили 25 килограммов. А может  это обогреватель с температурой  в 13 градусов тепла, который  нагрели еще на 12 градусов и  получили в результате обогреватель  с температурой 25 градусов. Это были  примеры правильного применения  арифметики. А что, если сложить  12 килограммов картошки и 13 градусов  тепла - что получится? 25? 25 чего? Килограммов  или градусов? Наверное ни то, ни другое - ведь такое применение арифметики неправильно. Или мы можем взять 12 кучек песка и еще 13 кучек песка и высыпать их все в одно место. В результате получится вовсе не 25 кучек песка, а одна большая куча. Снова неправильное применение арифметики.

 

 Так же и с булевой алгеброй. Можно для выяснения "истины" и "лжи" долго бить в  бубен или лбом об пол. Будет достигнут некий результат... который можно подставить в формулы булевой алгебры. Потом что-то получится в процессе вычислений... и это может оказаться "истиной" или "ложью" с точки зрения специалиста по битию в бубен. Если булева алгебра будет постоянно выдавать правильные ответы (как с картошкой), тогда для этой цели она будет признана пригодной. Вопрос о том, для чего пригодна булева алгебра, а для чего - не пригодна остается за рамками самой булевой алгебры.

 

 Итак, будем рассматривать интерпретацию  булевой алгебры "истина"/"ложь". Пусть нам был дан некий  фрагмент текста x и мы каким-то способом (который остается за рамками булевой алгебры) выясняем: истинный ли этот фрагмент текста или насколько истинный. Результат выяснения мы будем обозначать так: Tr(x). В некоторых случаях выяснить нам не удастся ничего, например, если этот фрагмент текста бессмысленный или непонятный. Если истинность установить можно, то такие тексты мы будем называть "высказываниями".

 

[высказывание]: Высказывание - это фрагмент текста, для которого можно выяснить его истинность (хотя бы приблизительно).

 

 В булевой алгебре рассматриваются  только те высказывания, для которых  истинность может принимать два  значения: либо истина (true), либо ложь (false). Другие значения - нельзя. Оба значения сразу - нельзя. Ни одного значения вообще - тоже нельзя. Подобные высказывания называются булевыми высказываниями. Любые другие тексты в булевой алгебре не рассматриваются. Не то, чтобы это было запрещено уголовным кодексом, просто таковы "область применимости" этого раздела математики.

 

 

[булево высказывание]: Булево высказывание - это такое высказывание, для которого рассматриваются только два значения истинности: true и false.

 

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

Таблица истинности - это один из способов вычислений в формальной логике. Таблица  позволяет определить истинность какого-нибудь сложного логического высказывания по истинности его фрагментов. К  сожалению, не для всякого высказывания можно составить таблицу истинности (особено вне булевой алгебры), но, когда это возможно, это удобно.

Таблица истинности имеет примерно вот такой вид:

A	B	~(A & B)
false	false	true
false	true	true
true	false	true
true	true	false

 

В верхней строке указана истинность фрагментов высказывания в виде переменных A и B а также формула ~(A & B).

 

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

 

 Если переменная 1, то сочетаний  2:

true

false

 

 Если переменных 2, то сочетаний  4 (как в рассмотренном случае):

false, false

false, true

true, false

true, true

 

 Если переменных 3, то сочетаний  8:

false, false, false

false, false, true

false, true, false

false, true, true

true, false, false

true, false, true

true, true, false

true, true, true

 

 Добавление одной новой переменной увеличивает число сочетаний ровно в два раза. Общее число сочетаний равно 2N, где N - число переменных. Выписывать все возможные комбинации удобно по столбцам, начиная справа. В столбце, который соответствует последней переменной, true и false меняются каждую строку, в следующем столбце - в два раза реже (два раза false, два раза true), в следующем столбце - еще в два раза реже (четыре раза false, четыре раза true) и так далее. Можно начинать чередование не с false, а с true, такой вариант ничем не хуже. В принципе, строки в таблице истинности можно перечислять в любом порядке, но описанные выше способы - наиболее удобные.

 

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

 

 Для того, чтобы определить истинность сложного высказывания по истинности фрагментов, надо вычислить истинность каждого фрагмента, затем найти в таблице строку, в которой истинность фрагментов в точности совпадает и следует в нужном порядке, а затем в самом правом столбце прочитать результат.

 

 Пусть, например, мы каким-то  образом выяснили, что A = true и B = false. Ищем в таблице строку, которая начинается с сочетания true,false. Это - четвертая строка (выделена желтым цветом). В самом правом столбце видим результат - true. Это - истинность, вычисленная по формуле ~(A & B).

 

 Теперь рассмотрим какую-нибудь  интерпретацию для этих вычислений.

 

 Пусть есть два фрагмента  текста: "Саша - женщина" и "Саша - чукча". Имя "Саша" может  прнадлежать как женщине, так и девушке, девочке или мужчине. Только в первом случае утверждение будет истинным, иначе - ложным. Получается, первый фрагмент текста может быть либо истинным, либо ложным, как и положено булевому высказыванию.

 

 Рассмотрим второй фрагмент. Имя "Саша" в ходу у разных  национальностей. Тут нам надо  избежать споров на тему: а  насколько чистокровная чукча  та Саша, чтобы называть ее  чукчей. Мы будем считать чукчами  всех, у кого есть отец, который  в данный момент жив и считает  себя чукчей, и мать, которая тоже  в данный момент жива и считает  себя чукчей. Такой критерий оставляет  нам только два варианта: либо  истина, либо ложь, так что второй  фрагмент, понимаемый таким образом,- тоже высказывание. Пусть далее  мы каким-то способом выяснили, что Саша, о которой шла речь,- действительно женщина, но не  чукча, а украинка.

 

 Первый фрагмент: "Саша - женщина". Обозначим его истинность переменной  A. Мы выяснили, что

 

A = Tr("Саша - женщина") = true,

 

 Второй фрагмент: "Саша - чукча". Его истинность обозначим переменной  B. Мы выяснили, что:

 

B = Tr("Саша - чукча") = false.

 

 

Дальше, как объяснялось выше, ищем в таблице нужную строку и выясняем, что по формуле ~(A & B) получается true. Теперь остается понять: это самое true к чему относится? В одном из вариантов интерпретации можно сказать, что это true будет истинностью фразы "Неправда, что Саша - женщина и чукча".

Из простых формул можно конструировать более сложные. Будем обозначать произвольные формулы как функции  от некоторого числа аргументов, например f(A) или g(x1, x2,... xn). В скобках перечисляются  переменные, входящие в формулу или  целые фрагменты формулы, представляющие собой единое целое, Если список переменных неважен, то будем писать многоточие, например f(...). Эти скобки важны для  того, чтобы отличить два случая:

1. Отдельная свободная переменная f, имеющая определенную область значений (например, true и false, если переменная булева).
2. Целая формула f(...), в которую может входить много переменных (или одна, или ни одной), каждая из которых, в принципе, может иметь свою область значений.

Для многих разделов математики приняты  правила построения формул по определенным правилам. Для булевой алгебры  эти правила таковы:

1. true - булева формула (простейшая).

2.false - булева формула (простейшая).

3. Одна отдельная булева переменная - формула (простейшая).

Примечание: булевой переменной называется переменная, у которой область  значений состоит всего из двух объектов: true и false.

4. Если есть булева формула f(...), то из нее можно построить формулы:

(f(...))

~(f(...)).

5.Если есть две булевы формулы (возможно одинаковые) f(...) и g(...), то из них можно построить формулы:

(f(...)  g(...))

(f(...)  g(...))

(f(...) & g(...))

(f(...)  g(...))

(f(...)  g(...))

(f(...)  g(...))

(f(...) | g(...))

(f(...)  g(...))

(f(...)  g(...))

(f(...)  g(...))

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

 

 Внешние скобки в правилах  призваны соблюсти тот порядок  операций, который соответствует  порядку построения формулы из  атомов. Для краткости лишние  скобки можно убирать. Процесс  убирания и восстановления скобок  выглядит точно так же, как  в школьной алгебре: в зависимости  от порядка операций. Когда скобки  отсутствуют, то в первую очередь  выполняется операция "~" (первый, высший приоритет), затем "&" (второй приоритет), затем "" и "" (третий приоритет), затем  все остальные (четвертый, низший  приоритет). Операции одного приоритета  выполняются слева направо.