Что такое логическая связка

ЛОГИЧЕСКИЕ СВЯЗКИ

ЛОГИЧЕСКИЕ СВЯЗКИ — символы логических языков, используемые для образования сложных высказываний (формул) из элементарных. Логическими связками называют также соответствующие этим символам союзы естественного языка. Обычно используются такие логические связки, как конъюнкция (союз «и», символические обозначения: &, л и точка в виде знака умножения, которые часто опускают, записывая конъюнкцию А и В как AB), дизъюнкция (нестрогий союз «или», обозначается как «v»), импликация («если…, то», обозначается с помощью знака отрицание («неверно, что…», обозначается: -ι, ЛОГИЧЕСКИЕ СВЯЗКИ или чертой над отрицаемым выражением). Из перечисленных отрицание является одноместной (унарной) связкой. Другие являются двухместными (бинарными). В принципе логические связки могут быть сколь угодно местными, но на практике более, чем бинарные, используются очень редко. В классической логике (Логика, Логика высказываний) любые многоместные логические связки выразимы через перечисленные. Некоторый практический смысл дает использование тернарной логической связки, называемой условной дизъюнкцией, связывающей три высказывания А, В и С и означающей, что «А в случае В, и С в случае нв-?» или формально: (В з А)&(-, В э О (Сидоренко Е. А. Пропозициональное исчисление с условной дизъюнкцией.- В кн.: Методы логического анализа. М.,1977).

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

ниях 1 (истинно) и 0 (ложно) высказывания А и В могут иметь четыре возможных набора упорядоченных истинностных зна^ чений: , , , . Пропозициональная истинностная функция ставит в соответствие каждому перечисленному набору одно из значений истинности — 1 или 0. Всгго таких функций 16. Конъюнкция приписывает выражению А&.В значение 1 только в случае, когда как Л, так и В истинны, т. е. оба имеют значение 1, в остальных случаях значение А&.В равно 0. Дизъюнкция Α ν В, напротив, ложна только в одном случае, когда ложны как А, так и В. Импликация А э В является ложной только при истинном (антецеденте) А и ложном (консеквенте) В. В остальных случаях А => В принимает значение 1. Из четырех одноместных функций интерес представляет только отрицание, меняющее значение высказывания на противоположное: когда А — истинно, -А — ложно, и наоборот. Все другие унарные и бинарные классические функции могут быть выражены через представленные. Когда принятая в соответствующей семантике система логических связок позволяет дать определение всех остальных, ее называют функционально полной. К полным системам в классической логике относятся, в частности, конъюнкция и отрицание; дизъюнкция и отрицание; импликация и отрицание. Конъюнкция и дизъюнкция определимы друг через друга за счет эквивалентностей (А&В) = -i(-i/4v-i.ß) и (A v В) a -,(-Α&-ιΒ), именуемых законами де Моргана, а также: (A^B)s(-iA^ В), (А&В) s -,(А э -ιΒ), (Α ν В) = ((А => В) •зА). Любая эквивалентность видаЛ = В имеет силу только тогда, когда общезначима (всегда истинна) конъюнкция (А =) В)&(В э А).

Функции антидизъюнкция и антиконъюнкция, определимые соответственно как -ι(Α ν В) и -(А&.В), также представляют каждая в отдельности функционально полную систему связок. Это последнее обстоятельство было известно уже Ч. Пирсу (неопубликованная при его жизни работа 1880 г.) и было переоткрыто X. Шеффером (H. M. Shefier). Используя антидизъюнкцию как единственную логическую связку, Шеффер в 1913 построил полное исчисление высказываний. Антидизъюнкцию обозначают А В и называют штрихом Ше4)фера, читая данное выражение, как «не-Д и не-В». Ж. Нико (J. G. P. Nicod) употребил то же обозначение для антиконъюнкции («Неверно, что одновременно А и В») и с помощью только этой связки в 1917 сформулировал полное исчисление высказываний с одной (всего!) аксиомой и одним правилом вывода. Т. о., штрихом Шеффера называют по сути саму вертикальную черту, которая у разных авторов может обозначать как антидизъюнкцию, так и антиконъюнкцию.

Экстенсиональность логических связок придает им однозначность, упрощает проблему построения логических исчислений, дает возможность решать для последних метатеоретические проблемы непротиворечивости, разрешимости, полноты (см. Металогика). Однако в некоторых случаях истинностно-функциональная трактовка связок приводит к значительному несоответствию с тем, как они понимаются в естественном языке. Так, указанная истинностная интерпретация импликации вынуждает признавать верными предложения вида «Если А, то В» даже в том случае, когда между высказываниями А и В (и, соответственно, событиями, о которых в них идет речь) нет никакой реальной связи. Достаточно, чтобы А было ложным или В — истинным. Поэтому из двух предложений: «Если А, то В» и «Если В, то А», по крайней мере одно приходится признавать верным, что плохо сообразуется с обычным употреблением условной связки. Импликацию в данном случае специально называют «материальной», отличая ее тем самым от условного союза, предполагающего, что между антецедентом и консеквентом истинного условного высказывания имеется действительная связь. При этом материальная импликация может прекрасно использоваться во многих контекстах, напр., математических, когда при этом не забывают о ее специфических особенностях. В некоторых случаях, однако, именно контекст не позволяет трактовать условный союз как материальную импликацию, предполагая взаимосвязь высказываний. Для анализа таких контекстов приходится строить специальные неклассические логики, напр., релевантные (см. Релевантная логика), в язык которых вместо материальной импликации (или наряду с ней) вводятся другие импликации, которые понимаются интенсионально (содержательно) и верность которых не может быть обоснована истинностно-функционально. Интенсионально могут трактоваться также другие логические связки.

Лит.: Чёрч Л. Введение в математическую логику, т. 1. M., 1960; КарриХ. Основания математической логики. М., 1969.

Ε. А. Сидоренко

Новая философская энциклопедия: В 4 тт. М.: Мысль. Под редакцией В. С. Стёпина. 2001.

Источник

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

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

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

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

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

На языке

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

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

1. Джек поднялся на холм.
2. Джилл поднялась на холм.
3. Джек поднялся на холм, а Джилл поднялась на холм.
4. Джек поднялся на холм, а Джилл поднялась на холм.

Обратите внимание в приведенном выше списке предложений, что те, что отмечены C и D, используют слова и и так далее. Эти слова называются грамматическими союзами, потому что они соединяют два предложения (A) и (B), образуя составные предложения (C) и (D). Слово и в предложении (C) является логической связкой. Обратите внимание, что истинность (C) как составного слова либо истинна, либо ложна. Но (C) полностью определяется тем, какая истина обнаруживается для более простого предложения (A), более простого предложения (B) и логического определения и. Было бы бессмысленно и нарушать правила логики, чтобы утверждать (A) истинно и (B) истинно, но отрицать, что (C) истинно. Однако слово так в (D) не является логической связкой, так как было бы вполне разумно утверждать (A) и (B), но отрицать (D): возможно, в конце концов, Джилл поднялась на холм за ведром. воды не потому, что Джек поднялся на холм.

Различные английские слова и пары слов выражают логические связки, и некоторые из них являются синонимами. К ним, среди прочего, относятся:

Формальные языки

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

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

Общие логические связки

Список общих логических связок

Обычно используемые логические связки включают:

• Отрицание (не) : ¬ , N (префикс), ~
• Конъюнкция (и) : ∧, K (префикс), &, ∙
• Дизъюнкция (или) : ∨, A (префикс)
• Материальное значение (если … то) : →, C (префикс), ⇒, ⊃
• Biconditional (если и только если) : ↔, E (префикс), ≡, =

Альтернативные имена для двусмысленных являются если и только если, xnor и двусмысленность.

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

Также часто считается, что формула всегда истинная и всегда ложная формула соединительны:

• Верно формула (⊤, 1, V [префикс] или T)
• Ложь формула (⊥, 0, O [префикс] или F)

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

• Отрицание: символ ¬ появился в Гейтинг в 1929 году (сравните с Фреге ⫟ в его Begriffsschrift ); символ ~ появился в Расселе в 1908 г .; альтернативное обозначение — добавить горизонтальную черту поверх формулы, как в P ¯ { displaystyle { overline {P}}} ; другое альтернативное обозначение — использовать простой символ , как в P ‘.
• Соединение: символ ∧ появился в Гейтинге в 1929 году (сравните с использованием Пеано теоретико-множественное обозначение пересечения ∩); символ & появился по крайней мере в Шёнфинкеле в 1924 г .; символ . происходит из интерпретации логики Булевым как элементарной алгебры .
• Дизъюнкция: символ ∨ появился в Рассел в 1908 году (сравните с Пеано Использование теоретико-множественной записи union ∪); символ + также используется, несмотря на двусмысленность, проистекающую из того факта, что + обычной элементарной алгебры является исключающим или при логической интерпретации в двухэлементном кольцо ; точечно в истории Пирс ,
• использовал знак + вместе с точкой в ​​правом нижнем углу. Следствие: символ → можно увидеть в Гильберте в 1917 году; ⊃ использовался Расселом в 1908 году (сравните с перевернутой нотацией C Пеано); ⇒ использовалось в Vax.
• Biconditional: символ ≡ использовался, по крайней мере, Расселом в 1908 году; ↔ использовался как минимум Тарским в 1940 г .; ⇔ использовалось в Vax; другие символы появлялись в истории точно так же, как ⊃⊂ в Gentzen , ~ в Schönfinkel или ⊂⊃ в Chazal.
• Верно: символ 1 происходит от Boole интерпретация логики как элементарной алгебры над двухэлементной булевой алгеброй ; другие обозначения включают ⋀ { displaystyle bigwedge} (можно найти в Пеано).
• Ложь: символ 0 также происходит из интерпретации логики Буля как кольца; другие обозначения включают ⋁ { displaystyle bigvee} (можно найти в Пеано).

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

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

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

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

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

Один элемент {↑}, {↓}. Два элемента {∨, ¬} { 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 { земля, leftrightarrow, bot }} , {∧, ↔, ↮} { displaystyle { land, leftrightarrow, nleftrightarrow }} , {∧, ↮, ⊤} { displaystyle { land, nleftrightarrow, top }} .

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

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

Свойства

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

Ассоциативность В выражении, содержащем две или более одинаковых ассоциативных связки подряд, порядок операций не имеет значения, пока последовательность операнды не изменяются. Коммутативность Операнды связки можно менять местами, сохраняя логическую эквивалентность исходному выражению. Дистрибутивность Связка, обозначенная ·, распределяется по другой связке, обозначенной +, если a · (b + c) = (a · b) + (a · c) для всех операндов a, b, c. Идемпотентность Когда операнды операции совпадают, соединение логически эквивалентно к операнду. Поглощение Пара связок ∧, ∨ удовлетворяет закону поглощения, если a ∧ (a ∨ b) = a { displaystyle a land (a lor b) = a} для всех операндов 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 . Например, ∨, ∧, ⊤, ⊥. Сходство Каждая переменная всегда влияет на истинностное значение операции или никогда не имеет значения. Например, ¬, ↔, ↮ { displaystyle nleftrightarrow} , ⊤, ⊥. Двойственность Чтобы прочитать назначения истинностных значений для операции сверху вниз на ее таблица истинности аналогична чтению дополнения таблицы той же или другой связки снизу вверх. Не обращаясь к таблицам истинности, его можно сформулировать как g̃ (¬a 1 , …, ¬a n ) = ¬g (a 1 ,. .., a n ). Например, ¬. Сохранение истины Составной частью всех этих аргументов являются тавтологии, тавтология сама по себе. Например, ∨, ∧, ⊤, →, ↔, ⊂ (см. действительность). сохранение ложности Все эти аргументы состоят из противоречий само по себе противоречие. Например, , ∨, ∧, ↮ { displaystyle nleftrightarrow} , ⊥, ⊄, ⊅ (см. validity ). Involutivity (для унарных связок) f (f (a)) = a. Например, отрицание в классической логике.

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

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

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

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

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

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

Приоритет оператора ¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5 { displaystyle { begin {array} {c | c} { text {Operator}} & { text {Precedence}} \ hline neg & 1 \ land & 2 \ vee & 3 \ к & 4 \ leftrightarrow & 5 end {array}}}

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

Информатика

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

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

См. Также

Примечания

Ссылки

• Бохенский , Józef Maria (1959), A Précis of Mathematical Logic, перевод с французского и немецкого изданий Отто Берда, Д. Рейделя, Дордрехт, Южная Голландия.
• Enderton, Herbert (2001), A Математическое введение в логику (2-е изд.), Бостон, Массачусетс: Academic Press, ISBN978-0-12-238452-3
• Gamut, LTF (1991), » Глава 2 », Логика, язык и значение, 1 , University of Chicago Press, стр. 54-64, OCLC21372380
• Раутенберг, W. (2010), Краткое введение в математическую логику (3-е изд.), Нью-Йорк : Springer Science + Business , doi : 10.1007 / 978-1-44 19-1221-3 , ISBN978-1-4419-1220-6 .

Дополнительная литература

• Ллойд Хамберстон (2011). Связки. MIT Press. ISBN978-0-262-01654-4 .

Внешние ссылки

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

Источник