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

Логическая дизъюнкция
ИЛИ
Определение
Таблица истинности
Логический вентиль
Нормальные формы
Дизъюнктивный
соединительный
Полином Жегалкина
Решетки постовые
0-сохраняющий	да
1-сохраняющий	да
монотонный	да
Аффинный	нет
Самодвойственный	нет
	v ; т ; и ;

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

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

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

Инклюзивная и исключительная дизъюнкция

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

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

Обозначения

В логике и смежных областях дизъюнкция обычно обозначается инфиксным оператором. $\lor$ (Юникод U + 2228 ∨ ЛОГИЧЕСКОЕ ИЛИ ). ^{[ 1 ]} Альтернативные обозначения включают $+$ , используемый в основном в электронике , а также $\vert$ и $\vert \!\vert$ во многих языках программирования . Иногда также используется английское слово «или», часто написанное заглавными буквами. В Яна Лукасевича префиксной записи логики оператор $A$ , сокращение от польского alternatywa (англ. alternatywa). ^{[ 4 ]}

Классическая дизъюнкция

Семантика

В семантике логики классическая дизъюнкция — это истинности функциональная операция , которая возвращает значение истинности «истина», если оба ее аргумента не являются «ложными». Его семантическая запись стандартно задается следующим образом: ^{[ 5 ]}

\models \phi \lor \psi

если

\models \phi

или

\models \psi

или оба

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

$A$	$B$	$A\lor B$
Ф	Ф	Ф
Ф	Т	Т
Т	Ф	Т
Т	Т	Т

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

В классических логических системах, где логическая дизъюнкция не является примитивом, ее можно определить через примитивы « и » ( $\land$ ) и « не » ( $\lnot$ ) как:

A\lor B=\neg ((\neg A)\land (\neg B))

.

Альтернативно, это может быть определено в терминах « подразумевается » ( $\to$ ) и «не» как: ^{[ 6 ]}

A\lor B=(\lnot A)\to B

.

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

$A$	$B$	$\neg A$	$\neg A\rightarrow B$	$A\lor B$
Ф	Ф	Т	Ф	Ф
Ф	Т	Т	Т	Т
Т	Ф	Ф	Т	Т
Т	Т	Ф	Т	Т

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

A\lor B=(A\to B)\to B

.

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

$A$	$B$	$A\rightarrow B$	$(A\rightarrow B)\rightarrow B$	$A\lor B$
Ф	Ф	Т	Ф	Ф
Ф	Т	Т	Т	Т
Т	Ф	Ф	Т	Т
Т	Т	Т	Т	Т

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

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

Ассоциативность : $a\lor (b\lor c)\equiv (a\lor b)\lor c$ ^{[ 7 ]}
Коммутативность : $a\lor b\equiv b\lor a$
Дистрибутивность : $(a\land (b\lor c))\equiv ((a\land b)\lor (a\land c))$

(a\lor (b\land c))\equiv ((a\lor b)\land (a\lor c))

(a\lor (b\lor c))\equiv ((a\lor b)\lor (a\lor c))

(a\lor (b\equiv c))\equiv ((a\lor b)\equiv (a\lor c))

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

(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

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

Логическая операция

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

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

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

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

Конструктивная дизъюнкция

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

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

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

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

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

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

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

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

Можно яблоко или грушу.

\rightsquigarrow

У вас может быть яблоко и груша (но вы не можете иметь оба)

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

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

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

Джонш

Джон- НОМ

Счет

Билл- ИМЯ

ваавуумшаа

3 -приходите- ПЛ - ФУТ - ИНФЕР

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

См. также

Примечания

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

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Алони, Мария (2016), «Расхождение» , в Залте, Эдвард Н. (ред.), Стэнфордская энциклопедия философии (изд. зимы 2016 г.), Лаборатория метафизических исследований, Стэнфордский университет , получено 3 сентября 2020 г.
^ «Дизъюнкция | логика» . Британская энциклопедия . Проверено 3 сентября 2020 г.
^ Билл, Джеффри С. (2010). Логика: основы . Основы (1. изд.). Лондон: Рутледж. п. 57. ИСБН 978-0-203-85155-5 .
^ Юзеф Мария Боченский (1959), Точная математическая логика , перевод Отто Берда из французского и немецкого изданий, Дордрехт, Северная Голландия: Д. Рейдель, passim.
^ В целях общности для классических систем в этой записи не указаны параметры оценки. « двойной турникет ». Символ $\models$ здесь означает «семантически влечет за собой».
^ Валицкий, Михал (2016). Введение в математическую логику . МИРОВАЯ НАУЧНАЯ. стр. 150. дои : 10.1142/9783 . ISBN 978-9814343879 .
^ Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Рутледж. п. 38. ISBN 978-0-415-13342-5 .
^ «Документация Python 3.12.1 — Справочник по языку Python — 6.11 Логические операции» . Проверено 25 декабря 2023 г.
^ «Справочники по JavaScript – Выражения и операторы – Логическое И (&&)» . 25 сентября 2023 г. Проверено 25 декабря 2023 г.
^ Маркус Винисиус Мидена Рамос; де Кейроз, Руи ЖГБ (2015). «Бесконтекстное обучение теории языка». Федеральный университет Пернамбуку : 6. arXiv : 1505.00061 .
^ Эббингауз, Хайнц-Дитер (2021). Введение в теорию множеств (на немецком языке) (5-е изд.). Спрингер. п. 32. ISBN 978-3-662-63865-1 .

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

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

[:1-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Алони, Мария (2016), «Расхождение» , в Залте, Эдвард Н. (ред.), Стэнфордская энциклопедия философии (изд. зимы 2016 г.), Лаборатория метафизических исследований, Стэнфордский университет , получено 3 сентября 2020 г.

[2] «Дизъюнкция | логика» . Британская энциклопедия . Проверено 3 сентября 2020 г.

[:21-3] Билл, Джеффри С. (2010). Логика: основы . Основы (1. изд.). Лондон: Рутледж. п. 57. ИСБН 978-0-203-85155-5 .

[4] Юзеф Мария Боченский (1959), Точная математическая логика , перевод Отто Берда из французского и немецкого изданий, Дордрехт, Северная Голландия: Д. Рейдель, passim.

[5] В целях общности для классических систем в этой записи не указаны параметры оценки. « двойной турникет ». Символ $\models$ здесь означает «семантически влечет за собой».

[6] Валицкий, Михал (2016). Введение в математическую логику . МИРОВАЯ НАУЧНАЯ. стр. 150. дои : 10.1142/9783 . ISBN 978-9814343879 .

[:13-7] Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Рутледж. п. 38. ISBN 978-0-415-13342-5 .

[8] «Документация Python 3.12.1 — Справочник по языку Python — 6.11 Логические операции» . Проверено 25 декабря 2023 г.

[9] «Справочники по JavaScript – Выражения и операторы – Логическое И (&&)» . 25 сентября 2023 г. Проверено 25 декабря 2023 г.

[10] Маркус Винисиус Мидена Рамос; де Кейроз, Руи ЖГБ (2015). «Бесконтекстное обучение теории языка». Федеральный университет Пернамбуку : 6. arXiv : 1505.00061 .

[11] Эббингауз, Хайнц-Дитер (2021). Введение в теорию множеств (на немецком языке) (5-е изд.). Спрингер. п. 32. ISBN 978-3-662-63865-1 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

v т и Общие логические связи
Tautology/True $\top$
Alternative denial (NAND gate) $\uparrow$ Converse implication $\leftarrow$ Implication (IMPLY gate) $\rightarrow$ Disjunction (OR gate) $\lor$
Negation (NOT gate) $\neg$ Exclusive or (XOR gate) $\not \leftrightarrow$ Biconditional (XNOR gate) $\leftrightarrow$ Statement (Digital buffer)
Joint denial (NOR gate) $\downarrow$ Nonimplication (NIMPLY gate) $\nrightarrow$ Converse nonimplication $\nleftarrow$ Conjunction (AND gate) $\land$
Contradiction/False $\bot$
Philosophy portal