Задачі до теми „Двоїстість і клас самодвоїстих функцій”
Приклад 1. Перевірити, чи є функція g двоїстою до функції f, якщо:
а) f(x, y) = x y, g(x, y) = x ~ y;
б) f(x, y) = x y, g(x, y) = y x;
в) f(x, y, z) = xy xz yz, g(x, y, z) = xy xz yz;
г) f(x, y, z) = x y z, g(x, y, z) = x y z;
д) f(x, y, z) = (x(y ~ z)), g(x, y, z) = (0 1 1 0 1 1 0 1).
Розв’язування
1а).
Запишемо для функції f
= x
y,
яка дорівнює 1 на наборах (0, 1), (1, 0) ДДНФ:
f
=
y
x
.
Тоді f*
=
=
.
За законами де Моргана
f*
=
=
= (
)(
)
= (
y)(x
)
= xy
.
Функція g = x ~ y дорівнює 1 на наборах (0, 0), (1, 1) і тому ДДНФ даної функції є форма вигляду g = xy, тобто f* = g.
Розв’язування 1б). Оскільки функція f = x y = y, то
f*
=
=
=
=
y.
Функція
g
= y
x
=
x
=
=
=
,
Отже, f*
g.
Розв’язування 1в). Використовуючи формули x(y z) = xy xz, x y = (x + y)( + ), маємо
g*
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
= (x
+ y
+
)(x
+
+ z)(y
+ z)
=
= (x + x + xz + xy + yz + x + )(y + z) = (x + yz + )(y + z) = xy + xz + yz = f(x, y, z).
Отже, g* = f(x, y, z).
Розв’язування 1д). Використовуючи формули x ~ y = + xy, маємо
f*
=
=
=
=
=
=
=
(
x
+ y
+ z)
= 0.
Отже, f*(x, y, z) = 0, g(x, y, z) = (0 1 1 0 0 1 1 0 1). Тому f* g.
Приклад 2. Навести приклад самодвоїстої функції, яка одночасно була б лінійною.
Приклад 3. Якщо 1 і 2 самодвоїсті функції, то чи будуть самодвоїстими функції 1 2 і 12?
Приклад 4. Показати, що не існує самодвоїстої функції, істотно залежної від двох змінних.
Приклад 5. Використовуючи принцип двоїстості, побудувати формулу, що реалізує функцію, двоїсту до функції f. Одержаний вираз спростити (записавши в ДНФ або у вигляді полінома Жегалкіна):
а) f = xy yz xt zt; г) f = ( y (y 1)) 1;
б) f = x y(zt ) ; д) f = ( / y ) ((y ~ z) );
в) f = (x y) ((x y) / ( ~ yz)); е) f = ( ~ yz) (x ).
Розв’язування 5в). Розглянемо підформули f1 = x y, f2 = x y, f3 = ~ yz. Тоді f = f1 (f2 f3). Двоїстими до f1, f2, f3 будуть функції
=
=
=
y,
=
=
,
=
.
Тоді згідно з принципом двоїстості
f*
=
=
=
=
.
Розв’язування 5д). Використовуючи формули x y = , x / y = , x y = (x + y)( + ), x ~ y = + xy, маємо
f*
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
= (z
+ y)(
+
)(
+
)(
+ z)
= (z
+ y
)(
+
z
+
+
z)
= z
+ z
+
z
+
z
+
y
=
z
+
y
.
Отже, f* = y + z .
Розв’язування 5е). Використовуючи формули x ~ y = + xy, x y = + y, x y = , маємо
f*
=
=
=
=
=
+
= x
+
(y
+ z)
+ x
+
+ z
= x
+
y
+
z
+ x
+
+ z
=
z
+
y
+ x
+
+ z
= x
+
+ z
+
y.
Приклад 6. Перевірити, чи є самодвоїстою функція f:
а) f( ) = m(x1, x2, x3);
б)
f(
)
=
;
в) f( ) = ( x2 )x4 x2 ;
г) f( ) = (0 0 0 1 0 0 1 0 0 1 1 0 0 1 1 1);
д)
f(
)
= x1
x2
…
x2m+1
,
{0, 1}.
Розв’язування 6б). Користуючись формулою x y = + y, маємо
f*
=
=
=
=
=
=
=
=
=
x3.
f(
)
=
=
=
=
=
+
x1x3
+
+ x3
=
=
x1
+ x1x3
+
+ x3
=
+ x3
=
,
f* f( ). Отже, функція f( ) не самодвоїста.
Розв’язування 6в). Перетворимо функцію
f*(
)
=
=
=
=
= (
+ x4)(
x2
+ x4)(
+ x4)(
+ x2
+
)
=
= ( x2 + x4 + x2x4 + x4)( + x4 + x2 + x4x2 + x4 + ) =
= ( x2 + x4 + x2x4 + x4)( + x4 + x2x4) = ( x2 + x4)( + x4 + x2x4) =
= x2 + x4 + x2x4 + x4 + x2x4 =
= x2 + x4 + x4 + x2x4.
Отже, f* f( ), функція f( ) не самодвоїста.
Приклад
7.
Довести, що функція f(
)
самодвоїста тоді і тільки тоді, коли в
розкладі f(
)
= x1f(1,
x2,
…, xn)
f(0,
x2,
…, xn)
= x1
(
)
(
)
x1-компонента
(
)
двоїста до її
-компоненти
(
).
Приклад
8.
Встановити, чи є самодвоїстою функція
f(
)
= x1
~ x2?
Приклад 9. Навести приклад самодвоїстої функції, яка одночасно була б лінійною.
Приклад 10. Перевірити, чи f1( ) = x1 x2, f2( ) = x1 / x2 T0, T1, L, S, M.
Приклад 11. Перерахувати всі самодвоїсті функції, які істотно залежать від змінних x1, x2, x3 і показати, що кожну з цих функцій можна подати або у вигляді m(x, y, z), або у вигляді x y z , де , , , {0, 1}.
Приклад 12. При яких значеннях n 2 функція f( ) самодвоїста?
а) f( ) = x1(x2 x3 … xn) x2(x3 … xn) … xn – 2(xn – 1 xn) xn – 1xn;
б) f( ) = x1(x2 … xn) x2(x3 … xn)… xn – 2(xn – 1xn) xn – 1xn;
в) f( ) = (x1 x2) (x2 x3) … (xn – 1 xn) (xn x2);
г) f( ) = x1 x2 … xn.
Приклад 13. Довести, що коли
а) f(x1, x2, …, xn) S, то f(x, x, …, x) {x, };
б) f( ) S , то m(x1 , x2 x3 f) x3 x4 S;
в) f( ) S , то f x2x3 x3 x2 x4 x5 S.
Розв’язування 13а). Якщо f(x1, x2, …, xn) S, то на протилежних наборах функція f набуває протилежних значень, тобто: 1) f(0, 0, …, 0) = 0, f(1, 1, …, 1) = 1 або 2) f(0, 0, …, 0) = 1, f(1, 1, …, 1) = 0. Розглянемо функцію (x) = f(x, x, …, x). У випадку 1) маємо: (0) = f(0, …, 0) = 0, (1) = f(1, …, 1) = 1, тобто (x) = x, а у випадку 2) (0) = f(0, …, 0) = 1, (1) = f(1, …, 1) = 0, тобто (x) = ; f(x, x, …, x) {x, }.
Приклад 14. Із несамодвоїстої функції f за допомогою підстановки на місце змінних x та побудувати константу:
а) f = (0 0 1 1 1 0 0 1); в) f = (x y) (x y);
б) f = (x + + z)t + yz; г) f = xy + xz + yt + zt.
Розв’язування
14а).
Функція f
несамодвоїста, оскільки на протилежних
наборах
= (0, 0, 1) і
= (1, 1, 0) маємо f(
)
= f(
)
= 0, тобто f
не набуває протилежних значень. Тоді
із леми про несамодвоїсту функцію
випливає, що підставляючи на місця
змінних x,
,
можна побудувати константу.
Приклад 15. Чи можна з функції f за допомогою операції суперпозиції дістати функцію g, якщо:
а) f = (1 0 1 1 0 0 1 0), g = (1 0 0 0);
б) f = (1 1 1 1 0 1 1 1 0 0 0 1 0 0 0 0), g = (0 0 0 1 0 1 1 1);
в) f = (1 1 0 0 1 1 0 0), g = (0 0 1 1 0 0 1 1).
Приклад 15. Чи можна з функції f за допомогою операції суперпозиції дістати функцію g, якщо:
а) f = (1 0 1 1 0 0 1 0), g = (1 0 0 0);
б) f = (1 1 1 1 0 1 1 1 0 0 0 1 0 0 0 0), g = (0 0 0 1 0 1 1 1);
в) f = (1 1 0 0 1 1 0 0), g = (0 0 1 1 0 0 1 1).
Приклад 16. Чи самодвоїста множина M?
а) M = {x y z, m(x y, x ~ z, y ~ };
б) M = {xy, x + y, x y m(x, y, z)};
в) M = {(x y) y, (x + y) x y, (x + y + z)t + yz};
г) M = S \ {x y , m(x, , z)};