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

Logical connective OR

Диаграмма Венна ${\displaystyle \scriptstyle A\lor B\lor C}$

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

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

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

Инклюзивная и исключающая дизъюнкция

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

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

Обозначение

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

В математике дизъюнкция произвольного числа элементов может быть обозначена как итеративная бинарная операция с использованием большего ⋁ (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 \models \phi }$ ${\displaystyle \models \psi }$

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

Определено другими операторами

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

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

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

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

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

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

${\displaystyle A\lor B=(A\to B)\to 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 (a\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))}$

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

Приложения в области компьютерных наук

Логический вентиль ИЛИ

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

Побитовая операция

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

• 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]}

Теория множеств

Принадлежность элемента множества объединения в теории множеств определяется в терминах логической дизъюнкции: . Вследствие этого логическая дизъюнкция удовлетворяет многим из тех же тождеств, что и теоретико-множественное объединение, таким как ассоциативность , коммутативность , дистрибутивность и законы де Моргана , отождествляющие логическую конъюнкцию с пересечением множеств , логическое отрицание с дополнением множеств . ^[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]

Джонш

Джон- НОМ

Биллш

Билл- НОМ

vʔaawuumšaa

3 -прийти- PL - FUT - INFER

Johnš Billš vʔaawuumšaa

John-NOM Bill-NOM 3-come-PL-FUT-INFER

«Джон или Билл придут».

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

• Утверждение дизъюнкта
• Булева алгебра (логика)
• Темы Булевой алгебры
• Булев домен
• Булева функция
• Булева функция
• Двойственность конъюнкции/дизъюнкции
• Дизъюнктивный силлогизм
• Неравенства Фреше
• Свободный выбор вывода
• Дизъюнкция Херфорда
• Логический граф
• Упрощение дизъюнктивных антецедентов

Примечания

1. Ради общности в классических системах эта запись подавляет параметры оценки. Двойной символ турникета здесь означает «семантически влечет». ${\displaystyle \models }$

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

Ссылки

1. Aloni, Maria (2016), «Дизъюнкция», в Zalta, Edward N. (ред.), The Stanford Encyclopedia of Philosophy (зима 2016 г.), Metaphysics Research Lab, Stanford University , получено 03.09.2020
2. "Дизъюнкция | логика". Encyclopedia Britannica . Получено 2020-09-03 .
3. Beall, Jeffrey C. (2010). Логика: основы . Основы (1-е изд.). Лондон: Routledge. С. 57. ISBN 978-0-203-85155-5.
4. Юзеф Мария Боченский (1959), Краткое изложение математической логики , перевод Отто Берда из французского и немецкого изданий, Дордрехт, Северная Голландия: Д. Рейдель, passim.
5. Weisstein, Eric W. "OR". MathWorld--A Wolfram Web Resource . Получено 24 сентября 2024 г.
6. Валицкий, Михал (2016). Введение в математическую логику. МИРОВАЯ НАУЧНАЯ. п. 150. дои : 10.1142/9783. ISBN 978-9814343879.
7. Howson, Colin (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Routledge. стр. 38. ISBN 978-0-415-13342-5.
8. "Python 3.12.1 Documentation - The Python Language Reference - 6.11 Boolean operations" . Получено 25 декабря 2023 г. .
9. "JavaScript References - Expressions & Operators - Logical AND (&&)". 25 сентября 2023 г. Получено 25 декабря 2023 г.
10. Маркус Винисиус Мидена Рамос; де Кейроз, Руи ЖГБ (2015). «Формализация теории бесконтекстного языка». Федеральный университет Пернамбуку : 6. arXiv : 1505.00061 .
11. Эббингауз, Хайнц-Дитер (2021). Einführung in die Mengenlehre (на немецком языке) (5-е изд.). Спрингер. п. 32. ISBN 978-3-662-63865-1.

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

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