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

редактировать

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

Определение	$xy {\ displaystyle xy}$ $xy$
Таблица истинности	$(0001) {\ displaystyle (0001)}$ ${\ displaystyle (0001)}$
Логический элемент
Нормальные формы
Дизъюнктивная	$xy {\ displaystyle xy}$ $xy$
Конъюнктивная	$xy {\ displaystyle xy}$ $xy$
Жегалкин многочлен	$xy {\ displaystyle xy}$ $xy$
Решетки поста
с сохранением 0	да
с сохранением 1	да
Монотонный	no
Аффинный	no
v t

Диаграмма Венна

A ∧ B ∧ C {\ displaystyle A \ land B \ land C}

{\ displaystyle A \ land B \ land C}

В логике, математике и лингвистике, And (∧) - это функционал истинности оператор логической конъюнкции ; и для набора операндов истинно тогда и только тогда, когда все его операнды истинны. Логическая связка , представляющая этот оператор, обычно записывается как ∧ или ⋅.

$A ∧ B {\ displaystyle A \ land B}$ $A \ land B$ истинно тогда и только тогда, когда $A {\ displaystyle A}$ $A$ верно, а $B {\ displaystyle B}$ $B$ верно.

Операнд конъюнкции - это конъюнкт .

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

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

Содержание

1 Обозначение
2 Определение
- 2.1 Таблица истинности
- 2.2 Определено другими операторами
3 Введение и правила исключения
4 Отрицание
- 4.1 Определение
- 4.2 Другие стратегии доказательства
5 Свойства
6 Приложения в компьютерной инженерии
7 Теоретико-множественное соответствие
8 Естественный язык
9 См. Также
10 Ссылки
11 Внешние ссылки

Обозначение

И обычно обозначают инфиксным оператором: в математике и логике это обозначает помечено ∧,или × ; в электронике, ⋅ ; а в языках программирования - , или и. В префиксной нотации Яна Лукасевича для логики используется оператор K для польской конюнкции.

Определение

Логическое соединение - это операция с двумя логическими значениями, обычно значениями двух предложений, которая производит значение true тогда и только тогда, когда оба его операнда истинны.

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

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

Соединения аргументов слева - истина бит образуют треугольник Серпинского.

Истина таблица из $A ∧ B {\ displaystyle A \ land B}$ $A \ land B$ :

$A {\ displaystyle A}$ $A$	$B {\ displaystyle B}$ $B$	$A ∧ B {\ displaystyle A \ wedge B }$ $A \ клин B$
T	T	T
T	F	F
F	T	F
F	F	F

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

В системах, где логическое соединение не является примитивом, оно может быть определено как

A ∧ B = ¬ (A → ¬ B) {\ displaystyle A \ land B = \ neg (A \ to \ neg B)}

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

или

A ∧ B = ¬ (¬ A ∨ ¬ B). {\ displaystyle A \ land B = \ neg (\ neg A \ lor \ neg B).}

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

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

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

Следовательно, A и B.

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

A, {\ displaystyle A,}

A,

B {\ displaystyle B}

B

⊢ A ∧ B {\ displaystyle \ vdash A \ land B}

{\ displaystyle \ vdash A \ land B}

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

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

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

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

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

A и B.

Следовательно, A.

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

A и B.

Следовательно, B.

In логический оператор обозначение:

A ∧ B {\ displaystyle A \ land B}

{\ displaystyle A \ land B}

⊢ A {\ displaystyle \ vdash A}

\ vdash A

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

A ∧ B {\ displaystyle A \ land B}

{\ displaystyle A \ land B}

⊢ B {\ displaystyle \ vdash B}

\ vdash B

Отрицание

Определение

A конъюнкция $A ∧ B {\ displaystyle A \ land B }$ $A \ land B$ оказывается ложным путем установления либо $¬ A {\ displaystyle \ neg A}$ $\ neg A$ , либо $¬ B {\ displaystyle \ neg B}$ $\ neg B$ . С точки зрения объектного языка это читается как

¬ A → ¬ (A ∧ B) {\ displaystyle \ neg A \ to \ neg (A \ land B)}

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

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

(A → C) → ((A ∧ B) → C) {\ displaystyle (A \ to C) \ to ((A \ land B) \ to C)}

{\ Displaystyle (от A \ к C) \ к ((A \ земля B) \ к C)}

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

Другие стратегии проверки

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

(A → ¬ B) → ¬ (A ∧ B) {\ displaystyle (A \ to \ neg {} B) \ to \ neg (A \ land B)}

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

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

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

(A → (B → C)) → ((A ∧ B) → C) {\ displaystyle (A \ to (B \ to C)) \ to ((A \ land B) \ to C)}

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

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

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

Свойства

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

$A ∧ B {\ displaystyle A \ land B}$ $A \ land B$	$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$	$B ∧ A {\ displaystyle B \ land A}$ ${\ displaystyle B \ land A}$
	$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$

ассоциативность : да

$A {\ displaystyle ~ A}$ $~A$	$∧ {\ displaystyle ~~~ \ land ~~~}$ ${\ displaystyle ~~~ \ land ~~~}$	$(В ∧ C) {\ displaystyle (B \ land C)}$ ${\ displaystyle (B \ land C)}$	$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$			$(A ∧ B) {\ displaystyle (A \ land B)}$ $(A \ land B)$	$∧ { \ displaystyle ~~~ \ land ~~~}$ ${\ displaystyle ~~~ \ land ~~~}$	$C {\ displaystyle ~ C}$ $~ C$
	$∧ {\ displaystyle ~~~ \ land ~~~}$ ${\ displaystyle ~~~ \ land ~~~}$		$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$		$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$		$∧ {\ displaystyle ~~~ \ land ~~~}$ ${\ displaystyle ~~~ \ land ~~~}$

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

$A {\ displaystyle ~ A}$ $~A$	$∧ {\ displaystyle \ land}$ $\ land$	$(B ∨ C) {\ displaystyle (B \ lor C)}$ ${ \ displaystyle (B \ lor C)}$	$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$			$(A ∧ B) {\ displaystyle ( A \ земля B)}$ $(A \ land B)$	$∨ {\ displaystyle \ lor}$ $\ lor$	$(A ∧ C) {\ displaystyle (A \ land C)}$ ${\ displaystyle (A \ land C)}$
	$∧ {\ displaystyle \ land}$ $\ land$		$⇔ {\ Displaystyl е \ Leftrightarrow}$ $\ Leftrightarrow$		$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$		$∨ {\ displaystyle \ lor}$ $\ lor$

другие

с эксклюзивным или :

$A {\ displaystyle ~ A}$ $~A$	$∧ {\ displaystyle \ land}$ $\ land$	$(B ⊕ C) {\ displaystyle (B \ oplus C)}$ $(B \ oplus C)$	$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$			$(A ∧ B) {\ displaystyle (A \ land B)}$ $(A \ land B)$	$⊕ {\ displaystyle \ oplus}$ $\ oplus$	$(A ∧ C) {\ displaystyle (A \ land C)}$ ${\ displaystyle (A \ land C)}$
	$∧ {\ displaystyle \ land}$ $\ land$		$⇔ {\ displaystyle \ Leftrightarrow }$ $\ Leftrightarrow$		$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$		$⊕ {\ displaystyle \ oplus}$ $\ oplus$

с неимпликационным материалом :

$A {\ displaystyle ~ A}$ $~A$	$∧ {\ displaystyle \ land}$ $\ land$	$(B ↛ C) {\ displaystyle (B \ nrightarrow C)}$ $(B \ nrightarrow C)$	$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$			$(A ∧ B) {\ displaystyle (A \ land B)}$ $(A \ land B)$	$↛ {\ displaystyle \ nrightarrow}$ $\ nrightarrow$	$(A ∧ C) {\ displaystyle (A \ land C)}$ ${\ displaystyle (A \ land C)}$
	$∧ {\ displaystyle \ land}$ $\ land$		$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$		$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$		$↛ {\ displaystyle \ nrightarrow}$ $\ nrightarrow$

с собой:

$A {\ displaystyle ~ A}$ $~A$	$∧ {\ displaystyle \ land}$ $\ land$	$(B ∧ C) {\ displaystyle (B \ land C)}$ ${\ displaystyle (B \ land C)}$	$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$			$(A ∧ B) {\ displaystyle (A \ land B)}$ $(A \ land B)$	$∧ {\ displaystyle \ land}$ $\ land$	$(A ∧ C) {\ displaystyle (A \ land C)}$ ${\ displaystyle (A \ land C)}$
	$∧ {\ displaystyle \ land}$ $\ land$		$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$		$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$		$∧ {\ displaystyle \ land}$ $\ land$

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

$A {\ displaystyle ~ A ~}$ $~ A ~$	$∧ {\ displaystyle ~ \ land ~}$ ${\ displaystyle ~ \ land ~}$	$A {\ displaystyle ~ A ~}$ $~ A ~$	$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$	$A {\ displaystyle A ~}$ $A ~$
	$∧ {\ displaystyle ~ \ земля ~}$ ${\ displaystyle ~ \ land ~}$		$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$

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

$A → B {\ displaystyle A \ rightarrow B}$ $A \ rightarrow B$	$⇒ {\ displaystyle \ Rightarrow}$ $\ Rightarrow$			$( A ∧ C) {\ displaystyle (A \ land C)}$ ${\ displaystyle (A \ land C)}$	$→ {\ displaystyle \ rightarrow}$ $\ rightarrow$	$(B ∧ C) {\ displaystyle (B \ land C)}$ ${\ displaystyle (B \ land C)}$
	$⇒ {\ displaystyle \ Rightarrow}$ $\ Rightarrow$		$⇔ {\ displaystyle \ Leftrightarrow}$ $\ Leftrightarrow$		$→ {\ displaystyle \ rightarrow}$ $\ rightarrow$

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

$A ∧ B {\ displaystyle A \ land B}$ $A \ land B$	$⇒ {\ displaystyle \ Rightarrow}$ $\ Rightarrow$	$A ∧ B {\ displaystyle A \ land B}$ $A \ land B$
	$⇒ {\ displaystyle \ Rightarrow}$ $\ Rightarrow$
		(подлежит проверке)

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

$A ∧ B {\ displaystyle A \ land B}$ $A \ land B$	$⇒ {\ displaystyle \ Rightarrow}$ $\ Rightarrow$	$A ∨ B {\ displaystyle A \ lor B}$ $A \ lor B$
	$⇒ {\ displaystyle \ Rightarrow}$ $\ Rightarrow$
(подлежит проверке)

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

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

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

Приложения в компьютерной инженерии

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

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

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

0 И 0= 0,
0 И 1= 0,
1 И 0= 0,
1 И 1= 1.

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

11000110 AND 10100011= 10000010.

Это может использоваться для выбора части строки битов с использованием битовой маски. Например, 1001 1 101 AND 0000 1 000= 0000 1 000извлекает пятый бит 8-битная битовая строка.

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

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

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

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

Принадлежность к элементу пересечения множество в теории множеств определяется в терминах логической конъюнкции: x ∈ A ∩ B тогда и только тогда, когда (x ∈ A) ∧ (x ∈ B). Благодаря этому соответствию теоретико-множественное пересечение разделяет несколько свойств с логическим соединением, например ассоциативность, коммутативность и идемпотентность.

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

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

Английский "and" имеет свойства, не захваченные логическим соединением. Например, «и» иногда подразумевает порядок, имеющий смысл «тогда». Например, «они поженились и родили ребенка» в просторечии означает, что брак был заключен раньше ребенка.

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

См. Также

Ссылки

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

На Викискладе есть материалы, относящиеся к Логическое соединение.

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