Конъю́нкция (от лат. conjunctio — «союз, связь») — логическая операция , по смыслу максимально приближенная к союзу «и». Синонимы: логи́ческое «И» , логи́ческое умноже́ние , иногда просто «И» .

Конъюнкция может быть бинарной операцией (т. e. иметь два операнда), тернарной операцией (т. e. иметь три операнда), или n-арной операцией (т. e. иметь n операндов).

Инверсией конъюнкции является штрих Шеффера .

Обозначения

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

${\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)}$

(в случае использования точки, как знака логического умножения, этот знак, как и при обычном умножении в алгебре , может быть опущен: ${\displaystyle ab}$ ).

При этом обозначение ${\displaystyle a\land b}$ , рекомендованное стандартом ISO 31-11 , наиболее широко распространено в современной математике и математической логике , где оно, впрочем, конкурирует со знаком амперсанда & ; последний, появившись ещё в I веке до н. э. как графическое сокращение ( лигатура ) латинского союза et ‘и’, уже Якобом и Иоганном Бернулли в 1685 году использовался в качестве логической связки (у них он, однако, связывал не высказывания , а понятия ) . Джордж Буль (а за ним — и другие пионеры систематического применения символического метода к логике: У. С. Джевонс , Э. Шрёдер , П. С. Порецкий ) обозначал конъюнкцию знаком ${\displaystyle \cdot }$ — как обычное умножение . Символ ⋀ (перевёрнутый знак дизъюнкции ) в качестве обозначения конъюнкции был предложен Арендом Гейтингом (1930) .

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

Наконец, при естественном упорядочении значений истинности двузначной логики (когда полагают, что ${\displaystyle 0<1}$ ), оказывается, что ${\displaystyle (a\land b)\,=\,\min(a,b).}$ Таким образом, конъюнкция оказывается частным случаем операции вычисления минимума ; это открывает наиболее естественный способ определить операцию конъюнкции в системах многозначной логики (хотя иногда рассматривают и другие способы обобщения конъюнкции — например, такой: ${\displaystyle (a\land b)\,=\,ab\;(\operatorname {mod} k)}$ в случае k -значной логики, в которой множество значений истинности представлено начальным отрезком ${\displaystyle \{0,\dots ,k-1\}}$ полугруппы ${\displaystyle \mathbb {N} }$ натуральных чисел ) .

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

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

Правило: результат равен наименьшему операнду.

Описание.
В булевой алгебре конъюнкция — это функция двух, трёх или более переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества ${\displaystyle \{0,1\}}$ . Результат также принадлежит множеству ${\displaystyle \{0,1\}}$ . Вычисление результата производится по простому правилу, либо по таблице истинности . Вместо значений ${\displaystyle 0,1}$ может использоваться любая другая пара подходящих символов, например ${\displaystyle false,true}$ или ${\displaystyle F,T}$ или «ложь», «истина», но при таком обозначении необходимо дополнительно доопределять старшинство, например, ${\displaystyle true>false}$ , при цифровом обозначении старшинство естественно ${\displaystyle 1>0}$ .
Правило: результат равен ${\displaystyle 1}$ , если все операнды равны ${\displaystyle 1}$ ; во всех остальных случаях результат равен ${\displaystyle 0}$ .

Таблицы истинности:
для бинарной конъюнкции

${\displaystyle a}$	${\displaystyle b}$	${\displaystyle a\land b}$
${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$
${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle 0}$
${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle 0}$
${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$

для тернарной конъюнкции

${\displaystyle a}$	${\displaystyle b}$	${\displaystyle c}$	${\displaystyle a\land b\land c}$
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

Конъюнкция коммутативна , ассоциативна и дистрибутивна по отношению к слабой дизъюнкции .

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

Операции, называемой в двоичной логике конъюнкция , в многозначных логиках обычно сопоставляется операция минимум : ${\displaystyle min(a,b)}$ , где ${\displaystyle a,b\in \{0,\dots ,k-1\},}$ а ${\displaystyle k}$ — значность логики; впрочем, возможны и другие варианты обобщения обычной конъюнкции на многозначный случай. Как правило, стараются сохранить совместимость с булевой алгеброй для значений операндов ${\displaystyle 0}$ и ${\displaystyle k-1}$ .

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

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

В классическом исчислении высказываний свойства конъюнкции определяются с помощью аксиом . Классическое исчисление высказываний может быть задано разными системами аксиом, и некоторые из них будут описывать свойства конъюнкции. Один из самых распространённых вариантов включает 3 аксиомы для конъюнкции:
${\displaystyle a\land b\to a}$
${\displaystyle a\land b\to b}$
${\displaystyle a\to (b\to (a\land b))}$

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

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

Логический элемент, реализующий функцию конъюнкции, называется схемой совпадения . Мнемоническое правило для конъюнкции с любым количеством входов звучит так: На выходе будет:

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

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

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

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

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

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

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

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

a = false; b = true; c = true;
if (a && b && c) 
{
    /* какие-то действия */ 
};

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

Результат будет равен ${\displaystyle true}$ , если оба операнда равны ${\displaystyle true}$ (для числовых типов не равны ${\displaystyle 0}$ ). В любом другом случае результат будет равен ${\displaystyle false}$ .

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

{$B-}

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

{$B+}

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

if (a != 0 && b / a > 3) 
{
    /* какие-то действия */
};

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

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

если
a =	${\displaystyle 01100101_{2}}$
b =	${\displaystyle 00101001_{2}}$
то
a И b =	${\displaystyle 00100001_{2}}$

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

Часто указывают на сходство между конъюнкцией и союзом «и» в естественном языке. Составное утверждение « A и B » считается истинным, когда истинны оба утверждения A и B , в противном случае составное утверждение ложно. Это в точности соответствует определению конъюнкции в булевой алгебре, если «истину» обозначать как ${\displaystyle 1}$ , а «ложь» как ${\displaystyle 0}$ . При этом часто делают стандартную оговорку о неоднозначности естественного языка. Например, в зависимости от контекста союз «и» может нести дополнительный оттенок «и тогда», «и поэтому», «и потом». Отличие логики естественного языка от математической выразил американский математик Стивен Клини , заметив, что в естественном языке «Мэри вышла замуж и родила ребёнка» — не то же самое, что «Мэри родила ребёнка и вышла замуж».

См. также

• Идентичность
• Отрицание
• Дизъюнкция
• Эквиваленция
• Исключающее или
• Импликация
• Обратная импликация
• Штрих Шеффера
• Стрелка Пирса
• Таблица истинности
• Закон тождества

Примечания

Литература

• Кондаков Н. И. . . — М. : Наука , 1975. — 720 с.