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

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

Булева алгебра. Часть 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, сигнал через нее не пройдет — цепь разорвана. Вывод: две релейные схемы эквивалентны друг другу тогда, когда равны их структурные формулы.

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

electrik.info

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

Дата добавления: 2015-08-31 ; просмотров: 427 ; Нарушение авторских прав

К основным законам (тождествам, правилам) булевой алгебры относятся:

1. Коммутативные (переместительные) законы:

2. Ассоциативные (сочетательные) законы:

3. Дистрибутивные (распределительные) законы:

4. Закон двойного отрицания:

5. Законы тавтологии (идемпотентности):

6. Законы нулевого элемента:

7. Законы единичного элемента:

8. Законы дополнительного элемента. В булевой алгебре дополнительным элементом по отношению к а является отрицание а

9. Законы двойственности (де Моргана):

10. Законы поглощения:

life-prog.ru

Основные законы и следствия Булевой алгебры

Логические основы цифровой техники

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

В алгебре логики рассматриваются переменные, которые могут принимать только два значения: 1 и 0.

Основные логические функции:

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

2. Логическое умножение И (конъюнкция). Символически обозначается: или

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

3. Логическое сложение ИЛИ (дизъюнкция). Операция обозначается выражениями: либо

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

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

4. закон поглощения:

5. закон склеивания:

6. закон отрицания или правило де Моргана:

Правило де Моргана справедливо для любого числа переменных:

Для алгебра логики справедливы следующие соотношения:

9.2. Минимизация логических функций с помощью алгебраических преобразований

Минимизация логических функций применяется при синтезе комбинационных логических цепей (КЛЦ). КЛЦ — это такие цепи, выходные сигналы которых не зависят от предыстории и однозначно определяются сигналами, поступающими на их входы в рассматриваемый момент времени.

Синтез КЛЦ проводят в следующей последовательности:

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

2) Исходя из таблицы истинности, записывается логическая функция.

3) Логическая функция минимизируется и преобразуется к удобному виду для реализации на логических ячейках заданного типа.

Рассмотрим работу мажоритарной ячейки на 3 входа. Строим таблицу истинности:

Построим схему по полученному выражению:

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

10. Основные параметры цифровых схем

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

11. Элемент И-НЕ в ДТЛ

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

Разберём работу схемы И-НЕ с ДТЛ, работающую от положительных сигналов (рисунок 7). Схема состоит из двух частей. В первой входные переменные подаются на диодный элемент И. Вторая часть выполнена на транзисторе и представляет собой инвертор. Таким образом в схеме последовательно выполняется логическая операция И-НЕ. Диоды VD3, VD4 называются смещающими диодами и предназначены для надёжного закрывания транзистора.

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

studopedia.ru

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

Законы и правила

1. Закон двойного отрицания

2. Закон коммутативности

3. Закон ассоциативности

4. Закон дистрибутивности

5. Правила де-Моргана

6. Правила операций с константами 0 и 1

7. Правила операций с переменной и ее инверсией

8. Закон поглощения

9. Закон идемпотентности

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

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

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

.

3. Синтез комбинационных схем

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

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

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

сформировать алгебраическое представление реализуемой булевой функции;

осуществить минимизацию полученной булевой функции;

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

Формы представления булевых функций

В алгебре логики доказывается, что любую функцию алгебры логики, кроме функции f = 0, можно представить в виде формулы через конъюнкцию, дизъюнкцию и отрицание в виде

(4)

где — общее обозначение для аргументаxkи его отрицания.

Логическое суммирование в (4) ведется для тех наборов 1,2, …,k, …,n, для которых.

Представление функции алгебры логики в форме (4) называют совершенной дизъюнктивной нормальной формой (СДНФ). Члены, входящие в СДНФ, называютдизъюнктивными членамииликонституентами единицы.

Правило построения СДНФдля булевой функции, заданной таблицей истинности:

1) выписать из таблицы те наборы, для которых функция равна единице;

2) для каждого выписанного набора составить конъюнкцию ;

3) соединить полученные конъюнкции знаком дизъюнкции — получается СДНФ искомой функции.

Пример 1.Составить СДНФ для таблично заданной функции (табл. 5).

studfiles.net

Математическая логика

1.3 Основные аксиомы и теоремы булевой алгебры:

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

(1.1) a v b=b v a ab=ba коммутативные законы

(1.2) a v (bc) = (a v b)(a v c); a(b v c)=(ab) v (ac) дистрибутивные законы.

(1.3)a v 0=a; a1=a

(1.4) а v ¬ а=1 закон исключенного третьего

а¬а=0 закон противоречия

(1.5) а v (Ь v с)=(а v Ь) v с; ас)=(аЬ) с ассоциативные законы

(1.6) если для всех а, а v b = а, то b=0 если для всех а .аЬ = а, то Ь=1

(1.7) если аvЬ=1 и аЬ=0, то b=¬ а

(1.10) а v 1=а, aa=a законы равностепенности или идемпотентности

(1.11) а v 1=1 a0=0

(1.12) а v (аЬ)=а a(a v b)=a законы поглощения

(1.13)¬(a v b)=¬a¬b, ¬(ab)=¬a v ¬b Законы де Моргана

1.4. Булевы формулы

Булевы функции могут быть представлены с помощью таблиц истинности иди в виде формулы.

* Каждая переменная есть формула.

* Если х, у — формулы, то формулами являются (¬x), (x v y), (х&у).

* Других формул нет.

В изображении формул приняты следующие допущения: внешние скобки опускают; наивысшим приоритетом обладает операция отрицания, затем конъюнкция, затем дизъюнкция. С учетом этих приоритетов избыточные скобки также опускаются. Часто не изображается символ конъюнкции (& или л). В изображениях формул допускается использование логических связок импликации (-») и эквивалентности (а).

Для каждой булевой формулы можно построить таблицу истинности, вычисляя ее значения на каждом наборе. Например, мы можем проверить справедливость основных теорем (1.1) — (1.13) с помощью таблиц истинности. Покажем,’ что формулы ау(Ь & с) и (а v Ь)&(а v с) равносильны. Построим их таблицы истинности (табл. 1.3)

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

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

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

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

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

bookwu.net

admin

Обсуждение закрыто.