# Конъюнкция

[править | править код]
Материал из Википедии — свободной энциклопедии
(перенаправлено с «Логическое умножение»)
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 13 июня 2023 года; проверки требуют 9 правок.
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 13 июня 2023 года; проверки требуют 9 правок.
Перейти к навигации Перейти к поиску

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

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

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

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

## Обозначения[править | править код]

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

a ∧ b , a & & b , a & b , a ⋅ b , a A N D b , min ( a , b ) {\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)}

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

При этом обозначение a ∧ b {\displaystyle a\land b} , рекомендованное стандартом ISO 31-11, наиболее широко распространено в современной математике и математической логике, где оно, впрочем, конкурирует со знаком амперсанда &[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 (a\land b)\,=\,\min(a,b).} Таким образом, конъюнкция оказывается частным случаем операции вычисления минимума; это открывает наиболее естественный способ определить операцию конъюнкции в системах многозначной логики (хотя иногда рассматривают и другие способы обобщения конъюнкции — например, такой: ( a ∧ b ) = a b ( mod ⁡ k ) {\displaystyle (a\land 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} может использоваться любая другая пара подходящих символов, например f a l s e , t r u e {\displaystyle false,true} или F , T {\displaystyle F,T} или «ложь», «истина», но при таком обозначении необходимо дополнительно доопределять старшинство, например, t r u e > f a l s e {\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 a\land 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 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

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

## Многозначная логика[править | править код]

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

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

## Классическая логика[править | править код]

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

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

## Схемотехника[править | править код]

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

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

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

## Теория множеств[править | править код]

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

## Программирование[править | править код]

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

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

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

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

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

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

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

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

    {$B-}

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

    {$B+}

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

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

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

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

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

## Связь с естественным языком[править | править код]

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

## См. также[править | править код]

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

## Примечания[править | править код]

1. ↑ Перейти обратно: 1 2 3 Кондаков, 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. ↑ Перейти обратно: 1 2 Словарь по кибернетике. 2-е изд / Под ред. В. С. Михалевича. — Киев: Украинская советская энциклопедия, 1989. — 751 с. — ISBN 5-88500-008-5.

## Литература[править | править код]

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

| В Викисловаре есть статья «конъюнкция»

Источник — https://ru.wikipedia.org/w/index.php?title=Конъюнкция&oldid=134119680
Категории:

- Математическая логика
- Логика высказываний
- Теория множеств
- Логические элементы
- Бинарные операции

Скрытые категории:

- Страницы, использующие устаревший тег source
- Википедия:Cite web (не указан язык)
- Википедия:Cite web (заменить webcitation-архив: deadlink no)
- Страницы, использующие волшебные ссылки ISBN
- Статьи со ссылками на Викисловарь
- Страницы, на которых шаблон Викисловарь изменит ссылку