4.1 Булевi функцiï x 1 x 2 ... x n f ( x 1 , x 2 , ..., x n ) 0 0 ... 0 f ( 0 , 0 , ..., 0 ) 0 0 ... 1 f ( 0 , 0 , ..., 1 ) ... ... ... ... 1 1 ... 1 f ( 1 , 1 , ..., 1 )
Табл . 4.1 : Таблиця iстинностi булевоï функцiï .
Таблицю такого типу називають таблицею iстинностi булевоï функцiï f . В такiй таблицi рядки мають пробiгати по одному разу усi можливi комбiнацiï значень аргументiв функцiï ( щоб функцiя була однозначно визначеною ). В загальному випадку , множина { 0 , 1 } n ( область визначення булевоï функцiï n змiнних мiстить ) мiстить
|{ 0 , 1 } n | = |{ 0 , 1 }| n = 2 n
елементiв , тому в таблицi iстинностi функцiï n змiнних має бути 2 n рядкiв .
Наприклад , таблиця iстинностi булевоï операцiï заперечення ( табл . 4.2 ) мiстить 2 рядки , а таблиця iстинностi операцiï ∧ ( табл . 4.3 ) мiстить 4 рядки . x 1
0 1 1 0
Табл . 4.2 : Таблиця iстинностi заперечення .
x
x 1 x 2 x 1 ∧ x 2 0 0 0 0 1 0 1 0 0 1 1 1
Табл . 4.3 : Таблиця iстинностi кон ’ юнкцiï .
Слiд зауважити , що розмiр таблицi необхiдний для задання булевоï функцiï n аргументiв швидко росте зi збiльшенням значення n ( наприклад , 32 рядки при n = 5 , 1024 рядки при n = 10 ).
57