Контрольная работа по Дискретной математике - файл n1.doc

Контрольная работа по Дискретной математике
скачать (2853.5 kb.)
Доступные файлы (1):
n1.doc2854kb.10.06.2012 06:59скачать

n1.doc

  1   2   3   4


Контрольная работа
Задание 1:

В таблице заданы номера наборов аргументов, на которых логическая функция принимает значение, равное единице. Необходимо записать эту функцию в СДНФ и произвести ее минимизацию методом Квайна, методом сочетания индексов и методом Карно (результаты минимизации для всех трех случаев должны совпасть).


1

6

7

9

12

13

14

15


Решение:

Двоичная форма данной булевой функции имеет вид

Составим таблицу истинности для заданной функции:





x1

x2

x3

x4



0

0

0

0

0

0

1

0

0

0

1

1

2

0

0

1

0

0

3

0

0

1

1

0

4

0

1

0

0

0

5

0

1

0

1

0

6

0

1

1

0

1

7

0

1

1

1

1

8

1

0

0

0

0

9

1

0

0

1

1

10

1

0

1

0

0

11

1

0

1

1

0

12

1

1

0

0

1

13

1

1

0

1

1

14

1

1

1

0

1

15

1

1

1

1

1


Для приведения функции к СДНФ (совершенной дизъюнктивной нормальной форме) отметим строки в которых функция равна 1 и выпишем переменные в этих строках, соединяя их знаком конъюнкции, причем, если переменная равна 1, то запишем саму эту переменную, если же она равна 0, то запишем ее отрицание. Все полученные выражения связываем знаком дизъюнкции.





X1

x2

x3

x4






1-я строка

0

0

0

1

1



6-я строка

0

1

1

0

1



7-я строка

0

1

1

1

1



9-я строка

1

0

0

1

1



12-я строка

1

1

0

0

1



13-я строка

1

1

0

1

1



14-я строка

1

1

1

0

1



15-я строка

1

1

1

1

1



СДНФ:



Произведем минимизацию функции методом Квайна:

Метод Квайна основывается на применении двух основных соотношений:

1. Соотношение склеивания:

2. Соотношение поглощения:

где - любое элементарное произведение.
На первом этапе необходимо подучить сокращенную ДНФ. Для удобства пометим каждую конституенту единицы из СДНФ функции каким-либо номером и выполним операции попарного склеивания и элементарного поглощения.




Эл. конъюнкция

Поглощение




Номера

склеивания

Результат

склеивания

1



+




1 – 4



2



+




2 – 3



3



+




2 – 7



4



+




3 – 8



5



+




4 – 6



6



+




5 – 6



7



+




5 – 7



8



+




6 – 8















7 – 8




На данном этапе все импликанты были поглощены своими собственными частями, а значит простые импликанты на этом шаге не получены.




Эл. конъюнкция

Поглощение




Номера

склеивания

Результат

склеивания

1









2 – 9



2



+




3 – 4



3



+




6 – 9



4



+




7 – 8



5















6



+










7



+










8



+










9



+











В результате получены простые импликанты:




Эл. конъюнкция

Поглощение










1















2
















В результате получены простые импликанты:
Таким образом, получили сокращенную ДНФ:

Переходим ко второму этапу. Для получения минимальной ДНФ необходимо убрать из сокращенной ДНФ все лишние простые импликанты. Это делается с помощью специальной импликантной матрицы Квайна. Строки такой матрицы отмечаются простыми импликантами булевой функции, т. е. членами сокращенной ДНФ, а столбцы - конституентами единицы, т. е. членами СДНФ булевой функции.

Простая импликанта поглощает некоторую конституенту единицы, если является ее собственной частью. Соответствующая клетка импликантной матрицы на пересечении строки с рассматриваемой простой импликантой и столбца с конституентой единицы отмечается крестиком.

Минимальная ДНФ строится по импликантной матрице следующим образом:

1. ищутся столбцы импликантной матрицы, имеющие только один крестик. Соответствующие этим крестикам простые импликанты называются базисными или существенными и составляют так называемое ядро булевой функции.

2. рассматриваются различные варианты выбора совокупности простых импликант, которые накроют крестиками остальные столбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числом букв в такой совокупности импликант.



































x

x

x

x






x

x










x

x



x







x
























x




x







  1   2   3   4


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации