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

Логическое соединение
И
Определение
Таблица истинности
Логический вентиль
Нормальные формы
Дизъюнктивный
соединительный
Полином Жегалкина
Решетки постовые
0-сохраняющий	да
1-сохраняющий	да
монотонный	нет
Аффинный	нет
Самодвойственный	нет
	v ; т ; и ;

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

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

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

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

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

Обозначения

И обычно обозначается инфиксным оператором: в математике и логике он обозначается $\wedge$ (Юникод U+2227 ∧ ЛОГИЧЕСКОЕ И ), ^[1] $\&$ или $\times$ ; в электронике, $\cdot$ ; и в языках программирования, &, &&, или and. В Яна Лукасевича префиксной записи логики оператор $K$ , для польского союза . ^[4]

Определение

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

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

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

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

$A$	$B$	$A\land B$
Ф	Ф	Ф
Ф	Т	Ф
Т	Ф	Ф
Т	Т	Т

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

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

A\land B=\neg (A\to \neg B)

или

A\land B=\neg (\neg A\lor \neg B).

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

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

A

,

B

.

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

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

A,

B

\vdash A\land B

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

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

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

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

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

A

и

B

.

Поэтому,

A

.

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

A

и

B

.

Поэтому,

B

.

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

A\land B

\vdash A

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

A\land B

\vdash B

Отрицание

Определение

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

\neg A\to \neg (A\land B)

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

(A\to C)\to ((A\land B)\to C)

когда $C$ это ложное предложение.

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

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

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

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

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

(A\to (B\to C))\to ((A\land B)\to C)

когда $C$ это ложное предложение.

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

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

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

$A\land B$	$\Leftrightarrow$	$B\land A$
	$\Leftrightarrow$

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

$~A$	$~~~\land ~~~$	$(B\land C)$	$\Leftrightarrow$			$(A\land B)$	$~~~\land ~~~$	$~C$
	$~~~\land ~~~$		$\Leftrightarrow$		$\Leftrightarrow$		$~~~\land ~~~$

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

$~A$	$\land$	$(B\lor C)$	$\Leftrightarrow$			$(A\land B)$	$\lor$	$(A\land C)$
	$\land$		$\Leftrightarrow$		$\Leftrightarrow$		$\lor$

другие

with exclusive or:

$~A$	$\land$	$(B\oplus C)$	$\Leftrightarrow$			$(A\land B)$	$\oplus$	$(A\land C)$
	$\land$		$\Leftrightarrow$		$\Leftrightarrow$		$\oplus$

with material nonimplication:

$~A$	$\land$	$(B\nrightarrow C)$	$\Leftrightarrow$			$(A\land B)$	$\nrightarrow$	$(A\land C)$
	$\land$		$\Leftrightarrow$		$\Leftrightarrow$		$\nrightarrow$

with itself:

$~A$	$\land$	$(B\land C)$	$\Leftrightarrow$			$(A\land B)$	$\land$	$(A\land C)$
	$\land$		$\Leftrightarrow$		$\Leftrightarrow$		$\land$

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

$~A~$	$~\land ~$	$~A~$	$\Leftrightarrow$	$A~$
	$~\land ~$		$\Leftrightarrow$

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

$A\rightarrow B$	$\Rightarrow$			$(A\land C)$	$\rightarrow$	$(B\land C)$
	$\Rightarrow$		$\Leftrightarrow$		$\rightarrow$

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

$A\land B$	$\Rightarrow$	$A\land B$
	$\Rightarrow$
		(будет протестирован)

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

$A\land B$	$\Rightarrow$	$A\lor B$
	$\Rightarrow$
(будет протестирован)

Спектр Уолша : (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.

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с ^д «2.2: Союзы и дизъюнкции» . Математика LibreTexts . 13 августа 2019 г. Проверено 02 сентября 2020 г.
^ Перейти обратно: ^а ^б ^с «Соединение, отрицание и дизъюнкция» . Философия.lander.edu . Проверено 02 сентября 2020 г.
^ Билл, Джеффри С. (2010). Логика: основы . Основы (1. изд.). Лондон: Рутледж. п. 17. ISBN 978-0-203-85155-5 .
^ Юзеф Мария Боченский (1959), Краткое изложение математической логики , перевод Отто Берда из французского и немецкого изданий, Дордрехт, Южная Голландия: Д. Рейдель, passim.
^ Смит, Питер. «Типы системы доказательств» (PDF) . п. 4.
^ Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Рутледж. п. 38. ISBN 978-0-415-13342-5 .

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

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

[:2-1] Перейти обратно: ^а ^б ^с ^д «2.2: Союзы и дизъюнкции» . Математика LibreTexts . 13 августа 2019 г. Проверено 02 сентября 2020 г.

[:1-2] Перейти обратно: ^а ^б ^с «Соединение, отрицание и дизъюнкция» . Философия.lander.edu . Проверено 02 сентября 2020 г.

[:21-3] Билл, Джеффри С. (2010). Логика: основы . Основы (1. изд.). Лондон: Рутледж. п. 17. ISBN 978-0-203-85155-5 .

[4] Юзеф Мария Боченский (1959), Краткое изложение математической логики , перевод Отто Берда из французского и немецкого изданий, Дордрехт, Южная Голландия: Д. Рейдель, passim.

[5] Смит, Питер. «Типы системы доказательств» (PDF) . п. 4.

[:13-6] Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Рутледж. п. 38. ISBN 978-0-415-13342-5 .

[1]

[2]

[3]

[4]

[5]

[6]

v т и Общие логические связи
Тавтология / Правда $\top$
Альтернативное отрицание ( ворота NAND ) $\uparrow$ Обратная импликация $\leftarrow$ Импликация ( ворота IMPLY ) $\rightarrow$ Дизъюнкция ( ворота ИЛИ ) $\lor$
Отрицание ( НЕ ворота ) $\neg$ Эксклюзивное или ( ворота XOR ) $\not \leftrightarrow$ Двуусловный ( ворота XNOR ) $\leftrightarrow$ Оператор ( цифровой буфер )
Совместное отрицание ( ворота NOR ) $\downarrow$ Неимпликация ( ворота NIMPLY ) $\nrightarrow$ Обратная неимпликация $\nleftarrow$ Соединение ( ворота И ) $\land$
Противоречие / Ложь $\bot$
Философский портал