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

Другие логические символы см. в разделе «Список логических символов» .

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

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

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

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

Обзор

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

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

Символ, имя		Правда стол					Венн диаграмма
Нулевые связки (константы)
⊤	Истина / тавтология				1
⊥	Ложь / противоречие				0
Унарные связки
		$p$ =	0		1
	Предложение $p$		0		1
¬	Отрицание		1		0
Бинарные связки
		$p$ =	0		1
		$q$ =	0	1	0	1
	Предложение $p$		0	0	1	1
	Предложение $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
$\nleftrightarrow$	Эксклюзивный или		0	1	1	0
↔	двуусловный		1	0	0	1
←	Обратная импликация		1	0	1	1
Дополнительная информация

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

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

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

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

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

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

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

В этой таблице обобщена терминология:

Соединительный	По-английски	Существительные для частей	Глагольная фраза
Соединение	И А, и Б	соединение	А и Б соединены
Дизъюнкция	Либо А, либо Б, либо оба	дизъюнктный	А и Б разделены
Отрицание	Дело не в том, что А	отклонен	А отрицается
Условный	Если А, то Б	предшествующий, последующий	B подразумевается под A
двуусловный	А тогда и только тогда, когда Б	эквиваленты	A и B эквивалентны

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

• Отрицание: символ $\neg$ появился в Хейтинге в 1930 г. (сравните с Фреге символом ⫟ в его Wortschrift ); символ $\sim$ появился у Рассела в 1908 году; Альтернативное обозначение — добавить горизонтальную линию поверх формулы, как в ${\overline {p}}$; другое альтернативное обозначение - использовать простой символ , как в $p'$.
• Союз: символ $\wedge$ появился в Хейтинге в 1930 г. (сравните с использованием Пеано теоретико-множественной записи пересечения $\cap$); символ $\&$ появился по крайней мере в Шёнфинкеле в 1924 году; символ $\cdot$ происходит от Буля интерпретации логики как элементарной алгебры .
• Дизъюнкция: символ $\vee$ появился у Рассела в 1908 году (сравните с использованием Пеано теоретико-множественной записи объединения $\cup$); символ $+$ также используется, несмотря на двусмысленность, связанную с тем, что $+$ обычной элементарной алгебры является исключительным или при логической интерпретации в двухэлементном кольце ; пунктуально в истории $+$ вместе с точкой в ​​правом нижнем углу использовал Пирс .
• Значение: символ $\to$ появился у Гильберта в 1918 году; $\supset$ использовался Расселом в 1908 году (сравните с перевернутой C Пеано); $\Rightarrow$ появился у Бурбаки в 1954 году.
• Эквивалентность: символ $\equiv$ во Фреге в 1879 году; $\leftrightarrow$ у Беккера в 1933 г. (не первый раз и об этом см. ниже); $\Leftrightarrow$ появился у Бурбаки в 1954 году; другие символы появлялись в истории регулярно, например, $\supset \subset$ в Генцене , $\sim$ в Шенфинкеле или $\subset \supset$ в Шазале,
• Правда: символ $1$ происходит из Буля интерпретации логики как элементарной алгебры над двухэлементной булевой алгеброй ; другие обозначения включают $\mathrm {V}$ (аббревиатура латинского слова «verum»), найденная в Пеано в 1889 году.
• Ложь: символ $0$ происходит также из интерпретации Буля логики как кольца; другие обозначения включают $\Lambda$ (повернутый $\mathrm {V}$), найденный в Пеано в 1889 году.

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

Избыточность

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

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

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

Один элемент

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

Два элемента

$\{\vee ,\neg \}$, $\{\wedge ,\neg \}$, $\{\to ,\neg \}$, $\{\gets ,\neg \}$, $\{\to ,\bot \}$, $\{\gets ,\bot \}$, $\{\to ,\nleftrightarrow \}$, $\{\gets ,\nleftrightarrow \}$, $\{\to ,\nrightarrow \}$, $\{\to ,\nleftarrow \}$, $\{\gets ,\nrightarrow \}$, $\{\gets ,\nleftarrow \}$, $\{\nrightarrow ,\neg \}$, $\{\nleftarrow ,\neg \}$, $\{\nrightarrow ,\top \}$, $\{\nleftarrow ,\top \}$, $\{\nrightarrow ,\leftrightarrow \}$, $\{\nleftarrow ,\leftrightarrow \}$.

Три элемента

$\{\lor ,\leftrightarrow ,\bot \}$, $\{\lor ,\leftrightarrow ,\nleftrightarrow \}$, $\{\lor ,\nleftrightarrow ,\top \}$, $\{\land ,\leftrightarrow ,\bot \}$, $\{\land ,\leftrightarrow ,\nleftrightarrow \}$, $\{\land ,\nleftrightarrow ,\top \}$.

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

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

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

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

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

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

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

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

Свойства

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

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

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

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

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

Дистрибутивность

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

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

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

Поглощение

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

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

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

Близость

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

Информатика

Основная статья: Логический вентиль

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

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

Теория множеств

Основные статьи: Теория множеств и Аксиоматическая теория множеств

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

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

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

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

См. также

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

Источники

• Боченский, Юзеф Мария (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), « Логические константы », Стэнфордская энциклопедия философии .