Функция истины - Truth function

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

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

Обзор

А логическая связка является истинно-функциональным, если истинностное значение составного предложения является функцией истинностного значения его под-предложений. Класс связок является истинно-функциональным, если каждый из его членов. Например, связующее "и"является истинно-функциональным, так как предложение вроде"Яблоки - это фрукты, а морковь - это овощи." правда если и только если каждое из его субпредложений "яблоки фрукты" и "морковь овощи"верно, в противном случае - ложно. Некоторые связки естественного языка, например английского, не являются функциональными по истине.

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

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

правда, пока

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

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

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

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

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

Противоречие /Ложь Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна ${\displaystyle \bot }$ "Нижний" п ∧ ¬п Оpq   Q 0 1 п 0    0   0  1    0   0	Тавтология /Истинный Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна ${\displaystyle \top }$ "верх" п ∨ ¬п Vpq   Q 0 1 п 0    1   1  1    1   1
Предложение п Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна п п яpq   Q 0 1 п 0    0   0  1    1   1	Отрицание п Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна ¬п ~п Nп Fpq   Q 0 1 п 0    1   1  1    0   0
Предложение Q Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна Q q ЧАСpq   Q 0 1 п 0    0   1  1    0   1	Отрицание Q Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна ¬Q ~Q Nq граммpq   Q 0 1 п 0    1   0  1    1   0
Соединение Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна п ∧ Q п & Q п · Q п ИQ п ↛¬Q ¬п ↚ Q ¬п ↓ ¬Q Kpq   Q 0 1 п 0    0   0  1    0   1	Альтернативное отрицание Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна п ↑ Q п | Q п NANDQ п → ¬Q ¬п ← Q ¬п ∨ ¬Q Dpq   Q 0 1 п 0    1   1  1    1   0
Дизъюнкция Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна п ∨ Q п ИЛИ ЖЕQ п ← ¬Q ¬п → Q ¬п ↑ ¬Q ¬(¬п ∧ ¬Q) Аpq   Q 0 1 п 0    0   1  1    1   1	Совместное отрицание Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна п ↓ Q п НИQ п ↚ ¬Q ¬п ↛ Q ¬п ∧ ¬Q Иксpq   Q 0 1 п 0    1   0  1    0   0
Существенное отсутствие импликации Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна п ↛ Q п ${\displaystyle \not \supset }$ Q п ${\displaystyle >}$ Q п ∧ ¬Q ¬п ↓ Q ¬п ↚ ¬Q Lpq   Q 0 1 п 0    0   0  1    1   0	Материальное значение Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна п → Q п ⊃ Q п ${\displaystyle \leq }$ Q п ↑ ¬Q ¬п ∨ Q ¬п ← ¬Q Cpq   Q 0 1 п 0    1   1  1    0   1
Конверс без импликации Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна п ↚ Q п ${\displaystyle \not \subset }$ Q п ${\displaystyle <}$ Q п ↓ ¬Q ¬п ∧ Q ¬п ↛ ¬Q Mpq   Q 0 1 п 0    0   1  1    0   0	Обратное значение Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна п ← Q п ⊂ Q п ${\displaystyle \geq }$ Q п ∨ ¬Q ¬п ↑ Q ¬п → ¬Q Bpq   Q 0 1 п 0    1   0  1    1   1
Исключительная дизъюнкция Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна п ↮ Q п ≢ Q п ⨁ Q п XORQ п ${\displaystyle \leftrightarrow }$ ¬Q ¬п ${\displaystyle \leftrightarrow }$ Q ¬п ↮ ¬Q Jpq   Q 0 1 п 0    0   1  1    1   0	Двусмысленный Обозначение Эквивалент формулы Таблица истинности Диаграмма Венна п ${\displaystyle \leftrightarrow }$ Q п ≡ Q п XNORQ п МКФQ п ↮ ¬Q ¬п ↮ Q ¬п ${\displaystyle \leftrightarrow }$ ¬Q Epq   Q 0 1 п 0    1   0  1    0   1

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

Смотрите также: Функциональная полнота

Поскольку функция может быть выражена как сочинение, логическое исчисление с функцией истинности не должно иметь выделенных символов для всех вышеупомянутых функций, чтобы быть функционально полный. Это выражается в пропозициональное исчисление в качестве логическая эквивалентность некоторых составных утверждений. Например, классическая логика ¬п ∨ Q эквивалентно п → 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 \}}$.

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

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

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

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

• монотонный: Если ж(а₁, ..., а_п) ≤ ж(б₁, ..., б_п) для всех а₁, ..., а_п, б₁, ..., б_п ∈ {0,1} такой, что а₁ ≤ б₁, а₂ ≤ б₂, ..., а_п ≤ б_п. Например., ${\displaystyle \vee ,\wedge ,\top ,\bot }$.
• аффинный: Для каждой переменной изменение ее значения всегда или никогда не изменяет истинностное значение операции для всех фиксированных значений всех других переменных. Например., ${\displaystyle \neg ,\leftrightarrow }$, ${\displaystyle \not \leftrightarrow ,\top ,\bot }$.
• самодвойственный: Чтобы прочитать назначения значений истинности для операции сверху вниз на ее таблица истинности это то же самое, что брать дополнение, читая его снизу вверх; другими словами, ж(¬а₁, ..., ¬а_п) = ¬ж(а₁, ..., а_п). Например., ${\displaystyle \neg }$.
• сохраняющий истину: Интерпретация, согласно которой всем переменным присваивается значение истины of 'true' производит значение истинности 'true' в результате этих операций. Например., ${\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow ,\subset }$. (видеть срок действия )
• сохраняющий ложь: Интерпретация, согласно которой всем переменным присваивается значение истины of 'false' производит значение истинности 'false' в результате этих операций. Например., ${\displaystyle \vee ,\wedge ,\nleftrightarrow ,\bot ,\not \subset ,\not \supset }$. (видеть срок действия )

Arity

Смотрите также: арность

Конкретная функция может также называться оператор. В двузначной логике 2 нулевых оператора (константы), 4 унарные операторы, 16 бинарные операторы, 256 тернарные операторы, и ${\displaystyle 2^{2^{n}}}$ п-арные операторы. В трехзначной логике есть 3 нулевых оператора (константы), 27 унарные операторы, 19683 бинарные операторы, 7625597484987 тернарные операторы, и ${\displaystyle 3^{3^{n}}}$ п-арные операторы. В k-значная логика, есть k нулевые операторы, ${\displaystyle k^{k}}$ унарные операторы, ${\displaystyle k^{k^{2}}}$ бинарные операторы, ${\displaystyle k^{k^{3}}}$ тернарные операторы и ${\displaystyle k^{k^{n}}}$ п-арные операторы. An п-арный оператор в k-значная логика - это функция от ${\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}$ - один из таких операторов, который на самом деле является унарным оператором, применяемым к одному входу и игнорирующим два других входа.

"Нет" это унарный оператор, требуется один член (¬п). Остальные бинарные операторы, взяв два члена, чтобы составить составной оператор (п ∧ Q, п ∨ Q, п → Q, п ↔ Q).

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

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

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

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

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

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

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

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

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

• ж_nand(Т, Т) = F; ж_nand(Т, F) = ж_nand(F, T) = ж_nand(F, F) = T

Затем для удобства ж_нет, ж_{или же} ж_и и т. д. определяются с помощью ж_nand:

• ж_нет(Икс) = ж_nand(Икс,Икс)
• ж_{или же}(Икс,у) = ж_nand(ж_нет(Икс), ж_нет(у))
• ж_и(Икс,у) = ж_нет(ж_nand(Икс,у))

или, альтернативно ж_нет, ж_{или же} ж_и и так далее определяются напрямую:

• ж_нет(Т) = F; ж_нет(F) = Т;
• ж_{или же}(Т, Т) = ж_{или же}(Т, F) = ж_{или же}(F, T) = T; ж_{или же}(F, F) = F
• ж_и(Т, Т) = Т; ж_и(Т, F) = ж_и(F, T) = ж_и(F, F) = F

потом

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

и Т. Д.

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

Информатика

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

«Логическая эквивалентность» «только И-НЕ», «только ИЛИ» и «НЕ и И» аналогична Эквивалентность Тьюринга.

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

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

Бертран Рассел и Альфред Норт Уайтхед, 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.

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

• Юзеф Мария Бохенски (1959), Краткое изложение математической логики, перевод с французской и немецкой версий Отто Берда, Дордрехт, Южная Голландия: D. Reidel.
• Церковь Алонсо (1944), Введение в математическую логику, Принстон, Нью-Джерси: Издательство Принстонского университета. Историю концепции функции истинности см. Во введении.