Вариант 1.

1. Докажите, что (А ٧ B) ٨(B ٧C) ٨(C ٨A) = (А ٧B) ٨(C ٨A), где А, В, C – простые высказывания.

2. Функция f(x₁, x₂, x₃) принимает единичные значения на наборах №№ 1, 2, 5, 6, 7.

3. Является ли полной система булевых функций, состоящая из дизъюнкции, константы 0 и эквивалентности?

Вариант 2.

1. Верно ли, что (А ٨ (B ٧ С) ٨(С ٧D) = А ٧B ٨C ٧С ٨D, где А, В, С, D – простые высказывания?

2. Функция f(x₁, x₂, x₃) принимает единичные значения на наборах №№ 0, 1, 4, 6, 7.

3. Является ли полной система булевых функций, состоящая из дизъюнкции и конъюнкции?

Вариант 3.

1. Верно ли, что

А ٨ В ٧B ٨ С ٧D٨E = (А ٧B) ٨ (B ٧C) ٨(D ٧E),

где А, В, С, D, E – простые высказывания?

2. Функция f(x₁, x₂, x₃) принимает единичные значения на наборах №№ 0, 1, 3, 6, 7.

3. Является ли полной система булевых функций, состоящая из импликации и отрицания?

Вариант 4.

1. Верно ли, что

А ٨ В ٧ С ٨ D٧E = (А ٧B) ٨ (C ٧D) ٨E,

где А, В, С, D, E – простые высказывания?

2. Функция f(x₁, x₂, x₃) принимает единичные значения на наборах №№ 0, 2, 3, 6, 7.

3. Является ли полной система булевых функций, состоящая из конъюнкции, константы 1 и сложения по модулю два?

Вариант 5.

1. Верно ли, что

(А ٨ В ٧ С ٨D٧E ٧F) = (А ٧B) ٨ (C ٧D) ٧E ٧F,

где А, В, С, D, E, F – простые высказывания?

2. Функция f(x₁, x₂, x₃) принимает единичные значения на наборах №№ 1, 2, 3, 5, 6.

3. Является ли полной система булевых функций, состоящая из конъюнкции, константы 0 и эквивалентности?

Вариант 6.

1. Верно ли, что

А ٨ В ٨ С ٨ (D٧E ) = А ٧B ٧C ٧D ٨ E,

где А, В, С, D, E – простые высказывания?

2. Функция f(x₁, x₂, x₃) принимает единичные значения на наборах №№ 1, 2, 3, 5, 7.

3. Является ли полной система булевых функций, состоящая из импликации и эквивалентности?

Вариант 7.

1. Верно ли, что

(А ٧В ٧С) ٨ ( D٧E) ٨F =А ٨B ٨C ٧D ٨ E ٧F,

где А, В, С, D, E, F – простые высказывания?

2. Функция f(x₁, x₂, x₃) принимает единичные значения на наборах №№ 0, 2, 5, 6, 7.

3. Является ли полной система булевых функций, состоящая из конъюнкции и импликации?

Вариант 8.

1. Верно ли, что

А ٨ В ٨ С ٨ ( D٧E) ٨F = А ٧B ٧C ٧ (D ٨ E ) ٧F,

где А, В, С, D, E, F – простые высказывания?

2. Функция f(x₁, x₂, x₃) принимает единичные значения на наборах №№ 2, 4, 5, 6, 7.

3. Является ли полной система булевых функций, состоящая из конъюнкции, эквивалентности и сложения по модулю два?

Вариант 9.

1. Верно ли, что

А ٨ (В ٧С) ٨ ( D٧E) ٨F = А ٧B ٨C ٧D ٨ E ٧F,

где А, В, С, D, E, F – простые высказывания?

2. Функция f(x₁, x₂, x₃) принимает единичные значения на наборах №№ 2, 3, 5, 6, 7.

3. Является ли полной система булевых функций, состоящая из дизъюнкции и импликации?

Вариант 10.

1. Верно ли, что

(А ٧ В) ٨ (С ٧D)٨E ٨F) = А ٨B ٧C ٨D ٧E ٧F,

где А, В, С, D, E, F – простые высказывания?

2. Функция f(x₁, x₂, x₃) принимает единичные значения на наборах №№ 0, 3, 4, 6, 7.

3. Является ли полной система булевых функций, состоящая из сложения по модулю два, константы 1 и эквивалентности?

Контрольная работа № 4

Эта контрольная работа включает в себя задания по теории алгоритмов и перечислительной комбинаторике. В работе требуется выполнить четыре задания.

1. Приведите три самостоятельных примера применения оператора подстановки к простейшим числовым функциям. Например,

s(С₂³(I₁³(3, 2, 4), I₂³(5, 8, 1), I₃³( 5, 6, 7))) = 3.

2. Приведите два самостоятельных примера применения оператора примитивной рекурсии (аналогично примерам из конспекта лекций).

3. Напишите программу для машины Тьюринга в соответствии с Вашим вариантом.

4. Решите комбинаторную задачу в соответствии с Вашим вариантом.