Класифікація формул алгебри висловлень

Формула алгебри висловлень F(X₁, X₂,..., Х_n) називається виконуваною, якщо деяка її конкретизація є істинним висловленням, тобто існують такі конкретні висловлення A₁, A₂,..., A_n які, будучи підставленими в цю формулу замість змінних X₁, X₂,..., Х_n, перетворюють її в істинне висловлення. Отже, F(X₁, X₂,..., Х_n) виконувана, якщо існують такі конкретні висловлення A₁, A₂,..., A_n, що λ(F(A₁, A₂,..., A_n))=1.

Формула F(X₁, X₂,..., Х_n) називається тавтологією, або тотожно істинно, якщо вона перетворюється в істинне висловлення при підстановці замість змінних будь-яких конкретних висловлень A₁, A₂,..., A_n, тобто якщо λ(F(A₁, A₂,..., A_n))=1 для довільних висловлень A₁, A₂,..., A_n. Для позначення тавтології використовується знак ╞, який ставиться перед формулою, котра є тавтологією. Таким чином, запис ╞ F(X₁, X₂,..., Х_n) означає, що формула F(X₁, X₂,..., Х_n) є тавтологією.

Формула F(X₁, X₂,..., Х_n) називається спростовною, якщо існують такі конкретні висловлення A₁, A₂,..., A_n, які перетворюють дану формулу в хибне висловлення F(A₁, A₂,..., A_n), тобто λ(F(A₁, A₂,..., A_n))=0. Іншими словами, спростовні формули - це формули, які не є тавтологіями.

Формула F(X₁, X₂,..., Х_n) називається тотожно хибною, або суперечністю, якщо λ(F(A₁, A₂,..., A_n))=0 для будь-яких висловлень A₁, A₂,..., A_n. Іншими словами, тотожно хибні формули - це такі формули, які не є виконуваними.

При розв’язуванні задач на класифікацію формул можна відмовитися від механічного складання таблиць істинності й розв’язувати їх методом аналізу структури формули та знаходження тих окремих наборів значень змінних, при яких формула приймає визначальне значення.

Звернемо увагу на те, що формула логіки висловлень сама по собі не має ніякого змісту. Зокрема, вона не є істинною, чи хибною. Вона перетворюється у висловлення, істинне чи хибне, при будь-якій підстановці замість усіх пропозиційних змінних довільних конкретних висловлень. Такий процес підстановки називається інтерпретацією даної формули.