Monotónní a Lineární Funkce 1. Relace předcházení Uvažujme dva vektory hodnot proměnných x1 ,…, xn
a to α = (α1 ,…,α n ) a β = ( β1 ,…, β n ) . Říkáme, že vektor hodnot α předchází vektor hodnot β (značíme
α ≺ β ) právě tehdy, když pro jednotlivé hodnoty platí α1 ≤ β1 , ,α n ≤ β n . Danou relaci nazýváme relace předcházení. Například vektor hodnot α = ( 0,1,0,1) předchází
vektor β = (1,1,0,1) , protože pro jednotlivé hodnoty zároveň platí
α1 = 0 ≤ 1 = β1 , α 2 = 1 ≤ 1 = β 2 , α 3 = 0 ≤ 0 = β3 , α 4 = 1 ≤ 1 = β 4 . Oproti tomu například vektory ( 0,1) a (1,0 ) jsou v relaci předcházení nesrovnatelné. Relace předcházení je vzhledem k množině všech nrozměrných vektorů hodnot proměnných ( x1 ,…, xn ) částečným uspořádáním.
2. T řída monotónních funkcí S pomocí relace předcházení můžeme specifikovat vybranou množinu logických funkcí. f ( x1 ,…, xn ) ∈ P2 nazveme Logickou funkci monotónní, jestliže pro každé dva vektory hodnot proměnných α , β takových, že α ≺ β , pro funkční
( ) ( )
hodnoty funkce f platí f α ≤ f β . Množinu všech monotónních funkcí nazýváme třída monotónních funkcí a značíme M. Mezi monotónní funkce patří například logické funkce 0,1, x, x1 ∧ x2 , x1 ∨ x2 . Monotónnost jde opět ověřit s pomocí tabulky pravdivostních hodnot dané funkce. Ukažme si postup na funkci x1 ∧ x2 . Nejdříve si vytvoříme tabulku 0 0 0 pravdivostních hodnot funkce. Existují dvě 0 1 0 posloupnosti vektorů hodnot v relaci a ( 0,0 ) ≺ ( 0,1) ≺ (1,1) 1 0 0 předcházení: 1 1 1 ( 0,0 ) ≺ (1,0 ) ≺ (1,1) . Pro dané posloupnosti vektorů hodnot srovnáme jejich funkční hodnoty. Platí f ( 0,0 ) = 0 ≤ f ( 0,1) = 0 ≤ f (1,1) = 1 a f ( 0,0 ) = 0 ≤ f (1,0 ) = 0 ≤ f (1,1) = 1. Vidíme, že funkce je monotónní. x1
x2
x1 ∧ x2
Věta 3.4.6 Třída všech monotónních funkcí je funkcionálně uzavřená. Důkaz. To, že M ⊆ [ M ] je evidentní. Musíme tedy dokázat ještě opačnou inkluzi. Vezměme libovolnou funkci F ∈ [ M ] , potom musí existovat monotónní funkce f , f1 ,…, f m ∈ M tak, že F ( x1 ,…, xn ) = f ( f1 ( x1 ,…, xn ) ,…, f m ( x1 ,…, xn ) ) . Poznamenejme, že obecně funkce F , f , f1 ,…, f m nemusí být funkcemi stejného počtu proměnných, za n však můžeme vzít maximální počet proměnných v jedné z funkcí a do ostatních přidat fiktivní proměnné, aniž by se hodnoty funkce změnily. Nechť α = (α1 ,…,α n ) a β = ( β1 ,…, β n ) , α ≤ β , jsou vektory hodnot proměnných ( x1 ,…, xn ) . Pro každé
( )
( )
i = 1,…, m platí fi ∈ M a tudíž f i α ≤ f i β . Pak
( f (α ) ,…, f (α )) ≺ ( f ( β ) ,…, f ( β )) 1
1
m
m
a protože funkce f je také monotónní, platí
( ( )
( )) ≤ f ( f ( β ) ,…, f ( β ))
f f1 α ,… , f m α
( )
( )
a tedy F α ≤ F β .
1
m
cbd.
Vektory
α = (α1 ,…,α i −1 , α i , α i +1 ,…,α n ) ,
β = ( β1 ,…, β i −1 , β i , β i +1 ,…, β n )
budeme nazývat sousední podle i-té souřadnice, jestliže α i ≠ βi a pro každé j ≠ i, j = 1,… , n platí α j = β j . Příklad. Vezměme vektory α = (1,0,1) a β = ( 0,0,1) . Tyto vektory jsou sousední podle první souřadnice. Věta 3.4.7 (lemma o nemonotónní funkci) Nechť logická funkce f ( x1 ,…, xn ) nepatří do třídy monotónních funkcí. Potom dosazením funkcí 0, 1, x za její proměnné lze získat nemonotónní funkci x . Důkaz. Důkaz této věty se skládá ze dvou částí. V první části dokážeme tvrzení, že existují dva sousední vektory hodnot α , β takové, že vektor α předchází vektor β a zároveň
( ) ( )
platí f α > f β . Z předpokladu věty, funkce f nepatří do třídy monotónních (1)
funkcí, potom musí existovat dva vektory α , β že zároveň platí α (1)
(1)
(1)
≺ β
(1)
(1)
takové,
( ) ( ) . Jsou-li
a f α
(1)
> f β
(1)
vektory α , β sousední, potom je tvrzení dokázáno.
Pokud ne, potom se musí lišit v určitém konečném počtu t hodnot proměnných, přičemž dané proměnné nabývají ve (1)
vektoru α
hodnoty 0 a ve vektoru β (2)
(1)
hodnoty 1. Potom
(t )
musí existovat t-1 vektorů α ,…,α , takových, že (1)
(2)
(t )
(1)
α ≺ α ≺ ≺ α ≺β a každé dva po sobě jdoucí vektory této posloupnosti jsou sousední. (1) (1) Díky tomu, že pro vektory α , β platí
( ) ( ),
f α
(1)
> f β
(1)
musí v této posloupnosti existovat
dvojice sousedních vektoru, označme je α , β , pro kterou
( ) ( )
platí f α > f β . Tím je první část dokázána. Nyní vezmeme dva sousední vektory α , β . Nechť se liší v i-té souřadnici. Můžeme tedy psát
α = (α1 ,…,α i −1 , 0, α i +1 ,…,α n ) ,
β = (α1 ,…,α i −1 ,1, α i +1 ,…,α n )
. Vytvořme funkci Φ ( x ) = f (α1 ,…,α i −1 , x, α i +1 ,…,α n ) . Ukážeme, že tato funkce je námi hledaná nemonotónní funkce x . Dosadíme za proměnnou x hodnoty 0 a 1. Φ ( 0 ) = f α a to je jistě z našeho předpokladu ostře větší
( )
( )
než Φ (1) = f β .
Ovšem nerovnost Φ ( 0 ) > Φ (1) platí
právě tehdy, když Φ ( 0 ) = 1 a zároveň Φ (1) = 0 . Toto je však vlastnost pro hodnoty funkce x . cbd.
Příklad. Uvažujme funkci f ( x1 , x2 ) = ( x1 ⇒ x2 ) . Nejdříve musíme ukázat, že tato funkce není monotónní. Vezměme například vektory α = (1,0 ) a β = ( 0,0 ) . Tyto vektory jsou sousední podle první souřadnice. Platí, že vektor (0,0) předchází vektoru (1,0) a f ( 0,0 ) = 1 > 0 = f (1,0 ) , tedy funkce není monotónní. Nyní definujme funkci Φ ( x ) = f ( x,0 ) = ( x ⇒ 0 ) . Dosazením hodnot 0 a 1 za proměnnou x ověříme, že funkce Φ ( x ) = x . Opravdu, Φ ( 0 ) = ( 0 ⇒ 0 ) = 1 a Φ (1) = (1 ⇒ 0 ) = 0 .
3. Třída lineárních logických funkcí Lineární logickou funkci nazveme každou funkci ve tvaru f ( x1 ,…, xn ) = c0 ⊕ c1 x1 ⊕
⊕ cn xn , c0 , c1 ,…, cn ∈ { 0,1}
tedy funkci, jejíž Žegalkinův polynom obsahuje pouze lineární členy. Tuto množinu funkcí nazýváme třída lineárních logických funkcí a značíme L. Tato třída je funkcionálně uzavřená. Věta 3.4.8 (lemma o nelineární funkci) Nechť logická funkce f ( x1 ,…, xn ) nepatří do třídy lineárních funkcí. Potom dosazením funkcí 0,1, x a x za její proměnné a případně negováním funkce f, můžeme vyjádřit nelineární funkci logického součinu dvou proměnných. Důkaz. Funkce f nepatří do třídy lineárních funkcí. Potom Žegalkinův polynom funkce f musí obsahovat alespoň jeden nelineární člen, bez újmy na obecnosti předpokládejme, že je to člen x1 x2 . Potom vytkneme-li postupně ze všech možných členů polynomu logický součin x1 x2 , z možných zbylých proměnnou x1 a x2 potom polynom funkce f můžeme upravit do tvaru
f ( x1 ,…, xn ) = x1 x2 f (1,2) ( x3 ,…, xn ) ⊕ x1 f (1) ( x3 ,…, xn ) ⊕ x2 f (2) ( x3 ,…, xn ) ⊕ f (0) ( x3 ,…, xn ) přičemž f (1,2) , f (1) , f (2) , f (0) jsou logické funkce n-2 proměnných x3 ,…, xn , které vznikly po řadě vytknutím jednotlivých členů x1 x2 , x1 , x2 a platí f (1,2) ( x3 ,… , xn ) ≠ 0 (v opačném případě bychom popřeli náš předpoklad, že funkce f obsahuje lineární člen x1 x2 - "vypadl" by nám). Potom musí existovat (n-2)-tice hodnot α 3 ,…,α n tak, že f (1,2) (α 3 ,… ,α n ) = 1. Můžeme tedy vytvořit funkci dvou proměnných Φ ( x1 , x2 ) = f ( x1 , x2 , α 3 ,…,α n ) = x1 x2 ⊕ ax1 ⊕ bx2 ⊕ c , kde a, b, c ∈ {0,1} . Z této funkce vytvoříme další funkci dvou proměnných Ψ ( x1 , x2 ) = Φ ( x1 ⊕ b, x2 ⊕ a ) ⊕ ab ⊕ c a ukážeme si, že je naši hledanou nelineární funkcí, která je ekvivalentní logickému součinu v našem případě x1 x2 .
Ψ ( x1 , x2 ) = Φ ( x1 ⊕ b, x2 ⊕ a ) ⊕ ab ⊕ c =
( x1 ⊕ b )( x2 ⊕ a ) ⊕ a ( x1 ⊕ b ) ⊕ b ( x2 ⊕ a ) ⊕ c ⊕ ab ⊕ c = x1 x2 ⊕ ax1 ⊕ bx2 ⊕ ab ⊕ ax1 ⊕ ab ⊕ bx2 ⊕ ab ⊕ c ⊕ ab ⊕ c = x1 x2 . cbd. Příklad.
Vezměme funkci f ( x1 , x2 , x3 ) = x1 ⊕ x1 x2 x3 ⊕ x2 x3 ⊕ 1. Tato funkce již je ve tvaru Žegalkinova polynomu a na první pohled je patrné, že není lineární protože obsahuje dva nelineární členy a to x1 x2 x3 a x2 x3 . (Pokud by funkce nebyla ve tvaru Žegalkinova polynomu, musí se nejdříve do tohoto tvaru převést.) Můžeme tedy z této funkce vytvořit funkci logického součinu. Možností máme několik, buď x1 x2 nebo x1 x3 a nebo x2 x3 . Zvolme dvojčlen x1 x2 . Potom funkci můžeme vytýkáním upravit f ( x1 , x2 , x3 ) = x1 ⊕ x1 x2 x3 ⊕ x2 x3 ⊕ 1 = x1 x2 ( x3 ) ⊕ x1 (1) ⊕ x2 ( x3 ) ⊕ 1 a tedy f (1,2) ( x3 ) = x3 , f (1) ( x3 ) = 1, f (2) ( x3 ) = x3 , f (0) ( x3 ) = 1. Funkce f (1,2) je různá od hodnoty nula pro proměnnou
α 3 = 1. Dosaďme tedy do funkce f za proměnnou x3 hodnotu α 3 = 1, čímž vytvoříme funkci Φ ( x1 , x2 ) = f ( x1 , x2 , α 3 ) = f ( x1 , x2 ,1) = x1 x2 ⊕ x1 ⊕ x2 ⊕ 1. Konkrétní hodnoty konstant a, b, c jsou a = b = c = 1. Nyní z této funkce vytvoříme další funkci dvou proměnných Ψ ( x1 , x2 ) = Φ ( x1 ⊕ b, x2 ⊕ a ) ⊕ ab ⊕ c a ukážeme, že je ekvivalentní funkci x1 x2 . Konkrétně tedy Ψ ( x1 , x2 ) = Φ ( x1 ⊕ 1, x2 ⊕ 1) ⊕ 1 ⋅1 ⊕ 1 =
( x1 ⊕ 1)( x2 ⊕ 1) ⊕ 1( x1 ⊕ 1) ⊕ 1( x2 ⊕ 1) ⊕ 1 ⊕ 1 ⋅1 ⊕ 1 = x1 x2 ⊕ 1x1 ⊕ 1x2 ⊕ 1 ⋅1 ⊕ 1x1 ⊕ 1 ⋅1 ⊕ 1x2 ⊕ 1 ⋅1 ⊕ 1 ⊕ 1 ⋅1 ⊕ 1 = x1 x2 ⊕ x1 ⊕ x1 ⊕ x2 ⊕ x2 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = x1 x2 . V případě, že zvolíme jiný nelineární člen, například x2 x3 , je postup analogický. f ( x1 , x2 , x3 ) = x1 ⊕ x1 x2 x3 ⊕ x2 x3 ⊕ 1 = x2 x3 ( x1 ⊕ 1) ⊕ ( x1 ⊕ 1) a tedy f (2,3) ( x1 ) = x1 ⊕ 1, f (2) ( x1 ) = 0, f (3) ( x1 ) = 0, f (0) ( x1 ) = x1 ⊕ 1 . Funkce f (2,3) je různá od hodnoty nula pro proměnnou α1 = 0 . Dosaďme tedy do funkce f za proměnnou x1 hodnotu 0, čímž vytvoříme funkci
Φ ( x2 , x3 ) = x2 x3 ⊕ 1 . Konkrétní hodnoty konstant a, b, c jsou a = b = 0, c = 1. Nyní z této funkce vytvoříme funkci Ψ ( x2 , x3 ) = Φ ( x2 ⊕ 0, x3 ⊕ 0 ) ⊕ 0 ⋅ 0 ⊕ 1 a ukážeme, že je to funkce x2 x3 : Ψ ( x2 , x3 ) = x2 x3 ⊕ 1 ⊕ 1 = x2 x3 .
4. Třídy T0 , T1 , S , M , L jsou vzájemně různé
Podotkněme, že uvedené funkcionálně uzavřené třídy T0 , T1 , S , M , L jsou po dvou navzájem různé, což lze vidět z následující tabulky. Vezměme tři nejjednodušší elementární funkce 0, 1 a x . Následující tabulka ukazuje zastoupení těchto funkcí v jednotlivých třídách (znaménko + znamená, že funkce do třídy patří, - funkce do třídy nepatří).
0 1 x
T0 + -
T1 + -
S +
M + + -
L + + +
Díky tomu, že ani v jedné z tříd nejsou funkce zastoupeny stejně, můžeme tvrdit, že třídy jsou vzájemně různé.
