В логике , А логическая связка (также называемый логический оператор , пропозициональной связкой , или сентенциальная оператор ) является логическим константа используется для соединения двух или более формул. Например , в синтаксисе из логики , в бинарной связкеможно использовать для соединения двух атомарных формул а также , переводя сложную формулу .
Общие связки включают отрицание , дизъюнкцию , союз и импликацию . В стандартных системах классической логики эти связки интерпретируются как функции истинности , хотя они получают множество альтернативных интерпретаций в неклассической логике . Их классические интерпретации аналогичны значениям выражений естественного языка, таких как английское «не», «или», «и», и «если», но не идентичны. Расхождения между связками естественного языка и связками классической логики мотивировали неклассические подходы к значению естественного языка, а также подходы, сочетающие классическую композиционную семантику с устойчивой прагматикой .
Логическая связка похожа, но не эквивалентна синтаксису, обычно используемому в языках программирования, называемому условным оператором . [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 | |||
Эксклюзивный или | 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 )
- Идёт дождь и я в помещении ()
- Идёт дождь или я в помещении ()
- Если идет дождь, то я в помещении ()
- Если я в помещении, значит идет дождь ()
- Я нахожусь в помещении тогда и только тогда, когда идет дождь ()
Также принято считать, что всегда истинная формула и всегда ложная формула являются связными: [2]
История обозначений
- Отрицание: символ ¬ появился у Гейтинга в 1929 году [5] [6] (сравните с символом Фреге ⫟ в его Begriffsschrift ); символ ~ появился у Рассела в 1908 году; [7] альтернативное обозначение - добавить горизонтальную черту поверх формулы, как в; [2] другое альтернативное обозначение - использовать символ штриха, как в 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 происходит из интерпретации логики Буля как элементарной алгебры над двухэлементной булевой алгеброй ; другие обозначения включают (можно найти в Пеано).
- Ложь: символ 0 также происходит из интерпретации логики Буля как кольца; другие обозначения включают (можно найти в Пеано).
Некоторые авторы когда-то использовали буквы для связок: 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:
- Один элемент
- {↑}, {↓}.
- Два элемента
- , , , , , , , , , , , , , , , , , .
- Три элемента
- , , , , , .
Другой подход - использование равноправных связок некоторого удобного и функционально полного, но не минимального набора. Этот подход требует большего количества пропозициональных аксиом , и каждая эквивалентность между логическими формами должна быть либо аксиомой, либо доказуемой как теорема.
Однако с интуиционистской логикой ситуация сложнее . Из его пяти связок, {∧, ∨, →, ¬, only}, только отрицание «¬» может быть сведено к другим связкам (см. Ложь (логика) § Ложь, отрицание и противоречие ). Ни соединение, ни дизъюнкция, ни материальное условное выражение не имеют эквивалентной формы, построенной из других четырех логических связок.
Естественный язык
Стандартные логические связки классической логики имеют грубые эквиваленты в грамматиках естественных языков. В английском языке , как и во многих других языках, такие выражения обычно представляют собой грамматические союзы . Тем не менее, они также могут принимать форму complementizers , глагольных суффиксов и частиц . В денотатах естественных языка связок являются основной темой исследований в формальной семантике , поле , которое изучает логическую структуру естественных языков.
Значения связок естественного языка не совсем идентичны их ближайшим эквивалентам в классической логике. В частности, дизъюнкция может получить исключительную интерпретацию на многих языках. Некоторые исследователи приняли этот факт как доказательство того, что естественный язык семантика является неклассической . Однако другие поддерживают классическую семантику, постулируя прагматические объяснения исключительности, которые создают иллюзию неклассичности. В таких случаях исключительность обычно рассматривается как скалярная импликатура . Связанные головоломки, включающие дизъюнкцию, включают в себя выводы свободного выбора , ограничение Херфорда и вклад дизъюнкции в альтернативные вопросы .
Другие очевидные несоответствия между естественным языком и классической логикой включают парадоксы материального значения , анафору осла и проблему контрфактических условий . Эти явления были взяты в качестве мотивации для идентификации обозначений условных выражений естественного языка с логическими операторами, включая строгие условные , переменно строгие условные , а также различные динамические операторы.
В следующей таблице показаны стандартные классически определяемые приближения для английских связок.
Английское слово | Соединительный | Символ | Логические ворота |
---|---|---|---|
нет | отрицание | "¬" | НЕТ |
а также | соединение | "∧" | А ТАКЖЕ |
или же | дизъюнкция | "∨" | ИЛИ ЖЕ |
если ... то | материальное значение | «→» | ПОДРАЗУМЕВАТЬ |
...если | обратное следствие | «←» | |
если и только если | двусмысленный | "↔" | 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 . Например, ∨, ∧, ⊤, ⊥.
- Близость
- Каждая переменная всегда имеет значение для истинности операции или никогда не имеет значения. Например, ¬, ↔, , ⊤, ⊥.
- Двойственность
- Прочитать присвоение значений истинности для операции сверху вниз по ее таблице истинности - это то же самое, что выполнить дополнение к чтению таблицы той же или другой связки снизу вверх. Не прибегая к таблицам истинности может быть сформулирована в виде г (¬ 1 , ..., ¬ п ) = ¬ г ( 1 , ..., п ) . Например, ¬.
- Сохраняющий правду
- Составной частью всех этих аргументов являются тавтологии - это сама тавтология. Например, ∨, ∧, ⊤, →, ↔, ⊂ (см. Справедливость ).
- Сохранение лжи
- Все эти аргументы состоят в противоречиях, и это противоречие само по себе. Например, ∨, ∧, , ⊥, ⊄, ⊅ (см. Справедливость ).
- Инволютивность (для унарных связок)
- е ( е ( )) = . Например, отрицание в классической логике.
Для классической и интуиционистской логики символ «=» означает, что соответствующие импликации «... → ...» и «... ← ...» для логических соединений могут быть доказаны как теоремы, так и символ «≤». означает, что «... → ...» для логических соединений является следствием соответствующих связок «... → ...» для пропозициональных переменных. Некоторые многозначные логики могут иметь несовместимые определения эквивалентности и порядка (следствия).
И конъюнкция, и дизъюнкция ассоциативны, коммутативны и идемпотентны в классической логике, большинстве разновидностей многозначной логики и интуиционистской логике. То же верно и для распределения конъюнкции по дизъюнкции и дизъюнкции по конъюнкции, а также для закона поглощения.
В классической логике и некоторых разновидностях многозначной логики конъюнкция и дизъюнкция двойственны, а отрицание самодвойственно, последнее также самодвойственно в интуиционистской логике.
Порядок старшинства
Чтобы уменьшить количество необходимых скобок, можно ввести правила приоритета : ¬ имеет более высокий приоритет, чем ∧, ∧ выше, чем ∨, и ∨ выше, чем →. Так, например, это сокращение от .
Вот таблица, которая показывает обычно используемый приоритет логических операторов. [18]
Однако не все компиляторы используют один и тот же порядок; например, также использовался порядок, в котором дизъюнкция имеет более низкий приоритет, чем импликация или двойная импликация. [19] Иногда приоритет между соединением и дизъюнкцией не указан, и требуется указать его явно в данной формуле с круглыми скобками. Порядок приоритета определяет, какая связка является «главной связкой» при интерпретации неатомарной формулы.
Информатика
Функциональный подход к логическим операторам реализован в виде логических вентилей в цифровых схемах . Практически все цифровые схемы (главным исключением является DRAM ) построены из NAND , NOR , NOT и шлюзов передачи ; см. дополнительные сведения в разделе « Функция истины в информатике» . Логические операторы над битовыми векторами (соответствующие конечным булевым алгебрам ) являются побитовыми операциями .
Но не каждое использование логической связки в компьютерном программировании имеет булеву семантику. Например, ленивое вычисление иногда реализуется для P ∧ Q и P ∨ Q , поэтому эти связки не коммутативны, если одно или оба выражения P , Q имеют побочные эффекты . Кроме того, условное выражение , которое в некотором смысле соответствует материальной условной связке, по существу не является логическим, потому что для if (P) then Q;
, консеквент Q не выполняется, если антецедент P является ложным (хотя соединение в целом является успешным ≈ "истина" в такой случай). Это ближе к интуиционистским и конструктивистским взглядам на материальные условности, а не к взглядам классической логики.
Смотрите также
|
|
Заметки
- ^ Зубчатое колесо. «В чем разница между логическим и условным / оператором /» . Переполнение стека . Проверено 9 апреля 2015 года .
- ^ а б в «Исчерпывающий список логических символов» . Математическое хранилище . 2020-04-06 . Проверено 2 сентября 2020 .
- ^ «Связная | логика» . Британская энциклопедия . Проверено 2 сентября 2020 .
- ^ Вайсштейн, Эрик В. «Отрицание» . mathworld.wolfram.com . Проверено 2 сентября 2020 .
- ^ a b Heyting (1929) Die formalen Regeln der intuitionistischen Logik .
- ^ Денис Рогель (2002), Краткий обзор логических обозначений 20-го века (см. Диаграмму на странице 2).
- ^ a b c d Рассел (1908) Математическая логика, основанная на теории типов (American Journal of Mathematics 30, p222–262, также в From Frege to Gödel под редакцией ван Хейеноорта).
- ^ Пеано (1889) Принципы арифметики, новая методика объяснения .
- ^ a b Schönfinkel (1924) Über die Bausteine der Mathematischen Logik , переведенный как « О строительных блоках математической логики» в «От Фреге к Геделю» под редакцией ван Хейеноорта.
- ^ Пирс (1867) Об улучшении логического исчисления Буля.
- ^ Гильберт (1917/1918) Prinzipien der Mathematik (примечания к курсу Бернейса).
- ^ Vax (1982) Lexique logique , Прессы Universitaires де Франс.
- ^ Тарский (1940) Введение в логику и методологию дедуктивных наук .
- ^ Генценовского (1934) Untersuchungen über дас Логических Schliessen .
- ^ Мудрецы (1996): ЭЛЕМЕНТЫ де logique formelle.
- ^ См. Roegel
- ^ Бохенского (1959), A конспект математической логики ,разных местах.
- ^ О'Доннелл, Джон; Холл, Корделия; Пейдж, Рекс (2007), Дискретная математика с использованием компьютера , Springer, стр. 120, ISBN 9781846285981.
- ^ Джексон, Дэниел (2012), Абстракции программного обеспечения: логика, язык и анализ , MIT Press, стр. 263, ISBN 9780262017152.
Рекомендации
- Бохенский, Юзеф Мария (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), « Логические константы », Стэнфордская энциклопедия философии .