Gfrktyl

Конъюнкция
И, AND
Диаграмма Венна
Определение	xy{displaystyle xy}
Таблица истинности	(0001){displaystyle (0001)}
Логический вентиль
Нормальные формы
Дизъюнктивная	xy{displaystyle xy}
Конъюнктивная	xy{displaystyle xy}
Полином Жегалкина	xy{displaystyle xy}
Принадлежность предполным классам
Сохраняет 0	Да
Сохраняет 1	Да
Монотонна	Да
Линейна	Нет
Самодвойственна	Нет

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

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

Обозначения |

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

a∧b,a&&b,a&b,a⋅b,aANDb,min(a,b){displaystyle aland b,quad aAnd And b,quad aAnd b,quad acdot b,quad a,,mathrm {AND} ,,b,quad min(a,b)}

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

При этом обозначение a∧b{displaystyle aland b} наиболее широко распространено в современной математике и математической логике, где оно, впрочем, конкурирует со знаком амперсанда &^[1]; последний, появившись ещё в I веке до н. э. как графическое сокращение (лигатура) латинского союза et ‘и’, уже Якобом и Иоганном Бернулли в 1685 году использовался в качестве логической связки (у них он, однако, связывал не высказывания, а понятия)^[2][3]. Джордж Буль (а за ним — и другие пионеры систематического применения символического метода к логике: У. С. Джевонс, Э. Шрёдер, П. С. Порецкий) обозначал конъюнкцию знаком ⋅{displaystyle cdot } — как обычное умножение^[4]. Символ ⋀ (перевёрнутый знак дизъюнкции) в качестве обозначения конъюнкции был предложен Арендом Гейтингом (1930)^[5].

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

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

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

Определение.

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

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

Описание.

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

Правило: результат равен 1{displaystyle 1}, если все операнды равны 1{displaystyle 1}; во всех остальных случаях результат равен 0{displaystyle 0}.

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

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

a{displaystyle a}	b{displaystyle b}	a∧b{displaystyle aland b}
0{displaystyle 0}	0{displaystyle 0}	0{displaystyle 0}
1{displaystyle 1}	0{displaystyle 0}	0{displaystyle 0}
0{displaystyle 0}	1{displaystyle 1}	0{displaystyle 0}
1{displaystyle 1}	1{displaystyle 1}	1{displaystyle 1}

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

a{displaystyle a}	b{displaystyle b}	c{displaystyle c}	a∧b∧c{displaystyle aland bland 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

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

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

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

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

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

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

a∧b→a{displaystyle aland bto a}

a∧b→b{displaystyle aland bto b}

a→(b→(a∧b)){displaystyle ato (bto (aland b))}

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

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

Логический элемент «И»

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

• «1» тогда и только тогда, когда на всех входах есть «1»,


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

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

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

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

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

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

if (a & b & c) 

{

    /* какие-то действия */

};

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

a = false; b = true; c = true;

if (a && b && c) 

{

    /* какие-то действия */ 

};

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

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

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

{$B-}

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

{$B+}

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

if (a != 0 && b / a > 3) 

{

    /* какие-то действия */

};

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

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

если
a =	011001012{displaystyle 01100101_{2}}
b =	001010012{displaystyle 00101001_{2}}
то
a И b =	001000012{displaystyle 00100001_{2}}

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

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

Примечания |

Литература |

• Кондаков Н. И.  Логический словарь-справочник. 2-е изд. — М.: Наука, 1975. — 720 с.