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

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

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

Обзор

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

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

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

правда, пока

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

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

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

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

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

Противоречие / ложь
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна

"Нижний"
P ∧ ¬ P
O pq
  Q
0 1
п 0    0   0 
1    0   0 
Venn0000.svg


Тавтология / Истина
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна

"вершина"
P ∨ ¬ P
V pq
  Q
0 1
п 0    1   1 
1    1   1 
Venn1111.svg


Предложение P
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна
п p
I pq
  Q
0 1
п 0    0   0 
1    1   1 
Venn0101.svg


Отрицание P
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна
¬ P
~ P
N p
F pq
  Q
0 1
п 0    1   1 
1    0   0 
Venn1010.svg


Предложение Q
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна
Q q
H pq
  Q
0 1
п 0    0   1 
1    0   1 
Venn0011.svg


Отрицание Q
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна
¬ Q
~ Q
N q
G pq
  Q
0 1
п 0    1   0 
1    1   0 
Venn1100.svg


Соединение
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна
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 
Venn0001.svg


Альтернативное отрицание
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна
P Q
P | Q
P  NAND  Q
P → ¬ Q
¬ P Q
¬ P ∨ ¬ Q
D pq
  Q
0 1
п 0    1   1 
1    1   0 
Venn1110.svg


Дизъюнкция
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна
P Q
P  OR  Q
P ← ¬ Q
¬ P Q
¬ P ↑ ¬ Q
¬ (¬ P ∧ ¬ Q )
A pq
  Q
0 1
п 0    0   1 
1    1   1 
Venn0111.svg


Совместное отрицание
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна
P Q
P  NOR  Q
P ↚ ¬ Q
¬ P Q
¬ P ∧ ¬ Q
X pq
  Q
0 1
п 0    1   0 
1    0   0 
Venn1000.svg


Существенное отсутствие импликации
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна
P Q
P Q P Q
P ∧ ¬ Q
¬ P Q
¬ P ↚ ¬ Q
L pq
  Q
0 1
п 0    0   0 
1    1   0 
Venn0100.svg


Материальное значение
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна
P Q
P Q
P Q
P ↑ ¬ Q
¬ P Q
¬ P ← ¬ Q
C pq
  Q
0 1
п 0    1   1 
1    0   1 
Venn1011.svg


Конверс без импликации
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна
P Q
P Q P Q
P ↓ ¬ Q
¬ P Q
¬ P ↛ ¬ Q
M pq
  Q
0 1
п 0    0   1 
1    0   0 
Venn0010.svg


Обратное значение
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна
P Q
P Q
P Q
P ∨ ¬ Q
¬ P Q
¬ P → ¬ Q
B pq
  Q
0 1
п 0    1   0 
1    1   1 
Venn1101.svg


Исключительная дизъюнкция
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна
P Q
P Q
P Q
P  XOR  Q
П ¬ Q ¬ P Q ¬ P ↮ ¬ Q J pq


  Q
0 1
п 0    0   1 
1    1   0 
Venn0110.svg


Двусмысленный
Обозначение Эквивалентные
формулы
Таблица истинности Диаграмма Венна
P Q PQ P  XNOR  Q P  IFF  Q


P ↮ ¬ Q
¬ P Q
¬ P ¬ Q E pq
  Q
0 1
п 0    1   0 
1    0   1 
Venn1001.svg


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

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

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

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

Один элемент
{↑}, {↓}.
Два элемента
, , , , , , , , , , , , , , , , , .
Три элемента
, , , , , .

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

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

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

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

  • монотонный : если f ( a 1 , ..., a n ) ≤ f ( b 1 , ..., b n ) для всех a 1 , ..., a n , b 1 , ..., b n ∈ {0,1} такие, что a 1 b 1 , a 2 b 2 , ..., a n b n . Например, .
  • affine : для каждой переменной изменение ее значения всегда или никогда не изменяет истинностное значение операции для всех фиксированных значений всех других переменных. Например, , .
  • самодвойственный : читать назначения значений истинности для операции сверху вниз в ее таблице истинности - то же самое, что читать ее снизу вверх; другими словами, f a 1 , ..., ¬ a n ) = ¬ f ( a 1 , ..., a n ). Например, .
  • сохранение истины : интерпретация, при которой всем переменным присваивается значение истинности «истина», в результате этих операций дает значение истинности «истина». Например, . (см. срок действия )
  • сохранение ложности : интерпретация, при которой всем переменным присваивается значение истинности «ложь», в результате этих операций дает значение истинности «ложь». Например, . (см. срок действия )

Артистия

Конкретная функция также может называться оператором . В двузначной логике есть 2 нулевых оператора (константы), 4 унарных оператора , 16 бинарных операторов , 256 тернарных операторов и n -арные операторы. В трехзначной логике есть 3 нулевых оператора (константы), 27 унарных операторов , 19683 бинарных оператора , 7625597484987 тернарных операторов и n -арные операторы. В k -значной логике есть k нулевых операторов, унарных операторов, бинарных операторов, тернарных операторов и n -арных операторов. П -ичный оператор в к - значной логики является функцией от . Следовательно, количество таких операторов равно , как и были получены указанные выше числа.

Однако некоторые из операторов определенной арности на самом деле являются вырожденными формами, которые выполняют операцию меньшей арности на некоторых входных данных и игнорируют остальные входные данные. Из 256 троичных булевых операторов, процитированных выше, это такие вырожденные формы бинарных операторов или операторов меньшей арности, использующие принцип включения-исключения . Тернарный оператор - один из таких операторов, который на самом деле является унарным оператором, применяемым к одному входу и игнорирующим два других входа.

«Не» - унарный оператор , он принимает один член (¬ P ). Остальные - бинарные операторы , в которых два члена образуют составное утверждение ( P Q , P Q , P Q , P Q ).

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

В этом разбиении - множество операторных символов арности j .

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

нулевые операторы:
унарные операторы:
бинарные операторы:

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

Вместо использования таблиц истинности логические соединительные символы можно интерпретировать с помощью функции интерпретации и функционально полного набора функций истинности (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

потом

  • I (~) = I ( ) = f не
  • I (&) = I ( ) = f и
  • I ( v ) = I ( ) = f или
  • I (~ Φ ) = I ( Φ ) = I ( ) ( I ( Φ )) = f not ( I ( Φ ))
  • I ( Φ Ψ ) = I ( · ) ( I ( Φ ), I ( Ψ )) = f и ( I ( Φ ), I ( Ψ ))

и т.п.

Таким образом, если S - предложение, которое представляет собой строку символов, состоящую из логических символов v 1 ... v n, представляющих логические связки, и нелогических символов c 1 ... c n , то тогда и только тогда, когда I ( v 1 ) ... I ( v n ) была предоставлена ​​интерпретация v 1 в v n с помощью f nand (или любого другого набора функциональных полных функций истинности), тогда значение истинности полностью определяется значениями истинности c 1 ... c n , то есть I ( c 1 ) ... I ( c n ) . Другими словами, как ожидалось и требовалось, S истинно или ложно только при интерпретации всех его нелогических символов.

Информатика

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

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

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

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

Заметки

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

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

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