1.2. Классы функций, сохраняющих 0 и 1, т0 и т1

1. Перечислить все элементарные булевы функции, сохраняющие 0. Перечислить все элементарные булевы функции, сохраняющие 1.

2. Определить мощность множеств:

2.1.

2.2.

3. Являются ли замкнутыми следующие множества:

1. P₂(0), P₂ (1), P₂(2),

2. T₁(0), T₁(1), T₁(2),

3. T₀(0), T₀(1), T₀(2),

4. T₀T_1,

5. T₀T₁.

4. Какие из множеств функций полны:

1. P₂(0), P₂(1), P₂(2);

2. T₁(0), T₁(1), T₁(2),

3. T₀(0), T₀(1), T₀(2),

4. Т₀Т₁,

5. Т₀Т₁?

5. Докажите, что для любых множеств D₁, D₂P₂ справедливо включение [D₁][D₂][D₁D₂]. Приведите пример, когда [D₁][D₂][D₁D₂].

1.3. Класс самодвойственных функций , s

1. Является ли функция g двойственной к функции f, если:

   1. f=xy, g=xy;

   2. f=xy, g=yx;

   3. f=xyxzyz, g=xyxzyz;

   4. f=xyz, g=xyz;

   5. 

2. Самодвойственная ли функция f:

   1. f=maj(x,y,z);

   2. 

   3. 

   4. 

   5. f=x₁x₂…x_2m+1 {0,1}.

3. Доказать, что если то |N₁(f)|=2^n-1.

4. Показать, что не существует самодвойственных функций, существенно зависящих от двух переменных.

5. Из не самодвойственной функции f подстановкой вместо переменных тождественной функции х и функции отрицания х получить константу.

   1. f=(0011 1001);

   2. f=(xy)(xz);

   3. f=xyxzytzt.

6. Пусть функции и удовлетворяют условию: Доказать, что если то fS.

7. Можно ли из функции f с помощью операции суперпозиции получить функцию g, если:

1. =(1011 0010), =(1000);

2. =(1111.0111.0001.0000), =(0001.0111);

3. =(1100.1100), =(0011.00011).

7. Рассмотрите работу леммы о не самодвойственных функциях на примере x₁x₂x₃.

1.4. Класс монотонных функций, м

1. Какие из перечисленных ниже функций являются монотонными:

1. x(xy);

2. x(yx);

3. xy(xy);

4. xyyzzxz;

5. f( =(0011 0111);

6. f( =(0110 0111);

7. 

8. 

2. Сколько существует таких монотонных функций , что f(011)=f(101)=1 f(001)=0? Сколько таких функций принадлежит множеству M\S? Есть ли среди них функции с фиктивными переменными?

3. Пусть существенно зависит от всех своих переменных. Найти

4. Перечислить все функции удовлетворяющие следующим условиям:

1. f(1000)=1, f(0111)=0;

2. f(1000)=1, ;

3. f(0100)f(1011), - симметрическая, т. е. Имеет вид

4. f(1001)=0, fS.

1.5. Класс линейных функций, l

1. Разлагая функцию f в полином Жегалкина, выяснить, является ли она линейной:

   1. 

   2. 

   3. 

   4. 

2. Доказать, что если на любых двух соседних наборах принимает противоположные значения, то она линейна. Верно ли обратное утверждение?

3. Доказать, что если и не является константой, то |N₁(f)|=2^n-1. Верно ли обратное?

4. Выяснить, является ли линейной функция f:

4.1. = (1010 1010 0110 1000);

4.2. = (1001 0110 011 1001);

4.3. = (1001 0110 1001 0110);

4.4. = (0110 1001 1010 0101).

5. Найти число самодвойственных функций, принадлежащих L(n).

6. Показать, что функцию xy нельзя получить суперпозицией функций xyz, x1, xy.

7. Можно ли из функции f подстановкой вместо ее переменных 0,1,x,x получить x&y?

   1. =(1110 1000);

   2. =(0111 1111);

   3. 7.3. =(1001 1001);

   4. 

8. Можно ли функцию xy реализовать формулой над множеством Ф, где

   1. Ф=L{xyxzyz};

   2. Ф=L\S;

   3. Ф=(L{maj(x,y,z)})\S.

   4. Ф=(L{xy})\S.

9. Рассмотрите работу леммы о нелинейных функциях на примере функции x₁x_2,

10. Какие из ниже перечисленных систем образуют базис в L?

    1. {1, xy}

    2. {xy, xyz,};

    3. {xy, xy, 0}

    4. {0, xyz1}

    5. {1xyz, xyz}.

11. Доказать, что если то N₁(f)=2^n-1.