Введение
Функция в классической логике
В логике функция истинности – это функция, принимающая значения истинности в качестве входных данных и выдающая единственное значение истинности в качестве результата. Иными словами, входные и выходные данные функции истинности являются значениями истинности; функция истинности всегда выдает ровно одно значение истинности, и при вводе одних и тех же значений истинности всегда выдает одно и то же значение. Типичный пример можно найти в пропозициональной логике, где сложное высказывание строится из простых высказываний, соединенных логическими связками. Если значение истинности сложного высказывания полностью определяется значениями истинности составляющих его простых высказываний, то сложное высказывание называется функцией истинности, а используемые логические связки – истинно-функциональными. Классическая пропозициональная логика является истинно-функциональной логикой, поскольку каждое высказывание имеет ровно одно значение истинности – либо истинное, либо ложное, и каждая логическая связка является истинно-функциональной (с соответствующей таблицей истинности), следовательно, каждое сложное высказывание является функцией истинности. Модальная логика, напротив, не является истинно-функциональной.
Таблица бинарных функций истинности
В двухзначной логике существует шестнадцать возможных функций истинности, также называемых булевыми функциями, от двух аргументов P и Q. Каждая из этих функций соответствует таблице истинности определенного логического оператора в классической логике, включая несколько особых случаев, таких как функция, не зависящая от одного или обоих своих аргументов. Истина и ложь обозначаются как 1 и 0 соответственно в следующих таблицах истинности для краткости.
Информатика
Логические операторы реализуются в виде логических элементов в цифровых схемах. Практически все цифровые схемы (главным исключением является DRAM) строятся на основе элементов NAND, NOR, NOT и передаточных вентилей. Элементы NAND и NOR с тремя и более входами, а не с обычными двумя, встречаются довольно часто, хотя они логически эквивалентны каскаду из двухвходовых элементов. Все остальные операторы реализуются путем разложения их на логически эквивалентную комбинацию из двух или более вышеуказанных логических элементов. "Логическая эквивалентность" систем, основанных только на "NAND", только на "NOR" и на "NOT и AND", аналогична эквивалентности по Тьюрингу. Тот факт, что все булевы функции могут быть выражены только с помощью NOR, демонстрируется на примере бортового компьютера системы управления Apollo.