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

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

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

Обзор

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

Связки формы «х считает, что ...» являются типичными примерами связок, не являющихся истинностными. Если, например, Мэри ошибочно полагает, что Эл Гор был президентом США 20 апреля 2000 г., но она не верит, что Луна сделана из зеленого сыра, тогда предложение

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

это правда, пока

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

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

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

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

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

Противоречие / Ложь Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей $\bot$ "нижний" П ∧ ¬ П О пк   вопрос 0 1 П 0    0   0  1    0   0	Тавтология / Правда Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей $\top$ "вершина" П ∨ ¬ П В пк   вопрос 0 1 П 0    1   1  1    1   1
Предложение П Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей П п я потому что   вопрос 0 1 П 0    0   0  1    1   1	Отрицание буквы П Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей ¬ P ~ П NНапример F pq   вопрос 0 1 П 0    1   1  1    0   0
Предложение Q Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей вопрос д HHPQ   вопрос 0 1 П 0    0   1  1    0   1	Отрицание Q Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей ¬ Q ~ Вопрос Н q Г пк   вопрос 0 1 П 0    1   0  1    1   0
Соединение Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей П ∧ Q П & В П   ·   К П И В П ↛¬ Q ¬ П ↚ К ¬ P ↓ ¬ Q К пк   вопрос 0 1 П 0    0   0  1    0   1	Несоединение/Альтернативное отрицание Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей П ↑ К П | вопрос П- НЕ- Q П → ¬ Q ¬ П ← Q ¬ P ∨ ¬ Q Д пк   вопрос 0 1 П 0    1   1  1    1   0
Дизъюнкция Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей П ∨ Q П ИЛИ В П ← ¬ Q ¬ П → К ¬ P ↑ ¬ Q ¬(¬ P ∧ ¬ Q ) ПК ​   вопрос 0 1 П 0    0   1  1    1   1	Нерасхождение/совместное отрицание Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей П ↓ К П НО К П ↚ ¬ Q ¬ П ↛ К ¬ P ∧ ¬ Q XХ   вопрос 0 1 П 0    1   0  1    0   0
Материальная непричастность Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей П ↛ К П $\not \supset$ вопрос П $>$ вопрос P ПРОСТОЙ Q П ∧ ¬ Q ¬ П ↓ К ¬ P ↚ ¬ Q л пк   вопрос 0 1 П 0    0   0  1    1   0	Материальное значение Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей П → К П ⊃ Q П $\leq$ вопрос P ПОДРАЗУМЕВАЕТ Q П ↑ ¬ Q ¬ П ∨ Q ¬ P ← ¬ Q C pq   вопрос 0 1 П 0    1   1  1    0   1
Обратная неимпликация Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей П ↚ К П $\not \subset$ вопрос П $<$ вопрос П ↓ ¬ Q ¬ П ∧ Q ¬ P ↛ ¬ Q М пк   вопрос 0 1 П 0    0   1  1    0   0	Обратная импликация Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей П ← К П ⊂ Q П $\geq$ вопрос П ∨ ¬ Q ¬ П ↑ Q ¬ P → ¬ Q Б пк   вопрос 0 1 П 0    1   0  1    1   1
Неэквивалентность/исключительная дизъюнкция Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей П ↮ К П ≢ К П ⨁ Q П Исключающее ИЛИ Q П $\leftrightarrow$ ¬ Q ¬ P $\leftrightarrow$ вопрос ¬ P ↮ ¬ Q J- цепочка   вопрос 0 1 П 0    0   1  1    1   0	Эквивалентность/Биусловие Обозначения Эквивалент формулы Таблица истинности Диаграмма друзей П $\leftrightarrow$ вопрос П ≡ Q P XNOR Q П МКФ Q П ↮ ¬ Q ¬ П ↮ К ¬ P $\leftrightarrow$ ¬ Q E pq   вопрос 0 1 П 0    1   0  1    0   1

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

Основная статья: Функциональная полнота

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

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

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

Один элемент

{↑}, {↓}.

Два элемента

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

Три элемента

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

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

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

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

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

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

Арити

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

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

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

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

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

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

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

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

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

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

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

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

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

• f _и (Т,Т) = F; f _nand (T,F) = f _nand (F,T) = f _nand (F,F) = T

Тогда для удобства f _not , f _или f _и т. д. определяются посредством f _{n и} :

• ж _не ( Икс ) знак _{равно ж и} ( Икс , Икс )
• f _или ( x , y ) = f _nи ( f _не ( x ), f _не ( y ))
• е _и ( Икс , y ) знак равно _{е не} ( е _и ( Икс , y ))

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

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

Затем

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

и т. д.

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

Информатика

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

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

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

См. также

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

Ссылки

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

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

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