Головна

Лемма про функції, які не зберігають T_0 і T_1. Теорема Поста про повноту (доказ теореми справа наліво).

Лемма. якщо f  T0 і g  T1, то або  ? [{f, g}], або 0, 1 ? [{f, g}].

Доведення. Маємо f (0,..., 0) = 1 і g (1,..., 1) = 0. Якщо f (1,..., 1) = 0, то f (x,..., x) =  x і лема доведена. Нехай тепер f (1,..., 1) = 1. Тоді f (x,..., X) = 1 і, отже, 1 ? [{f, g}].

Залишається показати, що 0 ? [{f, g}]:

Слідство. якщо f  T0, g  T1, p  S і q  M, то або, 0, 1 ? [{f, g, p}], або, 0, 1 ? [{f, g, q}].

Теорема (критерій Поста). Теорема. Клас функцій C ? F є повним тоді і

тільки тоді, коли C не міститься в класах T0, T1, M, L, S.

Док-во. Назад, нехай B міститься в одному з п'яти перерахованих вище класів.

Виділимо в B систему функцій fT0, fT1, f S, f M, f L, котрі належать до класів

T0, T1, S, M і L відповідно. Без обмеження спільності можна вважати, що кожна з цих функцій залежить від фіксованого числа змінних x1,. . . , Xn. Покажемо, що за допомогою функцій fT0, fT1 і fS можна отримати константи 0 і 1. Якщо fT0 (1,..., 1) = 1, то функція ? (x) = fT0 (x,..., X) тотожно дорівнює 1, оскільки ? (0) = 1 = ? (1). Константа 0 виходить з fT1, оскільки

fT1 (1,..., 1) = 0. Якщо ж fT0 (1,..., 1) = 0, то ? (x) = fT0 (x,..., x) =! x, оскільки ? (0) = fT0 (0,..., 0) = 1 і ? (1) = fT (1,..., 1) = 0. По лемі 10 за допомогою x і fS можна отримати константу. Друга константа виходить застосуванням x. за допомогою констант 0, 1 і функції fM можна отримати! x. Нарешті, по лемі 12 за допомогою констант 0, 1 і функцій! X і fL можна отримати x1 & x2. Тепер повнота системи B випливає з повноти кон'юнкції і заперечення. Неповний клас функцій A назвемо предполним, якщо клас A ? {f} буде

повним для будь-якої функції f 6? A.


 



 Лемма про несамодвойственной функції. Лемма про немонотонної функції. |  Неорієнтовані графи. Ступені вершин. Сума ступенів вершин графа. Ізоморфізм графів. Приклад неізоморфних графів з однаковими ступенями.

 штрих Шеффера |  Знаходження мінімальної ДНФ. |  приклади |  Вершин, ребер і компонент зв'язності. |  Ейлерови і Гамільтона шляху. Критерій існування ейлерового шляху. |  Теорема Келі про кількість дерев на n вершинах. Коди Прюфера. |  Доведення формули Ейлера для плоских зв'язкових графів |  доведення коректності |  алгоритм |  Операції об'єднання і перетину регулярних мов |

© um.co.ua - учбові матеріали та реферати