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


 

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

57846. Рівнобедрений трикутник. Властивість рівнобедреного трикутника 567.5 KB
  По закінченні прошу вас відповісти на запитання. Осмислення нових знань умінь Виконаємо декілька задач на розуміння означення рівнобедреного трикутника...
57847. Таємниці трикутника 475 KB
  Задачі проекту: розширити знання учнів з геометрії про трикутник та його властивості; ознаки подібності трикутників, Формулювати висновки на підставі проведених досліджень і роботи з інформацією...
57848. Урок. Трикутники 146.5 KB
  Мета уроку: Систематизувати та узагальнити знання учнів про зміст основних понять теми; систематизувати та узагальнити знання, вміння й навички учнів для розв’язування задач.
57849. Трикутник. Види трикутників. Периметр трикутника 62.5 KB
  Мета дидактична: подальше закріплення знань учнями класифікації трикутників; складання алгоритму побудови трикутників за двома сторонами і кутом між ними та за стороною і прилеглими кутами...
57850. Трикутники. Урок - захист проектів 361 KB
  Узагальнити початкові знання про трикутники: означення трикутника означення прямокутного трикутника сума кутів трикутника сума гострих кутів прямокутного трикутника види трикутників за його кутами визначні точки трикутника. Існує навіть окрема частина геометрії: геометрія трикутника. Слово надається Стегнію Валентину автору проекту Жорсткість трикутника Валентин. До вашої уваги презентація дослідницькоінформаційного проекту Жорсткість трикутника.
57851. Iнтегрований урок з читання, математики, Я i Украiни з використанням комп’ютерних технологiй. Тварини Лiсу 64.5 KB
  Мета: Вдосконалення техніки читання, вмiння складати схеми, речення, працювати з геометричним матеріалом, повторити калiграфiчне написання цифри 4, повторити таблицю додавання i вiднiмання числа 4, складання і розв’язування задачі.
57852. Уравнения. Угол. Многоугольники 48.5 KB
  Ожидаемые результаты: учащиеся должны решать уравнения на основе зависимости между компонентами при сложении и вычитании; уметь распознавать углы биссектрису угла строить углы с помощью транспортира решать задачи с помощью полученных знаний об углах...
57853. Дихання. Значення дихання. Органи дихання 211 KB
  Формувати знання та поняття у учнів про дихальну систему людини; ознайомити із диханням як процесом необхідним для життя; показати особливості та взаємозв’язок будови та функцій органів дихання; розглянути складові частини системи...
57854. Половое размножение. Строение и разнообразие цветков 56 KB
  Разнообразием и классификацией цветков и растений в зависимости от строения цветка; симметрией цветков. Концепция: дать определение цветка. Рассмотреть строение цветка и функции отдельных элементов.