Логическое соединение

Логическая связка И

Диаграмма Венна ${\displaystyle A\wedge B\land C}$

В логике , математике и лингвистике , and ( ) является истинностно-функциональным оператором конъюнкции или логической конъюнкции . Логическая связка этого оператора обычно представляется как ^[1] ​​или или (префикс) или или ^[2], в котором является наиболее современным и широко используемым. ${\displaystyle \wedge }$ ${\displaystyle \wedge }$ ${\displaystyle \&}$ ${\displaystyle K}$ ${\displaystyle \times }$ ${\displaystyle \cdot }$ ${\displaystyle \wedge }$

Оператор «И» набора операндов истинен тогда и только тогда, когда все его операнды истинны, т. е. истинен тогда и только тогда, когда истинен и истинен. ${\displaystyle A\land B}$ ${\displaystyle A}$ ${\displaystyle B}$

Операндом конъюнкции является конъюнкт . ^[3]

Помимо логики, термин «конъюнкция» также относится к схожим понятиям в других областях:

• В естественном языке обозначение таких выражений , как английское « и »;
• В языках программирования короткое замыкание и управляющая структура ;
• В теории множеств — пересечение .
• В теории решеток — логическая конъюнкция ( точная нижняя граница ).

Обозначение

И обычно обозначается инфиксным оператором: в математике и логике он обозначается «клином» (Unicode U+2227 ∧ LOGICAL AND ), ^[1] или ; в электронике ; а в языках программирования , , или . В префиксной нотации Яна Лукасевича для логики оператором является , для польского koniunkcja . ^[4] ${\displaystyle \wedge }$ ${\displaystyle \&}$ ${\displaystyle \times }$ ${\displaystyle \cdot }$&&&and ${\displaystyle K}$

В математике соединение произвольного числа элементов можно обозначить как итеративную бинарную операцию с использованием «большого клина» ⋀ (Unicode U+22C0 ⋀ N-АРНОЕ ЛОГИЧЕСКОЕ И ): ^[5] ${\displaystyle a_{1},\ldots ,a_{n}}$

${\displaystyle \bigwedge _{i=1}^{n}a_{i}=a_{1}\wedge a_{2}\wedge \ldots a_{n-1}\wedge a_{n}}$

Определение

Логическая конъюнкция — это операция над двумя логическими значениями , обычно значениями двух предложений , которая производит значение «истина» тогда и только тогда, когда (также известно как «если и только тогда») оба ее операнда истинны. ^{[2] [1]}

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

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

Конъюнкции аргументов слева — истинные биты образуют треугольник Серпинского .

Таблица истинности : [ 1 ^{] [2]} ${\displaystyle A\land B}$

Определено другими операторами

В системах, где логическое соединение не является примитивом, его можно определить как ^[6]

${\displaystyle A\land B=\neg (A\to \neg B)}$

Это можно проверить с помощью следующей таблицы истинности (сравните последние два столбца):

или

${\displaystyle A\land B=\neg (\neg A\lor \neg B).}$

Это можно проверить с помощью следующей таблицы истинности (сравните последние два столбца):

Правила введения и исключения

Как правило вывода, введение конъюнкции является классически допустимой , простой формой аргумента . Форма аргумента имеет две посылки, и . Интуитивно, это позволяет сделать вывод об их конъюнкции. ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle A}$,

${\displaystyle B}$.

Следовательно , А и В.

или в записи логического оператора :

${\displaystyle A,}$

${\displaystyle B}$

${\displaystyle \vdash A\land B}$

Вот пример аргумента, который соответствует форме введения союза :

Боб любит яблоки.

Боб любит апельсины.

Следовательно, Боб любит яблоки, а Боб любит апельсины.

Устранение конъюнкции — это еще одна классически допустимая , простая форма аргумента . Интуитивно, она позволяет делать вывод из любой конъюнкции любого элемента этой конъюнкции.

${\displaystyle A}$и . ${\displaystyle B}$

Поэтому, . ${\displaystyle A}$

...или альтернативно,

${\displaystyle A}$и . ${\displaystyle B}$

Поэтому, . ${\displaystyle B}$

В записи логического оператора :

${\displaystyle A\land B}$

${\displaystyle \vdash A}$

...или альтернативно,

${\displaystyle A\land B}$

${\displaystyle \vdash B}$

Отрицание

Определение

Ложность конъюнкции доказывается установлением либо , либо . В терминах объектного языка это звучит так: ${\displaystyle A\land B}$ ${\displaystyle \neg A}$ ${\displaystyle \neg B}$

${\displaystyle \neg A\to \neg (A\land B)}$

Эту формулу можно рассматривать как частный случай

${\displaystyle (A\to C)\to ((A\land B)\to C)}$

когда — ложное утверждение. ${\displaystyle C}$

Другие стратегии доказательства

Если подразумевает , то и то, и другое доказывает ложность конъюнкции: ${\displaystyle A}$ ${\displaystyle \neg B}$ ${\displaystyle \neg A}$ ${\displaystyle A}$

${\displaystyle (A\to \neg {}B)\to \neg (A\land B)}$

Другими словами, ложность конъюнкции можно доказать, просто зная об отношении ее конъюнктов, и не обязательно об их истинностных значениях.

Эту формулу можно рассматривать как частный случай

${\displaystyle (A\to (B\to C))\to ((A\land B)\to C)}$

когда — ложное утверждение. ${\displaystyle C}$

Любое из вышеперечисленных доказательств является конструктивно обоснованным доказательством от противного.

Характеристики

коммутативность : да

ассоциативность : да ^[7]

дистрибутивность : с различными операциями, особенно с или

идемпотентность : да

монотонность : да

сохранение истинности: да
Когда все входные данные истинны, выходные данные также истинны.

сохранение ложности: да
Когда все входные данные ложны, выходной сигнал ложный.

Спектр Уолша : (1,-1,-1,1)

Нелинейность : 1 ( функция искривлена )

Если использовать двоичные значения для «истина» (1) и «ложь» (0), то логическое соединение работает точно так же, как обычное арифметическое умножение .

Применение в вычислительной технике

И логический вентиль

В программировании высокого уровня и цифровой электронике логическое соединение обычно представляется инфиксным оператором, обычно в виде ключевого слова, такого как " AND", алгебраическое умножение или символ амперсанда &(иногда удваивается, как в &&). Многие языки также предоставляют структуры управления коротким замыканием, соответствующие логическому соединению.

Логическая конъюнкция часто используется для побитовых операций, где 0соответствует ложному и 1истинному:

• 0 AND 0  =  0,
• 0 AND 1  =  0,
• 1 AND 0  =  0,
• 1 AND 1  =  1.

Эту операцию можно также применить к двум двоичным словам, рассматриваемым как битовые строки одинаковой длины, выполняя побитовое И каждой пары битов в соответствующих позициях. Например:

• 11000110 AND 10100011  =  10000010.

Это можно использовать для выбора части битовой строки с помощью битовой маски . Например,  =  извлекает четвертый бит из 8-битовой битовой строки.10011101 AND 0000100000001000

В компьютерных сетях битовые маски используются для получения сетевого адреса подсети в существующей сети из заданного IP-адреса путем выполнения операции «И» между IP-адресом и маской подсети .

Логическая конъюнкция « AND» также используется в операциях SQL для формирования запросов к базе данных .

Соответствие Карри–Ховарда связывает логическую связь с типами продуктов .

Теоретико-множественное соответствие

Принадлежность элемента множества пересечения в теории множеств определяется в терминах логической конъюнкции: тогда и только тогда, когда . Благодаря этому соответствию теоретико-множественное пересечение разделяет несколько свойств с логической конъюнкцией, таких как ассоциативность , коммутативность и идемпотентность . ${\displaystyle x\in A\cap B}$ ${\displaystyle (x\in A)\wedge (x\in B)}$

Естественный язык

Как и другие понятия, формализованные в математической логике, логический союз и связан с грамматическим союзом и в естественных языках , но не является им .

Английское "and" имеет свойства, не охватываемые логическим союзом. Например, "and" иногда подразумевает порядок, имеющий значение "then". Например, "They got married and had a child" в разговорной речи означает, что брак состоялся до рождения ребенка.

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

Смотрите также

• График И-инвертора
• И ворота
• Побитовое И
• Булева алгебра
• Булевский конъюнктивный запрос
• Булев домен
• Булева функция
• Булева функция
• Двойственность конъюнкции/дизъюнкции
• Устранение конъюнкции
• Союз (грамматика)
• Законы де Моргана
• Логика первого порядка
• Неравенства Фреше
• Однородность (лингвистика)
• Список тем по булевой алгебре
• Логическая дизъюнкция
• Логический граф
• Отрицание
• Операция
• Обозначение Пеано–Рассела
• Пропозициональное исчисление

Ссылки

1. "2.2: Конъюнкции и дизъюнкции". Mathematics LibreTexts . 2019-08-13 . Получено 2020-09-02 .
2. "Конъюнкция, отрицание и дизъюнкция". philosophy.lander.edu . Получено 2020-09-02 .
3. Beall, Jeffrey C. (2010). Логика: основы . Основы (1-е изд.). Лондон: Routledge. С. 17. ISBN 978-0-203-85155-5.
4. Юзеф Мария Бохенский (1959), A Précis of Mathematical Logic , перевод Отто Берда с французского и немецкого изданий, Дордрехт, Южная Голландия: D. Reidel, passim.
5. Weisstein, Eric W. "Conjunction". MathWorld--A Wolfram Web Resource . Получено 24 сентября 2024 г.
6. Смит, Питер. «Типы систем доказательств» (PDF) . стр. 4.
7. Howson, Colin (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Routledge. стр. 38. ISBN 978-0-415-13342-5.

Внешние ссылки

• «Конъюнкция», Энциклопедия математики , EMS Press , 2001 [1994]
• Wolfram MathWorld: Соединение
• "Таблица свойств и истинности предложений AND". Архивировано из оригинала 6 мая 2017 г.