главнаяреклама на сайтезаработоксотрудничество Библиотека Revolution
 
 
Сколько стоит заказать работу?   Искать с помощью Google и Яндекса
 



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

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

Рубрика: Коммуникации, связь, цифровые приборы и радиоэлектроника
Вид: реферат
Язык: русский
Дата добавления: 12.06.2009
Размер файла: 48,5 K

Полная информация о работе Полная информация о работе
Скачать работу можно здесь Скачать работу можно здесь

рекомендуем


Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже.

Название работы:
E-mail (не обязательно):
Ваше имя или ник:
Файл:


Cтуденты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны

Подобные работы


1. Комбинационные схемы
Основные аксиомы, теоремы, тождества алгебры логики. Переключательные функции. Расчет комбинационной логической схемы по заданной переключательной функции. Минимизация переключательных функций с помощью карт Карно. Скобочные формы логических уравнений.
реферат [1,2 M], добавлена 24.12.2010

2. Компьютерная схемотехника
Применение булевой алгебры при анализе и синтезе цифровых электронных устройств. Реализация логических функций в разных базисах. Параметры и характеристики цифровых интегральных микросхем. Структура локальной микропроцессорной системы управления.
книга [3,6 M], добавлена 20.03.2011

3. Функции алгебры логики. Логический базис
Сущность современных радиотехнических систем и комплексов. Функции алгебры логики. Понятие совершенно дизъюнктивной нормальная формы. Формы реализации логических функций. Параметры полного логического базиса. Особенности принципа двойственности алгебры.
реферат [161,0 K], добавлена 10.12.2008

4. Цифровые устройства автоматики
Основные инструменты анализа и синтеза цифровых устройств. Синтез комбинационного устройства, реализующего заданную функцию. Минимизация переключательных функций с помощью карт Карно. Общие правила минимизации функций. Дешифратор базиса Шеффера.
контрольная работа [540,0 K], добавлена 09.01.2014

5. Синтез и исследование логической схемы цифрового автомата, построенного на цифровых микросхемах
Таблица истинности, функции алгебры логики разрабатываемого цифрового автомата. Функциональная логическая схема устройства. Минимизация функции алгебры логики, представление ее в базисе "И-НЕ". Функциональная схема минимизированных функций Y1 и Y2.
контрольная работа [2,1 M], добавлена 22.10.2012

6. Проектирование цифрового устройства
Логические основы синтеза цифровых устройства. Понятия и определения функций алгебры логики. Минимизация логических функций с помощью алгебраических преобразований, карт Карно. Построение аналитической модели устройства. Анализ и выбор элементной базы.
контрольная работа [696,4 K], добавлена 19.10.2011

7. Цифровая электроника
Системы счисления в цифровых устройствах. Теоремы, логические константы и переменные операции булевой алгебры. Назначение, параметры и классификация полупроводниковых запоминающих устройств, их структурная схема. Процесс аналого-цифрового преобразования.
курсовая работа [1,8 M], добавлена 21.02.2012

8. Создание цифровых устройств
Реализация булевых функций на мультиплексорах. Применение постоянных запоминающих устройств (ПЗУ). Структурная схема программируемых логических матриц (ПЛМ). Функциональная схема устройства на микросхемах малой и средней степени интеграции, ПЗУ и ПЛМ.
курсовая работа [524,1 K], добавлена 20.12.2013

9. ПЛМ, воспроизведение скобочных форм переключательных функций, схемы с двунаправленными выводами
Программируемые логические матрицы (ПЛМ), их структура, основные параметры. Воспроизведение скобочных форм переключательных функций. Общее правило решения задач с помощью ПЛМ. Программируемая матричная логика (ПМЛ) с разделяемыми коньюнкторами, ее схемы.
реферат [292,2 K], добавлена 25.01.2009

10. Синтез устройства, производящего арифметическую операцию суммирования по модулю семь
Замена симметричных переменных с использованием элементарных симметричных функций. Анализ совместной реализации системы функций. Раздельная минимизация системы функций алгебры логики. Факторизация системы логических уравнений. Выбор элементной базы.
дипломная работа [1,0 M], добавлена 22.11.2012


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


БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

КАФЕДРА РЭС

РЕФЕРАТ

НА ТЕМУ:

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

МИНСК, 2009

Основные аксиомы и тождества алгебры логики

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

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

Система аксиом:

Аксиома (1) является утверждением того, что в алгебре логики рассматриваются только двоичные переменные, аксиомы (2)…(5) определяют операции дизъюнкции и конъюнкции, а аксиома (5) -- операцию отрицания. Если в аксиомах (2)…(5), заданных парами, произвести взаимную замену операций дизъюнкции и конъюнкции, а также элементов 0 и 1, то из одной аксиомы пары получится другая. Это свойство называется принципом двойственности.

Теоремы и тождества алгебры логики

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

Метод перебора не слишком трудоемок, так как переменные могут иметь только два значения: 0 и 1.

Так, методом перебора легко убедиться в справедливости следующих теорем:

Идемпотентные законы (законы тождества):

(6)

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

(7)

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

(8)

Дистрибутивные законы:

(9)

Законы отрицания:

(10)

(11)

(12)

Законы двойственности (Теоремы де Моргана):

(13)

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

(14)

Законы поглощения (абсорбция):

(15)

Операции склеивания:

(16)

Операции обобщенного склеивания:

(17)

(18)

Теоремы (6)…(13) и (15)…(18) записаны парами, причем каждая из теорем пары двойственна другой, так как из одной теоремы пары можно получить другую на основании принципа двойственности, то есть путем взаимной замены операций дизъюнкции и конъюнкции, а также элементов 0 и 1, если они имеются. Теорема (14) самодвойственна, так как она не изменяется по принципу двойственности (отсутствуют элементы 0 и 1 и операции дизъюнкции и конъюнкции). Все теоремы могут быть доказаны аналитически или методом перебора. В качестве примера приведем доказательство тождества (13) методом перебора (табл. 1).

Таблица 1

x

y

0

0

0

1

1

0

1

1

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

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

.

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

.

Некоторые теоремы и тождества алгебры логики имеют особое значение, так как позволяют упрощать логические выражения. Например, в соотношениях (6), (10)…(12) и (15)…(18) правая часть проще левой, поэтому, произведя в логических выражениях соответствующие преобразования, можно добиться существенного их упрощения. С этой целью особенно часто используются тождества (15)…(18).

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

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

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

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

Допустим, что в ходе решения задачи требуется реализовать переключательную функцию, заданную таблицей 2.

Таблица 2

Номер

набора

Аргументы

Значение функции на i-ом наборе

0

0

0

0

0

1

0

0

1

0

2

0

1

0

0

3

0

1

1

1

4

1

0

0

0

5

1

0

1

0

6

1

1

0

1

7

1

1

1

1

Как видно из таблицы, функция должна принимать значение 1 только на 3-ем, 6-ом и 7-ом наборах. На всех остальных наборах ее значение равно 0. Возникает вопрос, каким образом записать эту функцию аналитически, то есть представить в виде формулы. Применительно к основному базису, содержащему элементы дизъюнкции, конъюнкции и отрицания, доказано, что любая переключательная функция, предварительно заданная в табличной форме, может быть записана аналитически в двух формах, получивших название канонических (нормальных): в дизъюнктивной совершенной нормальной форме (ДСНФ) и в конъюнктивной совершенной нормальной форме (КСНФ).

Аналитическая запись функций в виде ДСНФ и КСНФ предполагает представление этих функций посредством суперпозиции специально вводимых вспомогательных функций: минтермов и макстермов.

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

Отсюда следует, что переключательная функция от n переменных имеет число минтермов и макстермов, равное числу наборов, на которых она определена, то есть минтермов и макстермов.

В качестве примера приведем минтермы и макстермы двух переменных X1 и X2 (табл. 3 и 4).

Таблица 3.

Аргументы

Минтермы

0

0

1

0

0

0

0

1

0

1

0

0

1

0

0

0

1

0

1

1

0

0

0

1

Таблица 4.

Аргументы

Макстермы

0

0

0

1

1

1

0

1

1

0

1

1

1

0

1

1

0

1

1

1

1

1

1

0

Согласно приведенным определениям минтермы и макстермы двух аргументов выражаются формулами:

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

.

Таким образом, функция, заданная таблицей состояний (табл. 1.8), запишется аналитически следующим образом:

Термины сокращенного представления функции в виде ДСНФ в частности означают: термин «дизъюнкция» указывает на то, что внешней функцией разложения является дизъюнкция, а внутренней -- конъюнкция.

Термин «совершенная» указывает на то, что дизъюнктивные члены формируются из всех аргументов X1 …Xn, то есть на основе минтермов.

Термин «нормальная» указывает на то, что форма записи является двухуровневой, то есть дизъюнкция конъюнкций.

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

Поскольку от n аргументов существует макстермов, то аналитическая запись функции в КСНФ имеет вид:

В итоге для рассматриваемого примера (табл. 1.8):

или

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

ЛИТЕРАТУРА

1. Новиков Ю.В. Основы цифровой схемотехники. Базовые элементы и схемы. Методы проектирования. М.: Мир, 2001. - 379 с.

2. Новиков Ю.В., Скоробогатов П.К. Основы микропроцессорной техники. Курс лекций. М.: ИНТУИТ.РУ, 2003. - 440 с.

3. Пухальский Г.И., Новосельцева Т.Я. Цифровые устройства: Учеб. пособие для ВТУЗов. СПб.: Политехника, 2006. - 885 с.

4. Преснухин Л.Н., Воробьев Н.В., Шишкевич А.А. Расчет элементов цифровых устройств. М.: Высш. шк., 2001. - 526 с.

5. Букреев И.Н., Горячев В.И., Мансуров Б.М. Микроэлектронные схемы цифровых устройств. М.: Радио и связь, 2000. - 416 с.

6. Соломатин Н.М. Логические элементы ЭВМ. М.: Высш. шк., 2000. - 160 с.

... читать дальше >>>

Поcмотреть текст работы Поcмотреть полный текст
Скачать работу можно здесь Скачать работу "Основные аксиомы и тождества алгебры логики. Аналитическая форма представления булевых функций" можно здесь
Сколько стоит?

Рекомендуем!

база знанийглобальная сеть рефератов