Функция истины - 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 { клин, neg }}$, ${ Displaystyle { к, neg }}$, ${ Displaystyle { получает, neg }}$, ${ displaystyle { to, bot }}$, ${ Displaystyle { получает, бот }}$, ${ displaystyle { to, nleftrightarrow }}$, ${ displaystyle { gets, nleftrightarrow }}$, ${ displaystyle { to, nrightarrow }}$, ${ displaystyle { to, nleftarrow }}$, ${ Displaystyle { получает, nrightarrow }}$, ${ Displaystyle { получает, 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 { земля, leftrightarrow, bot }}$, ${ Displaystyle { земля, leftrightarrow, nleftrightarrow }}$, ${ displaystyle { land, nleftrightarrow, top }}$.

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

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

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

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

• монотонный: Если ж(а₁, ..., а_п) ≤ ж(б₁, ..., б_п) для всех а₁, ..., а_п, б₁, ..., б_п ∈ {0,1} такой, что а₁ ≤ б₁, а₂ ≤ б₂, ..., а_п ≤ б_п. Например., ${ displaystyle vee, wedge, top, bot}$.
• аффинный: Для каждой переменной изменение ее значения всегда или никогда не изменяет истинностное значение операции для всех фиксированных значений всех других переменных. Например., ${ displaystyle neg, leftrightarrow}$, ${ displaystyle not leftrightarrow, top, bot}$.
• самодвойственный: Чтобы прочитать назначения значений истинности для операции сверху вниз на ее таблица истинности это то же самое, что брать дополнение, читая его снизу вверх; другими словами, ж(¬а₁, ..., ¬а_п) = ¬ж(а₁, ..., а_п). Например., ${ displaystyle neg}$.
• сохраняющий истину: Интерпретация, согласно которой всем переменным присваивается значение истины of 'true' производит значение истинности 'true' в результате этих операций. Например., ${ Displaystyle Vee, клин, вверх, rightarrow, leftrightarrow, subset}$. (видеть срок действия )
• сохраняющий ложь: Интерпретация, согласно которой всем переменным присваивается значение истины of 'false' производит значение истинности 'false' в результате этих операций. Например., ${ displaystyle vee, клин, 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 к ^ {к}}$ унарные операторы, ${ Displaystyle к ^ {к ^ {2}}}$ бинарные операторы, ${ Displaystyle к ^ {к ^ {3}}}$ тернарные операторы и ${ Displaystyle к ^ {к ^ {п}}}$ п-арные операторы. 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 е (х, у, z) = lnot х}$ - один из таких операторов, который на самом деле является унарным оператором, применяемым к одному входу и игнорирующим два других входа.

"Нет" это унарный оператор, требуется один член (¬п). Остальные бинарные операторы, взяв два члена, чтобы составить составной оператор (п ∧ 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} substeq { 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

потом

и Т. Д.

Таким образом, если 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.

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

Примечания

Рекомендации

• Эта статья включает материалы TruthFunction о PlanetMath, который находится под лицензией Лицензия Creative Commons Attribution / Share-Alike.

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

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