Главная > Документ


Пример 4.1

Минимизировать методом Квайна – Мак-Класки неполностью определенную ФАЛ, заданую в следующем виде:

f(a,b,c,d) = (0,5,8,12,15), Х(1,2,3,10.13,14)

Решение

Этап 1. Найти рассмотренным выше способом сокращенную ДНФ для функции

f(a,b,c,d)СДНФ = (0,1,2,3,5,8,10,12,13,14,15)

0000*

000-*

00--

0001*

00-0*

-0-0

0010*

-000*

1--0

1000*

00-1*

11--

0011*

0-01

0101*

001-*

1010*

-010*

1100*

10-0*

1101*

1-00*

1110*

-101

1111*

1-10*

110-*

11-0*

11-1*

111-*

Сокращенная дизъюнктивная нормальная форма этой ФАЛ имеет вид:

f(a,b,c,d)СкДНФ = ¯a v v a¯ v a b v ¯a ¯c d v b ¯c ¯ d

Этап 2.

Составить импликантную матрицу для этой функции:

0000

0101

1000

1100

1111

00--

+

-0-0

+

+

1—0

+

+

11--

+

+

0-01

+

-101

+

Обратим внимание на то, что в этой таблице строка, имеющая в заголовке импликанту с k символами ";-";, не обязательно содержит 2k помеченных ячеек. Также в таблице могут присутствовать строки, не имеющие ни одной помеченной ячейки. В то же время, не должно быть ни одного столбца, не имеющего хотя бы одной помеченной ячейки.

Из анализа импликантной матрицы получим две возможные минимальные дизъюн­к­­тивные формы:

f1(a,b,c,d)МДНФ = v ab v ¯a ¯c ¯ d

f2(a,b,c,d)МДНФ = v ab v b ¯c ¯ d

Пример 4.2

Минимизировать методом Квайна - Мак-Класки неполностью определенную ФАЛ, заданую в виде:

f(a,b,c) = ∏(0,5,7), Х(1,6)

Решение

Этап 1.

Найти сокращенную КНФ для функции

f(a,b,c)СКНФ = ∏(0,1,5,6,7).

Сокращенная конъюнктивная нормальная форма этой ФАЛ имеет вид:

f(a,b,c,d)СкКНФ = (a v b) (b v ¯c) ( ¯a v ¯ c ) ( ¯a v )

Этап 2.

Составить имплицентную матрицу для исходной функции:

000

101

111

00-

+

-01

+

1-1

+

+

11-

+

Этап 3.

По имплицентной матрице получить минимальную конъюнктивную нормальную форма. Для этой функции она единственная:

f(a,b,c)МКНФ = (a v b) (¯a v ¯c)

4.2. Минимизация неполностью определенных функций Методом диаграмм Вейча

Пример 4.3

Получить методом диаграмм Вейча минимимальную дизъюнктивную нормальную форму неполностью определенной ФАЛ, заданой в следующем виде:

f(a,b,c,d) = (0,5,8,12,15), Х(1,2,3,10.13,14)

Решение

Этап 1.

Занести значение функции на диаграмму Вейча. Заполнить 1‑клетки и клетки, соответствующие неопределенным значениям функции (будем называть их X-клетками):

¯d

d

¯d

a

1

x

1

¯c

x

1

x

c

¯a

x

x

1

x

1

¯c

b

¯b


Этап 2.

Выбрать такие значения ФАЛ в x-клетках, которые обеспечивают покрытие всех 1-кле­ток минимальным количеством m-кубов максимальной площади. Для рассматриваемой функции су­щест­вует два варианта таких доопределений, обеспечивающих полу­че­ние двух минимальных дизъюнктивных нормальных форм:

¯d

d

¯d

a

1

x

1

¯c

x

1

x

c

¯a

x

x

1

x

1

¯c

b

¯b

f1(a,b,c,d)1МДНФ = ab v v ¯a ¯ccd

¯d

d

¯d

a

1

x

1

¯c

x

1

x

c

¯a

x

x

1

x

1

¯c

b

¯b

f(a,b,c,d)2МДНФ = ab v v b ¯cd

Пример 4.4

Получить методом диаграмм Вейча минимимальную конъюнктивную нормальную форму неполностью определенной ФАЛ, заданую в следующем виде:

f(a,b,c,d) = ∏(2,3,5,6,7,8,13,15), Х(0,1,9)

Решение

Этап 1.

Занести значение функции на диаграмму Вейча. Заполнить 0-клетки и клетки, соответствующие неопределенным значениям функции:

¯d

d

¯d

a

0

x

0

¯c

0

c

¯a

0

0

0

0

0

x

x

¯c

b

¯b


Этап 2.

Выбрать такие значения ФАЛ в X-клетках, которые обеспечивают покрытие всех 0-кле­ток минимальным количеством m-кубов максимальной площади:

¯d

d

¯d

a

0

x

0

¯c

0

c

¯a

0

0

0

0

0

x

x

¯c

b

¯b

Этап 3.

Записать минимальную КНФ, соответствующую по­лу­ченным m‑кубам.

f(a,b,c,d)МКНФ = (b vc) (a v ¯c) (v )

Пример 4.5

Получить методом диаграмм Вейча минимальные КНФ и ДНФ следующей неполностью определенной логической функции

f(a,b,c,d)СКНФ = ∏(0,2,3,4,7,11,15), X(1,8,9)

Решение

Получение минимальной КНФ.

Этап 1.

Заполнить на диаграмме Вейча 0-клетки и X-клетки:

¯d

d

¯d

a

x

x

¯c

0

0

c

¯a

0

0

0

0

x

0

¯c

b

¯b


Этап 2.

Выбрать такие значения ФАЛ в X-клетках, которые обеспечивают покрытие всех 0-кле­ток минимальным количеством m-кубов максимальной площади:

¯d

d

¯d

a

x

x

¯c

0

0

c

¯a

0

0

0

0

x

0

¯c

b

¯b

Этап 3.

Записать минимальную КНФ, соответствующую полученным m‑кубам:

f(a,b,c,d)МКНФ = (a v b ) ( ¯c v ) (a v c v d )

Получение минимальной ДНФ.

Этап 1.

Заполнить на диаграмме Вейча 1-клетки и X-клетки. На диаграмму заносятся все X-клетки вне зависимости от того, как доопределялась ФАЛ при получении МКНФ:

¯d

d

¯d

a

1

1

x

x

¯c

1

1

c

¯a

1

1

x

¯c

b

¯b

Этап 2.

Выбрать такие значения ФАЛ в X-клетках, которые обеспечивают покрытие всех 1-кле­ток минимальным количеством m-кубов максимальной площади:

¯d

d

¯d

a

1

1

x

x

¯c

1

1

c

¯a

1

1

x

¯c

b

¯b

Обратим внимание на то, что на наборе 1 при получении МКНФ функция доопределялась нулевым значением, а при получении МДНФ – единичным.

Этап 3.

Записать минимальную ДНФ, соответствующую полученным m‑кубам:

f(a,b,c,d)МДНФ = ¯c v a ¯c v bc

Список ЛИТЕРАТУРы

1. Вавилов Е.Н., Егоров Б.М., Ланцев В.С., Тоценко В.Г. Синтез схем на пороговых элементах. – Под ред. Е.Н.Вавилова. – М.: Сов. радио, 1970. 368 с.

2. Каган Б.М. Электронные вычислительные машины и системы. - М.: Энергоатом­издат, 1991.

3. Поспелов Д.А.. Логические методы анализа и синтеза схем. – М.: Энергия, 1974.

4.Савельев А.Я. Прикладная теория цифровых автоматов. - М.: Высшая школа, 1987.

СОДЕРЖАНИЕ

Введение …………………………………………………….3

1. Основные понятия и соотношения алгебры логики …5

2. Представление функций алгебры логики ……………..

3. Минимизация функций алгебры логики ……………...

3.1. Метод Квайна – Мак-Класки………………….

3.2. Метод диаграмм Вейча………………………...

4. Минимизация неполностью определенных функций...

4.1. Минимизация неполностью определенных

функций методом Квайна – Мак-Класки.…………

4.2. Минимизация неполностью определенных

функций методом диаграмм Вейча…….…………..

Список литературы ………………………………………….

В.В.Гуров

Синтез комбинационных схем

в примерах и решениях

Москва 2001

Валерий Валентинович Гуров

Синтез комбинационных схем

в примерах и решениях

Редактор Антонова Н.Н.

Лицензия ЛР 020676 от 09.12.97г.

Подписано в печать Формат 60х84 1/16

Уч.-изд. л. 5,0. Печ. л. 5,25 Тираж 150 экз.

Изд. №029-1 Заказ

Московский государственный инженерно-физический институт

(технический университет)

Типография МИФИ

115409 Москва, Каширское шоссе, 31

Примечания и дополнения

Ранг терма r определяется количеством переменных, входящих в данный терм. Например, для минтерма F = ¯a & b & c ранг r=3, а для макстерма Ф = ¯a v ¯b v c v d ранг r=4.

Дизъюнктивная нормальная форма (ДНФ) – объединение термов, включающее минтермы переменного ранга.

Конъюнктивная нормальная форма (КНФ) – объединение термов, включающее макстермы разного ранга.

Основное понятие алгебры логики - высказывание. Высказывание - некоторое предложение, в отношении которого можно утверждать, что оно истинно или ложно. Любое высказавание можно обозначить каким-либо симвлолом, например х, и считать, что х=1, есливысказывание истинно, и х=0, если высказывание ложно.

Конъюнкция всех переменных, от которых зависит ФАЛ, взятых с отрицаниями или без них, называется конституэнтой единицы. Любая конституэнта единицы равна единице только на одном наборе переменных.

Импликанта функции – некоторая логическая функция, обращаемая в нуль при наборе переменных, на котором сама функция также равна нулю.

Простыми импликантами логической функции называются такие элементарные конъюнкции, которые сами входят в данную функцию, но никакая собственная часть этих элементарных конъюнкций в данную функцию не входит.

Дизъюнкция всех переменных, от которых зависит ФАЛ, взятых с отрицаниями или без них, называется конституэнтой нуля. Любая конституэнта нуля равна нулю только на одном наборе переменных.

Отыскание минимальных дизъюнктивных нормальных форм сводится к определению вариантов, при которых все единицы диаграммы Вейча накрываются наименьшим числом наиболее коротких произведений, то есть прямоугольников наибольшей площади. Как правило, метод диаграмм Вейча используется в чисто прикладныз целях и предполагает отыскание какой-либо одной минимальной формы из нескольких возможных вариантов.

Здесь 1-кубу будет соответствовать импликанта, содержащая 4 переменные, 2-кубу – ранга 3, 3-кубу – ранга 2.

Если данную таблицу рассматривать как цилиндр, образованный соединением первой и последней колонок, то тогда склеивающиеся между собой конституэнты едини­цы или нуля в диаграммах Вейча будут расположены в соседних клетках (рис.3.2.б и 3.2.в).

В диаграммаах Вейча для функции двух переменных любая пара единиц, рас­по­ложенных в соседних клетках, при получении МДНФ выражается одной буквой, пред­ставляющую собой общую координату этой пары клеток.

48



Скачать документ

Похожие документы:

  1. Библиографический указатель из фонда научной библиотеки

    Библиографический указатель
    ... -технических работ. МИФИ - городу Москве:Каталог.-М.,2001.-Б.п. 195. Московский государственный инженерно-физический ... .-26с. 4553. Гуров В.В. Синтезкомбинационныхсхем в примерах и решениях: Учеб.пособие/Гуров В.В.-М.:МИФИ,2001.-56с. 4554. Гусев ...
  2. Москва 2011 1 Цели и задачи дисциплины (3)

    Рабочая программа
    ... коммуникационные технологии Москва 2011 1. ... схемотехнических решений и ... и синтезасхем ЭВМ. Анализ комбинационныхсхем. Синтезкомбинационныхсхем: мультиплексор ... СПб.: БХВ-Петербург, 2001. 2. Пухальский Г.И., Новосельцева ... также примеры оценочных ...
  3. Программа обучения студентов ( syllabus ) (3)

    Программа обучения студентов
    ... домашних заданий, самостоятельное решение задач), итоги индивидуальных ... А.В. и др. «Информатика». – Москва.: ACADEMA, 1999 г. Информатика/ Под ... ДИАЛОГ-МИФИ,1993 Гуров В.В. Синтезкомбинационныхсхем в примерах М.: МИФИ, 2001 Гуров В.В., Ленский О.Д., ...
  4. РУССКАЯ ВЕРОЯТНОСТНАЯ ЛОГИКА

    Документ
    ... -ЭЛЕКТРОНЩИКА Москва 2008 ... Русская механика» А.Ф.Черняева (М.:2001 – 592с.) и « ... 1.4. СинтезкомбинационныхсхемСинтезкомбинационныхсхем можно проиллюстрировать решением простой ... Пример 1. «Энциклопедия - Россия-Он-Лайн» излагает примеррешения ...
  5. РУССКАЯ ВЕРОЯТНОСТНАЯ ЛОГИКА (2)

    Документ
    ... -ЭЛЕКТРОНЩИКА Москва 2008 ... Русская механика» А.Ф.Черняева (М.:2001 – 592с.) и « ... 1.4. СинтезкомбинационныхсхемСинтезкомбинационныхсхем можно проиллюстрировать решением простой ... Пример 1. «Энциклопедия - Россия-Он-Лайн» излагает примеррешения ...

Другие похожие документы..