Конъюнкция
Шаблон:Булева функция Конъю́нкция (от лат. conjunctio — «союз, связь») — логическая операция, по смыслу максимально приближенная к союзу «и». Синонимы: логи́ческое «И», логи́ческое умноже́ние, иногда просто «И»[1].
Конъюнкция может быть бинарной операцией (т. e. иметь два операнда), тернарной операцией (т. e. иметь три операнда), или n-арной операцией (т. e. иметь n операндов).
Обозначения
Наиболее часто встречаются следующие обозначения для операции конъюнкции:
[math]\displaystyle{ a \land b, \quad a \And \And b, \quad a \And b, \quad a \cdot b, \quad a\,\,\mathrm{AND}\,\,b, \quad \min(a,b) }[/math]
(в случае использования точки, как знака логического умножения, этот знак, как и при обычном умножении в алгебре, может быть опущен: [math]\displaystyle{ a b }[/math][1]).
При этом обозначение [math]\displaystyle{ a \land b }[/math], рекомендованное стандартом ISO 31-11, наиболее широко распространено в современной математике и математической логике, где оно, впрочем, конкурирует со знаком амперсанда &[1]; последний, появившись ещё в I веке до н. э. как графическое сокращение (лигатура) латинского союза et ‘и’, уже Якобом и Иоганном Бернулли в 1685 году использовался в качестве логической связки (у них он, однако, связывал не высказывания, а понятия)[2][3]. Джордж Буль (а за ним — и другие пионеры систематического применения символического метода к логике: У. С. Джевонс, Э. Шрёдер, П. С. Порецкий) обозначал конъюнкцию знаком [math]\displaystyle{ \cdot }[/math] — как обычное умножение[4]. Символ ⋀ (перевёрнутый знак дизъюнкции) в качестве обозначения конъюнкции был предложен Арендом Гейтингом (1930)[5].
Обозначение ⋀ для конъюнкции было использовано и в раннем языке программирования Алгол 60[6]. Однако из-за отсутствия соответствующего символа в стандартных наборах символов (например, в ASCII или EBCDIC), применявшихся на большинстве компьютеров, в получивших наибольшее распространение языках программирования были предусмотрены иные обозначения для конъюнкции. Так, в Фортране IV и PL/I применялись соответственно обозначения .AND. и & (с возможностью замены последнего на ключевое слово AND)[7]; в языках Паскаль и Ада используется зарезервированное слово and[8][9]; в языках C и C++ применяются обозначения & для побитовой конъюнкции и && для логической конъюнкции[10]).
Наконец, при естественном упорядочении значений истинности двузначной логики (когда полагают, что [math]\displaystyle{ 0 \lt 1 }[/math]), оказывается, что [math]\displaystyle{ (a \land b)\,=\,\min(a,b). }[/math] Таким образом, конъюнкция оказывается частным случаем операции вычисления минимума; это открывает наиболее естественный способ определить операцию конъюнкции в системах многозначной логики (хотя иногда рассматривают и другие способы обобщения конъюнкции — например, такой: [math]\displaystyle{ (a \land b)\,=\,ab\;(\operatorname{mod} k) }[/math] в случае k-значной логики, в которой множество значений истинности представлено начальным отрезком [math]\displaystyle{ \{0,\dots,k-1\} }[/math] полугруппы [math]\displaystyle{ \mathbb N }[/math] натуральных чисел)[11][12].
Булева алгебра
Определение.
Логическая функция MIN в двухзначной (двоичной) логике называется конъюнкция (логи́ческое «И», логи́ческое умноже́ние или просто «И»).
Правило: результат равен наименьшему операнду.
Описание.
В булевой алгебре конъюнкция — это функция двух, трёх или более переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества [math]\displaystyle{ \{0, 1\} }[/math]. Результат также принадлежит множеству [math]\displaystyle{ \{0, 1\} }[/math]. Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений [math]\displaystyle{ 0, 1 }[/math] может использоваться любая другая пара подходящих символов, например [math]\displaystyle{ false, true }[/math] или [math]\displaystyle{ F, T }[/math] или «ложь», «истина», но при таком обозначении необходимо дополнительно доопределять старшинство, например, [math]\displaystyle{ true \gt false }[/math], при цифровом обозначении старшинство естественно [math]\displaystyle{ 1 \gt 0 }[/math].
Правило: результат равен [math]\displaystyle{ 1 }[/math], если все операнды равны [math]\displaystyle{ 1 }[/math]; во всех остальных случаях результат равен [math]\displaystyle{ 0 }[/math].
Таблицы истинности:
для бинарной конъюнкции
| [math]\displaystyle{ a }[/math] | [math]\displaystyle{ b }[/math] | [math]\displaystyle{ a \land b }[/math] |
|---|---|---|
| [math]\displaystyle{ 0 }[/math] | [math]\displaystyle{ 0 }[/math] | [math]\displaystyle{ 0 }[/math] |
| [math]\displaystyle{ 1 }[/math] | [math]\displaystyle{ 0 }[/math] | [math]\displaystyle{ 0 }[/math] |
| [math]\displaystyle{ 0 }[/math] | [math]\displaystyle{ 1 }[/math] | [math]\displaystyle{ 0 }[/math] |
| [math]\displaystyle{ 1 }[/math] | [math]\displaystyle{ 1 }[/math] | [math]\displaystyle{ 1 }[/math] |
для тернарной конъюнкции
| [math]\displaystyle{ a }[/math] | [math]\displaystyle{ b }[/math] | [math]\displaystyle{ c }[/math] | [math]\displaystyle{ a \land b \land c }[/math] |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 |
Конъюнкция коммутативна, ассоциативна и дистрибутивна по отношению к слабой дизъюнкции[13].
Многозначная логика
Операции, называемой в двоичной логике конъюнкция, в многозначных логиках обычно сопоставляется операция минимум: [math]\displaystyle{ min(a,b) }[/math], где [math]\displaystyle{ a, b \in \{0,\dots,k-1\}, }[/math] а [math]\displaystyle{ k }[/math] — значность логики; впрочем, возможны и другие варианты обобщения обычной конъюнкции на многозначный случай. Как правило, стараются сохранить совместимость с булевой алгеброй для значений операндов [math]\displaystyle{ 0 }[/math] и [math]\displaystyle{ k-1 }[/math].
Название этой операции минимум имеет смысл в логиках с любой значностью, в том числе и в двоичной логике, а названия конъюнкция, логи́ческое «И», логическое умноже́ние и просто «И» характерны для двоичной логики, а при переходе к многозначным логикам используются реже.
Классическая логика
В классическом исчислении высказываний свойства конъюнкции определяются с помощью аксиом. Классическое исчисление высказываний может быть задано разными системами аксиом, и некоторые из них будут описывать свойства конъюнкции. Один из самых распространённых вариантов включает 3 аксиомы для конъюнкции:
[math]\displaystyle{ a \land b \to a }[/math]
[math]\displaystyle{ a \land b \to b }[/math]
[math]\displaystyle{ a \to (b \to (a \land b)) }[/math]
С помощью этих аксиом можно доказать другие формулы, содержащие операцию конъюнкции. Обратите внимание, что в классическом исчислении высказываний не происходит вычисления результата по значениям операндов (как в булевой алгебре), а требуется доказать формулу как единое целое на основе аксиом и правил вывода.
Схемотехника
Логический элемент, реализующий функцию конъюнкции, называется схемой совпадения[13]. Мнемоническое правило для конъюнкции с любым количеством входов звучит так: На выходе будет:
- «1» тогда и только тогда, когда на всех входах есть «1»,
- «0» тогда и только тогда, когда хотя бы на одном входе есть «0»
Теория множеств
С точки зрения теории множеств, конъюнкция аналогична операции пересечения.
Программирование
В компьютерных языках используется два основных варианта конъюнкции: логическое «И» и побитовое (поразрядное) «И». Например, в языках C/C++ логическое «И» обозначается символом «&&», а побитовое — символом «&». В терминологии, используемой в C#, операцию «&» принято называть логическим «И», а операцию «&&» — условным «И», поскольку значения операндов являются условиями для продолжения вычисления. В языках Pascal/Delphi оба вида конъюнкции обозначаются с использованием ключевого слова «and», а результат действия определяется типом операндов. Если операнды имеют логический тип (например, Boolean) — выполняется логическая операция, если целочисленный (например, Byte) — поразрядная.
Логическое «И» применяется в операторах условного перехода или в аналогичных случаях, когда требуется получение результата [math]\displaystyle{ false }[/math] или [math]\displaystyle{ true }[/math]. Например:
if (a & b & c)
{
/* какие-то действия */
};
Сравнение в данном случае будет продолжаться до конца выражения, независимо от промежуточных результатов. Принцип работы условного «И» в аналогичной ситуации:
a = false; b = true; c = true;
if (a && b && c)
{
/* какие-то действия */
};
Проверка истинности выражения в данном случае остановится после проверки переменной a, так как дальнейшее сравнение не имеет смысла.
Результат будет равен [math]\displaystyle{ true }[/math], если оба операнда равны [math]\displaystyle{ true }[/math] (для числовых типов не равны [math]\displaystyle{ 0 }[/math]). В любом другом случае результат будет равен [math]\displaystyle{ false }[/math].
При этом применяется стандартное соглашение: если значение левого операнда равно [math]\displaystyle{ false }[/math], то значение правого операнда не вычисляется (вместо [math]\displaystyle{ b }[/math] может стоять сложная формула). Такое соглашение ускоряет исполнение программы и служит полезным приёмом в некоторых случаях. Компилятор Delphi поддерживает специальную директиву, включающую
{$B-}
или выключающую
{$B+}
подобное поведение. Например, если левый операнд проверяет возможность вычисления правого операнда:
if (a != 0 && b / a > 3)
{
/* какие-то действия */
};
В этом примере, благодаря проверке в левом операнде, в правом операнде никогда не произойдёт деления на ноль.
Побитовое «И» выполняет обычную операцию булевой алгебры для всех битов левого и правого операнда попарно. Например,
| если | |
| a = | [math]\displaystyle{ 01100101_2 }[/math] |
| b = | [math]\displaystyle{ 00101001_2 }[/math] |
| то | |
| a И b = | [math]\displaystyle{ 00100001_2 }[/math] |
Связь с естественным языком
Часто указывают на сходство между конъюнкцией и союзом «и» в естественном языке. Составное утверждение «A и B» считается истинным, когда истинны оба утверждения A и B, в противном случае составное утверждение ложно. Это в точности соответствует определению конъюнкции в булевой алгебре, если «истину» обозначать как [math]\displaystyle{ 1 }[/math], а «ложь» как [math]\displaystyle{ 0 }[/math]. При этом часто делают стандартную оговорку о неоднозначности естественного языка. Например, в зависимости от контекста союз «и» может нести дополнительный оттенок «и тогда», «и поэтому», «и потом». Отличие логики естественного языка от математической остроумно выразил американский математик Стивен Клини, заметив, что в естественном языке «Мэри вышла замуж и родила ребёнка» — не то же самое, что «Мэри родила ребёнка и вышла замуж».
См. также
Примечания
- ↑ 1,0 1,1 1,2 Кондаков, 1975, с. 264—266, 534—536.
- ↑ Ampersand. // Website Online Etymology Dictionary. Дата обращения: 7 февраля 2016. Архивировано 18 февраля 2011 года.
- ↑ Кондаков, 1975, с. 67.
- ↑ Стяжкин Н. И. . Формирование математической логики. — М.: Наука, 1967. — 508 с. — С. 321, 348, 352, 368.
- ↑ Earliest Uses of Symbols of Set Theory and Logic. // Website Jeff Miller Web Pages. Дата обращения: 7 февраля 2016. Архивировано 21 августа 2011 года.
- ↑ Кондаков, 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.
- ↑ 13,0 13,1 Словарь по кибернетике. 2-е изд / Под ред. В. С. Михалевича. — Киев: Украинская советская энциклопедия, 1989. — 751 с. — ISBN 5-88500-008-5.
Литература
- Кондаков Н. И. . Логический словарь-справочник. 2-е изд. — М.: Наука, 1975. — 720 с.
| |
