Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Топ:
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Интересное:
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Дисциплины:
2017-12-21 | 376 |
5.00
из
|
Заказать работу |
|
|
Каждую логическую функцию можно представить в виде полинома Жигалкина, представляющего собой элементарные конъюнкции соединены операцией исключающего или Å. Например: f(x,y,z) = (y & z) Å (x & z) Å (x & y & z)
Процедура построения Полинома Жигалкина
По таблице истинности строим СДНФ.
СДНФ приводим к минимальной ДНФ
Выражаем дизъюнкции Ú и отрицания ù через операции конъюнкции & и исключающего или Å.
x Ú y = x Å y Å (x & y) ù x = x Å 1
4) Раскрываем скобки используя дистрибутивность x & (y Å z) = (x & y) Å (x & z), (x Å y) & z = (x & z) Å (y & z). В результате могут получится формула двух видов
(xa & xb &...) Å... Å (xc & xd &...) или (xa & xb &...) Å... Å (xc & xd &...) Å 1
Сокращаются повторяющиеся элементы внутри скобок при помощи a&a=a, a&1=a, 1&a=a
Сокращаются одинаковые скобки при помощи поглощения aÅa=0, aÅ0=a, 0Åa=a.
Пример: построение полинома Жигалкина
Пусть для функции получена минимальная ДНФ:
f(x,y,z) = ( ù x & y & z) Ú (x & ù z)
Используя ù a = a Å 1 заменим отрицание:
f(x,y,z) = ((x Å 1) & y & z) Ú (x & (z Å 1))
Используя a Ú b = a Å b Å (a & b) заменим дизъюнкцию:
f(x,y,z) = ((x Å 1) & y & z) Å (x & (z Å 1)) Å ((x Å 1) & y & z & x & (z Å 1))
Используя дистрибутивность раскроем скобки:
f(x,y,z) = (x & y & z) Å (1 & y & z) Å (x & z) Å (x & 1) Å
Å (x & y & z & x & z) Å (1 & y & z & x & z) Å
Å (x & y & z & x & 1) Å (1 & y & z & x & 1)
Применим законы поглощения внутри скобок:
f(x,y,z) = (x & y & z) Å (y & z) Å (x & z) Å x Å (y & x & z) Å
Å (y & x & z) Å (y & z & x) Å (y & z & x)
Применим законы поглощения для одинаковых скобок
f(x,y,z) = (x & y & z) Å (y & z) Å (x & z) Å x
|
Классы логических функций: сохраняющие 0, сохраняющие 1, монотонные, линейные, двойственные, самодвойственные. Критерий поста.
Классы логических функций
Класс S0: Функции «сохраняющие 0» - это логические функции, значение которых равны 0, если все аргументы равны 0: f(0,0,...,0)=0. Например Ú
Класс S1: Функции «сохраняющие 1» - это логические функции, значение которых равны 1, если все аргументы равны 1: f(1,1,...,1)=1. Например &
Класс M: "Монотонные" функции -это логические функции, которые можно выразить через & и Ú.
Монотонную функцию можно распознать по ее таблице истинности. Для этого нужно взять все пары наборов переменных, которые отличаются всего в одном столбце. Например: 0,0,0,0 и 0,0,0,1; 1,0,0,1 и 1,1,0,1. Пусть в одном наборе переменных в некотором столбце стоит "0", а в другом наборе переменных в этом же столбце стоит "1". Нельзя, чтобы значение функции при этих наборах было "1", а потом "0" соответственно. Пример монотонной функции: Ú.
Наборы переменных Значение функций
00; 01 0; 1
00; 10 0; 1
01; 11 1; 1
10; 11 1; 1
Класс L:"Линейные" функции – это логические функции, которые можно выразить через Å, 0 и 1.
Чтобы узнать, линейна ли функция, надо выразить ее через полином Жегалкина и посмотреть, не встречается ли там операция &. Если нет, то функция линейна.
Класс D: «Двойственные» функции f и g, т.е. функции
удовлетворяющие условию f(ù x1, ù x2,..., ù xN) = ù g(x1,x2,...,xN)
Двойственные функции легко обнаружить с помощью простого приема. Надо заменить в таблице истинности все "0" на "1", а все "1" на "0". Полученная таблица истинности и будет таблицей двойственной функции. Пример & и Ú.
Класс S:"Самодвойственные" функции, т.е. функции, которые двойственны сами себе:
f(ù x1, ù x2,..., ù xN) = ù f(x1, x2,..., xN).
Критерий Поста
Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов S0, S1, S, L, M. T.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
|
Упрощение СДНФ при помощи Карты Карно. Булева алгебра и коммутационные схемы. Анализ и синтез коммутационных схем. Проектирование полубитного сумматора.
|
|
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!