Булева алгебра законы алгебры логики

Алгебра логики (Булева алгебра)

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

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

Алгебру логики называют булевой алгеброй в честь выдающегося английского математика XIX в. Джорджа Буля, который разработал ее основы.

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

В логической алгебре существуют всего три базовых логических операции:

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

Джордж Буль
(George Boole)
1815 — 1864

Основатель математической логики. Профессор математики Королевского колледжа Корка с 1849 года.
В 1847 г. написал статью по началам математической логики – «Математический анализ логики, или Опыт исчисления Дедуктивных умозаключений».
В 1854 году появился главный его труд «Исследование законов мышления, на которых основаны математические теории логики и вероятностей».

Сайт находится в разработке, поэтому, пожалуйста, проявите снисходительность к тому, что материалов, пока мало.

Алгебра логики и логические основы компьютера

Что такое алгебра логики?

Алгебра логики (булева алгебра) – это раздел математики, возникший в XIX веке благодаря усилиям английского математика Дж. Буля. Поначалу булева алгебра не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор). Хотя это не единственная сфера применения данной науки.

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

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

Логические операции. Дизъюнкция, конъюнкция и отрицание

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

Алгебра логики предусматривает множество логических операций. Однако три из них заслуживают особого внимания, т.к. с их помощью можно описать все остальные, и, следовательно, использовать меньше разнообразных устройств при конструировании схем. Такими операциями являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ). Часто конъюнкцию обозначают &, дизъюнкцию — ||, а отрицание — чертой над переменной, обозначающей высказывание.

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

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

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

Логические основы компьютера

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

Переключательные схемы

Вентили, триггеры и сумматоры

Сумматоры широко используются в арифметико-логических устройствах (АЛУ) процессора и выполняют суммирование двоичных разрядов.

Булева алгебра. Часть 2. Основные законы и функции

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

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

Форма записи выражений в булевой алгебре.

Если высказывание истинно, то его записывают так: А = 1, если же оно ложно, то А = 0 (ведь неверно, что картошка — это фрукт). Для любого высказывания А либо истинно (А = 1), либо ложно (А = 0). Середины здесь быть не может. Об этом мы уже говорили.

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

Отсюда сложное высказывание «Три больше двух И меньше пяти» есть логическое (в данном случае заглавная буква И, говорит о том, что это «И» логическая операция, также как далее в тексте «ИЛИ» и «НЕ».) произведение высказываний А и В. Обозначается оно так: A^B или А*В.

Логическое умножение (операция «И»).

В элементарной алгебре А*А =А2. Но в алгебре Буля А*А = А2 = А, А * А = А так как знак умножения (*) теперь обозначает. И. в смысле И. И. Весь наш опыт подтверждает, что и А И А — это то же самое, что одно А. С этим нельзя не согласиться. Истинность высказывания не меняется, если его повторить сомножителем несколько раз.

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

1*1 = 1, 1*0 = 0 = 0*1 = 0, 0*0 = 0.

Первое равенство читается так: если и А и В истинны, то произведение А*В истинно. В алгебре Буля знак умножения (*) заменяет союз И.

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

Логическое сложение (операция «ИЛИ»)

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

Рассмотрим пример логической суммы. Высказывание А: «Сегодня я пойду в кино».

Высказывание В: «Сегодня я пойду на дискотеку». Складываем оба высказывания и получаем: «Сегодня я пойду в кино ИЛИ на дискотеку».

Это сложное высказывание обозначается так: А + В = С или (А V В) = С.

Через С мы обозначили сложное высказывание логической суммы.

В рассматриваемом примере союз ИЛИ нельзя употреблять в исключающем смысле. Ведь в один и тот же день можно попасть И в кино И на дискотеку. А вот высказывание:

«Председателем садового товарищества будет Петров или Иванов»—не является логической суммой, потому, что председателем будет только кто-то один, а другой простым рядовым садоводом — любителем.

Знак V для обозначения логической суммы выбран потому, что это начальная буква латинского слова «vel», обозначающего «или», в отличие от латинского слова «aut>, обозначающего «и». Теперь всем должно быть ясно, почему логическое произведение обозначается знаком ^.

В элементарной алгебре есть правило A + А = 2А. Это правило верно, какое бы число ни изображалось буквой А. В булевой алгебре ему соответствует правило А + А = А. Весь наш жизненный опыт говорит, что сказать А ИЛИ А ИЛИ оба А есть лишь другой и более длинный способ сказать просто А.

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

А + В = 1, если ИЛИ А = 1 ИЛИ В = 1, что согласуется с обычной арифметикой:

Если оба складываемых высказывания истинны, то сумма считается также истинной, поэтому в алгебре Буля имеем: (1) + (1) = 1.

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

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

Итак, сумма двух высказываний А + В считается истинной, если истинно ИЛИ А, ИЛИ В, ИЛИ оба слагаемых вместе. Таким образом, слово ИЛИ обозначается знаком +.

Помня, что высказывания А и В могут быть только истинными или ложными и, следовательно, иметь меру истинности 1 или 0, результаты рассмотренных операций И и ИЛИ можно свести в таблицы 1 и 2.

Третья операция, широко используемая алгеброй Буля, — операция отрицания — НЕ. Напоминаем, элементарная алгебра пользуется операциями СЛОЖИТЬ, ВЫЧЕСТЬ, УМНОЖИТЬ НА, РАЗДЕЛИТЬ НА и некоторыми другими.

Для каждого высказывания А существует его отрицание НЕ А, которое мы будем обозначать символом /А. Это ни у кого не должно вызывать сомнения.

Приведем примеры: «Мы поедем в лес» А, «Мы не поедем в лес» /А.

Если высказывание А истинно, то есть А = 1, то его отрицание /А обязательно должно быть ложно /А = 0. И наоборот, если какое-либо высказывание ложно, то его отрицание истинно. Например: «Лошадь не ест сена» /А = 0, «Лошадь ест сено» (А = 1). Это можно выразить таблицей 3.

Определяя смысл действия отрицания, и полагая, что из двух высказываний А и /А всегда одно истинно, следуют две новые формулы алгебры Буля:

А + (/А) = 1 и А* (/А) = 0.

Имеются еще и другие формулы, упрощающие логическую обработку высказываний. Например, 1+А = 1, так как, согласно определению сложения, в случае, когда одно слагаемое равно единице, сумма всегда равна единице. Полученный результат не зависит от того, будет ли А = 0 или А = 1.

Каждая из трех рассмотренных нами логических операций (И, ИЛИ, НЕ) обладает определенными свойствами, близкими к правилам элементарной алгебры. Если все их сформулировать, то получим 25 правил булевой алгебры. Их вполне достаточно для решения почти любой логической задачи. Без этих правил решать логические задачи из-за их кажущейся запутанности становится довольно трудно. Пытаться найти правильный ответ, не пользуясь правилами, — значит заменять их смекалкой и общими рассуждениями. Правила значительно облегчают эту работу и экономят время.

В рамках статьи невозможно рассмотреть все эти 25 правил, но желающие всегда могут найти их в соответствующей литературе.

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

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

Что помогло Шеннону вторично «открыть» булеву алгебру? Случай? Ничего подобного.

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

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

Новая алгебра справедлива только для рассмотрения релейных и переключательных цепей. Ведь только в таких схемах удовлетворяется условие «сигнал есть» и «сигнала нет». Там, где сигнал меняется непрерывно, приобретая сколь угодно большое число промежуточных условий (такой сигнал называется аналоговым), релейная алгебра неприменима. Об этом нужно всегда помнить. Но как раз большинство электронных вычислительных машин и кибернетических автоматов используют дискретный принцип обработки сигналов, в основу которого положены элементы «да — нет».

Выражение «Контакт замкнут» Шеннон принял за истинное (1), а «Контакт разомкнут» — за ложное (0). Всю остальную «алгебру», включая операции И, ИЛИ и НЕ и 25 правил Шеннон заимствовал у Буля.

Алгебра релейных схем получилась проще алгебры Буля, так как она имеет дело только с элементами типа «да — нет». Кроме того, новая алгебра более наглядна.

Элементами в этой алгебре являются контакты, которые мы будем обозначать буквами А, В, С. Контакт замкнут— А, контакт разомкнут — /А (буква с черточкой).

Система обозначений, как видите, полностью взята из алгебры Буля. Разомкнутый контакт является отрицанием замкнутого контакта. Один и тот же контакт не может быть одновременно замкнутым и разомкнутым.

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

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

Если в некоторой цепи какой-либо контакт есть отрицание другого контакта, то их значения всегда противоположны. Например, контакты С и /С никогда не могут быть одновременно разомкнуты или одновременно замкнуты. А на схеме их можно представлять механически соединенными: если один из них размыкается, то другой замыкается.

Знакомство с релейной алгеброй начнем с разбора простейших схем, соответствующих операциям И, ИЛИ и НЕ.

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

Суммой двух контактов (операция ИЛИ) будем называть схему, образованную при их параллельном соединении: она замкнута (равна 1) тогда, когда замкнут (равен 1) хотя бы один из образующих схему контактов.

Противоположный данному контакту (операция НЕ) — это контакт, равный 0 (разомкнутый), если данный контакт равен 1 (замкнут), и наоборот.

Как и в алгебре Буля, если контакты обозначены буквами А и В, то произведение двух контактов мы будем обозначать через А*В, сумму — через А + В, а контакт, противоположный А, — через /А. Сказанное поясним рисунками 1, 2 и 3.

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

Остановимся на двух примерах: 1*0 = 0 и 1+0=1.

Из рисунка видно, что постоянно замкнутый контакт, последовательно соединенный с постоянно разомкнутым контактом, эквивалентен постоянно разомкнутому контакту (1*0 = 0) Постоянно замкнутый контакт, параллельно соединенный с постоянно разомкнутым контактом, эквивалентен постоянно замкнутому контакту.

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

Если структурная формула какой-либо релейной схемы равна 1, то через нее сможет пройти сигнал — цепь замкнута. И наоборот, если структурная формула схемы равна 0, сигнал через нее не пройдет — цепь разорвана. Вывод: две релейные схемы эквивалентны друг другу тогда, когда равны их структурные формулы.

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

Малый математический факультет

Кубанского государственного университета

Основы алгебры логики

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

Алгебра – это раздел математики, предназначенный для описания действий над переменными величинами, которые принято обозначать строчными буквами латинского алфавита – а, b, x, y и т.д. Действия над переменными величинами записываются в виде математических выражений.

Термин «логика» происходит от древнегреческого “logos”, означающего «слово, мысль, понятие, рассуждение, закон».

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

Алгебру логику называют также алгеброй Буля, или булевой алгеброй, по имени английского математика Джорджа Буля, разработавшего в XIX веке ее основные положения. В булевой алгебре высказывания принято обозначать прописными латинскими буквами: A, B, X, Y. В алгебре Буля введены три основные логические операции с высказываниями? Сложение, умножение, отрицание. Определены аксиомы (законы) алгебры логики для выполнения этих операций. Действия, которые производятся над высказываниями, записываются в виде логических выражений.

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

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

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

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

• НЕ (логическое отрицание, инверсия);

• ИЛИ (логическое сложение, дизъюнкция);

• И (логическое умножение, конъюнкция).

Логическое отрицание является одноместной операцией, так как в ней участвует одно высказывание. Логическое сложение и умножение — двуместные операции, в них участвует два выска¬зывания. Существуют и другие операции, например операции следования и эквивалентности, правило работы которых можно вывести на основании основных операций.

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

  • таблица истинности одноместной логической операции состоит из двух строк: два различных значения аргумента — «истина» (1) и «ложь» (0) и два соответствующих им значения функции;
  • в таблице истинности двуместной логической операции — четыре строки: 4 различных сочетания значений аргументов — 00, 01, 10 и 11 и 4 соответствующих им значения функции;
  • если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.
  • Операция НЕ — логическое отрицание (инверсия)

    Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее:

    • если исходное выражение истинно, то результат его отрицания будет ложным;

    • если исходное выражение ложно, то результат его отрицания будет истинным.

    Для операции отрицания НЕ приняты следующие условные обозначения:

    Результат операции отрицания НЕ определяется следующей таблицей истинности:

    Конспект и презентации по теме Булева алгебра

    Успейте воспользоваться скидками до 60% на курсы «Инфоурок»

    Выбранный для просмотра документ Логические основы ЭВМ.doc

    Логические основы ЭВМ

    Алгебра логики и логические основы компьютера

    Что такое алгебра логики?

    Алгебра логики (булева алгебра) – это раздел математики, возникший в XIX веке благодаря усилиям английского математика Дж. Буля. Поначалу булева алгебра не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор). Хотя это не единственная сфера применения данной науки.

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

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

    Логические операции. Дизъюнкция, конъюнкция и отрицание(инверсия)

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

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

    Алгебра логики предусматривает множество логических операций. Однако три из них заслуживают особого внимания, т.к. с их помощью можно описать все остальные, и, следовательно, использовать меньше разнообразных устройств при конструировании схем. Такими операциями являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ). Часто конъюнкцию обозначают &, дизъюнкцию — ||, а отрицание — чертой над переменной, обозначающей высказывание.

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

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

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

    Логические основы компьютера

    В ЭВМ используются различные устройства, работу которых прекрасно описывает алгебра логики. К таким устройствам относятся группы переключателей, триггеры, сумматоры.

    В ЭВМ применяются электрические схемы, состоящие из множества переключателей. Переключатель может находиться только в двух состояниях: замкнутом и разомкнутом. В первом случае – ток проходит, во втором – нет. Описывать работу таких схем очень удобно с помощью алгебры логики. В зависимости от положения переключателей можно получить или не получить сигналы на выходах.

    Вентили, триггеры и сумматоры

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

    Триггеры и сумматоры – это относительно сложные устройства, состоящие из более простых элементов – вентилей.

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

    Законы алгебры логики

    Для логических величин обычно используются три операции:

    Конъюнкция – логическое умножение (И) – and, &, .

    Дизъюнкция – логическое сложение (ИЛИ) – or, |, v.

    Логическое отрицание (НЕ) – not, ¬.

    Логические выражения можно преобразовывать в соответствии с законами алгебры логики:

    Законы рефлексивности
    a ∨ a = a
    a ∧ a = a

    Законы коммутативности
    a ∨ b = b ∨ a
    a ∧ b = b ∧ a

    Законы ассоциативности
    (a ∧ b) ∧ c = a ∧ (b ∧ c)
    (a ∨ b) ∨ c = a ∨ (b ∨ c)

    Законы дистрибутивности
    a ∧ (b ∨ c) = a ∧ b ∨ a ∧ c
    a ∨ b ∧ c = (a ∨ b) ∧ (a ∨ c)

    Закон двойного отрицания
    ¬ (¬ a) = a

    Законы де Моргана
    ¬ (a ∧ b) = ¬ a ∨ ¬ b
    ¬ (a ∨ b) = ¬ a ∧ ¬ b

    Законы поглощения
    a ∨ a ∧ b = a
    a ∧ (a ∨ b) = a

    Логические элементы. Вентили

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

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

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

    Выходной сигнал вентиля можно выражать как функцию от входных.

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

    Сумматор и полусумматор

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

    Как происходит сложение? Допустим, требуется сложить двоичные числа 1001 и 0011. Сначала складываем младшие разряды (последние цифры): 1+1=10. Т.е. в младшем разряде будет 0, а единица – это перенос в старший разряд. Далее: 0 + 1 + 1(от переноса) = 10, т.е. в данном разряде снова запишется 0, а единица уйдет в старший разряд. На третьем шаге: 0 + 0 + 1(от переноса) = 1. В итоге сумма равна 1100.

    Теперь не будем обращать внимание на перенос из предыдущего разряда и рассмотрим только, как формируется сумма текущего разряда. Если были даны две единицы или два нуля, то сумма текущего разряда равна 0. Если одно из двух слагаемых равно единице, то сумма равна единицы. Получить такие результаты можно при использовании вентиля ИСКЛЮЧАЮЩЕГО ИЛИ.

    Перенос единицы в следующий разряд происходит, если два слагаемых равны единице. И это реализуемо вентилем И.

    Тогда сложение в пределах одного разряда (без учета возможной пришедшей единицы из младшего разряда) можно реализовать изображенной ниже схемой, которая называется полусумматором. У полусумматора два входа (для слагаемых) и два выхода (для суммы и переноса). На схеме изображен полусумматор, состоящий из вентилей ИСКЛЮЧАЮЩЕЕ ИЛИ и И.

    В отличие от полусумматора сумматор учитывает перенос из предыдущего разряда, поэтому имеет не два, а три входа.

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

    Рассмотрим один из случаев. Требуется сложить 0 и 1, а также 1 из переноса. Сначала определяем сумму текущего разряда. Судя по левой схеме ИСКЛЮЧАЮЩЕЕ ИЛИ, куда входят a и b, на выходе получаем единицу. В следующее ИСКЛЮЧАЮЩЕЕ ИЛИ уже входят две единицы. Следовательно, сумма будет равна 0.

    Теперь смотрим, что происходит с переносом. В один вентиль И входят 0 и 1 (a и b). Получаем 0. Во второй вентиль (правее) заходят две единицы, что дает 1. Проход через вентиль ИЛИ нуля от первого И и единицы от второго И дает нам 1.

    Проверим работу схемы простым сложением 0 + 1 + 1 = 10. Т.е. 0 остается в текущем разряде, и единица переходит в старший. Следовательно, логическая схема работает верно.

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

    Триггер как элемент памяти. Схема RS-триггера

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

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

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

    Разнообразие триггеров весьма велико. Наиболее простой из них так называемый RS-триггер, который собирается из двух вентилей. Обычно используют вентили ИЛИ-НЕ или И-НЕ.

    RS-триггер на вентилях ИЛИ-НЕ

    RS-триггер «запоминает», на какой его вход подавался сигнал, соответствующий единице, в последний раз. Если сигнал был подан на S-вход, то триггер на выходе постоянно «сообщает», что хранит единицу. Если сигнал, соответствующий единице, подан на R-вход, то триггер на выходе имеет 0. Не смотря на то, что триггер имеет два выхода, имеется в виду выход Q. (Q с чертой всегда имеет противоположное Q значение.)

    Другими словами, вход S (set) отвечает за установку триггера в 1, а вход R (reset) – за установку триггера в 0. Установка производится сигналом, с высоким напряжением (соответствует единице). Просто все зависит от того, на какой вход он подается.

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

    Возможны следующие ситуации:

    Q = 1, сигнал подан на S, следовательно, Q не меняется.

    Q = 0, сигнал подан на S, следовательно, Q = 1.

    Q = 1, сигнал подан на R, следовательно, Q = 0.

    Q = 0, сигнал подан на R, следовательно, Q не меняется.

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

    Как триггер сохраняет состояние? Допустим, триггер выдает на выходе Q логический 0. Тогда судя по схеме, этот 0 возвращается также и в верхний вентиль, где инвертируется (получается 1) и уже в этом виде передается нижнему вентилю. Тот в свою очередь снова инвертирует сигнал (получается 0), который и имеется на выходе Q. Состояние триггера сохраняется, он хранит 0.

    Теперь, допустим, был подан единичный сигнал на вход S. Теперь в верхний вентиль входят два сигнала: 1 от S и 0 от Q. Поскольку вентиль вида ИЛИ-НЕ, то на выходе из него получается 0. Ноль идет на нижний вентиль, там инвертируется (получается 1). Сигнал на выходе Q становится соответствующим 1.

    Практическое значение алгебры логики

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

    0 + 0 = 0; 0 + 1 = 1; 1 + 0 = 1; 1 + 1 = 0.

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

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

    Сумматоры и полусумматоры являются однотактными логическими схемами. Значения их выходов однозначно определяется значениями их входов. Фактор времени в них отсутствует. Наряду с ними существуют многотактные логические схемы, в которых значения их выходов определяются не только значениями их входов, но и их состоянием в предыдущем такте. Фактор времени и определяется такими тактами. К таким логическим схемам относятся схемы памяти (триггеры). Они строятся с помощью обратной связи с выхода на вход.

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

    Такая схема памяти имеет еще и другое название – триггер с раздельными входами. В такой схеме есть вход для запоминания (S) и стирания (R). Широко используется в вычислительной технике и триггер со счетным входом. Он имеет только один вход и один выход. Такая схема осуществляет деление на 2, т.е. состояние ее выхода изменяется только после подачи подряд двух входных импульсов. Соединяя триггеры со счетным выходом в последовательный каскад, можно осуществлять деление на 2, 4, 8, 16, 32, 64 и т.д.

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

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

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

    Связи между электромагнитными реле в схемах удобно обозначать с помощью логических операций НЕ, И, ИЛИ, повторения (ДА) и т.д. Например, последовательное соединение контактов реле реализует логическую операцию И, а параллельное соединение этих контактов – логическую операцию ИЛИ. Аналогично выполняются операции И, ИЛИ, НЕ в электронных схемах, где роль реле, замыкающих и размыкающих электрические цепи, выполняют бесконтактные полупроводниковые элементы – транзисторы, созданные в 1947-1948 гг. Дж. Бардином, У. Шокли и У. Браттейном.

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

    Смотрите так же:

    • Срок по закону аренда земли Минимальный срок аренды государственных земель фермерами могут повысить Подумать над этим поручил правительству Президент РФ Владимир Путин. Имеются в виду земельные участки, находящиеся в государственной или муниципальной собственности и предоставленные в аренду для ведения […]
    • Разместить объявление о ликвидации Публикация сообщений о существенных фактах в журнале «Вестник государственной регистрации» Сообщение о ликвидации ЮЛ Документы необходимые для публикации сообщения Не используя электронную подпись. Используя электронную подпись. Бланк-заявка — 1 экз. Сопроводительное письмо — 1 […]
    • Как подать объявление в вестник о ликвидации ооо Публикация о ликвидации в «Вестнике государственной регистрации» Журнал «Вестник государственной регистрации» — СМИ для официальных сообщений налоговой службы и юридических лиц. Согласно приказу ФНС России от 16.06.2006 N САЭ-3-09/[email protected] (скачать pdf), российские компании обязаны […]
    • Условия материнского капитала 2011 Направляем материнский капитал на улучшение жилищных условий Анна Мазухина, Эксперт Службы Правового консалтинга компании "Гарант" Право на федеральный материнский капитал имеет любая женщина-россиянка, родившая или усыновившая второго или последующего ребенка (тоже гражданина России) в […]
    • Институт медико социальной экспертизы СПбИУВЭК, кафедра терапии, МСЭ и реабилитации Кафедра терапии, медико-социальной экспертизы и реабилитации ФГОУ ДПО "Санкт-Петербургского института усовершенствования врачей-экспертов" располагается на базе Госпиталя для ветеранов войн с 1980 года. На снимке заведующий кафедрой доцент […]
    • Приказ 186 мвд гибдд Приказ 186 мвд 02 марта 2009 года приказом МВД РФ 185 был утвержден Административный регламент МВД РФ по исполнению государственной функции по контролю и надзору за соблюдением участниками дорожного движения требований в области обеспечения безопасности дорожного движения. Также советуем […]