Конъюнкция

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
У этого термина существуют и другие значения, см. Конъюнкция (значения).

Шаблон:Булева функция Конъю́нкция (от лат. 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. ↑ 1,0 1,1 1,2 Кондаков, 1975, с. 264—266, 534—536.
  2. ↑ Ampersand. // Website Online Etymology Dictionary. Дата обращения: 7 февраля 2016. Архивировано 18 февраля 2011 года.
  3. ↑ Кондаков, 1975, с. 67.
  4. ↑ Стяжкин Н. И. . Формирование математической логики. — М.: Наука, 1967. — 508 с. — С. 321, 348, 352, 368.
  5. ↑ Earliest Uses of Symbols of Set Theory and Logic. // Website Jeff Miller Web Pages. Дата обращения: 7 февраля 2016. Архивировано 21 августа 2011 года.
  6. ↑ Кондаков, 1975, с. 30.
  7. ↑ Пратт Т. . Языки программирования: разработка и реализация. — М.: Мир, 1979. — 574 с. — С. 352, 439.
  8. ↑ Грогоно П. . Программирование на языке Паскаль. — М.: Мир, 1982. — 384 с. — С. 51.
  9. ↑ Вегнер П. . Программирование на языке Ада. — М.: Мир, 1983. — 240 с. — С. 68.
  10. ↑ Эллис М.[en], Строуструп Б. . Справочное руководство по языку программирования C++ с комментариями. — М.: Мир, 1992. — 445 с. — ISBN 5-03-002868-4. — С. 65, 86—87.
  11. ↑ Яблонский С. В. . Введение в дискретную математику. — М.: Наука, 1979. — 272 с. — С. 9—10, 37.
  12. ↑ Рвачёв В. Л. . Теория R-функций и некоторые её приложения. — Киев: Наукова думка, 1982. — 552 с. — С. 38, 66.
  13. ↑ 13,0 13,1 Словарь по кибернетике. 2-е изд / Под ред. В. С. Михалевича. — Киев: Украинская советская энциклопедия, 1989. — 751 с. — ISBN 5-88500-008-5.

Литература


Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Конъюнкция&oldid=5844836