Клас інваріантний функцій алгебри логіки

Клас інваріа́нтний фу́нкцій а́лгебри ло́гіки — множина функцій алгебри логіки така, що:

1. якщо функція$f(x_1,\dots ,x_n)\in Q$ то до класу $Q$ належать і всі функції, що виходять з $f$ шляхом перейменування (без ототожнення) змінних;
2. якщо функція $f(x_1,\dots ,x_n)\in Q$ до класу $Q$ належать і всі функції, що виходять з $f$ шляхом будь-якої підстановки констант на місце (не обов'язково всіх) змінних;
3. якщо функція $f(x_1,\dots ,x_n)\in Q$ то до класу $Q$ належать і всі функції, що виходять з $f$ шляхом видалення або введення фіктивних змінних (змінна $x_i$ називається фіктивною, якщо $f(x_1,\dots ,x_{i-1},0,x_{i+1},\dots ,x_n)\equiv f(x_1,\dots ,x_{i-1},1,x_{i+1},\dots ,x_n)$

Множина всіх класів інваріантних функцій алгебри логіки має потужність континууму.

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

М. І. Кратко

Література

• Шаблон:ЕК