Теоретические основы. Проверить на полноту систему функций.

Воспользуемся критерием Поста. Проверим каждую из этих функций на принадлежность к замкнутым классам P₀, P₁, L, S, M.

1) P₀ - класс функий, сохраняющих нуль (т.е если f(0,0,...,0)=0, то f принадлежит этому классу). Проверяем
F₁(0,0)=0∼0=1 - не принадлежит классу P₀
F₂(0,0)=0∨0=0 - принадлежит классу P₀
F₃(0)=0=1 - не принадлежит этому классу.

2) P₁ - класс функций, сохраняющих единицу (т.е если f(1,1,...,1)=1, то f принадлежит этому классу).
F₁(1,1)=1∼1=1 - принадлежит P₁
F₂(1,1)=1∨1=1 - принадлежит P₁
F₃(1)=1=0 - не принадлжеит P₁

3) L -класс фунций, представимы линейным многочленом Жегалкина.
F₁(x,y)=x∼y=xy∨xy=xy⋅xy⊕xy⊕xy =0⊕(x⊕1)(y⊕1)⊕xy=xy⊕x⊕y⊕1⊕xy=x⊕y⊕1
Получился линейный многочлен, значит, функция принадлежит классу L

F₂(x,y)=x∨y=xy⊕x⊕y - нелиненый многочлен, значит, функция не принадлжеит классу L.
F₃(x)=x=x⊕1 - линейный многочлен, значит, функция принадлежит этому классу.

4) S - класс самодвойственных функций. То есть функций, для которых выполняется:
f(x₁,x₂,...,x_n)=f(x₁,x₂,...,x_n)

Самодвойственность проще всего определять по таблице значений функции.

Таблица самодвойственной функции, интересна тем, что столбец ее значений переходит сам в себя при инвертировании. То есть, например, первое значение функции должно равнятся отрицанию последнего, второе - отрицании предпоследнего, и так далее.

В нашем случает, самодвойственной функцие является только функция F₃.

5) M -класс монотоных функций.
Функция f называется монотоной, если для любых наборов значений переменных (α₁,α₂,...,α_n) и (β₁,β₂,...,β_n), таких что (α₁,α₂,...,α_n)≤(β₁,β₂,...,β_n), выполняется f(α₁,α₂,...,α_n)≤f(β₁,β₂,...,β_n).

Бинарное отношение ≤ понимается так: (α₁,α₂,...,α_n)≤(β₁,β₂,...,β_n) ⇔ ∀i (α_i≤β_i).

Тогда, функции F₁ и F₃ не монотоны, а функция F₂ - монотона.

Теперь, когда мы проверили все функции на принадлженость к этим пяти классам, можно построить таблицу Поста.

Согласно критерию Поста, чтобы система функций была полна, необходимо и достаточно, чтобы в кажом столбце таблицы Поста был хотя бы один минус. Значит, наша система функций полна.

Не нашли, что искали? Воспользуйтесь поиском: