Дизъюнкция сложение. Логические операции. Дизъюнкция, конъюнкция и отрицание. Обозначения для логических связок

вид сложного суждения, образованного из простых суждений при помощи союза «или». Дизъюнкция бывает нестрогой, когда ее элементы (входящие в нее простые суждения) друг друга не исключают.

Отличное определение

Неполное определение ↓

ДИЗЪЮНКЦИЯ

от лат. disjunctio - разобщение, различение)

Логическая операция - аналог употребления союза "или" в обычном языке, с помощью которой из двух или более исходных суждений строится новое суждение. Так, из суждений "Он - способен" и "Он - прилежен" с помощью операции "или" можно получить новое суждение "Он способен или он прилежен" (1). Из суждений "Он совершил преступление", "Он не совершал преступления" с помощью "или" можно получить новое суждение "Он совершил преступление или он не совершал преступления" (2). Суждение (1) истинно в трех случаях: 1) когда какой-то человек оказывается способным, но не прилежным; 2) когда этот человек оказывается прилежным, но не способным; 3) когда установлено, что этот человек и способен, и прилежен. Оно является ложным, когда оказалось, что этот человек не является ни способным, ни прилежным. Суждения типа (1) в логике называют соединительно-разделительными. Суждение же (2) истинно лишь только в том случае, когда имеет место или только первая ситуация ("Он совершил преступление"), или только вторая ситуация ("Он не совершал преступления"). Суждение (2) не допускает, чтобы имели место обе ситуации. Суждения типа (2) носят название исключающе-разделительных или строго разделительных.

Дизъюнкция

Дизъю́нкция - (лат. disjunctio - разобщение) логическая операция , по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу». Синонимы: логи́ческое «ИЛИ» , включа́ющее «ИЛИ» , логи́ческое сложе́ние , иногда просто «ИЛИ» .

Дизъюнкция может быть бинарной операцией, то есть, иметь два операнда, тернарной операцией, то есть иметь три операнда или n-арной операцией, то есть иметь n операндов.
Запись может быть префиксной - знак операции стоит перед операндами (польская запись), инфиксной - знак операции стоит между операндами или постфиксной - знак операции стоит после операндов. При числе операндов более 2-х префиксная и постфиксная записи экономичнее.
Чаще всего встречаются следующие варианты записи:
|| | .

Булева алгебра

Определение.
Логическая функция MAX в двухзначной (двоичной) логике называется дизъюнкция (логи́ческое "ИЛИ" , логи́ческое сложе́ние или просто "ИЛИ" ).
Правило: результат равен наибольшему операнду.
Описание.
В булевой алгебре дизъюнкция - это функция двух, трёх или более переменных (они же - операнды операции, они же - аргументы функции).
Правило: результат равен , если все операнды равны ; во всех остальных случаях результат равен .

Таблица истинности

Таблица истинности для тернарной (трёхоперандной) дизъюнкции:

X	Y	Z	X Y Z
0	0	0	0
1	0	0	1
0	1	0	1
1	1	0	1
0	0	1	1
1	0	1	1
0	1	1	1
1	1	1	1

Многозначная логика

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

Следует отметить, что название этой операции максимум имеет смысл в логиках с любой значностью, в том числе и в двоичной логике, а названия дизъюнкция , логи́ческое "ИЛИ" , логическое сложе́ние и просто "ИЛИ" имеют смысл только в двоичной логике, а при переходе к многозначным логикам теряют смысл.

Классическая логика

В классическом исчислении высказываний свойства дизъюнкции определяются с помощью аксиом . Классическое исчисление высказываний может быть задано разными системами аксиом, и некоторые из них будут описывать свойства дизъюнкции. Один из самых распространённых вариантов включает 3 аксиомы для дизъюнкции:

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

Схемотехника


0	0	0
1	0	1
0	1	1
1	1	1

Мнемоническое правило для дизъюнкции с любым количеством входов звучит так: На выходе будет:

"1" тогда и только тогда, когда хотя бы на одном входе есть «1»,
"0" тогда и только тогда, когда на всех входах «0»

Программирование

В компьютерных языках используется два основных варианта дизъюнкции: логическое «ИЛИ» и побитовое «ИЛИ». Например, в языках C/C++ логическое «ИЛИ» обозначается символом "||", а побитовое - символом "|". В языках Pascal/Delphi оба вида дизъюнкции обозначаются с использованием ключевого слова «or », а результат действия определяется типом операндов. Если операнды имеют логический тип (например, Boolean) - выполняется логическая операция, если целочисленный (например, Byte) - поразрядная.

Логическое «ИЛИ» применяется в операторах условного перехода или в аналогичных случаях, когда требуется получение результата или . Например:

If (a || b) { /* какие-то действия */ } ;

Результат будет равен , если оба операнда равны или . В любом другом случае результат будет равен .

При этом применяется стандартное соглашение: если значение левого операнда равно , то значение правого операнда не вычисляется (вместо может стоять сложная формула). Такое соглашение ускоряет исполнение программы и служит полезным приёмом в некоторых случаях. Компилятор Delphi поддерживает специальную директиву, включающую

{$B-}

или выключающую

{$B+}

подобное поведение. Например, если левый операнд проверяет необходимость вычисления правого операнда:

If (a == NULL || a-> x == 0 ) { /* какие-то действия */ } ;

В этом примере, благодаря проверке в левом операнде, в правом операнде никогда не произойдёт разыменования нулевого указателя.

Побитовое «ИЛИ» выполняет обычную операцию булевой алгебры для всех битов левого и правого операнда попарно. Например,

если
a =
b =
то
a ИЛИ b =

Связь с естественным языком

Часто указывают на сходство между дизъюнкцией и союзом «или» в естественном языке, когда он употребляется в смысле «или то, или то, или оба сразу». В юридических документах часто пишут: «и/или», подразумевая «или то, или то, или оба сразу». Составное утверждение «A и/или B» считается ложным, когда ложны оба утверждения A и B, в противном случае составное утверждение истинно. Это в точности соответствует определению дизъюнкции в булевой алгебре, если «истину» обозначать как , а «ложь» как .

Неоднозначность естественного языка заключается в том, что союз «или» используется в двух значениях: то для обозначения дизъюнкции, то для другой операции -

Конъюнкция: соответствует союзу: «и», обозначается знаком^, обозначает логическое умножение.

Конъюнкция двух логических ~ истинна тогда и только тогда, когда оба высказываний истинны. Можно обобщить для любого количества переменных А^В^С = 1 если А=1, В=1, С=1.

Таблица истинности для операции «Конъюнкция»:

Таблица №2

Дизъюнкция

Логическая операция соответствует союзу ИЛИ, обозначается знаком v, иначе называется ЛОГИЧЕСКОЕ СЛОЖЕНИЕ.

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

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

A v В v С = 0, только если А = О, В = О, С - 0.

Таблица истинности для операции «Дизъюнкция»:

Таблица №3

Инверсия

Логическая операция соответствует частице не, обозначается ¬ или ¯ и является логическим отрицанием.

Инверсия логической переменной истинна, если переменная ложна и наоборот: инверсия ложна, если переменная истинна.

Таблица истинности для операции «Инверсия»:

Таблица №5

Эквивалентность «А тогда В и только тогда», обозначается А ~ В

Таблица №6

При вычислении значения логического выражения (формулы) логические операции вычисляются в определенном порядке, согласно их приоритету:

инверсия;

конъюнкция;

дизъюнкция;

импликация и эквивалентность;

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

Формализация высказываний

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

Земля вращается вокруг своей оси и вокруг Солнца;

орбиты всех планет проходят вокруг Солнца;

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

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

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

Процесс построения информационных моделей с помощью формальных языков называется формализацией.

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

Конъюнктивная x + y {\displaystyle x+y} Полином Жегалкина x ⊕ y ⊕ x y {\displaystyle x\oplus y\oplus xy} Принадлежность предполным классам Сохраняет 0 Да Сохраняет 1 Да Монотонна Да Линейна Нет Самодвойственна Нет

Дизъюнкция может быть операцией как бинарной (имеющей два операнда), так и n {\displaystyle n} -арной (имеющей n {\displaystyle n} операндов) для произвольного n {\displaystyle n} .

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

Обозначения

Наиболее часто встречаются следующие обозначения для операции дизъюнкции:

a ∨ b , a {\displaystyle a\lor b,\;a} || b , a {\displaystyle b,\;a} | b , a OR b {\displaystyle b,\;a~{\mbox{OR}}\,\,b} , max (a , b) . {\displaystyle ,\;\max(a,b).}

При этом обозначение наиболее широко распространено в современной математике и математической логике . Появилось оно не сразу: Джордж Буль , положивший начало систематическому применению символического метода к логике, не работал с дизъюнкцией (используя вместо неё строгую дизъюнкцию , которую обозначал знаком + ), а Уильям Джевонс предложил для дизъюнкции знак ·|· . Эрнст Шрёдер и П. С. Порецкий вновь использовали знак + , но уже применительно к обычной дизъюнкции . Символ ∨ {\displaystyle \lor } как обозначение дизъюнкции впервые встречается в статье «Математическая логика, основанная на теории типов» Бертрана Рассела (1908); он образован от лат. vel что означает ‘или’ .

Обозначение ⋁ для дизъюнкции было использовано и в раннем языке программирования Алгол 60 . Однако из-за отсутствия соответствующего символа в стандартных наборах символов (например, в ASCII или EBCDIC), применявшихся на большинстве компьютеров , в получивших наибольшее распространение языках программирования были предусмотрены иные обозначения для дизъюнкции. Так, в Фортране IV и PL/I применялись соответственно обозначения.OR. и | (с возможностью замены последнего на ключевое слово OR) ; в языках Паскаль и Ада используется зарезервированное слово or ; в языках и C++ применяются обозначения | для побитовой дизъюнкции и || для логической дизъюнкции ).

Наконец, при естественном упорядочении значений истинности двузначной логики (когда полагают, что 0 < 1 {\displaystyle 0<1} ), оказывается, что (a ∨ b) = max (a , b) . {\displaystyle (a\lor b)\,=\,\max(a,b).} Таким образом, дизъюнкция оказывается частным случаем операции вычисления максимума ; это открывает наиболее естественный способ определить операцию дизъюнкции в системах многозначной логики .

Булева алгебра

Логическая функция MAX в двухзначной (двоичной) логике называется дизъюнкция (логи́ческое «ИЛИ» , логи́ческое сложе́ние или просто «ИЛИ» ). При этом результат равен наибольшему операнду.

В булевой алгебре дизъюнкция - это функция двух, трёх или более переменных (они же - операнды операции, они же - аргументы функции). Таким образом, результат равен , если все операнды равны ; во всех остальных случаях результат равен 1 {\displaystyle 1} .

Таблица истинности
a {\displaystyle a}	b {\displaystyle b}	a ∨ b {\displaystyle a\lor b}

	1 {\displaystyle 1}	1 {\displaystyle 1}
1 {\displaystyle 1}		1 {\displaystyle 1}
1 {\displaystyle 1}	1 {\displaystyle 1}	1 {\displaystyle 1}

Таблица истинности для тернарной (трёхоперандной) дизъюнкции:

a {\displaystyle a}	b {\displaystyle b}	c {\displaystyle c}	a ∨ b ∨ c {\displaystyle a\lor b\lor c}
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

Многозначная логика

Операция, называемая в двоичной логике дизъюнкция , в многозначных логиках называется максимум : m a x (a , b) {\displaystyle max(a,b)} , где a , b ∈ [ 0 , . . . , n − 1 ] {\displaystyle a,b\in } , а n {\displaystyle n} - значность логики. Возможны и другие варианты [чего? ] . Как правило, стараются сохранить совместимость с булевой алгеброй для значений операндов 0 , 1 {\displaystyle 0,1} .

Следует отметить, что название этой операции максимум имеет смысл в логиках с любой значностью, в том числе и в двоичной логике, а названия дизъюнкция , логи́ческое «ИЛИ» , логическое сложе́ние и просто «ИЛИ» характерны для двоичной логики, а при переходе к многозначным логикам используются реже.

Классическая логика

Схемотехника

Мнемоническое правило для дизъюнкции с любым количеством входов звучит так: На выходе будет:

«1» тогда и только тогда, когда хотя бы на одном входе есть «1»,
«0» тогда и только тогда, когда на всех входах «0»

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

Программирование

В компьютерных языках используется два основных варианта дизъюнкции: логическое «ИЛИ» и побитовое «ИЛИ». Например, в языках C/C++/Perl/PHP логическое «ИЛИ» обозначается символом "||", а побитовое - символом "|". В языках Pascal/Delphi оба вида дизъюнкции обозначаются с использованием ключевого слова «or », а результат действия определяется типом операндов. Если операнды имеют логический тип (например, Boolean) - выполняется логическая операция, если целочисленный (например, Byte) - поразрядная.

if (a || b ) { /* какие-то действия */ };

Результат будет равен f a l s e {\displaystyle false} , если оба операнда равны f a l s e {\displaystyle false} или . В любом другом случае результат будет равен t r u e {\displaystyle true} .

При этом применяется стандартное соглашение: если значение левого операнда равно t r u e {\displaystyle true} , то значение правого операнда не вычисляется (вместо b {\displaystyle b} может стоять сложная формула). Такое соглашение ускоряет исполнение программы и служит полезным приёмом в некоторых случаях. Компилятор Delphi поддерживает специальную директиву, включающую

СВОЙСТВА ЛОГИЧЕСКИХ ОПЕРАЦИЙ

1. Обозначения

1.1. Обозначения для логических связок (операций):

a) отрицание (инверсия, логическое НЕ) обозначается ¬ (например, ¬А);

b) конъюнкция (логическое умножение, логическое И) обозначается /\
(например, А /\ В) либо & (например, А & В);

c) дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/
(например, А \/ В);

d) следование (импликация) обозначается → (например, А → В);

e) тождество обозначается ≡ (например, A ≡ B). Выражение A ≡ B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны);

f) символ 1 используется для обозначения истины (истинного высказывания); символ 0 – для обозначения лжи (ложного высказывания).

1.2. Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А → В и (¬А) \/ В равносильны, а А /\ В и А \/ В – нет (значения выражений разные, например, при А = 1, В = 0).

1.3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), тождество. Таким образом, ¬А \/ В \/ С \/ D означает то же, что и

((¬А) \/ В)\/ (С \/ D).

Возможна запись А \/ В \/ С вместо (А \/ В) \/ С. То же относится и к конъюнкции: возможна запись А /\ В /\ С вместо (А /\ В) /\ С.

2. Свойства

Приведенный ниже список НЕ претендует на полноту, но, надеемся, достаточно представителен.

2.1. Общие свойства

Для набора из n логических переменных существует ровно 2 n различных значений. Таблица истинности для логического выражения от n переменных содержит n+1 столбец и 2 n строк.

2.2.Дизъюнкция

Если хоть одно из подвыражений, к которым применяется дизъюнкция, истинно на некотором наборе значений переменных, то и вся дизъюнкция истинна для этого набора значений.
Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже истинна.
Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже ложна.
Значение дизъюнкции не зависит от порядка записи подвыражений, к которым она применяется.

2.3. Конъюнкция

Если хоть одно из подвыражений, к которым применяется конъюнкция, ложно на некотором наборе значений переменных, то и вся конъюнкция ложна для этого набора значений.
Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то конъюнкция этих выражений тоже истинна.
Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то конъюнкция этих выражений тоже ложна.
Значение конюнкции не зависит от порядка записи подвыражений, к которым она применяется.

2.4. Простые дизъюнкции и конъюнкции

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

Простая конъюнкция принимает значение 1 (истина) ровно на одном наборе значений переменных.
Простая дизъюнкция принимает значение 0 (ложь) ровно на одном наборе значений переменных.

2.5. Импликация

Импликация A →B равносильна дизъюнкции (¬ А) \/ В. Эту дизъюнкцию можно записать и так: ¬А \/ В.
Импликация A →B принимает значение 0 (ложь) только если A=1 и B=0. Если A=0, то импликация A →B истинна при любом значении B.