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

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

Введение

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

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

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

1. Булева алгебра. Логические операции

Алгебра логики, она же булева алгебра - это раздел математики, возникший в XIX веке благодаря усилиям английского математика Дж. Буля. Поначалу булева алгебра не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор). Хотя это не единственная сфера применения данной науки. Итак: Булева алгебра?--?раздел математики, изучающий логические выражения и операции. Логические выражения представляют собой высказывания?--?некоторые утверждения, которым всегда можно сопоставить одно из двух логических значений: ложь или истина (их можно обозначать как 0 и 1, f и t, false и true).

Что же собой представляет алгебра логики? Во-первых, она изучает методы установления истинности или ложности сложных логических высказываний с помощью алгебраических методов. Во-вторых, булева алгебра делает это таким образом, что сложное логическое высказывание описывается функцией, результатом вычисления которой может быть либо истина, либо ложь (1, либо 0). При этом аргументы функции (простые высказывания) также могут иметь только два значения: 0, либо 1.

Что такое простое логическое высказывание? Это фразы типа «два больше одного», «5.8 является целым числом». В первом случае мы имеем истину, а во втором ложь. Алгебра логики не касается сути этих высказываний. Если кто-то решит, что высказывание «Земля квадратная» истинно, то алгебра логики это примет как факт. Дело в том, что булева алгебра занимается вычислениями результата сложных логических высказываний на основе заранее известных значений простых высказываний.

2. Основные логические операции

Логические операции булевой алгебры подобны арифметическим операциям элементарной алгебры. Если последние применяются к числам, то первые?--?к логическим значениям соответствующих высказываний. Составные высказывания можно получать с помощью логических операций так же, как в элементарной алгебре?--?формулы. И, если известны значения исходных высказываний, значение составного высказывания можно вычислить, прибегая лишь к формальным правилам. Уравнения, составленные в алгебре логики можно формально решать. Все это обеспечивает широкие возможности по применению математического аппарата к суждениям из реальной жизни (там, где не хватает аппарата булевой алгебры, применяются более сложные методы математической логики, в частности, исчисление предикатов первого порядка и др.).

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

Отрицание НЕ

Отрицание?--?операция, применяемая к одному операнду, т.е. унарная операция. Выражение не А записывается как А, А_ _ _ или !А. Операции отрицания задается таблицей истинности показанной правее:

Соответственно, операции отрицания можно дать следующее истолкование: истинность выражения, построенного с помощью отрицания, противоположна истинности исходного выражения. Если А истинно, ¬А ложно, и наоборот.

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

Логическое И

Логическое И (конъюнкция)?--?операция, применяемая к двум операндам, т.е. бинарная операция. Выражение А и В записывается как А В, А.В или А&В. Конъюнкция задается таблицей истинности :

Логическое И, как не сложно понять из названия, образует выражение, которое истинно только тогда, когда истинны оба исходных выражения, входящих в его состав: И первое, И второе.

Операция конъюнкции подобна умножению. Это легко заметить по таблицы истинности. Конъюнкция дает такой же результат, как если бы мы просто перемножали ее операнды.

Логическое ИЛИ Логическое ИЛИ (дизъюнкция)?--?еще одна бинарная операция. Выражение А или В записывается как А?В, А+В или А||В. Дизъюнкция задается таблицей истинности:

Логическое ИЛИ образует выражение, которое истинно тогда, когда истинно хотя бы одно исходных выражение, входящее в его состав: ИЛИ первое, ИЛИ второе.

Операция дизъюнкции подобна сложению. Как и в случае с конъюнкцией, это можно заметить по таблице истинности. Единственным исключением тут является правило 1+1=1, а не 2, как можно было бы ожидать. Но это нормальное явление, учитывая, что пространство логических значений ограничено нулем и единицей.

3. Производные логические операции

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

Исключающее ИЛИ

Операция исключающего ИЛИ похожа на обычную дизъюнкцию. Ее обозначают как АВ или А€В. Операция задается следующей таблицей истинности: Как видно из таблицы, отличие исключающего ИЛИ от дизъюнкции заключается в том, что полученное выражение будет ложным, если истинны оба исходных выражения, а не только одно из них.

Высказывание вида АВ в логическом выражении можно заменить на А?¬В?В?¬А.

Операция импликации

Бинарная операция импликации выражается связками если… , то, из … следует, влечет. Операция записывается как А>В или A=>B и задается следующей таблицей истинности:

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

Высказывание вида А>В в логическом выражении можно заменить на ¬А?В, при этом оно останется тождественно исходному, то есть будет истинно или ложно ровно в тех же самых случаях, что и оригинальное.

Операция эквивалентности

Данная операция выражается связками тогда и только тогда, необходимо и достаточно, равносильно. Операция имеет следующие обозначения: А?В, А<=>В, А==В. Таблица истинности выглядит так:

Выражение, образованное эквивалентностью, истинно, если истинность обоих операндов совпадает.

Эквивалентность можно заменить на две импликации, а те, в свою очередь, раскрыть по правилам, указанным выше. Получится, что высказывание вида А?В можно заменить на А?В?¬А?¬В.

4. Приоритеты операций

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

5. Основные законы Булевой алгебры

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

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

Ассоциативность. Ассоциативность конъюнкции и дизъюнкции выражается следующими формулами:

(А?В) ?С=А? (В?С)=А?В?С (А?В) ?С=А? (В?С)=А?В?С

На практике это означает, что можно опускать те скобки, которые определяют, в каком порядке должна выполняться конъюнкция в выражениях вида А₁ ? А₂ ?…? А_n и дизъюнкция в выражениях А₁?А₂?…?А_n

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

Конъюнкция и дизъюнкция являются коммутативными операциями:

А?В=В?А А?В=В?А

Дистрибутивность

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

А?(В?С)=А?В?А?С A?B?C=(А?В)?(А?С).

Свойства единицы и нуля

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

А?0=0 А?1=1 А?0=А А?1=1

Идемпотентность

Операция называется идемнотентной, если, применяя ее к двум равным операндам, получается тот же самый операнд. Идемпотентность позволяет «выкидывать» лишние повторные применения операции из формулы. Конъюнкция и дизъюнкция идемпотентны:

А?А=А

А?А=А

Поглощение

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

А?В?В=В (А?В) ?В=В

Законы де Моргана

Законы де Моргана позволяют применять отрицания к целой скобке, позволяя перейти к так называемым тесным отрицаниям, когда ни одно отрицание не стоит перед скобкой.

(А?В)=¬А?¬В ¬(А?В)=¬А?¬В Дополнение

Отрицание операнда называется его дополнением. Конъюнкция или дизъюнкция операнда со своим дополнением дает однозначные результат независимо от значения операнда:

А?¬А=0 А?¬А=1

Двойное отрицание

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

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

I. Логические элементы компьютера

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

6. Основные определения

Логический элемент -- часть электронной логической схемы, которая выполняет логические операции конъюнкции, дизъюнкт и инверсии. Каждый логический элемент имеет свое условное обозначение, один или несколько входов и только один выход. На вход подается сигнал (1) или не подается (0). На выходе получается результат выполнения логической операции: 1 -- есть сигнал, 0 -- нет сиг- нала. Рассмотрим логические элементы, реализующие основные логические операции.

Инвертор -- логическая схема, реализующая операцию отрицания (инверсию).

Дизъюнктор -- логическая схема, реализующая операцию дизъюнкции (логического сложения).

Конъюнктор -- логическая схема, реализующая логическую операцию конъюнкции (логического умножения).

Сумматор -- это электронный логический элемент, выполняющий суммирование двоичных чисел. Он является центральным узлом арифметико-логического устройства процессора. У него на входе ряд двоичных чисел А и В, на выходе -- результат сложения: значение (разряд) суммы S и перенос Р.

Триггер -- электронный логический элемент, являющаяся памятью компьютера для хранения одного бита информации. Он может находиться в одном из двух устойчивых состояний и спо- собен почти мгновенно переходить из одного электрического состояния в другое и наоборот. Самый распространенный триггер -- SR-триггер (S и R -- соответственно от английских слов set -- «установка», reset -- «сброс»).

Он имеет два входа S и R и два выхода Q и Q. Причем один вы- ходной сигнал является логическим отрицанием другого. Несколько триггеров объединяются в группы -- регистры, предназначенные для кратковременного хранения двоичной информации и обработки информации. Число триггеров в регистре называется разрядностью компьютера, которая может быть равна 8, 16, 32 и 64.

Заключение

Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами. Функция от n переменных называется логической или булевой или переключательной или функцией алгебры логики, если сама функция и любой из ее аргументов могут принимать значения только из множества {0, 1}. Количество функций от n переменных равно 2 в степени n. Значениям переменной в булевой алгебре соответствуют состояниям элементов микросхем компьютера или любого другого электронного устройства: сигнал присутствует (логическая "1") или сигнал отсутствует (логический "0").

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

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

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