Алгебра Жегалкіна

Алгебра Жегалкіна - алгебра булевих функцій утворених за допомогою:

• булевої константи 1
• булевих змінних
• булевих функцій:
  • $\oplus$ - сума за модулем 2
  • $*$ - кон'юнкція

Тотожності алгебри Жегалкіна

• $x\oplus y=y\oplus x$
• $x*y=y*x$
• $x\oplus (y\oplus z)=(x\oplus y)\oplus z$
• $x*(y*z)=(x*y)*z$
• $x*(y\oplus z)=x*y\oplus x*z)$
• $x*1=x$
• $x*0=0$
• $x*x=x$
• $x\oplus 0=x$
• $x\oplus x=0$

Вираження логічних операцій в алгебрі Жегалкіна

• $x\oplus 1=\overline{x}$
• $x\oplus 0=x$
• $x\oplus y=\overline{x}\cdot y\vee x\cdot \overline{y}$
• $x\vee y=x\oplus y\oplus x\cdot y$
• $x\equiv y=1\oplus x\oplus y$ (еквівалентність)
• $x\to y=1\oplus x\oplus x\cdot y$ (імплікація)
• $x\downarrow y=1\oplus x\oplus y\oplus x\cdot y$ (Стрілка Пірса)
• $x|y=1\oplus x\cdot y$ (Штрих Шефера)

Дивись також

• Поліном Жегалкіна

Посилання

1. Іванов Є.О., Шевченко В.П. Дискретна математика Шаблон:Webarchive