Критерій Поста — одна з центральних теорем математичної логіки , описує необхідні та достатні умови функціональної повноти множини булевих функцій . Був сформульований американським математиком Емілем Постом в 1921 . Отже, для того щоб наша система була повною , необхідно і достатньо, щоб вона містила хоча б одну нелінійну функцію , хоча б одну несамодвоїсту , хоча б одну немонотонну , хоча б одну неафінну, хоча б одну функцію, яка не зберігатиме нуль та хоча б одну функцію, що не зберігає одиницю .
Постановка задачі
ред.
Булева n -арна функція, це функція
B
n
→
B
{\displaystyle ~B^{n}\to B}
B
=
{
0
,
1
}
{\displaystyle ~B=\{0,1\}}
булева множина .
Кількість n -арних булевих функцій дорівнює
2
2
n
{\displaystyle 2^{2^{n}}}
Довільна булева функція може бути представлена у вигляді:
Тому природним є питання: чи є функціонально повною деяка множина функцій?
Замкнені класи
ред.
Критерій
ред.
Множина булевих функцій є функціонально повною тоді і тільки тоді , коли вона не міститься повністю ні в одному з передповних класів.
Доведення
ред.
Необхідність умови випливає з функціональної замкненості та неповноти классів монотонних, лінійних, самодвоїстих функцій та функції, які зберігають 0 та 1. Для доведення достатності необхідно показати, що за допомогою функцій, які не належать деяким з класів
T
0
{\displaystyle T_{0}}
T
1
,
M
,
L
,
S
{\displaystyle T_{1},M,L,S}
повну систему функцій . Прикладом повної системи є заперечення та кон'юнкція . Дійсно довільна булева функція може бути представлена у вигляді ДДНФ , тобто у вигляді кон'юнкції, диз'юнкції та заперечення. Відповідна система є функціонально повною. Можна виключити з неї диз'юнкцію так що вона буде представлена як суперпозиція
∧
{\displaystyle \land }
¬
{\displaystyle \neg }
x
∧
y
=
(
x
¯
∧
y
¯
)
¯
{\displaystyle x\land y={\overline {({\bar {x}}\land {\bar {y}})}}}
ϕ
(
0
)
=
f
0
(
x
,
.
.
.
x
)
{\displaystyle \phi (0)=f_{0}(x,...x)}
f
0
{\displaystyle f_{0}}
ϕ
(
0
)
=
f
0
(
0
,
.
.
.0
)
≠
0
{\displaystyle \phi (0)=f_{0}(0,...0)\neq 0}
ϕ
(
0
)
=
1
{\displaystyle \phi (0)=1}
1.
ϕ
(
1
)
=
1
{\displaystyle \phi (1)=1}
2.
ϕ
(
1
)
=
0
{\displaystyle \phi (1)=0}
ϕ
{\displaystyle \phi }
f
^
{\displaystyle {\hat {f}}}
∃
α
1
,
…
,
α
n
:
f
^
(
α
1
,
…
,
α
n
)
≠
¬
f
^
(
¬
α
1
,
…
,
¬
α
n
)
{\displaystyle \exists \alpha _{1},\dots ,\alpha _{n}:{\hat {f}}(\alpha _{1},\dots ,\alpha _{n})\neq \neg {\hat {f}}(\neg \alpha _{1},\dots ,\neg \alpha _{n})}
Відповідно,
f
^
(
α
1
,
…
,
α
n
)
=
f
^
(
¬
α
1
,
…
,
¬
α
n
)
{\displaystyle {\hat {f}}(\alpha _{1},\dots ,\alpha _{n})={\hat {f}}(\neg \alpha _{1},\dots ,\neg \alpha _{n})}
ψ
(
x
)
=
f
^
(
x
α
1
,
…
,
x
α
n
)
{\displaystyle \psi (x)={\hat {f}}(x^{\alpha _{1}},\dots ,x^{\alpha _{n}})}
ψ
(
0
)
=
f
^
(
0
α
1
,
…
,
0
α
n
)
=
f
^
(
α
1
,
…
,
α
n
)
=
f
^
(
1
α
1
,
…
,
1
α
n
)
=
ψ
(
1
)
{\displaystyle \psi (0)={\hat {f}}(0^{\alpha _{1}},\dots ,0^{\alpha _{n}})={\hat {f}}(\alpha ^{1},\dots ,\alpha ^{n})={\hat {f}}(1^{\alpha _{1}},\dots ,1^{\alpha _{n}})=\psi (1)}
Таким чином,
ψ
(
0
)
=
ψ
(
1
)
{\displaystyle \psi (0)=\psi (1)}
ψ
=
1
{\displaystyle \psi =1}
ψ
=
0
{\displaystyle \psi =0}
ψ
=
1
{\displaystyle \psi =1}
ψ
{\displaystyle \psi }
ϕ
(
ψ
(
x
)
)
=
1
{\displaystyle \phi (\psi (x))=1}
f
0
{\displaystyle f_{0}}
f
1
{\displaystyle f_{1}}
За допомогою немонотонної функції підстановкою в неї констант можна побудувати заперечення. Нехай
f
M
{\displaystyle f_{M}}
α
{\displaystyle \alpha }
β
{\displaystyle \beta }
α
{\displaystyle \alpha }
β
{\displaystyle \beta }
α
≤
β
{\displaystyle \alpha \leq \beta }
f
M
(
α
)
=
1
{\displaystyle f_{M}(\alpha )=1}
f
M
(
β
)
=
1
{\displaystyle f_{M}(\beta )=1}
α
≤
β
{\displaystyle \alpha \leq \beta }
α
{\displaystyle \alpha }
k
{\displaystyle k}
β
{\displaystyle \beta }
α
{\displaystyle \alpha }
α
1
{\displaystyle \alpha _{1}}
α
≤
α
1
{\displaystyle \alpha \leq \alpha _{1}}
α
{\displaystyle \alpha }
k
{\displaystyle k}
α
≤
α
1
≤
⋯
≤
α
k
−
1
≤
β
{\displaystyle \alpha \leq \alpha _{1}\leq \dots \leq \alpha _{k-1}\leq \beta }
α
i
,
α
i
+
1
{\displaystyle \alpha ^{i},\alpha ^{i+1}}
f
M
(
α
i
)
=
1
{\displaystyle f_{M}(\alpha ^{i})=1}
f
M
(
α
i
+
1
)
=
1
{\displaystyle f_{M}(\alpha ^{i+1})=1}
j
{\displaystyle j}
x
j
{\displaystyle x_{j}}
f
M
{\displaystyle f_{M}}
f
M
(
α
1
i
,
…
,
α
j
−
1
i
,
x
j
,
α
j
+
1
i
,
α
n
i
=
ω
(
x
j
)
{\displaystyle f_{M}(\alpha _{1}^{i},\dots ,\alpha _{j-1}^{i},x_{j},\alpha _{j+1}^{i},\alpha _{n}^{i}=\omega (x_{j})}
x
j
{\displaystyle x_{j}}
ω
(
0
)
=
ω
(
α
j
i
)
=
f
(
α
i
)
=
1
{\displaystyle \omega (0)=\omega (\alpha _{j}^{i})=f(\alpha ^{i})=1}
ω
(
1
)
=
ω
(
α
j
i
+
1
)
=
f
(
α
i
+
1
)
=
0
{\displaystyle \omega (1)=\omega (\alpha _{j}^{i+1})=f(\alpha ^{i+1})=0}
ω
(
x
j
)
=
¬
x
j
{\displaystyle \omega (x_{j})=\neg x_{j}}
Побудуємо кон’юнкцію за допомогою підстановки у нелінійну функцію констант та використання заперечення. Нехай
f
L
{\displaystyle f_{L}}
поліномі Жегалкіна існує нелінійний доданок, який містить кон'юнкцію принаймні двох змінних. Нехай, для визначеності, це
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
f
L
=
(
x
1
∧
x
2
∧
f
a
(
x
3
,
…
,
x
n
)
)
⊕
(
x
1
∧
f
b
(
x
3
,
…
,
x
n
)
)
⊕
(
x
2
∧
f
c
(
x
3
,
…
,
x
n
)
)
⊕
f
d
(
x
3
,
…
,
x
n
)
{\displaystyle f_{L}=(x_{1}\land x_{2}\land f_{a}(x_{3},\dots ,x_{n}))\oplus (x_{1}\land f_{b}(x_{3},\dots ,x_{n}))\oplus (x_{2}\land f_{c}(x_{3},\dots ,x_{n}))\oplus f_{d}(x_{3},\dots ,x_{n})}
до того ж
f
a
(
x
3
,
…
,
x
n
)
{\displaystyle f_{a}(x_{3},\dots ,x_{n})}
∃
α
3
,
…
,
α
n
:
f
a
(
α
3
,
…
,
α
n
)
=
1
{\displaystyle \exists \alpha _{3},\dots ,\alpha _{n}:f_{a}(\alpha _{3},\dots ,\alpha _{n})=1}
Нехай
b
=
f
b
(
α
3
,
…
,
α
n
)
,
c
=
f
c
(
α
3
,
…
,
α
n
)
,
d
=
f
d
(
α
3
,
…
,
α
n
)
{\displaystyle b=f_{b}(\alpha _{3},\dots ,\alpha _{n}),c=f_{c}(\alpha _{3},\dots ,\alpha _{n}),d=f_{d}(\alpha _{3},\dots ,\alpha _{n})}
ϕ
(
x
1
,
x
2
)
=
f
L
(
x
1
,
x
2
,
α
3
,
…
,
α
n
)
=
(
x
1
∧
x
2
)
⊕
(
x
1
∧
b
)
⊕
(
x
2
∧
c
)
⊕
d
{\displaystyle \phi (x_{1},x_{2})=f_{L}(x_{1},x_{2},\alpha _{3},\dots ,\alpha _{n})=(x_{1}\land x_{2})\oplus (x_{1}\land b)\oplus (x_{2}\land c)\oplus d}
Тоді нехай
ψ
(
x
1
,
x
2
)
=
ϕ
(
x
1
∧
c
,
x
2
∧
b
)
⊕
(
b
∧
c
)
⊕
d
{\displaystyle \psi (x_{1},x_{2})=\phi (x_{1}\land c,x_{2}\land b)\oplus (b\land c)\oplus d}
Тоді
ψ
(
x
1
,
x
2
)
=
(
x
1
⊕
c
)
∧
(
x
2
⊕
b
)
⊕
b
∧
(
x
1
⊕
c
)
⊕
c
∧
(
x
2
⊕
b
)
⊕
d
⊕
(
b
∧
c
)
⊕
d
=
{\displaystyle \psi (x_{1},x_{2})=(x_{1}\oplus c)\land (x_{2}\oplus b)\oplus b\land (x_{1}\oplus c)\oplus c\land (x_{2}\oplus b)\oplus d\oplus (b\land c)\oplus d=}
=
(
x
1
∧
x
2
)
⊕
(
x
2
∧
c
)
⊕
(
x
1
∧
b
)
⊕
(
c
∧
b
)
⊕
(
x
1
∧
b
)
⊕
(
x
2
∧
c
)
⊕
(
c
∧
b
)
⊕
(
c
∧
b
)
⊕
(
c
∧
b
)
⊕
d
⊕
d
=
x
1
∧
x
2
{\displaystyle =(x_{1}\land x_{2})\oplus (x_{2}\land c)\oplus (x_{1}\land b)\oplus (c\land b)\oplus (x_{1}\land b)\oplus (x_{2}\land c)\oplus (c\land b)\oplus (c\land b)\oplus (c\land b)\oplus d\oplus d=x_{1}\land x_{2}}
(функцію
x
⊕
α
{\displaystyle x\oplus \alpha }
x
⊕
1
=
x
¯
,
x
⊕
0
=
x
{\displaystyle x\oplus 1={\bar {x}},x\oplus 0=x}
Приклади
ред.
Приклад 1
ред.
Перевірити повноту системи
x
→
y
,
x
¯
{\displaystyle {x\to y,{\bar {x}}}}
Розглянемо формулу
F
=
x
→
y
{\displaystyle F=x\to y}
х
y
F
0
0
1
0
1
1
1
0
0
1
1
1
Розглянемо формулу
V
=
x
¯
{\displaystyle V={\bar {x}}}
Побудуємо таблицю Поста( якщо функція входить у функціонально замкнений клас, то в таблиці Поста у відповідній комірці ставиться знак "+", інакше - "-"
Т0
Т1
S
M
L
F
-
+
-
-
-
V
-
-
-
-
+
Система є повною.
Приклад 2
ред.
Перевірити на повноту систему:
(
x
∧
y
¯
)
→
z
,
(
x
⊕
y
)
↔
(
x
∧
z
¯
)
,
x
¯
∧
y
{\displaystyle (x\land {\bar {y}})\to z,(x\oplus y)\leftrightarrow (x\land {\bar {z}}),{\bar {x}}\land y}
Розглянемо
F
=
(
x
∧
y
¯
)
→
z
{\displaystyle F=(x\land {\bar {y}})\to z}
x
y
z
y
¯
{\displaystyle {\bar {y}}}
x
∧
y
¯
{\displaystyle x\land {\bar {y}}}
F
0
0
0
1
0
1
0
0
1
1
0
1
0
1
0
0
0
1
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
1
1
1
1
1
0
0
0
1
1
1
1
0
0
1
Перевірка на лінійність:
x
¯
y
¯
z
¯
⊕
x
¯
y
¯
z
⊕
x
¯
y
z
¯
⊕
x
¯
y
z
⊕
x
y
¯
z
⊕
x
y
z
¯
⊕
x
y
z
=
{\displaystyle {\bar {x}}{\bar {y}}{\bar {z}}\oplus {\bar {x}}{\bar {y}}z\oplus {\bar {x}}y{\bar {z}}\oplus {\bar {x}}yz\oplus x{\bar {y}}z\oplus xy{\bar {z}}\oplus xyz=}
=
(
x
⊕
1
)
(
y
⊕
1
)
(
z
⊕
1
)
⊕
(
x
⊕
1
)
(
y
⊕
1
)
z
⊕
(
x
⊕
1
)
y
(
z
⊕
1
)
⊕
(
x
⊕
1
)
y
z
⊕
x
(
y
⊕
1
)
z
⊕
x
y
(
z
⊕
1
)
⊕
x
y
z
=
{\displaystyle =(x\oplus 1)(y\oplus 1)(z\oplus 1)\oplus (x\oplus 1)(y\oplus 1)z\oplus (x\oplus 1)y(z\oplus 1)\oplus (x\oplus 1)yz\oplus x(y\oplus 1)z\oplus xy(z\oplus 1)\oplus xyz=}
=
x
y
z
⊕
x
y
⊕
x
z
⊕
y
z
⊕
x
⊕
y
⊕
z
⊕
1
⊕
x
y
z
⊕
x
z
⊕
y
z
⊕
z
⊕
x
y
z
⊕
x
y
⊕
y
z
⊕
y
⊕
x
y
z
⊕
y
z
⊕
x
y
z
⊕
x
z
⊕
x
y
z
⊕
x
y
⊕
x
y
z
=
{\displaystyle =xyz\oplus xy\oplus xz\oplus yz\oplus x\oplus y\oplus z\oplus 1\oplus xyz\oplus xz\oplus yz\oplus z\oplus xyz\oplus xy\oplus yz\oplus y\oplus xyz\oplus yz\oplus xyz\oplus xz\oplus xyz\oplus xy\oplus xyz=}
=
x
y
z
⊕
x
y
⊕
y
z
⊕
x
z
⊕
x
⊕
1
{\displaystyle =xyz\oplus xy\oplus yz\oplus xz\oplus x\oplus 1}
B
=
(
x
⊕
y
)
↔
(
x
∧
z
¯
)
{\displaystyle B=(x\oplus y)\leftrightarrow (x\land {\bar {z}})}
x
y
z
z
¯
{\displaystyle {\bar {z}}}
x
⊕
y
{\displaystyle x\oplus y}
x
∧
z
¯
{\displaystyle x\land {\bar {z}}}
B
0
0
0
1
0
0
1
0
0
1
0
0
0
1
0
1
0
1
1
0
0
0
1
1
0
1
0
0
1
0
0
1
1
1
1
1
0
1
0
1
0
0
1
1
0
1
0
1
0
1
1
1
0
0
0
1
Перевірка на лінійність:
x
¯
y
¯
z
¯
⊕
x
¯
y
¯
z
⊕
x
y
¯
z
¯
⊕
x
y
z
=
x
y
z
⊕
x
y
⊕
y
z
⊕
x
z
⊕
x
⊕
y
⊕
z
⊕
1
⊕
x
y
z
⊕
x
z
⊕
y
z
⊕
z
⊕
x
y
z
⊕
x
y
⊕
x
z
⊕
x
⊕
x
y
z
=
x
z
⊕
y
⊕
1
{\displaystyle {\bar {x}}{\bar {y}}{\bar {z}}\oplus {\bar {x}}{\bar {y}}z\oplus x{\bar {y}}{\bar {z}}\oplus xyz=xyz\oplus xy\oplus yz\oplus xz\oplus x\oplus y\oplus z\oplus 1\oplus xyz\oplus xz\oplus yz\oplus z\oplus xyz\oplus xy\oplus xz\oplus x\oplus xyz=xz\oplus y\oplus 1}
C
=
x
¯
∧
y
{\displaystyle C={\bar {x}}\land y}
x
y
x
¯
{\displaystyle {\bar {x}}}
C
0
0
1
0
0
1
1
1
1
0
0
0
1
1
0
0
Перевірка на лінійність:
x
¯
y
=
x
y
⊕
y
{\displaystyle {\bar {x}}y=xy\oplus y}
Т0
Т1
M
S
L
F
-
+
-
-
-
B
-
+
-
-
-
C
+
-
-
-
-
Отже система є повною.
Приклад 3
ред.
Перевірити на повноту систему
(
x
¯
∨
y
)
→
z
,
(
x
↔
y
)
⊕
(
x
∨
z
)
,
x
¯
∨
y
¯
{\displaystyle {({\bar {x}}\lor y)\to z,(x\leftrightarrow y)\oplus (x\lor z),{\bar {x}}\lor {\bar {y}}}}
Розглянемо
F
=
(
x
¯
∨
y
)
→
z
{\displaystyle F=({\bar {x}}\lor y)\to z}
x
y
z
x
¯
{\displaystyle {\bar {x}}}
x
¯
∨
y
{\displaystyle {\bar {x}}\lor y}
F
0
0
0
1
1
0
0
0
1
1
1
1
0
1
0
1
1
0
0
1
1
1
1
1
1
0
0
0
0
1
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
Перевіримо на лінійність:
x
¯
y
¯
z
⊕
x
¯
y
z
⊕
x
y
¯
z
¯
⊕
x
y
¯
z
⊕
x
y
z
=
{\displaystyle {\bar {x}}{\bar {y}}z\oplus {\bar {x}}yz\oplus x{\bar {y}}{\bar {z}}\oplus x{\bar {y}}z\oplus xyz=}
=
(
x
⊕
1
)
(
y
⊕
1
)
z
⊕
(
x
⊕
1
)
y
z
⊕
x
(
y
⊕
1
)
(
z
⊕
1
)
⊕
x
(
y
⊕
1
)
z
⊕
x
y
z
=
{\displaystyle =(x\oplus 1)(y\oplus 1)z\oplus (x\oplus 1)yz\oplus x(y\oplus 1)(z\oplus 1)\oplus x(y\oplus 1)z\oplus xyz=}
=
x
y
z
⊕
x
z
⊕
y
z
⊕
z
⊕
x
y
z
⊕
y
z
⊕
x
y
z
⊕
x
y
⊕
x
z
⊕
x
⊕
x
y
z
⊕
x
z
⊕
x
y
z
=
{\displaystyle =xyz\oplus xz\oplus yz\oplus z\oplus xyz\oplus yz\oplus xyz\oplus xy\oplus xz\oplus x\oplus xyz\oplus xz\oplus xyz=}
=
x
⊕
z
⊕
x
y
⊕
x
z
⊕
x
y
z
{\displaystyle =x\oplus z\oplus xy\oplus xz\oplus xyz}
P
=
(
x
↔
y
)
⊕
(
x
∨
z
)
{\displaystyle P=(x\leftrightarrow y)\oplus (x\lor z)}
x
y
z
x
↔
y
{\displaystyle x\leftrightarrow y}
x
∨
z
{\displaystyle x\lor z}
P
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
0
0
0
0
1
1
0
1
1
1
0
0
0
1
1
1
0
1
0
1
1
1
1
0
1
1
0
1
1
1
1
1
0
Перевіримо на лінійність:
x
¯
y
¯
z
¯
⊕
x
¯
y
z
⊕
x
y
¯
z
¯
⊕
x
y
¯
z
=
{\displaystyle {\bar {x}}{\bar {y}}{\bar {z}}\oplus {\bar {x}}yz\oplus x{\bar {y}}{\bar {z}}\oplus x{\bar {y}}z=}
=
(
x
⊕
1
)
(
y
⊕
1
)
(
z
⊕
1
)
⊕
(
x
⊕
1
)
y
z
⊕
x
(
y
⊕
1
)
(
z
⊕
1
)
⊕
x
(
y
⊕
1
)
z
=
{\displaystyle =(x\oplus 1)(y\oplus 1)(z\oplus 1)\oplus (x\oplus 1)yz\oplus x(y\oplus 1)(z\oplus 1)\oplus x(y\oplus 1)z=}
=
x
y
z
⊕
x
y
⊕
y
z
⊕
x
z
⊕
x
⊕
y
⊕
z
⊕
1
⊕
x
y
z
⊕
y
z
⊕
x
y
z
⊕
x
y
⊕
x
z
⊕
x
⊕
x
y
z
⊕
x
z
=
x
z
⊕
y
⊕
z
⊕
1
{\displaystyle =xyz\oplus xy\oplus yz\oplus xz\oplus x\oplus y\oplus z\oplus 1\oplus xyz\oplus yz\oplus xyz\oplus xy\oplus xz\oplus x\oplus xyz\oplus xz=xz\oplus y\oplus z\oplus 1}
B
=
x
¯
∨
y
¯
{\displaystyle B={\bar {x}}\lor {\bar {y}}}
x
y
x
¯
{\displaystyle {\bar {x}}}
y
¯
{\displaystyle {\bar {y}}}
B
0
0
1
1
1
0
1
0
1
1
1
0
0
1
1
1
1
0
0
0
Перевіримо на лінійність:
x
¯
y
¯
⊕
x
¯
y
⊕
x
y
¯
=
(
x
⊕
1
)
(
y
⊕
1
)
⊕
(
x
⊕
1
)
y
⊕
x
(
y
⊕
1
)
=
x
y
⊕
x
⊕
y
⊕
1
⊕
x
y
⊕
x
⊕
x
y
⊕
y
=
x
y
⊕
1
{\displaystyle {\bar {x}}{\bar {y}}\oplus {\bar {x}}y\oplus x{\bar {y}}=(x\oplus 1)(y\oplus 1)\oplus (x\oplus 1)y\oplus x(y\oplus 1)=xy\oplus x\oplus y\oplus 1\oplus xy\oplus x\oplus xy\oplus y=xy\oplus 1}
T0
T1
M
S
L
F
+
+
-
-
-
P
-
-
-
-
-
B
-
-
-
-
-
Отже, система - повна.
