Tam tikrai loginei funkcijai f dualioji funkcija yra tokia funkcija f* , kad kiekvienam parametrų rinkiniui galioja lygybė
f
∗
(
x
1
,
x
2
,
.
.
.
,
x
n
)
=
¬
f
(
¬
x
1
,
¬
x
2
,
.
.
.
,
¬
x
n
)
{\displaystyle f^{*}(x_{1},x_{2},...,x_{n})=\neg f(\neg x_{1},\neg x_{2},...,\neg x_{n})}
Pavyzdžiui, Būlio algebros funkcijai IR dualioji funkcija yra ARBA , nes
x
∧
y
=
¬
(
¬
x
∨
¬
y
)
{\displaystyle x\land y=\neg (\neg x\lor \neg y)}
[ 1]
Formuluotė: Jei
f
(
x
1
,
x
2
,
.
.
.
,
x
n
)
=
g
(
x
1
,
x
2
,
.
.
.
,
x
n
)
{\displaystyle f(x_{1},x_{2},...,x_{n})=g(x_{1},x_{2},...,x_{n})}
f
∗
(
x
1
,
x
2
,
.
.
.
,
x
n
)
=
g
∗
(
x
1
,
.
.
.
,
x
n
)
{\displaystyle f^{*}(x_{1},x_{2},...,x_{n})=g^{*}(x_{1},...,x_{n})}
Įrodymas:
f
∗
(
x
1
,
.
.
.
,
x
n
)
=
¬
f
(
¬
x
1
,
.
.
.
,
¬
x
n
)
=
¬
g
(
¬
x
1
,
.
.
.
,
¬
x
n
)
=
g
∗
(
x
1
,
.
.
.
,
x
n
)
{\displaystyle f^{*}(x_{1},...,x_{n})=\neg f(\neg x_{1},...,\neg x_{n})=\neg g(\neg x_{1},...,\neg x_{n})=g^{*}(x_{1},...,x_{n})}
f
(
x
1
,
.
.
.
,
x
n
)
=
g
(
x
1
,
.
.
.
,
x
n
)
⇒
f
(
¬
x
1
,
.
.
.
,
¬
x
n
)
=
g
(
¬
x
1
,
.
.
.
,
¬
x
n
)
{\displaystyle f(x_{1},...,x_{n})=g(x_{1},...,x_{n})\Rightarrow f(\neg x_{1},...,\neg x_{n})=g(\neg x_{1},...,\neg x_{n})}
Išvada:
f
(
x
1
,
x
2
,
.
.
.
,
x
n
)
=
g
(
x
1
,
x
2
,
.
.
.
,
x
n
)
{\displaystyle f(x_{1},x_{2},...,x_{n})=g(x_{1},x_{2},...,x_{n})}
tada ir tik tada , kai
f
∗
(
x
1
,
x
2
,
.
.
.
,
x
n
)
=
g
∗
(
x
1
,
.
.
.
,
x
n
)
{\displaystyle f^{*}(x_{1},x_{2},...,x_{n})=g^{*}(x_{1},...,x_{n})}
(f*)* =f
lengva įsitikinti…
Dualumo dėsnis
Įrodymas ankstesnioje pastraipoje
Jei
f
(
x
1
,
.
.
.
,
x
n
)
=
g
(
f
1
(
x
11
,
.
.
.
,
x
1
n
)
,
.
.
.
,
f
n
(
x
n
1
,
.
.
.
,
x
n
n
)
{\displaystyle f(x_{1},...,x_{n})=g(f_{1}(x_{11},...,x_{1n}),...,f_{n}(x_{n1},...,x_{nn})}
f
∗
(
x
1
,
.
.
.
,
x
n
)
=
g
∗
(
f
1
∗
(
x
11
,
.
.
.
,
x
1
n
)
,
.
.
.
,
f
n
∗
(
x
n
1
,
.
.
.
,
x
n
n
)
)
{\displaystyle f*(x_{1},...,x_{n})=g*(f_{1}*(x_{11},...,x_{1n}),...,f_{n}*(x_{n1},...,x_{nn}))}
f
∗
(
x
1
,
.
.
.
,
x
n
)
=
¬
g
(
f
1
(
¬
x
11
,
.
.
.
,
¬
x
1
n
)
,
.
.
.
,
f
n
(
¬
x
n
1
,
.
.
.
,
¬
x
n
n
)
{\displaystyle f*(x_{1},...,x_{n})=\neg g(f_{1}(\neg x_{11},...,\neg x_{1n}),...,f_{n}(\neg x_{n1},...,\neg x_{nn})}
=
¬
g
(
¬
¬
f
1
(
¬
x
11
,
.
.
.
,
¬
x
1
n
)
,
.
.
.
,
¬
¬
f
n
(
¬
x
n
1
,
.
.
.
,
¬
x
n
n
)
{\displaystyle =\neg g(\neg \neg f_{1}(\neg x_{11},...,\neg x_{1n}),...,\neg \neg f_{n}(\neg x_{n1},...,\neg x_{nn})}
=
¬
g
(
¬
f
1
∗
(
x
11
,
.
.
.
,
x
1
n
)
,
.
.
.
,
¬
f
n
∗
(
x
n
1
,
.
.
.
,
x
n
n
)
{\displaystyle =\neg g(\neg f_{1}*(x_{11},...,x_{1n}),...,\neg f_{n}*(x_{n1},...,x_{nn})}
=
g
∗
(
f
1
∗
(
x
11
,
.
.
.
,
x
1
n
)
,
.
.
.
,
f
n
∗
(
x
n
1
,
.
.
.
,
x
n
n
)
{\displaystyle =g*(f_{1}*(x_{11},...,x_{1n}),...,f_{n}*(x_{n1},...,x_{nn})}
Apibrėžimas:
f
1
(
x
1
,
.
.
.
,
x
n
)
∈
S
⇔
f
∗
=
f
{\displaystyle f_{1}(x_{1},...,x_{n})\in S\Leftrightarrow f^{*}=f}
Teorema: Jei
f
(
x
1
,
.
.
.
,
x
n
)
∉
S
{\displaystyle f(x_{1},...,x_{n})\notin S}
¬
x
{\displaystyle \neg x}
Pavyzdys:
f
(
¬
x
,
x
,
x
,
¬
x
)
=
s
(
x
)
=
c
{\displaystyle f(\neg x,x,x,\neg x)=s(x)=c}
Įrodymas: Jei
f
(
x
1
,
.
.
.
,
x
n
)
∉
S
{\displaystyle f(x_{1},...,x_{n})\notin S}
a
1
,
.
.
.
,
a
n
(
a
i
=
0
∨
a
i
=
1
,
1
≤
i
≤
n
{\displaystyle a_{1},...,a_{n}(a_{i}=0\lor a_{i}=1,1\leq i\leq n}
f
(
a
1
,
.
.
.
,
a
n
)
=
f
(
¬
a
1
,
.
.
.
,
¬
a
n
)
{\displaystyle f(a_{1},...,a_{n})=f(\neg a_{1},...,\neg a_{n})}
x
a
i
{\displaystyle x^{a_{i}}}
i =1 reikštų x, o ai =0 –
¬
x
{\displaystyle \neg x}
ϕ
(
x
)
=
f
(
x
a
1
,
…
,
a
n
)
{\displaystyle \phi (x)=f(x^{a_{1}},\ldots ,^{a_{n}})}
ϕ
(
x
)
=
f
(
x
a
1
,
…
,
a
n
)
=
f
(
¬
x
a
1
,
…
,
¬
x
a
1
)
=
ϕ
(
¬
x
)
{\displaystyle \phi (x)=f(x^{a_{1}},\ldots ,^{a_{n}})=f(\neg x^{a_{1}},\ldots ,\neg x^{a_{1}})=\phi (\neg x)}
ϕ
{\displaystyle \phi }
Aibė S yra uždara
Tarkime, kad
f
(
x
1
,
…
,
x
n
)
∈
S
,
f
1
(
x
1
1
,
…
,
x
n
1
)
∈
S
,
…
,
f
m
(
x
1
m
,
…
,
x
n
m
)
∈
S
{\displaystyle f(x_{1},\ldots ,x_{n})\in S,f_{1}(x_{1}^{1},\ldots ,x_{n}^{1})\in S,\ldots ,f_{m}(x_{1}^{m},\ldots ,x_{n}^{m})\in S}
g
=
f
(
f
1
,
…
,
f
m
)
{\displaystyle g=f(f_{1},\ldots ,f_{m})}
g
∗
=
f
∗
(
f
1
∗
(
…
)
,
…
,
f
m
∗
(
…
)
)
{\displaystyle g^{*}=f^{*}(f_{1}^{*}(\ldots ),\ldots ,f_{m}^{*}(\ldots ))}
i funkcijos bus autodualios, todėl ši aibė yra uždara
Richard Lassaigne, Michel de Rougemont „Logika ir Informatikos pagrindai“. vert. Stanislovas Norgėla. 1996 Leidykla „Žodynas“ 
