Минимизация логических функций реферат
Обновлено: 05.07.2024
Содержание работы
Введение…………………………………………………………….. 3
Основные логические функции……………………………………. 4
Свойства конъюнкции, дизъюнкции и отрицания………………. 6
ДНФ, СДНФ, КНФ, СКНФ………………………………………. 7
Представление логических функций в виде СДНФ (СКНФ)…… 8
Минимизация логических функций………………………………. 10
Реализация функций алгебры логики схемами………………….. 12
Заключение…………………………………………………………. 15
Список литературы………………………………………………… 16
Файлы: 1 файл
Схемотехника(Курсач).docx
Основные логические функции……………………………………. 4
Свойства конъюнкции, дизъюнкции и отрицания………………. 6
Представление логических функций в виде СДНФ (СКНФ)…… 8
Минимизация логических функций………………………………. 10
Реализация функций алгебры логики схемами………………….. 12
При решении задач автоматизации необходимо решение логических функций разной сложности, т.е. выполнение определенного действия при достижении ряда необходимых условий. Достаточно простые логические функции в автоматике решают с помощью специальных устройств – логических элементов.
Основные логические функции
Само множество Еn можно естественным образом упорядочить, для чего достаточно считать каждый набор двоичным разложением целого числа k (0≤k≤ 2n –1), записанного с помощью n знаков. Упорядочение наборов проводится по числу k . Например, при n = 3 множество Е3 может быть упорядочено следующим образом (рис.1).
Этот естественный порядок элементов Еn является самым распространенным, но, как будет видно в разд. 6, иногда удобен другой способ упорядочения.
Логической (булевой) функцией (или просто функцией) n переменных y = f(x1, x2, …, xn) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1. Переменные, которые могут принимать только два значения 0 и 1 называются логическими переменными (или просто переменными). Заметим, что логическая переменная х может подразумевать под числом 0 некоторое высказывание, которое ложно, и под числом 1 высказывание, которое истинно.
Логическая функция может быть задана словесно, алгебраическим выражением или таблицей, которая называется таблицей соответствия или истинности. Из определения логической функции следует, что функция n переменных - это отображение Еn в Е, которое можно задать непосредственно таблицей, называемой таблицей истинности данной функции. Например, функция трех переменных f(x,y,z) может определяться следующей таблицей истинности.
Это означает, что f(0,0,0) = 1, f(0,0,1) = 0, f(0,1,0) = 1 и т. д.
Две функции равны, если совпадают их таблицы истинности (на объединенном наборе переменных).
При таком задании наборы Еn всегда упорядочены естественным образом, это позволяет определять функцию только последним столбцом (который иногда для экономии места записывается в строчку). Например, в нашем примере функцию f(x,y,z) можно задать так: f(x,y,z) = (10110100).
Если фактически функция не зависит от некоторой переменной, то такую переменную называют фиктивной.
Теперь можно описать основные функции дискретной математики.
Перенумеруем четыре функции одной переменной y=f(x) естественным образом и расположим в виде таблицы 2:
Видно, что f0 (х) = 0, a f3 (х) =1, т. е. эти две функции не зависят от х,
f1 (х)=х, т. е. она не меняет аргумента. Функция f2 (х) действительно содержательная функция. Она принимает значения, противоположные значениям аргумента, обозначается f2 (х)= и называется отрицанием.
Аналитическое выражение логической функции, составленное в СДНФ или СКНФ по таблице истинности, как правило, является избыточным. В большинстве случаев его можно упростить. Т. е. найти такое аналитическое выражение, которое эквивалентно исходному выражению функции, но содержит меньшее число переменных и (или) операций. Процедура уменьшения числа переменных и (или) операций в аналитическом выражении логической функции называется минимизацией.
Практическая цель минимизации является уменьшение числа логических элементов при аппаратной реализации логической функции, и, как следствие этого, повышение быстродействия, уменьшение размеров, стоимости и потребления энергии у проектируемой логической схемы.
Минимизацию можно проводить различными методами. При числе переменных шесть и меньше наибольшее распространение имеет метод с использованием карты Карно (диаграммы Вейча).
Карта Карно представляет собой составленную по определенным правилам таблицу, куда занесены все значения логической функции. Таким образом, карта Карно является одним из способов задания логических функций. Вариантов изображения карты Карно много. Один из вариантов показан на рисунке 1 для двух переменных а), трех переменных б) и четырех переменных в). Принципиального значения не имеет, каким вариантом изображения карты Карно пользоваться. В дальнейшем для минимизации используются карты Карно, представленные на рисунке 1 и студентам рекомендуется тоже их использовать.
В картах Карно, показанных на рисунке 1, области, где переменные находятся без инверсий (X i), обозначены чертой. В областях, не обозначенных чертой, переменные находятся с инверсий ( ). Например, к области переменных Х 3 относятся клетки 4,5,6,7,12,13,14,15, а к области относятся клетки 0,1,4,5,8,9,12,13. Таким образом, в картах Карно, показанных на рисунке 1 имеются области переменных Младшая переменная обозначается Х 1, а старшинство остальных переменных линейно возрастает с увеличением индекса.
Каждой клетке карты Карно соответствует определенный и единственный минтерм (макстерм). Индекс минтерма является номером клетки карты Карно. Номер клетки также соответствует числу, которое выражает двоичная комбинация значений переменных, находящихся в строке таблицы истинности.
Карта Карно заполняется по таблице истинности или по аналитическому выражению функции, которую нужно минимизировать.
Если функция задана таблицей истинности, то порядок заполнения карты Карно следующий.
Берется строка таблицы истинности, и определяются области переменных, в которых находится клетка, соответствующая выбранной строке. Затем на карте Карно эти области выделяются. Искомой будет та клетка, которая одновременно находится во всех выделенных областях переменных (принадлежит одновременно всем выделенным областям, является для них общей). В найденную клетку проставляется значение функции, соответствующее комбинации переменных выбранной строки. Эта процедура повторяется для всех строк таблицы истинности до полного заполнения карты Карно.
Пусть, например, требуется в карте Карно найти клетку, соответствующую строке 3 таблицы истинности 1. В этой строке находятся следующие значения переменных: Х3 = 0, Х2 = 1 Х1 =1. На карте Карно (рисунок 2) выделяются области (инверсное значение потому, что Х3 = 0) - красным цветом (область 1), Х2 - синим цветом (область 2), Х1 - зелёным цветом (область 3). Общей клеткой для всех трех областей будет клетка, выделенная желтым цветом. В эту клетку и проставляется значение функции. Для рассматриваемой комбинации переменных оно равно 1.
Если функция задана аналитическим выражением, то порядок заполнения карты Карно следующий. Сначала функцию приводят к дизъюнктивной нормальной форме, т.е. форме, где инверсии стоят только над отдельными переменными. Это можно сделать, используя теоремы и тождества алгебры логики. Конъюнкции полученного выражения могут содержать от одной переменной до всех используемых в данном случае переменных. Каждая конъюнкция полученного выражения - это конкретная группа клеток карты Карно, в которых должны находиться 1. Такая группа клеток находятся в зоне пересечения областей переменных (одновременно принадлежат областям переменных) входящих в рассматриваемую конъюнкцию. Процедура установки единиц применяется для всех конъюнкций заданного выражения. Если в клетке уже установлена единица при заполнении по предыдущим конъюнкциям, то единица остаётся.
В остальные клетки, где не установлены единицы, устанавливаются нули.
Например, необходимо заполнить карту Карно для выражения ƒ(ν) = . В это выражение входит сложная конъюнкция . Применяя для неё правило де Моргана, получим = . В дизъюнктивной нормальной форме заданная функция имеет вид ƒ(ν) = и состоит из трёх конъюнкции. Первая конъюнкция включает в себя одну переменную , значит, единицы устанавливаются в клетках, которые принадлежат области . Карта Карно для этой конъюнкции с проставленными 1 показана на рисунке 3 а). Вторая конъюнкция включает в себя две переменные: и , значит, единицы устанавливаются в клетках, которые одновременно принадлежат областям (находятся на пересечении областей) и . Карта Карно для этой конъюнкции с проставленными 1 показана на рисунке 3 б). Третья конъюнкция включает в себя три переменные: , , , значит, единицы устанавливаются в клетках, которые одновременно принадлежат областям (находятся на пересечении областей) , и . Карта Карно для этой конъюнкции с проставленными 1 показана на рисунке 3 в).
При наложении друг на друга всех этих трех карт Карно получится карта, показанная на рисунке 4 а). После проставления 0 в оставшиеся пустые клетки, получится полностью заполненная карта Карно, которая и показана на рисунке 4 б).
После заполнения карты Карно начинается минимизации. В процессе минимизации все клетки, содержащие 1 (либо 0) должны быть объедены в группы.
В группы объединяются соседние клетки, содержащие 1 (либо 0) и образующие прямоугольники или квадрат. Группа должна содержать 2 n клеток (n = 0, 1, 2, 3 и т. д), иными словами 1, 2, 4, 8, 16 и т.д. клеток. Причем нужно стремиться, чтобы групп было как можно меньше, и для достижения этого включать в каждую группу максимально возможное число клеток. Процесс создания групп продолжается до тех пор, пока все клетки не будут объединены в группы. Клетки с 1 (либо 0 ), которые невозможно объединить с другими, образуют группы с числом клеток 1. Одна и та же клетка может входить в несколько групп.
При определении соседних клеток карту Карно можно сворачивать в рулон по горизонтали и по вертикали. В карте Карно на рисунке 1.8в) например, соседними будут клетки 2 и 10; 1, 5, 9 и 13; а также 0, 4, 8 и 12!
Равнозначных вариантов объединения клеток может быть несколько.
Минимизированную функцию записывают в дизъюнктивной нормальной форме (ДНФ) или в конъюнктивной нормальной форме (КНФ). Чаще используется ДНФ. В ДНФ минимизированная функция имеет вид
при объединении клеток с единицами:
при объединении клеток с нулями:
,
где Сi – конъюнкция для i – ой группы; m – количество групп.
В выражение конъюнкции входят те переменные с инверсией или без инверсии (но не одновременно), в области которых i – ая группа находится вся целиком.
Для определения областей, в которых группа находится целиком, можно предложить следующий алгоритм.
Мысленно или фигурально (например, куском бумаги, вырезанным по размеру области карты Карно) закрывается одна из областей переменных карты Карно. Если рассматриваемая группа клеток карты Карно полностью закрылась и не высовывается из-за закрытой области, значит, данная переменная входит в выражение конъюнкции для рассматриваемой группы клеток. Эта действие повторяется для всех областей карты Карно. Например, у карты Карно четырех переменных это -
Например, необходимо определить, в каких областях переменных полностью находится группа клеток с 1, показанная на рисунке 5.
Последовательно закрывая области переменных , получим картину, показанную на рисунке 6.
Из этого рисунка видно, что группа клеток с 1 полностью закрыта только на рисунках в) и е), на рисунках а) и б) она закрыта только частично, а на рисунках г ) и д) не закрыта вообще. Это значит, что конъюнкция для этой группы клеток будет содержать переменные , т. е. будет иметь вид .
Если вырожденная (не для всех переменных определенная) функция задана таблицей истинности, то при заполнении карты Карно в клетки, для которых функция не определена, устанавливают такие значения функции, которые позволяют получить минимальное конечное аналитическое выражение функции. Часто в такие клетки при заполнении карты Карно ставят крестик (Х).
Порядок минимизации функции с помощью карты Карно следующий:
1) Используя таблицу истинности или аналитическое выражение функции, заполняют карту Карно;
2) В карте Карно создаются группы, объединяющие клетки с 1(или с 0). Принципиальной разницы между минимизацией функции по 1 или по 0 нет. Выбирается вариант, при котором функция имеет минимальное выражение;
3) Записывают минимизированное выражение функции в выбранной форме.
Раздел: Математика
Количество знаков с пробелами: 9534
Количество таблиц: 1
Количество изображений: 6
- Для учеников 1-11 классов и дошкольников
- Бесплатные сертификаты учителям и участникам
1. По таблице истинности составить СДНФ логической функции.
2. Произвести минимизацию логической функции методом непосредственных преобразований, применением законов и следствий алгебры логики, карт Карно.
1. Записываем СДНФ согласно правилу :
1) По каждому набору двоичных переменных, при котором функция принимает значение 1, составляем минтермы.
2) В минтермах переменные, равные единицы, записываются без изменения, а равные нулю – инвертированными.
3) Все минтермы соединить знаком дизъюнкции.
2. Произведём минимизацию логической функции методом непосредственных преобразований:
Построим карту Карно :
Функция принимает вид :
Результаты, полученные двумя способами, совпали.
Элемент "И-НЕ" реализуем на ДТЛ (рис. 1). Элемент "НЕ" реализуем на одном транзисторе. Функцию "ИЛИ" реализуем на ЭСЛ.
Вариант реализации схемы на элементах ДТЛ и ЭСЛ дан на рис. 2.
Функция имеет вид :
Схема реализации функции на элементах на логических элементах 2И, НЕ, 2ИЛИ приведена на рис. 3.
- подготовка к ЕГЭ/ОГЭ и ВПР
- по всем предметам 1-11 классов
Курс повышения квалификации
Охрана труда
Курс профессиональной переподготовки
Охрана труда
Курс профессиональной переподготовки
Библиотечно-библиографические и информационные знания в педагогическом процессе
- Сейчас обучается 353 человека из 64 регионов
- ЗП до 91 000 руб.
- Гибкий график
- Удаленная работа
Дистанционные курсы для педагогов
Свидетельство и скидка на обучение каждому участнику
Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:
5 595 243 материала в базе
Самые массовые международные дистанционные
Школьные Инфоконкурсы 2022
Свидетельство и скидка на обучение каждому участнику
Другие материалы
Вам будут интересны эти курсы:
Оставьте свой комментарий
- 17.02.2022 10
- DOCX 739 кбайт
- 0 скачиваний
- Оцените материал:
Настоящий материал опубликован пользователем Долонов Александр Сергеевич. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Автор материала
40%
- Подготовка к ЕГЭ/ОГЭ и ВПР
- Для учеников 1-11 классов
Московский институт профессиональной
переподготовки и повышения
квалификации педагогов
Дистанционные курсы
для педагогов
663 курса от 690 рублей
Выбрать курс со скидкой
Выдаём документы
установленного образца!
Учителя о ЕГЭ: секреты успешной подготовки
Время чтения: 11 минут
В ростовских школах рассматривают гибридный формат обучения с учетом эвакуированных
Время чтения: 1 минута
Время чтения: 2 минуты
Минобрнауки и Минпросвещения запустили горячие линии по оказанию психологической помощи
Время чтения: 1 минута
Ленобласть распределит в школы прибывающих из Донбасса детей
Время чтения: 1 минута
В Белгородской области отменяют занятия в школах и детсадах на границе с Украиной
Время чтения: 0 минут
Минпросвещения России подготовит учителей для обучения детей из Донбасса
Время чтения: 1 минута
Подарочные сертификаты
Ответственность за разрешение любых спорных моментов, касающихся самих материалов и их содержания, берут на себя пользователи, разместившие материал на сайте. Однако администрация сайта готова оказать всяческую поддержку в решении любых вопросов, связанных с работой и содержанием сайта. Если Вы заметили, что на данном сайте незаконно используются материалы, сообщите об этом администрации сайта через форму обратной связи.
Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.
Литература. Метод Квайна — Мак-Класки. Методы синтеза последовательностных схем. Минимизация логических функций1. 1. Минимизация логических функций по картам Карно. Синтез КС с учётом ограничений на. Введение. Синтез КС с учётом ограничений на. Методы синтеза комбинационных и последовательностных схем2. 1. Канонический метод синтеза комбинационных схем. Заключение. Читать ещё >
Минимизация логических функций. Методы синтеза комбинационных и последовательностных схем ( реферат , курсовая , диплом , контрольная )
Содержание
- Введение
- 1. Минимизация логических функций
- 1. 1. Минимизация логических функций по картам Карно
- 1. 2. Метод Квайна — Мак-Класки
- 2. 1. Канонический метод синтеза комбинационных схем
- 2. 2. Синтез КС с учётом ограничений на
- 2. 3. Синтез КС с учётом ограничений на
- 2. 4. Методы синтеза последовательностных схем
При проектировании схем, выполняющих ту или иную логическую функцию, необходимо обеспечить минимизацию аппаратных затрат на реализацию этих схем, а также во многих случаях необходимо сократить номенклатуру используемых логических элементов. Последнее требование реализуется путем выбора соответствующей системы элементов.
Проблема минимизации логических функций решается на основе применения законов склеивания и поглощения с последующим перебором получаемых дизъюнктивных форм и выбором из них оптимальной (минимальной). Существует большое количество методов минимизации ЛФ. Все они отличаются друг от друга спецификой применения операций склеивания и поглощения, а также различными способами сокращения переборов. Среди аналитических методов наиболее известным является метод Квайна-Маккласки, среди табличных — метод с применением диаграмм Вейча. Графические методы минимизации отличаются большей наглядностью и меньшей трудоемкостью. Однако их применение эффективно при малом числе переменных п Богданова Б. К. и статьи из сети Инернет.
Читайте также: