37331
Аналитическое и табличное представление булевой функции
Контрольная
Математика и математический анализ
Аналитическое и табличное представление булевой функции. Представление функции в ДНСФ. Минимизация функции по формулам склеивания. Минимизация функции методом Карно.
Русский
2013-09-24
315.5 KB
8 чел.
Содержание
[1] Задание
[2] [3] 1.1 Аналитическое и табличное представление булевой функции. [4] 1.2 Представление функции в ДНСФ. [5] 1.3 Минимизация функции по формулам склеивания. [6] 1.4 Минимизация функции методом Карно. [7] 1.5 Минимизация функции методом Квайна. [8] 1.6 Представление функции в базисе И-НЕ. [9] 1.7 Представление функции в КНСФ. [10] 1.8 Минимизация функции по формулам склеивания. [11] 1.9 Минимизация функции методом Карно. [12] 1.10 Преобразователь кодов.
[13] |
Пусть мы имеем функцию четырех переменных, как суперпозицию всех элементарных функций, заданную аналитически:
Представим функцию в табличном виде:
x1 |
x2 |
x3 |
x4 |
f |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
Представим функцию в ДНСФ (дизъюнктивная нормальная совершенная формула):
Произведем минимизацию функции при помощи формулы склеивания ():
Произведем минимизацию методом Карно:
1 |
1 |
1 |
0 |
|
1 |
1 |
1 |
0 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
Произведем минимизацию методом Квайна:
выпишем все сочетания, соответствующие единичному значению функции и сгруппируем их по количеству единиц:
0000
0001
0100
0101
0110
1010
1100
1101
1110
1110
Произведем склеивание соседних наборов согласно правилу (), получим:
000-
0-00
0-01
01-0
-100
-101
11-0
01-1
1-10
Сгруппируем наборы и произведем склеивание еще раз:
0-00 -100 01-0 000-
0-01 -101 11-0
1-10 -10- 01-1
0-0- -1-0
1-10 01
В итоге получим:
000-
0-0-
-10-
-1-0
01--
1-00
Представим полученный результат в табличной реализации:
f |
||||||||||
X |
X |
X |
X |
|||||||
X |
X |
X |
X |
|||||||
X |
X |
X |
X |
|||||||
X |
X |
X |
X |
|||||||
X |
X |
|||||||||
X |
X |
Получим:
Выполнив минимизацию мы получили ДНФ функции, применив закон Де-Моргана (), перейдем к базису И-НЕ:
Представим функцию в КНСФ (конъюнктивная нормальная совершенная формула):
Произведем минимизацию функции при помощи формулы склеивания ():
Произведем минимизацию методом Карно:
1 |
1 |
1 |
0 |
|
1 |
1 |
1 |
0 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
Выполнив минимизацию мы получили ДНФ функции, применив закон Де-Моргана (), перейдем к базису ИЛИ-НЕ:
Разработаем преобразователь кодов. Пусть нам необходимо преобразовать бинарный код в код Грея. Зададим два кода таблично:
Десятичный код |
Бинарный код |
Код Грея |
0 |
0000 |
0000 |
1 |
0001 |
0001 |
2 |
0010 |
0011 |
3 |
0011 |
0010 |
4 |
0100 |
0110 |
5 |
0101 |
0111 |
6 |
0110 |
0111 |
7 |
0111 |
0100 |
8 |
1000 |
1100 |
9 |
1001 |
1101 |
Как видно из таблицы, старший разряд кода Грея совпадает со старшим кодом числа, записанного бинарным кодом, поэтому старший разряд со входа достаточно передать на выход. Остальные разряды зададим таблично и минимизируем при помощи метода Карно. Обозначим входной код как x1x2x3x4, а выходной как y1y2y3y4, тогда (начиная со старших разрядов):
x1 |
x2 |
x3 |
x4 |
y2 |
y3 |
y4 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
Минимизируем функцию методом Карно:
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
0 |
0 |
Выполнив минимизацию мы получили ДНФ функции, применив закон Де-Моргана (), перейдем к базису И-НЕ:
Минимизируем функцию методом Карно:
0 |
1 |
0 |
0 |
|
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
Выполнив минимизацию мы получили ДНФ функции, применив закон Де-Моргана (), перейдем к базису И-НЕ:
Минимизируем функцию методом Карно:
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
|
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
0 |
Выполнив минимизацию мы получили ДНФ функции, применив закон Де-Моргана (), перейдем к базису И-НЕ:
Таким образом, выполнив минимизацию функций, мы получили преобразователь кодов (бинарный - Грея), выполненный на базисе элементов И-НЕ:
На рисунке 1 показан технологический процесс, который заключается в следующем. Имеется конвейер 1, который двигается только в прямом направлении; два манипулятора 4 и 5, предназначенные для транспортировки детали в корзины 2 и 3; корзина 2 для деталей зеленого цвета; корзина 3 для деталей красного цвета; корзина 6 для деталей любого другого цвета.
Имеются датчики:
х1 датчик информирующий о том, что деталь красного цвета;
х2 датчик информирующий о том, что деталь зеленого цвета;
х3 датчик конечного положения манипулятора 4;
х4 датчик конечного положения манипулятора 5;
Имеются привода, выполняющие следующие действия:
у1 движение конвейера на один шаг;
у2 движение конвейера на два шага;
у5 непрерывное движение конвейера;
у3 движение манипулятора 4 в прямом направлении;
у6 движение манипулятора 4 в обратном направлении;
у4 движение манипулятора 5 в прямом направлении;
у7 движение манипулятора 5 в обратном направлении;
Необходимо придумать микропрограммный аппарат, который управлял бы станком, который в свою очередь выполнял следующую операцию. При начальном запуске включается привод конвейера в режим непрерывного движения (у5). При этом предполагается, что в некоторый момент на нем окажется деталь. Когда деталь окажется напротив датчиков х1 и х2, может произойти следующее. Датчики х1 и х2 настроены таким образом, что обладают чувствительностью в определенной области спектра, а именно датчик х1 районе красного цвета, а датчик х2 зеленого. Если деталь оказалась красного цвета (сработал датчик х1), то необходимо провести конвейер на 2 шага (у2), затем включить манипулятор 5 в прямом направлении (у4), который сбросит деталь в ящик 3; после всего этого необходимо включить манипулятор 5 в обратном направлении и запустить конвейер в режим непрерывного движения (у5). Если деталь оказалась зеленого цвета (сработал датчик х2), то необходимо провести конвейер на 1 шаг (у1), затем включить манипулятор 4 в прямом направлении (у3), который сбросит деталь в ящик 2; после всего этого необходимо включить манипулятор 4 в обратном направлении и запустить конвейер в режим непрерывного движения (у5). Если не сработал ни один из датчиков, то конвейер продолжает двигаться и деталь, оказавшееся не красного и не зеленого цвета, будет сброшена в корзину 6. Таким образом будет осуществляться сортировка деталей по цветам.
Опишем все вышеперечисленные действия в таблице:
N операции |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
Датчик |
1 |
y5 |
x1 |
||||||
2 |
y2 |
y4 |
x4 |
|||||
3 |
y5 |
y7 |
||||||
4 |
у5 |
x2 |
||||||
5 |
y1 |
y3 |
x3 |
|||||
6 |
y5 |
y6 |
А также другие работы, которые могут Вас заинтересовать | |||
63205. | Цивільно-правова відповідальність | 24.03 KB | |
Мета: ознайомити учнів з особливостями та порядком притягнення до цивільноправової відповідальності; сформувати розуміння можливої відповідальності за завдану шкоду; виховувати почуття відповідальності за свої дії. | |||
63207. | Спадкове право | 27.55 KB | |
Мета: розкрити основні поняття спадкового права; познайомити учнів з особливостями спадкового права з умовами відкриття спадщини й винесення права на спадщину; виховувати в учнів правову культуру та правову свідомість. | |||
63211. | Узагальнення знань за темою «Київська Русь у другій половині XI — першій половині XIII ст.» | 380 KB | |
Мета: повторити та узагальнити матеріал, вивчений із теми «Київська Русь у другій половині XI — першій половині XIII ст.», підготуватися до уроку тематичного оцінювання; розвивати в учнів уміння аналізувати матеріал, робити висновки, виділяти головне, удосконалювати навички роботи з історичними джерелами... | |||