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

В каждой своей интерпретации формула принимает одно из двух истинностных значений — И или JI. Другими словами, формула задает функцию вида:

{ И, Л } ^п → { И, Л }.

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

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

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

Например одноместных истинностных функций — 4 ()

x	f1	f2	f3	f4
		x

двухместных истинностных функций — (0 – истина, 1 – ложь):

Та же таблица в обозначениях {И, Л}:

Задание: заполнить нижнюю строку полностью.

Теорема. Число п -местных истинностных функций равно

□Существует 2 ^п различных наборов значений п атомов. Любая истинностная функция с каждым из этих наборов сопоставляет одно из двух истинностных значений — И или Л. Значит, истинностных функций столько, сколько можно составить различных наборов из И или Л длины 2. Но всякий такой набор есть размещение с повторениями из двух элементов (И или Л) по 2 ^п. А таких размещений с повторениями имеется . Значит, различных п -местных истинностных функций существует .■