Что такое дизъюнкция в информатике определение. Операция дизъюнкция

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

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

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

Таблица №2

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

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

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

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

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

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

Таблица №3

1. Инверсия

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

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

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

Таблица №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} .

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

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

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

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

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

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

• «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 поддерживает специальную директиву, включающую

Конъюнкция или логическое умножение (в теории множеств – это пересечение)

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

Обозначение: &, $\wedge$, $\cdot$.

Таблица истинности для конъюнкции

Рисунок 1.

Свойства конъюнкции:

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

Дизъюнкция или логическое сложение (в теории множеств это объединение)

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

Обозначение: +, $\vee$.

Таблица истинности для дизъюнкции

Рисунок 2.

Свойства дизъюнкции:

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

Отрицание, логическое отрицание или инверсия (в теории множеств это отрицание)

Отрицание - означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО и в итоге получаем, что если исходное выражение истинно, то отрицание исходного – будет ложно и наоборот, если исходное выражение ложно, то его отрицание будет истинно.

Обозначения: не $A$, $\bar{A}$, $¬A$.

Таблица истинности для инверсии

Рисунок 3.

Свойства отрицания:

«Двойное отрицание» $¬¬A$ является следствием суждения $A$, то есть имеет место тавтология в формальной логике и равно самому значению в булевой логике.

Импликация или логическое следование

Импликация - это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть, данная логическая операция связывает два простых логических выражения, из которых первое является условием ($A$), а второе ($A$) является следствием условия ($A$).

Обозначения: $\to$, $\Rightarrow$.

Таблица истинности для импликации

Рисунок 4.

Свойства импликации:

1. $A \to B = ¬A \vee B$.
2. Импликация $A \to B$ ложна, если $A=1$ и $B=0$.
3. Если $A=0$, то импликация $A \to B$ истинна при любом значении $B$, (из лжи может следовать истинна).

Эквивалентность или логическая равнозначность

Эквивалентность - это сложное логическое выражение, которое истинно на равных значениях переменных $A$ и $B$.

Обозначения: $\leftrightarrow$, $\Leftrightarrow$, $\equiv$.

Таблица истинности для эквивалентности

Рисунок 5.

Свойства эквивалентности:

1. Эквивалентность истинна на равных наборах значений переменных $A$ и $B$.
2. КНФ $A \equiv B = (\bar{A} \vee B) \cdot (A \cdot \bar{B})$
3. ДНФ $A \equiv B = \bar{A} \cdot \bar{B} \vee A \cdot B$

Строгая дизъюнкция или сложение по модулю 2 (в теории множеств это объединение двух множеств без их пересечения)

Строгая дизъюнкция истинна, если значения аргументов не равны.

Для электроники это означает, что реализация схем возможна с использованием одного типового элемента (правда это дорогостоящий элемент).

Порядок выполнения логических операций в сложном логическом выражении

1. Инверсия(отрицание);
2. Конъюнкция (логическое умножение);
3. Дизъюнкция и строгая дизъюнкция (логическое сложение);
4. Импликация (следствие);
5. Эквивалентность (тождество).

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

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

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

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

Отрицание

Перед тем как начать подробно рассматривать конкретные примеры, перечислим основные логические операции в информатике:

• отрицание;
• сложение;
• умножение;
• следование;
• равенство.

Также перед началом изучения логических операций стоит сказать, что в информатике ложь обозначается "0", а правда "1".

Для каждого действия, как и в обычной математике, используются следующие знаки логических операций в информатике: ¬, v, &, ->.

Каждое действие возможно описать либо цифрами 1/0, либо просто логическими выражениями. Начнём рассмотрение математической логики с простейшей операции, использующей всего одну переменную.

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

При записи этого выражения используется следующее обозначение "¬A".

Приведём таблицу истинности - схему, которая показывает все возможные результаты операции при любых исходных данных.

То есть, если у нас исходное выражение - истина (1), то его отрицание будет ложным (0). А если исходное выражение - ложь (0), то его отрицание - истина (1).

Сложение

Оставшиеся операции требуют наличия двух переменных. Обозначим одно выражение -

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

1. Е=1, Н=1 ,тогда Е v Н = 1. Если оба тогда и их дизъюнкция также истинна.
2. Е=0, Н=1 ,в итоге Е v Н = 1. Е=1, Н=0 , тогда Е v Н= 1. Если хотябы одно из выражений истинно, тогда и результат их сложения будет истиной.
3. Е=0, Н=0 ,результат Е v Н = 0. Если оба выражения ложны, то их сумма также - ложь.

Для краткости создадим таблицу истинности.

Дизъюнкция

Е	х	х	о	о
Н	х	о	х	о
Е v Н	х	х	х	о

Умножение

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

1. Е=1, Н=1 ,тогда Е & Н = 1. Если оба тогда их конъюнкция - истина.
2. Если хотя бы одно из выражений - ложь, тогда результатом логического умножения также будет ложь.

• Е=1, Н=0, поэтому Е & Н = 0.
• Е=0, Н=1, тогда Е & Н = 0.
• Е=0, Н=0, итог Е & Н = 0.

Конъюнкция

Е	х	х	0	0
Н	х	0	х	0
Е & Н	х	0	0	0

Следствие

Логическая операция следования (импликация) - одна из простейших в математической логике. Она основана на единственной аксиоме - из правды не может следовать ложь.

1. Е=1, Н=, поэтому Е -> Н = 1. Если пара влюблена, то они могут целоваться - правда.
2. Е=0, Н=1, тогда Е -> Н = 1. Если пара не влюблена, то они могут целоваться - также может быть истиной.
3. Е=0, Н=0, из этого Е -> Н = 1. Если пара не влюблена, то они и не целуются - тоже правда.
4. Е=1, Н=0, результатом будет Е -> Н = 0. Если пара влюблена, то они не целуются - ложь.

Для облегчения выполнения математических действий также приведём таблицу истинности.

Равенство

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

1. А=1, В=1, тогда А≡В = 1. Человек пьёт таблетки тогда и только тогда, когда болеет. (истина)
2. А=0, В=0, в итоге А≡В = 1. Человек не пьёт таблетки тогда и только тогда, когда не болеет. (истина)
3. А=1, В=0, поэтому А≡В = 0. Человек пьёт таблетки тогда и только тогда, когда не болеет. (ложь)
4. А=0, В=1 ,тогда А≡В = 0. Человек не пьёт таблетки тогда и только тогда, когда болеет. (ложь)

Свойства

Итак, рассмотрев простейшие в информатике, можем приступить к изучению некоторых их свойств. Как и в математике, у логических операций существует свой порядок обработки. В больших логических выражениях операции в скобках выполняются в первую очередь. После них первым делом подсчитываем все значения отрицания в примере. Следующим шагом станет вычисление конъюнкции, а затем дизъюнкции. Только после этого выполняем операцию следствия и, наконец, эквивалентности. Рассмотрим небольшой пример для наглядности.

А v В & ¬В -> В ≡ А

Порядок выполнения действий следующий.

1. В&(¬В)
2. А v(В&(¬В))
3. (А v(В&(¬В)))->В
4. ((А v(В&(¬В)))->В)≡А

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

Решение примера

А	В				(А v(В&(¬В)))->В	((А v(В&(¬В)))->В)≡А
х	о	х	о	х	х	х
х	х	о	о	х	х	х
о	о	х	о	о	х	о
о	х	о	о	о	х	о

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

Заключение

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

Логическое сложение (дизъюнкция)

Логическое умножение (конъюнкция)

Логическое умножение есть соединение двух простых высказываний союзом "И". Например, возьмем два высказывания: «Дважды два равно четырем» (a), «Трижды три равно девяти» (a). Сложное высказывание «Дважды два равно четырем и Трижды три равно девяти» истинно, т.к. истинны оба высказывания a и b. Но если взять другие высказывания: «Дважды два равно четырем» (c), и «Стол имеет 2 ножки» (d), то сложное высказывание «Дважды два равно четырем и Стол имеет 2 ножки» будет ложным, т.к. ложно высказывание (d).

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

Обозначения операции «конъюнкция»: a & b, a and b, ab, a Λ b.

Знак & - амперсанд - читается как английское "and".

Таблица истинности функции «логическое умножение»:

Логическое умножение
Аргументы	Функция
a	b	F = ab

Значение функции a = «2*2=4» =1, значение функции b = «3*3=8» = 0.

Значение функции ab = «(2*2=4) & (3*3=8)» = 0

Логическое сложение есть соединение двух простых высказываний союзом "ИЛИ". Например, возьмем два высказывания: «Дважды два равно четырем» (a), «Трижды три равно девяти» (b). Сложное высказывание «Дважды два равно четырем ИЛИ трижды три равно девяти» истинно, т.к. оно соответствует действительности. Формально, это сложное высказывание является истинным, т.к. истинны оба этих высказывания. С точки зрения здравого смысла, даже если взять два других высказывания: «Дважды два равно четырем» (c) и «Стол имеет 2 ножки» (d), то сложное высказывание «Дважды два равно четырем ИЛИ стол имеет 2 ножки» соответствует действительности и является истинным. Формально оно является истинным, т.к. в этом сложном высказывании есть одно истинное высказывание (c). Таким образом, исходя из обычного смысла союза "ИЛИ", приходим к определению соответствующей логической операции - дизъюнкции.

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

Обозначения операции «дизъюнкция»: a ! b, a or b, a + b, a V b.

Таблица истинности функции «логическое сложение»:

Логическое умножение
Аргументы	Функция
a	b	F = a V b

1. Значение функции a = «2*2=4» =1, значение функции b = «3*3=8» = 0.

Значение функции a V b = «(2*2=4) V (3*3=8)» = 1

2. Значение функции a = «2*2=4» =1, значение функции b = «3*3=9» = 1.

Значение функции a V b = «(2*2=4) V (3*3=9)» = 1

3. Значение функции a = «2*2=5» =0, значение функции b = «3*3=8» = 0.

Значение функции a V b = «(2*2=5) V (3*3=8)» = 0

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

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

Сравнивая эти две таблицы истинности, можно убедиться в равносильности двух сложных выражений.

Для обозначения равносильных логических выражений применяется знак «=».

Для рассмотренного случая можно записать: &= .