Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Интересное:
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Дисциплины:
2017-11-22 | 246 |
5.00
из
|
Заказать работу |
Максимальный интервал Ia, который не содержится ни в каком другом интервале Ia Ë Iк
где Iк - все интервалы функции, кроме Ia.
Рассмотрим функцию, заданную в СНФК:
N | Ki | F |
В левой части двоичный эквивалент конституент,а в правой присутствует ли она в функциональном представлении или нет.
Кроме интервалов,представленные конституентами выделим другие интервалы более крупные.
001 0х1
011 х11
100 1х0 - максимальные интервалы относительно конституент.
110 11х
Лемма.
Если в представление функции включен не максимальный интервал, то этот интервал может быть преобразован с помощью вычеркивания первичных термов.
Доказательство:
Исходя из определения, в функциональном представлении присутствует интервал, содержащий не максимум,а состоящий из некоторых первичных термов не максимальный интервал. Следовательно, максимальный интервал мажет быть получен вычеркиванием незначительных термов из немаксимального интервала.
М = А + В = А + В
В – максимальный интервал
В Ì В - не максимальный интервал
Вычеркиванием терма – получим максимальный интервал.
Тупиковой формой –называется нормальная форма Кантора, из которой не может быть вычеркнут ни один терм без изменения представления функции.
Минимальной формой – называется тупиковаяформа, минимальной сложности
Выражения для максимальных интервалов называются простыми импликантами.
ТЕОРЕМА.
Все тупиковые,а следовательно и минимальные формы содержатся в объединении всех простых импликант.
Доказательство:
Из определения следует,что если вНФК присутствует неминимальный интервал,то она не является тупиковой и не является минимальной.
Следовательно, тупиковой и минимальной формой есть объединение некоторых простых импликант из множества всех простых импликант.
Согласно вышеуказанной теореме 1-й шаг метода Квайна состоит в выделении простых импликант функции и составлении таблицы.
Строки соответствуют простым импликантам.
Столбцы – конституентам функции.
0х1 | |||||
х11 | |||||
1х0 | |||||
11х |
Если конституента содержится соответственном максимальном интервале, то в клетке ставится 1, если нет, то клетка остаётся пустой.
2-й шаг
Состоит в том, что из множества простых импликант составляются всевозможные подмножества, обладающие свойствами:
1. Элементы подмножества суммарно покрывают все конституенты функции.
2. При вычеркивании любого элемента подмножества свойство 1 не выполняется.
Подмножество, удовлетворяющее свойствам называется минимальными покрытиями таблицы Квайна.
ТЕОРЕМА
Возможные минимальные покрытия таблицы Квайна представляют все тупиковые формы функционального представления, среди которых содержатся и минимальные формы.
Доказательство:
Необходимость следует из того, что тупиковые и минимальные формы есть объединение простых импликант. Достаточность следует из того, что не возможно вычеркнуть простую импликанту, а следовательно любой первичный термин, без нарушения покрытия всех конституент функции.
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!