Реферат: Основные аксиомы и тождества алгебры логики. Аналитическая форма представления булевых функций - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

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

Банк рефератов / Информатика, информационные технологии

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 813 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

БЕЛОРУССКИЙ ГОСУДАРСТВЕ ННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ КАФЕДРА РЭС РЕФЕРАТ НА ТЕМУ: « Основные аксиомы и тождества алгебры логики. Анал итическая форма представления булевых функций » МИНСК, 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 переменных имеет число минтер мов и макстермов, равное числу наборов, на которых она определена, то есть минтермов и макстермов. В качестве примера приведем минтермы и макстермы двух переменных X 1 и X 2 (табл. 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), запишется аналитически следующим образом: Термины сокращенного представления функции в вид е ДСНФ в частности означают: термин «дизъюнкция» указывает на то, что вне шней функцией разложения является дизъюнкция, а внутренней — конъюнкц ия. Термин «совершенная» указывает на то, что дизъюнктивные члены формирую тся из всех аргументов X 1 … X n , то есть на основе минтермов. Термин «нормальная» указывает на то, что форма записи является двухуровневой , то есть дизъюнкция к онъюнкций. Аналитическая запись функции в виде КСНФ означает, что переключательна я функция, заданная табличным способом, может быть представлена в виде логического произведения (к онъюнкцией) дизъюнктивных членов. При этом каждый из этих членов предста вляет собой сумму значений функции на 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 с.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Стас Михайлов за прошлый год заработал 18 миллионов долларов.
Больше у пожилых женщин отнял только Сергей Мавроди.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

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

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru