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

Функция в классической логике

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

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

Обзор

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

Связки формы «х считает, что ...» являются типичными примерами связок, не являющихся истинностными. Если, например, Мэри ошибочно полагает, что Эл Гор был президентом США 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 ₁ , ..., a _n ) ≤ f ( b ₁ , ..., b _n ) для всех a ₁ , ..., a _n , b ₁ , ..., b _n ∈ {0,1} такой, что a ₁ ≤ b ₁ , a ₂ ≤ b ₂ , ..., a _n ≤ b _n . Например,. ${\displaystyle \vee ,\wedge ,\top ,\bot }$
• affine : для каждой переменной изменение ее значения всегда или никогда не меняет истинное значение операции для всех фиксированных значений всех других переменных. Например,, . ${\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}$

«Not» — унарный оператор , он принимает один термин (¬ 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 _{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 ))
• f _и ( x , y ) = f _not ( f _nand ( x , 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

Затем

• I (~) = I ( ) = f _не ${\displaystyle \neg }$
• I (&) = I ( ) = f _и ${\displaystyle \wedge }$
• я ( v ) = я ( ) = ж _или ${\displaystyle \lor }$
• я (~ Φ ) знак равно я ( Φ ) знак равно я ( )( я ( Φ )) знак равно ж _не ( I ( Φ )) ${\displaystyle \neg }$ ${\displaystyle \neg }$
• я ( Φ Ψ ) знак равно я ( )( я ( Φ ), я ( Ψ )) = f _и ( я ( Φ ), я ( Ψ )) ${\displaystyle \wedge }$ ${\displaystyle \wedge }$

и т. д.

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

Информатика

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

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

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