Основи дискретної математики 2

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ

Кафедра комп'ютерних інтелектуальних систем і мереж

Розрахунково-графічна робота

з дисципліни

«Основи дискретної математики»

Виконав

студент групи АЕ-074

П.І.Б.

Перевірив

доцент кафедри КІСМ

Мартинюк А. М.

Одеса 2008

Введення

Дана розрахунково-графічна робота з дисципліни "Основи дискретної математики» включає в себе:

  • задачу мінімізації заданого виразу алгебри множин на підставі відомих властивостей;

  • аналіз заданого бінарного відносини в загальному вигляді, побудова його графіка і повне визначення властивостей відносини, включаючи властивості, успадкованих ним від відповідностей;

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

  • перетворення формули булевої функції заданої логічної схеми в КНФ, ДНФ, СКНФ і СДНФ, а також її мінімізацію методами Квайна-МакКласкі, Петрика, і за допомогою карт Карно;

  • поповнення булевої функції заданими байдужими вхідними наборами та мінімізацію поповнений функції за допомогою карт Карно, а також методів Квайна-МакКласкі і Петрика;

  • переклад отриманих мінімізованих формул з булева базису в заданий функціональний базис і синтез відповідних логічних схем.

Завдання № 1

Спрощення заданого виразу алгебри множин

1.1 Вибір варіанта завдання

Варіанти РГР утворюються завданням індивідуальних:

  • вираження алгебри множин;

  • бінарного відносини;

  • вихідної логічної схеми;

  • байдужих вхідних наборів.

В основі вибору варіанта лежить процедура визначення цілочисельного залишку від ділення висловлювання, в якому присутня число. (Варіант 9)

Таблиці - див література 1.

Вибір варіанту вираження алгебри множин.

«№ операцій» = 9 mod 7 +1 = 3

№ операції

a

b

g

d

l

Варіант 3

Ø

\

Ç

-

È

«№ операндів» = 9 mod 5 +1 = 5

№ операнда

оп-д1

оп-Д2

оп-Д3

оп-Д4

оп-Д5

Варіант 5

A d F

B b A

E d B

a E

A g B

Результати підставляються в шаблонну формулу:

(A (Оп-д1 b (a Оп-Д2))) g (ùa ((Оп-Д3 d Оп-Д4) l (ùa Оп-Д5)))

1.2 Мінімізація заданого виразу

Задане вираз виглядає наступним чином:

((A - F) \ (B \ A )) Ç (            E            A Ç  B))

Мінімізація проводиться з використанням вісімнадцяти законів. (Див. літератури 2)

  1. ((A - F) \ (B \ A)) =

((A \ F)   (F \ A)  \ (B   A)) =

((A   F)   (F  A)   ( (B   A))) =

(A   F)   (F   A)   ( B  A) =

(A   F)    B =

A   F    B

  1. (   (E - B - E))   (    A    B  ))  

   (  B   (     A  B ))) =

(  B      A   B )) =

A    B

  1. (A   F    B)      A    B    

(A   F    B    A)     A   F    B    B    

Ø   (A    F    B) =

A    F    B

     F     B - так виглядає вираз після мінімізації.

Завдання № 2

Аналіз заданого бінарного відносини

2.1 Вибір варіанта завдання

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

«№ операцій» = 9 mod 4 +1 = 2

№ операц

a

b

g

d

Варіант 2

abs

-

Æ

*

«№ операндів» = 9 mod 7 +1 = 3

№ операется

оп-д1

оп-Д2

оп-Д3

оп-Д4

Варіант 3

b - a

5 * a

2 * a + b

a / 2

«№ відносини» = 24mod 5 +1 = 5

№ варіанту

ставлення

Варіант 5

=

2.2 Бінарне відношення

У шаблонну формулу

( (ОП1  ОП2)) Relation ( (Оп3  ОП4))

підставляються результати, і виходить:

(Abs ((b - a -5 * a)) = (Æ ((2 * a + b) * a / 2)

спрощення формули:

| B - a - 5a | = (2a + b) a / 2

2.3 Побудова графіка

За даним відношенню за допомогою програм MathCad або MathLab, або ж від руки, можна побудувати графік:

2.4 Дослідження властивостей відносини

Властивості відносин доводяться шляхом приведення прикладів на графіку:

  1. Функціональний, тому що не містить пари з однаковими першими коефіцієнтом

  2. Ін'ектівен, тому що не містить пари з однаковими другими компонентами «b» і різними першими компонентами «a».

  3. Не всюди визначений, тому що область визначення не збігається з областю відправлення

  4. Сюрьектівен так як його область значень дорівнює області прибуття.

  5. Біектівен, так як функціональний, ін'ектівен і сюрьектівен.

  6. Чи не рефлексіва оскільки графік не містить пряму в = а.

  7. Актірефлексівен так як графік містить точки, що лежать на прямий і = а.

  8. Чи не іррефлексівен, оскільки знайдуться точки, що належать графіку і лежать на прямій в = а.

  9. Не симетричний, так як знайдуться точки, що не належать графіку і симетричні відносно прямої у = а.

  10. Чи не анттісімметрічен, оскільки знайдуться точки, що належать графіку і не симетричні відносно прямої у = а.

  11. Чи не ассіметрічен, оскільки знайдуться точки, що належать графіку і симетричні відносно прямої у = а, і одночасно знайдуться точки, що не належать графіку і симетричні відносно прямої у = а.

  12. Чи не транзітіва.

Властивості відносини внесені в таблицю

Функціональність

+

Ін'ектівность

+

Усюди визначеність

-

Сюр'ектівность

+

Биективное

+

Рефлексивність

-

Чи не рефлексивність

-

Антірефлексівность

+

Симетричність

-

Асиметричність

-

Антисиметричність

-

Транзитивність

-

Завдання № 3

Аналіз заданої в певному функціональному базисі логічної схеми

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

Номер варіанту заданого функціонального базису логічних функцій {№ ​​Ф-ціі1, № Ф-ціі2, № Ф-ціі3} з таблиці 6, що позначається як «№ Базис», виходить так:

«№ Базис» = («№ заліковку»% 8) +1

де% - операція отримання цілочислового залишку від ділення.

«№ Базис» = (9% 8) +1 = 2, тобто з таблиці 6 випливає, що

{№ Ф-ціі1, № Ф-ціі2, № Ф-ціі3} = {2,9,14}

Графічне зображення логічної схеми містить п'ятнадцять місць для розміщення (три ряди по п'ять елементів) логічних елементів, що реалізують логічні функції базису. Елементи пронумеровані з 5 по 19 включно, номери з 1 по 4 належать входів логічного схеми, а номер 20 приписаний виходу всієї схеми.

Номер варіанту розміщення логічних елементів у сітці місць графічного зображення логічної схеми з таблиці 7, що позначається як «№ Розміщення» виходить таким чином:

«№ Розміщення» = («№ заліковку»% 3) +1

де% - операція отримання цілочислового залишку від ділення.

«№ Розміщення» = (9% 3) +1 = 1, тобто з таблиці 7 отримуємо таке розташування для базису {№ Ф-ціі1, № Ф-ціі2, № Ф-ціі3} = {4,6,8} :

№ елем

№ вар

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

ф-Я1



x



x



x



x



x

ф-Я2

x



x



x



x



x



ф-я3


x



x



x



x



x


Номер варіанту списку зв'язків входів і виходів логічних елементів логічної схеми позначається як «№ Зв'язків» виходить таким чином:

«№ Зв'язків» = («№ заліковку»% 13) +1

де% - операція отримання цілочислового залишку від ділення.

«№ Зв'язків» = (9% 13) +1 = 10

У списку зв'язків для кожного логічного елемента вказані номери логічних елементів, виходи яких з'єднані з його входами.

Для даного варіанту список зв'язків виглядає наступним чином:

5 (1,2); 6 (1,2); 7 (3,4,6); 8 (5,6,7); 9 (4,6), 10 (4,7), 11 (1, 8,10), 12 (1,9); 13 (9,10), 14 (9,11); 15 (10,12,14); 16 (10,13); 17 (11,14), 18 (15,17); 19 (16,18); 20 (18).

Отримана схема приведена нижче:

Аналіз схеми.

Аналіз схеми виконується шляхом поетапної підстановки виразів для реалізації y

y5 = x1 ~ x2 = ù x1 ù x2 + x1x2

y6 = x1/x2 = ù x1 + ù x2

y7 = x3 ù → x4 ù → y6 = (x3 ù x4) ù → y6 = x3x4x1x2 = x1x2x3x4

y8 = y5 ~ y6 ~ y7 = ((x1 + x2) (ù x1 + ù x2) x1x2 + (ù x1 ù x2 + x1x2) (ù x1 + ù x2)) ~ y7 =

= (Ù x1 ù x2) ~ y7 = (x1 + x2) (ù x1 + ù x2 + ù x3 + ù x4) + (ù x1 ù x2) x1x2x3x4 = x1 ù x2 + x1 ù x3 +

+ X1 ù x4 + ù x1x2 + x2 ù x3 + x2 ù x4

y9 = x4/y6 = ù x4 + x1x2

y10 = x4 ù → y7 = x4 (ù x1 + ù x2 + ù x3 + ù x4) = ù x1x4 + ù x2x4 + ù x3x4

y11 = x1 ~ y8 ~ y10 = (ù x1 (ù x1 + x2) (ù x1 + x3) (ù x1 + x4) (x1 + ù x2) (ù x2 + x3) (ù x2 + x4) +

+ X1 (x1 ù x2 + x1 ù x3 + x1 ù x4 + ù x1x2 + x2 ù x3 + x2 ù x4)) ~ y10 = ((ù x1 + ù x1x2) (ù x1 + x3) (ù x1 + x4) (x1 + ù x2) (ù x2 + x3) (ù x2 + x4) + (x1 ù x2 + x1 ù x3 + x1 ù x4 + x1x2 ù x3 + x1x2 ù x4)) ~ y10 = (ù x1 ù x2 (ù x1 + x3) ​​(ù x2 + x3) (ù x2 + x4) (ù x1 + x4) + (x1 ù x2 + x1 ù x3 + x1 ù x4 + + x1x2 ù x3 + x1x2 ù x4)) ~ y10 = ((ù x1 ù x2 + ù x1 ù x2x3) (ù x2 + x3) (ù x2 + x4) (ù x1 + x4) +

+ (X1 ù x2 + x1 ù x3 + x1 ù x4 + + x1x2 ù x3 + x1x2 ù x4)) ~ y10 = ((ù x1 ù x2 + ù x1 ù x2x3)

(Ù x2 + x4) (ù x1 + x4) + (x1 ù x2 + x1 ù x3 + x1 ù x4 + x1x2 ù x3 + x1x2 ù x4)) ~ y10 =

= ((Ù x1 ù x2 + ù x1 ù x2x4 + ù x1 ù x2x3 + ù x1 ù x2x3x4) (ù x1 + x4) + (x1 ù x2 + x1 ù x3 +

+ X1 ù x4 + x1x2 ù x3 + x1x2 ù x4)) ~ y10 = (ù x1 ù x2 + ù x1 ù x2x4 + ù x1 ù x2x3x4 +

+ X1 ù x2 + x1 ù x3 + x1 ù x4 + x1x2 ù x3 + x1x2 ù x4) ~ y10 = (ù x1 ù x2 + x1 ù x2 + x1 ù x3 +

+ X1 ù x4 + x1x2 ù x3 + x1x2 ù x4) ~ y10 = (ù x2 + x1 ù x3 + x1 ù x4 + x1x2 ù x3 + x1x2 ù x4) ~ y10 =

= (Ù x2 + x1 ù x3 + x1 ù x4) ~ y10 = x2 (ù x1 + x3) (ù x1 + x4) (x1 + ù x4) (x2 + ù x4) (x3 + ù x4) +

+ (Ù x2 + x1 ù x3 + x1 ù x4) (ù x1x4 + ù x2x4 + ù x3x4) = x2 (ù x1 + x3) (ù x1 ù x4 + x1x4)

(X2 + ù x4) (x3 + ù x4) + (ù x2 + x1 ù x3 + x1 ù x4) (ù x1x4 + ù x2x4 + ù x3x4) =

= X2 (ù x1 + x3) (ù x1x2 ù x4 + x1x2x4 + ù x1 ù x4) (x3 + ù x4) + (ù x2 + x1 ù x3 + x1 ù x4)

(Ù x1x4 + ù x2x4 + ù x3x4) = x2 (ù x1 + x3) (ù x1x2x3 ù x4 + x1x2x3x4 + ù x1x2x4 +

+ Ù x1x2 ù x4) + (ù x2 + x1 ù x3 + x1 ù x4) (ù x1x4 + ù x2x4 + ù x3x4) = (ù x1 + x3) (ù x1x2x4 +

+ X1x2x3x4 + ù x1x2x3x4) + (ù x2 + x1 ù x3 + x1 ù x4) (ù x1x4 + ù x2x4 + ù x3x4) =

= (Ù x1 + x3) (ù x1x2x4 + x1x2x3x4) + (ù x2 + x1 ù x3 + x1 ù x4) (ù x1x4 + ù x2x4 + ù x3x4) =

= Ù x1x2x4 + ù x1x2x3x4 + x1x2x3x4 + ù x1 ù x2x4 + ù x2x4 + ù x2 ù x3x4 + x1 ù x2 ù x3x4 +

+ X1 ù x3x4 = ù x1x2x3 + x1x2x3x4 + ù x2x4 + x1 ù x3x4

y12 = x1/y9 = ù x1 + x4 (ù x1 + ù x2) = ù x1 + ù x1x4 + ù x2x4 = x1 + ù x2x4

y13 = y9 ù → y10 = (ù x4 + x1x2) (x1 + ù x4) (x2 + ù x4) (x3 + ù x4) = (x1 ù x4 + ù x4 + x1x2 +

+ X1x2 ù x4) (x2 + ù x4) (x3 + ù x4) = (ù x4 + x1x2) (x2 + ù x4) (x3 + ù x4) = (x2 ù x4 + ù x4 +

+ X1x2 + x1x2 ù x4) (x3 + ù x4) = (ù x4 + x1x2) (x3 + ù x4) = x3 ù x4 + ù x4 + x1x2x3 +

+ X1x2 ù x4 = ù x4 + x1x2x3

y14 = y9 ~ y11 = x4 (ù x1 + ù x2) (x1 + ù x2 + ù x4) (ù x1 + ù x2 + ù x3 + ù x4) (x2 + ù x4)

(Ù x1 + x3 + ù x4) + (ù x4 + x1x2) (ù x1x2x4 + x1x2x3x4 + ù x2x4 + x1 ù x3x4) =

= X4 (ù x1 ù x2 + ù x1 ù x4 + x1 ù x2 + ù x2) (ù x1 + ù x2 + ù x3 + ù x4) (x2 + ù x4) (ù x1 + x3 + ù x4) +

+ (Ù x4 + x1x2) (ù x1x2x4 + x1x2x3x4 + ù x2x4 + x1 ù x3x4) = x4 (ù x2 + ù x1 ù x4) (ù x1 + ù x2 +

+ Ù x3 + ù x4) (ù x1x2 + x2x3 + x2 ù x4 + ù x1 ù x4 + ù x3 ù x4 + ù x4) + (ù x4 + x1x2) (ù x1x2x4 +

+ X1x2x3x4 + ù x2x4 + x1 ù x3x4) = ù x2x4 (ù x1 + ù x2 + ù x3 + ù x4) (ù x1x2 + x2x3 + ù x4) +

+ (Ù x4 + x1x2) (ù x1x2x4 + x1x2x3x4 + ù x2x4 + x1 ù x3x4) = (ù x1 ù x2x4 + ù x2x4 +

+ Ù x2 ù x3x4) (ù x1x2 + x2x3 + ù x4) + (ù x4 + x1x2) (ù x1x2x4 + x1x2x3x4 + ù x2x4 +

+ X1 ù x3x4) = ù x2x4 (ù x1x2 + x2x3 + ù x4) + (ù x4 + x1x2) (ù x1x2x4 + x1x2x3x4 + ù x2x4 +

x1 ù x3x4) = (ù x4 + x1x2) (ù x1x2x4 + x1x2x3x4 + ù x2x4 + x1 ù x3x4) = x1x2x3x4 +

+ X1x2 ù x3x4 = x1x2x4

y15 = y10/y12/y14 = ((x1 + ù x4) (x2 + ù x4) (x3 + ù x4) + x1 (x2 + ù x4)) / y14 =

= ((X1x2 + x1 ù x4 + x2 ù x4 + ù x4) + x1x2 + x1 ù x4) / y14 = ((x1x2x3 + x1x2 ù x4 + x3 ù x4 + ù x4) +

+ X1x2 + x1 ù x4) / y14 = (x1x2 + ù x4) / y14 = (ù x1 + ù x2) x4 + (ù x1 + ù x2 + ù x4) =

= Ù x1x4 + ù x2x4 + ù x1 + ù x2 + ù x4 = ù x1 + ù x2 + ù x4

y16 = y10 ù → y13 = (ù x1x4 + ù x2x4 + ù x3x4) x4 (ù x1 + ù x2 + ù x3) = ù x1x4 + ù x1 ù x2x4 +

+ Ù x1 ù x3x4 + ù x2x4 + ù x1 ù x2x4 + ù x1 ù x3x4 + ù x3x4 + ù x1 ù x3x4 + ù x2 ù x3x4 =

= Ù x1x4 + ù x2x4 + ù x3x4

y17 = y11 ~ y14 = (x1 + ù x2 + x4) (ù x1 + ù x2 + ù x3 + ù x4) (x2 + ù x4) (ù x1 + x3 + ù x4)

(Ù x1 + ù x2 + ù x4) + (ù x1x2x4 + x1x2x3x4 + ù x2x4 + x1 ù x3x4) x1x2x4 =

= (X1 ù x2 + x1 ù x3 + x1 ù x4 + ù x1 ù x2 + ù x2 + ù x2 ù x3 + ù x2 ù x4 + ù x1x4 + ù x2x4 + ù x3x4)

(Ù x1x2 + x2x3 + x2 ù x4 + ù x1 ù x4 + x3 ù x4 + ù x4) + x1x2x3x4 + x1x2 ù x3x4 =

= Ù x2 ù x4 + x1 ù x3 ù x4 + x1x2x3 ù x4 + x1 ù x4 + ù x1x2x4 + ù x1x2x3x4 + ù x1x2 ù x3x4 +

+ X1x2x3x4 + x1x2 ù x3x4 = ù x2 ù x4 + x1 ù x4 + ù x1x2x4 + ù x1x2x3x4 + ù x1x2 ù x3x4 +

+ X2x4 = ù x2 ù x4 + x1 ù x4 + x2x4

y18 = y15/y17 = x1x2x4 + (x2 + x4) (ù x1 + x4) (ù x2 + ù x4) = x1x2x4 + (ù x1x2 + x2x4 +

+ Ù x1x4 + x4) (ù x2 + ù x4) = x1x2x4 + (ù x1x2 + x4) (ù x2 + ù x4) = x1x2x4 + ù x1x2 ù x4 +

+ Ù x2x4 = ù x1x2 ù x4 + x1x4 + ù x2x4

y19 = y16 ù → y18 = (ù x1x4 + ù x2x4 + ù x3x4) (ù x1 + ù x2 + ù x4) (x1 + ù x2 + x4) (x2 + ù x4) =

= (Ù x1x4 + ù x2x4 + ù x3x4) (ù x1 + ù x2 + ù x4) (x1x2 + x1 ù x4 + ù x2 ù x4 + x2x4) =

= (Ù x1x4 + ù x2x4 + ù x3x4) (ù x1 ù x2 ù x4 + ù x1x2x4 + x1 ù x2 ù x4 + ù x2 ù x4 + x1x2 ù x4 +

+ X1 ù x4 + ù x2 ù x4) = (ù x1x4 + ù x2x4 + ù x3x4) (ù x1x2x4 + ù x2 ù x4 + x1 ù x4) =

= Ù x1x2x4 + ù x1x2 ù x3x4 = ù x1x2x4

y20 = y18 = ù x1x2 ù x4 + x1x4 + ù x2x4

Тепер виконаємо побудова зведеної таблиці. У лівій частині таблиці наводяться всі можливі набори з чотирьох аргументів - від нульового до п'ятнадцятого, а в правій - значення функції для кожного елемента логічної схеми.

x 1

x 2

x 3

x 4

y 5

y 6

y 7

y 8

y 9

y 10

y 11

y 12

y 13

y 14

y 15

y 16

y 17

y 18

y 19

y 20

0

0

0

0

1

1

0

0

1

0

0

0

1

0

1

0

1

0

0

0

0

0

0

1

1

1

0

0

0

1

1

1

0

0

1

1

0

1

0

1

0

0

1

0

1

1

0

0

1

0

0

0

1

0

1

0

1

0

0

0

0

0

1

1

1

1

0

0

0

1

1

1

0

0

1

1

0

1

0

1

0

1

0

0

0

1

0

1

1

0

0

0

1

0

1

0

0

1

0

1

0

1

0

1

0

1

0

1

0

1

1

0

0

0

1

1

1

0

1

0

0

1

1

0

0

1

0

1

1

0

0

0

1

0

1

0

0

1

0

1

0

1

1

1

0

1

0

1

0

1

1

0

0

0

1

1

1

0

1

0

1

0

0

0

0

1

0

1

1

0

0

1

1

0

1

0

1

0

0

0

1

0

0

1

0

1

0

1

0

1

1

1

0

0

1

1

0

1

0

1

1

0

1

0

0

1

0

1

1

0

0

1

1

0

1

0

1

0

0

0

1

0

1

1

0

1

0

1

0

1

1

1

0

0

1

1

0

1

0

1

1

1

0

0

1

0

0

1

1

0

0

1

1

0

1

0

1

0

0

0

1

1

0

1

1

0

0

1

1

1

1

1

0

1

0

1

1

1

0

1

1

1

1

0

1

0

0

1

1

0

0

1

1

0

1

0

1

0

0

0

1

1

1

1

1

0

1

0

1

0

1

1

1

1

0

0

1

1

0

1

Формула ù x 1 x 2 ù x 4 + x 1 x 4 + ù x 2 x 4, отримана для всієї таблиці, записана у вигляді ДНФ. Для переведення її в СДНФ, введемо одиниці для відсутніх елементів в кожен мінітерм:

СДНФ = (x 3 + ù x 3) (x 2 + ù x 2) x 1 x 4 + (x 3 + ù x 3) ù x 1 x 2 ù x 4 + (x 3 + ù x 3) (x 1 + ù x 1) ù x 2 x 4 =

= X 1 x 2 x 3 x 4 + x 1 x 2 ù x 3 x 4 + ù x 1 x 2 x 3 ù x 4 + ù x 1 x 2 ù x 3 ù x 4 + x 1 ù x 2 x 3 x 4 + x 1 ù x 2 ù x 3 x 4 +

+ Ù x 1 ù x 2 x 3 x 4 + ù x 1 ù x 2 ù x 3 x 4

Виконаємо переклад з C ДНФ в C КНФ:

C КНФ = (ù x 1 + ù x 2 + ù x 3 + ù x 4) (ù x 1 + ù x 2 + x 3 + ù x 4) (x 1 + ù x 2 + ù x 3 + x 4 ) (x 1 + ù x 2 + x 3 + x 4)

(Ù x 1 + x 2 + ù x 3 + ù x 4) (ù x 1 + x 2 + x 3 + ù x 4) (x 1 + x 2 + ù x 3 + ù x 4) (x 1 + x 2 + x 3 + ù x 4)

Завдання № 4

Мінімізація методами Квайна-МакКласкі і Петрика, а також за допомогою карт Карно булевої функції з вихідної таблиці істинності, отриманої в п.4

Метод Квайна-Мак-Класки

Розглянемо функцію чотирьох змінних Q = f (x 1, x 2, x 3, x 4) задану таблицею 2.

Їй відповідає діз'юнктівная досконала нормальна форма

x 1 x 2 x 3 x 4 + x 1 x 2 ù x 3 x 4 + ù x 1 x 2 x 3 ù x 4 + ù x 1 x 2 ù x 3 ù x 4 + x 1 ù x 2 x 3 x 4 + x 1 ù x 2 ù x 3 x 4 +

+ Ù x 1 ù x 2 x 3 x 4 + ù x 1 ù x 2 ù x 3 x 4

Безліч 0-Кубів після розбиття та впорядкування записується наступним чином:

0001

0100

0110

1001

0011

1101

1011

1111

K 0 =

Будемо попарно порівнювати S-куби з сусідніх поясів, склеюючи такі, що відрізняються тільки по одній координаті. Така операція склеювання відповідає об'єднанню двох S-кубів. Отримаємо (S +1)-куб, в якому склеюється координату замести символом «~». Склеювані куби будемо відзначати знаком «ü».

0001 ü

0100 ü

0110 ü

1001 ü

0011 ü

1101 ü

1011 ü

1111 ü

K '0 =

~ 001 ü

00 ~ 1 ü

01 ~ 0

1 ~ 01 ü

10 ~ 1 ü

~ 011 ü

11 ~ 1 ü

1 ~ 11 ü


K 1 =

K

~ 0 ~ 1

1 ~ ~ 1

K 2 =

K 3 = Æ

Очевидно, у безлічі K 2 склеювання S-кубів неможливо. Тому наступне безліч K 3 - пусте. Отримана скорочена форма містить чотири прості імпліканти (невідмічені куби, тобто ті, які не склеїлися в процесі порівняння).

Тепер побудуємо таблицю Квайна. Її рядкам відповідають прості імпліканти зі скороченої форми, стовпцях - констітуенти булевої функції.



0001

0100

0110

1001

0011

1101

1011

1111

01 ~ 0

a


ü

ü






~ 0 ~ 1

b

ü



ü

ü


ü


1 ~ ~ 1

c




ü


ü

ü

ü

Очевидно, кожна импликанта є суттєвою. У цьому випадку тупикова форма єдина. Вона ж буде і мінімальної формою.

МДНФ = ù x 1 x 2 ù x 4 + x 1 x 4 + ù x 2 x 4

Отримана формула в точності дорівнює отриманої ще на етапі аналізу логічної схеми. Дійсно, при аналізі ми користувалися аналітичної мінімізацією, застосовуючи ті чи інші властивості. Універсальний метод Квайна-Мак-Класки показав, що отримана ДНФ дійсно є мінімальною.

Отриманий висновок можна підтвердити також за допомогою методу Петрика. Логічне умова покриття всієї таблиці Квайна має вигляд:

b Ù a Ù a Ù (b Ú c) Ù b Ù c Ù (b Ú c) Ù c

Виробляючи прості перетворення, отримуємо:

a Ú b Ú c

Таким чином, за допомогою методу Петрика отримуємо такий вираз для МДНФ:

МДНФ = ù x 1 x 2 ù x 4 + x 1 x 4 + ù x 2 x 4

Бачимо, що воно збігається з виразом, отриманим за допомогою методу Квайна-Мак-Класки.

Тепер розглянемо мінімізацію методом карти Карно:

МДНФ = ù x 1 x 2 ù x 4 + x 1 x 4 + ù x 2 x 4

Ми отримали результат, який збігається з двома результатами, отриманими раніше. Це говорить про правильність зроблених обчислень.

Мінімізація методами Квайна-Мак-Класкі та Петрика, а також за допомогою карт Карно формули частково певної булевой функції, отриманої з таблиці істинності п.4, поповнений заданими байдужими вхідними наборами.

Вибір байдужих наборів

За побудованої таблиці істинності булевої функції заданої логічної схеми будується таблиця істинності частково певної булевой функції вибором чотирьох випадково вибраних байдужих вхідних двійкових наборів, на яких часткова булева функція не визначена (байдужа). У разі накладення байдужого набору на одиничний набір (на якому функція приймає значення «1») для даного набору значень аргументів зберігається значення функції, рівне «1».

Номер варіанту байдужих вхідних наборів часткової булевої функції {№ Наб1, № Наб2, № Наб3, № Наб4} з таблиці 8, що позначається як «№ Наборів», виходить визначенням зміщеного на «1» цілочисельного залишку від ділення «№ заліковки» на число « 11 »- число варіантів таблиці 8 за такою формулою:

«№ Наборів» = «№ заліковки»% 9 +1

де% - операція отримання цілочислового залишку від ділення.

«№ Наборів» = (9% 11) +1 = 3, тобто з таблиці 8 слід, що обрані байдужі набори {№ Наб1, № Наб2, № Наб3, № Наб4} = {8,10,11,12} =

= {0111, 1001, 1010, 1011}.

Таким чином, зрозуміло, що змін не відбудеться, тому що всі байдужі набори вже присутні в наборах булевої функції, отриманої зі зведеної таблиці. Значить обчислення мінімізації для функції, поповнений байдужими наборами, дасть результат, отриманий раннє, тобто

МДНФ = ù x 1 x 2 ù x 4 + x 1 x 4 + ù x 2 x 4

Переклад отриманих в пунктах 5 і 6 мінімальних формул з булевого базису в заданий функціональний базис.

Побудуємо логічну схему для МДНФ:

МДНФ = ù x 1 x 2 ù x 4 + x 1 x 4 + ù x 2 x 4

Перетворимо МДНФ з булевого базису {Ú, Ù, ù} в заданий функціональний базис:

МДНФ =((((( x 2 ù → x 4) ù → x 1) / (x 2 ù → x 4) ù → x 1 ))/(( x 4 ù → x 2) / (x 4 ù → x 2))) /

/ (((X 2 ù → x 4) ù → x 1) / (x 2 ù → x 4) ù → x 1 ))/(( x 4 ù → x 2) / (x 4 ù → x 2 ))))/( x 1 / x 4)

Логічна схема для отриманої формули булевої функції виглядає наступним чином:


Висновки

У ході виконання розрахунково-графічної роботи з дисципліни «Основи дискретної математики» були закріплені основні теоретичні знання і практичні навики.

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

Література:

1. Методичні вказівки виконання розрахунково-графічної роботи з дисципліни «Основи дискретної математики» для студентів спеціальностей 6.0804 і 6.0915. / Сост. А. Н. Мартинюк. - Одеса: ОНПУ, 2002.

2. Конспект лекцій з дисципліни «Основи дискретної математики» для студентів спеціальностей 6.0804 і 6.0915. / Сост. А. Н. Мартинюк. - Одеса: ОНПУ, 2002.

Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Контрольна робота
170кб. | скачати

Схожі роботи:
Основні положення дискретної математики
Прикладне вживання методів дискретної математики
Основи дискретної схемотехніки
Основи математики
Основи вищої математики
Психолого педагогічні основи навчання математики
Психолого-педагогічні основи навчання математики
Основи роботи в системі символьної математики MATLAB 5 2
Основи підготовки дітей до навчання математики у школі
© Усі права захищені
написати до нас