Логическая связка - Logical connective

Диаграмма Хассе логических связок.

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

Общие связки включают отрицание , дизъюнкцию , союз и импликацию . В стандартных системах классической логики эти связки интерпретируются как функции истинности , хотя они получают множество альтернативных интерпретаций в неклассической логике . Их классические интерпретации аналогичны значениям выражений естественного языка, таких как английское «не», «или», «и», и «если», но не идентичны. Расхождения между связками естественного языка и связками классической логики мотивировали неклассические подходы к значению естественного языка, а также подходы, сочетающие классическую композиционную семантику с устойчивой прагматикой .

Логическая связка похожа, но не эквивалентна синтаксису, обычно используемому в языках программирования, называемому условным оператором .

Обзор

В формальных языках функции истинности представлены однозначными символами. Это позволяет избежать неоднозначного понимания логических утверждений. Эти символы называются логическими связками , логические операторы , пропозициональные операторы , или, в классической логике , истинности функциональных связок . Чтобы узнать о правилах, которые позволяют создавать новые правильно сформированные формулы путем соединения других хорошо сформированных формул с использованием связок, функционирующих на основе истинности, см. Правильно сформированные формулы .

Логические связки могут использоваться для связывания более двух операторов, поэтому можно говорить о n- мерной логической связке .

Общие логические связки

Символ, имя
Таблица истинности
Диаграмма Венна
Нулевые связки (константы)
Правда / тавтология 1 Красная площадь.svg
Ложь / противоречие 0 Пустой квадрат.svg
Унарные связки
P  = 0 1
Предложение P 0 1 Venn01.svg
¬ Отрицание 1 0 Venn10.svg
Бинарные связки
P  = 0 1
Q  = 0 1 0 1
Предложение P 0 0 1 1 Venn0101.svg
Предложение Q 0 1 0 1 Venn0011.svg
Соединение 0 0 0 1 Venn0001.svg
Альтернативное отрицание 1 1 1 0 Venn1110.svg
Дизъюнкция 0 1 1 1 Venn0111.svg
Совместное отрицание 1 0 0 0 Venn1000.svg
Материал условный 1 1 0 1 Venn1011.svg
Эксклюзивный или 0 1 1 0 Venn0110.svg
Двусмысленный 1 0 0 1 Venn1001.svg
Обратное значение 1 0 1 1 Venn1101.svg
Больше информации

Список общих логических связок

Обычно используемые логические связки включают:

Альтернативные имена для двусмысленных выражений - iff , xnor и двузначный вывод .

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

  • Это не дождь ( P )
  • Идет дождь, а я в помещении ( )
  • Идет дождь или я в помещении ( )
  • Если идет дождь, то я в помещении ( )
  • Если я в помещении, значит идет дождь ( )
  • Я нахожусь в помещении тогда и только тогда, когда идет дождь ( )

Также принято считать, что всегда истинная формула и всегда ложная формула являются связными:

История обозначений

  • Отрицание: символ ¬ появился у Гейтинга в 1929 году (сравните с символом Фреге ⫟ в его Begriffsschrift ); символ ~ появился у Рассела в 1908 году; альтернативное обозначение - добавить горизонтальную черту поверх формулы, как в ; другое альтернативное обозначение - использовать символ штриха, как в P '.
  • Соединение: символ ∧ появился у Гейтинга в 1929 году (сравните с использованием Пеано теоретико-множественной записи пересечения ); символ & появился, по крайней мере, в Шенфинкеле в 1924 году; символ . происходит из интерпретации Буля логики как элементарной алгебры .
  • Дизъюнкция: символ ∨ появился у Рассела в 1908 году (сравните с использованием Пеано теоретико-множественной записи объединения ); символ + также используется, несмотря на двусмысленность, проистекающую из того факта, что + обычной элементарной алгебры является исключающим или при логической интерпретации в двухэлементном кольце ; точно в истории знак + вместе с точкой в ​​правом нижнем углу использовался Пирсом ,
  • Следствие: символ → можно увидеть у Гильберта в 1917 году; ⊃ использовался Расселом в 1908 году (сравните с перевернутой нотацией C Пеано); ⇒ использовался в Vax.
  • Двикондиционный: символ ≡ использовался, по крайней мере, Расселом в 1908 году; ↔ использовался по крайней мере Тарским в 1940 году; ⇔ использовалось в Vax; другие символы появились пунктуально в истории, такие как ⊃⊂ в Генцене , \ в Schönfinkel или ⊂⊃ в Chazal.
  • Верно: символ 1 происходит из интерпретации логики Буля как элементарной алгебры над двухэлементной булевой алгеброй ; другие обозначения включают (можно найти в Пеано).
  • Ложь: символ 0 также происходит из интерпретации логики Буля как кольца; другие обозначения включают (можно найти в Пеано).

Некоторые авторы когда-то использовали буквы для связок: u. для соединения (немецкий "und" для "и") и о. для дизъюнкции (немецкая «oder» для «или») в более ранних работах Гильберта (1904); N p для отрицания, K pq для конъюнкции, D pq для альтернативного отрицания, A pq для дизъюнкции, X pq для совместного отрицания, C pq для импликации, E pq для двусмысленного выражения у Лукасевича (1929); ср. Польская нотация .

Резервирование

Такая логическая связка, как обратная импликация «←», на самом деле то же самое, что и материальное условие с переставленными аргументами; таким образом, символ обратной импликации избыточен. В некоторых логических исчислениях (особенно в классической логике ) некоторые существенно различные составные утверждения логически эквивалентны . Менее тривиальным примером избыточности является классическая эквивалентность между ¬ P  ∨  Q и P  →  Q . Следовательно, классическая логическая система не нуждается в условном операторе «→», если «¬» (не) и «∨» (или) уже используются, или может использовать «→» только как синтаксический сахар для соединение, имеющее одно отрицание и одну дизъюнкцию.

Существует шестнадцать булевых функций, связывающих входные значения истинности P и Q с четырехзначными двоичными выходными данными. Они соответствуют возможному выбору двоичных логических связок для классической логики . Различные реализации классической логики могут выбирать различные функционально полные подмножества связок.

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

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

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

Однако с интуиционистской логикой ситуация сложнее . Из его пяти связок, {∧, ∨, →, ¬, ⊥}, только отрицание «¬» может быть сведено к другим связкам (см. Ложь (логика) § Ложь, отрицание и противоречие ). Ни соединение, ни дизъюнкция, ни материальное условное выражение не имеют эквивалентной формы, построенной из других четырех логических связок.

Естественный язык

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

Значения связок естественного языка не совсем идентичны их ближайшим эквивалентам в классической логике. В частности, дизъюнкция может получить исключительную интерпретацию на многих языках. Некоторые исследователи приняли этот факт как доказательство того, что естественный язык семантика является неклассической . Однако другие поддерживают классическую семантику, постулируя прагматические объяснения исключительности, которые создают иллюзию неклассичности. В таких случаях исключительность обычно рассматривается как скалярная импликатура . Связанные головоломки, включающие дизъюнкцию, включают в себя выводы свободного выбора , ограничение Херфорда и вклад дизъюнкции в альтернативные вопросы .

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

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

Английское слово Соединительный Условное обозначение Логические ворота
нет отрицание "¬" НЕТ
а также соединение "∧" А ТАКЖЕ
или дизъюнкция "∨" ИЛИ
если ... то материальное значение «→» ПОДРАЗУМЕВАТЬ
...если обратное следствие «←»
если и только если двусмысленный "↔" XNOR
не оба альтернативное отрицание «↑» NAND
ни ни совместное отрицание «↓» НИ
но нет материальное непонимание "↛" ПРОСТО

Характеристики

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

Ассоциативность
В выражении, содержащем две или более одинаковых ассоциативных связки подряд, порядок операций не имеет значения, пока последовательность операндов не изменяется.
Коммутативность
Операнды связки можно поменять местами, сохраняя логическую эквивалентность исходному выражению.
Распределительность
Связка, обозначенная ·, распределяется по другой связке, обозначенной как +, если 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 1b 1 , a 2b 2 , ..., a nb n . Например, ∨, ∧, ⊤, ⊥.
Близость
Каждая переменная всегда имеет значение для истинности операции или никогда не имеет значения. Например, ¬, ↔`` ⊤, ⊥.
Двойственность
Прочитать присвоение значений истинности для операции сверху вниз по ее таблице истинности - это то же самое, что выполнить дополнение к чтению таблицы той же или другой связки снизу вверх. Не прибегая к таблицам истинности, его можно сформулировать как a 1 , ..., ¬ a n ) = ¬ g ( a 1 , ..., a n ) . Например, ¬.
Сохраняющий правду
Составной частью всех этих аргументов являются тавтология - это сама тавтология. Например, ∨, ∧, ⊤, →, ↔, ⊂ (см. Справедливость ).
Сохранение лжи
Все эти аргументы состоят в противоречиях, и это противоречие само по себе. Например, ∨, ∧`` ⊥, ⊄, ⊅ (см. Справедливость ).
Инволютивность (для унарных связок)
е ( е ( а )) = а . Например, отрицание в классической логике.

Для классической и интуиционистской логики символ «=» означает, что соответствующие импликации «... → ...» и «... ← ...» для логических соединений могут быть доказаны как теоремы, так и символ «≤». означает, что «... → ...» для логических соединений является следствием соответствующих связок «... → ...» для пропозициональных переменных. Некоторые многозначные логики могут иметь несовместимые определения эквивалентности и порядка (следствия).

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

В классической логике и некоторых разновидностях многозначной логики конъюнкция и дизъюнкция двойственны, а отрицание самодвойственно, последнее также самодвойственно в интуиционистской логике.

Порядок старшинства

Чтобы уменьшить количество необходимых скобок, можно ввести правила приоритета : ¬ имеет более высокий приоритет, чем ∧, ∧ выше, чем ∨, и ∨ выше, чем →. Так, например, это сокращение от .

Вот таблица, которая показывает обычно используемый приоритет логических операторов.

Однако не все компиляторы используют один и тот же порядок; например, также использовался порядок, в котором дизъюнкция имеет более низкий приоритет, чем импликация или двойная импликация. Иногда приоритет между соединением и дизъюнкцией не указан, и требуется указать его явно в данной формуле в круглых скобках. Порядок приоритета определяет, какая связка является «основной связкой» при интерпретации неатомарной формулы.

Информатика

Функциональный подход к логическим операторам реализован в виде логических вентилей в цифровых схемах . Практически все цифровые схемы (главным исключением является DRAM ) построены из NAND , NOR , NOT и шлюзов передачи ; см. дополнительные сведения в разделе « Функция истины в информатике» . Логические операторы над битовыми векторами (соответствующие конечным булевым алгебрам ) являются побитовыми операциями .

Но не каждое использование логической связки в компьютерном программировании имеет булеву семантику. Например, ленивое вычисление иногда реализуется для P  ∧  Q и P  ∨  Q , поэтому эти связки не коммутативны, если одно или оба выражения P , Q имеют побочные эффекты . Кроме того, условное выражение , которое в некотором смысле соответствует материальной условной связке, по существу не является логическим, потому что для if (P) then Q;, консеквент Q не выполняется, если антецедент  P является ложным (хотя соединение в целом является успешным ≈ "истина" в такой случай). Это ближе к интуиционистским и конструктивистским взглядам на материальные условности, а не к взглядам классической логики.

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

Примечания

использованная литература

Источники

внешние ссылки