Дизъюнкция
| Дизъюнкция | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ИЛИ | ||||||||||||
| ||||||||||||
| Основная информация | ||||||||||||
| Определение | <math>x+y</math> | |||||||||||
| Классы |
| |||||||||||
| ДНФ | <math>x+y</math> | |||||||||||
| КНФ | <math>x+y</math> | |||||||||||
| Полином Жегалкина | <math>x \oplus y \oplus xy</math> | |||||||||||
| Таблица истинности | <math>(0111)</math> | |||||||||||
Дизъю́нкция (лат. disjunctio — разобщение), логи́ческое сложе́ние, логи́ческое ИЛИ, включа́ющее ИЛИ; иногда просто ИЛИ — логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу»[1].
Дизъюнкция может быть бинарной операцией (иметь два операнда), тернарной операцией (иметь три операнда) или <math>n</math>-арной операцией (иметь <math>n</math> операндов).
Запись может быть префиксной — знак операции стоит перед операндами (польская запись), инфиксной — знак операции стоит между операндами или постфиксной — знак операции стоит после операндов. При числе операндов более 2-х префиксная и постфиксная записи экономичнее.
Содержание
Обозначения
Наиболее часто встречаются следующие обозначения для операции дизъюнкции:
- <math>a \lor b, \; a</math> || <math>b, \; a</math> | <math>b, \; a~\mbox{OR}\,\,b</math><math>, \; \max(a,b).</math>
При этом обозначение <math>a \lor b</math> наиболее широко распространено в современной математике и математической логике[2]. Появилось оно не сразу: Джордж Буль, положивший начало систематическому применению символического метода к логике, не работал с дизъюнкцией (используя вместо неё строгую дизъюнкцию, которую обозначал знаком +), а Уильям Джевонс предложил для дизъюнкции знак ·|·. Эрнст Шрёдер и П. С. Порецкий вновь использовали знак +, но уже применительно к обычной дизъюнкции[3]. Символ <math>\lor</math> как обозначение дизъюнкции впервые встречается в статье «Математическая логика, основанная на теории типов»[4] Бертрана Рассела (1908); он образован от лат. vel что означает ‘или’[5][6].
Обозначение ⋁ для дизъюнкции было использовано и в раннем языке программирования Алгол 60[7]. Однако из-за отсутствия соответствующего символа в стандартных наборах символов (например, в ASCII или EBCDIC), применявшихся на большинстве компьютеров, в получивших наибольшее распространение языках программирования были предусмотрены иные обозначения для дизъюнкции. Так, в Фортране IV и PL/I применялись соответственно обозначения .OR. и | (с возможностью замены последнего на ключевое слово OR)[8]; в языках Паскаль и Ада используется зарезервированное слово or[9][10]; в языках C и C++ применяются обозначения | для побитовой дизъюнкции и || для логической дизъюнкции[11]).
Наконец, при естественном упорядочении значений истинности двузначной логики (когда полагают, что <math>0 < 1</math>), оказывается, что <math>(a \lor b)\,=\,\max(a,b).</math> Таким образом, дизъюнкция оказывается частным случаем операции вычисления максимума; это открывает наиболее естественный способ определить операцию дизъюнкции в системах многозначной логики[12][13].
Булева алгебра
Определение.
Логическая функция MAX в двухзначной (двоичной) логике называется дизъюнкция (логи́ческое «ИЛИ», логи́ческое сложе́ние или просто «ИЛИ»).
Правило: результат равен наибольшему операнду.
Описание.
В булевой алгебре дизъюнкция — это функция двух, трёх или более переменных (они же — операнды операции, они же — аргументы функции).
Правило: результат равен <math>0</math>, если все операнды равны <math>0</math>; во всех остальных случаях результат равен <math>1</math>.
| Таблица истинности | ||
|---|---|---|
| <math>a</math> | <math>b</math> | <math>a \lor b</math> |
| <math>0</math> | <math>0</math> | <math>0</math> |
| <math>0</math> | <math>1</math> | <math>1</math> |
| <math>1</math> | <math>0</math> | <math>1</math> |
| <math>1</math> | <math>1</math> | <math>1</math> |
Таблица истинности для тернарной (трёхоперандной) дизъюнкции:
| X | Y | Z | X <math>\lor</math> Y <math>\lor</math> Z |
|---|---|---|---|
| 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 |
Многозначная логика
Операция, называемая в двоичной логике дизъюнкция, в многозначных логиках называется максимум: <math>max(a,b)</math>, где <math>a, b \in [0,...,n-1]</math>, а <math>n</math> — значность логики. Возможны и другие варианты[чего?]. Как правило, стараются сохранить совместимость с булевой алгеброй для значений операндов <math>0, 1</math>.
Следует отметить, что название этой операции максимум имеет смысл в логиках с любой значностью, в том числе и в двоичной логике, а названия дизъюнкция, логи́ческое «ИЛИ», логическое сложе́ние и просто «ИЛИ» характерны для двоичной логики, а при переходе к многозначным логикам используются реже.
Классическая логика
В классическом исчислении высказываний свойства дизъюнкции определяются с помощью аксиом. Классическое исчисление высказываний может быть задано разными системами аксиом, и некоторые из них будут описывать свойства дизъюнкции. Один из самых распространённых вариантов включает 3 аксиомы для дизъюнкции:
<math>a \to a \lor b</math>
<math>b \to a \lor b</math>
<math>(a \to c) \to ((b \to c) \to ((a \lor b) \to c))</math>
С помощью этих аксиом можно доказать другие формулы, содержащие операцию дизъюнкции. Обратите внимание, что в классическом исчислении высказываний не происходит вычисления результата по значениям операндов (как в булевой алгебре), а требуется доказать формулу как единое целое на основе аксиом и правил вывода.
Схемотехника
| <math> A</math> | <math> B</math> | <math> f(AB)</math> |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 1 |
- «1» тогда и только тогда, когда хотя бы на одном входе есть «1»,
- «0» тогда и только тогда, когда на всех входах «0»
Теория множеств
С точки зрения теории множеств, дизъюнкция аналогична операции объединения.
Программирование
В компьютерных языках используется два основных варианта дизъюнкции: логическое «ИЛИ» и побитовое «ИЛИ». Например, в языках C/C++ логическое «ИЛИ» обозначается символом "||", а побитовое — символом "|". В языках Pascal/Delphi оба вида дизъюнкции обозначаются с использованием ключевого слова «or», а результат действия определяется типом операндов. Если операнды имеют логический тип (например, Boolean) — выполняется логическая операция, если целочисленный (например, Byte) — поразрядная.
Логическое «ИЛИ» применяется в операторах условного перехода или в аналогичных случаях, когда требуется получение результата <math>false</math> или <math>true</math>. Например:
if (a || b)
{
/* какие-то действия */
};Результат будет равен <math>false</math>, если оба операнда равны <math>false</math> или <math>0</math>. В любом другом случае результат будет равен <math>true</math>.
При этом применяется стандартное соглашение: если значение левого операнда равно <math>true</math>, то значение правого операнда не вычисляется (вместо <math>b</math> может стоять сложная формула). Такое соглашение ускоряет исполнение программы и служит полезным приёмом в некоторых случаях. Компилятор Delphi поддерживает специальную директиву, включающую{$B-}{$B+}if (a == NULL || a->x == 0)
{
/* какие-то действия */
};В этом примере, благодаря проверке в левом операнде, в правом операнде никогда не произойдёт разыменования нулевого указателя.
Побитовое «ИЛИ» выполняет обычную операцию булевой алгебры для всех битов левого и правого операнда попарно. Например,
| если | |
| a = | <math>01100101_2</math> |
| b = | <math>00101001_2</math> |
| то | |
| a ИЛИ b = | <math>01101101_2</math> |
Связь с естественным языком
Часто указывают на сходство между дизъюнкцией и союзом «или» в естественном языке, когда он употребляется в смысле «или то, или то, или оба сразу». В юридических документах часто пишут: «и (или)», иногда «и/или», подразумевая «или то, или то, или оба сразу». Составное утверждение «A и/или B» считается ложным, когда ложны оба утверждения A и B, в противном случае составное утверждение истинно. Это в точности соответствует определению дизъюнкции в булевой алгебре, если «истину» обозначать как <math>1</math>, а «ложь» как <math>0</math>.
Неоднозначность естественного языка заключается в том, что союз «или» используется в двух значениях: то для обозначения дизъюнкции, то для другой операции — строгой дизъюнкции (исключающего «ИЛИ»).
См. также
- Логический элемент
- Логическая операция
- Конъюнкция
- Строгая дизъюнкция
- Импликация
- Отрицание
- Эквиваленция
Напишите отзыв о статье "Дизъюнкция"
Примечания
- ↑ Гутников В. С. Интегральная электроника в измерительных приборах. — Л.: Энергия, 1974. — 144 с. — С. 14—16.
- ↑ Кондаков, 1975, с. 534.
- ↑ Стяжкин Н. И. Формирование математической логики. — М.: Наука, 1967. — 508 с. — С. 320, 349, 352, 368.
- ↑ Russell B. [www.jstor.org/stable/2369948 Mathematical Logic as Based on the Theory of Types] // American Journal of Mathematics. — 1908. — Vol. 30, no. 3. — P. 222—262.
- ↑ [jeff560.tripod.com/set.html Earliest Uses of Symbols of Set Theory and Logic]. // Website Jeff Miller Web Pages. Проверено 5 февраля 2016.
- ↑ Кондаков, 1975, с. 149—150.
- ↑ Кондаков, 1975, с. 30.
- ↑ Пратт Т. Языки программирования: разработка и реализация. — М.: Мир, 1979. — 574 с. — С. 352, 439.
- ↑ Грогоно П. Программирование на языке Паскаль. — М.: Мир, 1982. — 384 с. — С. 51.
- ↑ Вегнер П. Программирование на языке Ада. — М.: Мир, 1983. — 240 с. — С. 68.
- ↑ Эллис М., Строуструп Б. Справочное руководство по языку программирования C++ с комментариями. — М.: Мир, 1992. — 445 с. — ISBN 5-03-002868-4. — С. 65, 86—87.
- ↑ Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1979. — 272 с. — С. 9—10, 37.
- ↑ Рвачёв В. Л. Теория R-функций и некоторые её приложения. — Киев: Наукова думка, 1982. — 552 с. — С. 38, 66.
Литература
- Кондаков Н. И. [www.runivers.ru/upload/iblock/443/logichesky%20slovar.pdf Логический словарь-справочник. 2-е изд]. — М.: Наука, 1975. — 720 с.
<imagemap>: неверное или отсутствующее изображение |
В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена.
Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 3 ноября 2009 года. |
| ||||||||||||||
Отрывок, характеризующий Дизъюнкция
– Ah, mon ami! – сказала она с тем же жестом, как утром с сыном, дотрогиваясь до его руки: – croyez, que je souffre autant, que vous, mais soyez homme. [Поверьте, я страдаю не меньше вас, но будьте мужчиной.]– Право, я пойду? – спросил Пьер, ласково чрез очки глядя на Анну Михайловну.
– Ah, mon ami, oubliez les torts qu'on a pu avoir envers vous, pensez que c'est votre pere… peut etre a l'agonie. – Она вздохнула. – Je vous ai tout de suite aime comme mon fils. Fiez vous a moi, Pierre. Je n'oublirai pas vos interets. [Забудьте, друг мой, в чем были против вас неправы. Вспомните, что это ваш отец… Может быть, в агонии. Я тотчас полюбила вас, как сына. Доверьтесь мне, Пьер. Я не забуду ваших интересов.]
Пьер ничего не понимал; опять ему еще сильнее показалось, что всё это так должно быть, и он покорно последовал за Анною Михайловной, уже отворявшею дверь.
Дверь выходила в переднюю заднего хода. В углу сидел старик слуга княжен и вязал чулок. Пьер никогда не был на этой половине, даже не предполагал существования таких покоев. Анна Михайловна спросила у обгонявшей их, с графином на подносе, девушки (назвав ее милой и голубушкой) о здоровье княжен и повлекла Пьера дальше по каменному коридору. Из коридора первая дверь налево вела в жилые комнаты княжен. Горничная, с графином, второпях (как и всё делалось второпях в эту минуту в этом доме) не затворила двери, и Пьер с Анною Михайловной, проходя мимо, невольно заглянули в ту комнату, где, разговаривая, сидели близко друг от друга старшая княжна с князем Васильем. Увидав проходящих, князь Василий сделал нетерпеливое движение и откинулся назад; княжна вскочила и отчаянным жестом изо всей силы хлопнула дверью, затворяя ее.
Жест этот был так не похож на всегдашнее спокойствие княжны, страх, выразившийся на лице князя Василья, был так несвойствен его важности, что Пьер, остановившись, вопросительно, через очки, посмотрел на свою руководительницу.
Анна Михайловна не выразила удивления, она только слегка улыбнулась и вздохнула, как будто показывая, что всего этого она ожидала.
– Soyez homme, mon ami, c'est moi qui veillerai a vos interets, [Будьте мужчиною, друг мой, я же стану блюсти за вашими интересами.] – сказала она в ответ на его взгляд и еще скорее пошла по коридору.
Пьер не понимал, в чем дело, и еще меньше, что значило veiller a vos interets, [блюсти ваши интересы,] но он понимал, что всё это так должно быть. Коридором они вышли в полуосвещенную залу, примыкавшую к приемной графа. Это была одна из тех холодных и роскошных комнат, которые знал Пьер с парадного крыльца. Но и в этой комнате, посередине, стояла пустая ванна и была пролита вода по ковру. Навстречу им вышли на цыпочках, не обращая на них внимания, слуга и причетник с кадилом. Они вошли в знакомую Пьеру приемную с двумя итальянскими окнами, выходом в зимний сад, с большим бюстом и во весь рост портретом Екатерины. Все те же люди, почти в тех же положениях, сидели, перешептываясь, в приемной. Все, смолкнув, оглянулись на вошедшую Анну Михайловну, с ее исплаканным, бледным лицом, и на толстого, большого Пьера, который, опустив голову, покорно следовал за нею.
На лице Анны Михайловны выразилось сознание того, что решительная минута наступила; она, с приемами деловой петербургской дамы, вошла в комнату, не отпуская от себя Пьера, еще смелее, чем утром. Она чувствовала, что так как она ведет за собою того, кого желал видеть умирающий, то прием ее был обеспечен. Быстрым взглядом оглядев всех, бывших в комнате, и заметив графова духовника, она, не то что согнувшись, но сделавшись вдруг меньше ростом, мелкою иноходью подплыла к духовнику и почтительно приняла благословение одного, потом другого духовного лица.
– Слава Богу, что успели, – сказала она духовному лицу, – мы все, родные, так боялись. Вот этот молодой человек – сын графа, – прибавила она тише. – Ужасная минута!
Проговорив эти слова, она подошла к доктору.
– Cher docteur, – сказала она ему, – ce jeune homme est le fils du comte… y a t il de l'espoir? [этот молодой человек – сын графа… Есть ли надежда?]
Доктор молча, быстрым движением возвел кверху глаза и плечи. Анна Михайловна точно таким же движением возвела плечи и глаза, почти закрыв их, вздохнула и отошла от доктора к Пьеру. Она особенно почтительно и нежно грустно обратилась к Пьеру.
– Ayez confiance en Sa misericorde, [Доверьтесь Его милосердию,] – сказала она ему, указав ему диванчик, чтобы сесть подождать ее, сама неслышно направилась к двери, на которую все смотрели, и вслед за чуть слышным звуком этой двери скрылась за нею.
Пьер, решившись во всем повиноваться своей руководительнице, направился к диванчику, который она ему указала. Как только Анна Михайловна скрылась, он заметил, что взгляды всех, бывших в комнате, больше чем с любопытством и с участием устремились на него. Он заметил, что все перешептывались, указывая на него глазами, как будто со страхом и даже с подобострастием. Ему оказывали уважение, какого прежде никогда не оказывали: неизвестная ему дама, которая говорила с духовными лицами, встала с своего места и предложила ему сесть, адъютант поднял уроненную Пьером перчатку и подал ему; доктора почтительно замолкли, когда он проходил мимо их, и посторонились, чтобы дать ему место. Пьер хотел сначала сесть на другое место, чтобы не стеснять даму, хотел сам поднять перчатку и обойти докторов, которые вовсе и не стояли на дороге; но он вдруг почувствовал, что это было бы неприлично, он почувствовал, что он в нынешнюю ночь есть лицо, которое обязано совершить какой то страшный и ожидаемый всеми обряд, и что поэтому он должен был принимать от всех услуги. Он принял молча перчатку от адъютанта, сел на место дамы, положив свои большие руки на симметрично выставленные колени, в наивной позе египетской статуи, и решил про себя, что всё это так именно должно быть и что ему в нынешний вечер, для того чтобы не потеряться и не наделать глупостей, не следует действовать по своим соображениям, а надобно предоставить себя вполне на волю тех, которые руководили им.
Не прошло и двух минут, как князь Василий, в своем кафтане с тремя звездами, величественно, высоко неся голову, вошел в комнату. Он казался похудевшим с утра; глаза его были больше обыкновенного, когда он оглянул комнату и увидал Пьера. Он подошел к нему, взял руку (чего он прежде никогда не делал) и потянул ее книзу, как будто он хотел испытать, крепко ли она держится.
– Courage, courage, mon ami. Il a demande a vous voir. C'est bien… [Не унывать, не унывать, мой друг. Он пожелал вас видеть. Это хорошо…] – и он хотел итти.
Но Пьер почел нужным спросить:
– Как здоровье…
Он замялся, не зная, прилично ли назвать умирающего графом; назвать же отцом ему было совестно.
– Il a eu encore un coup, il y a une demi heure. Еще был удар. Courage, mon аmi… [Полчаса назад у него был еще удар. Не унывать, мой друг…]
Пьер был в таком состоянии неясности мысли, что при слове «удар» ему представился удар какого нибудь тела. Он, недоумевая, посмотрел на князя Василия и уже потом сообразил, что ударом называется болезнь. Князь Василий на ходу сказал несколько слов Лоррену и прошел в дверь на цыпочках. Он не умел ходить на цыпочках и неловко подпрыгивал всем телом. Вслед за ним прошла старшая княжна, потом прошли духовные лица и причетники, люди (прислуга) тоже прошли в дверь. За этою дверью послышалось передвиженье, и наконец, всё с тем же бледным, но твердым в исполнении долга лицом, выбежала Анна Михайловна и, дотронувшись до руки Пьера, сказала:
– La bonte divine est inepuisable. C'est la ceremonie de l'extreme onction qui va commencer. Venez. [Милосердие Божие неисчерпаемо. Соборование сейчас начнется. Пойдемте.]
Пьер прошел в дверь, ступая по мягкому ковру, и заметил, что и адъютант, и незнакомая дама, и еще кто то из прислуги – все прошли за ним, как будто теперь уж не надо было спрашивать разрешения входить в эту комнату.
Пьер хорошо знал эту большую, разделенную колоннами и аркой комнату, всю обитую персидскими коврами. Часть комнаты за колоннами, где с одной стороны стояла высокая красного дерева кровать, под шелковыми занавесами, а с другой – огромный киот с образами, была красно и ярко освещена, как бывают освещены церкви во время вечерней службы. Под освещенными ризами киота стояло длинное вольтеровское кресло, и на кресле, обложенном вверху снежно белыми, не смятыми, видимо, только – что перемененными подушками, укрытая до пояса ярко зеленым одеялом, лежала знакомая Пьеру величественная фигура его отца, графа Безухого, с тою же седою гривой волос, напоминавших льва, над широким лбом и с теми же характерно благородными крупными морщинами на красивом красно желтом лице. Он лежал прямо под образами; обе толстые, большие руки его были выпростаны из под одеяла и лежали на нем. В правую руку, лежавшую ладонью книзу, между большим и указательным пальцами вставлена была восковая свеча, которую, нагибаясь из за кресла, придерживал в ней старый слуга. Над креслом стояли духовные лица в своих величественных блестящих одеждах, с выпростанными на них длинными волосами, с зажженными свечами в руках, и медленно торжественно служили. Немного позади их стояли две младшие княжны, с платком в руках и у глаз, и впереди их старшая, Катишь, с злобным и решительным видом, ни на мгновение не спуская глаз с икон, как будто говорила всем, что не отвечает за себя, если оглянется. Анна Михайловна, с кроткою печалью и всепрощением на лице, и неизвестная дама стояли у двери. Князь Василий стоял с другой стороны двери, близко к креслу, за резным бархатным стулом, который он поворотил к себе спинкой, и, облокотив на нее левую руку со свечой, крестился правою, каждый раз поднимая глаза кверху, когда приставлял персты ко лбу. Лицо его выражало спокойную набожность и преданность воле Божией. «Ежели вы не понимаете этих чувств, то тем хуже для вас», казалось, говорило его лицо.
Сзади его стоял адъютант, доктора и мужская прислуга; как бы в церкви, мужчины и женщины разделились. Всё молчало, крестилось, только слышны были церковное чтение, сдержанное, густое басовое пение и в минуты молчания перестановка ног и вздохи. Анна Михайловна, с тем значительным видом, который показывал, что она знает, что делает, перешла через всю комнату к Пьеру и подала ему свечу. Он зажег ее и, развлеченный наблюдениями над окружающими, стал креститься тою же рукой, в которой была свеча.
Младшая, румяная и смешливая княжна Софи, с родинкою, смотрела на него. Она улыбнулась, спрятала свое лицо в платок и долго не открывала его; но, посмотрев на Пьера, опять засмеялась. Она, видимо, чувствовала себя не в силах глядеть на него без смеха, но не могла удержаться, чтобы не смотреть на него, и во избежание искушений тихо перешла за колонну. В середине службы голоса духовенства вдруг замолкли; духовные лица шопотом сказали что то друг другу; старый слуга, державший руку графа, поднялся и обратился к дамам. Анна Михайловна выступила вперед и, нагнувшись над больным, из за спины пальцем поманила к себе Лоррена. Француз доктор, – стоявший без зажженной свечи, прислонившись к колонне, в той почтительной позе иностранца, которая показывает, что, несмотря на различие веры, он понимает всю важность совершающегося обряда и даже одобряет его, – неслышными шагами человека во всей силе возраста подошел к больному, взял своими белыми тонкими пальцами его свободную руку с зеленого одеяла и, отвернувшись, стал щупать пульс и задумался. Больному дали чего то выпить, зашевелились около него, потом опять расступились по местам, и богослужение возобновилось. Во время этого перерыва Пьер заметил, что князь Василий вышел из за своей спинки стула и, с тем же видом, который показывал, что он знает, что делает, и что тем хуже для других, ежели они не понимают его, не подошел к больному, а, пройдя мимо его, присоединился к старшей княжне и с нею вместе направился в глубь спальни, к высокой кровати под шелковыми занавесами. От кровати и князь и княжна оба скрылись в заднюю дверь, но перед концом службы один за другим возвратились на свои места. Пьер обратил на это обстоятельство не более внимания, как и на все другие, раз навсегда решив в своем уме, что всё, что совершалось перед ним нынешний вечер, было так необходимо нужно.
