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


Из Википедии, свободной энциклопедии

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

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

обзор

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

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

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

Правда, пока

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

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

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

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

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

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

"низ"
Р ∧ ¬ Р
О рд
  Q
0 1
п 0    0   0 
1    0   0 
Venn0000.svg


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

"Топ"
P ∨ ¬ Р
В рд
  Q
0 1
п 0    1   1 
1    1   1 
Venn1111.svg


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


Отрицание P
нотация Эквивалентные
формулы
таблица истинности Диаграмма Венна
¬ P
~ P
Н р
Р рд
  Q
0 1
п 0    1   1 
1    0   0 
Venn1010.svg


Предложение Q
нотация Эквивалентные
формулы
таблица истинности Диаграмма Венна
Q д
Н рд
  Q
0 1
п 0    0   1 
1    0   1 
Venn0011.svg


Отрицание Q
нотация Эквивалентные
формулы
таблица истинности Диаграмма Венна
¬ Q
~ Q
Н д
С рд
  Q
0 1
п 0    1   0 
1    1   0 
Venn1100.svg


конъюнкция
нотация Эквивалентные
формулы
таблица истинности Диаграмма Венна
PQ
P & Q
P  ·  Q
Р  и  Q
Р ↛¬ Q
¬ РВ
¬ Р ↓ ¬ Q
К рд
  Q
0 1
п 0    0   0 
1    0   1 
Venn0001.svg


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


дизъюнкция
нотация Эквивалентные
формулы
таблица истинности Диаграмма Венна
РQ
Р  ИЛИ  Q
Р ← ¬ Q
¬ PQ
¬ P ↑ ¬ Q
¬ (¬ P ∧ ¬ Q ) рд
  Q
0 1
п 0    0   1 
1    1   1 
Venn0111.svg


Совместное отрицание
нотация Эквивалентные
формулы
таблица истинности Диаграмма Венна
РВ
Р -  НЕ  Q
Р ↚ ¬ Q
¬ РВ
¬ Р ∧ ¬ Вопрос
Х рд
  Q
0 1
п 0    1   0 
1    0   0 
Venn1000.svg


Материал nonimplication
нотация Эквивалентные
формулы
таблица истинности Диаграмма Венна
РQ
Р Q
Р ∧ ¬ Q
¬ PQ
¬ Р ↚ ¬ Q
л рд
  Q
0 1
п 0    0   0 
1    1   0 
Venn0100.svg


Материальная импликация
нотация Эквивалентные
формулы
таблица истинности Диаграмма Венна
РВ
РQ
P ↑ ¬ Q
¬ PQ
¬ Р ← ¬ В
С рд
  Q
0 1
п 0    1   1 
1    0   1 
Venn1011.svg


Converse nonimplication
нотация Эквивалентные
формулы
таблица истинности Диаграмма Венна
РQ
Р Q
Р ↓ ¬ Q
¬ PQ
¬ Р ↛ ¬ Вопрос
М рд
  Q
0 1
п 0    0   1 
1    0   0 
Venn0010.svg


Converse подразумевается
нотация Эквивалентные
формулы
таблица истинности Диаграмма Венна
РQ
PQ
P ∨ ¬ Q
¬ PQ
¬ P → ¬ В
В рд
  Q
0 1
п 0    1   0 
1    1   1 
Venn1101.svg


Эксклюзивные дизъюнкции
нотация Эквивалентные
формулы
таблица истинности Диаграмма Венна
РQ
РQ
РQ
Р  исключающее  ИЛИ Q
Р ¬ Q ¬ Р В ¬ Р ↮ ¬ Q J рд


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


Biconditional
нотация Эквивалентные
формулы
таблица истинности Диаграмма Венна
P Q PQ P  XNOR  Q P  IFF  Q


Р ↮ ¬ Q
¬ РВ
¬ Р ¬ В Е рд
  Q
0 1
п 0    1   0 
1    0   1 
Venn1001.svg


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

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

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

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

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

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

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

  • ассоциативность :пределах выражениясодержащего два или более одинаковых ассоциативных связок в ряд, порядок операций не имеет значениятех поркак последовательность операндов не изменяется.
  • коммутативности : Операнды соединительного могут быть заменены без влияния на значениях истинности выражения.
  • Дистрибутивность : соединительнотканный обозначается · распределяет над другой связкойобозначенной +, если· ( Ь + с ) = (· б ) + (· с ) для всех операндов а , б , гр .
  • идемпотентность : Всякий разкогда операнды операции такие же, соединительно дает операндкачестве результата. Другими словами, операция является как истина сохраняющих и ложьсохраняющих (смотри ниже).
  • поглощения : Пара связокудовлетворяет закон поглощенияеслидля всех операндов а , б .

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

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

Arity

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

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

«Не» является унарный оператор , он принимает один член (¬ P ). Остальные бинарные операторы , принимающие два члена , чтобы сделать составной оператор ( РQ , PQ , PQ , PQ ).

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

В этом разделе, есть множество операторных символов валентность J .

В более привычных пропозициональных конкрементах, обычно разделен следующим образом :

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

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

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

  • е NAND (Т, Т) = Р; е NAND (T, F) = F NAND (Р, Т) = ф NAND (F, F) = Т

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

  • е не ( х ) = е NAND ( х , х )
  • е или ( х , у ) = е NAND ( е не ( х ), е не ( у ))
  • е и ( х , у ) = е не ( е NAND ( х , у ))

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

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

затем

  • Я (~) = I ( ) = е не
  • Я (&) = Я ( ) = е и
  • Я ( v ) = I ( ) = F или
  • Я (~ Φ ) = I ( Φ ) = I ( ) ( I ( Φ )) = е не ( я ( Φ ))
  • Я ( Ф Ч ) = I ( ) ( Я ( Ф ), я ( Ч )) = F и ( я ( Ф ), я ( Ч ))

и т.п.

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

Информатика

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

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

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

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

Заметки

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

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

  • Бохеньский (1959), конспект математической логики , в переводе с французского и немецкого версии Отто Bird, Дордрехт, Южная Голландия: Д. Reidel.
  • Алонзо Чёрч (1944), Введение в математическую логику , Princeton, NJ: Princeton University Press. Обратитесь к Введению к истории понятия функции истины.