41738

Мінімізація функцій за допомогою карт Карно

Лабораторная работа

Информатика, кибернетика и программирование

Мета: навчитися мінімізувати функції за допомогою карт Карно Завдання: Для кожного варіанта задана функція від п'яти змінних номерами відсутніх конституент. Мінімізувати функцію за допомогою карт Карно. Побудована таблиця називається картою Карно.

Украинкский

2013-10-25

48.54 KB

16 чел.

6

Лабораторна робота №2

Тема: Мінімізація функцій за допомогою карт Карно.

Мета: навчитися мінімізувати функції за допомогою карт Карно

Завдання: 

Для кожного варіанта задана функція від п'яти змінних номерами відсутніх конституент. Мінімізувати функцію за допомогою карт Карно. Визначити складність функції до та після мінімізації. Проаналізувати отримані результати. Індивідуальні варіанти завдань представлені в таблицях А.1-А.3 (додаток А).

Теоретичні основи:

Графічний спосіб мінімізації функцій зручний для трьох, у крайньому випадку для чотирьох аргументів. Для того, щоб використовувати сам принцип цього методу для більшої кількості змінних була запропонована його модернізація. Ідея полягає в розгортці куба на площині. Покажемо цю розгортку на малюнку.

                          011                              111

1

100              101                111              110                 100

Виходячи з розгортки куба побудуємо наступну таблицю.

00

01

11

10

0

1

1

1

1

1

Побудована таблиця називається картою Карно. У карті позначено конституенти, присутні у функції. Подібно тому, як відмічені вершини куба поєднувалися в ребра й грані, поєднуються й одиниці карти в так звані інтервали. В інтервали можна поєднувати 2m одиниць, тобто 2,4,8…і т.д. Покажемо об'єднання одиниць і зчитування мінімальної форми на карті Карно.

М3

00

01

11

10

0

1

1

М1

1

1

1

М2

Усього на карті виділено три інтервали. В кожний інтервал входять ті мінітерми, у яких він повністю перебуває. Виходячи з карти, мінімальна форма має вигляд :

                         __                                   __  __

f(М1, M2 , M3) = М1  M3  +  M2  M3 +  М1 M2, M3

Як видно, результат повністю збігається з попереднім. Покажемо, як виглядають карти Карно для чотирьох змінних.

00

01

11

10

00

1

1

01

1

1

11

1

1

10

1

1

Можна скласти карти Карно для п'яти й більше аргументів, однак, з ростом числа аргументів складність роботи з картою зростає швидше, і при цьому процес оптимізації важко алгоритмізувати.

Зміст звіту:

  1.  Титульний лист.
  2.  Мета, індивідуальне завдання.
  3.  Карти Карно з означеними інтервалами.
  4.  Опис інтервалів.
  5.  Визначення складності функції.
  6.  Аналіз результатів.

Контрольні питання.

  1.  Перерахуйте відомі операції над множинами.
  2.  Назвіть закони над операціями для множин.
  3.  Дайте визначення первинного терму.
  4.  Визначите поняття конституенти.
  5.  Як функція від множин представляється графічно?
  6.  Що таке інтервали й максимальні інтервали?
  7.  Дайте визначення нормальної й зробленої нормальної форми Кантора.
  8.  Як проводиться графічна мінімізація функції від множин?
  9.  Як одержати карту Карно для трьох змінних?
  10.  Карти Карно для чотирьох і п'яти змінних.


Додаток А Варіанти завдань

Таблиця А.1 – Варіанти завдань групи а

Номер варіанта

відсутні конституенти

Номер варіанта

відсутні конституенти

1

5, 9, 17, 26

17

7, 10, 11, 13, 29

2

4, 10, 15, 29

18

1, 4, 6, 7, 12, 30

3

7, 12, 13, 16, 26

19

5, 8, 10, 22, 30

4

3, 5, 18, 21

20

1, 4, 7, 12, 16, 27

5

2, 10, 22, 23

21

8, 14, 23, 26, 31

6

6, 9, 14, 20, 21

22

2, 6, 15, 20, 27

7

6, 7, 9, 21, 22

23

5, 15, 21, 27, 29

8

1, 3, 12, 23, 30

24

2, 4, 8, 11, 25, 30

9

5, 10, 11, 13, 28

25

11, 18, 27, 29, 31

10

8, 11, 16, 23

26

9, 13, 16, 20, 29

11

5, 16, 20, 26

27

7, 12, 22, 25, 31

12

6, 7, 22, 24, 30

28

0, 4, 8, 11, 22, 27

13

8, 20, 24, 30

29

13, 17, 24, 27, 28

14

1, 7, 13, 24, 28

30

7, 15, 25, 27, 29

15

2, 6, 12, 15, 26

31

1, 5, 9, 17, 23, 27

16

9, 11, 15, 21, 26

32

11, 16, 23, 25, 29


таблиця А.2 – Варіанти завдань групи б

Номер варіанта

відсутні конституенти

Номер варіанта

відсутні конституенти

1

6, 10, 18, 27

17

8, 11, 12, 14, 30

2

5, 11, 16, 30

18

25, 7, 8, 13, 31

3

8, 13, 14, 17, 27

19

6, 9, 11, 23, 31

4

4, 6, 19, 22

20

2, 5, 8, 13, 17, 28

5

3, 11, 23, 24

21

9, 15, 24, 27, 0

6

7, 10, 15, 21, 22

22

3, 7, 16, 21, 28

7

7, 8, 10, 22, 23

23

6, 16, 22, 28, 30

8

2, 4, 13, 24, 31

24

3, 5, 9, 12, 26, 31

9

6, 11, 12, 14, 29

25

12, 19, 28, 30, 0

10

9, 12, 17, 24

26

10, 14, 17, 21, 30

11

6, 17, 21, 27

27

8, 13, 23, 26, 0

12

7, 8, 23, 25, 31

28

1, 5, 9, 12, 23, 28

13

9, 21, 25, 31

29

14, 18, 25, 28, 29

14

2, 8, 14, 25, 29

30

8, 16, 26, 28, 30

15

3, 7, 13, 16, 27

31

2, 6, 10, 18, 24, 28

16

10, 12, 16, 22, 27

32

12, 17, 24, 26, 30


таблиця А.3 – Варіанти завдань групи в

Номер варіанта

відсутні конституенти

Номер варіанта

відсутні конституенти

1

7, 11, 19, 28

17

9, 12, 13, 15, 31

2

6, 12, 17, 31

18

3, 6, 8, 9, 14, 30

3

9, 14, 15, 18, 28

19

7, 10, 12, 24, 29

4

5, 7, 20, 23

20

3, 6, 9, 14, 18, 29

5

4, 12, 24, 25

21

10, 16, 25, 28, 30

6

7, 11, 16, 22, 23

22

4, 8, 17, 22, 29

7

8, 9, 11, 23, 24

23

7, 17, 23, 29, 31

8

3, 5, 14, 25, 0

24

4, 6, 10, 13, 27

9

7, 12, 13, 15, 30

25

13, 20, 29, 31

10

10, 13, 18, 25

26

11, 15, 18, 22, 31

11

7, 18, 22, 28

27

9, 14, 24, 27, 29

12

8, 9, 24, 26, 0

28

2, 6, 10, 13, 24

13

10, 22, 26, 0

29

15, 19, 26, 29, 30

14

3, 9, 15, 26, 30

30

9, 17, 27, 29, 31

15

4, 8, 14, 17, 28

31

3, 7, 11, 19, 25

16

11, 13, 17, 23, 28

32

13, 18, 25, 27, 31


 

А также другие работы, которые могут Вас заинтересовать

85188. Духовная и культурная жизнь БССР в 1920-1930гг.: достижения и противоречия 25.66 KB
  Культуры вылученне белорусов на партыйую советскую профсоюзную и общественную работу перевод делопроизводства государственного партийного профессионального и кооперативного аппаратов на белорусский язык. Центральная место в мероприятиях в белорусизации отводилось проблеме языка так как в республике язык выполняла очень мизерны объем соц. Преобладала русский язык. При этом официально было заявлено что на территории БССР признаются равноправными языки белорусский русский еврейский и польский.
85189. Западная Беларусь в составе Польши 27.1 KB
  Было введено принятое в Польше административно-тер деление, созданы 4 воеводства: Виленское, Полесское, Новогрудское, Белостокское. Эти воеводства делились на 29 поветов аповеты на гимны.
85190. Начало второй мировой войны. Вхождение Западной Беларуси с состав БССР 26.28 KB
  Вхождение Западной Беларуси с состав БССР. Беларуси принял декларацию об установлении советской власти на всей освобожденной территории i высказался за вхождение в состав БССР. Приняты законы о включении Западной Беларуси в состав СССР i воссоединение с БССР. Единогласно делегаты высказались и за вхождение в БССР.
85191. Начало Великой Отечественной войны. Ход военных действий на советско-германском фронте в 1941-1942 годах 27.92 KB
  Для войны против СССР Гитлер сосредоточил подавляющую часть своих сухопутных сил. Однако основной причиной такого огромного успеха немцев в первые недели войны является то что Красная армия сама готовилась к наступлению. Сталин прекрасно понимал что войны с Германией не избежать но он не думал что Гитлер нарушит пакт МолотоваРибентропа о ненападении.
85192. Фашистский оккупационный режим на территории БССР 26.93 KB
  К концу августа 1941 г гитлеровцы оккупировали всю территорию Бел. На захваченной территории гитлеровцы установили оккупационный режим- систему политических, идеологических, экономических, и военных мер направленных на ликвидацию существующего общественного и гос. строя, грабёж нац. богатства, уничтожение населения
85193. Коренной перелом в ходе Великой Отечественной войны 29.96 KB
  Коренной перелом начатый под Сталинградом был завершен в ходе Курской битвы и сражениях за р. в ходе Киевской наступательной операции 6 ноября столица Украины была освобождена. В ходе оборонительных боев к концу декабря 1943 г.
85194. Партизанское и подпольное движение в БССР 28.28 KB
  Один из первых партизанских отрядов был организован уже на пятый день войны в Пинске под командованием Коржа насчитывал 60 чел. Полесской области действовал отряд под командованием Бумажкова и Павловского. В июле 41 начал боевые действия отряд пол командованием Шмырёва в Вит.
85195. Освобождение Беларуси. Окончание Великой Отечественной и Второй мировой войны. Вклад белорусского парода в Победу над фашизмом 28.18 KB
  Начать операцию освобождения Украины и Беларуси. 23 сентября советские войска освободили первый районный центр Беларуси –г. Всего в Беларуси в результате осенне– зимнего наступления 1943-1944 гг.
85196. Система биполярного мира после Второй мировой войны 26.8 KB
  Основной причиной противостояния была борьба СССР и США за геополитическое превосходство прежде всего в Европе. Начало оформлению политики холодной войны положила доктрина Трумэна 1947 внешнеполитическая программа США которая высказывала просьбу выделить помощь 400 млн Греции и Турции обосновывая это тем что США должны оказывать поддержку свободным народом Предложения США критиковались правительством СССР которое считало что они фактически означают подчинение экономики западноевропейских стран экономике США и нарушают их...