Логическая связка - Logical connective
В логике , А логическая связка (также называемый логический оператор , пропозициональной связкой , или сентенциальная оператор ) является логическим константа используется для соединения двух или более формул. Например , в синтаксисе из логики , то двоичный соединительно может быть использован для соединения двух атомных формул и , делая сложную формулу .
Общие связки включают отрицание , дизъюнкцию , союз и импликацию . В стандартных системах классической логики эти связки интерпретируются как функции истинности , хотя они получают множество альтернативных интерпретаций в неклассической логике . Их классические интерпретации аналогичны значениям выражений естественного языка, таких как английское «не», «или», «и», и «если», но не идентичны. Расхождения между связками естественного языка и связками классической логики мотивировали неклассические подходы к значению естественного языка, а также подходы, сочетающие классическую композиционную семантику с устойчивой прагматикой .
Логическая связка похожа, но не эквивалентна синтаксису, обычно используемому в языках программирования, называемому условным оператором .
Обзор
В формальных языках функции истинности представлены однозначными символами. Это позволяет избежать неоднозначного понимания логических утверждений. Эти символы называются логическими связками , логические операторы , пропозициональные операторы , или, в классической логике , истинности функциональных связок . Чтобы узнать о правилах, которые позволяют создавать новые правильно сформированные формулы путем соединения других хорошо сформированных формул с использованием связок, функционирующих на основе истинности, см. Правильно сформированные формулы .
Логические связки могут использоваться для связывания более двух операторов, поэтому можно говорить о 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 | |||
Эксклюзивный или | 0 | 1 | 1 | 0 | ||||
↔ | Двусмысленный | 1 | 0 | 0 | 1 | |||
← | Обратное значение | 1 | 0 | 1 | 1 | |||
Больше информации |
Список общих логических связок
Обычно используемые логические связки включают:
- Отрицание (не) : ¬, N (префикс), ~
- Соединение (и) : ∧, K (префикс), &, ∙
- Дизъюнкция (или) : ∨, A (префикс)
- Материальная импликация (если ... то) : →, C (префикс), ⇒, ⊃
- Биконусный (если и только если) : ↔, E (префикс), ≡, =
Альтернативные имена для двусмысленных выражений - 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 1 ≤ b 1 , a 2 ≤ b 2 , ..., a n ≤ b n . Например, ∨, ∧, ⊤, ⊥.
- Близость
- Каждая переменная всегда имеет значение для истинности операции или никогда не имеет значения. Например, ¬, ↔`` ⊤, ⊥.
- Двойственность
- Прочитать присвоение значений истинности для операции сверху вниз по ее таблице истинности - это то же самое, что выполнить дополнение к чтению таблицы той же или другой связки снизу вверх. Не прибегая к таблицам истинности, его можно сформулировать как g̃ (¬ 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 является ложным (хотя соединение в целом является успешным ≈ "истина" в такой случай). Это ближе к интуиционистским и конструктивистским взглядам на материальные условности, а не к взглядам классической логики.
Смотрите также
|
Примечания
использованная литература
Источники
- Бохенский, Юзеф Мария (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), « Логические константы », Стэнфордская энциклопедия философии .