9. Булевы функции.

Ф-ция f зависящая от n-переменных x₁, x₂…x₃ называется булевой или переключательной если функция f и любой из её аргументов принимают значение только из множества {0;1}.

10. Построение таблицы истинности для булевых функций.

Ну вы таблицу-то сможете построить, правда ведь?

11. Что такое днф и кнф.

Дизъюнкция конечного множества элементарных конъюнкций называется дизъюнктивной нормальной формой(ДНФ).

ДНФ – формула, равносильная данной формуле и являющейся дизъюнкцией элементарных конъюнкций. Пример: (x₁Ʌx₂)V(x₁Ʌx₃Ʌx₂)x₂

ДНФ содержащая только полные элементарные конъюнкции называется совершенной ДНФ(или СДНФ)

Конъюнкция конечного множества элементарных дизъюнкций называется конъюнктивной нормальной формой(или сокращенно КНФ). КНФ – формула, равносильная данной формуле и являющейся конъюнкцией элементарных дизъюнкций.

Пример: Тоже самое что в ДНФ, только галочки поменять местами наоборот.

12. Правила преобразования формул СДНФ и СКНФ.

Совершенная дизъюнктивная нормальная форма формулы (СДНФ) это равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций, обладающая свойствами

1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x1,x2,...xn)

2. Все логические слагаемые формулы различны

3. Ни одно логическое слагаемое не содержит переменную и её отрицание

4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды. СДНФ можно получить или с помощью таблиц истинности или с помощью равносильных преобразований. Для каждой функции СДНФ и СКНФ определены единственным образом с точностью до перестановки.

13. Как булевы функции связаны с формулами алгебры высказываний.

ОТВЕТ НЕ ТОЧНЫЙ!

Булевы функции, как и формулы алгебры высказываний принимают значения из множества {0;1}. А так же операции в булевых функциях означают тоже самое что и формулы алгебры высказываний. --- Это короче если совсем ответить нечего. Главное с умным видом говорите.

14. Определение многочлена Жегалкина.

Многочленом Жегалкина называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой степени(так написано в конспекте).

Многочленами Жегалкина называются формулы над множеством функций F_J={ 0, 1, *, +} (здесь * - это другое обозначение конъюнкции). Таким образом, каждый многочлен Жегалкина (возможно, после раскрытия скобок и "приведения" подобных членов) представляет сумму (по модулю 2) положительных (монотонных) элементарных конъюнкций (т.е. элементарных конъюнкций без отрицаний). – а так написано на интуите.

15. Теорема Жегалкина

Каждая булева функция единственным образом представляется в виде полинома Жегалкина.

1. Многочлен Жегалкина константы равен самой константе.

2. Многочлен Жегалкина булевой функции одной переменной имеет вид: f_(x)=a₀a₁x

3. Многочлен Жегалкина булевой функции двух переменных: f_(x1,x2)=a₀a₁x₁a₂x₂a₁₂(x₁Ʌx₂)

4. Многочлен Жегалкина булевой функции трёх переменных: f_(x1,x2,x3)= a₀a₁x₁a₂x₂a₃x₃a₁₂(x₁Ʌx₂)a₁₃(x₁Ʌ x₃)a₂₃(x₂Ʌ x₃)a₁₂₃(x₁Ʌ x₂Ʌ x₃)

Коэфф. a₁…_I и a₀ принимают значения 0 или 1. Число слагаемых в формуле равно 2ⁿ, где n- число слагаемых.

- сумма Жегалкина или сумма по мод.2