Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Хід заняття



Задача 1.Для даної функції , заданої векторно, проробити наступне :

1) Записати її ДДНФ і ДКНФ.

2)Методом Квайна знайти скорочену ДНФ.

3) Для скороченої ДНФ побудувати матрицю Квайна, указати ядрові імпліканти.

4) За допомогою матриці Квайна знайти мінімальну ДНФ, указати її складність.

5) Знайти мінімальну ДНФ даної функція за допомогою карт Карно, порівняти отриманий результат із ДНФ, знайденої в п.4Розв’язування. 1) Зобразимо таблицю функції f у виді двовимірної таблиці- карти Карно: Знайдемо ДДНФ даної функції:

zw xy
I

 

Знайдений ДКНФ даної функції:

 

2) Побудуємо скорочену ДНФ зі ДДНФ, використовуючи формули неповного склеювання і поглинання. Для зручності, замість символів перемінних будемо працювати тільки з показниками ступенів перемінних. Наприклад, замість будемо вживати набір 0-1. Тоді ДДНФ функції буде відповідати безліч усіх її одиничних наборів.

 

 

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

0 0 0 0 + 0 0 0 - + 0 - 0 0 + - 0 0 0 + - 0 0 - - - 0 0  
0 0 0 1 + 0 1 0 0 + 1 0 0 0 +  
 
0 0 – 1 + 0 1 – 0 - 0 0 1 + 1 0 0 - + - 1 0 0 + 1 – 0 0 + - 0 - 1 1 – 0 -  
0 0 1 1 + 0 1 1 0 + 1 0 0 1 + 1 1 0 0 +  
 
 
 
1 0 1 1 + 1 1 0 1 +  
- 0 1 1 + 1 0 – 1 + 1 – 0 1 + 1 1 0 - +  
 
 
 
 
1 смуга 2 смуга 3 смуга  

 

Тоді для застосування формули неповного склеювання досить переглянути всілякі пари наборів, що входять у сусідні групи. Результати склеювання наборів з I смуги помістимо в И смузі, а набори, що беруть участь у склеюваннях, позначимо хрестиком. В другій смузі знову застосовуємо, наскільки можливо, операцію склеювання, записуючи результати в III смугу і т.д. Після завершення процедури склеювання всі прості імпліканти потраплять у таблицю і не будуть позначені хрестиком. Позначені ж кон’юнкції поглинуться на етапі застосування формули поглинання.

Скорочена ДНФ даної булевой функції має вигляд:

3) Для одержання зі скороченої ДНФ мінімальної ДНФ зобразимо наступну таблицю - матрицю Квайна: Ядровими імплікантами будуть 1, 4 і 5, тому що для кожної з них найдеться одиничний набір, на якому вона одна приймає значення 1.

 

№ простої імпліканти
Прості імпліканти Одиничні набори
     
     
       
     
       
   
   
       
     
       

 

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

 

Задача 2.Нехай , , .

Побудувати карту Карно для функції . Знайти мінімальну КНФ, мінімальну ДНФ функції .

Розв’язування.

z xy

 

Карту Карно для функції від трьох змінних має такий вигляд.

Ми вважаємо її як би наклеєної на поверхню циліндра, тобто ототожнюємо верхню частину карти Карно з нижньої. При відшуканні мінімальної ДНФ одиниці карти Карно покриваємо прямокутниками виду 2x2 і 1x2, що відповідає імплікантам і xz відповідно, одержуємо мінімальну ДНФ .

Її складність дорівнює 3.

Для перебування мінімальної КНФ покриваємо нулі карти Карнау двома прямокутниками розмірами 1x2, що відповідають елементарним диз'юнкціям і . У результаті одержуємо мінімальну КНФ

При перебуванні мінімальної ДНФ функції заповнюємо карту- Карно і покриваємо одиниці карти прямокутниками можливо великих розмірів:

zw xy

 

Одержимо мінімальну ДНФ: .

Складність мінімальної ДНФ дорівнює 6.

Відшукаємо мінімальну КНФ . Для цього зробимо покриття нулів Карно: Мінімальна КНФ буде мати вигляд: .

zw xy