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

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

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

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

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

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

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

На языке

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• это нет дождь (${displaystyle eg}$п)
• Идет дождь и Я в помещении (${displaystyle Pwedge Q}$)
• Идет дождь или же Я в помещении (${displaystyle Plor Q}$)
• Если идет дождь, тогда Я в помещении (${displaystyle Pightarrow Q}$)
• Если Я в помещении, тогда идет дождь (${displaystyle Qightarrow P}$)
• Я в помещении если и только если идет дождь (${displaystyle Pleftrightarrow Q}$)

Также принято рассматривать всегда правда формула и всегда ложь формула быть связной:^[1]

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

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

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

Некоторые авторы использовали буквы для связок в какой-то момент истории: u. для соединения (немецкий "und" для "и") и о. для дизъюнкции (немецкая «oder» для «или») в более ранних работах Гильберта (1904); Nп для отрицания, Kpq для соединения, Dpq за альтернативное отрицание, Аpq для дизъюнкции, Иксpq за совместное отрицание, Cpq для импликации, Epq для двусмысленной Лукасевич (1929);^[16] ср. Польская нотация.

Резервирование

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

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

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

Один элемент

{↑}, {↓}.

Два элемента

${displaystyle {vee, eg}}$, ${displaystyle {клин, например}}$, ${displaystyle {o, eg}}$, ${displaystyle {получает, например}}$, ${displaystyle {o, ot}}$, ${displaystyle {gets, ot}}$, ${displaystyle {o, leftrightarrow}}$, ${displaystyle {gets, leftrightarrow}}$, ${displaystyle {o, rightarrow}}$, ${displaystyle {o, leftarrow}}$, ${displaystyle {gets, rightarrow}}$, ${displaystyle {gets, leftarrow}}$, ${displaystyle {rightarrow, eg}}$, ${displaystyle {leftarrow, например}}$, ${displaystyle {rightarrow, op}}$, ${displaystyle {leftarrow, op}}$, ${displaystyle {rightarrow, leftrightarrow}}$, ${displaystyle {leftarrow, leftrightarrow}}$.

Три элемента

${displaystyle {lor, leftrightarrow, ot}}$, ${displaystyle {lor, leftrightarrow, leftrightarrow}}$, ${displaystyle {lor, leftrightarrow, op}}$, ${displaystyle {land, leftrightarrow, ot}}$, ${displaystyle {land, leftrightarrow, leftrightarrow}}$, ${displaystyle {land, leftrightarrow, op}}$.

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

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

Характеристики

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

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

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

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

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

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

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

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

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

Абсорбция

Пара связок ∧, ∨ удовлетворяет закону поглощения, если ${displaystyle aland (alor b) = a}$ для всех операндов а, б.

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

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

Близость

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

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

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

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

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

Сохранение лжи

Сложность всех этих аргументов противоречия само противоречие. Например, ∨, ∧, ${displaystyle leftrightarrow}$, ⊥, ⊄, ⊅ (см. срок действия ).

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

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

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

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

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

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Март 2012 г.)

Порядок старшинства

Чтобы сократить количество необходимых скобок, можно ввести правила приоритета: ¬ имеет более высокий приоритет, чем ∧, ∧ выше, чем ∨, и ∨ выше, чем →. Так, например, ${displaystyle Pvee Qwedge {например, R} ightarrow S}$ это сокращение от ${displaystyle (Pvee (Qwedge (например, R))) ightarrow S}$.

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

${displaystyle {egin {array} {c | c} {ext {Operator}} & {ext {Precedence}} hline eg & 1 land & 2 vee & 3 o & 4 leftrightarrow & 5end {array}}}$

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

Информатика

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Март 2012 г.)

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

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

Смотрите также

Примечания

Рекомендации

• Бохенский, Юзеф Мария (1959), Краткое изложение математической логики, перевод с французского и немецкого изданий Отто Берда, Д. Рейделя, Дордрехт, Южная Голландия.
• Эндертон, Герберт (2001), Математическое введение в логику (2-е изд.), Бостон, Массачусетс: Academic Press, ISBN  978-0-12-238452-3
• Гамут, L.T.F (1991), «Глава 2», Логика, язык и смысл, 1, University of Chicago Press, стр. 54–64, OCLC  21372380
• Раутенберг, В. (2010), Краткое введение в математическую логику (3-е изд.), Нью-Йорк: Springer Science + Business Media, Дои: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) "Связные предложения в формальной логике ", Стэнфордская энциклопедия философии (An абстрактная алгебраическая логика подход к связкам.)
• Джон Макфарлейн (2005) "Логические константы ", Стэнфордская энциклопедия философии.