Составители:
Рубрика:
15
x
1
0= x
2
0= x
3
1
=
, тогда fx x x(, , )
123
0
=
, fx x x(, , )
123
1= , поэтому
),,(),,(
321321
xxxfxxxf ≠
, следовательно функция f несамодвойственна.
8.30. Функция )1011(
=f немонотонная, т.к.
()()00 01
<
, но )1,0()0,0( ff > .
9.30. Для доказательства полноты системы
},,{
21121
xxxxx →↔ необходимо проверить,
что система содержит функцию не сохраняющую 0, функцию не сохраняющую 1, немоно-
тонную функцию, несамодвойственную функцию и нелинейную функцию. Докажем полноту
системы
{}
=→
∑
xxxx x
1211 2
~,, . Обозначим fxx x x
112 1 2
(, ) ~
=
и выпишем ее
таблицу истинности
x
1
x
2
xx
12
~
0 0 1
0 1 0
1 0 0
1 1 1
Функция f
1
не сохраняет 0. Выясним, является ли f
1
самодвойственной.
x
1
x
2
xx
12
~
fxx
112
(, )
1 1 1 0
1 0 0 1
0 1 0 1
0 0 1 0
Т.к. fxx fxx
112 11 2
(, ) (, )≠ , то f
1
несамодвойственна.
Функция
fx x
2
()= немонотонная, и не сохраняет 1. Найдем полином Жегалкина для
fxx x x
312 1 2
(, )=→ = aaxaxaxx
011221212
⊕
⊕
⊕
x
1
x
2
x
1
x
2
xx
12
→
0 0 1 1 1
0 1 1 0 0
1 0 0 1 1
1 1 0 0 1
a
0
1= ; 01 1
22
=⊕ ⇒ =aa; 11 0
11
=
⊕
⇒
=
aa ; 11 1 1
12 12
=
⊕
⊕⇒
=
aa;
x1 = 0 x 2 = 0 x 3 = 1 , тогда f ( x1 , x 2 , x 3 ) = 0 , f ( x1 , x 2 , x 3 ) = 1 , поэтому
f ( x1 , x2 , x3 ) ≠ f ( x1 , x2 , x3 ) , следовательно функция f несамодвойственна.
8.30. Функция f = (1011) немонотонная, т.к. ( 00) < ( 01) , но f (0,0) > f (0,1) .
9.30. Для доказательства полноты системы {x1 ↔ x2 , x1 , x1 → x2 } необходимо проверить,
что система содержит функцию не сохраняющую 0, функцию не сохраняющую 1, немоно-
тонную функцию, несамодвойственную функцию и нелинейную функцию. Докажем полноту
системы ∑ ={x1 ~ x 2 , x1 , x1 → x 2 } . Обозначим f 1 ( x1 , x 2 ) = x1 ~ x 2 и выпишем ее
таблицу истинности
x1 x2 x1 ~ x 2
0 0 1
0 1 0
1 0 0
1 1 1
Функция f1 не сохраняет 0. Выясним, является ли f1 самодвойственной.
x1 x2 x1 ~ x 2 f 1 ( x1 , x 2 )
1 1 1 0
1 0 0 1
0 1 0 1
0 0 1 0
Т.к. f 1 ( x1 , x 2 ) ≠ f 1 ( x1 , x 2 ) , то f1 несамодвойственна.
Функция f 2 ( x ) = x немонотонная, и не сохраняет 1. Найдем полином Жегалкина для
f 3 ( x1 , x 2 ) = x1 → x 2 = a 0 ⊕ a1 x1 ⊕ a 2 x 2 ⊕ a12 x1 x 2
x1 x2 x1 x2 x1 → x 2
0 0 1 1 1
0 1 1 0 0
1 0 0 1 1
1 1 0 0 1
a 0 = 1 ; 0 = 1 ⊕ a 2 ⇒ a 2 = 1 ; 1 = 1 ⊕ a1 ⇒ a1 = 0 ; 1 = 1 ⊕ 1 ⊕ a12 ⇒ a12 = 1 ;
15
