Булевой алгеброй называется непустое множество с двумя двуместными операциями (аналог конъюнкции), (аналог дизъюнкции), одноместной операцией ¬ (аналог отрицания) и двумя выделенными элементами: 0 (или «Ложь») и (или «Истина») такими, что для всех , и из множества верны следующие аксиомы:
Первые три аксиомы означают, что (, , ) является решёткой. Таким образом, булева алгебра может быть определена как дистрибутивная решётка, в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется псевдобулевой алгеброй.
Булева алгебра имеет практическое приложение в цифровой технике, основанной на двоичной логике. Как существуют булевы функции, так существуют и булевы производные. Булевы производные – единственный математический аппарат для разработки тестов цифровой техники.
Множество элементов с заданными на них двуместными операциями «логическое И» и «логическое ИЛИ» (конъюнкция и дизъюнкция), удовлетворяющими законам коммутативности, ассоциативности, идемпотентности и поглощения, называется структурой, а если выполняется еще и закон дистрибутивности, то и дистрибутивной структурой. В случае, когда к указанным выше операциям добавляется еще одна одноместная инволютивная операция НЕ (отрицание), причем удовлетворяются законы де Моргана и законы нейтральности, говорят о булевой структуре или булевой алгебре.


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

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

Склеивания

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

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

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


Используя логические соотношения , можно получить

Принцип двойственности

В булевых алгебрах существуют двойственные утверждения, они либо одновременно верны, либо одновременно неверны. Если в формуле, которая верна в некоторой булевой алгебре, поменять все конъюнкции на дизъюнкции, 0 на 1, ? на ? и наоборот, то получится формула, также истинная в этой булевой алгебре. Это следует из симметричности аксиом относительно таких замен.
Булевы операции очень близки (хотя и не тождественны) логическим связкам в классической логике. Бит можно рассматривать как логическое суждение — его значениями являются 1 «истина» и 0 «ложь». При такой интерпретации известные в логике связки конъюнкции, дизъюнкции, импликации, отрицания и другие имеют представление на языке битов. И наоборот, битовые операции легко описываются на языке исчисления высказываний.
Связкам математической логики более соответствуют логические операции в том числе в программировании, чем собственно битовые операции.
Высказывания могут быть простыми и сложными. Сложное высказывание образуется в результате объединения простых высказываний с помощью логических связей. Сложные высказывания, получаемые из простых, будут истинными или ложными в зависимости от истинности или ложности простых высказываний, входящих в сложные. Значение сложного высказывания, так же как и простого, может принимать значение 0 или 1. Сложное высказывание можно рассматривать как электрический сигнал на выходе некоторой преобразующей схемы. Значение его будет равно 0 или 1 в зависимости от значений сигналов (простых высказываний) на входе рассматриваемой схемы. Это позволяет применять символику алгебры логики для анализа и синтеза цифровых схем.

Булевы операции как основа цифровой техники

Булевы операции лежат в основе обработки цифровых сигналов. Через булевы операции можно из одного или нескольких сигналов на входе получить на выходе новый сигнал, который, в свою очередь, может быть подан на вход одной или нескольким таким операциям. Булевы операции в сочетании с запоминающими элементами (например, триггерами) реализуют всё богатство возможностей современной цифровой техники.«Логическое НЕ (NOT)», инвертирование — аналог отрицания в логике. Данная одноместная операция (с одним входом) заменяет 0 на 1 и наоборот. Реализующий её элемент называется инвертором. НЕ инвертирует любую двоичную цифру или группу цифр.
«Логическое И (AND)» — аналог конъюнкции в логике. Иногда называется логическим умножением. Выход вентиля И принимает значение 1 только в том случае, если обе входные переменные A и B, то на выходе появляется 1, во всех остальных случаях выход принимает значение 0. В общем случае число входов вентиля не ограничено.«Логическое ИЛИ (OR)» — аналог дизъюнкции в логике. Выход вентиля ИЛИ принимает значение 0 если обе входные переменные A и B принимают значение 0, во всех остальных случаях выход равен 1. В общем случае число входов вентиля не ограничено. Операция двойственна AND: при инвертировании выхода и всех входов (то есть при замене 0 и 1 местами) «И» и «ИЛИ» взаимно превращаются друг в друга.
Операции могут совмещать инвертирование с выполнением функций И и ИЛИ.
«ИЛИ-НЕ (NOR, «стрелка Пирса»)». Стрелка Пирса является результатом инвертирования результата «ИЛИ» своих аргументов, выдаёт значение 1 только когда оба входа 0.
«И-НЕ (NAND, штрих Шеффера)». Двойственная стрелке Пирса операция: является результатом инвертирования результата «И» своих аргументов, выдаёт значение 0 только когда оба входа 1.
Импликация («если-то») – аналог импликации в логике. Совпадает с «ИЛИ» с инвертированным первым аргументом, выдаёт значение 0 только когда первый вход 1 а второй — 0. Данная операция не является коммутативной, в отличие от всех вышеописанных бинарных операций. Её можно понимать как арифметическое (меньше или равно).
Эквиваленция. Выдаёт 1 если и только если оба аргумента равны между собой. Является результатом инвертирования результата «исключающего ИЛИ» своих аргументов. Она же и двойственна исключающему «ИЛИ» в вышеописанном смысле.«Исключающее ИЛИ (XOR, сложение по модулю 2)» – аналог исключающего ИЛИ в логике. Если входные переменные A и B имеют разное значение, то выход принимает значение 1, во всех остальных случаях выход равен 0. Операция обозначается символом . Результат операции XOR отличается от результата OR только в случае одновременного равенства аргументов 1: . Значение данной логической связки можно передавать союзом «либо».
Результат операции XOR является сложением в кольце вычетов по модулю 2, в отличие от операций «И» и «ИЛИ» данная операция является обратимой, или инволютивной: .
В компьютерной графике «исключающее ИЛИ» применяется в компьютерной анимации при выводе элементов изображения (спрайтов) на экран – повторное применение операции XOR к тем же элементам изображения стирает спрайты с экрана. Благодаря инволютивности операция XOR нашла применение в криптографии как простейшая реализация шифра Вернама. «Исключающее ИЛИ» также может использоваться для обмена двух переменных, используя алгоритм обмена при помощи исключающего ИЛИ.
Операции «И», «ИЛИ» и «исключающее ИЛИ» являются не только коммутативными, но и ассоциативными, и потому легко обобщаются на случай нескольких аргументов (входов).Теперь вместо одиночных битов рассмотрим векторы из фиксированного количества битов (для нас это регистры и ячейки памяти). Регистр можно рассматривать, как двоичное разложение целого числа:
(N – количество битов в регистре) и булевые операции проводят по-компонентно (значение в k-ом бите – результат операции над k-ми битами аргументов). Булевы операции распространяются таким образом на произвольную булеву алгебру. Таким образом мы получаем операции побитового AND, OR, NOT, XOR и так далее. Побитовое NOT для чисел в дополнительном коде совпадает с вычитанием из минус единицы.


(единицы повторятся раз)
(нули повторятся раз)




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

Логические соотношения

Теоретической основой проектирования цифровых систем является алгебра логики или булева алгебра. В алгебре логики различные выражения (высказывания) могут иметь только два значения ? «истинно» или «ложно». Для обозначения истинности или ложности высказываний пользуются символами 1 или 0. Это хорошо согласуется с двоичной системой счисления и с работой двухпозиционных элементов, используемых в микропроцессоре. Например, истинность высказывания может быть представлена в микропроцессоре сигналом положительного (отрицательного) электрического напряжения, а ложность – отрицательным (положительным) напряжением или отсутствием сигнала вообще.

1. Чему равны следующие соотношения?
   1. 
   2. 
   3. 
   4. 
   5. 
   6. 
   7. 
   8. 
   9. 
2. Как модифицировать операцию «Исключающее ИЛИ» что бы получилась инверсия?
3. C помощью логических преобразований покажите, что
   
   
4. Докажите, что
5. найти
   1. 
   2. 
   3. 
   4. 
6. Докажите, что
7. C помощью логических преобразований выведите уравнение Хантингтона
8. Доказать, что
9. C помощью логических преобразований выведите уравнение Роббинса
   
10. Докажите что
11. Используя взаимные замены операций AND и OR и символов 0 и 1 расположите в одной таблице тождества и законы алгебры логики.

Миниатюры

     

     

 

Изображения

 

0