Повнота систем булевих функцій
Приклад 6. Використовуючи критерій повноти, з’ясувати чи повна система P:
а) P = {x y, x z};
б) P = {x , x ~ yz};
в) P = {0, 1, x(y ~ z) (y z)};
г) P = {0, x y, x ~ y};
д) P = {x y, xy, x y};
е) P = {(0 1 1 0 1 0 0 1), (1 0 0 0 1 1 0 1), (0 0 0 1 1 1 0 0)};
ж) P = {(0 0 1 0), (1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1)};
з) P = (S \ M) (L \ (T1 T0));
к) P = (S M) (L \ M) (T0 \ S);
л) P = {x1 / x2, x1 ~ x2}.
Розв’язування
6б).
Нехай f1
= x
,
f2
= x
~ yz.
Тоді f1(0,
0, 0) = 0, тобто f1
T0,
але f2(0,
0, 0) = 0 ~ 0 = 1, тому f2
T0
і тому P
T0.
Крім того, f1(1,
1, 1) = 0, f1
T1
і P
T1.
Оскільки f1
= x
= x(y
1) = xy
x,
то f
L
і P
L.
Побудуємо двоїсту до f1
функцію:
=
=
+
= x
+
f1.
Отже, f1
S
і тому P
S.
Якщо
= (0, 0, 0),
= (0, 1, 1), то
<<
і f2(0,
0, 0) = 0 ~ 0 = 1, f2(0,
1, 1) = 0 ~ 1 = 0, тому f2
M,
P
M.
Оскільки система P
не включається повністю в жоден із
замкнутих класів T0,
T1,
L,
S,
M,
то за критерієм Поста система P
– повна.
Розв’язування 6е). Побудуємо таблицю істинності функцій
x1 |
x2 |
x3 |
f1 |
f2 |
f3 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
Оскільки
f1(0,
0, 0) = 0,
то f1
T0,
але f2(0,
0, 0) = 1,
тому f2
T0
і, отже, P
T0.
Крім того, f3(1,
1, 1) = 0, тому f3
T1
і P
T1.
Оскільки f1(1,
0, 0) = 1, f1(1,
0, 1) = 0, то f1
L
і P
L.
Побудуємо двоїсту до f3
функцію:
(0,
0, 0) = 1
f3(0,
0, 0) = 0. Тому f3
S
і P
S.
Якщо
= (0, 1, 0),
= (0, 1, 1), то
<<
і f1(0,
1, 0) = 1, f1(0,
1, 1) = 0, тому f2
M,
P
M.
Оскільки система P
не включається повністю в жоден із
замкнутих класів T0,
T1,
L,
S,
M,
то за критерієм Поста система P
– повна.
Приклад 7. Чи утворює повну систему функція m(x1, x2, x3) = x1x2 x1x3 x2x3 і функція f(x1) = ?
Приклад 8. Чи буде повною система P = {f1( ), f2( )}, якщо
а)
f1
S
\ M,
f2
L
S,
f2
1;
б)
f1
T0
L,
f2
S,
f1
1;
в) f1 T0 T1, f2 M \ T1, f1 f2 1.
Приклад 9. Чи буде повною система P = { f1( ), f2( ), f3( )}, якщо відомо, що f1 L (T0 T1), f2 M \ L, f1 f2 1, f1 f2 = 1?
Тема „Рекурсивні функції”
Для алгоритмічних проблем типовою є ситуація, коли потрібно знайти алгоритм для визначення функції f(x1, …, xn), яка набуває цілочислових значень та залежить від цілочислових аргументів. Позначимо через N = 0, 1, 2, … множину натуральних чисел.
Означення 1. Функція f(x1, …, xn) називається частково числовою n-місною функцією, якщо D0(f) Nn, а D3(f) Nn, де D0(f) – область визначення функції f(x1, …, xn), а D3(f) – область значень.
Якщо D0(f) = Nn, то функція f є всюди визначеною.
Означення 2. Обчислювальною називається числова функція f(x1, …, xn), значення якої можна обчислювати за допомогою деякого алгоритму на підставі відомих значень аргументу.
Зосередимося тепер на конкретному виборі засобів, за допомогою якого будуватимуться обчислювальні функції.
Означення 3. Наступні всюди визначені числові функції називаються найпростішими:
O(x) = 0 (нуль-функція).
S(x) = x + 1 (функція наступності, або додавання одиниці).
(x1,
…, xn)
= xm,
де m
= 1, 2, …, n
(функція проекції, або функція тотожності,
або введення фіктивних змінних).
Одним з основних засобів утворення нових функцій з тих, що вже існують, є суперпозиція.
Означення
4.
Оператором суперпозиції
називається підстановка у функцію m
змінних f(x1,
…, xm)
т функцій f1(x1,
…, xn),
…, fm(x1,
…, xn)
одних і тих самих n
змінних.
Наприклад, для функцій
f(x1, …, xm), f1(x1, …, xn), …, fm(x1, …, xn)
маємо
(f, f1, …, fm) = f(f1(x1, …, xn), …, fm(x1, …, xn)) = (x1, …, xn).
Означення 5. Оператор примітивної рекурсії Rn визначає (n + 1)-місну функцію f(x1, …, xn, y) через n-місну функцію(x1, …, xn) й (n + 2)-місну функцію (x1, …, xn, y, z) таким чином (за схемою примітивної рекурсії):
(1)
Той факт, що функція визначена схемою (1), виражається рівністю f(x1, …, xn, y) = Rn(, ), при n = 0, f(0) = a, f(y + 1) = (y, f(y)), a – константа.
Означення 6. Функція називається примітивно-рекурсивною, якщо вона може бути утворена з найпростіших функцій за допомогою скінченого числа застосувань операторів суперпозиції та примітивної рекурсії.
Цьому означенню можна надати більш формально індуктивного вигляду:
Функції O(x), S(x) й (для всіх натуральних n, m, де m = 1, …, n) є примітивно-рекурсивними.
Якщо f1(x1, …, xn), …, fm(x1, …, xn), (x1, …, xn) – примітивно-рекурсивні функції, то (, f1, …, fm) – примітивно-рекурсивні функції для будь-яких натуральних n, m.
Якщо f(x1, …, xn) і (x1, …, xn, y, z) – примітивно-рекурсивні функції, то Rn(f, ) – примітивно-рекурсивна функція.
Інших примітивно-рекурсивних функцій немає.