Головна » Статті » Математика програмістів » Алгебра Жегалкіна
Кілька слів про використання алгебри Жегалкіна
Сильно багато сказати про використання алгебри Жегалкіна, мабуть, не вдасться, тому ми сконцентруємо свою увагу лише на ключових нюансах, в яких вона буває досить корисною, а саме:
  1. у перевірці тотожностей;
  2. у булевих функціях.
Отож, стостовно перевірки тотожностей варто відмітити той факт, що алгебра Жегалкіна інколи є надзвичайно зручним інструментом. Все діло в переведенні. Так як у алгебрі Жегалкіна операцій менше, ніж у алгебрі Буля (навіть, якщо мову вести про базові), то це, в принципі, може спростити дану в умові формулу і, відповідно, полегшити аналіз. Але буває інколи так, що може взагалі не бути, що аналізувати. Візьмеш, буває, якусь тавтологію в алгебрі Буля (чисто, щоб її перевірити), переведеш обидві її сторони в алгебру Жегалкіна, а тут на тобі: рівності типу х=х, 1=1 чи 0=0. Такого роду результат можна отримати, для прикладу, з законами де Моргана чи з тавтологією стосовно логічної суми (можете перевірити, якщо не вірите).
З булевими функціями ситуація подібна. Як Ви, мабуть, знаєте, у алгебрі Буля загалом є 6 операцій, і всі вони зводяться до 3-х. Але це життя сильно не полегшує, так як формула функції може бути записана таким чином, що будь-яка спроба її спростити може тільки погіршити ситуацію. В такому випадку знову на допомогу приходить алгебра Жегалкіна. У ній є така річ як поліном Жегалкіна. В чому його суть? Як Ви, мабуть, знаєте, у алгебрі Жегалкіна є лише дві операції: логічне множення та додавання за модулем 2. Поліном Жегалкіна являє собою суму логічних добутків змінних на певні константи. Ну і що? - можливо, хтось запитає. А діло в тому, що будь-яку булеву функцію (а вони зазвичай записуються в алгебрі Буля) можна записати таким поліномом Жегалкіна (це свого роду аналог розписування функції в ряд) і "полегшити собі життя" при її аналізі.
Отож, давайте підведемо підсумок. Алгебра Жегалкіна може використовуватися для спрощення аналізу булевої функції та доведенні тавтологій. Звідси випливає, що вона здадна інколи полегшити розв'язання задачі.
Надіюсь, дана інформація була для Вас корисною, і дала причину вчити алгебру Жегалкіна.
Категорія: Алгебра Жегалкіна | Додав: Lord_Adwond (28-02-2018)
Переглядів: 7094 | Теги: алгебра Жегалкіна, Алгебра, використання | Рейтинг: 0.0/0
Всього коментарів: 0
Увійдіть:
avatar