Операции булевой алгебры: Булева алгебра — Boolean algebra

Содержание

Законы Булевой алгебры. — таблицы Tehtab.ru


Навигация по справочнику TehTab.ru:  главная страница  / / Техническая информация / / Математический справочник / / Математическая логика.  / / Законы Булевой алгебры.
Законы Булевой алгебры.
Законы Булевой алгебры.

Поглощение

A + (A*B) = A

A*(A + B) = A

Аннулирование

A + 1 = 1

A*0 = 0

Ассоциативность (объединение)

(A + B) + C = A + (B + C)

(A*B)*C=A*(B*C)

Коммутативность (перестановка)

A + B = B + A

A*B=B*A

Дополнение

A + ¬A = 1

A*¬A = 0

Правило Де Моргана

¬(A + B) = ¬A*¬B

¬(A*B) = ¬A + ¬B

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

A*(B + C) = (A*B) + (A*C)

A + (B*C) = (A + B)*(A + C)

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

¬¬A=A

Тождественность

A + 0 = A

A*1 = A

Тавтология

A*A = A

A + A = A




Нашли ошибку? Есть дополнения? Напишите нам об этом, указав ссылку на страницу.
TehTab.ru

Реклама, сотрудничество: [email protected]

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

Основные операции булевой алгебры

 

Булева функция представляет собой зависимость y = f(x1 … xn), где x = [0; 1], y = [0; 1]

1. Логическое сложение (OR).

Обозначение:

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

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

 

Схема на диодах:

 

2. Конъюнкция, логическое умножение.

 

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

0 • 0 = 1

1 • 0 = 0

0 • 1 = 0

1 • 1 = 0

 

3. Инверсия (NOT).

 

Некоторые правила булевой алгебры

 

 

Принцип сложения с 0 и 1

X + 0 = X

X + 1 = X

X +X = X

Умножение переменной на 0 и 1

X • 0 = 0

X • X = X

X • 1 = X

Принцип сочетания:

X1 + X2 + X3 = (X1 + X2) + X3 = X1 + (X2 + X3)

Построение логической комбинационной схемы

По заданной функции

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

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

Функция И-НЕ — функция Шеффера.

Функция Пирса — ИЛИ-НЕ

 

Построение комбинационно-логической системы

По заданной функции

 

 

Основные функциональные элементы,

Реализуемые в логических схемах

 

Инвертор

 

 

Функция запрета

 


Узнать еще:

Математика — Алгебра Логики

Существует 16 = 222 разных булевых функции с 2 аргументами (обозначим их x и y). Некоторые из них всегда совпадают по значению с булевой константой, булевой переменной или функцией только от одной из двух переменных. Таких функций всего шесть: 0, 1, x, ~x, y, ~y. Далее мы будем из называть тривиальными. Вот таблицы истинности для них:

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

Конъюнкция

Другие названия этой функции: «И», «логическое И», «логическое умножение», «булево умножение». Другие обозначения этой функции: .

Функция «И» дает 1 только когда оба операнда равны 1. Эта функция называется иногда логическим умножением, поскольку ее результаты совпадают с аналогичной операцией в арифметике: 0 * 0 = 0, 0 * 1 = 0, 1 * 0 = 0, 1 * 1 = 1.

Больше

Функция «>» дает 1 только когда первый операнд равен 1, а второй 0. Эта функция не имеет общеупотребительных названий или обозначений. Я обозначил ее символом «>» и назвал «больше» поскольку она равна 1, только когда первый операнд больше второго в арифметическом смысле: 1 > 0.

Меньше

Функция « Сложение по модулю «2»

xyxy
000
011
101
110

Другие названия этой функции: «исключающее ИЛИ», «логическое ЛИБО», «неравносильность», «неэквивалентность», «логическое сложение», «булево сложение».

Другие обозначения этой функции: .

Функция «» дает 1 только когда первый операнд не равен второму операнду. Она похожа на арифметическое сложение: 0 0 = 0, 0 1 = 1, 1 0 = 1, но не всегда: в булевой алгебре 1 1 = 0, а не 2, как в арифметике. Как уже говорилось ранее, булевы величины 1 и 0 не являются числами и для них арифметика неприменима.

Дизъюнкция

xyxy
000
011
101
111

Другие названия этой функции: «ИЛИ», «логическое ИЛИ».

Другие обозначения этой функции:

С обозначением этой функции очень много путаницы. Во-первых, в программировании для нее используется обозначение x|y, но в математике это обозначение уже занято другой логической функцией — штрих Шеффера (см. чуть ниже). Во-вторых, сплошь и рядом для этой функции применяется обозначение «+», но так же часто обозначение «+» применяется для сложения по модулю «2».

Функция «ИЛИ» дает 0 только когда оба операнда равны 0.

Стрелка Пирса

xyxy
001
010
100
110
Другие названия этой функции: «ИЛИ-НЕ».

Эта функция дает 1 только когда оба операнда равны 0.

Равносильность

xyxy
001
010
100
111

Другие названия этой функции: «равносильность».

Другие обозначения этой функции:

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

Обратная импликация

xyxy
001
010
101
111

Другие обозначения этой функции:

Эта функция дает 0 только когда первый операнд равен 0, а второй равен 1.

Импликация

xyxy
001
011
100
111

Другие обозначения этой функции:

Эта функция дает 0 только когда первый операнд равен 1, а второй равен 0.

Штрих Шеффера

Другие названия этой функции: «И-НЕ».

Другие обозначения этой функции: ‘ (апостроф).

Эта функция дает 0 только когда оба операнда равны 1.

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

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

Итак, общий формат для обозначения функции от двух аргументов через знак бинарной операции выглядит как (F)#(G), где F и G — некоторые формулы, а # — знак бинарной операции. Для вычисления значения формулы (F)#(G) надо вычислить значение формул F и G, и подставить их в таблицу истинности как первый и второй аргументы функции.

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

Скобки вокруг F можно опускать, если F имеет вид: 0, 1, ~0, ~1, x, ~x, ~(H), где x — произвольная булева переменная, H - произвольная формула булевой алгебры. Иначе скобки опускать нельзя. То же правило относится и к G. Например: (~z & (x & y)) (~(~t & z) & x).

На практике опускают еще больше скобок, если это не затрудняет понимание, и есть договоренность о том, в каком порядке какие операции вычисляются. Обычно первой вычисляется операция «&», потом «» и «», потом все остальные. Если рядом идут операции одного приоритета, то вычисляются подряд слева направо.

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

2 глава. Логические основы ЭВМ.

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

Основные элементы булевой алгебры.

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

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

Операции в булевой алгебре – действия над числами.

А) Операция отрицания (инверсии). В результате этой операции переменная принимает противоположное значение.

Пример. А=1 – переменная имеет значение равное «12».

А=0 – при инверсии переменная принимает значение равное «02».

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

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

Б) Операция конъюнкции (логическое умножение, логическая операция «И»).

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

С=А*В=АВ=АВ, где А, В – логические переменные.

С- результат конъюнкции.

Правила логического умножения.

А

В

С

0

0

0

1

1

1

1

0

0

Операцию конъюнкции выполняют на устройстве, которое на схеме принято обозначать следующим образом:

Х1

Y

XN

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

В) Операция дизъюнкции (логическое сложение, логическая операция «ИЛИ»).

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

С=А+В=АВ= где А, В – логические переменные.

С- результат конъюнкции.

Правила логического умножения.

А

В

С

0

0

0

1

1

1

1

0

1

Операцию дизъюнкции выполняют на устройстве, которое на схеме принято обозначать следующим образом:

Х1

Y

XN

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

Старшинство операций. 1 очередь – инверсия, 2 очередь – умножение, 3 очередь – сложение.

Булевой или логической функцией вида F(x1,x2……..xN), называется функция, аргументами которой являются булевые переменные xiи которая принимает значения из множества {0,1}.

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

Пример. Y=F(x1,x2)= x1x2, где n=2 – число аргументов функции.

x1,x2 – аргументы функции.

 — операция дизъюнкции, соединяющая аргументы x1 и x2.

Отметим, что используя три логические операции (,,) и n-е число булевых переменных можно создать булевые функции любой сложности.

Количество всевозможных функций N от n-го числа аргументов булевой функции выражается зависимостью:

N=(2)n

Так при n=0 число функций N=2. Такими функциями с n=0 аргументов являются функции не зависящие от аргументов функции.

Пример. F0( _ )=0 или const=0

F1( _ )=1 или const=1

При n=1 число функций N=4. Представим зависимость значений этих функций от значений аргументов булевых функций в виде таблицы истинности.

Таблица истинности функций от одной переменной.

Значение аргумента

Значение функции

Y0

Y1

Y2

Y3

0

0

0

1

1

1

0

1

0

1

Y1 – функция аналогичная F0 (смотри предыдущий пример).

Y3 – функция аналогичная F1 (смотри предыдущий пример).

Y2 – функция, выполняющая инверсию аргумента. (Y=X)

Y1– функция повторения аргумента. (Y= X).

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

M=2n., где n – число аргументов.

Так при n=1 M=2 (смотри таблицу истинности от 1 аргумента).

Способы задания булевых функций.

Существует 4 способы задания булевых функций.

  1. Аналитический. При этом способе функция Y=F(x1,x2……..xN) будет записана в следующем виде:

Y= x1+x2x3……, то есть аналитическая форма представления функции получается при помощи соединения логическими операциями (,,) переменных. Добавим, что эта форма наиболее часто употребляется для представления логических функций.

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

Пример. Функция Y=F(x1,x2) – принимает значения 1 при равенстве двух аргументов. Количество наборов M=2n=22=4. Тогда таблица истинности будет иметь вид:

Значение аргументов

Значение функции

Примечания

x1

x2

Y

0

0

1

Аргументы равны

0

1

0

Аргументы не равны

1

0

0

Аргументы не равны

1

1

1

Аргументы равны

  1. Числовой.

  2. Графический.

Лекция 3 Булевы алгебры и булевы функции

2 Перечень технических средств обучения

Практическая работа 6 Решение логических задач с применением законов алгебры логики Цель работы: закрепление умений преобразовывать логические выражения с использованием законов алгебры логики, вычислять

Подробнее

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

Расчетная работа 4 Основы алгебры логики Поскольку в цифровых устройствах используются только два символа 0 и 1, алгебра логики использует логические переменные и функции от них, которые также принимают

Подробнее

Тема 9.

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

Тема 9. Логические основы ЭВМ. 1. Логика. Информация, обрабатываемая в ЭВМ, представляется с помощью физических величин, которые могут принимать только два устойчивых состояния и называются «двоичные переменные».

Подробнее

ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ (продолжение)

ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ (продолжение) Число булевых функций от n переменных находится по формуле: P2 (n) = 2 2n Логических функций двух переменных 6 Наиболее часто употребляются следующие функции: f (x,

Подробнее

Аксиоматический метод

Аксиоматический метод Лекция по предмету «основы мат. Обработки информации» Составитель: доцент кафедры ИТОиМ КГПУ им. В.П. Астафьева Романова Н.Ю. Аксиоматический метод построения научной теории заключается

Подробнее

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

Алгебра логики

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

Подробнее

ДИСКРЕТНАЯ МАТЕМАТИКА

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Подробнее

Основы математической логики.

Основы математической логики. Киселев Александр Сергеевич Аничков лицей, 6 класс, первый год обучения январь-февраль 2012/13 учебный год 1 Высказывания и предикаты 1.1 Высказывания Определение 1.1. Определение:

Подробнее

II. АЛГЕБРА ЛОГИКИ.

1. Понятие алгебры

II АЛГЕБРА ЛОГИКИ Понятие алгебры n Функция типа ϕ: M M называется n -арной операцией на множестве M ; n называется арностью операции Множество M вместе с заданной на нем совокупностью операций = { ϕ,,

Подробнее

Тождества Булевой алгебры

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

Подробнее

1.Основные сведения из алгебры логики

Тема 4. Логические основы ЭВМ 1.ОСНОВНЫЕ СВЕДЕНИЯ ИЗ АЛГЕБРЫ ЛОГИКИ… 1 2. ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ… 4 3. ПОНЯТИЕ О МИНИМИЗАЦИИ ЛОГИЧЕСКИХ ФУНКЦИЙ… 6 4.ТЕХНИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ…

Подробнее

Глава III. Алгебра логики

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

Подробнее

Дискретная математика

Дискретная математика Часть 2 ВЕ Алексеев 2016 Глава 6 Логические функции Алгебра логики 61 Булевы функции Существенные и фиктивные переменные Функция, у которой каждая переменная принимает значения из

Подробнее

Дискретная математика

Дискретная математика Часть 4 ВЕ Алексеев 2014 Глава 6 Логические функции Алгебра логики 61 Булевы функции Существенные и фиктивнык переменные Функция, у которой каждая переменная принимает значения из

Подробнее

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

Основы алгебры логики Максименкова Ольга Вениаминовна, ст. преподаватель департамента программной инженерии ФКН НИУ ВШЭ, м.н.с. МНУЛ ИССА Чуйкин Николай Константинович, выпускник образовательной программы

Подробнее

Глава III. АЛГЕБРА ЛОГИКИ

Глава III АЛГЕБРА ЛОГИКИ Функцией алгебры логики называется отображение f: E2, где x i E 2, i =, 2,, Функции алгебры логики также называются булевыми функциями (в честь английского математика Дж Буля)

Подробнее

1 Дизъюнкция, конъюнкция и др.

1 Дизъюнкция, конъюнкция и др. 1. Таблица истинности дизъюнкции, стрелка Пирса 1. p q p q p q 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 2. Таблица истинности. Конъюнкция, штрих Шеффера 2 p q p q p q 0 0 0 1 0 1

Подробнее

Сборник задач по высшей математике

Сборник задач по высшей математике àñòü 2 Учебное пособие Под редакцией À. Ñ. Ïîñïåëîâà Рекомендовано Министерством образования и науки РФ в качестве учебного пособия для студентов вузов, обучающихся по

Подробнее

Полные системы связок

Математическая логика и теория вычислимости Лекция 2. Кафедра математических и информационных технологий Санкт-Петербургского академического университета 20.02.2017 План лекции 1 Полнота системы связок

Подробнее

Теория меры, лекция 3: Булевы алгебры

Теория меры, лекция 3: Булевы алгебры Миша Вербицкий 28 февраля, 2015 матфак ВШЭ и НМУ 1 Решетки ОПРЕДЕЛЕНИЕ: Пусть (M, ) частично упорядоченное множество, а S его подмножество. Верхняя грань inf S есть

Подробнее

Функции алгебры логики

Математическая логика Функции алгебры логики Лектор: к.ф.-м.н., доцент кафедры прикладной информатики и теории вероятностей РУДН Зарипова Эльвира Ринатовна [email protected] ru Курс математической логики Наименование

Подробнее

First Prev Next Last Go Back Full Screen Close Quit

Ткачев С.Б. каф. Математического моделирования МГТУ им. Н.Э. Баумана ДИСКРЕТНАЯ МАТЕМАТИКА ИУ5 4 семестр, 2015 г. Лекция 10. АЛГЕБРЫ: ПОЛУКОЛЬЦА Определение 10.1. Полукольцо это алгебра с двумя бинарными

Подробнее

Логические основы работы ЭВМ

Министерство образования и науки Российской Федерации Государственное образовательное учреждение высшего профессионального образования «Тихоокеанский государственный университет» Логические основы работы

Подробнее

Глава I. ОСНОВЫ ТЕОРИИ МНОЖЕСТВ

Глава I ОСНОВЫ ТЕОРИИ МНОЖЕСТВ Под множеством понимают любой набор определенных и различимых между собой объектов, мыслимый как единое целое Объекты, составляющие множество, называются элементами множества

Подробнее

Теория Меры 2: мера Лебега

Теория Меры 2: мера Лебега 2. 1. Булевы алгебры Определение 2.1. Решетка это множество L, наделенное алгебраическими бинарными операциями и : L L L, которые удовлетворяют следующим условиям. а. Идемпотентность:

Подробнее

5. БУЛЕВЫ ФУНКЦИИ(примеры доказательств)

5. БУЛЕВЫ ФУНКЦИИ(примеры доказательств) 1. Двоичные векторы Любое положительное целое число имеет единственное двоичное представление (представление в виде суммы неповторяющихся степеней числа 2). Например:

Подробнее

Элементы общей алгебры. Алгебра, гомомофризм, изоморфизм, полугруппа, группа

Элементы общей алгебры Алгебра, гомомофризм, изоморфизм, полугруппа, группа Алгебраическая операция На множестве А определена алгебраическая операция, если каждым двум элементам этого множества, взятым

Подробнее

Основные понятия алгебры логики.

Основные понятия алгебры логики. Для математического описания работы вычислительных устройств и их программного проектирования широко используется алгебра логики (булевская алгебра). Алгебра логики — часть

Подробнее

сайты:

Федеральное агентство по образованию Уральский государственный экономический университет Ю. Б. Мельников Булевы и логические функции Раздел электронного учебника для сопровождения лекции Изд. 3-е, испр.

Подробнее

Лекция 3: множества и логика

Лекция 3: множества и логика Дискретная математика, ВШЭ, факультет компьютерных наук (Осень 2014 весна 2015) Мы уже использовали понятие множества и в дальнейшем будем его использовать постоянно. Сейчас

Подробнее

Информатика и ИКТ Лекция 6 1 курс

Информатика и ИКТ Лекция 6 1 курс ФГОУ СПО «УМТК» Кондаратцева Т. П. 1 Принципы обработки информации компьютером. Арифметические и логические основы работы компьютера ФГОУ СПО «УМТК» Кондаратцева Т.П. 2

Подробнее

Дискретная математика

Дискретная математика ЛИТЕРАТУРА. Яблонский С.В. Введение в дискретную математику. — М.: Наука, 979. 2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. М.: Энергоатомиздат, 988.

Подробнее

Задачи по дискретной математике

Задачи по дискретной математике Ф.Г. Кораблев 1 Комбинаторика 1.1. Найти число подмножеств X множества {A, B, C, D, E, F, G, H, I, J}, обладающие следующими свойствами: 1. X = 3 2. X = 5, A X 3. X = 6,

Подробнее

Решения задач по двузначной логике

Решения задач по двузначной логике Ф.Г. Кораблев Задача 1. Для функции f(x, y, z) = ((x y) (x z)) (z x) найти существенные и фиктивные переменные, произвести операцию исключения фиктивных переменных. Решение.

Подробнее

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

III. МАТЕМАТИЧЕСКАЯ ЛОГИКА ГЛАВА 1. ПЕРЕКЛЮЧАТЕЛЬНЫЕ ФУНКЦИИ 1.1. Основные определения Переключательными (логическими) функциями называют функции, область значений которых есть подмножество двухэлементного

Подробнее

Логика предикатов лекция 5

Логика предикатов лекция 5 Лев Дмитриевич Беклемишев http://lpcs.math.msu.su/vml2009 [email protected] 12.03.2008 Предикаты и функции Пусть M непустое множество. n-арный предикат на M: подмножество Q M n

Подробнее

Булевы решетки и булевы алгебры


Определение: Дистрибутивная решетка с дополнениями называется Булевой решеткой.

Определение: Булева Алгебра А=(А, ∨, ∧, ⌐, 0, 1) есть множество А на котором определены три операции:
1) x∨y: AxA → A
2) x∧y: AxA → A
3) ⌐x: A → A
и два отмеченных элемента (0, 1) (универсальные границы) удовлетворяющие следующим аксиомам ∀ x,y,z ∈A:

B1) x∧x=x, x∨x=x
B2) x∧y=y∧x, x∨y = y∨x
B3) x∧(y∧z) = (x∧y)∧z, (x∨y)∨z = x∨(y∨z)
B4) x∧(x∨y) = x, x∨(x∧y) = x
B5) x∧(y∨z) = (x∧y)∨(x∧z), x∨(y∧z) = (x∨y)∧(x∨z)
B6) ⌐⌐x = x
B7) x∧1=x, x∧0=0, x∨1=1, x∨0=x
B8) x∨⌐x=1, x∧⌐x=0
B9) ⌐(x∨y)=⌐y ∧⌐x, ⌐(x∧y)= ⌐x ∨ ⌐y – правило де Моргана.

Замечание: иногда вместо x∧y пишут x&y, xy xy

Пример 1: Если U – есть конечное множество с n элементами и P(U) — есть множество всех его 2n подмножеств, то система (P(U), ∨, ∧,-,0,1) – есть Булева алгебра в которой для подмножеств А и В.
A∨B=A∪B
A∧B=A∩B
A=U-A
0=∅
I=U

Пример 2: система ({0,1},∨,&,¬,0,1) – есть Булева алгебра.

Замечание: (Принцип двойственности): Если в Булевой алгебре истинно некоторое равенство, построенное с помощью ∨, &, ¬, 0, 1 с некоторым расставлением скобок, то истинно и равенство, полученное из исходного заменой: ∨ на &, & на ∨, 0 на 1, 1 на 0 с тем же расставлением скобок.

Теорема (Связь булевых решеток и булевых алгебр). Если алгебра является булевой алгеброй, то – булева решётка. Если алгебра – булева решётка, то , где операция ¬ определена как дополнение в булевой решётке, 0 и 1 – соответственно как ноль и единица в булевой решётке – булева алгебра.

Замечание: всякая Булева алгебра (А, ∨, ∧, ¬,0, 1) – есть решетка (А, ∨, ∧) в которой можно задать отношение частичного порядка, определенного соотношением a ≤ b ↔ a*b=a (или a∨b=b), тогда система (А, ≤) – есть ЧУМ.

Теорема: если Ai =(Аi, ∨i, ∧i, ¬ i,0 i, 1 i) i=1,2 – есть две Булевых алгебры, то A1 ≅ A2 ↔ (А1, ≤1) ↔ (А2, ≤2). Другими словами Булевы алгебры A1 ≅ A2 ⇔ когда A1 и A2 – изоморфны как ЧУМ.
Без доказательства.

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

Следствие:
1) конечные Булевы Алгебры изоморфны ⇔ они равноправны
2) Число элементов Булевой алгебры равно степени 2
3) Теорема Стоуна (о представлении) справедлива для бесконечной Булевой алгебры.

2 4 Законы Булевой алгебры

2.4. Законы Булевой алгебры.

БА базируется на нескольких аксиомах:

Аксиомы операции отрицания:

Аксиомы операций.

конъюнкции

и

конъюнкции

0·0 = 0

11 = 1

1·0 = 0·1 = 0

01 = 10 = 1

1·1 = 1

00 = 0

Законы БА вытекают из аксиом и имеют две формы выражения: для конъюнкции и дизъюнкции. Их правильность легко проверить по таблицам истинности, либо путем подстановки 0 и 1 вместо соответствующих значений переменных.

Для конъюнкции

Для дизъюнкции

1. Переместительный закон:

2. Закон повторения (тавтологии):

3. Закон нулевого множества:

4. Закон универсального множества:

5. Закон дополнительности:

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

7. Закон склеивания:

8. Закон инверсии (закон Де Моргана):

или после инвертирования правых и левых частей

9. Закон обращения: если , то

10. Закон двойной инверсии:

11. Сочетательный закон:

12. Распределительный закон:

Для примера преобразуем на основе законов БА функцию:

Раскроем скобки:

Так как закон дополнительности, то

Схемы, реализующие заданную функцию и полученную, представлены на рисунках 2.6 а и 2.6.б.

Аналогично можно минимизировать рассмотренное ранее выражение (2.1):

Для минимизации были использованы соотношения:

Закон дополнительности:

Закон универсального множества:

Схема, реализующая полученную функцию, представлена на рис.2.7.

Математика булевой алгебры (Стэнфордская энциклопедия философии)

Булева алгебра (BA) — это множество \ (A \) вместе с двоичными операции + и \ (\ cdot \) и унарная операция \ (- \), а также элементы 0, 1 из \ (A \) такие, что выполняются следующие законы: коммутативность и ассоциативные законы сложения и умножения, законы распределения как для умножения над сложением, так и для сложения над умножение и следующие специальные законы:

\ [\ begin {align *} (х + (х \ cdot у) & = х \\ (х \ cdot (х + у) & = х \\ х + (-х) & = 1 \\ х \ cdot (-x) & = 0 \ конец {выравнивание *} \]

Эти законы лучше понять на базовом примере BA, состоящий из набора \ (A \) подмножеств множества \ (X \) замкнутых при операциях объединения, пересечения, дополнения с относительно \ (X \), с членами \ (\ varnothing \) и \ (X \). Можно легко вывести из этих аксиом многие элементарные законы, имея в виду этот пример для мотивации. Любая БА имеет естественный частичный порядок \ (\ le \) определил на нем, сказав, что \ (x \ le y \) тогда и только тогда, когда \ (x + у = у \). В нашем основном примере это соответствует \ (\ substeq \). Из Особое значение имеет двухэлементная БА, образованная набором \ (X \), чтобы иметь только один элемент. Двухэлементная БА показывает прямую связь с элементарной логикой. Два члена, 0 и 1, соответствуют к лжи и правде соответственно.Затем логические операции выражают обычные таблицы истинности для дизъюнкции (с \ (+) \), конъюнкции (с \ (\ cdot) \) и отрицанием (с \ (-) \). Важный элементарный В результате уравнение выполняется во всех БА тогда и только тогда, когда оно выполняется в двухэлементный БА. Затем мы определяем \ (x \ oplus y = (x \ cdot -y) + (y \ cdot -x) \). Тогда \ (A \) вместе с \ (\ oplus \) и \ (\ cdot \), вдоль с 0 и 1, образует кольцо с единицей, в котором каждый элемент идемпотентный. Наоборот, для такого кольца с добавлением \ (\ oplus \) и умножение, определите \ (x + y = x \ oplus y \ oplus (x \ cdot y) \) и \ (- x = 1 \ oplus x \).Это превращает кольцо в BA. Эти двое процессы противоположны друг другу и показывают, что теория Булевых алгебр и колец с единицей, в которых каждый элемент идемпотенты по определению эквивалентны. Это ставит теорию БА в стандартный объект исследования в алгебре. Атом в БА — это ненулевой элемент \ (a \) такой, что не существует элемента \ (b \) с \ (0 \ lt б \ л а \). БА является атомарной, если каждый ненулевой элемент БА выше атом. Конечные БА атомарны, как и многие бесконечные БА.Под частичный порядок \ (\ le \) выше, \ (x + y \) является точной верхней границей \ (x \) и \ (y \), а \ (x \ cdot y \) — точная нижняя граница \ (х \) и \ (у \). Мы можем обобщить это: \ (\ Sigma X \) — наименьшее верхняя граница множества \ (X \) элементов, а \ (\ Pi X \) — наибольшее нижняя граница множества \ (X \) элементов. Это не для всех множества во всех булевых алгебрах; если они существуют всегда, логическое алгебра называется полной.

Некоторые алгебраические конструкции имеют очевидные определения и простые свойства БА: подалгебры, гомоморфизмы, изоморфизмы и прямые произведения (даже бесконечного числа алгебр).Некоторые другие Стандартные алгебраические конструкции более характерны для БА. Идеал в BA — это подмножество \ (I \), замкнутое относительно +, с 0 в качестве члена, и такое что если \ (a \ le b \ in I \), то также \ (a \ in I \). Хотя нет сразу очевидно, это то же самое, что и теоретико-кольцевой концепция. Существует двойственное понятие фильтра (без аналога в кольца в целом). Фильтр — это подмножество \ (F \), замкнутое относительно \ (\ cdot \), имеющий 1 в качестве члена и такой, что если \ (a \ ge b \ in F \), то также \ (а \ в F \). Ультрафильтр на \ (A \) — это фильтр \ (F \) с следующие свойства: \ (0 \ not \ in F \), и для любого \ (a \ in A \) либо \ (а \ в F \) или \ (- а \ в F \).Для любого \ (a \ in A \) пусть

\ [ S (a) = \ {F: F \ text {является ультрафильтром на} A \ text {и} a \ in F \}. \]

Тогда \ (S \) — изоморфизм на БА подмножеств множества \ (X \) все ультрафильтры на \ (A \). Это устанавливает основной камень теорема о представлении и проясняет происхождение БА как конкретных алгебры множеств. Более того, множества \ (S (a) \) можно объявить база топологии на \ (X \), что превращает \ (X \) в полностью несвязное компактное хаусдорфово пространство. Это устанавливает однозначный соответствие между классом БА и классом таких пробелы.Как следствие, очень часто используемые в теории БА, многие топологические теоремы и концепции имеют последствия для БА. Если \ (x \) является элементом БА, пусть \ (0x = -x \) и \ (1x = x \). Если \ ((x \) (0), \ (\ ldots x (m — 1)) \) — конечная последовательность элементов BA \ (A \), то каждый элемент подалгебры в \ (A \), порожденный \ (\ {x (0), \ ldots, x (m — 1) \} \) можно записать как сумму мономов \ (e (0) x (0) \ cdot \ ldots \ cdot e (m — 1) x (m — 1) \) для \ (e \) в некотором наборе функций, отображающих \ (m = \ {0, \ ldots, m — 1 \} \) в \ (2 = \ {0, 1 \} \). Это алгебраическое выражение дизъюнктивной нормальной формы Теорема сентенциальной логики. Функция \ (f \) из множества \ (X \) образующие БА \ (А \) в БА \ (B \) продолжаются до гомоморфизм тогда и только тогда, когда

\ [ е (0) х (0) \ cdot \ ldots \ cdot e (m — 1) x (m — 1) = 0 \]

всегда означает, что

\ [e (0) f (x (0)) \ cdot \ ldots \ cdot e (m — 1) f (x (m — 1)) = 0. \]

Это критерий расширения Сикорского. Каждый BA \ (A \) может быть вложено в полный BA \ (B \) таким образом, что каждый элемент \ (B \) — наименьшая верхняя граница набора элементов \ (A \).\ (B \) есть единственна с точностью до \ (A \) — изоморфизма и называется пополнением \ (А \). Если \ (f \) — гомоморфизм БА \ (А \) в полную БА \ (B \), и если \ (A \) — подалгебра в \ (C \), то \ (f \) может быть продолжается до гомоморфизма \ (C \) в \ (B \). Это Теорема Сикорского о продолжении. Еще одно общее алгебраическое понятие применительно к булевым алгебрам — понятие свободного алгебра. Это может быть конкретно сконструировано для БА. А именно бесплатные BA на \ (\ kappa \) — это БА замкнутых открытых подмножеств двух элементов дискретное пространство возведено в степень \ (\ kappa \).

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

  • Атомарные БА, уже упомянутые выше.
  • безатомных БА, которые определяются как БА без атомов. Например, любое бесконечное свободный БА безатомен.
  • Полные BA, определенные выше. Это специально важен в основах теории множеств.
  • Интервальные алгебры. Они получены из линейно упорядоченных множеств \ ((L, \ lt) \) с первым элементом следующим образом.Один берет самое маленькое алгебра подмножеств \ (L \), содержащая все полуоткрытые интервалы [\ (a, b) \) с \ (a \) в \ (L \) и \ (b \) в \ (L \) или равно \ (\ infty \). Эти БА полезны в изучение алгебр Линденбаума-Тарского. Каждый счетный БА изоморфна интервальной алгебре, а значит, счетная БА может быть описывается указанием упорядоченного набора, который изоморфен соответствующая интервальная алгебра.
  • Древовидные алгебры. Дерево — это частично упорядоченное множество \ ((T, \ lt) \) в в котором множество предшественников любого элемента упорядочено.Данный такое дерево, рассматривается алгебра подмножеств \ (T \), порожденная всеми множествами вида \ (\ {b: a \ le b \} \) для некоторого \ (a \) в \ (Т \).
  • Суператомные БА. Это БА которые не только атомарны, но таковы, что каждая подалгебра и гомоморфный образ атомарен.

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

  1. Клеточность \ (c (A) \) БА есть верхняя грань мощности множеств попарно непересекающихся элементов \ (A \).
  2. Подмножество \ (X \) БА \ (A \) является независимым, если \ (X \) — набор свободных образующих подалгебры, генерирует. Независимость \ (A \) есть супремум мощности независимых подмножеств \ (A \).
  3. Подмножество \ (X \) БА \ (A \) плотно в \ (A \), если каждый ненулевой элемент \ (A \) является \ (\ ge \) ненулевым элементом \(ИКС\). \ (\ Pi \) — вес \ (A \) — это наименьшая мощность плотного подмножества \ (A \).
  4. Два элемента \ (x, y \) из \ (A \) несравнимы если ни один из них не является \ (\ le \) другим. Супремум мощностей подмножество \ (X \) в \ (A \), состоящее из попарно несравнимых элементов — это несравнимость \ (A \).
  5. Подмножество \ (X \) из \ (A \) неизбыточно, если ни один элемент \ (X \) находится в подалгебре, порожденной другими.

Важным фактом, касающимся клеточности, является метод Эрдеша-Тарского. Теорема: если клеточность БА — особый кардинал, то существует фактически представляет собой набор непересекающихся элементов такого размера; на клеточность штатный лимит (недоступен), есть контрпримеры. Каждый бесконечная полная БА имеет независимое подмножество того же размера, что и алгебра. Каждый бесконечный BA \ (A \) имеет неизбыточную несравнимую подмножество, размер которого равен \ (\ pi \) — весу \ (A \). Каждый интервал алгебра имеет счетную независимость.Суператомная алгебра не даже иметь бесконечное независимое подмножество. Любая древовидная алгебра может быть вложено в интервальную алгебру. БА только с удостоверением личности автоморфизм называется жестким. Существуют жесткие полные БА, а также жесткие интервальные алгебры и жесткие древовидные алгебры.

Совсем недавно многие кардинальные функции типа min-max были учился. Например, малая независимость — это наименьший размер бесконечное максимальное независимое множество; и малая клеточность — это наименьший размер бесконечного разбиения единицы.

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

Очень важная конструкция, которая переносится на многие логики и многих алгебр, кроме булевых, является построением Булева алгебра связана с предложениями в некоторой логике.В Самый простой случай — это логика предложений. Здесь есть символы предложений, и общие связки, составляющие из них более длинные предложения: дизъюнкция, союз и отрицание. Дан набор \ (A \) предложений в этом языке два предложения \ (s \) и \ (t \) эквивалентны по модулю \ (A \) тогда и только тогда, когда двусмысленность между ними является логическим следствие \ (A \). Классы эквивалентности могут быть преобразованы в БА. такой, что + соответствует дизъюнкции, \ (\ cdot \) — конъюнкции и \ (- \) к отрицанию. Любая БА изоморфна одной из этих форм.Можно сделайте что-нибудь подобное для теории первого порядка. Пусть \ (T \) — теория первого порядка в языке первого порядка \ (L \). Мы называем формулы \ (\ phi \) и \ (\ psi \) эквивалент при условии, что \ (T \ vdash \ phi \ leftrightarrow \ psi \). Класс эквивалентности предложения \ (\ phi \) обозначается [\ (\ phi \)]. Пусть \ (A \) — совокупность всех классы эквивалентности по этому отношению эквивалентности. Мы можем сделать \ (A \) в БА следующими определениями, которые легко обосновано:

\ [\ begin {align *} [\ phi] + [\ psi] & = [\ phi \ vee \ psi] \\ [\ phi] \ cdot [\ psi] & = [\ phi \ wedge \ psi] \\ — [\ phi] & = [\ neg \ phi] \\ 0 & = [\ mathrm {F}] \\ 1 & = [\ mathrm {T}] \ конец {выравнивание *} \]

Каждая БА изоморфна БА Линденбаума-Тарского. алгебра.Однако одно из самых важных применений этих классических Алгебры Линденбаума-Тарского должны описать их для важных теорий. (обычно разрешимые теории). Для счетных языков это может быть делается путем описания их изоморфных интервальных алгебр. Обычно это дает доскональное знание теории. Вот несколько примеров:

Теория Изоморфна интервальной алгебре на
(1) по существу неразрешимая теория \ (\ mathbb {Q} \), рациональные числа
(2) БА \ (\ mathbb {N} \ times \ mathbb {N} \), квадрат натуральных чисел в лексикографическом порядке
(3) линейных заказов \ (\ mathbf {A} \ times \ mathbb {Q} \) упорядочены антилексикографически, где \ (\ mathbf {A} \) — это \ (\ mathbb {N} ^ \ mathbb {N} \) в обычном порядке
(4) абелевых групп \ ((\ mathbb {Q} + \ mathbf {A}) \ times \ mathbb {Q} \)

В теории моделей можно принимать значения в любом полном БА, а не в двухэлементный БА. Эта теория булевозначных моделей была развита примерно в 1950–1970 годах, но с тех пор почти не работал. Но частный случай, булевозначные модели для теории множеств, очень авангард современных исследований в области теории множеств. Это фактически формирует эквивалентный способ взглянуть на форсирующую конструкцию Коэна, и имеет ряд технических преимуществ и недостатков. Философски это кажется более удовлетворительным, чем концепция принуждения. Мы описываем это случай теории множеств здесь; тогда станет очевидно, почему только завершать Рассмотрены БА.Пусть B — полная БА. Сначала мы определяем Булевозначный универсум \ (V (B) \). Обычный теоретико-множественный универсум можно отождествить с \ (V \) (2), где 2 — двухэлементная БА. Определение дается трансфинитной рекурсией, где \ (\ alpha, \ beta \) — порядковые числа, а \ (\ lambda \) — предельный порядковый номер:

\ [\ begin {align *} V (B, 0) & = \ varnothing \\ V (B, \ alpha + 1) & = \ {f: \ dom (f) \ subset V (B, \ alpha) \ text {and} \ range (f) \ subset B \} \\ V (B, \ lambda) & = \ bigcup _ {\ beta \ lt \ lambda} V (B, \ beta). \ конец {выравнивание *} \]

где \ (\ dom (f) \) — область определения функции \ (f \), а \ (\ range (f) \) — диапазон функции \ (f \). \ (B \) -значная вселенная является собственно класс \ (V (B) \), который является объединением всех этих \ (V \) s. Следующий определяется довольно сложной трансфинитной рекурсией над обоснованно устанавливает значение теоретико-множественной формулы с элементами булевозначной вселенной, присвоенной его свободным переменным:

\ [\ begin {align *} \ val {x \ in y} & = \ sum_ {t \ in \ dom (y)} \ val {x = t} \ cdot y (t) \\ \ val {x \ substeq y} & = \ prod_ {t \ in \ dom (x)} -x (t) + \ val {t \ in y} \\ \ val {x = y} & = \ val {x \ substeq y} \ cdot \ val {y \ substeq x} \\ \ val {\ neg \ phi} & = — \ val {\ phi} \\ \ val {\ phi \ vee \ psi} & = \ val {\ phi} + \ val {\ psi} \\ \ val {\ exists x \ phi (x)} & = \ sum_ {a \ in V (B)} \ val {\ phi (a)}.4) булевы функции между двумя логическими переменными. Логическая переменная представляет собой единичный источник двоичных данных в цифровой электронике, то есть одиночный бит или последовательный поток битов. Таким образом, в цифровых схемах может быть максимум 16 логических функций. Давайте узнаем обо всех логических операциях.

Рис.1: Репрезентативное изображение всех логических операций

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

.

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

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

F0: Null — Выходное значение false для всех входов логических переменных называется Null. Это эквивалентно двоичной константе 0. Функция эквивалентна логическому выражению F = 0.Соответственно следующим 16 комбинациям возможных исходов, существуют следующие логические операции —

F1: AND — Выходное значение «истина», когда оба входа логических переменных имеют значение «истина», в противном случае выходное значение «ложь» называется операцией «И». Это одна из основных логических операций. В логической алгебре он представлен оператором точка (.). Функция эквивалентна логическому выражению F = xy или F = x.y.

F2: Запрещение — Выход, истинный для одной переменной, истинной, но не для другой, называется запретом.Для функции F2 результат истинен, если x истинно, но не y. В логических алгебраических обозначениях это записывается как x / y. Функция эквивалентна логическому выражению F = xy ’.

F3: Передача — Выходное значение «истина» тогда и только тогда, когда одна из логических переменных имеет значение «истина», называется передачей. Для функции F3 результат истинен при условии, только если x истинно, независимо от y. В булевых алгебраических обозначениях это представляется просто записью x. Функция эквивалентна логическому выражению F = x.

F4: Запрещение — Выход, истинный для одной переменной, истинной, но не истинной для другой, называется запрещением. Функция F4 аналогична функции F2. Для F4 результат истинен, если y истинно, но не x. В логической алгебраической записи это записывается как y / x. Функция эквивалентна логическому выражению F = x’y.

F5: Передача — Выходное значение «истина» тогда и только тогда, когда одна из логических переменных имеет значение «истина», называется передачей. Функция F5 аналогична функции F3.Для F5 результат истинен при условии, только если y истинно независимо от x. В булевых алгебраических обозначениях это обозначается просто буквой y. Функция эквивалентна логическому выражению F = y.

F6: Исключающее ИЛИ — Выходное значение истинно только тогда, когда одна из логических переменных истинна, но не другая, называется Исключающее ИЛИ. Для этой функции результат истинен, если x или y истинны, но не оба одновременно. В булевой алгебре операция EX-OR представлена ​​оператором.Функция эквивалентна логическому выражению F = xy ‘+ x’y.

F7: OR — Выходное значение «истина», если одна или обе логические переменные истинны, называется операцией ИЛИ. Это одна из основных логических операций. Он представлен оператором Плюс (+) в булевой алгебре. Функция эквивалентна логическому выражению F = x + y.

F8: NOR — Операция, обратная OR, называется NOR. Его результат верен только тогда, когда обе переменные ложны.В булевой алгебре он представлен стрелкой вниз. Он записывается как. Функция эквивалентна логическому выражению F = (x + y) ’.

F9: Эквивалентность — Выходное значение «истина», только если обе переменные либо истинны, либо обе ложны, называется эквивалентностью. Это инверсия EX-OR, поэтому также называется Exclusive NOR (EX-NOR). В булевой алгебре он представлен как (xy) ’. Функция эквивалентна логическому выражению F = xy + x’y ‘.

F10: Дополнение — В функции F10 вывод является дополнением к одной из логических переменных.Результат истинен, если y ложно, независимо от x. В булевой алгебре он представлен как НЕ из Y. Он записывается как y ’. Функция эквивалентна логическому выражению F = y ’.

F11: Импликация — Выходное значение «истина», если одна из логических переменных имеет значение «ложь» или другое значение «истина», называется импликацией. В функции F11 вывод истинен, если либо y ложно, либо x истинно. В булевой алгебре он представлен как x y. Функция эквивалентна логическому выражению F = x + y ’.

F12: Дополнение — В функции F12 вывод является дополнением к одной из булевых переменных. Результат истинен, если x ложно, независимо от y. В булевой алгебре он представлен как НЕ x. Он записывается как x ’. Функция эквивалентна логическому выражению F = x ’.

F13: Импликация — Выходное значение «истина», если одна из логических переменных имеет значение «ложь» или другое значение «истина», называется импликацией. В функции F13 вывод истинен, если либо x ложно, либо y истинно.В булевой алгебре он представлен как y x. Функция эквивалентна логическому выражению F = x ’+ y.

F14: NAND — Операция, обратная AND, называется NAND. Это одна из основных логических операций. Результатом NAND является ложь, если обе логические переменные истинны, в противном случае — истина. В булевой алгебре он представлен стрелкой вверх (). Он записывается как x y. Функция эквивалентна логическому выражению F = (xy) ’.

F15: Идентичность — Выход, истинный для всех входов логических переменных, называется Идентификацией.Это эквивалентно двоичной константе 1. Функция эквивалентна логическому выражению F = 1.

Все возможные логические операции между двумя логическими переменными сведены в следующую таблицу —

Рис. 3: Таблица, в которой перечислены все логические функции с двумя переменными

Итак, основные логические операции — И, ИЛИ, НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ, ИСКЛЮЧИТЕЛЬНОЕ ИЛИ, НЕ-ИЛИ, ИЛИ-НЕ вместе с операциями буфера, запрета, импликации, нулевого значения и идентичности являются единственными логическими (логическими) операциями.Операции дополнения и передачи — это унарные операции, которые работают с одним операндом.

В предыдущем руководстве логическое выражение было минимизировано с помощью таблицы истинности. Но это не стандартный или систематический способ минимизировать логическое выражение. В следующем руководстве вы узнаете о минимизации уровня шлюза, которая включает важные методы сопоставления для упрощения логического выражения. Методы K-Map, VEM и QM являются важными методами минимизации уровня логических элементов, которые должны быть известны для реализации логических выражений на уровне элементов управления и, следовательно, для цифровых схем.После того, как станут известны методы минимизации уровня затвора, можно разработать практические цифровые схемы. Итак, основные логические операции — AND, OR, NOT, XOR, XNOR, NAND, NOR вместе с буфером, запретом, импликацией, нулевыми и идентификационными операциями являются единственными логическими (логическими) операциями. Операции дополнения и передачи — это унарные операции, которые работают с одним операндом.

Учебное пособие по таблице истинности логической алгебры

— объяснение XOR, NOR и логических символов

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

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

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

Что такое булева алгебра?

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

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

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

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

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

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

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

На изображении ниже показан весь набор вещественных чисел. Набор действительных чисел включает натуральные числа (1, 2, 3, 4 . …), целые числа (все натуральные числа и 0), целые числа (…..- 2, -1, 0, 1, 2, 3 …) и так далее. Обычная алгебра занимается всем этим набором чисел.

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

Например, в информатике мы чаще всего представляем эти значения, используя 0 и 1. 0 используется для False и 1 для True.

Вы также можете сделать это более изящными способами, представив значения истинности некоторыми другими символами, такими как Кошки и Собаки или Бананы и Апельсины.

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

Теперь вопрос в том, что если (Истина и Ложь), (0 и 1) — это просто представления, то что они пытаются представить?

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

Предложение — это просто утверждение вроде «Все кошки милые».

Если вышеприведенное утверждение верно, то мы присваиваем ему значение истинности «Истина» или «1», в противном случае мы присваиваем ему «Ложь» или «0».

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

Логические операции и таблицы истинности

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

Булева алгебра состоит из трех основных операций.

ИЛИ : Также известна как Дизъюнкция . Эта операция выполняется с двумя логическими переменными.Результатом операции ИЛИ будет 0, когда оба операнда равны 0, в противном случае — 1.

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

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

ИЛИ Операция

Переменная-1 Переменная-2 Выход
  0 0 0
  0 1 1
  1 0 1
  1 1 1  

И : Также известна как Соединение .Эта операция выполняется с двумя логическими переменными. Результатом операции И будет 1, когда оба операнда равны 1, в противном случае — 0. Таблица истинности представлена ​​следующим образом.

  И Работа

Переменная-1 Переменная-2 Выход
  0 0 0
  0 1 0
  1 0 0
  1 1 1  

НЕ : Также известно как Отрицание . Эта операция выполняется только с одной переменной. Если значение переменной равно 1, эта операция просто преобразует его в 0, а если значение переменной равно 0, то оно преобразует его в 1.

  Не работает

Выход переменной-1
  0 1
  1 0  

Булева алгебра и цифровые схемы

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

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

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

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

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

И-НЕ : вентиль И-НЕ образован комбинацией вентилей НЕ и И. Логический элемент И-НЕ дает на выходе 0, если оба входа равны 1, иначе 1.

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

  NAND Gate

Переменная-1 Переменная-2 Выход
  0 0 1
  0 1 1
  1 0 1
  1 1 0  

NOR : ворота NOR формируются комбинацией элементов NOT и OR.Логический элемент ИЛИ-НЕ дает на выходе 1, если оба входа равны 0, в противном случае — 0.

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

  NOR Ворота

Переменная-1 Переменная-2 Выход
  0 0 1
  0 1 0
  1 0 0
  1 1 0  

Большинство цифровых схем построено с использованием логических элементов И-НЕ или ИЛИ-ИЛИ из-за их функциональной полноты, а также из-за того, что их легко изготовить.

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

XOR : вентиль XOR или вентиль Exclusive-OR — это особый тип логического элемента, который дает 0 на выходе, если оба входа равны 0 или 1, в противном случае он дает 1.

  XOR Ворота

Переменная-1 Переменная-2 Выход
  0 0 0
  0 1 1
  1 0 1
  1 1 0  

XNOR : вентиль XNOR или вентиль Exclusive-NOR — это особый тип логического элемента, который дает 1 на выходе, когда оба входа равны 0 или 1, в противном случае он дает 0.

  XNOR ворота

Переменная-1 Переменная-2 Выход
  0 0 1
  0 1 0
  1 0 0
  1 1 1  

Заключение

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

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

Булева алгебра — обзор

Теорема A.7

Всякая булева алгебра изоморфна алгебре множеств .

Булевы алгебры связаны с линейными порядками. Если A является линейным порядком, то мы формируем соответствующую алгебру интервалов I ( A ). Предполагая, что A имеет первый элемент, это алгебра наборов, генерируемых полуоткрытыми интервалами [ a, b ), где b — это либо элемент, либо ∞. Если A не имеет первого элемента, мы складываем интервалы (−∞, b ).

Пусть A = ( A , ∨, ∧, ′, 0, 1) булева алгебра. У нас есть отношение x y , определенное атомарной формулой x y = x . Атом — это элемент b , такой что для всех x b либо x = 0, либо x = b . Например, в алгебре интервалов упорядочения типа ω интервалы вида [ n, n + 1) являются атомами.Булева алгебра — это без атомов , если в ней нет атомов. Мы получаем безатомную булеву алгебру, образуя I (η), где η — порядковый тип рациональных чисел. Элемент b является атомарным , если для всех x b , таких что x ≠ 0, существует атом y x . Так, например, в интервальной алгебре упорядочения типа ω + η атомарными элементами являются те, которые не содержат плотных подинтервалов.

Для любой булевой алгебры A мы можем определить последовательность отношений конгруэнтности с соответствующими структурными факторами.Пусть x 0 y , если x = y , пусть x α + 1 y , если соответствующие элементы A / ∼α отличаются конечным числом атомов, а для предельного ординала α пусть x α y , если x β y для некоторого β <α. Мы определяем понятие α-атома по индукции, говоря, что x является 0-атомом, если это атом, и для a > 0, x является α-атомом, если x не может быть выражается как конечное соединение β-атомов при β <α, но для всех y в этой форме могут быть выражены либо x y , либо x y ′ .

Булева алгебра A — это суператомная алгебра , если существует a такой, что A / ∼α является тривиальной (т.е. это одноэлементная булева алгебра).

Булева алгебра — статья энциклопедии

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

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

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

История

Булева алгебра была введена в 1854 году Джорджем Булем в его книге Исследование законов мысли . [2] Эта алгебра была показана в 1938 году Клодом Шенноном как полезная при разработке логических схем. [3]

Аксиомы

Операции булевой алгебры, а именно две бинарные операции на множестве A с именами AND (умножение, •) и OR (сложение, +), и одна унарная операция NOT (отрицание, ~ ), дополнены двумя выделенными элементами, а именно 0 (называется ноль ) и 1 (называется один ), которые удовлетворяют следующим аксиомам для любых подмножеств p , q , r набора A :

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

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

Однако это выражение эквивалентно в рамках приведенных выше булевых аксиом. Согласно другим аксиомам, p · p = p . Кроме того, p · r + q · p = p · (q + r). Этот набор находится в пределах p , поэтому интуитивно p + p · (q + r) = p. Используя булевы аксиомы вместо интуиции, p + p · (q + r) = p · (1 + q + r) и согласно свойствам ‘ 1 ‘, (1 + q + r) = 1.Таким образом, элементарный алгебраический результат при интерпретации в терминах булевых аксиом сводится к булеву закону распределения.

Альтернативные обозначения

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

&& &

Диаграммы Венна

(PD) Изображение: John R. Brews
Интерпретация булевых операций с использованием диаграмм Венна.
Для получения дополнительной информации см .: Диаграмма Венна .

Диаграммы Венна обеспечивают графическую визуализацию булевых операций. [4] Пересечение двух наборов A∩B играет роль операции AND , а объединение двух наборов A∪B представляет функцию OR , как показано серым заштрихованные участки на рисунке. Чтобы представить операцию НЕ , универсальный набор представлен прямоугольником, поэтому ~ A — это набор всего, что не входит в A , что соответствует серой части прямоугольника на третьей панели слева.

Эти диаграммы также обеспечивают визуализацию булевых аксиом. Например, изображение ~ (A∩B) легко увидеть как то же самое, что и (~ A) ∪ (~ B) , как того требует аксиома Де Моргана.

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

Таблица истинности для логического предложения — это формальный способ определить, является ли вывод действительным или недействительным, где «0» соответствует «недействительному», а «1» — «действительному». В контексте булевой алгебры внимание сосредоточено на булевых функциях , обозначенных f (A, B, C) , где переменные A, B, C и функция f являются допустимыми значениями ‘1’ или ‘ 0 ‘в зависимости от того, действительны или недействительны утверждения, которым они соответствуют.Таблица истинности для f — это просто таблица значений f для всех возможных значений A, B, C . Например, предположим:

Соответствующая таблица истинности находится ниже слева:

(PD) Изображение: Джон Р. Брюс
Диаграмма Венна для f = ~ A + B · C .
f = ~ A + B · C
А B С f = ~ A + B · C
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1

Таблица истинности может быть установлена ​​в соответствии с диаграммой Венна, как показано справа. Запись «0» таблицы истинности в столбце A интерпретируется как набор точек , а не в A , тогда как запись «1» используется для ссылки на точки, содержащиеся в A . На схеме обозначение Ā для ~ A используется для сохранения компактности маркировки, а знак «·» для пересечения опущен. Метки обозначают области с границами, окружающими метку, поэтому метка ABC обозначает область, общую для всех трех наборов A , B и C .Цветная область охватывает все точки, соответствующие f = 1 , то есть все точки в области ~ A + B · C , а белое пространство соответствует областям за пределами этой области.

Фактически, A , B , C — это утверждения:

  • A: точка p находится в наборе A
  • B: точка p находится в наборе B
  • C: точка p находится в наборе C

и предложение f :

  • f: точка p является общей для наборов B и C или отсутствует в наборе A .

Таблица истинности и диаграмма Венна определяют действительность f для всех вариантов достоверности A , B и C .

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

  • A: Набор умных людей
  • B: Набор политиков
  • C: Множество мошенников

Тогда, если бы Билл был умен и кривым политиком (A · B · C), он попал бы в группу f :

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

Расширение логики

Вышеупомянутое обсуждение обрисовывает в общих чертах метод описания различных наборов и их подмножеств, а также предоставляет формальную систему для принятия решения о том, когда различные описания подмножества эквивалентны. Применение этой системы к анализу логических аргументов требует связи с такими конструкциями, как «если A , то B », иногда называемые условными выражениями . Если предположить, что утверждения A, и B являются либо истинным, «1», либо ложным «0», условное «подразумевает», обозначенное «→», может быть определено таблицей истинности:

А → В
А B А → В
0 0 1
0 1 1
1 0 0
1 1 1

Другими словами, A → B ложно тогда и только тогда, когда A истинно, а B ложно.Эта таблица истинности такая же, как ~ A + B . В качестве примера можно взять:

  • A: Мяч подброшен.
  • B: Собака бежит.

Тогда A → B означает, что собака всегда бежит, когда мяч подброшен, но собака может бегать и в противном случае, или нет.

«Эквивалентность» с двумя условными условиями , обозначенная как «», может быть определена с помощью таблицы истинности:

A ↔ B
А B A ↔ B
0 0 1
0 1 0
1 0 0
1 1 1

Таким образом, A ↔ B имеет ту же таблицу истинности, что и (A → B) • (B → A) .В качестве примера можно взять:

  • A: Переключатель замкнут.
  • B: Свет горит.

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

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

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

Список литературы

  1. Эллиотт Мендельсон (1970). «Глава 1: Алгебра логики», Схема булевой алгебры и коммутационных схем Шаума . Макгроу-Хилл. ISBN 0070414602.
  2. Джордж Буль (1854 г.). Исследование законов мышления, на которых основаны математические теории логики и вероятностей . Macmillan and Co . .
  3. ↑ Например, см. Джонатан Стерн (2003). «Шеннон, Клод (1916-2001)», Стив Джонс, изд: Энциклопедия новых медиа: важная ссылка на коммуникацию и технологии .Публикации SAGE, стр. 406. ISBN 0761923829.
  4. ↑ Для обсуждения см. J. Eldon Whitesitt (1995). «§1–4: диаграммы Венна», Булева алгебра и ее приложения , Републикация Эддисона-Уэсли, 1961 изд. Courier Dover Publications, pp. 5 ff . ISBN 0486684830.

математических единиц за минуту: логическая алгебра

A B A AND B
Истина Истина Истина
Истина Ложь Ложь
Ложь Ложь Ложь Ложь Ложь
Ложь Ложь Ложь

Простая таблица истинности, показывающая все
возможных значений « A И B ».

Каждый раз, когда вы используете компьютер, вы полагаетесь на булеву логику : систему логики, созданную задолго до появления компьютеров, названную в честь английского математика Джорджа Буля (1815–1864). В логической логике утверждения могут быть либо истинными, либо ложными (например, в данный момент «я хочу чашку чая» ложно, но «я хочу кусок торта» всегда верно), и вы можете связать их вместе, используя слова И , ИЛИ и НЕ. Чтобы установить, являются ли эти составные утверждения истинными или ложными, вы можете создать так называемую таблицу истинности , в которой перечислены все возможные значения, которые могут принимать базовые операторы, а затем все соответствующие значения, которые может принимать составной оператор.(Вы можете узнать больше в математике через минуту: таблицы истинности.)

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

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

0 + 0 = 0 (поскольку «ложь ИЛИ ложь» — ложь)
1 + 0 = 0 + 1 = 1 (поскольку «истина ИЛИ ложь» и «ложь ИЛИ истина» оба истинны)
1 + 1 = 1 (поскольку «истина ИЛИ истина» верно).

Мы можем переписать AND как своего рода умножение:

0 x 1 = 1 x 0 = 0 (поскольку «ложь И истина» и «истина И ложь» оба ложны)
0 x 0 = 0 (поскольку «ложь И ложь» — ложь)
1 x 1 = 1 (поскольку «правда И правда» верно).

Поскольку переменные могут иметь только значения 0 и 1, мы можем определить операцию НЕ как дополнение, взяв число, противоположное ее значению:

Если A = 1, то НЕ A = 0
Если A = 0, то НЕ A = 1
A + НЕ A = 1 (поскольку «истина ИЛИ ложь» истинна)
A x НЕ A = 0 (поскольку «истина И ложь» — ложь).

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

A + A x B

не имеет значения, независимо от того, какое значение имеет B или какое логическое утверждение оно представляет. Это потому, что если A истинно (или, что эквивалентно A = 1), то A OR ( A И B ) истинно независимо от того, истинно ли утверждение B . И если A ложно (то есть A = 0), то ( A AND B ) ложно независимо от значения B , и поэтому A OR ( A AND B ) ложно. Итак, булева алгебра предоставляет нам исчезающий акт: выражение A + A x B равно простому маленькому A :

A + A x B = A .

Кроме того, в булевой алгебре существует своего рода обратная двойственность между сложением и умножением:

( A + B ) ‘= A ‘ x B ‘и ( A x B )’ = A ‘+ B ‘.

Эти два равенства известны как Законы Де Моргана в честь британского математика Августа де Моргана (1806–1871). (Вы можете убедиться, что они верны, используя эквивалентные таблицы истинности.)

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

Алгебра переключений или булева алгебра

Булева алгебра или алгебра переключений — это система математической логики для выполнения различных математических операций в двоичной системе.Это всего лишь два элемента 1 и 0, с помощью которых должны выполняться все математические операции. Есть только три базовых двоичных операции: И, ИЛИ и НЕ, с помощью которых должны выполняться как простые, так и сложные двоичные математические операции. В булевой алгебре существует множество правил, по которым выполняются эти математические операции.
В булевой алгебре переменные представлены английскими заглавными буквами, например A, B, C и т. Д., И значение каждой переменной может быть либо 1, либо 0, ничего больше.

Некоторые базовые логические логические операции —
операция И,

операция ИЛИ,

Не операция,

Некоторые основные законы булевой алгебры,

A.0 = 0, где A может быть 0 или 1.
A. 1 = A, где A может быть 0 или 1.
A. A = A, где A может быть 0 или 1.
A. Ā = 0, где A может быть 0 или 1.
A + 0 = A, где A может быть 0 или 1.
A + 1 = 1, где A может быть либо 0, либо 1.
A + Ā = 1
A + A = A
A + B = B + A, где A и B могут быть 0 или 1.
A. В = В. A, где A и B могут быть 0 или 1.
Законы булевой алгебры также верны для более чем двух переменных, например,

Кумулятивные законы для булевой алгебры

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

Распределительные законы для логической алгебры

Избыточное буквенное правило


Из таблицы истинности,

900 057 A + ĀB
Входы Выход
A B ĀB
0 0
0 1 1 1
1 0 0 1
1 1 0 1
Входы Выход
A B A + B
0 0 0
0 1 1
1 0 1
1 1 1

Из таблицы истинности доказано, что ,

Законы поглощения для булевой алгебры


Доказательство по таблице истинности,

Входные данные Выходные данные
A B AB A + A. B
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 1

Столбцы A и A + AB одинаковы.

Доказательство из таблицы истинности,

A B A + B AX (A + B)
0 0 0 0
0 1 1 0
1 0 1 1
1 1 1 1

И A, и A.Столбцы X или A (A + B) совпадают.

Терем Де Моргана,

Доказательство из таблицы истинности,

Примеры булевой алгебры



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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *