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

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

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

Обзор [ править ]

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

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

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

правда, пока

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

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

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

Таблица двоичных функций истинности [ править ]

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

Противоречие / ложь Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна ${\ displaystyle \ bot}$ "Нижний" P ∧ ¬ P O pq   Q 0 1 п 0    0   0  1    0   0	Тавтология / Истина Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна ${\ displaystyle \ top}$ "верх" P ∨ ¬ P V pq   Q 0 1 п 0    1   1  1    1   1
Предложение P Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна п p I pq   Q 0 1 п 0    0   0  1    1   1	Отрицание P Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна ¬ P ~ P N p F pq   Q 0 1 п 0    1   1  1    0   0
Предложение Q Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна Q q H pq   Q 0 1 п 0    0   1  1    0   1	Отрицание Q Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна ¬ Q ~ Q N q G pq   Q 0 1 п 0    1   0  1    1   0
Соединение Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна P ∧ Q P & Q P  ·  Q P  AND  Q P ↛¬ Q ¬ P ↚ Q ¬ P ↓ ¬ Q K pq   Q 0 1 п 0    0   0  1    0   1	Альтернативное отрицание Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна P ↑ Q P | Q P  NAND  Q P → ¬ Q ¬ P ← Q ¬ P ∨ ¬ Q D pq   Q 0 1 п 0    1   1  1    1   0
Дизъюнкция Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна P ∨ Q P  OR  Q P ← ¬ Q ¬ P → Q ¬ P ↑ ¬ Q ¬ (¬ P ∧ ¬ Q ) A pq   Q 0 1 п 0    0   1  1    1   1	Совместное отрицание Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна P ↓ Q P  NOR  Q P ↚ ¬ Q ¬ P ↛ Q ¬ P ∧ ¬ Q X pq   Q 0 1 п 0    1   0  1    0   0
Существенное отсутствие импликации Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна P ↛ Q P Q P Q${\ Displaystyle \ not \ supset}$ ${\ displaystyle>}$ P ∧ ¬ Q ¬ P ↓ Q ¬ P ↚ ¬ Q L pq   Q 0 1 п 0    0   0  1    1   0	Материальное значение Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна P → Q P ⊃ Q P Q${\ displaystyle \ leq}$ P ↑ ¬ Q ¬ P ∨ Q ¬ P ← ¬ Q C pq   Q 0 1 п 0    1   1  1    0   1
Конверс без импликации Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна P ↚ Q P Q P Q${\ displaystyle \ not \ subset}$ ${\ displaystyle <}$ P ↓ ¬ Q ¬ P ∧ Q ¬ P ↛ ¬ Q M pq   Q 0 1 п 0    0   1  1    0   0	Обратное значение Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна P ← Q P ⊂ Q P Q${\ displaystyle \ geq}$ P ∨ ¬ Q ¬ P ↑ Q ¬ P → ¬ Q B pq   Q 0 1 п 0    1   0  1    1   1
Исключительная дизъюнкция Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна P ↮ Q P ≢ Q P ⨁ Q P  XOR  Q P ¬ Q ¬ P Q ¬ P ↮ ¬ Q J pq${\ displaystyle \ leftrightarrow}$ ${\ displaystyle \ leftrightarrow}$   Q 0 1 п 0    0   1  1    1   0	Двусмысленный Обозначение Эквивалентные формулы Таблица истинности Диаграмма Венна P Q P ≡ Q P  XNOR  Q P  IFF  Q${\ displaystyle \ leftrightarrow}$ P ↮ ¬ Q ¬ P ↮ Q ¬ P ¬ Q E pq${\ displaystyle \ leftrightarrow}$   Q 0 1 п 0    1   0  1    0   1

Функциональная полнота [ править ]

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

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

• монотонный : если 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${\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}\subseteq \{\land ,\lor ,\rightarrow ,\leftrightarrow \}}$

Принцип композиционности [ править ]

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

• f _{n и} (T, T) = F; f _{n и} (T, F) = f _{n и} (F, T) = f _{n и} (F, F) = T

Тогда для удобства е _не , е _или е _и и так далее определяются с помощью ф _NAND :

• f _not ( x ) = f _{n и} ( x , x )
• f _или ( x , y ) = f _{n и} ( f _not ( x ), f _not ( y ))
• f _и ( x , y ) = f _not ( f _nand ( x , y ))

или, в качестве альтернативы F _не , F _или F , _и и так далее определяются непосредственно:

• f _not (T) = F; f _not (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

потом

и Т. Д.

Таким образом, если 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 или более вышеуказанных логических вентилей.

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

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

См. Также [ править ]

Примечания [ править ]

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

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