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

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

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

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

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

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

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

Дивись також

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

Посилання

1. Іванов Є.О., Шевченко В.П. Дискретна математика [ 3 квітня 2016 у Wayback Machine.]