подвійні функції

1. f = x Ú y;

Визначення. Функція, що збігається зі своєю двоїстої, називається самодвоїстих.

Затвердження. Якщо функція f (x1. X2. ..., xn) самодвоїстих, то функція теж самодвоїстих.

Затвердження. Щоб функція була самодвоїстих необхідно і досить, щоб на будь-яких двох протилежних наборах вона приймала різні значення.

Протилежними називаються ті набори, які в сумі дають двійкового коду числа (2 n -1).

З'ясувати чи є функції самодвоїстих:

1. Будуємо таблицю істинності для даної функції (табл. 55):

Перерахуємо пари протилежних наборів: (0, 7), (1, 6), (2, 5), (3, 4). Легко переконатися по таблиці, що на всяких двох протилежних наборах функція приймає різні значення. Отже, функція є самодвоїстих.

Теорема. КлассS = самодвоїстих функцій замкнутий щодо суперпозиций.

2.2.3.2. лінійні функції

Визначення. Арифметичні функції в алгебрі логіки це додавання по модулю два і множення (кон'юнкція).

Визначення. Многочленом Жегалкина називається многочлен, який є сумою константи 0 або 1 і різних одночленним, в які всі змінні входять не вище, ніж в першого ступеня:, причому на кожному наборі все аij (j = 1, ..., k) різні, aj Î .

Теорема. Будь-яку булеву функцію можна представити єдиним полиномом Жегалкина.

Многочлен Жегалкина можна отримати різними способами. Зупинимося на розгляді побудови многочлена Жегалкина за допомогою трикутника Паскаля. Розглянемо алгоритм на прикладі.

Побудувати многочлен Жегалкина для функції f = 10011110.

Алгоритм побудови многочлена Жегалкина:

Крок 1. Будуємо таблицю (табл. 57). Перший стовпець містить можливі складові полінома Жегалкина. Нульового набору завжди відповідає доданок 1. Іншим наборам відповідає доданок, що представляє собою кон'юнкцію змінних, які на даному наборі приймають значення 1. Наступні n стовпців - всілякі набори з 0 і 1, відповідні змінним. Далі стовпець значень функції f. Функція g є допоміжною, тому спочатку цей стовпець не заповнено.

Складові полінома Жегалкина