Лекции по "Алгебре"

Совершенная конъюнктивная  нормальная форма:

, после упрощения получаем  выражение: , зависящее от .

Ответ: функция  зависит от . 

5. При каких  и система функций полна в

Решение.

   Так как для того чтобы система  булевых функций {f₁ (x₁₁,..., x_1p1),..., f_s (x_s1,..., x_sps),…} была полна, необходимо и достаточно, чтобы она содержала функцию, не сохраняющую 0; функцию, не сохраняющую 1; несамодвойственную функцию; немонотонную функцию; нелинейную функцию, а функция является сохраняющей 0 (так как ), сохраняющей 1 (так как ), несамодвойственной (так как , но ), монотонной (так как для любой пары наборов a = (a₁,...,a_n) и b = (b₁,...,b_n) таких, что a ≼ b,                  f (a) £ f(b)) и нелинейной (так как полином этой функции имеет вид f (x, y, z) = x Å y Å z Å yz Å xz Å xy Å xyz), то для того чтобы система функций была полна, необходимо и достаточно, чтобы функция не сохраняла 0 (то есть ), не сохраняла 1 (то есть ) и была немонотонной (то есть и ). Следовательно, имеет место система уравнений: ; откуда и .

   Ответ: система функций полна в тогда и только тогда, когда и .