Cuprins

Forme normale pentru funcţii booleene

Pentru o funcţie oarecare, putem obţine forma normală disjunctivă (FND) descriind combinaţiile de valori pentru variabilele de intrare pentru care funcţia are valoarea 1, respectiv putem obţine forma normală conjunctivă (FNC) descriind combinaţiile de valori pentru variabilele de intrare diferite de cele pentru care funcţia are valoarea 0.

Fie următorul exemplu de funcţie booleană:

xyzf(x, y, z)
0001
0010
0101
0111
1001
1010
1100
1110

FND

Observăm că f(x, y, z) = 1 dacă şi numai dacă:

  • x = 0 şi y = 0 şi z = 0 sau
  • x = 0 şi y = 1 şi z = 0 sau
  • x = 0 şi y = 1 şi z = 1 sau
  • x = 1 şi y = 0 şi z = 0

Din această descriere obţinem uşor forma normală disjunctivă:

f(x, y, z) = x y z + x y z + x y z + x y z

Regulă generală:

  • Se consideră din tabelul de adevăr acele linii pentru care valoarea funcţiei este 1
  • Pentru fiecare astfel de linie se formeaza un termen conţinând variabilele de intrare legate prin conjuncţie; valorile variabilelor de intrare corespunzătoare fiecărei astfel de linii determină "starea" (negat sau nenegat) acestor variabile astfel:
    • dacă variabila xi apare cu valoarea 0, atunci în termenul respectiv ea va aparea negată
    • dacă variabila xi apare cu valoarea 1, atunci în termenul respectiv ea va aparea nenegată
    De exemplu, pentru x = 0, y = 1, z = 0, se construieşte conjuncţia xyz.
  • Termenii astfel obţinuţi se leagă prin disjuncţie.

FNC

În mod asemănător, observăm că f(x, y, z) != 0 dacă şi numai dacă:

  • x != 0 sau y != 0 sau z != 1 şi
  • x != 1 sau y != 0 sau z != 1 şi
  • x != 1 sau y != 1 sau z != 0 şi
  • x != 1 sau y != 1 sau z != 1

Din această descriere obţinem uşor forma normală conjunctivă:

f(x, y, z) = (x + y + z) (x + y +z) (x + y + z) (x + y + z)

Regulă generală:

  • Se consideră din tabelul de adevăr acele linii pentru care valoarea funcţiei este 0
  • Pentru fiecare astfel de linie se formeaza un factor conţinând variabilele de intrare legate prin disjuncţie; valorile variabilelor de intrare corespunzătoare fiecărei astfel de linii determină "starea" (negat sau nenegat) acestor variabile astfel:
    • dacă variabila xi apare cu valoarea 1, atunci în termenul respectiv ea va aparea negată
    • dacă variabila xi apare cu valoarea 0, atunci în termenul respectiv ea va aparea nenegată
    De exemplu, pentru x = 0, y = 1, z = 0, se construieşte disjuncţia x+y+z.
  • Factorii astfel obţinuţi se leagă prin conjuncţie.

∑-notaţie

O modalitate mai concisă de a exprima o funcţie booleană este dată de ∑-notaţie. Aceasta presupune reprezentarea variabilelor de intrare printr-un şir de biţi, în care fiecare variabilă este reprezentată de un bit 1 dacă apare direct şi de un bit 0 dacă apare negată. Şirul de biţi poate fi scris sub formă zecimală. Se vor preciza exact acele combinaţii pentru care valoarea funcţiei este 1.

De exemplu, pentru funcţia de mai sus, reprezentările variantelor pentru care funcţia are valoarea 1 sunt:

  • 0 0 0 (x y z) – 010
  • 0 1 0 (x y z) – 210
  • 0 1 1 (x y z) – 310
  • 1 0 0 (x y z) – 410

Aşadar, funcţia descrisă mai sus poate fi scrisă şi în forma: f(x,y,z) = ∑(0, 2, 3, 4)

De observat că numărul de intrări ale funcţiei este cel mai mic k pentru care cel mai mare număr care apare în ∑-notaţie este mai mic strict decăt 2k (de pildă, pentru funcţia de mai sus, k = 3).

Exerciţii

Să se scrie FND şi FNC pentru următoarele funcţii şi să se obţină forme simplificate ale acestor expresii, folosind axiomele şi teoremele algebrei booleene:

  1. ∑(1,4,5,6,7)
  2. ∑(3,5,6,7)
  3. ∑(2,3,5,6,7)
  4. ∑(1,2,3,4,9,15)
  5. ∑(0,2,6,8,10)
  6. ∑(0,2,5,7,13,16,21,23,29)