Існує загальноприйнята класифікація булевих формул в залежності від виду таблиці істинності. По-перше, як само собою зрозуміле, можна сказати про кількість перменная у формулі. Як мінімум нуль змінних для формул на кшталт (true false). як максимум - хоч греблю гати. По-друге, має значення, що написано в останньому стовпчику. Якщо там одні тільки true. то така формула називається "загальнозначущої" або "тавтологією". Інакше це буде "необщезначімая" формула. Якщо там одні тільки false. то така формула називається "нездійсненним", інакше це буде "здійсненне" формула. "Нейтральні" формули містять як true. так і false.
[Загальнозначуща формула]: тавтологію або загальнозначущої формулою називається булева формула, таблиця істинності якої містить лише true в правій колонці.
Приклад: true false
[Здійсненне формула]: виконуваності формул називається булева формула, таблиця істинності якої містить хоча б одне true в правій колонці.
[Нездійсненне формула]: виконуваності формул називається булева формула, таблиця істинності якої містить лише false в правій колонці.
[Необщезначімая формула]: Необщезначімой формулою називається булева формула, таблиця істинності якої містить хоча б одне false в правій колонці.
Приклад: A B C
[Нейтральна формула]: Нейтральній формулою називається булева формула, таблиця істинності якої містить хоча б одне false і хоча б одне true в правій колонці.
Приклад: (A B) C
Слово "тавтологія" означає не те, поза математики. Це - твердження, які використовують різного роду примітивні повторення. Наприклад "масло масляне", "світ світлий", "сон - це сон", "не може бути тому, що не може бути ніколи". Тавтологія в математиці не обов'язково містить настільки примітивні повторення. Наприклад, формула (A
A B C D) - тавтологія. Незабаром ви побачите, що математичні тавтології бувають вельми корисні.
Отже, все булеві формули діляться на три ізольованих класу - загальнозначущі (тавтології), нейтральні і нездійсненні. Загальнозначущі і нейтральні разом дають клас здійсненних формул. Нездійсненні і нейтральні разом дають клас необщезначімих. Ось наочна таблиця для цієї класифікації: