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

Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Апрель 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

Обзор [ править ]

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

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

Общие логические связки [ править ]

Символ, имя		Таблица истинности					Диаграмма Венна
Нулевые связки (константы)
⊤	Правда / тавтология				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
${\ displaystyle \ nleftrightarrow}$	Эксклюзивный или		0	1	1	0
↔	Двусмысленный		1	0	0	1
←	Обратное значение		1	0	1	1
Дополнительная информация

Список общих логических связок [ править ]

Обычно используемые логические связки включают: ^{[2] [3]}

• Отрицание (не) : ¬, N (префикс), ~ ^[4]
• Соединение (и) : ∧, K (префикс), &, ∙
• Дизъюнкция (или) : ∨, A (префикс)
• Материальная импликация (если ... то) : →, C (префикс), ⇒, ⊃
• Биконусный (если и только если) : ↔, E (префикс), ≡, =

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

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

• Это не дождь ( P )${\ displaystyle \ neg}$
• Идет дождь, а я в помещении ( )${\ displaystyle P \ wedge Q}$
• Идёт дождь или я в помещении ( )${\ Displaystyle P \ lor Q}$
• Если идет дождь, то я в помещении ( )${\ Displaystyle P \ rightarrow Q}$
• Если я в помещении, значит идет дождь ( )${\ displaystyle Q \ rightarrow P}$
• Я нахожусь в помещении тогда и только тогда, когда идет дождь ( )${\ displaystyle P \ leftrightarrow Q}$

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

• Истинная формула (⊤, 1, V [префикс] или T)
• Неверная формула (⊥, 0, O [префикс] или F)

История обозначений [ править ]

• Отрицание: символ ¬ появился у Гейтинга в 1929 году ^{[5] [6]} (сравните с символом Фреге ⫟ в его Begriffsschrift ); символ ~ появился у Рассела в 1908 году; ^[7] альтернативное обозначение - добавить горизонтальную черту поверх формулы, как в ; ^[2] другое альтернативное обозначение - использовать символ штриха, как в P '.${\ displaystyle {\ overline {P}}}$
• Соединение: символ ∧ появился у Гейтинга в 1929 г. ^[5] (сравните с использованием Пеано теоретико-множественной записи пересечения ∩ ^[8] ); символ & появился, по крайней мере, в Шенфинкеле в 1924 году; ^[9] символ. происходит из интерпретации Буля логики как элементарной алгебры .
• Дизъюнкция: символ ∨ появился у Рассела в 1908 году ^[7] (сравните с использованием Пеано теоретико-множественной записи объединения ); символ + также используется, несмотря на двусмысленность, проистекающую из того факта, что + обычной элементарной алгебры является исключающим или при логической интерпретации в двухэлементном кольце ; точечно в истории а + вместе с точкой в нижнем правом углу был использован Пирса , ^[10]
• Следствие: символ → можно увидеть у Гильберта в 1917 году; ^[11] ⊃ использовался Расселом в 1908 году ^[7] (сравните с перевернутой нотацией C Пеано); ⇒ использовался в Vax. ^[12]
• Двикондиционный: символ ≡ использовался, по крайней мере, Расселом в 1908 году; ^[7] ↔ использовался по крайней мере Тарским в 1940 году; ^[13] ⇔ использовалось в Vax; другие символы появились точечно в истории, такие как ⊃⊂ в Генцене , ^[14] \ в Schönfinkel ^[9] или ⊂⊃ в Шазали. ^[15]
• Верно: символ 1 происходит из интерпретации логики Буля как элементарной алгебры над двухэлементной булевой алгеброй ; другие обозначения включают (можно найти в Пеано).${\ displaystyle \ bigwedge}$
• Ложь: символ 0 также происходит из интерпретации логики Буля как кольца; другие обозначения включают (можно найти в Пеано).${\ displaystyle \ bigvee}$

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

Избыточность [ править ]

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

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

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

Один элемент

{↑}, {↓}.

Два элемента

${\ Displaystyle \ {\ vee, \ neg \}}$, , , , , , , , , , , , , , , , , .${\ Displaystyle \ {\ клин, \ neg \}}$${\ Displaystyle \ {\ к, \ neg \}}$${\ Displaystyle \ {\ получает, \ neg \}}$${\ displaystyle \ {\ to, \ bot \}}$${\ Displaystyle \ {\ получает, \ бот \}}$${\ 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 \}}$

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

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

Естественный язык [ править ]

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

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

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

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

Свойства [ править ]

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

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

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

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

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

Распределительность

Связка, обозначаемая ·, распределяется по другой связке, обозначаемой +, если 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 ₁ ≤ b ₁ , a ₂ ≤ b ₂ , ..., a _n ≤ b _n . Например, ∨, ∧, ⊤, ⊥.

Близость

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

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

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

Сохраняющий правду

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

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

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

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

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

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

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

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

Порядок приоритета [ править ]

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

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

${\displaystyle {\begin{array}{c|c}{\text{Operator}}&{\text{Precedence}}\\\hline \neg &1\\\land &2\\\vee &3\\\to &4\\\leftrightarrow &5\end{array}}}$

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

Информатика [ править ]

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

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

См. Также [ править ]

Заметки [ править ]

Ссылки [ править ]

• Бохенский, Юзеф Мария (1959), Краткое изложение математической логики , перевод с французского и немецкого изданий Отто Берда, Д. Рейделя, Дордрехт, Южная Голландия.
• Эндертон, Герберт (2001), Математическое введение в логику (2-е изд.), Бостон, Массачусетс: Academic Press, ISBN 978-0-12-238452-3
• Gamut, 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). Связки . MIT Press. ISBN 978-0-262-01654-4.

Внешние ссылки [ править ]

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

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