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

Символ, соединяющий смысловые формулы в логике

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

В логике логическая связка (также называемая логическим оператором , промысловой связкой или промысловым оператором ) является логической константой . Связки можно использовать для соединения логических формул. Например , в синтаксисе логики высказываний двоичная связка может использоваться для соединения двух атомарных формул и отображения сложной формулы . ${\displaystyle \lor }$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle P\lor Q}$

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

Логическая связка похожа, но не эквивалентна синтаксису, обычно используемому в языках программирования и называемому условным оператором . ^{[1] [ нужен лучший источник ]}

Обзор

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

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

Список распространенных логических связок

К наиболее часто используемым логическим связкам относятся следующие. ^[2]

• Отрицание (не) : , , (префикс) в котором является наиболее современным и широко используемым, а также используется многими людьми; ${\displaystyle \neg }$ ${\displaystyle \sim }$ ${\displaystyle N}$ ${\displaystyle \neg }$ ${\displaystyle \sim }$
• Союз (и) : , , (приставка) в котором является наиболее современным и широкоупотребительным; ${\displaystyle \wedge }$ ${\displaystyle \&}$ ${\displaystyle K}$ ${\displaystyle \wedge }$
• Дизъюнкция (или) : , (приставка) в которой является наиболее современной и широко употребляемой; ${\displaystyle \vee }$ ${\displaystyle A}$ ${\displaystyle \vee }$
• Импликация (if...then) : , , , (префикс) в котором является наиболее современным и широко используемым, а также используется многими людьми; ${\displaystyle \to }$ ${\displaystyle \supset }$ ${\displaystyle \Rightarrow }$ ${\displaystyle C}$ ${\displaystyle \to }$ ${\displaystyle \supset }$
• Эквивалентность (тогда и только если) : , , , , (префикс) в которой является наиболее современной и широко используемой, а также может быть хорошим выбором по сравнению с обозначением импликации , например . ${\displaystyle \leftrightarrow }$ ${\displaystyle \subset \!\!\!\supset }$ ${\displaystyle \Leftrightarrow }$ ${\displaystyle \equiv }$ ${\displaystyle E}$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \subset \!\!\!\supset }$ ${\displaystyle \supset }$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \to }$

Например, значение высказываний идет дождь (обозначено ) и я нахожусь в помещении (обозначено ) трансформируется, когда они объединены логическими связками: ${\displaystyle p}$ ${\displaystyle q}$

• Дождь не идет ( ); ${\displaystyle \neg p}$
• Идет дождь , а я дома ( ); ${\displaystyle p\wedge q}$
• Идет дождь или я нахожусь в помещении ( ); ${\displaystyle p\lor q}$
• Если идет дождь, то я в помещении (); ${\displaystyle p\rightarrow q}$
• Если я в помещении, то идет дождь (); ${\displaystyle q\rightarrow p}$
• Я нахожусь в помещении тогда и только тогда, когда идет дождь ( ). ${\displaystyle p\leftrightarrow q}$

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

• Истинная формула: , , (префикс) или ; ${\displaystyle \top }$ ${\displaystyle 1}$ ${\displaystyle V}$ ${\displaystyle \mathrm {T} }$
• Неверная формула: , , (префикс) или . ${\displaystyle \bot }$ ${\displaystyle 0}$ ${\displaystyle O}$ ${\displaystyle \mathrm {F} }$

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

• Отрицание: символ появился у Хейтинга в 1930 году ^{[3] [4]} (сравните с символом Фреге ⫟ в его Begriffsschrift [ ^5] ); символ появился у Рассела в 1908 году; ^[6] альтернативным обозначением является добавление горизонтальной линии поверх формулы, как в ; другое альтернативное обозначение — использовать простой символ , как в . ${\displaystyle \neg }$ ${\displaystyle \sim }$ ${\displaystyle {\overline {p}}}$ ${\displaystyle p'}$
• Соединение: символ появился у Хейтинга в 1930 году ^[3] (сравните с использованием Пеано теоретико-множественной записи пересечения [ 7 ^] ); символ появился по крайней мере в Шёнфинкеле в 1924 году; ^[8] этот символ происходит от интерпретации Буля логики как элементарной алгебры . ${\displaystyle \wedge }$ ${\displaystyle \cap }$ ${\displaystyle \&}$ ${\displaystyle \cdot }$
• Дизъюнкция: символ появился у Рассела в 1908 году ^[6] (сравните с использованием Пеано теоретико-множественной записи объединения ); этот символ также используется, несмотря на двусмысленность, возникающую из-за того, что обычная элементарная алгебра является исключающим или при логической интерпретации в двухэлементном кольце ; пунктуально в истории Пирс использовал букву вместе с точкой в ​​правом нижнем углу . ^[9] ${\displaystyle \vee }$ ${\displaystyle \cup }$ ${\displaystyle +}$ ${\displaystyle +}$ ${\displaystyle +}$
• Смысл: этот символ появился у Гильберта в 1918 году; ^{[10] : 76} использовалось Расселом в 1908 году ^[6] (сравните с пеано — перевернутая C); появился у Бурбаки в 1954 году. ^[11] ${\displaystyle \to }$ ${\displaystyle \supset }$ ${\displaystyle \Rightarrow }$
• Эквивалентность: символ Фреге в 1879 году ; ^[12] у Беккера в 1933 г. (не первый раз и об этом см. ниже); ^[13] появилась у Бурбаки в 1954 г.; ^[14] другие символы появлялись в истории пунктуально, например, в Генцене , ^[15] в Шёнфинкеле ^[8] или в Хазале, ^[16] ${\displaystyle \equiv }$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \Leftrightarrow }$ ${\displaystyle \supset \subset }$ ${\displaystyle \sim }$ ${\displaystyle \subset \supset }$
• Верно: этот символ происходит от интерпретации Буля логики как элементарной алгебры над двухэлементной булевой алгеброй ; другие обозначения включают (аббревиатуру латинского слова «verum»), найденную у Пеано в 1889 году. ${\displaystyle 1}$ ${\displaystyle \mathrm {V} }$
• Неверно: этот символ также происходит от интерпретации Буля логики как кольца; другие обозначения включают (повернутые ), найденные у Пеано в 1889 году. ${\displaystyle 0}$ ${\displaystyle \Lambda }$ ${\displaystyle \mathrm {V} }$

Некоторые авторы использовали буквы для связок: для соединения (немецкое «und» вместо «и») и для дизъюнкции (немецкое «oder» вместо «или») в ранних работах Гильберта (1904); ^[17] для отрицания, для конъюнкции, для альтернативного отрицания, для дизъюнкции, для импликации, для бикондиционала у Лукасевича в 1929 году. ${\displaystyle \operatorname {u.} }$ ${\displaystyle \operatorname {o.} }$ ${\displaystyle Np}$ ${\displaystyle Kpq}$ ${\displaystyle Dpq}$ ${\displaystyle Apq}$ ${\displaystyle Cpq}$ ${\displaystyle Epq}$

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

Такая логическая связка, как обратная импликация " ", на самом деле то же самое, что и материальный кондиционал с переставленными аргументами; таким образом, символ обратной импликации является избыточным. В некоторых логических исчислениях (в частности, в классической логике ) некоторые существенно разные составные высказывания логически эквивалентны . Менее тривиальный пример избыточности — классическая эквивалентность между и . Следовательно, логическая система, основанная на классической логике, не нуждается в условном операторе " ", если " " (нет) и " " (или) уже используются, или может использовать " " только как синтаксический сахар для составного слова, имеющего одно отрицание. и одна дизъюнкция. ${\displaystyle \leftarrow }$ ${\displaystyle \neg p\vee q}$ ${\displaystyle p\to q}$ ${\displaystyle \to }$ ${\displaystyle \neg }$ ${\displaystyle \vee }$ ${\displaystyle \to }$

Существует шестнадцать логических функций , связывающих входные значения истинности и четырехзначные двоичные выходные данные. ^[18] Они соответствуют возможному выбору бинарных логических связок для классической логики . Различные реализации классической логики могут выбирать разные функционально полные подмножества связок. ${\displaystyle p}$ ${\displaystyle q}$

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

Один элемент

${\displaystyle \{\uparrow \}}$, . ${\displaystyle \{\downarrow \}}$

Два элемента

${\displaystyle \{\vee ,\neg \}}$, , , , , , , , , , , , , , , , , . ${\displaystyle \{\wedge ,\neg \}}$ ${\displaystyle \{\to ,\neg \}}$ ${\displaystyle \{\gets ,\neg \}}$ ${\displaystyle \{\to ,\bot \}}$ ${\displaystyle \{\gets ,\bot \}}$ ${\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 a\land (a\lor b)=a}$

Монотонность

Если f ( a ₁ , ..., a _n ) ≤ f ( b ₁ , ..., b _n ) для всех a ₁ , ..., a _n , b ₁ , ..., b _n ∈ {0 ,1} такой, что a 1 _≤ b 1 _, a 2 _≤ b 2 _, ..., a _n ≤ bn _. Например, ∨, ∧, ⊤, ⊥.

Близость

Каждая переменная всегда влияет на истинное значение операции или никогда не влияет. Например, ¬, ↔, , ⊤, ⊥. ${\displaystyle \nleftrightarrow }$

Двойственность

Прочитать истинностные присвоения для операции сверху вниз по ее таблице истинности - это то же самое, что взять дополнение чтения таблицы той же или другой связки снизу вверх. Не прибегая к таблицам истинности, его можно сформулировать как g̃ (¬ a ₁ , ..., ¬ a _n ) = ¬ g ( a ₁ , ..., an _n ) . Например, ¬.

Сохраняющий истину

То, что все эти аргументы являются тавтологиями, само по себе является тавтологией. Например, ∨, ∧, ⊤, →, ↔, ⊂ (см. достоверность ).

Сохраняющий ложь

Соединение всех этих аргументов является противоречием само по себе. Например, ∨, ∧, , ⊥, ⊄, ⊅ (см. достоверность ). ${\displaystyle \nleftrightarrow }$

Инволютивность (для одинарных связок)

ж ( ж ( а )) знак равно а . Например, отрицание в классической логике.

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

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

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

Порядок приоритета

Чтобы уменьшить количество необходимых круглых скобок, можно ввести правила приоритета : ¬ имеет более высокий приоритет, чем ∧, ∧ выше, чем ∨, и ∨ выше, чем →. Например, это сокращение от . ${\displaystyle P\vee Q\wedge {\neg R}\rightarrow S}$ ${\displaystyle (P\vee (Q\wedge (\neg R)))\rightarrow S}$

Вот таблица, показывающая часто используемый приоритет логических операторов. ^[19]

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

Информатика

Истинно-функциональный подход к логическим операторам реализуется в виде логических элементов в цифровых схемах . Практически все цифровые схемы (основное исключение — DRAM ) построены из И-НЕ , ИЛИ -НЕ , НЕ и передающих вентилей ; Более подробную информацию см. в разделе «Функция истины в информатике» . Логические операторы над битовыми векторами (соответствующие конечным булевым алгебрам ) являются побитовыми операциями .

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

Таблица и диаграмма Хассе

16 логических связок можно частично упорядочить , чтобы получить следующую диаграмму Хассе . Частичный порядок определяется заявлением, что если и только если всякий раз, когда выполняется, то так же и происходит. ${\displaystyle x\leq y}$ ${\displaystyle x}$ ${\displaystyle y.}$

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

• Философский портал
• Психологический портал

• Логический домен
• Булева функция
• Булева логика
• Логическая функция
• Четырехзначная логика
• Список тем по булевой алгебре
• Логическая константа
• Модальный оператор
• Пропозициональное исчисление
• Функция истины
• Таблица истинности
• Истинные ценности

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

1. Зубчатое колесо. «В чем разница между логическим и условным /оператором/». Переполнение стека . Проверено 9 апреля 2015 г.
2. Чао, К. (2023).数理逻辑:形式化方法的应用[ Математическая логика: применение метода формализации ] (на китайском языке). Пекин: Препринт. стр. 15–28.
3. Хейтинг, А. (1930). «Формальное правило интуиционистской логики». Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-mathematische Klasse (на немецком языке): 42–56.
4. Денис Рогель (2002), Краткий обзор логических обозначений 20-го века (см. Диаграмму на странице 2).
5. Фреге, Г. (1879). Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens . Halle a/S: Verlag von Louis Nebert. п. 10.
6. Рассел (1908) Математическая логика, основанная на теории типов (Американский журнал математики 30, стр. 222–262, также в книге «От Фреге до Гёделя» под редакцией ван Хейеноорта).
7. Пеано (1889) Principia Arithmetices, nova Methodo Exposita .
8. Schönfinkel (1924) Über die Bausteine ​​der mathematischen Logik , переведено как « О строительных блоках математической логики» в книге «От Фреге к Гёделю» под редакцией ван Хейеноорта.
9. Пирс (1867) Об улучшении логического исчисления Буля.
10. Гильберт, Д. (1918). Бернейс, П. (ред.). Принцип математики . Конспекты лекций в Геттингенском университете, зимний семестр, 1917–1918 гг.; Перепечатано как Гильберт Д. (2013). «Принципы математики». В Эвальде, В.; Зиг, В. (ред.). Лекции Дэвида Гильберта по основам арифметики и логики 1917–1933 гг . Гейдельберг, Нью-Йорк, Дордрехт и Лондон: Springer. стр. 59–221.
11. Бурбаки, Н. (1954). Теория ансамблей . Париж: Hermann & Cie, Éditeurs. п. 14.
12. Фреге, Г. (1879). Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens (на немецком языке). Halle a/S: Verlag von Louis Nebert. п. 15.
13. Беккер, А. (1933). Die Aristotelische Theorie der Möglichkeitsschlösse: Eine logisch-philologische Untersuruchung der Kapitel 13-22 Аристотеля Analytica Priora I (на немецком языке). Берлин: Junker und Dünnhaupt Verlag. п. 4.
14. Бурбаки, Н. (1954). Теория ансамблей (на французском языке). Париж: Hermann & Cie, Éditeurs. п. 32.
15. Genzen (1934) Untersuchungen über das logische Schließen .
16. Chazal (1996): Éléments de logique formelle.
17. Гильберт, Д. (1905) [1904]. «Über die Grundlagen der Logik und der Arithmetik». В Кразере, К. (ред.). Verhandlungen des Dritten Internationalen Mathematik Kongresses в Гейдельберге, от 8 до 13 августа 1904 года . стр. 174–185.
18. Боченский (1959), Краткое изложение математической логики , passim.
19. О'Доннелл, Джон; Холл, Корделия; Пейдж, Рекс (2007), Дискретная математика с использованием компьютера, Springer, стр. 120, ISBN 9781846285981.
20. Джексон, Дэниел (2012), Абстракции программного обеспечения: логика, язык и анализ, MIT Press, стр. 263, ISBN 9780262017152.

Источники

• Боченский, Юзеф Мария (1959), Краткое изложение математической логики , перевод с французского и немецкого изданий Отто Берда, Д. Рейделя, Дордрехт, Южная Голландия.
• Чао, К. (2023).数理逻辑:形式化方法的应用[ Математическая логика: применение метода формализации ] (на китайском языке). Пекин: Препринт. стр. 15–28.
• Эндертон, Герберт (2001), Математическое введение в логику (2-е изд.), Бостон, Массачусетс: Academic Press, ISBN 978-0-12-238452-3
• Гамут, LTF (1991), «Глава 2», Логика, язык и значение , том. 1, University of Chicago Press, стр. 54–64, OCLC  21372380.
• Раутенберг, В. (2010), Краткое введение в математическую логику (3-е изд.), Нью-Йорк : Springer Science+Business Media , doi : 10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6.
• Хамберстон, Ллойд (2011). Соединения . МТИ Пресс. ISBN 978-0-262-01654-4.

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

• «Пропозициональная связка», Математическая энциклопедия , EMS Press , 2001 [1994]
• Ллойд Хамберстон (2010), «Связки предложений в формальной логике», Стэнфордская энциклопедия философии ( абстрактный алгебраический логический подход к связкам.)
• Джон Макфарлейн (2005), «Логические константы», Стэнфордская энциклопедия философии .