Функция истинности

Функция в логике

В логике функция истинности ^[1] — это функция , которая принимает значения истинности в качестве входных данных и выдает уникальное значение истинности в качестве выходных данных. Другими словами: входные данные и выходные данные функции истинности являются значениями истинности; функция истинности всегда выводит ровно одно значение истинности, а ввод одних и тех же значений истинности всегда выводит одно и то же значение истинности. Типичный пример — пропозициональная логика , в которой составное утверждение строится с использованием отдельных утверждений, соединенных логическими связками ; если значение истинности составного утверждения полностью определяется значением истинности составляющих утверждений, составное утверждение называется функцией истинности, а любые используемые логические связки называются функциональными истинами . ^[2]

Классическая пропозициональная логика является истинностно-функциональной логикой ^[3] , в которой каждое утверждение имеет ровно одно истинностное значение, которое либо истинно, либо ложно, и каждая логическая связка является истинностно-функциональной (с соответствующей таблицей истинности ), таким образом, каждое составное утверждение является истинностной функцией. ^[4] С другой стороны, модальная логика не является истинностно-функциональной.

Обзор

Логическая связка является истинностно-функциональной, если истинностное значение сложного предложения является функцией истинностного значения его подпредложений. Класс связок является истинностно-функциональным, если каждый из его членов является истинностным. Например, связка " and " является истинностно-функциональной, поскольку предложение типа " Apples are fruits and carrots are vegetables " истинно тогда и только тогда , когда каждое из его подпредложений " apples are fruits " и " carrots are vegetables " истинно, и ложно в противном случае. Некоторые связки естественного языка, такого как английский, не являются истинностно-функциональными.

Связки вида "x считает, что ..." являются типичными примерами связок, которые не являются истинностно-функциональными. Если, например, Мэри ошибочно полагает, что Эл Гор был президентом США 20 апреля 2000 года, но она не верит, что луна сделана из зеленого сыра, то предложение

« Мэри считает, что 20 апреля 2000 года президентом США был Альберт Гор »

верно, пока

« Мэри верит, что луна сделана из зеленого сыра »

ложно. В обоих случаях каждое составное предложение (например, « Эл Гор был президентом США 20 апреля 2000 года » и « Луна сделана из зеленого сыра ») ложно, но каждое сложное предложение, образованное префиксом фразы « Мэри верит, что » отличается по истинностному значению. То есть истинностное значение предложения формы « Мэри верит, что... » определяется не только истинностным значением его составного предложения, и, следовательно, (унарный) соединительный элемент (или просто оператор , поскольку он унарный) не является истинностно-функциональным.

Класс классических логических связок (например , & , → ), используемых при построении формул, является истинностно-функциональным. Их значения для различных истинностных значений в качестве аргумента обычно задаются таблицами истинности . Истинностно-функциональное пропозициональное исчисление — это формальная система , формулы которой могут быть интерпретированы как истинные или ложные.

Таблица бинарных функций истинности

В двузначной логике существует шестнадцать возможных функций истинности, также называемых булевыми функциями , двух входов P и Q. Любая из этих функций соответствует таблице истинности определенной логической связки в классической логике, включая несколько вырожденных случаев, таких как функция, не зависящая от одного или обоих своих аргументов. Истина и ложь обозначаются как 1 и 0 соответственно в следующих таблицах истинности для краткости.

Функциональная полнота

Поскольку функция может быть выражена как композиция , истинностно-функциональному логическому исчислению не нужно иметь выделенные символы для всех вышеупомянутых функций, чтобы быть функционально полным . Это выражается в пропозициональном исчислении как логическая эквивалентность определенных составных утверждений. Например, классическая логика имеет ¬ P  ∨  Q, эквивалентную P  →  Q. Условный оператор "→" поэтому не является необходимым для логической системы на основе классики , если "¬" (не) и "∨" (или) уже используются.

Минимальный набор операторов, который может выразить каждое высказывание, выражаемое в исчислении высказываний, называется минимальным функционально полным набором . Минимально полный набор операторов достигается только с помощью NAND {↑} и NOR {↓}.

Ниже приведены минимальные функционально полные наборы операторов, арность которых не превышает 2: ^[5]

Один элемент

{↑}, {↓}.

Два элемента

${\displaystyle \{\vee ,\neg \}}$, , , , , , , , , , , , , , , , , . ${\displaystyle \{\wedge ,\neg \}}$ ${\displaystyle \{\to ,\neg \}}$ ${\displaystyle \{\gets ,\neg \}}$ ${\displaystyle \{\to ,\bot \}}$ ${\displaystyle \{\gets ,\bot \}}$ ${\displaystyle \{\to ,\nleftrightarrow \}}$ ${\displaystyle \{\gets ,\nleftrightarrow \}}$ ${\displaystyle \{\to ,\nrightarrow \}}$ ${\displaystyle \{\to ,\nleftarrow \}}$ ${\displaystyle \{\gets ,\nrightarrow \}}$ ${\displaystyle \{\gets ,\nleftarrow \}}$ ${\displaystyle \{\nrightarrow ,\neg \}}$ ${\displaystyle \{\nleftarrow ,\neg \}}$ ${\displaystyle \{\nrightarrow ,\top \}}$ ${\displaystyle \{\nleftarrow ,\top \}}$ ${\displaystyle \{\nrightarrow ,\leftrightarrow \}}$ ${\displaystyle \{\nleftarrow ,\leftrightarrow \}}$

Три элемента

${\displaystyle \{\lor ,\leftrightarrow ,\bot \}}$, , , , , . ${\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}$ ${\displaystyle \{\lor ,\nleftrightarrow ,\top \}}$ ${\displaystyle \{\land ,\leftrightarrow ,\bot \}}$ ${\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}$ ${\displaystyle \{\land ,\nleftrightarrow ,\top \}}$

Алгебраические свойства

Некоторые функции истинности обладают свойствами, которые могут быть выражены в теоремах, содержащих соответствующую связку. Некоторые из этих свойств, которые может иметь бинарная функция истинности (или соответствующая логическая связку), следующие:

• Ассоциативность : в выражении, содержащем две или более одинаковых ассоциативных связок подряд, порядок операций не имеет значения, если последовательность операндов не изменяется.
• Коммутативность : операнды связки можно менять местами, не влияя на истинностное значение выражения.
• Дистрибутивность : Связка, обозначенная ·, распределяется по другой связке, обозначенной +, если a · ( b + c ) = ( a · b ) + ( a · c ) для всех операндов a , b , c .
• идемпотентность : Всякий раз, когда операнды операции одинаковы, связка дает операнд в качестве результата. Другими словами, операция является как сохраняющей истину, так и сохраняющей ложь (см. ниже).
• поглощение : Пара связокудовлетворяет закону поглощения, еслидля всех операндов a , b . ${\displaystyle \land ,\lor }$ ${\displaystyle a\land (a\lor b)=a\lor (a\land b)=a}$

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

• монотонный : если f ( a ₁ , ..., an ) ≤ f ( b ₁ , ..., b _n ) для всех _a 1 _, ..., _an , b 1 _, ..., b _n ∈ {0,1} таких, что _a 1 _≤ b ₁ , a 2 _≤ b 2 _, ..., an ≤ b _n . Например,. ${\displaystyle \vee ,\wedge ,\top ,\bot }$
• аффинный : Для каждой переменной изменение ее значения всегда или никогда не изменяет истинностное значение операции для всех фиксированных значений всех других переменных. Например,, . ${\displaystyle \neg ,\leftrightarrow }$ ${\displaystyle \not \leftrightarrow ,\top ,\bot }$
• самодвойственно : чтение значений истинности для операции сверху вниз по ее таблице истинности равносильно выполнению дополнения чтения ее снизу вверх; другими словами, f (¬ a ₁ , ..., ¬ a _n ) = ¬ f ( a ₁ , ..., a _n ). Например, . ${\displaystyle \neg }$
• сохранение истины : интерпретация, при которой всем переменным присваивается значение истинности « истина», в результате этих операций получается значение истинности « истина» . Например, . (см. валидность ) ${\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow ,\subset }$
• сохранение ложности : интерпретация, при которой всем переменным присваивается значение истинности ложь , в результате этих операций получается значение истинности ложь . Например, . (см. валидность ) ${\displaystyle \vee ,\wedge ,\nleftrightarrow ,\bot ,\not \subset ,\not \supset }$

Арити

Конкретная функция может также называться оператором . В двузначной логике есть 2 нуль-арных оператора (константы), 4 унарных оператора , 16 бинарных операторов , 256 тернарных операторов и n -арные операторы. В трехзначной логике есть 3 нуль-арных оператора (константы), 27 унарных операторов , 19683 бинарных оператора , 7625597484987 тернарных операторов и n -арные операторы. В k -значной логике есть k нуль-арных операторов, унарных операторов, бинарных операторов, тернарных операторов и n -арных операторов. n -арный оператор в k -значной логике является функцией из . Следовательно, число таких операторов равно , откуда и были получены приведенные выше числа. ${\displaystyle 2^{2^{n}}}$ ${\displaystyle 3^{3^{n}}}$ ${\displaystyle k^{k}}$ ${\displaystyle k^{k^{2}}}$ ${\displaystyle k^{k^{3}}}$ ${\displaystyle k^{k^{n}}}$ ${\displaystyle \mathbb {Z} _{k}^{n}\to \mathbb {Z} _{k}}$ ${\displaystyle |\mathbb {Z} _{k}|^{|\mathbb {Z} _{k}^{n}|}=k^{k^{n}}}$

Однако некоторые операторы определенной арности на самом деле являются вырожденными формами, которые выполняют операцию с более низкой арностью на некоторых входах и игнорируют остальные входы. Из 256 тернарных булевых операторов, приведенных выше, некоторые из них являются такими вырожденными формами бинарных или операторов с более низкой арностью, использующими принцип включения-исключения . Тернарный оператор — это один из таких операторов, который на самом деле является унарным оператором, примененным к одному входу и игнорирующим два других входа. ${\displaystyle {\binom {3}{2}}\cdot 16-{\binom {3}{1}}\cdot 4+{\binom {3}{0}}\cdot 2}$ ${\displaystyle f(x,y,z)=\lnot x}$

«Не» — это унарный оператор , он принимает один член (¬ P ). Остальные — бинарные операторы , принимающие два члена для создания составного оператора ( P ∧ Q , P ∨ Q , P → Q , P ↔ Q ).

Множество логических операторов Ω можно разбить на непересекающиеся подмножества следующим образом:

${\displaystyle \Omega =\Omega _{0}\cup \Omega _{1}\cup \ldots \cup \Omega _{j}\cup \ldots \cup \Omega _{m}\,.}$

В этом разбиении есть множество символов операторов арности j . ${\displaystyle \Omega _{j}}$

В более привычных исчислениях высказываний обычно разделяется следующим образом: ${\displaystyle \Omega }$

Нулевые операторы: ${\displaystyle \Omega _{0}=\{\bot ,\top \}}$

унарные операторы: ${\displaystyle \Omega _{1}=\{\lnot \}}$

бинарные операторы: ${\displaystyle \Omega _{2}\supset \{\land ,\lor ,\rightarrow ,\leftrightarrow \}}$

Принцип композиционности

Вместо использования таблиц истинности логические соединительные символы могут быть интерпретированы с помощью функции интерпретации и функционально полного набора функций истинности (Gamut 1991), как подробно описано в принципе композиционности смысла. Пусть I будет функцией интерпретации, пусть Φ , Ψ будут любыми двумя предложениями и пусть функция истинности f _nand будет определена как:

• f _nand (T,T) = F; f _nand (T,F) = f _nand (F,T) = f _nand (F,F) = T

Тогда для удобства f _not , f _or f _и т. д. определяются с помощью f _nand :

• f _не ( x ) = f _{не и} ( x , x )
• f _или ( x , y ) = f _и ( f _не ( x ), f _не ( y ))
• f _и ( x , y ) = f _не ( f _{n и} ( x , y ))

или, в качестве альтернативы , f _not , f _или f _и т. д. определяются напрямую:

• f _не (T) = F; f _не (F) = T;
• f _или (T,T) = f _или (T,F) = f _или (F,T) = T; f _или (F,F) = F
• f _и (T,T) = T; f _и (T,F) = f _и (F,T) = f _и (F,F) = F

Затем

• Я (~) = Я ( ) = f _не ${\displaystyle \neg }$
• Я (&) = Я ( ) = ж _и ${\displaystyle \wedge }$
• Я ( v ) = Я ( ) = f _или ${\displaystyle \lor }$
• Я (~ Φ ) = Я ( Φ ) = Я ( )( Я ( Φ )) = f _не ( Я ( Φ )) ${\displaystyle \neg }$ ${\displaystyle \neg }$
• I ( Φ Ψ ) = I ( )( I ( Φ ), I ( Ψ )) = f _и ( I ( Φ ), I ( Ψ )) ${\displaystyle \wedge }$ ${\displaystyle \wedge }$

и т. д.

Таким образом, если S — это предложение, которое является строкой символов, состоящей из логических символов v ₁ ... v _{n ,} представляющих логические связки, и нелогических символов c ₁ ... c _n , то тогда и только тогда, когда I ( v ₁ )... I ( v _n ) были предоставлены для интерпретации v ₁ в v _n с помощью f _nand (или любого другого набора функциональных полных функций истинности), то истинностное значение ⁠ ⁠ ${\displaystyle I(s)}$ полностью определяется истинностными значениями c ₁ ... c _n , т. е. I ( c ₁ )... I ( c _n ) . Другими словами, как и ожидалось и требовалось, S является истинным или ложным только при интерпретации всех его нелогических символов.

Информатика

Логические операторы реализованы как логические вентили в цифровых схемах . Практически все цифровые схемы (главным исключением является DRAM ) построены из NAND , NOR , NOT и вентилей передачи . Вентили NAND и NOR с 3 или более входами вместо обычных 2 входов довольно распространены, хотя они логически эквивалентны каскаду вентилей с 2 ​​входами. Все другие операторы реализованы путем разбиения их на логически эквивалентную комбинацию из 2 или более из указанных выше логических вентилей.

«Логическая эквивалентность» «только NAND», «только NOR» и «NOT и AND» аналогична эквивалентности Тьюринга .

Тот факт, что все функции истинности могут быть выражены только с помощью NOR, продемонстрирован бортовым компьютером миссии «Аполлон» .

Смотрите также

• Философский портал
• Психологический портал

• Бертран Рассел и Альфред Норт Уайтхед ,
  Principia Mathematica , 2-е издание
• Людвиг Витгенштейн ,
  Логико-философский трактат , Положение 5.101.
• Побитовая операция
• Двоичная функция
• Булев домен
• Булева логика
• Булева функция
• Список тем по булевой алгебре
• Логическая константа
• Модальный оператор
• Пропозициональное исчисление
• Истинностно-функциональная пропозициональная логика

Примечания

1. Рой Т. Кук (2009). Словарь философской логики , стр. 294: Функция истины. Издательство Эдинбургского университета.
2. Рой Т. Кук (2009). Словарь философской логики , стр. 295: Функциональная истина. Издательство Эдинбургского университета.
3. Интернет-энциклопедия философии: Пропозициональная логика, Кевин С. Клемент
4. Рой Т. Кук (2009). Словарь философской логики , стр. 47: Классическая логика. Издательство Эдинбургского университета.
5. Верник, Уильям (1942) «Полные наборы логических функций», Труды Американского математического общества 51 : 117–32. В своем списке на последней странице статьи Верник не делает различий между ← и →, или между и . ${\displaystyle \nleftarrow }$ ${\displaystyle \nrightarrow }$

Ссылки

• В данной статье использованы материалы TruthFunction на PlanetMath , лицензированные по лицензии Creative Commons Attribution/Share-Alike License .

Дальнейшее чтение

• Юзеф Мария Бохенский (1959), A Précis of Mathematical Logic , перевод с французской и немецкой версий Отто Берда, Дордрехт, Южная Голландия: D. Reidel.
• Алонзо Чёрч (1944), Введение в математическую логику , Принстон, Нью-Джерси: Princeton University Press. См. Введение для истории концепции истинностной функции.