выш мат. Алексеев-В.В.-Алгебра-логики. Инистерство образования и науки российской федерации
 Скачать 6.59 Mb.
|
|
Отсюда получаем: . 2.5 Метод минимизирующих карт (Карты Карно) Один из способов графического представления ФАЛ от небольшого числа переменных - использование карт Карно. Их разновидность - карты Вейча, которые строят как развертки кубов на плоскости. При этом вершины куба представляются клетками карты, координаты которых совпадают с координатами соответствующих вершин куба. Карта Карно заполняется также, как таблица истинности: В каждой клетке, соответствующей набору, проставляется значение функции. Переменные размещаются на карте так, что при переходе из одной клетки в любую соседнюю, должна изменяться только одна переменная. Нижний ряд карты следует рассматривать как примыкающий к верхнему ряду, а левый ряд - к правому. Карты Карно для: 2-х переменных 3-х переменных 4-переменных. Если требуется получить карту Карно для какой-нибудь функции, то сначала записывают эту функцию в НДФ. Каждый член, который появляется в этой форме, задается на карте Карно с помощью 1 в соответствующей клетке. Затем группируют единицы в соответствующих полях, очерчивая их замкнутыми линиями. При изучении карты с очерченными полями оказывается, что если две соседние клетки содержат 1, то из них всегда можно удалить одну переменную, а именно ту переменную, для которой ее инверсия располагается в следующей соседней клетке. Рассмотрим примеры для функций 2-х, 3-х и 4-х переменных. 1. . Имеем следующую карту Карно: И тогда в минимальной форме функцию можно представить как: . 2. Для этой функции карта Карно будет иметь вид: После минимизации получаем: . 3. . Получаем: 4. Вполне очевидно, что логическую функцию в последнем примере можно представить в минимальной форме и другими вариантами, объединяя ”1” по иному. Карты Карно для числа переменных n>4 составляются из идентичных (в смысле обозначения сторон первичными термами) карт для четырех переменных. Две карты Карно для четырех переменных будем называть соседними, если они имеют общую грань. Клетки, расположенные в одинаковых местах соседних карт для четырех переменных, являются соседними, т.к. им соответствуют соседние минтермы. Например, для n=5 Соседними клетками здесь являются: 0 и 16, 1 и 17, 7 и 23, 14 и 30, 8 и 24 и т.п. При n=6 имеем: Здесь соседними являются клетки: 0 и 32, 0 и 16, 5 и 37, 5 и 21, 14 и 30, 14 и 46 и т.п. Но 0 и 48, 18 и 34, 15 и 63 и т.п. не являются соседними. Пример. Минимизировать ФАЛ: В соответствии с вышеизложенным получаем карту Карно, вид которой представлен на рис. 2.4. И в результате минимизации получим: = = . Вполне очевидно, что располагая поля переменных иным образом, но соблюдая правила составления карт Карно, должна получиться такая же минимальная функция. (По числу термов и их длине). Рис. 2.4. Пример. Минимизировать ФАЛ: Заполняя карту Карно для n=6 получаем: Результат минимизации будет представлен в данном случае как: . Карты Карно используют и для получения минимальных КНФ. Это вытекает из принципа двойственности и законов двойственности. Покажем это на примере. Пусть имеем ФАЛ . Минимизируя с помощью карты Карно (рис.2.5) получаем: . Тогда имеет место в данном случае следующее соотношение: , откуда на основании двойственности получаем: . Рис. 2.5. 2.6 Минимизация не полностью определенных функций Основная задача минимизации не полностью определенных функций заключается в отыскании оптимального варианта ее доопределения, позволяющего получить минимальную из всех возможных ДНФ или КНФ. Если значения функции не заданы в m точках, то ее можно доопределить способами. СНДФ не полностью определенной функции можно представить в виде: =, где , - номера наборов, при которых функция определена и равна ”1”; - номера наборов при которых функция имеет не доопределенное значение (f=). Пример. Пусть необходимо минимизировать не полностью определенную ФАЛ, имеющей вид: . Для данной функции имеем следующую карту Карно: ` И тогда доопределяя карту Карно (а равно и функцию) получаем следующую минимизированную функцию: или Глава 3 Приложения алгебры логики 3.1. Логические элементы и их применение Одним из самых широких приложений алгебры логики является разработка дискретных, цифровых устройств различного назначения и, в частности, средств вычислительной техники. Техническим аналогом элементарных логических функций являются логические элементы (ЛЭ), представляющие собой физические устройства, выполняющие логические операции над сигналами, представленными в физической форме. Т.е. в этих устройствах логические единица и нуль представлены физическими сигналами различной величины, одна из величин соответствует логической единице, другая – логическому нулю. Например, различные величины давления: р1 и р2 (пневматические или гидравлические логические элементы); различные величины интенсивности освещения: s1, s2 (оптические или оптоэлектронные логические элементы). Но доминирующее значение в технике имеют электронные логические элементы, которые представляют собой определенные электронные схемы, реализующие логические операции над логическими переменными, представленными в этом случае в виде электрических сигналов. Имеет место несколько способов представления логических единицы и нуля в виде электрических сигналов, но преимущественно используется потенциальный способ представления логических переменных, при котором значениям логической единицы и нуля соответствуют вполне определенные уровни напряжения: U1 и U0. Потенциальные логические элементы (схемы) в настоящее время составляют основу системы изделий микроэлектроники для цифровой, вычислительной техники. Они представлены в виде серии микросхем различных степеней интеграции, предназначенных для построения цифровых устройств различного назначения, и в частности – ЭВМ различных классов. По виду реализуемой логической функции основные логические элементы условно разделяют на элементы одноступенчатой логики, реализующие функции И (конъюнкция), ИЛИ (дизъюнкция), НЕ (отрицание), И-НЕ, ИЛИ-НЕ, и на элементы двухступенчатой логики, реализующие функции И-ИЛИ, ИЛИ-И, И-ИЛИ-НЕ, ИЛИ-И-НЕ, И-ИЛИ и т.п. Число входов ЛЭ соответствует числу входных переменных, воспроизводимой им логической функции. На основании вышеизложенного вполне очевидно, что любой функции алгебры логики можно сопоставить соответствующую логическую схему, составленную из соответствующих логических элементов. Схема, значение выходного сигнала которой определяется только комбинацией входного сигнала, называется комбинационной. Для набора логических элементов можно ввести понятие функциональной полноты, подобно тому, как это было сделано для случая ФАЛ. Набор ЛЭ обладает функциональной полнотой, если с помощью этого набора можно реализовать схему с любым законом функционирования. Т.е. любая комбинационная схема может быть построена с применением логических элементов типа И, ИЛИ, НЕ, совокупность которых является функционально полной системой (т.е. базисом), а также и из элементов типа И-НЕ (функция ), или из элементов типа ИЛИ-НЕ (функция ), или из элементов типа И-ИЛИ-НЕ (функция ), каждая из которых представляет функционально полною систему. Принятые условные обозначения некоторых основных ЛЭ приведены в таблице 3.1. Промышленно выпускаемые логические элементы имеют ограниченное количество входов (коэффициент разветвления по входу в большинстве случаев равен 2, 3, 4, 8) и ограниченную нагрузочную способность. Но имеются известные схемотехнические решения увеличения коэффициента разветвления по входу и выходу, и которые, к сожалению, увеличивают и логическую глубину схемы, тем самым ухудшая временные и другие характеристики схемы в целом. Практическая реализация логических схем осуществляется, как правило, с применением интегральной схемотехники, среди которой наиболее широкое распространение получили элементы потенциального типа, логические переменные 0 и 1 в которых, как уже отмечалось, отображаются двумя уровнями напряжения: U0 и U1 соответственно. Для логического описания цепей не требуются абсолютные значения U0 и U1. Необходимо лишь условиться, какой из них отображает логический нуль и какой - логическую единицу. Таблица 3.1
|