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

Логические связки
НЕТ ${\displaystyle \отрицательный А}$,${\displaystyle -A}$,${\displaystyle {\overline {A}}}$,${\displaystyle \сим А}$ И ${\displaystyle А\и Б}$,${\displaystyle A\cdot B}$,${\displaystyle AB}$,${\displaystyle А\&Б}$,${\displaystyle А\&\&Б}$ НЕ-И ${\displaystyle A{\overline {\land }}B}$,${\displaystyle A\uparrow B}$,${\displaystyle A\середина B}$,${\displaystyle {\overline {A\cdot B}}}$ ИЛИ ${\displaystyle A\или B}$,${\displaystyle А+Б}$,${\displaystyle A\середина B}$,${\displaystyle A\параллельно B}$ НИ ${\displaystyle A{\overline {\lor }}B}$,${\displaystyle A\downarrow B}$,${\displaystyle {\overline {A+B}}}$ X-NOR-не ${\displaystyle A\ {\text{XNOR}}\ B}$ └ equivalent ${\displaystyle A\equiv B}$, ${\displaystyle A\Leftrightarrow B}$, ${\displaystyle A\leftrightharpoons B}$ XOR ${\displaystyle A{\underline {\lor }}B}$, ${\displaystyle A\oplus B}$ └nonequivalent ${\displaystyle A\not \equiv B}$, ${\displaystyle A\not \Leftrightarrow B}$, ${\displaystyle A\nleftrightarrow B}$ implies ${\displaystyle A\Rightarrow B}$, ${\displaystyle A\supset B}$, ${\displaystyle A\rightarrow B}$ converse ${\displaystyle A\Leftarrow B}$, ${\displaystyle A\subset B}$, ${\displaystyle A\leftarrow B}$
Related concepts
Propositional calculus Predicate logic Boolean algebra Truth table Truth function Boolean function Functional completeness Scope (logic)
Applications
Digital logic Programming languages Mathematical logic Philosophy of logic
Category
v t e

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

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

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

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

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

Символ, имя		Таблица истинности					Диаграмма Венна
Нулевые связки (константы)
⊤	Истина / тавтология				1
⊥	Ложь / противоречие				0
Унарные связки
		${\displaystyle p}$ =	0		1
	Предложение${\displaystyle p}$		0		1
¬	Отрицание		1		0
Бинарные связки
${\displaystyle p}$ =	0	0	1	1
${\displaystyle q}$ =	0	1	0	1
	Предложение${\displaystyle p}$		0	0	1	1
	Предложение${\displaystyle q}$		0	1	0	1
∧	Соединение		0	0	0	1
↑	Альтернативное отрицание		1	1	1	0
∨	Дизъюнкция		0	1	1	1
↓	Совместное отрицание		1	0	0	0
→	Материал условный		1	1	0	1
${\displaystyle \nleftrightarrow }$	Эксклюзивный или		0	1	1	0
↔	Двуусловный		1	0	0	1
←	Обратное следствие		1	0	1	1
Дополнительная информация

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

• Отрицание (not) : , , (префикс) в котором является самым современным и широко используемым, а также используется многими людьми;${\displaystyle \neg }$${\displaystyle \sim }$${\displaystyle N}$${\displaystyle \neg }$${\displaystyle \sim }$
• Союз (и) : , , (префикс) в котором является наиболее современным и широко используемым;${\displaystyle \wedge }$${\displaystyle \&}$${\displaystyle K}$${\displaystyle \wedge }$
• Дизъюнкция (или) : , (префикс) в котором является наиболее современным и широко используемым;${\displaystyle \vee }$${\displaystyle A}$${\displaystyle \vee }$
• Импликация (если...тогда) : , , , (префикс) в котором является наиболее современным и широко используемым, а также используется многими людьми;${\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] (сравните с использованием Пеано теоретико-множественной нотации объединения ); символ также используется, несмотря на неоднозначность, возникающую из-за того, что в обычной элементарной алгебре это исключающее или при логической интерпретации в двухэлементном кольце ; пунктуально в истории a вместе с точкой в ​​нижнем правом углу использовался Пирсом . ^[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 \}}$

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

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

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

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

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

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

английское слово	Соединительный	Символ	Логический вентиль
нет	отрицание	${\displaystyle \neg }$	НЕТ
и	соединение	${\displaystyle \wedge }$	И
или	дизъюнкция	${\displaystyle \vee }$	ИЛИ
если...тогда	материальный подтекст	${\displaystyle \to }$	ПОДРАЗУМЕВАТЬ
...если	обратная импликация	${\displaystyle \leftarrow }$
или...или	исключающая дизъюнкция	${\displaystyle \oplus }$	XOR
если и только если	двуусловный	${\displaystyle \leftrightarrow }$	X-NOR-не
не оба	альтернативное отрицание	${\displaystyle \uparrow }$	НЕ-И
ни...ни	совместное отрицание	${\displaystyle \downarrow }$	НИ
но не	материальная неимпликация	${\displaystyle \not \to }$	НИМПЛИ

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

Ассоциативность

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

Коммутативность

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

Распределяемость

Связка, обозначенная ·, распределяется по другой связке, обозначенной +, если a · ( b + c ) = ( a · b ) + ( a · c ) для всех операндов a , b , c .

Идемпотентность

Если операнды операции одинаковы, соединение логически эквивалентно операнду.

Поглощение

Пара связок ∧, ∨ удовлетворяет закону поглощения, если для всех операндов a , b .${\displaystyle a\land (a\lor b)=a}$

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

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

Сродство

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

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

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

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

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

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

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

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

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

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

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

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

This section needs expansion. You can help by adding to it. (March 2012)

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

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

Оператор	Приоритет
${\displaystyle \neg }$	1
${\displaystyle \land }$	2
${\displaystyle \lor }$	3
${\displaystyle \to }$	4
${\displaystyle \leftrightarrow }$	5

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

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

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

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

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

Логические связки используются для определения основных операций теории множеств ^[22] следующим образом:

Операции и связки теории множеств

Установить операцию	Соединительный	Определение
Пересечение	Соединение	${\displaystyle A\cap B=\{x:x\in A\land x\in B\}}$[23] [24] [25]
Союз	Дизъюнкция	${\displaystyle A\cup B=\{x:x\in A\lor x\in B\}}$[26] [23] [24]
Дополнение	Отрицание	${\displaystyle {\overline {A}}=\{x:x\notin A\}}$[27] [24] [28]
Подмножество	Импликация	${\displaystyle A\subseteq B\leftrightarrow (x\in A\rightarrow x\in B)}$[29] [24] [30]
Равенство	Двуусловный	${\displaystyle A=B\leftrightarrow (\forall X)[A\in X\leftrightarrow B\in X]}$[29] [24] [31]

Это определение равенства множеств эквивалентно аксиоме экстенсиональности .

• Бохеньский, Юзеф Мария (1959), A Précis of Mathematical Logic , перевод с французского и немецкого изданий Отто Берда, Д. Рейдель, Дордрехт, Южная Голландия.
• Чао, К. (2023).数理逻辑:形式化方法的应用[ Математическая логика: применение метода формализации ] (на китайском языке). Пекин: Препринт. стр. 15–28.
• Эндертон, Герберт (2001), Математическое введение в логику (2-е изд.), Бостон, Массачусетс: Academic Press, ISBN 978-0-12-238452-3
• Гамут, LTF (1991), «Глава 2», Логика, язык и значение , т. 1, Издательство Чикагского университета, стр. 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). Связующие . MIT Press. ISBN 978-0-262-01654-4.

На Викискладе есть медиафайлы по теме Логические связки .

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