După cum sa menționat deja, valoarea formulei Boolean este complet dependentă de valorile incluse în această formulă rostiri. Prin urmare, formula boolean este o funcție de propunerile sale constitutive elementare.
De exemplu, formula (x y) ®z este o funcție de trei variabile f (x, y. z). O caracteristică a acestei caracteristici este faptul că argumentele sale ia una dintre cele două valori: zero sau unu, și, prin urmare, de asemenea, funcția are una din cele două valori: zero sau unu.
Funcția variabilelor booleene n (sau funcția boolean) este o funcție de variabile n, în cazul în care fiecare variabilă are două valori: 0 și 1, și în care funcția poate lua numai una dintre cele două valori: 0 sau 1.
In mod clar, formulă falsă identică și identic adevărată a funcțiilor booleene sunt constante, iar cele două formule echivalente exprimă aceeași funcție.
Să vedem ce este numărul de funcții de n variabile. Evident, orice funcție booleană (ca în logica algebra formula) pot fi specificate folosind un tabel de adevăr, care va conține rânduri 2n. Prin urmare, fiecare funcție variabilă n ia valori 2n compuse din unu și zero. Astfel, funcția n variabile definite complet set de valori de zero-uri și cele de lungime 2n. Numărul total de seturi constând din zerouri și cele, de o lungime egală cu 2n. Prin urmare, numărul diferitelor funcții logice de n variabile este egal cu algebra.
În special, diferitele funcții ale unei variabile este de patru, iar diferitele funcții ale două șaisprezece variabile. De exemplu, toate funcțiile algebra logicii poate fi rezumată în tabelul variabilă. 8.
Posibile funcții booleene ale unei variabile
Din acest tabel rezultă că cele două funcții ale unei singure variabile va fi constantă: F 1 (x) 1 °, F 4 (x) 0 ° F 2 (x) º x și.
Orice funcție booleană arbitrară poate fi reprezentată sub forma unor formule Booleene.
Să presupunem, de exemplu, F (x 1, x 2. xn) - o funcție arbitrară a variabilelor booleene n. Luați în considerare formula
ÚF (1,1. 0) x 1 x 2. Ú (1)
ÚF (1,1. 1,0,1) x 1 x 2. xn Ú. Ú
care este compus după cum urmează: fiecare termen al sumei logice este o conjuncție în care primul termen este valoarea funcției F la anumite valori specifice ale variabilelor x 1, x 2. xn. în timp ce membrii rămași ai conjuncției sunt variabile sau negațiile lor. Astfel, sub semnul negației sunt acelea și doar acele variabile care primul termen coroborat au valoarea 0. Astfel, formula (1) conține o conjuncție logică a tuturor termenilor posibile ale formei indicate.
In mod evident, formula (1) specifică complet funcția F (x 1, x 2. xn). Cu alte cuvinte, valorile funcției F și formula (1) sunt aceleași în toate seturile de valori variabile x 1, x 2. xn.
De exemplu, dacă 1 x ia valoarea 0 și variabilele rămase asumă valoarea 1, funcția F este setată la F (0,1,1. 1). În acest termen logică F (0,1 1). x 2. xn. inclus în formula (1), primește, de asemenea, valoarea F (0,1. 1), x 2. xn º1 și F (x 1, x 2. xn) 1ºF (x 1, x 2. xn). Toți ceilalți termeni logici cu formula (1) au o valoare de 0. De fapt, în negarea semnelor variabile sunt distribuite în mod diferit decât în termenul de mai sus, dar în cazul în care schimbarea variabilelor aceleași valori în conjuncție introduce simbolul 0 nega semnul, simbolul 1 sub semnul negației . În acest caz, un membru al conjuncției are valoarea 0, și, prin urmare, toate conjuncției are valoarea 0 și F (x 1, x 2. xn) 0º0. În acest sens, pe baza echivalenței x Ú 0 ° valoarea X cu formula (1) este F (0,1. 1).
In mod evident, tipul de formula (1) poate fi mult simplificată dacă trebuie să se debaraseze acei termeni logici, în care prima conjuncția membru respectiv F (x 1, x 2. xn) are o valoare de 0 (și, prin urmare, toate conjuncției are valoarea 0). Dacă primul termen din membrul conjunctii logic are valoarea 1 (adică, F (x 1, x 2. xn) = 1) apoi, folosind equipollence 1x ° x. Acest membru al conjuncției nu poate scrie.
Astfel, rezultatul este formula (1), care conține variabile propozitionale numai elementare și are următoarele proprietăți.
1. Fiecare formulă pe termen logic conține toate variabilele incluse în funcția F (x 1, x 2. xn).
2. termeni Toți logic diferite formule.
3. Nici unul dintre formula logică include un termen nu ambele variabile și negația.
4. Nici unul dintre formula logică termenul nu conține aceeași variabilă de două ori.
Aceste proprietăți sunt numite proprietăți perfecțiune sau proprietăți pe scurt (C). Astfel, proprietățile perfecțiune - un set de proprietăți ale funcțiilor booleene, în care are forma cea mai simplă.
Din discuția de mai sus, se observă că fiecare funcție nu este corespunde identic cu numai formulă de tip fals indicat.
Dacă funcția F (x 1, x 2. xn) este dat un tabel de adevăr, atunci formula corespunzătoare algebra logicii poate fi obținută simplu. Într-adevăr, pentru fiecare set de variabile pe care funcția F (x 1, x 2. xn) este 1, vom scrie conjunction elementare variabile propoziționale, luând XK membru coroborat. în cazul în care valoarea XK pe un anumit set de valori ale variabilelor au un 1 și o negare a XK. în cazul în care valoarea 0. XK au Disjuncția toate conjuncțiilor înregistrate este formula necesară.
Să presupunem, de exemplu, funcția F (x 1, x 2, x 3) având următorul tabel de adevăr (tabelul. 9).
Tabelul de adevăr pentru funcția F (x 1, x 2, x 3)
Seturi de valori pentru variabile (1,1,0) și (0,1,0), în cazul în care funcția ia valoarea 1, vom scrie conjuncția și formula dorită având proprietățile (c) are forma
Luați în considerare așa-numita lege a dualitatii este folosită în transformarea ecuațiilor booleene.
Să presupunem formula A conține numai operații de conjuncție, disjuncție și negație. Vom numi conjuncția funcționarea duală a funcționării disjuncție și funcționarea disjuncție a funcționării dublă conjuncției.
Formula A și A * sunt numite dublu dacă formula A * se obține din formula A prin înlocuirea acesteia fiecare operație pe dual.
De exemplu, cu formula A = (x Úy) z formula voință formula dublă A * ° (x y)Úz.
Afirmăm fără dovezi teorema următoare în ceea ce privește formula dublă.
Teorema 1. Dacă formulele A și B sunt echivalente, atunci ele sunt echivalente și sunt formulă dublă, adică A * ºV *.
Teorema 2 Dacă formula A (x 1, x 2, ..., xn) este o formulă dublă A * (x 1, x 2, ..., xn), atunci următoarea echivalență
Astfel, ca rezultat al negației unei formule obținute prin formula duală în care variabilele sunt negațiile lor.
articole similare
Trimiteți-le prietenilor: