Учебно-методический комплекс дисциплины обсужден на заседании кафедры информационной безопасности «7»

Минимизация логических функций методом квайна Метод Квайна относится к числу таких методов минимизации функции алгебры логики, которые позволяют представлять функции в ДНФ или КНФ с минимальным числом членов и минимальным числом букв в членах. Этот метод содержит два этапа преобразования выражения функции: на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращенной форме, на втором этапе—переход от сокращенной формы логического выражения к минимальной форме.   Первый этап (получение сокращенной формы). Пусть заданная функция f представлена в СДНФ. Переход к сокращенной форме основан на последовательном применении двух операций: операции склеивания и операции поглощения. Для выполнения операции склеивания выявляются в выражении пары членов вида и , различающихся лишь тем, что один из аргументов в одном из членов представлен без инверсии, в другом—с инверсией. Затем проводится склеивание таких пар членов: , и резуль-таты склеивания w вводятся в выражение функции в качестве дополнительных членов. Далее проводится операция поглощения. Она основана на равенстве (член w поглощает член w? z). При проведении этой операции из логического выражения вычеркиваются все члены, поглощаемые членами, которые введены в результате проведения операции склеивания. Операции склеивания и поглощения проводятся последовательно до тех пор, пока их выполнение оказывается возможным. Покажем выполнение этих операций применительно к функции, представленной в табл. 3.5. Записываем СДНФ функции (3.12) Попарным сравнением членов (каждого из членов со всеми последующими) выявляем склеивающиеся пары членов: первый и четвертый члены (результат склеивания ); второй и третий члены (результат склеивания ); второй и четвертый члены (результат склеивания ); третий и пятый члены (результат склеивания ). Таблица 3.5 x1 0 0 0 0 1 1 1 1 x2 0 0 1 1 0 0 1 1 x3 0 1 0 1 0 1 0 1 f(x1,x2,x3) 0 0 1 1 0 1 0 1 Результаты операции склеивания вводим в выражение функции и проводим операцию поглощения ими членов исходного выражения: Член поглощает те члены исходного выражения, которые содержат, т. е. первый и четвертый. Эти члены вычеркиваются. Член поглощает второй и третий, а член x1? x3 – пятый член исходного выражения. Повторяем операции склеивания и поглощения:  Член операции склеиванияЗдесь склеивается лишь пара членов и , (склеивание пары членов и , приводит к тому же результату), результат склеивания х1, поглощает второй, третий, четвертый и пятый члены выражения. Дальнейшее проведение операций склеивания и поглощения оказывается невозможным, сокращенная форма выражения заданной функции (в данном примере она совпадает с минимальной формой) (3.13) Члены сокращенной формы (в рассмотренном примере такими членами служат и х1 называются простыми импликантами функции. Как видим, получено выражение существенно более простое по сравнению с СДНФ функции. На рис. 3.27 приведена структурная схема логического устройства в базисе И, ИЛИ, НЕ, построенная с использованием выражения (3.13). Второй этап (получение минимальной формы). Сокращенная форма может содержать лишние члены, исключение которых из выражения функции не повлияет на значение функции. Таким образом, дальнейшее упрощение логического выражения достигается исключением из выражения лишних членов. В этом и заключается содержание второго этапа минимизации. Покажем этот этап минимизации логического выражения на примере построения логического устройства для функции в табл. 3.6. рис 3.27 Таблица 3.6 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 1 Совершенная ДНФ.данной функции (3.14) Для получения сокращенной формы проводим операции склеивания и поглощения. Полученное выражение представляет собой сокращенную форму логического выражения заданной функции, а члены его — простые импликанты функции. Переход от сокращенной формы к минимальной осуществляется с помощью импликантной матрицы, приведенной в табл. 3.7. В столбцы импликантной матрицы вписываются члены СДНФ заданной функции, в строки — простые импликанты функции, т. е. члены сокращенной формы логического выражения функции. Таблица 3.7 Простые импликанты Члены СДНФ X X X X X X X X X X Отмечаются (например, крестиками) столбцы членов СДНФ, поглощаемых отдельными простыми импликантами. В табл. 3.7 простая импликанта поглощает члены , , и в первом и во втором столбцах первой строки поставлены крестики; вторая импликанта поглощает первый и третий члены СДНФ, и поставлены крестики в первом и третьем столбцах второй строки и т. д. Импликанты, которые не могут быть лишними и, следовательно, не могут быть исключены из сокращенной формы, составляют ядро. Входящие в ядро импликанты легко определяются по импликантной матрице. Для каждой из них имеется хотя бы один столбец, перекрываемый только данной импликантой. В рассматриваемом примере ядро составляют импликанты и, (только ими перекрываются второй и шестой столбцы матрицы). Исключение из сокращенной формы одновременно всех импликант, не входящих в ядро, невозможно, так как исключение одной из импликант может превратить другую уже в нелишний член. Для получения минимальной формы достаточно выбрать из импликант, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждой из этих импликант, которое обеспечит перекрытие всех столбцов импликантной матрицы, не перекрытых членами ядра. В рассматриваемом примере необходимо импликантами, не входящими в ядро, перекрыть третий и четвертый столбцы матрицы. Это может быть достигнуто различными способами, но так как необходимо выбирать минимальное число импликант, то, очевидно, для перекрытия этих столбцов следует выбрать импликанту . Минимальная дизъюнктивная нормальная форма (МДНФ) заданной функции (3.16)

Похожие:

	Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс дисциплины составлен на основании требований государственного образовательного стандарта высшего профессионального...		Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Системы и сети связи 090104. 65 – Комплексная защита объектов информатизации Форма подготовки очная
	Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Защита информационных процессов в компьютерных системах 090104. 65 – Комплексная защита объектов информатизации Форма подготовки...		Учебно-методический комплекс дисциплины Туризм, утвержденного приказом Министерства образования и науки РФ от 20. 01. 2006 г. №739гум/бак. Учебно-методический комплекс обсужден...
	Учебно-методический комплекс дисциплины «Формальности проживания в гостинице» Туризм, утвержденного приказом Министерства образования и науки РФ от 20. 01. 2006 г. №739гум/бак. Учебно-методический комплекс обсужден...		Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс составлен в соответствии с требованиями государственного образовательного стандарта высшего профессионального...
	Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс составлен в соответствии с требованиями государственного образовательного стандарта высшего профессионального...		Учебно-методический комплекс дисциплины обсужден на заседании кафедры «Финансы и кредит» Учебно-методический комплекс составлен в соответствии с требованиями государственного образовательного стандарта высшего профессионального...
	Учебно-методический комплекс дисциплины организация работы гостиниц 100200. 62 «Туризм» Туризм, утвержденного приказом Министерства образования и науки РФ от 20. 01. 2006 г. №739гум/бак. Учебно-методический комплекс обсужден...		Учебно-методический комплекс дисциплины обсужден на заседании кафедры компьютерных систем «03» Учебно-методический комплекс составлен в соответствии с требованиями федерального государственного образовательного стандарта высшего...
	Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс составлен в соответствии с требованиями федерального государственного образовательного стандарта высшего...		Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс составлен в соответствии с требованиями государственного стандарта высшего профессионального образования...
	Проект) (КР,КП), Расчётно-графическая работа (ргр) Домашнее задание... Учебно-методический комплекс дисциплины обсуждён и утверждён на заседании кафедры «Гидротехнические сооружения»		Учебно-методический комплекс составлен на основании требований государственного... Учебно-методический комплекс дисциплины обсуждена на заседании кафедры Информационные системы управления «29» июня 2011 г
	Учебно-методический комплекс дисциплины материаловедение направление... Учебная программа обсуждена на заседании кафедры технологии и предпринимательства		Учебно-методический комплекс Наименование дисциплины Аритмология... Переутверждено на заседании кафедры госпитальной хирургии с курсом детской хирургии