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

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

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

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

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

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

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

На языке [ править ]

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

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

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

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

Формальные языки [ править ]

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

С помощью логических связок можно связать более двух операторов, поэтому можно говорить о 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
Дополнительная информация

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

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

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

Альтернативные названия biconditional являются тогда и только тогда , 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}$

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

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

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

• Отрицание: символ ¬ появился у Гейтинга в 1929 году ^{[5] [6]} (сравните с символом Фреге ⫟ в его Begriffsschrift ); символ ~ появился у Рассела в 1908 году; ^[7] альтернативное обозначение - добавить горизонтальную черту вверху формулы, как в ; ^[1] другое альтернативное обозначение - использовать символ штриха, как в P '.${\displaystyle {\overline {P}}}$
• Соединение: символ ∧ появился у Гейтинга в 1929 году ^[5] (сравните с использованием Пеано теоретико-множественной записи пересечения ∩ ^[8] ); символ & появился, по крайней мере, в Шенфинкеле в 1924 году; ^[9] символ. происходит из интерпретации Буля логики как элементарной алгебры .
• Дизъюнкция: символ ∨ появился у Рассела в 1908 году ^[7] (сравните с использованием Пеано теоретико-множественной записи объединения ∪); символ + также используется, несмотря на двусмысленность, проистекающую из того факта, что + обычной элементарной алгебры является исключительным или при логической интерпретации в двухэлементном кольце ; точечно в истории а + вместе с точкой в нижнем правом углу был использован Пирса , ^[10]
• Следствие: символ → можно увидеть у Гильберта в 1917 году; ^[11] ⊃ использовался Расселом в 1908 году ^[7] (сравните с перевернутой С-нотацией Пеано); ⇒ использовался в 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 \{\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 \{\land ,\leftrightarrow ,\bot \}}$${\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}$${\displaystyle \{\land ,\nleftrightarrow ,\top \}}$

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

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

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

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

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

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

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

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

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

Связка, обозначенная ·, распределяется по другой связке, обозначенной +, если 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), « Логические константы », Стэнфордская энциклопедия философии .