Русская Википедия:Конъюнкция
Шаблон:Другие значения Шаблон:Булева функция Конъю́нкция (от Шаблон:Lang-lat — «союз, связь») — логическая операция, по смыслу максимально приближенная к союзу «и». Синонимы: логи́ческое «И», логи́ческое умноже́ние, иногда просто «И»Шаблон:Sfn.
Конъюнкция может быть бинарной операцией (т. e. иметь два операнда), тернарной операцией (т. e. иметь три операнда), или n-арной операцией (т. e. иметь n операндов).
Инверсией конъюнкции является штрих Шеффера.
Обозначения
Наиболее часто встречаются следующие обозначения для операции конъюнкции:
<math>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>a b</math>[1]).
При этом обозначение <math>a \land b</math>, рекомендованное стандартом ISO 31-11, наиболее широко распространено в современной математике и математической логике, где оно, впрочем, конкурирует со знаком амперсанда Шаблон:Big[1]; последний, появившись ещё в I веке Шаблон:Донэ как графическое сокращение (лигатура) латинского союза et ‘и’, уже Якобом и Иоганном Бернулли в 1685 году использовался в качестве логической связки (у них он, однако, связывал не высказывания, а понятия)[2]Шаблон:Sfn. Джордж Буль (а за ним — и другие пионеры систематического применения символического метода к логике: У. С. Джевонс, Э. Шрёдер, П. С. Порецкий) обозначал конъюнкцию знаком <math>\cdot</math> — как обычное умножение[3]. Символ Шаблон:Big (перевёрнутый знак дизъюнкции) в качестве обозначения конъюнкции был предложен Арендом Гейтингом (1930)[4].
Обозначение ⋀
для конъюнкции было использовано и в раннем языке программирования Алгол 60Шаблон:Sfn. Однако из-за отсутствия соответствующего символа в стандартных наборах символов (например, в ASCII или EBCDIC), применявшихся на большинстве компьютеров, в получивших наибольшее распространение языках программирования были предусмотрены иные обозначения для конъюнкции. Так, в Фортране IV и PL/I применялись соответственно обозначения .AND.
и &
(с возможностью замены последнего на ключевое слово AND
)[5]; в языках Паскаль и Ада используется зарезервированное слово and
[6][7]; в языках C и C++ применяются обозначения &
для побитовой конъюнкции и &&
для логической конъюнкции[8]).
Наконец, при естественном упорядочении значений истинности двузначной логики (когда полагают, что <math>0 < 1</math>), оказывается, что <math>(a \land b)\,=\,\min(a,b).</math> Таким образом, конъюнкция оказывается частным случаем операции вычисления минимума; это открывает наиболее естественный способ определить операцию конъюнкции в системах многозначной логики (хотя иногда рассматривают и другие способы обобщения конъюнкции — например, такой: <math>(a \land b)\,=\,ab\;(\operatorname{mod} k)</math> в случае k-значной логики, в которой множество значений истинности представлено начальным отрезком <math>\{0,\dots,k-1\}</math> полугруппы <math>\mathbb N</math> натуральных чисел)[9][10].
Булева алгебра
Определение.
Логическая функция MIN в двухзначной (двоичной) логике называется конъюнкция (логи́ческое «И», логи́ческое умноже́ние или просто «И»).
Правило: результат равен наименьшему операнду.
Описание.
В булевой алгебре конъюнкция — это функция двух, трёх или более переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества <math>\{0, 1\}</math>. Результат также принадлежит множеству <math>\{0, 1\}</math>. Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений <math>0, 1</math> может использоваться любая другая пара подходящих символов, например <math>false, true</math> или <math>F, T</math> или «ложь», «истина», но при таком обозначении необходимо дополнительно доопределять старшинство, например, <math>true > false</math>, при цифровом обозначении старшинство естественно <math>1 > 0</math>.
Правило: результат равен <math>1</math>, если все операнды равны <math>1</math>; во всех остальных случаях результат равен <math>0</math>.
Таблицы истинности:
для бинарной конъюнкции
<math>a</math> | <math>b</math> | <math>a \land b</math> |
---|---|---|
<math>0</math> | <math>0</math> | <math>0</math> |
<math>1</math> | <math>0</math> | <math>0</math> |
<math>0</math> | <math>1</math> | <math>0</math> |
<math>1</math> | <math>1</math> | <math>1</math> |
для тернарной конъюнкции
<math>a</math> | <math>b</math> | <math>c</math> | <math>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 |
Конъюнкция коммутативна, ассоциативна и дистрибутивна по отношению к слабой дизъюнкции[11].
Многозначная логика
Операции, называемой в двоичной логике конъюнкция, в многозначных логиках обычно сопоставляется операция минимум: <math>min(a,b)</math>, где <math>a, b \in \{0,\dots,k-1\},</math> а <math>k</math> — значность логики; впрочем, возможны и другие варианты обобщения обычной конъюнкции на многозначный случай. Как правило, стараются сохранить совместимость с булевой алгеброй для значений операндов <math>0</math> и <math>k-1</math>.
Название этой операции минимум имеет смысл в логиках с любой значностью, в том числе и в двоичной логике, а названия конъюнкция, логи́ческое «И», логическое умноже́ние и просто «И» характерны для двоичной логики, а при переходе к многозначным логикам используются реже.
Классическая логика
В классическом исчислении высказываний свойства конъюнкции определяются с помощью аксиом. Классическое исчисление высказываний может быть задано разными системами аксиом, и некоторые из них будут описывать свойства конъюнкции. Один из самых распространённых вариантов включает 3 аксиомы для конъюнкции:
<math>a \land b \to a</math>
<math>a \land b \to b</math>
<math>a \to (b \to (a \land b))</math>
С помощью этих аксиом можно доказать другие формулы, содержащие операцию конъюнкции. Обратите внимание, что в классическом исчислении высказываний не происходит вычисления результата по значениям операндов (как в булевой алгебре), а требуется доказать формулу как единое целое на основе аксиом и правил вывода.
Схемотехника
Логический элемент, реализующий функцию конъюнкции, называется схемой совпадения[11]. Мнемоническое правило для конъюнкции с любым количеством входов звучит так: На выходе будет:
- «1» тогда и только тогда, когда на всех входах есть «1»,
- «0» тогда и только тогда, когда хотя бы на одном входе есть «0»
Теория множеств
С точки зрения теории множеств, конъюнкция аналогична операции пересечения.
Программирование
В компьютерных языках используется два основных варианта конъюнкции: логическое «И» и побитовое (поразрядное) «И». Например, в языках C/C++ логическое «И» обозначается символом «&&», а побитовое — символом «&». В терминологии, используемой в C#, операцию «&» принято называть логическим «И», а операцию «&&» — условным «И», поскольку значения операндов являются условиями для продолжения вычисления. В языках Pascal/Delphi оба вида конъюнкции обозначаются с использованием ключевого слова «and», а результат действия определяется типом операндов. Если операнды имеют логический тип (например, Boolean) — выполняется логическая операция, если целочисленный (например, Byte) — поразрядная.
Логическое «И» применяется в операторах условного перехода или в аналогичных случаях, когда требуется получение результата <math>false</math> или <math>true</math>. Например:
if (a & b & c)
{
/* какие-то действия */
};
Сравнение в данном случае будет продолжаться до конца выражения, независимо от промежуточных результатов. Принцип работы условного «И» в аналогичной ситуации:
a = false; b = true; c = true;
if (a && b && c)
{
/* какие-то действия */
};
Проверка истинности выражения в данном случае остановится после проверки переменной a, так как дальнейшее сравнение не имеет смысла.
Результат будет равен <math>true</math>, если оба операнда равны <math>true</math> (для числовых типов не равны <math>0</math>). В любом другом случае результат будет равен <math>false</math>.
При этом применяется стандартное соглашение: если значение левого операнда равно <math>false</math>, то значение правого операнда не вычисляется (вместо <math>b</math> может стоять сложная формула). Такое соглашение ускоряет исполнение программы и служит полезным приёмом в некоторых случаях. Компилятор Delphi поддерживает специальную директиву, включающую
{$B-}
или выключающую
{$B+}
подобное поведение. Например, если левый операнд проверяет возможность вычисления правого операнда:
if (a != 0 && b / a > 3)
{
/* какие-то действия */
};
В этом примере, благодаря проверке в левом операнде, в правом операнде никогда не произойдёт деления на ноль.
Побитовое «И» выполняет обычную операцию булевой алгебры для всех битов левого и правого операнда попарно. Например,
если | |
a = | <math>01100101_2</math> |
b = | <math>00101001_2</math> |
то | |
a И b = | <math>00100001_2</math> |
Связь с естественным языком
Часто указывают на сходство между конъюнкцией и союзом «и» в естественном языке. Составное утверждение «A и B» считается истинным, когда истинны оба утверждения A и B, в противном случае составное утверждение ложно. Это в точности соответствует определению конъюнкции в булевой алгебре, если «истину» обозначать как <math>1</math>, а «ложь» как <math>0</math>. При этом часто делают стандартную оговорку о неоднозначности естественного языка. Например, в зависимости от контекста союз «и» может нести дополнительный оттенок «и тогда», «и поэтому», «и потом». Отличие логики естественного языка от математической выразил американский математик Стивен Клини, заметив, что в естественном языке «Мэри вышла замуж и родила ребёнка» — не то же самое, что «Мэри родила ребёнка и вышла замуж».
См. также
- Идентичность
- Отрицание
- Дизъюнкция
- Импликация
- Обратная импликация
- Штрих Шеффера
- Таблица истинности
- Закон тождества
Примечания
Литература
Шаблон:Викисловарь Шаблон:ВС Шаблон:Булева алгебра Шаблон:Логика
- ↑ 1,0 1,1 Ошибка цитирования Неверный тег
<ref>
; для сносокKond264
не указан текст - ↑ Шаблон:Cite web
- ↑ Шаблон:Книга — С. 321, 348, 352, 368.
- ↑ Шаблон:Cite web
- ↑ Шаблон:Книга — С. 352, 439.
- ↑ Шаблон:Книга — С. 51.
- ↑ Шаблон:Книга — С. 68.
- ↑ Шаблон:Книга — С. 65, 86—87.
- ↑ Шаблон:Книга — С. 9—10, 37.
- ↑ Шаблон:Книга — С. 38, 66.
- ↑ 11,0 11,1 Шаблон:Книга
- Страницы, использующие устаревший тег source
- Русская Википедия
- Страницы с неработающими файловыми ссылками
- Математическая логика
- Логика высказываний
- Теория множеств
- Логические элементы
- Бинарные операции
- Страницы, где используется шаблон "Навигационная таблица/Телепорт"
- Страницы с телепортом
- Википедия
- Статья из Википедии
- Статья из Русской Википедии
- Страницы с ошибками в примечаниях