Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Представление логических функций (ЛФ)
СДНФ переключательной функции записывается по таблице истинности. Для того чтобы по таблице истинности построить СДНФ, надо каждому набору переменных, на котором ЛФ принимает единичное значение, поставить в соответствие элементарную конъюнкцию ранга п и все эти конъюнкции соединить дизъюнктивно; в каждой конъюнкции СДНФ с отрицанием берутся те переменные, которые на соответствующем этой конъюнкции наборе имеют нулевое значение. Используя это правило, запишем в СДНФ функции f1 и f2 трех переменных, заданных таблице 3.13. Таблица 3.13
В результате получим следующие выражения: Для получения f1 используем 2, 4 и 6 строки f1 = + х2 (3.1) Для получения f2 используем 1, 7 и 8 строки. f2 = + х2 + х1 х2 х3 (3.2)
Элементарные конъюнкции СДНФ называют конституантами (составляющими) единицы, так как они соответствуют наборам, при которых ЛФ принимает значения 1. После составления выражения для f1 можно построить из логических элементов И, ИЛИ, НЕ функциональную схему, которая будет вычислять значение ЛФ f1. Чтобы построить функциональную схему для ЛФ, записанной в СДНФ, надо взять k ЛЭ И на n входов каждая, где k — число конъюнкций СДНФ, и объединить выходы схем И с помощью элемента ИЛИ на k входов. Для ЛФ f1 функциональная (или логическая) схема приведена на рис. 3. 6 (на схеме не показаны лишь элементы НЕ, с помощью которых получаются инверсные значения переменных х1 и x2). Рисунок 3.6 Рисунок 3.7 Для каждой функциональной схемы можно сделать оценку ее сложности, которая выражается ценой схемы С (по Квайну). Цена С определяется суммарным числом входов логических элементов. Чем меньше величина С, тем проще функциональная схема. Если ЛФ задана в СДНФ, ее цену можно выразить формулой: С = kn + k. Для ЛФ f1 - k = 3 -число конъюнкций, а n = 3 –число входов (х1 х2 х3). Тогда С = 3 х 3 + 3 = 12 Используя правило склеивания (ПРАВИЛО 11), можно упростить ЛФ, заданную в СДНФ. Для этого в СДНФ сначала склеиваются между собой конъюнкции ранга п, затем полученные конъюнкции ранга (n — 1), (n — 2), и так до тех пор, пока в выражении для ПФ не останется ни одной пары склеиваемых между собой конъюнкций. Операция склеивания позволяет понизить ранг конъюнкций и сократить их число. В результате уменьшается цена функциональной схемы.
Например, в выражении f1 = + х2 выполним склеивание: -конъюнкций и х2 по переменной х2, получим: ; -и конъюнкций и по переменной х1 , получим: . В результате функция f1 преобразуется к виду f1 = + (3.3) Функциональная схема, реализующая ЛФ f1 по выражению (3.3), изображена на рис. 3.7. Цена этой схемы С = 6, т. е. по сравнению с эквивалентной схемой на рис. 3.8 цена уменьшилась в 2 раза. В результате попарного склеивания конъюнкций ранга п, а далее (п — 1), (п — 2) и т. д., в выражении для ЛФ остаются конъюнкции, которые между собой не склеиваются. Конъюнкция, которая не склеивается ни с какой другой конъюнкцией ДНФ, называется простой импликантой. В выражении (3.3) конъюнкции не склеиваются между собой, т. е. они являются простыми импликантами. ДНФ, представляющая собой дизъюнкцию простых импликант, называется сокращенной ДНФ.
Понятие суперпозиции Суперпозиция - есть подстановка в логическую формулу вместо переменных, других булевых выражений. С помощью суперпозиции можно получить более сложные функции любого числа переменных. Пример: Если F = X1 v X2 и X1 =Z1Z2; Х2 = Z3 v Z4, тогда Y = Z1 Z2 v Z3 v Z4. Система функций, суперпозицией которых может быть представлена любая булева функция, называется функционально полной; она образует базис в логическом пространстве. Систему функций называют минимально полным базисом, если удаление из нее любой функции превращает эту систему в неполную. В теории алгебры логики доказано, что функционально полные системы образуют следующие наборы функций: 1. , Х1 v Х2, Х1 Х2 - НЕ, ИЛИ и И - булев базис, избыточный; 2. , Х1 v Х2 - НЕ и ИЛИ; 3. , Х1 Х2 - НЕ и И; 4. ; - И-НЕ; 5. - ИЛИ-НЕ и др.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2017-01-19; просмотров: 326; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.152.77.92 (0.105 с.) |