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

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

☰

Алгебра логики (булева алгебра) – это раздел математики, возникший в XIX веке благодаря усилиям английского математика Дж. Буля. Поначалу булева алгебра не имела никакого практического значения.

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

Хотя это не единственная сфера применения данной науки.

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

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

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

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

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

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

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

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

Такими операциями являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ).

Часто конъюнкцию обозначают &, дизъюнкцию — ||, а отрицание — чертой над переменной, обозначающей высказывание.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник: https://inf1.info/logic

Булевы функции и формулы

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

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

Есть трудности с задачами? МатБюро поможет вам: дискретная математика на заказсдача дистанционных тестов.

Лучшее спасибо — порекомендовать эту страницу

Задача 1. Проверить, является ли тавтологией формула: $a \& b \to(a \& b \vee c \vee \bar c)$

Решение задачи о проверке формулы

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

$$(\overline {x_1} \vee x_2) \to (\overline {x_1}\sim x_3)\overline {x_3} $$ Преобразование булевой формулы к виду без скобок

Задача 3. Показать, что $x_1$ — фиктивная переменная функции $f$ (реализовав для этой цели функцию $f$ формулой, не содержащей явно переменную $x_1$).

Решение задачи о фиктивной переменной

Задача 4. Используя приведенные ниже (основные) эквивалентности и соотношения, доказать эквивалентность формул $U$ и $B$.

Решение задачи об эквивалентности формул

Задача 5. Классифицировать формулу $\overline{ (\overline{xy}\to x) \vee y}$

Решение о классификации булевой формулы
Решим задания по булевым формулам на заказ

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

Булевой алгеброй называется непустое множество $A$ с двумя бинарными операциями $\land$ (аналог конъюнкции), $\lor $ (аналог дизъюнкции), одной унарной операцией $\lnot$ (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для любых a, b и c из множества A верны следующие аксиомы:

Логические операции

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

Основные формулы по алгебре логики: функции алгебры логики, таблица истинности, основные эквивалентности, преобразование к конъюнкции, дизъюнкции и отрицанию

Приоритет логических операций

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

$$ eg \quad \wedge \quad \vee \quad \to \quad \leftrightarrow $$

Словесно: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.

Бесплатные решения задач по дискретной математике

Источник: https://www.matburo.ru/ex_dm.php?p1=dmbul

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

На этом уроке знакомимся с алгеброй логики (булевой алгеброй). Одним из её основателей стал английский математик Джордж Буль (1815-1864), который был из довольно бедной семьи, а в юности зарабатывал переводами сочинений древнегреческих философов. За этим занятием его и посетила мысль о том, что высказываниям можно присваивать значения 1 («истина») и 0 «ложь».

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

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

Пусть функция от n переменных и любой из её аргументов могут принимать значения только из множества {0, 1}. Тогда эта функция называется логической, или булевой, или переключательной, или функцией алгебры логики. Описанную функцию часто называют также булевым вектором. Количество функций от n переменных равно 2 в степени n. То же самое можно сказать и иначе: число различных n-мерных булевых векторов равно 2 в степени n. А число различных функций алгебры логики от этих векторов равно уже .

Значениям переменной в булевой алгебре соответствуют состояниям элементов микросхем компьютера или любого другого электронного устройства: сигнал присутствует (логическая «1») или сигнал отсутствует (логический «0»).

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

Законы булевой алгебры применяются и в программировании — при написании сложных логических условий и сложных запросов к базе данных. Один пример со скриптом на PHP приведён здесь (это статья о системе многокритериального поиска по сайту с базой данных). Ещё один пример — применение алгебры логики в создании многоуровневого меню сайта, в котором были бы открыты все пункты всех уровней, по которому пролегает путь к конечному открытому пункту меню.

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

Функция	Название	Обозначение
Константа нуля
Повторение x
Логическое отрицание, инверсия, «НЕ»
Константа единицы

Переменная	Логические функции
x
			1	1
1		1		1

Нет времени вникать в решение? Можно заказать работу!

Логические функции двух переменных

Функция	Название	Обозначение
Константа нуля	или False
Логическое умножение, конъюнкция, «И»	или или или
Запрет по	или
Переменная
Запрет по	или
Переменная
Сложение по модулю 2, отрицание эквивалентности, исключающее «ИЛИ»	или или
Логическое сложение, дизъюнкция, «ИЛИ»	или или или
Функция Пирса (Вебба), «ИЛИ-НЕ»	или или
Логическая равнозначность, эквиваленция	или или или
Отрицание
Правая импликация	или
Отрицание
Левая импликация	или
Функция Шеффера, «И-НЕ»	или или
Константа единицы	или True

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

X1			1	1
X2		1		1
			1
		1
		1	1
	1
	1		1
	1	1
	1	1	1
1
1			1
1		1
1		1	1
1	1
1	1		1
1	1	1
1	1	1	1

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

Ответить на контрольные вопросы, а затем посмотреть ответы

Контрольный вопрос 1. Даны две переменные x1 и x2. Число различных булевых векторов и различных ФАЛ от полученных векторов равны соответственно:

• 8 и 16
• 8 и 32
• 4 и 8
• 4 и 16

Контрольный вопрос 2. Какие из функций не являются ФАЛ одной переменной (и одна, и вторая в варианте ответа):

• отрицание и сложение по модулю два
• эквивалентность и повторение x
• отрицание и импликация
• функция Шеффера и эквивалентность
• запрет по x2 и отрицание

Правильные ответы на вопрос 1 и вопрос 2.

Нет времени вникать в решение? Можно заказать работу! Пройти тест по теме Математическая логика

Булев базис (логический базис)

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

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

.

	1
1

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

.

	1
1
1	1	1

Дизъюнкция (логическое сложение, «ИЛИ»)

.

	1	1
1		1
1	1	1

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

Аналитическое представление логических функций

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

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

Первая форма записи имеет название дизъюнктивной нормальной формы (ДНФ), вторая — конъюнктивной нормальной формы (КНФ). В этих названиях термин «нормальная» означает отсутствие общей инверсии (отрицания) над несколькими перемнными сразу.

Дизъюнктивная нормальная форма

.

Конъюнктивная нормальная форма

.

Способы описания логических функций

Применяются следующие способы описания логических функций:

• словесный;
• табличный;
• числовой;
• аналитический;
• координатный;
• графический.

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

Номер набора	f
1	1
2
3
4	1
5	1
6
7	1

X1	X2	X3	f
		1	1
	1
	1	1
1			1
1		1	1
1	1
1	1	1	1

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

Пример числового описания логических функций

или .

Пример аналитического описания логических функций

Пример координатного описания логических функций

Карта Карно

Пример графического описания логических функций

Аксиомы алгебры логики

Аксиомы конъюнкции

.

Аксиомы дизъюнкции

.

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

если , то ; если , то .

Теоремы алгебры логики

Теоремы исключения констант

.

Теоремы идемпотентности (тавтологии, повторения)

.

для n переменных

.

Теорема противоречия

.

Теорема «исключённого третьего»

.

Теорема двойного отрицания (инволюции)

.

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

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

.

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

.

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

.

.

Законы де Моргана (законы общей инверсии или дуальности)

.

.

Закон поглощения (элиминации)

.

Закон склеивания (исключения)

.

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

Источник: https://function-x.ru/buleva_algebra.html

Логические функции алгебры логики: схемы и таблицы истинности

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

Введение в булевую алгебру

В 1854 году Джордж Буль провел исследование «законов мышления», которые основывались на упрощенной версии теории «групп» или «множеств», и из этого была выведена булевая алгебра.

Булева алгебра имеет дело, главным образом, с теорией, согласно которой логические операции и операции над множествами являются либо «ИСТИННЫМИ», либо «ЛОЖНЫМИ», но не обеими одновременно.

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

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

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

Функция «И» представлена в электронике символом точки или полной остановки ( . ) Таким образом, 2-входное ( АВ ) «И» элемент имеет выходной термин, представленный логическим выражением A.B или просто AB.

Представление функции «И» на схеме

Здесь два переключателя A и B соединены вместе, образуя последовательную цепь. Поэтому в вышеупомянутой цепи оба выключателя A «И» B должны быть замкнуты (логика «1»), чтобы включить лампу. Другими словами, оба переключателя должны быть замкнуты или должны иметь логическую «1», чтобы лампа горела.

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

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

Таблица истинности для функции «И»

Логические «И» элементы доступны как стандартные пакеты ic, такие как общие TTL 74LS08 Четырехпозиционные 2-входные положительные элементы «И» (или эквивалент CMOS 4081), TTL 74LS11 Тройные 3-входные положительные элементы «И» или 74LS21 Двойные 4-входные положительные элементы «И». «И» ворота можно также «каскадировать» вместе для создания цепей с более чем 4 входами.

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

Функция логического «ИЛИ» заявляет, что выходное действие станет ИСТИНОЙ, если одно «ИЛИ» больше событий ИСТИНЫ, но порядок, в котором они происходят, не имеет значения, поскольку он не влияет на конечный результат.

Так , например, А + В = В + А . В булевой алгебре функция логического «ИЛИ» подчиняется коммутативному закону так же, как и для логической функции «И», что позволяет изменять положение любой переменной.

Логика или логическое выражение, данное для логического элемента «ИЛИ», является логическим выражением, которое обозначается знаком плюс, ( + ). Таким образом, 2-входной ( АВ ) Логический элемент «ИЛИ» имеет выход термин, представленный булевой выражением:  A + B = Q .

Представление функции «ИЛИ» на схеме

Здесь два переключателя А и B соединены параллельно и, либо переключатель A «ИЛИ» переключатель B может быть закрыт, чтобы включить лампу. Другими словами, выключатель может быть замкнут, либо быть на логике «1», чтобы лампа была включена.

Тогда этот тип логического элемента генерирует и выводит только тогда, когда присутствует «ЛЮБОЙ» из его входов, и в терминах Булевой алгебры выход будет ИСТИНА, если любой из его входов ИСТИНЕН. В электрическом смысле логическая функция «ИЛИ» равна параллельной цепи.

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

Таблица истинности для функции «ИЛИ»

Логические «ИЛИ» элементы доступны в виде стандартных пакетов ic, таких как общие TTL 74LS32 Четырехместные 2-входные положительные «ИЛИ» элементы. Как и в предыдущем логическом элементе «И», «ИЛИ» также может быть «каскадно» соединен для создания цепей с большим количеством входов, таких как системы охранной сигнализации (зона A или зона B или зона C и т.д.).

Логическая функция «НЕ» (отрицание)

Функция «Логическое НЕ» — это просто инвертор с одним входом, который изменяет вход логического уровня «1» на выход логического уровня «0» и наоборот.

«Функция логического НЕ» называется так, потому что ее выходное состояние НЕсовпадает с его входным состоянием с ее логическим выражением, обычно обозначаемым чертой или линией ( ¯ ) над его входным символом, который обозначает операцию инвертирования (отсюда ее название как инвертор).

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

Представление функции «НЕ» на схеме

Если A означает, что переключатель замкнут, то «НЕ» A или А (с верхней чертой) говорит, что переключатель НЕ замкнут или, другими словами, он разомкнут. Функция логического НЕ имеет один вход и один выход, как показано на рисунке.

Таблица истинности для функции «НЕ»

Индикатор инверсии для логической функции «НЕ» является символом «пузыря», ( O) на выходе (или входе) символа логических элементов. В булевой алгебре инвертирующая логическая функция «НЕ» следует Закону дополнения, создающему инверсию.

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

При проектировании логических схем вам может понадобиться только один или два инвертора в вашей конструкции, но если у вас нет места или денег для выделенного чипа инвертора, такого как 74LS04. Тогда вы можете легко заставить логику «НЕ» функционировать, используя любые запасные элементы «НЕ А» или «НЕ ИЛИ», просто соединяя их входы вместе, как показано ниже.

Логическая функция «НЕ И»

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

Функция логического «НЕ И» генерирует выход, только когда «ЛЮБЫЕ» из ее входов отсутствуют, и в терминах булевой алгебры выход будет ИСТИНА, только когда любой из ее входов ЛОЖЬ (0).

Представление функции «НЕ И» на схеме

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

Таблица истинности для функции «НЕ И»

Функция «НЕ И» обозначается вертикальной чертой или стрелкой вверх, например, логический B = A | Bили A B .

Логика «НЕ И» используется в качестве основных «строительных блоков», чтобы построить другие функции логического элемента и доступны в стандартных IC пакетов, такие как общий TTL — 74LS00 Четырехместный 2-входной «НЕ И» элемент, TTL — 74LS10 Тройной 3-входной «НЕ И» элемент или 74LS20 Двойной 4-х входной «НЕ И» элемент. Есть даже один чип 74LS30 с 8 входами «НЕ И» элемента.

Логическая функция «НЕ ИЛИ»

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

Чтобы создать вентиль «НЕ ИЛИ», функция «ИЛИ» и функция «НЕ» соединены вместе последовательно, и ее операция определяется булевым выражением как, A + B (с верхней чертой).

Функция логического «НЕ ИЛИ» генерирует и выводит только тогда, когда отсутствуют «ВСЕ» ее входы, и в терминах булевой алгебры выход будет ИСТИНА только тогда, когда все ее входы ЛОЖНЫ .

Представление функции «НЕ ИЛИ» на схеме

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

Таблица истинности для функции «НЕ ИЛИ»

Функция «НЕ ИЛИ» иногда известна как функция Пирса и обозначается стрелкой вниз, А «НЕ ИЛИ» B = A ↓ B.

Логика элемента «НЕ ИЛИ» доступны как стандартные IC пакетов, таких как TTL 74LS02 Четырехместный 2-входной элемент «НЕ ИЛИ», TTL 74LS27 Тройной 3-входной элемент «НЕ ИЛИ» или 74LS260 Двойной 5-входной элемент «НЕ ИЛИ».

Источник: https://meanders.ru/logicheskie-funkcii-bulevoj-algebry-shemy-tablicy-istinnosti.shtml

Цифровые схемы — булева алгебра

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

Диапазон напряжений, соответствующий логике «Высокий», обозначен «1», а диапазон напряжений, соответствующий логике «Низкий», представлен «0».

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

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

Булевы Постулаты

Рассмотрим двоичные числа 0 и 1, булеву переменную (x) и ее дополнение (x ‘). Булева переменная или ее дополнение называется литералом . Четыре возможных логических операции ИЛИ среди этих литералов и двоичных чисел показаны ниже.

х + 0 = х

х + 1 = 1

х + х = х

х + х ‘= 1

Точно так же четыре возможные логические операции И среди этих литералов и двоичных чисел показаны ниже.

х.1 = х

х.0 = 0

хх = х

x.x ‘= 0

Это простые булевы постулаты. Мы можем легко проверить эти постулаты, заменив логическую переменную на «0» или «1».

Примечание . Дополнение к любой булевой переменной равно самой переменной. т.е. (x ‘)’ = x.

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

Ниже приведены три основных закона булевой алгебры.

• Коммутативное право
• Ассоциативный закон
• Распределительное право

Коммутативное право

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

х + у = у + х

xy = yx

Символ «+» указывает на логическую операцию ИЛИ. Точно так же символ «.» указывает логическую операцию И, и это необязательно для представления. Коммутативное право подчиняется логическому ИЛИ, логическому И операциям.

Ассоциативное право

Если сначала выполняется логическая операция любых двух логических переменных, а затем выполняется та же самая операция с оставшейся переменной, которая дает тот же результат, то эта логическая операция называется ассоциативной . Логические операции ИЛИ, логические И трех булевых переменных x, y & z показаны ниже.

x + (y + z) = (x + y) + z

x. (yz) = (xy) .z

Ассоциативный закон подчиняется логическому ИЛИ и логическому И операциям.

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

Если какая-либо логическая операция может быть распространена на все члены, присутствующие в булевой функции, то эта логическая операция называется распределительной . Распределение логических ИЛИ и логических И операций трех булевых переменных x, y & z показано ниже.

х. (у + г) = ху + хз

x + (yz) = (x + y). (x + z)

Распределительный закон подчиняется логическому ИЛИ и логическому И операциям.

Это основные законы булевой алгебры. Мы можем легко проверить эти законы, заменив логические переменные на «0» или «1».

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

Следующие две теоремы используются в булевой алгебре.

• Теорема двойственности
• Теорема Деморгана

Теорема двойственности

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

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

Группа 1 Group2

х + 0 = х	х.1 = х
х + 1 = 1	х.0 = 0
х + х = х	хх = х
х + х ‘= 1	x.x ‘= 0
х + у = у + х	xy = yx
x + (y + z) = (x + y) + z	x. (yz) = (xy) .z
х. (у + г) = ху + хз	x + (yz) = (x + y). (x + z)

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

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

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

Теорема Деморгана с 2 булевыми переменными x и y может быть представлена ​​в виде

(x + y) ‘= x’.y’

Двойственная из вышеупомянутых булевых функций

(xy) ‘= x’ + y ‘

Следовательно, дополнение логического И двух логических переменных равно логическому ИЛИ каждой дополненной переменной. Точно так же мы можем применить теорему Деморгана для более чем 2 булевых переменных.

Упрощение булевых функций

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

Пример 1

Упростим булеву функцию: f = p’qr + pq’r + pqr ‘+ pqr

Мы можем упростить эту функцию двумя способами.

Способ 1

Для данной булевой функции f = p’qr + pq’r + pqr ‘+ pqr.

Шаг 1 – В первом и втором членах r является общим, а в третьем и четвертом членах pq является общим. Итак, примите общие термины, используя Распределительный закон .

⇒ f = (p’q + pq ‘) r + pq (r’ + r)

Шаг 2 – Термины, представленные в первых скобках, могут быть упрощены до операции Ex-OR. Термины, присутствующие во второй скобке, могут быть упрощены до «1» с использованием булева постулата

⇒ f = (p ⊕q) r + pq (1)

Шаг 3 – Первый термин не может быть упрощен в дальнейшем. Но второй член можно упростить до pq, используя булев постулат .

⇒ f = (p ⊕q) r + pq

Следовательно, упрощенная булева функция имеет вид f = (p⊕q) r + pq

Способ 2

Для данной булевой функции f = p’qr + pq’r + pqr ‘+ pqr.

Шаг 1 – Используйте булев постулат , х + х = х. Это означает, что операция логического ИЛИ с любой логической переменной n раз будет равна той же самой переменной. Итак, мы можем написать последний член pqr еще два раза.

⇒ f = p’qr + pq’r + pqr ‘+ pqr + pqr + pqr

Шаг 2 – Используйте Распределительный закон для 1- го и 4- го терминов, 2- го и 5- го терминов, 3- го и 6- го терминов.

⇒ f = qr (p ‘+ p) + pr (q’ + q) + pq (r ‘+ r)

Шаг 3 – Используйте булев постулат , x + x ‘= 1 для упрощения терминов, присутствующих в каждой скобке.

⇒ f = qr (1) + pr (1) + pq (1)

Шаг 4 – Используйте булев постулат , x.1 = x для упрощения трех указанных выше терминов.

⇒ f = qr + pr + pq

⇒ f = pq + qr + pr

Следовательно, упрощенная булева функция имеет вид f = pq + qr + pr .

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

Пример 2

Найдем дополнение к булевой функции f = p’q + pq ‘.

Дополнением к булевой функции является f ‘= (p’q + pq’) ‘.

Шаг 1 – Используйте теорему Деморгана, (x + y) ‘= x’.y’.

⇒ f ‘= (p’q)’. (Pq ‘)’

Шаг 2 – Используйте теорему Деморгана, (xy) ‘= x’ + y ‘

⇒ f ‘= {(p’) ‘+ q’}. {P ‘+ (q’) ‘}

Шаг 3 – Используйте булев постулат, (x ‘)’ = x.

⇒ f ‘= {p + q’}. {P ‘+ q}

⇒ f ‘= pp’ + pq + p’q ‘+ qq’

Шаг 4 – Используйте булев постулат, хх ‘= 0.

⇒ f = 0 + pq + p’q ‘+ 0

⇒ f = pq + p’q ‘

Следовательно, дополнение к булевой функции p’q + pq ‘равно pq + p’q’ .

Источник: https://coderlessons.com/tutorials/akademicheskii/izuchite-tsifrovye-skhemy/tsifrovye-skhemy-buleva-algebra

Алгебра высказываний (булева алгебра)

Основные понятия

Основное понятие булевой алгебры — выказывание. Под простым высказыванием понимается предложение, о котором можно сказать, истинно оно или ложно (третьего не дано). Высказывания обозначаются латинскими буквами и могут принимать одно из двух значений: ЛОЖЬ (обозначим 0 ) или ИСТИНА (обозначим 3).

Например, содержание высказывания А: «дважды два равно четырем» истинно А = 1, а высказывание В: «три больше пяти» всегда есть ЛОЖЬ. В дальнейшем нас не будет интересовать содержательная часть высказываний, а только их истинность.

Два высказывания А и В называются равносильными, если они имеют одинаковые значения истинности, записывается А = В.

Логические операции

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

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

Это правило можно записать в виде следующей таблицы:

Такая таблица называется таблицей истинности.

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

Примером такой операции может быть следующая: пусть высказывание А состоит в том, что «высота шкафа меньше высоты двери», событие В «ширина шкафа меньше ширины двери», событие С «шкаф можно внести в дверь, если ширина шкафа меньше ширины двери И высота шкафа меньше высоты двери», т.е. данная операция применяется, если два высказывания связываются союзом И.

Таблица истинности этой операции, как следует из определения, имеет вид

Дизъюнкцией (логическим сложением) двух высказываний А и В является новое высказывание С, которое истинно, если истинно хотя бы одно высказывание. Записывается (при этом говорят:

С равно А ИЛИ В). Пример такой операции следующий: пусть высказывание А состоит в том, что «студент может добираться домой на автобусе», событие В «студент может добираться домой на троллейбусе», событие С «студент добрался домой на автобусе ИЛИ троллейбусе», т.е. данная операция применяется, если два высказывания связываются союзом ИЛИ.

Таблица истинности такой операции следующая:

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

Примером такой операции может быть любое рассуждение типа: если произошло событие А, то произойдет событие В, «если идет дождь, то на небе тучи». Очевидно, операция не симметрична, т.е.

из не всегда истинно, в нашем примере «если на небе тучи, то идет дождь» не всегда истинно.

Таблица истинности импликации следующая:

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

Примером такой операции может быть любое высказывание типа: событие А равносильно событию В.

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

Логические Выражения. Порядок логических операций

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

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

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

Зависимости между логическими операциями

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

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

Первая из них — дизъюнктивная нормальная форма (ДНФ), имеет вид , где каждое из составляющих есть конъюнкция простых высказываний и их отрицаний, например:

Вторая- конъюнктивная нормальная форма (КНФ), имеет вид

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

Табличное и алгебраическое задание булевских функций

Задать булевскую функцию можно, определяя ее значения для всех наборов значений аргументов. Каждый аргумент может иметь два значения: 0 и 1, следовательно, n аргументов могут принимать 2n различных наборов. Пусть, например, булевская функция имеет три аргумента: X,, Х2, Х3 Общее число наборов 23 = 8; зададим таблицу истинности функции, указав для каждого набора значение функции.

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

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

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

,

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

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

1.6.2. Элементы теории множеств

Множеством называется любое объединение определенных вполне различимых объектов; их может и не быть вообще. Можно говорить о множестве точек на отрезке [0,1], множестве студентов в группе, множестве снежных дней в июле на экваторе, т.е.

множество образуют любые объекты, объединенные по любому признаку. Объекты, составляющие множество, называются элементами множества. Множество, не имеющее ни одного элемента, называется пустым, оно обозначается 0.

Множество, состоящее из конечного числа элементов, называется конечным, в противном случае — бесконечным.

Задать множество можно перечислением его элементов. Например, множество образованное из п элементов ар а2, , ап, обозначается А = {а,, а2, , ап}; пишется а е А (говорится «элемент а при надлежит множеству А»), если а является элементом множества А, в противном случае

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

Два множества считаются равными, если состоят из одних и тех же элементов; записывается этот факт А = В.

Множество А1 называется подмножеством А (записываете ),

если все элементы множества А, являются элементами А,

Для множеств определены следующие операции: объединение, пересечение, дополнение.

Объединением множеств А и В (записывается ) называется

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

Пересечением множеств А и В (записывается ) называется

множество, состоящее из элементов, принадлежащих как одному, так и второму множеству одновременно.

Дополнением множества А до В называется множество, состоящее из элементов множества В, не принадлежащих А. Дополнение обозначается (рис. 1.7).

Рис. 1.7. Операции надмножествами

16.3, Элементы теории графов

Основные понятия

Граф задается парой множеств: множества Е, называемого множеством вершин, и множества II, называемого множеством ребер. Ребро есть пара, где ,

указывающая, между какими двумя вершинами проведено ребро. Говорят, что ребро инцидентно вершинам е., е. Если порядок ребер не имеет значения, т.е. , то ребро называется неориентированным или просто ребром, если же порядок имеет значение, то ребро называется ориентированным ребром или дугой. Вершина еi. — называется началом дуги, еj. — конец дуги. Граф, содержащий хотя бы одну дугу, называется ориентированным графом или орграфом

Граф называется конечным, если множество Е вершин

конечно.

Граф •, у которого любые две вершины соединены ребром,

называется полным. Если хотя бы две вершины соединены несколькими ребрами, то такой граф называется мультиграфом. Две вершины называются смежными, если они соединены ребром. Число ребер, инцидентных данной вершине е., называется локальной степенью этой вершины p(ei) Число ребер r графа G(Е,U) определяется выражением

, где n — количество вершин в графе. Рассмотрим граф,

изображенный на рис. 1.8.

Рис. 1.8. Ориентированный граф

Множество вершин графа состоит из пяти элементов: Е = {1, 2, 3, 4, 5}, а множество ребер U = {(1, 2), (1, 4), (1, 5), (2, 3), (3, 4), {5, 3)}. Ребро (5, 3) — является ориентированным ребром или дугой. Число ребер в графе определяется по значению локальных степеней для каждой вершины:

Важным в теории графов является понятие части графа G(Е,U), который обозначается

Множества вершин и ребер части графа являются подмножествами вершин и ребер исходного графа

Статьи к прочтению:

• Алгоритм эрли (основные принципы)
• Алгоритмы ассиметричного шифрования

Начала Булевой алгебры

Источник: http://csaa.ru/algebra-vyskazyvanij-buleva-algebra/