В логике , А функция истинности [1] является функцией , которая принимает значения истинности в качестве входных данных и производит уникальное значение истинности в качестве вывода. Другими словами: все входные и выходные данные функции истинности являются значениями истинности; функция истинности всегда будет выводить ровно одно значение истинности; и ввод одного и того же значения истинности всегда будет выводить одно и то же значение истинности. Типичный пример - логика высказываний , в которой составное высказывание строится с использованием отдельных высказываний, связанных логическими связками ; если значение истинности составного утверждения полностью определяется значением (ями) истинности составного утверждения (ов), составное утверждение называетсяфункция истины , и любые используемые логические связки считаются функциональными по истине . [2]
Классическая логика высказываний является функциональной логикой истинности [3] в том смысле, что каждое утверждение имеет ровно одно значение истинности, которое является либо истинным, либо ложным, и каждая логическая связка является функциональной истинностью (с соответствующей таблицей истинности ), таким образом, каждое составное утверждение является функция истины. [4] С другой стороны, модальная логика не является истинно-функциональной.
Обзор [ править ]
Логическая связка является истиной-функциональной , если истинное значение составного предложения является функцией истинности значения его суб-предложений. Класс связок является истинно-функциональным, если таковым является каждый из его членов. Например, связка « и » является истинно-функциональной, поскольку предложение типа « Яблоки - это фрукты, а морковь - это овощи » истинно тогда и только тогда, когда каждое из его вложенных предложений « яблоки - фрукты » и « морковь - овощи » верно истина, в противном случае - ложь. Некоторые связки естественного языка, например английского, не являются функциональными по истине.
Связки формы «x считает, что ...» являются типичными примерами связок, которые не являются истинно-функциональными. Если, например, Мэри ошибочно полагает, что Эл Гор был президентом США 20 апреля 2000 г., но она не верит, что луна сделана из зеленого сыра, тогда приговор
- " Мэри считает, что Эл Гор был президентом США 20 апреля 2000 г. "
правда, пока
- « Мэри считает, что луна сделана из зеленого сыра »
ложно. В обоих случаях каждое составное предложение (например, « Эл Гор был президентом США 20 апреля 2000 года » и « луна сделана из зеленого сыра ») ложно, но каждое составное предложение, образованное префиксом фразы « Мэри считает, что "отличается истинной ценностью. То есть истинностное значение предложения формы « Мэри считает, что ... » не определяется исключительно истинностным значением его составного предложения и, следовательно, (унарной) связкой (или просто оператором, поскольку оно унарное ) не является истинно-функциональным.
Класс классических логических связок (например, & , → ), используемых при построении формул, является истинностно-функциональным. Их значения для различных значений истинности в качестве аргумента обычно даются таблицами истинности . Истинно-функциональное исчисление высказываний - это формальная система , формулы которой можно интерпретировать как истинные или ложные.
Таблица двоичных функций истинности [ править ]
В двузначной логики, есть шестнадцать возможных функций истинности, также называемые булевы функции , из двух входов P и Q . Любая из этих функций соответствует таблице истинности определенной логической связки в классической логике, включая несколько вырожденных случаев, таких как функция, не зависящая от одного или обоих своих аргументов. Истина и ложь обозначены как 1 и 0 соответственно в следующих таблицах истинности для краткости.
|
| ||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||
|
|
Функциональная полнота [ править ]
Поскольку функция может быть выражена как композиция , логическое исчисление с функцией истинности не должно иметь выделенных символов для всех вышеупомянутых функций, чтобы быть функционально завершенными . Это выражается в исчислении высказываний как логическая эквивалентность определенных составных утверждений. Например, классическая логика имеет ¬ P ∨ Q , эквивалентное P → Q . Следовательно, условный оператор «→» не является необходимым для классической логической системы, если «¬» (не) и «∨» (или) уже используются.
Минимальный набор операторов , которые могут выразить каждое заявление выразимых в исчислении высказываний называется минимальным функционально полный набор . Минимально полный набор операторов достигается только с помощью NAND {↑} и только NOR {↓}.
Ниже приведены минимальные функционально полные наборы операторов, арности которых не превышают 2: [5]
- Один элемент
- {↑}, {↓}.
- Два элемента
- , , , , , , , , , , , , , , , , , .
- Три элемента
- , , , , , .
Алгебраические свойства [ править ]
Некоторые функции истинности обладают свойствами, которые могут быть выражены в теоремах, содержащих соответствующую связку. Вот некоторые из тех свойств, которыми может обладать двоичная функция истинности (или соответствующая логическая связка):
- ассоциативность : в выражении, содержащем две или более одинаковых ассоциативных связки подряд, порядок операций не имеет значения, пока последовательность операндов не изменяется.
- Коммутативность : операнды связки можно менять местами, не влияя на истинность выражения.
- дистрибутивность : связка, обозначенная ·, распределяется по другой связке, обозначенной +, если 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 .
См. Также [ править ]
|
|
Заметки [ править ]
- ^ Рой Т. Кук (2009). Словарь философской логики , стр. 294: Функция истины. Издательство Эдинбургского университета.
- ^ Рой Т. Кук (2009). Словарь философской логики , стр. 295: Истина Функционал. Издательство Эдинбургского университета.
- ^ Интернет-энциклопедия философии: логика высказываний , Кевин К. Клемент
- ^ Рой Т. Кук (2009). Словарь философской логики , стр. 47: Классическая логика. Издательство Эдинбургского университета.
- ^ Верник, Уильям (1942) "Полные наборы логических функций", Труды Американского математического общества 51 : 117–32. В своем списке на последней странице статьи Верник не делает различий между ← и → или междуи.
Ссылки [ править ]
- Эта статья включает материал из TruthFunction на PlanetMath , который находится под лицензией Creative Commons Attribution / Share-Alike License .
Дальнейшее чтение [ править ]
- Юзеф Мария Бохенский (1959), Краткое изложение математической логики , перевод с французской и немецкой версий Отто Берд, Дордрехт, Южная Голландия: Д. Рейдел.
- Алонзо Черч (1944), Введение в математическую логику , Принстон, Нью-Джерси: Princeton University Press. Историю концепции функции истинности см. Во введении.