2015-06-28
312
1. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.550-564.
2. Новоселов В.Г., Скатков А.В. Прикладная математика для инженеров-системотехников. Дискретная математика в задачах и примерах. – К.: Учебно-методический кабинет высшего образования, 1992. - С.146-183.
3. Горбатов В.А. Основы дискретной математики. – М.: Высш. шк., 1986. - С.50-55.
Додаткова
4. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.91-92.
Для практичних занять
5. Методичні вказівки і завдання до контрольних робіт з дисципліни «Основи дискретної математики» для студентів очної та заочної форм навчання фахів 6.0804, 6.0915 / О.М. Мартинюк. – Одеса: ОНПУ, 2001. – С.38-40.
6. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1973. - С.38-50.
Лекція 29. Матричні форми
Вступ
Лекція має за мету навести поняття матричних форм. Розглянуто визначення матричних й інтервальних форм, осі симетрії. Звернено увагу на модифікацію спрощення ДНФ за матричною формою Закревського.
У лекції присутні три підрозділи:
|
|
|
29.1. Основні визначення
29.2. Інтервальне представлення в матричній формі
29.3. Спрощення ДНФ за матричною формою Закревського
29.1 Основні визначення
Визначення. Матрична двовимірна форма для зіставлення своїм елементам 2n наборів розбиває безліч змінних Х = {x1, x2, …, xn} на дві підмножини молодших і старших змінних:
Х = {x1, x2, …, xn} = {x1, x2, …, x]n/2[} È {x]n/2[+1, x]n/2[+2, …, xn},
де ]k[ - найменше ціле, більше або дорівнююче k. Набори значень безлічі {x1, x2, …, x]n/2[} молодших змінних зіставляються стовпцям матриці, набори старших - рядкам матриці.
Є два варіанти впорядкування: послідовний позиційний код і код Грея. Для коду Грея послідовність починається з нульового набору (0, 0,..., 0), при переході від чергового набору до наступного змінюється значення тільки однієї змінної - тієї молодшої змінної, котра приводить до одержання нового коду стосовно усім раніше побудованим.
Приклад. При n=4 й упорядкуванні змінних x4, x3, x2, x1 виходить така послідовність наборів при рахуванні в коді Грея: 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000.
Якщо при перерахуванні наборів застосовується позиційний код, матриця називається діаграмою Вейча, якщо використається код Грея - картою Карно. Прийнято позначення наборів: одиничне значення змінної зображується рисою над стовпцем або ліворуч від рядка, нульове значення - відсутністю риси
(табл. 29.1, табл. 29.2).
Таблиця 29.1
| x 3 | x 3 | x 3 | x 3 | ||||||
| x 2 | x 2 | x2 | x 2 | ||||||
| x 1 | x 1 | x 1 | x 1 | ||||||
| · | · | · | · | ||||||
| x4| | · | · | · | · | · | · | |||
| x5| | · | · | |||||||
| x5| | x4| | · | · |
Таблиця 29.2
|
|
|
| x 3 | x 3 | x3 | x 3 | ||||||
| x 2 | x 2 | x 2 | x 2 | ||||||
| x 1 | x 1 | x 1 | x 1 | ||||||
| x4| | |||||||||
| x5| | x4| | ||||||||
| x5| |
Кожній клітці таблиці відповідає сукупний набір значень молодших і старших змінних. Одиничне значення на відповідному наборі позначається міткою (одиницею, міткою) у клітці матриці.
Матрична форма в позиційному коді зручна для програмного розв’язання завдань, у коді Грея - для «ручного» розв’язання.
