Базисные логические функции

3.4 Базисные логические функции

Любую логическую функцию можно представить совокупностью элементарных логических функций: дизъюнкцией, конъюнкцией, инверсией или их суперпозицией. Набор элементарных функций ИЛИ, И, НЕ называют функционально полным или базисным (базисом). Кроме того существуют еще два базиса: И-НЕ; ИЛИ-НЕ.

3.5 Принцип двойственности булевой алгебры

Если в выражении F8=АВ конъюнкцию заменить на дизъюнкцию и проинвертировать обе переменные, то результат окажется инверсией прежнего значения функции . Аналогично, если в выражении F14=АВ дизъюнкцию заменить на конъюнкцию и проинвертировать обе переменные, то результат окажется инверсией прежнего значения функции .

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

3.6 Основные тождества булевой алгебры

А+0=А;А+1=1;

А+А=А;А+=1;

А*0=0;А*1=А;

А*А=А;А*=0;=А.

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

3.7.1 Законы

Переместительный (свойство коммутативности): А+В=В+А; А*В=В*А.

Сочетательный (свойство ассоциативности): (А+В)+С=А+(В+С); (А*В)*С=А*(В*С).

Распределительный (свойство дистрибутивности): А*(В+С)=А*В+А*С; А+В*С=(А+В)*(А+С).

3.7.2 Теоремы

Поглощения: А+А*В=А; А*(А+В)=А.

Склеивания:

Де Моргана. Существует две формы записи теоремы де Моргана:

Форма 1:(3.1.1)

Форма 2:(3.1.2)

Последние два выражения вытекают из принципа двойственности булевой алгебры (раздел 3.5).

Теорема без названия. Существует еще одна теорема без названия, которую представим следующим образом:

(3.1.3)

Два полезных соотношения:

(3.1.4)

3.8 Совершенная дизъюнктивная нормальная форма (СДНФ) записи булевых выражений

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

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

Таблица 3.4

Эта функция имеет четыре конституенты единицы К1, К4, К5 и К6 (коституента единицы – это единичное значение ПФ на одном конкретном наборе. Всего для ПФ трех переменных может быть восемь конституент единицы, если функция принимает единичное значение на всех наборах). Конституента единицы записывается в виде конъюнкции. Для нашего примера  ;  .

Булево выражение ПФ в СДНФ представляет сумму конституент единицы:

.(3.2)

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

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

Похожие работы

Цифровая схемотехника

Скачать

100365

3

18

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

Интегральные логические элементы

Скачать

35831

55

44

осхемы К155ЛА3 (4 логических элемента 2И-НЕ). Принцип работы ЛЭ И-НЕ ТТЛ Основная особенность микросхем ТТЛ состоит в том, что во входной цепи используется специфический интегральный прибор – многоэмиттерный транзистор (МЭТ), имеющий несколько эмиттеров, объединенных общей базой. Эмиттеры расположены так, что непосредственное взаимодействие между ними через участок базы отсутствует. Поэтому МЭТ ...

Схемотехника ЭВМ

Скачать

38073

13

21

... . Минимальное количество листов графических работ формата А1 — два. Графические документы выполняются карандашом или черной тушью на листах ватмана формата А1. Возможно выполнение чертежей с применением ЭВМ. Допускается использовать формат А2. Листы нумеруются. Номер помещается в верхнем левом углу листа. Допускается выполнять номера на отдельных листах бумаги, которые прикрепляются во время ...

Разработка печатной платы устройства управления питания компьютерной системы

Скачать

34672

3

0

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