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

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

булевої константи 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={\bar {x}}$
$x\oplus 0=x$
$x\oplus y={\bar {x}}\cdot y\vee x\cdot {\bar {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$ (Штрих Шефера)

Дивись також

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

Посилання

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.