 |
|
Находим полином Жегалкина по СДНФ
Индивидуальное домашнее задание № 1
Задача I. Вычисление слова по его номеру в словаре универсального языка (5 баллов)
По номеру №(x) = 1450 – 15 * 18 слова x в лексикографическом словаре позитивного языка над упорядоченным алфавитом 
определить это слово и проверить результат вычисления.
Решение:
|A| = 6
№(x) = 1450 – 15 * 18 = 1450 – 270 = 1180
Переводим в шестеричную систему
1180/6 = 196 (4)
196/6 = 32 (4)
32/6 = 5 (2)
X = 5244 = tbdd
Ответ: x = tbdd
Задача III. Совершенные нормальные формы булевых функций (5 баллов)
Найти СДНФ, СКНФ и полином Жегалкина булевой функции f от четырёх переменных, заданной таблицей:
| X1 | X2 | X3 | X4 | f |
| 0 | ||||
| 1 | ||||
| 1 | ||||
| 0 | ||||
| 1 | ||||
| 0 | ||||
| 1 | ||||
| 0 | ||||
| 1 | ||||
| 0 | ||||
| 0 | ||||
| 0 | ||||
| 0 | ||||
| 0 | ||||
| 1 |
В таблице B1B2B3B4B5B6B7B8B9 B11B12B13B14B15B16 – двоичная запись натурального числа 215+19N, где N – номер фамилии студента в журнале группы. Если возможно, сократить запись совершенной нормальной формы и сделать проверку, используя таблицу истинности.
Решение:
215+19 * 18 = 32768 + 342 = 33110
f = 33110 = 1000000101010110
Имеем исходную таблицу
| X1 | X2 | X3 | X4 | f |
| 0 | ||||
| 1 | ||||
| 1 | ||||
| 0 | ||||
| 1 | ||||
| 0 | ||||
| 1 | ||||
| 0 | ||||
| 1 | ||||
| 0 | ||||
| 0 | ||||
| 0 | ||||
| 0 | ||||
| 0 | ||||
| 1 |
Находим СДНФ
Выделяем в таблице истинности все строки, в которых функция принимает значение 1
f (X1, X2, X3, X4 ) = 
* 
* 
+ * 
* X3* 
+ *X2 
* 
* X2 * X3* 
+ X1 * 
* 
* + X1 * X2 * X3 * 
Находим СКНФ
Выделяем в таблице истинности все строки, в которых функция принимает значение 0
Выделяем элементарн 
е дизъюнкции и соединяем знаком конъюнкции
f (X1, X2, X3, X4 ) = (X1 + X2 + X3 + ) * (X1 + X2 + 
+ ) * (X1 + + X3 + ) *
(X1 + + + 
( 
X2 + X3+ 
) * ( X2 + + 
* ( X2 + + 
+ 
X3 + 
)* 
+ X3+ + + + )
Находим полином Жегалкина по СДНФ
f (X1, X2, X3, X4 ) = * * + * * X3* + *X2 * * X2 * X3* + X1 * * * + X1 * X2 * X3 * = * * 
* * X3* *X2 * 
* X2 * X3* X1 * * * X1 * X2 * X3 * =
= (1 
(1 
(1 
X3 
) 
(1 
(1 
(1 
) 
(1 
) X1 * X2 * X3 * =
= 
X3 
(1 
X1 * X2 * X3 * = 
X3 
X1 X2 X3 = P
Задача IV. Синтез булевой функции логической схемой из функциональных элементов (5 баллов)
Синтезировать булеву функцию из предыдущей задачи III с помощью логической схемы из стандартных функциональных элементов (дублятора, дизъюнктора, конъюнктора и инвертора). Провести анализ результата и представить его в виде соответствующего графа.
Задача V. Синтез контактной (переключательной) схемы (5 баллов)
Методом каскадов синтезировать контактную (переключательную) схему для булевой функции из задачи III. Проверить результат, используя диаграмму дерева анализа, и представить его в виде соответствующего графа.