Законы булевой алгебры: Булевы = логические функции. Основные законы математической логики = законы Булевой алгебры. Формы представления булевых = логических функций.

Содержание

Булевы = логические функции. Основные законы математической логики = законы Булевой алгебры. Формы представления булевых = логических функций.





Адрес этой страницы (вложенность) в справочнике dpva.ru:  главная страница  / / Техническая информация / / Математический справочник / / Математическая логика. Булева алгебра = алгебра логики.  / / Булевы = логические функции. Основные законы математической логики = законы Булевой алгебры. Формы представления булевых = логических функций.

Поделиться:   

Булевы = логические функции. Основные законы математической логики = законы Булевой алгебры. Формы представления булевых = логических функций.

*Бабичева, Болдовская, Справочник по математике. СибАДИ, 2010. (классная книга)

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

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

Поглощение

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
Поиск в инженерном справочнике DPVA. Введите свой запрос:
Поиск в инженерном справочнике DPVA. Введите свой запрос:
Если Вы не обнаружили себя в списке поставщиков, заметили ошибку, или у Вас есть дополнительные численные данные для коллег по теме, сообщите , пожалуйста.
Вложите в письмо ссылку на страницу с ошибкой, пожалуйста.
Коды баннеров проекта DPVA.ru
Начинка: KJR Publisiers

Консультации и техническая
поддержка сайта: Zavarka Team

Проект является некоммерческим. Информация, представленная на сайте, не является официальной и предоставлена только в целях ознакомления. Владельцы сайта www.dpva.ru не несут никакой ответственности за риски, связанные с использованием информации, полученной с этого интернет-ресурса. Free xml sitemap generator

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

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

высказываниям можно присваивать значения 1 («истина») и 0 «ложь».

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

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

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

n переменных равно 2 в степени n. То же самое можно сказать и иначе: число различных n-мерных булевых векторов равно 2 в степени n. А число различных функций алгебры логики от этих векторов равно уже .

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

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

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

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

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

 

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

 

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

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

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

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

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

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

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

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

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

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

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

.

01
10

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

.

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

.

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

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

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

.

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

.

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

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

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

Номер набораf
00
11
20
3
0
41
51
60
71

 

X1X2X3f
0000
0011
0100
0110
1001
1011
1100
1111

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

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

или .

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

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

Карта Карно

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

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

.

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

.

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

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

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

.

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

.

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

.

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

.

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

.

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

.

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

.

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

.

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

.

.

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

.

.

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

.

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

.

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.

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

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

Дизъюнкция

Конъюнкция

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

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

х1х2=х2х1

х1х2=х2х1

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

х1(х2х3) = (х1х2)х3

х1(х2х3) = (х1х2)х3

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

х1(х2х3) =х1х2х1х3

х1х2х3= (х1х2)(х1х3)

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

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

х0 =х;х1 = 1

х0 = 0;х1 =х

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

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

х1х1х2=х1

х1(х1х2) = х1

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

хх…х=х

ххх=х

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

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

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

.

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

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

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

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

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

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

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

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

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

(4)

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

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

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

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

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

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

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

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

Таблица 5

х1

х2

х3

z

0

0

0

0

0

0

1

1

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

0

Используя правило построения СДНФ, получим:

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

Для рассмотренного примера 1СКНФ функции будет иметь вид:

.

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

  • выписывается логическая сумма дизъюнктивных членов, не вошедших в СДНФ, т.е. отрицание функции;

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

Пример 2.Построить СКНФ булевой функции по ее СДНФ:. Получим отрицание этой функции:

Взяв отрицание от полученного выражения еще раз и использую правило де-Моргана, получим

Аналогично осуществляется переход от СКНФ к СДНФ представления функции алгебры логики.

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

 

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

 

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

+

 

2.Сочетательный закон (ассоциативный). Можно производить объединение переменных в скобки.

 

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

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

1 + Х2)×(Х1 + Х3) = Х1×Х1 + Х1×Х3 + Х1×Х2 + Х2×Х31 + Х1×Х3 + Х1×Х2 + Х2×Х3 = Х1×(1 + Х3 + Х2) + Х2×Х3 = Х1 + Х2×Х3, что и требовалось доказать.

 

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

Докажем первое выражение:

=

Докажем второе выражение:

 

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

=

Докажем первое выражение:

Докажем второе выражение:

=

6.Закон инверсии или правило де Моргана. (Огастес де Морган – 1806-1871 шотландский математик и логик, независимо от Джорджа Буля пришел к основным идеям математической логики).

; Инверсия дизъюнкции переменных есть конъюнкция инверсий этих же переменных.

Соответственно: Инверсия конъюнкции переменных есть дизъюнкция инверсий этих же переменных

или

; Дизъюнкция переменных есть инверсия конъюнкции инверсий этих же переменных.

 

7.Закон повторений или тавтологии:

 

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

; Четное количество инверсий может быть отброшено.

 

Логические функции Л.Ф.

Л.Ф. называется функция двоичных переменных

Y = (

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

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

Конкретную комбинацию переменных называют набором.

Пример:

 

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

Л.Ф. называется частично определенной, если для некоторых наборов переменных функция Y = ( недоопределена (не задана).

 

 


Узнать еще:

Законы и функции булевой алгебры

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

Рисунок — 1

Булева функция от N переменных имеет 2N допустимых комбинаций значений, и такую функцию можно описать в таблице с 2N строками. Каждая строка будет иметь значение функции для разных комбинаций. Такая таблица имеет название — таблица истинности. Если взять за стандарт расположение строк таблицы истинности по порядку номеров (00,01 и тд), то функцию можно абсолютно описать 2N — битным двоичным числом, которое получается, если считать по вертикали колонку результатов. По-этому, НЕ-И это 1110, НЕ-ИЛИ это 1000, И — 0001, ИЛИ это 0111. Есть только 16 булевых функций от двух переменных, которые определяются из 16 возможных 4-битных цепочек. На рис.2.а видна таблица истинности для булевой функции от трех переменных: М -f (A,B,C).

Рисунок — 2

Любую булеву функцию можно определить, при указании комбинаций значений переменных дают выходной результат — 1. Для функции на рис.2 есть 4 комбинации переменных, которые дают значение — 1. Черта над переменной определяет инверсию значения. Функция И обозначается знаком *, функция ИЛИ обозначается знаком +. К примеру, АВС имеет значение 1, если А = 1, В = 0, С = 1. Функция М имеет значение истины (1), если одно из этих 4 условий истинно: М = АВС + АВС + АВС + АВС.

Реализация булевых функций

На рис.2.б входные сигналы А, В, С показаны с левой стороны, а функция М — с правой. Поскольку нужны дополнительные величины(инверсии) входных переменных, реализован инверторы 1,2 и 3. Схема имеет 4 вентиля И, и по одному для каждого члена в уравнении для М. Каждый вентиль И считает одну из указанных строк таблицы истинности. Также на схеме обозначается пересечение линий используют жирную точку.
Законы булевой алгебры показаны в таблице 1.

Название законов И ИЛИ
Законы тождества 1А=А 0+А=А
Законы нуля 0А=А 1+А=1
Законы идемпотентности АА=А А+А=А
Законы инверсии АА‾=0 A+A‾=1
Коммуникативные законы АВ=ВА А+В=В+А
Ассоциативные законы (АВ)С=А(ВС) (А+В)+С=А+(В+С)
Дистрибутивные законы А+ВС=(А+В)(А+С) А(В+С)=АВ+АС
Законы поглащения А(А+В)=А А+АВ=А
Законы Де Моргана АВ‾= А + В‾ (А+В)‾=АВ‾

КОНТРОЛЬНАЯ РАБОТА «ОСНОВНЫЕ ЗАКОНЫ БУЛЕВОЙ АЛГЕБРЫ И ПРАВИЛА ПРЕОБРАЗОВАНИЙ»

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

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

Подробнее

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

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

Подробнее

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

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

Подробнее

Тема 9. Логические основы ЭВМ.

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

Подробнее

II. АЛГЕБРА ЛОГИКИ. 1. Понятие алгебры

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

Подробнее

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

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

Подробнее

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

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

Подробнее

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

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

Подробнее

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

Лекция 3 Булевы алгебры и булевы функции Булевы алгебры Понятие об алгебраических системах Алгебраическая система или алгебраическая структура множество символов некоторого алфавита (носитель) с заданным

Подробнее

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. Кафедра математических и информационных технологий Санкт-Петербургского академического университета 20.02.2017 План лекции 1 Полнота системы связок

Подробнее

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

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

Подробнее

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

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

Подробнее

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

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

Подробнее

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

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

Подробнее

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

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

Подробнее

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

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

Подробнее

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

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

Подробнее

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

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

Подробнее

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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ ДИСКРЕТНАЯ МАТЕМАТИКА Часть ЛОГИЧЕСКИЕ ФУНКЦИИ Учебное пособие по дисциплинам «Дискретная математика»

Подробнее

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

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

Подробнее

A8 (базовый уровень, время 1 мин)

A8 (базовый уровень, время 1 мин) Тема: Преобразование логических выражений. Формулы де Моргана. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

Подробнее

X 1 X 2 F(X 1, X 2 ) X X 1

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

Подробнее

сайты:

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

Подробнее

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

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

Подробнее

Нормальные формы булевых функций

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

Подробнее

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

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

Подробнее

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

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

Подробнее

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

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

Подробнее

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

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

Подробнее

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

Подробнее

Сократ человек Платон человек

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

Подробнее

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

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

Подробнее

A10 (базовый уровень, время 1 мин)

A10 (базовый уровень, время 1 мин) Тема: Преобразование логических выражений. Формулы де Моргана. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

Подробнее

Логика высказываний лекция 2

Логика высказываний лекция 2 Лев Дмитриевич Беклемишев http://lpcs.math.msu.su/vml2010 http://www.mi.ras.ru/~bekl [email protected] 18.02.2010 Логика высказываний Связки:,,,. Истинностные значения: B = {Л,

Подробнее

ВВЕДЕНИЕ. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ

5 ВВЕДЕНИЕ. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ Все математические дисциплины можно условно разделить на д и с к р е- т н ы е и н е п р е р ы в н ы е. Дискретная математика это та часть математики, главной особенностью

Подробнее

B4 (высокий уровень, время 10 мин)

B4 (высокий уровень, время 1 мин) Тема: Преобразование логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (,, ),

Подробнее

Раздел 2. Основы логики высказываний.

Лекция 2 Раздел 2. Основы логики высказываний. Высказывание. Операции над высказываниями: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность. Истинностные таблицы. Пропозициональные буквы,

Подробнее

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

Законы алгебры логики Это интересно! Математика и закон де Моргана Как вы запишите математически принадлежность точки x отрезку [2;5]? Это можно сделать так: 2 x 5. Это означает, что одновременно должны

Подробнее

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

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

Подробнее

A9 (базовый уровень, время 2 мин)

A9 (базовый уровень, время 2 мин) Тема: Построение таблиц истинности логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

Подробнее

Логические операции трехзначной логики

ВА Бубнов Московский городской педагогический университет Электронный научный журнал «Вестник Омского государственного педагогического университета» Выпуск 6 wwwomskedu Логические операции трехзначной

Подробнее

Законы булевой алгебры | Учебник по организации и архитектуре компьютера

Основные законы булевой алгебры можно сформулировать следующим образом:

  • Закон коммутации гласит, что изменение порядка операндов в булевом уравнении не меняет его результата. Например:
    1. Оператор ИЛИ → A + B = B + A
    2. Оператор И → A * B = B * A
  • Ассоциативный закон умножения гласит, что операция И выполняется над двумя или более чем двумя переменными.Например:
    A * (B * C) = (A * B) * C
  • Закон распределения гласит, что умножение двух переменных и сложение результата с переменной приведет к тому же значению, что и умножение сложения переменной с отдельными переменными. Например:
    A + BC = (A + B) (A + C).
  • Закон об аннулировании:
    A.0 = 0
    A + 1 = 1
  • Закон идентичности:
    A.1 = A
    A + 0 = A
  • Идемпотентный закон:
    A + A = A
    A.A = A
  • Закон дополнения:
    A + A ‘= 1
    A.А ‘= 0
  • Закон двойного отрицания:
    ((A) ‘)’ = A
  • Закон поглощения:
    A. (A + B) = A
    A + AB = A

Закон Де Моргана, также известный как теорема Де Моргана, работает в зависимости от концепции двойственности. Двойственность утверждает, что перестановка операторов и переменных в функции, например замена 0 на 1 и 1 на 0, оператора AND на оператор OR и оператора OR на оператор AND.

Де Морган сформулировал 2 теоремы, которые помогут нам в решении алгебраических задач в цифровой электронике.Заявления Де Моргана:

  1. «Отрицание конъюнкции — это дизъюнкция отрицаний», что означает, что дополнение произведения двух переменных равно сумме дополнений отдельных переменных. Например, (A.B) ‘= A’ + B ‘.
  2. «Отрицание дизъюнкции — это соединение отрицаний», что означает, что дополнение суммы двух переменных равно произведению дополнения каждой переменной. Например, (A + B) ‘= A’B’.

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

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

Логическое сложение

Операция сложения булевой алгебры аналогична операции ИЛИ. В цифровых схемах операция ИЛИ используется для вычисления члена суммы без использования операции И.A + B, A + B ‘, A + B + C’ и A ‘+ B + + D’ являются одними из примеров «суммарного члена». Значение суммы — истина, когда один или несколько литералов истинны, и ложь, когда все литералы ложны.

Логическое умножение

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

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

Существуют следующие законы булевой алгебры:

Коммутативный закон

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

Для двух переменных коммутативный закон сложения записывается как:

А + В = В + А


Для двух переменных коммутативный закон умножения записывается как:

А.B = B.A


Ассоциативный закон

Этот закон гласит, что операция может выполняться в любом порядке при одинаковом приоритете переменных. Поскольку ‘*’ и ‘/’ имеют одинаковый приоритет. На диаграмме ниже ассоциативный закон применяется к логическому элементу ИЛИ с 2 входами.

Для трех переменных ассоциативный закон сложения записывается как:

А + (В + С) = (А + В) + С


Для трех переменных ассоциативный закон умножения записывается как:

А (ВС) = (АВ) С

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

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

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

Для трех переменных закон распределения записывается как:

А (В + С) = АВ + АС


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

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

1. А + 0 = А 7. A.A = A
2. А + 1 = 1 8. A.A ‘= 0
3. A.0 = 0 9. А » = А
4. A.1 = A 10. А + АВ = А
5. А + А = А 11. А + А’В = А + В
6. А + А ‘= 1 12. (A + B) (A + C) = A + BC

Правило 1: A + 0 = A

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

Правило 2: (A + 1) = 1

Предположим; у нас есть входная переменная A, значение которой равно 0 или 1. Когда мы выполняем операцию ИЛИ с 1, результат всегда будет 1. Таким образом, если значение переменной равно 1 или 0, то результат всегда будет 1. Диаграмма. , это правило можно определить как:

Правило 3: (A.0) = 0

Предположим; у нас есть входная переменная A, значение которой равно 0 или 1. Когда мы выполняем операцию И с 0, результатом всегда будет 0.Это правило гласит, что входная переменная с оператором AND с 0 всегда равна 0. Схематично это правило можно определить как:

Правило 4: (A.1) = A

Предположим; у нас есть входная переменная A, значение которой равно 0 или 1. Когда мы выполняем операцию И с 1, результат всегда будет равен входной переменной. Это правило гласит, что входная переменная, объединенная операцией AND с 1, всегда равна входной переменной. Схематично это правило можно определить как:

Правило 5: (A + A) = A

Предположим; у нас есть входная переменная A, значение которой равно 0 или 1.Когда мы выполняем операцию ИЛИ с той же переменной, результат всегда будет равен входной переменной. Это правило гласит, что входная переменная, объединенная с самим собой, всегда равна входной переменной. Схематично это правило можно определить как:

Правило 6: (A + A ‘) = 1

Предположим; у нас есть входная переменная A, значение которой равно 0 или 1. Когда мы выполняем операцию OR с дополнением этой переменной, результат всегда будет равен 1. Это правило гласит, что переменная, объединенная OR с ее дополнением, равна 1 всегда.Схематично это правило можно определить как:

Правило 7: (A.A) = A

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

Правило 8: (A.A ‘) = 0

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

Правило 9: A = (A ‘)’

Это правило гласит, что если мы выполним двойное дополнение переменной, результат будет таким же, как и исходная переменная. Итак, когда мы выполняем дополнение переменной A, результатом будет A ‘. Далее, если мы снова выполним дополнение к A ‘, мы получим A, то есть исходную переменную.

Правило 10: (A + AB) = A

Мы можем доказать это правило, используя правило 2, правило 4 и закон распределения как:

A + AB = A (1 + B) Факторинг (закон распределения)
A + AB = A.1 Правило 2: (1 + B) = 1
A + AB = A Правило 4: A .1 = A


Правило 11: A + AB = A + B

Мы можем доказать это правило, используя приведенные выше правила как:

A + AB = (A + AB) + AB Правило 10: A = A + AB
A + AB = (AA + AB) + AB Правило 7: A = AA
A + AB = AA + AB + AA + AB Правило 8: сложение AA = 0
A + AB = (A + A) (A + B) Факторинг
A + AB = 1.(A + B) Правило 6: A + A = 1
A + AB = A + B Правило 4: бросьте 1


Правило 12: (A + B) (A + C) = A + BC

Мы можем доказать это правило, используя приведенные выше правила как:

(A + B) (A + C) = AA + AC + AB + BC Закон распределения
(A + B) (A + C) = A + AC + AB + BC Правило 7: AA = A
(A + B ) (A + C) = A (1 + C) + AB + BC Правило 2: 1 + C = 1
(A + B) (A + C) = A.1 + AB + BC Факторинг (закон распределения)
(A + B) (A + C) = A (1 + B) + BC Правило 2: 1 + B = 1
(A + B) (A + C) = A.1 + BC Правило 4: A .1 = A
(A + B) (A + C) = A + BC



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

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

Логическая алгебра

Введение

При работе с логическими отношениями в цифровой форме нам понадобится набор правила символического манипулирования, которые позволят нам упростить сложные выражения и решите для неизвестных. Первоначально булева алгебра сформулировал Джордж Буль, английский математик (1815-1864) описал предложения, результат которых будет либо истина, либо ложь .В компьютерной работе используется в дополнение для описания схем, состояние которых может быть либо 1 (истина) или 0 (ложь) . Используя отношения, определенные в И, ИЛИ и НЕ эксплуатации, ряд постулатов изложен в таблице 2.1. [Ссылка 3].

  • P1: X = 0 или X = 1
  • P2: 0 0 = 0
  • P3: 1 + 1 = 1
  • P4: 0 + 0 = 0
  • P5: 1 1 = 1
  • P6: 1 0 = 0 1 = 0
  • P7: 1 + 0 = 0 + 1 = 1
Таблица 2.1 Логические постулаты


Основные булевы теоремы

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

Принцип двойственности 1. Замена операций OR и AND в выражении.
2. Меняем местами элементы выражения 0 и 1.
3. Не менять форму переменных.

Таблица 2.2 Теоремы булевой алгебры
T1: Коммутативный закон
(а) A + B = B + A
(б) A B = B A
T2: Ассоциативный закон
(а) (A + B) + C = A + (B + C)
(б) (А Б) С = А (В С)
T3: Закон о распределении
(а) A (B + C) = A B + A C
(б) А + (В С) = (А + В) (А + С)
T4: Закон о личности
(а) А + А = А
(б) A A = A
T5: Закон об отрицании
(a)
(b)
T6: Закон о резервировании
(а) A + A B = A
(б) А (А + В) = А
T7:
(а) 0 + A = A
(б) 1 А = А
(в) 1 + A = 1
(г) 0 А = 0
T8:
(а)
(б)
T9:
(a)
(b)
T10: Теорема Де Моргана
(а)
(б)

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


Пример 2.1 Доказательство T9: (a)

(1) Алгебраически,

(2) Используя таблицу истинности,

(3) Используя диаграммы Венна,


Пример 2.2 Нарисуйте принципиальную схему логического выражения. :

Цепь:


Пример 2.3 Напомним определение логического элемента И-НЕ:

На выходе логического элемента И-НЕ высокий уровень, если на каком-либо из его входов низкий уровень. То есть выход низкий, только если все его входы высокая. Логическое выражение для логического элемента И-НЕ с 4 входами:


где Выход = 0, когда A = 1, B = 1, C = 1 и D = 1; Выход = 1 в противном случае.
Проблема 2,1

(a) Докажите T9 (b).

(b) Докажите T10: (a) и (b), заполнив таблицы истинности ниже:

Щелкните здесь, чтобы ознакомиться с типовым ответом.

Проблема 2.2

(a) Запишите логическое выражение на выходе Y 3-входного Ворота NAND,

с точки зрения входов A, B и C.

(b) Заполните приведенную ниже таблицу истинности для схемы в (a). Щелкните здесь, чтобы ознакомиться с типовым ответом.

Перейти к следующей главе или Предыдущая глава или Домашняя страница

Законы и теоремы булевой алгебры

1а. X • 0 = 0 1b. Х + 1 = 1 Закон об аннулировании
2а. X • 1 = X 2b. Х + 0 = Х Закон о личности
3а. X • X = X 3b. Х + Х = Х Идемпотентный закон
4а. X • X = 0 4b. Х + Х = 1 Закон о дополнении
5. = Х Закон о двойном отрицании
6а. X • Y = Y • X 6б. X + Y = Y + X Коммутативный закон
7а. Х (Y Z) = (X Y) Z = (X Z) Y = X Y Z Ассоциативный закон
7b. Х + (Y + Z) = (X + Y) + Z = (X + Z) + Y = X + Y + Z Ассоциативный закон
8а. X • (Y + Z) = X Y + X Z 8b. X + Y Z = (X + Y) • (X + Z) Закон о распределении
9а. X • Y = X + Y 9b. X + Y = X • Y Теорема де Моргана
10а. X • (X + Y) = X 10б. Х + Х Y = Х Закон поглощения
11а. (X + Y) • (X + Y) = X 11b. X Y + X Y = X Закон о резервировании
12а. (X + Y) • Y = XY 12b. X Y + Y = X + Y Закон о резервировании
13а. (X + Y) • (X + Z) • (Y + Z) = (X + Y) • (X + Z) Закон о консенсусе
13b. X Y + X Z + Y Z = X Y + X Z Закон о консенсусе
14а. X ⊕ Y = (X + Y) • (X + Y) 14b. X ⊕ Y = X Y + X Y Ворота XOR
15а. X ⊙ Y = (X + Y) • (X • Y) 15b. X ⊙ Y = X Y + X Y Ворота XNOR
15c. X ⊙ Y = (X + Y) • (X + Y) Ворота XNOR

Булева алгебра — курс цифровой электроники

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

Калькулятор логических выражений

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

    Примечания:
  • Используйте ~ * + для обозначения НЕ И ИЛИ соответственно. Не пропускайте оператор * для операции И.
    • (~ AB) + (B ~ C) + (AB) вернет ошибку
    • (~ A * B) + (B * ~ C) + (A * B) в порядке
  • Логические операции следуют порядку приоритета НЕ И ИЛИ.Выражения внутри скобок () всегда оцениваются первыми, имея приоритет над порядком приоритета.
  • Пожалуйста, вводите только переменные, константы вроде 0,1 не допускаются.
  • Переменные E, I, N, O, Q, S не допускаются

Упрощение логических выражений

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

~ (A * B) * (~ A + B) * (~ B + B)
~ (A * B) * (~ A + B) * 1 6 — Закон дополнения
~ (A * B) * (~ A + B) 5 — Закон идентичности
(~ A + ~ B) * (~ A + B) 8 — Закон ДеМоргана
~ A + ~ B * B 4 — Закон распределения
~ A + 0 6 — Закон дополнения
~ A 5 — Закон идентичности

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

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

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

    Основные логические законы

  1. Идемпотентный закон
  2. Ассоциативный закон
    • (A * B) * C = A * (B * C)
    • (А + В) + С = А + (В + С)
  3. Коммутативный закон
    • А * В = В * А
    • А + В = В + А
  4. Распределительное право
    • А * (В + С) = А * В + А * С
    • А + (В * С) = (А + В) * (А + С)
  5. Закон о личности
    • А * 0 = 0 А * 1 = А
    • А + 1 = 1 А + 0 = А
  6. Закон о дополнении
  7. Закон об инволюции
  8. Закон ДеМоргана
    • ~ (А * В) = ~ А + ~ В
    • ~ (А + В) = ~ А * ~ В

    Законы о резервировании

  9. Поглощение
    • А + (А * В) = А
    • А * (А + В) = А
    • (А * В) + (А * ~ В) = А
    • (А + В) * (А + ~ В) = А
    • А + (~ А * В) = А + В
    • А * (~ А + В) = А * В

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

  • Замена операций + (ИЛИ) и * (И) в выражении.
  • Замена элементов 0 и 1 в выражении местами.
  • Не меняет форму переменных.

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

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

состоит из следующих этапов.

  1. Из проектной спецификации найдите таблицу истинности
  2. Из таблицы истинности выведите логическое выражение «Сумма произведений».
  3. Используйте логическую алгебру, чтобы упростить логическое выражение. Чем проще логическое выражение, тем меньше логических элементов будет использоваться.
  4. Используйте логические элементы для реализации упрощенного логического выражения.

Присоединяйтесь к обсуждению

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

Если вы получили пользу от этого сайта и можете, пожалуйста, дайте 10 долларов через Paypal . Это позволит нам продолжаем в будущее. Это займет всего минуту. Спасибо!

Я хочу дать!

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

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

Булева алгебра (разработанная Джорджем Булем и Августом Де Морганом) формирует базовый набор правил, которые регулируют отношения между утверждениями истина и ложь в логике.Применительно к цифровым логическим схемам и системам утверждения «истина-ложь» регулируют взаимосвязь между логическими уровнями (логический 0 и 1) в цифровых логических схемах и системах. Связи основаны на переменных и константах:

Идентификатор логического оператора AND -. (точка).

Идентификатор логического оператора ИЛИ — + (символ математического сложения).

Идентификатор логического оператора НЕ: (полоса в выражении).

Идентификатор логического оператора EX-OR — Å (заключенный в кружок символ сложения).

На рисунке 5.5 показано логическое выражение для каждого из этих операторов.

Рисунок 5.5. Логические выражения для основных логических операторов

Каждый из операторов можно комбинировать для создания более сложных логических выражений. Например, если схема имеет четыре входа (A, B, C и D) и один выход (Z), то если Z — это логическая 1, когда (A и B) — это логическая 1, или , когда ( C и D) представляет собой логическую единицу, логическое выражение имеет вид:

Z = (A.B) + (C.D)

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

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

1.

Логические операции над константами

2.

Логические операции над одной переменной

3.

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

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

Таблица 5.10. Логические операции над константами

В таблице 5.11 приведены логические операции над одной переменной (A). Операция выполняется только с переменной или с переменной и постоянным значением. Каждая переменная и постоянное значение могут быть либо логическим 0, либо 1. Результатом является либо логический 0, либо 1 в соответствии с логическим оператором.

Таблица 5.11. Логические операции над одной переменной

Полоса над переменной указывает на логическую инверсию переменной.Двойная полоса указывает на логическую инверсию, за которой следует другая логическая инверсия. Этот эффект показан на рисунке 5.6 при использовании символа схемы для логического элемента НЕ (символ представляет собой треугольник с кружком на конце — см. Рис. 5.8). По логике, двойная инверсия сигнала не имеет логического эффекта.

Рисунок 5.8. Условные обозначения схем логического оператора

Рисунок 5.6. Инверсия переменной

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

Рисунок 5.7. Обозначение схемы логического буфера

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

В таблице 5.12 приведены логические операции с двумя или более переменными. Здесь рассматриваются две ( A и B ) или три переменные ( A, B и C ). Каждое значение переменной может быть либо логическим 0, либо 1. Результатом является либо логический 0, либо 1 в соответствии с логическим оператором.

Таблица 5.12. Логические операции над двумя или тремя переменными

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

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

Булева алгебра (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)}.\ конец {выравнивание *} \] .

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

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