Логическая дизъюнкция

Логическая дизъюнкция

ИЛИ
Определение	${\displaystyle x+y}$
Таблица истинности	${\displaystyle (1110)}$
Логический вентиль
Нормальные формы
Дизъюнктивный	${\displaystyle x+y}$
Соединительный	${\displaystyle x+y}$
Полином Жегалкина	${\displaystyle x\oplus y\oplus xy}$
Решетки Поста
0-сохраняющий	да
1-сохраняющий	да
Монотонный	да
Аффинный	нет
Самодвойственный	нет
в т е

Логические связки
НЕТ ${\displaystyle \neg A,-A,{\overline {A}},\sim A}$ И ${\displaystyle A\land B,A\cdot B,AB,A\ \&\ B,A\ \&\&\ B}$ НЕ-И ${\displaystyle A{\overline {\land }}B,A\uparrow B,A\mid B,{\overline {A\cdot B}}}$ ИЛИ ${\displaystyle A\or B,A+B,A\mid B,A\parallel B}$ НИ ${\displaystyle A{\overline {\lor }}B,A\downarrow B,{\overline {A+B}}}$ X-NOR-не ${\displaystyle A\odot B,{\overline {A{\overline {\lor }}B}}}$ └ эквивалент ${\displaystyle A\equiv B,A\Leftrightarrow B,A\leftrightharpoons B}$ XOR ${\displaystyle A{\underline {\lor }}B,A\oplus B}$ └неэквивалентный ${\displaystyle A\not \equiv B,A\not \Leftrightarrow B,A\nleftrightarrow B}$ подразумевает ${\displaystyle A\Стрелка вправо B,A\supset B,A\Стрелка вправо B}$ неподразумеваемый (NIMPLY) ${\displaystyle A\not \Rightarrow B,A\not \supset B,A\nrightarrow B}$ общаться ${\displaystyle A\Leftarrow B,A\subset B,A\leftarrow B}$ обратная неимпликация ${\displaystyle A\not \Leftarrow B,A\not \subset B,A\nleftarrow B}$
Связанные концепции
Пропозициональное исчисление Логика предикатов Булева алгебра Таблица истинности Функция истинности Булева функция Функциональная полнота Область действия (логика)
Приложения
Цифровая логика Языки программирования Математическая логика Философия логики
Категория
в т е

В логике дизъюнкция , также известная как логическая дизъюнкция , логическое или , логическое сложение или инклюзивная дизъюнкция , является логической связкой, обычно обозначаемой как и читаемой вслух как «или». Например, предложение на английском языке «it is sunny or it is warm» может быть представлено в логике с помощью дизъюнктивной формулы , предполагая, что сокращает «it is sunny» и сокращает «it is warm».${\displaystyle \лор }$${\displaystyle S\или W}$${\displaystyle S}$${\displaystyle W}$

В классической логике дизъюнкции придается истинностная функциональная семантика, согласно которой формула истинна, если оба и не ложны. Поскольку эта семантика позволяет дизъюнктивной формуле быть истинной, когда оба ее дизъюнкта истинны, она является инклюзивной интерпретацией дизъюнкции, в отличие от исключающей дизъюнкции . Классические теоретические трактовки доказательств часто даются в терминах правил, таких как введение дизъюнкции и устранение дизъюнкции . Дизъюнкции также даются многочисленные неклассические трактовки, мотивированные проблемами, включая аргумент Аристотеля о морском сражении , принцип неопределенности Гейзенберга , а также многочисленные несоответствия между классической дизъюнкцией и ее ближайшими эквивалентами в естественных языках . ^{[1] [2]}${\displaystyle \phi \lor \psi }$${\displaystyle \фи}$${\displaystyle \пси}$

Операндом дизъюнкции является дизъюнкт . ^[3]

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

Когда необходимо уточнить, подразумевается ли включающее или исключающее or , носители английского языка иногда используют фразу and/or . С точки зрения логики эта фраза идентична or , но делает включение обоих истинным явным.

В логике и смежных областях дизъюнкция обычно обозначается инфиксным оператором (Unicode U+2228 ∨ LOGICAL OR ). ^[1] Альтернативные обозначения включают , используемый в основном в электронике , а также и во многих языках программирования . Иногда также используется английское слово or , часто заглавными буквами. В префиксной нотации Яна Лукасевича для логики оператор — , сокращение от польского alternatywa (английский: альтернатива). ^[4]${\displaystyle \лор }$ ${\displaystyle +}$${\displaystyle \vert}$${\displaystyle \vert \!\vert }$${\displaystyle А}$

В математике дизъюнкция произвольного числа элементов может быть обозначена как итеративная бинарная операция с использованием большего ⋁ (Unicode U+22C1 ⋁ N-ARY LOGICAL OR ): ^[5]${\displaystyle a_{1},\ldots ,a_{n}}$

${\displaystyle \bigvee _{i=1}^{n}a_{i}=a_{1}\lor a_{2}\lor \ldots a_{n-1}\lor a_{n}}$

В семантике логики классическая дизъюнкция — это операция истинностного функционала , которая возвращает значение истинности true, если оба ее аргумента не являются false . Ее семантическая запись стандартно задается следующим образом: ^[a]

${\displaystyle \models \phi \lor \psi }$     если         или         или оба${\displaystyle \модели \фи}$${\displaystyle \models \psi }$

Эта семантика соответствует следующей таблице истинности : ^[1]

${\displaystyle А}$	${\displaystyle Б}$	${\displaystyle A\или B}$
Ф	Ф	Ф
Ф	Т	Т
Т	Ф	Т
Т	Т	Т

В классических логических системах, где логическая дизъюнкция не является примитивом, ее можно определить в терминах примитива и ( ) и не ( ) следующим образом:${\displaystyle \земля}$${\displaystyle \lnot}$

${\displaystyle A\lor B=\neg ((\neg A)\land (\neg B))}$.

В качестве альтернативы его можно определить в терминах подразумевает ( ), а не как: ^[6]${\displaystyle \to}$

${\displaystyle A\lor B=(\lnot A)\to B}$.

Последнее можно проверить с помощью следующей таблицы истинности:

${\displaystyle А}$	${\displaystyle Б}$	${\displaystyle \отрицательный А}$	${\displaystyle \neg A\rightarrow B}$	${\displaystyle A\или B}$
Ф	Ф	Т	Ф	Ф
Ф	Т	Т	Т	Т
Т	Ф	Ф	Т	Т
Т	Т	Ф	Т	Т

Его также можно определить исключительно с точки зрения :${\displaystyle \to}$

${\displaystyle A\or B=(A\to B)\to B}$.

Это можно проверить с помощью следующей таблицы истинности:

${\displaystyle А}$	${\displaystyle Б}$	${\displaystyle A\rightarrow B}$	${\displaystyle (A\rightarrow B)\rightarrow B}$	${\displaystyle A\или B}$
Ф	Ф	Т	Ф	Ф
Ф	Т	Т	Т	Т
Т	Ф	Ф	Т	Т
Т	Т	Т	Т	Т

К дизъюнкции применимы следующие свойства:

• Ассоциативность : ^[7]${\displaystyle a\lor (b\lor c)\equiv (a\lor b)\lor c}$
• Коммутативность :${\displaystyle a\lor b\equiv b\lor a}$
• Распределяемость :${\displaystyle (a\land (b\lor c))\equiv ((a\land b)\lor (a\land c))}$

${\displaystyle (a\lor (b\land c))\equiv ((a\lor b)\land (a\lor c))}$

${\displaystyle (а\lor (b\lor c))\equiv ((a\lor b)\lor (a\lor c))}$

${\displaystyle (a\lor (b\equiv c))\equiv ((a\lor b)\equiv (a\lor c))}$

• Идемпотентность :${\displaystyle a\lor a\equiv a}$
• Монотонность :${\displaystyle (a\rightarrow b)\rightarrow ((c\lor a)\rightarrow (c\lor b))}$

${\displaystyle (a\rightarrow b)\rightarrow ((a\lor c)\rightarrow (b\lor c))}$

• Сохранение истины : интерпретация, при которой всем переменным присваивается истинностное значение «истина», в результате дизъюнкции получается истинностное значение «истина».
• Сохранение ложности : интерпретация, при которой всем переменным присваивается значение истинности «ложь», в результате дизъюнкции получается значение истинности «ложь».

This section needs expansion. You can help by adding to it. (February 2021)

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

Дизъюнкция часто используется для побитовых операций . Примеры:

• 0 или 0 = 0
• 0 или 1 = 1
• 1 или 0 = 1
• 1 или 1 = 1
• 1010 или 1100 = 1110

Оператор orможно использовать для установки битов в битовом поле в 1, объединив orполе с константным полем, установив соответствующие биты в 1. Например, x = x | 0b00000001принудительно установит последний бит в 1, оставив остальные биты без изменений. ^{[ необходима цитата ]}

Во многих языках побитовая и логическая дизъюнкция различаются с помощью двух отдельных операторов; в языках, следующих за C , побитовая дизъюнкция выполняется с помощью оператора одинарной вертикальной линии ( |), а логическая дизъюнкция — с помощью оператора двойной вертикальной линии ( ||).

Логическая дизъюнкция обычно является короткозамкнутой ; то есть, если первый (левый) операнд оценивается как true, то второй (правый) операнд не оценивается. Таким образом, оператор логической дизъюнкции обычно представляет собой точку последовательности .

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

Хотя тип выражения логической дизъюнкции в большинстве языков является булевым (и, таким образом, может иметь только значение trueили false), в некоторых языках (таких как Python и JavaScript ) оператор логической дизъюнкции возвращает один из своих операндов: первый операнд, если он оценивается как истинное значение, и второй операнд в противном случае. ^{[8] [9]} Это позволяет ему выполнять роль оператора Элвиса .

Соответствие Карри–Ховарда связывает конструктивистскую форму дизъюнкции с маркированными типами объединения . ^{[ необходима ссылка ] [10]}

This section needs expansion. You can help by adding to it. (February 2021)

Принадлежность элемента множества объединения в теории множеств определяется в терминах логической дизъюнкции: . Вследствие этого логическая дизъюнкция удовлетворяет многим из тех же тождеств, что и теоретико-множественное объединение, таким как ассоциативность , коммутативность , дистрибутивность и законы де Моргана , отождествляющие логическую конъюнкцию с пересечением множеств , логическое отрицание с дополнением множеств . ^[11]${\displaystyle x\in A\cup B\Leftrightarrow (x\in A)\vee (x\in B)}$

Дизъюнкция в естественных языках не совсем соответствует интерпретации в классической логике. Примечательно, что классическая дизъюнкция является инклюзивной, в то время как дизъюнкция в естественном языке часто понимается исключительно, как это обычно бывает в следующем английском примере. ^[1]${\displaystyle \lor }$

• Мэри ест яблоко или грушу.

Этот вывод иногда понимался как вывод , например, Альфредом Тарским , который предположил, что дизъюнкция естественного языка неоднозначна между классической и неклассической интерпретацией. Более поздние работы в прагматике показали, что этот вывод может быть выведен как разговорная импликатура на основе семантического обозначения, которое ведет себя классически. Однако, дизъюнктивные конструкции, включая венгерское vagy... vagy и французское soit... soit , как утверждается, являются по своей сути исключительными, делая неграмматичными в контекстах, где в противном случае было бы вынуждено инклюзивное прочтение. ^[1]

Похожие отклонения от классической логики были отмечены в таких случаях, как свободная дизъюнкция и упрощение дизъюнктивных антецедентов , где определенные модальные операторы вызывают конъюнктивную интерпретацию дизъюнкции. Как и в случае с исключительностью, эти выводы анализировались как импликатуры, так и следствия, возникающие из неклассической интерпретации дизъюнкции. ^[1]

• Вы можете съесть яблоко или грушу.

${\displaystyle \rightsquigarrow }$Вы можете съесть яблоко и грушу (но не оба).

Во многих языках разделительные выражения играют роль в формировании вопроса.

• Мэри — философ или лингвист?

Например, хотя приведенный выше пример на английском языке можно интерпретировать как полярный вопрос о том, правда ли, что Мэри является либо философом, либо лингвистом, его также можно интерпретировать как альтернативный вопрос о том, какая из двух профессий принадлежит ей. Роль дизъюнкции в этих случаях была проанализирована с использованием неклассических логик, таких как альтернативная семантика и пытливая семантика , которые также были приняты для объяснения выводов свободного выбора и упрощения. ^[1]

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

• Джордж Буль , внимательно следуя аналогии с обычной математикой, предположил, как необходимое условие определения x + y, что x и y являются взаимоисключающими. Джевонс и практически все математические логики после него, отстаивали, на различных основаниях, определение логического сложения в форме, которая не требует обязательного взаимоисключения.

• «Дизъюнкция», Энциклопедия математики , EMS Press , 2001 [1994]
• Алони, Мария . «Дизъюнкция». В Zalta, Edward N. (ред.). Стэнфордская энциклопедия философии .
• Эрик В. Вайсштейн. «Дизъюнкция». Из MathWorld — веб-ресурс Wolfram