Substituind a0 + a1 + a2 x este 1 la 4 sistemul de ecuații, avem:
Adăugarea primelor trei ecuații, și observând că x + x = 0, obținem 0 = a0 + a0 = 0 ⇒ 1.
Substituind în ecuația 1 rezultate valorile a0 și a3. Obținem 0 + 1 = a2 + 1 sau 1 + 1 = a2, a2 = 0 unde.
Substituind valorile A0 și a3 în ecuația 2, obținem:
Astfel, g (x, y, z) = 0 + + + 1⋅h 0⋅u 1⋅z = x + z.
Pe baza acestei formule, vom găsi valorile funcției g din aceste seturi, pe care nu a fost determinată: g (0,0,0) = 0 + 0 = 0; g (0,0,1) = 0 + 1 = 1; g (0,1,0) = 0 + 0 = 0; g (1,0,0) = 1 + 0 = 1.
Ca rezultat, avem: g (x, y, z) = (01011010).
Extindem functia h, folosind definiția funcțiilor auto-duale. Deoarece seturile (0,0,0) și (1,1,1) opuse și h (0,0,0) = 1 ⇒ h (1,1,1) = 0.
Opunându perechi de seturi de valori ale variabilelor sunt (0,0,1) și (1,1,0), (0,1,0) și (1,0,1), (0,1,1) și (1 0.0).
Folosind valorile cunoscute ale funcției h, obținem:
h (0,0,1) = h (1,1,0) = 1 = 0, h (1,0,1) = h (0,1,0) = 1 = 0.
Astfel, h (x, y, z) = (10101010).
1. Poate funcția f (x, y, z) prin superpoziții obține g (x, y, z)?
2. Este adevărat că f (x, y, z) ∈ [g]. ([G] - închidere grad).
Verificăm f (x, y, z) să aparțină claselor poștale.
(0,0,0) ⪯ (0,0,1) și f (0,0,0)> f (0,0,1) ⇒ f ∉ M;
(0,0,1) și (1,1,0) - seturi opuse
f (0,0,1) = f (1,1,0) ⇒ f ∉ S;
f (x, y, z) = (x + 1) (y + 1) (z + 1) + (x + 1) yz + x (y + 1) z =
= 1 + x + y + z + xy + xz + yz + xyz + xyz + yz + xyz + xz =
= 1 + x + y + z + xy + xyz.
Deoarece în funcțiile polinomiale f conjuncție prezent, atunci f ∉ L.
Deci, vedem că funcția f (x, y, z) nu fac parte din niciuna dintre categoriile de Postul Mare, prin urmare, sistemul este complet funcțional, și prin suprapunerea f poate obține orice funcție booleană, în special, g (x, y, z).
Verificarea valorii funcției g (x, y, z) pentru toate perechile de seturi opuse, vom vedea:
g (0,0,0) = 1 = g (1,1,1). g (0,0,1) = 0 = g (1,1,0),
g (0,1,0) = 1 = g (1,0,1). g (0,1,1) = 1 = g (1,0,0).
Deoarece S - class funcțional închis, apoi [g] ⊆ S, dar f ∉ S, apoi, f ∉ [g].
Pentru funcții f (x, y, z) și g (x, y, z) pentru a clarifica problema apartenenței lor la T0 clasei. T1. L, S, M
Dacă o funcție este o clasă complet funcțional, exprimă din ea prin superpoziții constantă de 0,1, și xy negație conjuncție.
Dacă o funcție este o caracteristică-completă, în sensul slab al unei clase de ea exprimată prin suprapunerea și fixarea negația variabile și xy conjuncție.
Rezultatele obținute sunt verificate prin construirea tabelelor.
1. investiga functia f (x, y, z). Verificăm f (x, y, z) să aparțină claselor poștale.
Rețineți că acest lucru implică faptul că nu este funcțional clasa completă.
Deoarece seturile (0,0,0) și (1,1,1) opuse și f (0,0,0) = f (1,1,1), apoi f ∉ S.
Avem că (0,1,0) ⪯ (0,1,1), dar f (0,1,0)> f (0,1,1), apoi, f ∉ M.
Am găsit polinomială pentru f (x, y, z):
= Xyz + xy + yz + y + xyz + xy + xz + x = xz + yz + x + y.
Deoarece polinomul funcții f cuprinde conjugarea, atunci f ∉ L.
După cum sa menționat mai devreme, nu este funcțional de clasă completă, ci ca o funcție f este neliniară și monotonă - complet funcțional în sensul slab al clasei.
Ne exprimăm negarea f prin fixare variabile. Pe seturi învecinate (0,1,0) și (0,1,1) este încălcat monotonie, considerăm funcția p (x) = f (0,1, x).
Găsim toate valorile lui p (x):
p (0) = f (0,1,0) = 1, p (1) = f (0,1,1) = 0 ⇒ p (x) = x.
Negația construite, x = f (0,1, x).
Pentru a construi o conjuncție stabilească o variabilă și relabel variabilele rămase, astfel încât a luat forma unui polinom
xy + αx + βy + γ, unde α, β, γ ∈.
De exemplu, este posibil să se facă acest lucru: f (1, y, x) = 1⋅h + 1 + xy + y = xy + x + y + 1. In acest caz, α = β = γ = 1.
Prezentați functia h (x, y) = f (1, y + a, x + β) + αβ + γ = f (1, y. X) = = f (1, f (0,1, y), f (0,1, x)).
Să ne găsim valoarea h pe toate kiturile ei.
h (0,0) = f (1, f (0,1,0), f (0,1,0)) = f (1,1,1) = 0;
h (0,1) = f (1 f (0,1,1), f (0,1,0)) = f (1,0,1) = 0;
h (1,0) = f (1, f (0,1,0), f (0,1,1)) = f (1,1,0) = 0;
h (1,1) = f (1, f (0,1,1), f (0,1,1)) = f (1,0,0) = 1.
După cum vedem, funcția de masa h (x, y) coincide cu tabelul coroborat așadar h⋅u = f (1, f (0,1, y), f (0,1, x)).
2. investiga g (x, y, z) să aparțină claselor poștale.
Seturi (1,0,1) și (0,1,0) opuse și g (1,0,1) = g (0,1,0) ⇒ g ∉ S.
Deoarece (0,0,0) ⪯ (0,0,1), dar g (0,0,0)> g (0,0,1) ⇒ g ∉ M.
Am găsit polinomială pentru g (x, y, z):
g (x, y, z) = (x + 1) (y + 1) (x + 1) + (x + 1) yz + xy (z + 1) =
= Xyz + xy + xz + yz + x + y + z + 1 + xyz + yz + xyz + xy =
= 1 + x + y + z + xz + xyz.
Deoarece funcția polinomială g conține o conjuncție, atunci g ∉ L.
Astfel, g funcție nu face parte din oricare dintre cele cinci clase de post, aceasta înseamnă că funcționează ca o clasă completă.
Exprimă negație a g, folosind simpla superpoziție. Luați în considerare funcția s (x) = g (x, x, x).
Găsiți toate valorile funcției s (x):
s (0) = g (0,0,0) = 1, s (1) = g (1,1,1) = 0 ⇒ s (x) = x
Negația construite, x = g (x, x, x).
Construirea unei constante 0. Pentru aceasta vom lua un set de perechi de set oppositely pe care funcția g este 0, de exemplu, (1,0,1), și ia în considerare funcția G (x): (x) = g (x 1. x 0. x 1) = g (x, x. x) = g (x, g (x, x, x) x).
Să ne găsim valoarea funcției (x) pe seturi ei.
o (0) = g (0, g (0,0,0), 0) = g (0,1,0) = 0;
o (1) = g (1, g (1, g (1,1,1) 1) = g (1,0,1) = 0.
Constant construit 0, g (x, g (x, x, x), x) = 0.
Pentru a construi constant 1 ia negarea funcției v (x) și reprezintă funcția rezultată prin f (x).
Deci, koystanta 1 a fost obținut,
Pentru a construi conjuncție fixa variabila z, conferindu-i valoarea 1.
Obținem: g (x, y, 1) = 1 + x + y + 1 + x⋅1 + xy⋅1 = xy + y + 1, adică, avem o expresie de forma xy + + αh βu + gamma, unde .. α = γ = 0, β = 1.
Să considerăm funcția k (x, y) = g (x + β, y + a, 1) + αβ + γ =
= G (x + 1, y, 1) + 0⋅l + 0 = g (g (x, x, x), y, 1) =
Să ne găsim valoarea funcției pentru toate seturile sale.
k (0,0) = g (g (0,0,0), 0, g (G0, g (0,0,0), 0x g (0, g (0,0,0), 0) g (0, g (0,0,0), 0))) =
= G (1,0, g (g (0,1,0), g (0,1,0), g (0,1,0)) = g (1,0,0) = 0;
După cum se poate observa, funcția de tabelă h (x, y) coincide cu tabelul de conjuncție, prin urmare,
Se calculează numărul de diferite funcții booleene de n variabile care aparțin unui anumit set A.
Exemplul 1. Se calculează numărul de funcții booleene distincte de n variabile care aparțin setului L \ (T0 ∩S).
Vom nota cu L (n). T (n) 0. S (n), respectiv, o multitudine de liniar conservare zero, și auto-duale functii n variabile.
Zona hașurată corespunde funcțiilor clasei dorite. Evident, egalitatea:
| L (n) \ (T (n) 0 ∩S (n)) | = | L (n) | - | L (n) ∩T (n) 0 ∩S (n) |
Cu fiecare astfel de vector binar funcție a coeficienților său (a0. A1. A0. A0). Evident, această linie - bijectie, atunci numărul diferitelor funcții liniare de n variabile este egal cu numărul de seturi diferite de dimensiuni binare n + 1, adică, 2 n + 1, deci | L (n) | = 2 n + 1.
Dacă funcția liniară menține o constantă 0, a0 + a1 + a0 ⋅ ⋅ 0 + 0. AN + ⋅ 0 = 0 ⇒ a0 = 0, și are forma a1 x1 + a2 x2 +. AN + xn. Pentru funcția de auto-duală este realizată proprietatea f (x 1 x n) = f (x1. Xn). Având în vedere că x = x + 1, să vedem cum va arăta această ecuație într-un liniar, zero menținerea funcțiilor:
Adăugați modulo 2 la ambele părți ale expresiei rezultat egalitatea a1 x1 + x2 + a2. AN + xn. ținem cont de faptul că x + x = 0. Apoi, după simplificări avem: A1 + A1 +. = 1 + a1. (*)
Coeficienților a1. a1. AN poate atribui în mod arbitrar raportul n-1, și o valoare a coeficientului n-lea este unic determinat din ecuația (*). Deci, între setul de funcții booleene în clasa L (n) ∩T (n) 0 ∩S (n) și setul de vectori binari de dimensiune n-1 există bijectie, atunci egalitatea | L (n) ∩T (n) 0 ∩S (n) | = 2 n-1.
Ca rezultat, obținem:
| L (n) \ T (n) 0 ∩ S (n)) | = | L (n) | - | L (n) ∩ T (n) 0 ∩ S (n) | = 2 n + 1 - 2 n-1 = 2 n-1 (4-1) = 3⋅2 n-1.
Exemplul 2. Se calculează numărul de diferite funcții booleene de n variabile care aparțin setului S ∪ T 1.
Vom nota cu S (n) și T (n) 1, respectiv, și o multitudine de funcții auto-duale de conservare unitate n variabile.
Zugrăvi seturi S (n) și T (n) 1 (Fig. 2.4.4, b).
| S (n) ∪ T (n) 1 | = | S (n) | + | T (n) 1 | - | S (n) ∩ T (n) 1 |.
Fie f ∈ S (n). g ∈ T (n) 1. h ∈ S (n) ∩T (n) 1. Tabelul descrie aceste funcții.