Истинностные функции

В каждой своей интерпретации формула принимает одно из двух истинностных значений — И или Л. Дру­гими словами, формула задает функцию вида {И, Л}ⁿ ® {И, Л}

Определение 6. Функция вида {И, Л}ⁿ ® {И, Л} назы­вается п-местной истинностной функцией или функцией алгебры высказываний.

Две равносильные формулы определяют одну и ту же истинностную функцию. Следовательно, истинностные функции можно рассматривать как характеристики клас­сов равносильных формул.

Исходя из данного набора п атомов, можно соста­вить счетное множество формул. Однако все эти форму­лы описывают лишь конечное множество истинностных функций, например двухместных истинностных функ­ций — 16 (табл. 1.4).

Таблица 1

Предложение 1. Число п-местных истинностных функций равно 2⁽²ⁿ⁾

Виды формул алгебры высказываний и их классификации

В алгебре высказываний для некоторых классов фор­мул применяются специальные имена, которые мы введем следующими определениями.

Определение 7. Формула А называется общезначи­мой (тождественно истинной, тавтологией), если во всех своих интерпретациях она принимает значение И.

Определение 8. Формула А называется невыпол­нимой (тождественно ложной, противоречием), если во всех своих интерпретациях она принимает значение Л.

Определение 9. Формула А называется нейтраль­ной, если она не является ни общезначимой, ни невы­полнимой.

Определение 10. Формула А называется выполни­мой, если она общезначимая или нейтральная.

Определение 11. Формула А называется необщезна­чимой, если она невыполнимая или нейтральная.

Определения 7 — 11 дают три классификации фор­мул, которые наглядно представлены табл. 2

Таблица 2