Булев базис

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 14:27, 10 декабря 2016.
TemplateDifinitionIcon.svg Определение «Определение - Логический базис»
Логический базис (функционально полный набор операций) - это такой набор, который для реализации любой сколь угодно сложной логической функции не потребует использования каких-либо других операций, не входящих в этот набор.

Основные элементы

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

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

f(a)= ā

a ā
0 1
1 0

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

f(a,b)= a ∧ b

a b a ∧ b
0 0 0
0 1 0
1 0 0
1 1 1

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

f(a,b)= a ∨ b

a b a ∨ b
0 0 0
0 1 1
1 0 1
1 1 1

Применение

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

  • (И, ИЛИ, НЕ) - булев базис
  • (И-НЕ), (ИЛИ-НЕ) - универсальные базисы
  • (И, НЕ), (ИЛИ, НЕ) - сокращенные булевы базисы (базис Шеффера, базис Пирса)
  • (И, М2) - базис Жегалкина

В базисе Жегалкина элемент М2 реализует фукнцию сложения по модулю два.

Пример

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

Комбинационная схема в булевом базисе

Список источников

  1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов / Под ред. В.С. Зарубина, А.П. Крищенко. – 3-е изд., стереотип. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. – 744 с.
  2. Довгий П.С., Поляков В.И. Синтез комбинационных схем. Учебное пособие к курсовой работе по дисциплине "Дискретная математика". - СПб: СПбГУ ИТМО, 2009.- 64 с.
  3. Function-x [Электронный ресурс]: Булева алгебра (алгебра логики) / Дата обращения: 26.06.16. — Режим доступа: http://function-x.ru/buleva_algebra.html