Таблиці істинності

У таблиці істин­ності формули f(p,q,r) кожному символу логічної опера­ції в формулі f(p,q,r) відповідає окремий стовпчик таблиці, останній стовпчик відповідає істинісному значенню, яке визначається даною формулою (її головною операцією). Звернемо увагу на те, що кожен стовпчик таблиці істин­ності для формули f(p,q,r) відповідає певному кроку процесу її побудови або, як кажуть, певній підформулі f(p,q,r).

Наприклад, нехай задано функцію f(p,q,r)=( ®q Ú r )Ù(q®pÚ`r).

Часто таблицею істинності формули f(p₁, ..., p_n) називають скорочену таблицю, в якій з вищенаведеної залишають перших п стовпчиків (значень аргументів p₁, ..., p_n) і останній стовпчик.

Степінь складності таблиці істинності для формули f швидко зростає із збільшенням кількості різ­них пропозиційних букв, що входять до f. Так, при п = 3 кількість рядків таблиці дорівнює 2³ = 8, при п = 4 воно становить 2⁴= 16, при п= 5 дорівнює 2⁵= 32, а при п = 10 — вже 1024. Практично побудувати таблицю істин­ності в останньому випадку вже неможливо.