Автор работы: Пользователь скрыл имя, 27 Ноября 2011 в 19:44, курс лекций
Линейная алгебра
I. ПРЕДМЕТ ЛИНЕЙНОЙ АЛГЕБРЫ
Вариант 6
1. Представить функцию в с.д.н.ф. Полученное выражение упростить.
Решение.
В стандартной форме данная булева функция определяется таблицей:
| x1 | x2 | x3 | x4 | f |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 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 | 0 |
| 1 | 1 | 1 | 1 | 0 |
Что в совершенной дизъюнктивной нормальной форме соответствует следующей формуле:
, после упрощения получаем выражение: .
2. Представить функцию в с.к.н.ф.
Решение.
Составим таблицу истинности функции:
| x | y | z | xy | ¬x | ¬z | y(¬z) | ¬x or y(¬z) | f |
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
Ответ: совершенная
конъюнктивная нормальная форма
.
3. Представить функцию
в виде полинома Жегалкина.
Решение.
Составим таблицу истинности функции:
| x | y | z | x or y | x or z | f |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Поскольку функция зависит от трех переменных, общий вид полинома Жегалкина задается равенством:
f (x1, x2, x3) = a123 x1 x2 x3 ⊕ a12 x1 x2 ⊕ a13 x1 x3 ⊕ a23 x2 x3 ⊕a1 x1 ⊕ a2 x2 ⊕ a3 x3 ⊕ a0 .
Подстановка в него
наборов значений переменных (x1,
x2, x3) — последовательностей
нулей и единиц, приводит к следующим соотношениям
для коэффициентов полинома: f (0 , 0
, 0 ) = a0 , f (0 , 0 , 1)
= a3 ⊕ a0 , f
(0 , 1 , 0) = a2 ⊕ a0 , f
(0 , 1 , 1) = a23 ⊕ a2 ⊕ a3 ⊕ a0 , f (1
, 0 , 0) = a1 ⊕ a0 ,
f (1 , 0 , 1) = a13 ⊕ a1 ⊕ a3 ⊕ a0 , f (1
, 1 , 0) = a12 ⊕ a1 ⊕ a2 ⊕ a0 , f (1
, 1 , 1) = a123 ⊕ a12 ⊕
a13 ⊕ a23 ⊕
a1 ⊕ a2 ⊕ a3 ⊕ a0.
Так как f (0 ,
0 , 0 ) = 0, то a0=0; f (0 , 0 , 1)
= a3 ⊕ 0 = 0, то a3
= 0; f (0 , 1 , 0) = a2 ⊕ 0 = 1, то a2
= 1; f (1 , 0 , 0) = a1 ⊕ 0 = 1 , то a1
= 1;
f (0 , 1 , 1) = a23 ⊕ 1 ⊕ 0 ⊕ 0 = a23 ⊕
1 = 0, то a23 = 1; f (1 , 0 , 1) =
a13 ⊕ 1 ⊕ 0 ⊕ 0 = a13 ⊕
1 = 1, то a13 = 0;
f (1 , 1 , 0) = a12 ⊕ 1 ⊕ 1 ⊕ 0 = a12 ⊕
0 = 1, то a12 =1; f (1 , 1 ,
1) = a123 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 = a123 ⊕ 0
= 1, то a123 = 1.
Ответ: f (x1,
x2, x3) = x1 x2
x3 ⊕ x1 x2 ⊕
x2 x3 ⊕ x1 ⊕ x2 .
4. От каких переменных зависит функция
Решение.
В стандартной форме данная булева функция определяется таблицей:
| x1 | x2 | x3 | x4 | f | х1 and х4 | ¬х1 | х3 and ¬х1 | or | ¬х4 | ¬х1 and ¬х4 | f после упрощения | |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | |
| 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | |
| 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | |
| 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |