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


 

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

83465. Види визнання 36.34 KB
  Визнання держави має місце у випадках появи нової незалежної держави революційних та інших соціальних перетворень територіальних змін обєднання та розділу держав і т. Основним критерієм визнання держави є її незалежність та самостійність у реалізації ефективної та легітимної державної влади що означає законність її встановлення та підтримку з боку населення встановленого режиму. Визнання уряду означає визнання його здатності здійснювати ефективну державну владу в країні та представляти її на міжнародній арені.
83466. Визнання держав 34.95 KB
  В міжнародному праві існують дві теорії визнання держав конститутивна і декларативна. Конститутивна теорія: політичний акт визнання є попередньою умовою існування юридичних прав нової держави. Саме акт визнання іншими державами створює нову державу породжує і забезпечує її міжнародну правосубєктність. Визнання нової держави яка додержує умов державності має бути правовим обовязком.
83467. Форми визнання 36.2 KB
  Найбільш поширеним є визнання dejure яке є офіційним повним та остаточним. Воно передбачає встановлення між субєктами міжнародного права міжнародних відносин у повному обсязі та супроводжується як правило заявою про офіційне визнання та встановленням дипломатичних відносин. Визнання деюре носить безумовний характер та як правило не може буди відкликане.
83468. Визнання урядів 35.44 KB
  Значення і правові наслідки визнання нового уряду відрізняються від визнання нової держави. Визнання уряду надає йому можливість репрезентувати державу в міжнародних відносинах. Питання визнання уряду виникає лише в тому випадку коли уряд здобуває владу іншим аніж визначено в національному законодавстві шляхом. В міжнародному праві існують такі доктрини щодо визнання урядів: 1.
83469. Доктрини визнання урядів 35.14 KB
  Історії міжнародного права відомі спеціальні доктрини про визнання урядів, названі іменами міністрів закордонних справ Еквадору Карлоса Тобара (доктрина Тобара) і Мексики Хенаро Естради (доктрина Естради), що сформувалися на початку XX століття в практиці держав американського континенту.
83471. Інститут правонаступництва держав в міжнародному праві. Джерела міжнародного правонаступництва 35.98 KB
  Джерела міжнародного правонаступництва Для стабільності міжнародних відносин важливе значення має послідовне виконання субєктами міжнародного права укладених ними міжнародних договорів їх міжнародних зобовязань щодо території власності членства у міжнародних організаціях тощо. Інститут правонаступництва у міжнародному праві є міжгалузевим інститутом: його норми містяться в праві міжнародних договорів праві міжнародних організацій міжнародному економічному праві та ін. Тривалий час основу інституту правонаступництва складали звичаєві...
83472. Поняття правонаступництва в міжнародному праві. Види і форми правонаступництва. Підстави правонаступництва 37.07 KB
  Види і форми правонаступництва. Підстави правонаступництва. Таким чином правонаступництво являє собою правовідносини у яких беруть участь дві сторони: державапопередниця яка була змінена іншою державою в процесі правонаступництва; державаспадкоємниця яка замінила іншу державу в процесі правонаступництва.
83473. Міжнародне правонаступництво держав щодо міжнародних договорів 38.6 KB
  Відносно усних договорів і договорів між державами й іншими субєктами міжнародного права діють звичаєві норми міжнародного права. встановлює наступні правила правонаступництва щодо міжнародних договорів: а у разі створення в результаті деколонізації нової незалежної держави діє принцип tbul rs чистої дошки: нова держава не звязана договорами укладеними колишніми державамиметрополіями і не зобовязана зберігати чинність будьякого договору або ставати його учасницею в силу виключно того факту...