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