Conjunção lógica - Logical conjunction

Conjunção lógica

E
Definição	${\ displaystyle xy}$
Mesa da verdade	${\ displaystyle (0001)}$
Portão lógico
Formas normais
Disjuntivo	${\ displaystyle xy}$
Conjuntivo	${\ displaystyle xy}$
Polinômio de Zhegalkin	${\ displaystyle xy}$
Treliça do Post
0-preservação	sim
1-preservando	sim
Monótono	não
Afim	não
v t e

Em lógica , matemática e linguística , And ( ) é o operador funcional de verdade da conjunção lógica ; o e de um conjunto de operandos é verdadeiro se e somente se todos os seus operandos forem verdadeiros. O conectivo lógico que representa esse operador é geralmente escrito como ou ⋅ . ${\ displaystyle \ wedge}$${\ displaystyle \ wedge}$

${\ displaystyle A \ land B}$é verdadeiro se e somente se for verdadeiro e verdadeiro. ${\ displaystyle A}$${\ displaystyle B}$

Um operando de uma conjunção é um conjunto .

Além da lógica, o termo "conjunção" também se refere a conceitos semelhantes em outros campos:

• Em linguagem natural , a denotação de expressões como Inglês "e".
• Nas linguagens de programação , o curto-circuito e a estrutura de controle .
• Na teoria dos conjuntos , interseção .
• Na teoria da rede , conjunção lógica ( maior limite inferior ).
• Na lógica de predicados , quantificação universal .

Notação

E geralmente é denotado por um operador infixo: em matemática e lógica, é denotado por , & ou × ; em eletrônica, ⋅ ; e em linguagens de programação, , , ou . Em Jan Lukasiewicz 's prefixo notação para a lógica , o operador é K , para Polish koniunkcja . ${\ displaystyle \ wedge}$&&&and

Definição

A conjunção lógica é uma operação em dois valores lógicos , normalmente os valores de duas proposições , que produz um valor verdadeiro se e somente se ambos os operandos forem verdadeiros.

A identidade conjuntiva é verdadeira, o que quer dizer que AND-ing uma expressão com true nunca mudará o valor da expressão. De acordo com o conceito de verdade vazia , quando a conjunção é definida como um operador ou função de aridade arbitrária , a conjunção vazia (AND-ing sobre um conjunto vazio de operandos) é freqüentemente definida como tendo o resultado verdadeiro.

Mesa da verdade

A tabela de verdade de : ${\ displaystyle A \ land B}$

${\ displaystyle A}$	${\ displaystyle B}$	${\ displaystyle A \ wedge B}$
T	T	T
T	F	F
F	T	F
F	F	F

Definido por outros operadores

Em sistemas onde a conjunção lógica não é primitiva, pode ser definida como

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

ou

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

Regras de introdução e eliminação

Como regra de inferência, a introdução da conjunção é uma forma de argumento simples e classicamente válida . A forma argumento tem duas premissas, A e B . Intuitivamente, permite a inferência de sua conjunção.

A ,

B .

Portanto, um e B .

ou em notação de operador lógico :

${\ displaystyle A,}$

${\ displaystyle B}$

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

Aqui está um exemplo de um argumento que se encaixa na introdução do formulário de conjunção :

Bob gosta de maçãs.

Bob gosta de laranjas.

Portanto, Bob gosta de maçãs e Bob gosta de laranjas.

A eliminação da conjunção é outra forma de argumento simples e classicamente válida . Intuitivamente, ele permite a inferência de qualquer conjunção de qualquer um dos elementos dessa conjunção.

A e B .

Por conseguinte, um .

...ou alternativamente,

A e B .

Portanto, B .

Em notação de operador lógico :

${\ displaystyle A \ land B}$

${\ displaystyle \ vdash A}$

...ou alternativamente,

${\ displaystyle A \ land B}$

${\ displaystyle \ vdash B}$

Negação

Definição

Uma conjunção é provada falsa estabelecendo ou . Em termos de linguagem de objeto, isso lê ${\ displaystyle A \ land B}$${\ displaystyle \ neg A}$${\ displaystyle \ neg B}$

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

Esta fórmula pode ser vista como um caso especial de

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

quando é uma proposição falsa. ${\ displaystyle C}$

Outras estratégias de prova

Se implica , então , além de provar que a conjunção é falsa: ${\ displaystyle A}$${\ displaystyle \ neg B}$${\ displaystyle \ neg A}$${\ displaystyle A}$

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

Em outras palavras, uma conjunção pode realmente ser provada falsa apenas por saber sobre a relação de suas conjunções, e não necessariamente sobre seus valores de verdade.

Esta fórmula pode ser vista como um caso especial de

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

quando é uma proposição falsa. ${\ displaystyle C}$

Qualquer uma das opções acima são provas construtivamente válidas por contradição.

Propriedades

comutatividade : sim

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

associatividade : sim

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

distributividade : com várias operações, especialmente com ou

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

outros

com exclusividade ou : ${\ displaystyle ~ A}$ ${\ displaystyle \ land}$ ${\ displaystyle (B \ oplus C)}$     ${\ displaystyle \ Leftrightarrow}$     ${\ displaystyle (A \ land B)}$ ${\ displaystyle \ oplus}$ ${\ displaystyle (A \ land C)}$ ${\ displaystyle \ land}$     ${\ displaystyle \ Leftrightarrow}$         ${\ displaystyle \ Leftrightarrow}$     ${\ displaystyle \ oplus}$ com não implicação material : ${\ displaystyle ~ A}$ ${\ displaystyle \ land}$ ${\ displaystyle (B \ nrightarrow C)}$     ${\ displaystyle \ Leftrightarrow}$     ${\ displaystyle (A \ land B)}$ ${\ displaystyle \ nrightarrow}$ ${\ displaystyle (A \ land C)}$ ${\ displaystyle \ land}$     ${\ displaystyle \ Leftrightarrow}$         ${\ displaystyle \ Leftrightarrow}$     ${\ displaystyle \ nrightarrow}$ consigo mesmo: ${\ displaystyle ~ A}$ ${\ displaystyle \ land}$ ${\ displaystyle (B \ land C)}$     ${\ displaystyle \ Leftrightarrow}$     ${\ displaystyle (A \ land B)}$ ${\ displaystyle \ land}$ ${\ displaystyle (A \ land C)}$ ${\ displaystyle \ land}$     ${\ displaystyle \ Leftrightarrow}$         ${\ displaystyle \ Leftrightarrow}$     ${\ displaystyle \ land}$

idempotência : sim

${\ displaystyle ~ A ~}$	${\ displaystyle ~ \ land ~}$	${\ displaystyle ~ A ~}$	${\ displaystyle \ Leftrightarrow}$	${\ displaystyle A ~}$
	${\ displaystyle ~ \ land ~}$		${\ displaystyle \ Leftrightarrow}$

monotonicidade : sim

${\ displaystyle A \ rightarrow B}$	${\ displaystyle \ Rightarrow}$			${\ displaystyle (A \ land C)}$	${\ displaystyle \ rightarrow}$	${\ displaystyle (B \ land C)}$
	${\ displaystyle \ Rightarrow}$		${\ displaystyle \ Leftrightarrow}$		${\ displaystyle \ rightarrow}$

preservação da verdade: sim
Quando todas as entradas são verdadeiras, a saída é verdadeira.

${\ displaystyle A \ land B}$	${\ displaystyle \ Rightarrow}$	${\ displaystyle A \ land B}$
	${\ displaystyle \ Rightarrow}$
		(para ser testado)

preservação de falsidade: sim
Quando todas as entradas são falsas, a saída é falsa.

${\ displaystyle A \ land B}$	${\ displaystyle \ Rightarrow}$	${\ displaystyle A \ lor B}$
	${\ displaystyle \ Rightarrow}$
(para ser testado)

Espectro de Walsh : (1, -1, -1,1)

Não linearidade : 1 (a função é dobrada )

Se estiver usando valores binários para verdadeiro (1) e falso (0), a conjunção lógica funcionará exatamente como a multiplicação aritmética normal .

Aplicações em engenharia da computação

Na programação de computador de alto nível e na eletrônica digital , a conjunção lógica é comumente representada por um operador infixo, geralmente como uma palavra-chave como " AND", uma multiplicação algébrica ou o símbolo do e comercial &(às vezes duplicado como em &&). Muitas linguagens também fornecem estruturas de controle de curto-circuito correspondentes à conjunção lógica.

A conjunção lógica é frequentemente usada para operações bit a bit, onde 0corresponde a falso e 1verdadeiro:

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

A operação também pode ser aplicada a duas palavras binárias vistas como bitstrings de igual comprimento, tomando o AND bit a bit de cada par de bits nas posições correspondentes. Por exemplo:

• 11000110 AND 10100011  =  10000010.

Isso pode ser usado para selecionar parte de uma bitstring usando uma máscara de bits . Por exemplo,  =  extrai o quinto bit de uma bitstring de 8 bits. 10011101 AND 0000100000001000

Na rede de computadores , as máscaras de bits são usadas para derivar o endereço de rede de uma sub - rede dentro de uma rede existente de um determinado endereço IP , colocando o endereço IP e a máscara de sub-rede em AND .

A conjunção lógica " AND" também é usada em operações SQL para formar consultas de banco de dados .

A correspondência Curry-Howard relaciona a conjunção lógica aos tipos de produtos .

Correspondência teórica de conjuntos

A pertinência de um elemento de um conjunto de interseção na teoria dos conjuntos é definida em termos de uma conjunção lógica: x ∈ A ∩ B se e somente se ( x ∈ A ) ∧ ( x ∈ B ). Por meio dessa correspondência, a intersecção teórica dos conjuntos compartilha várias propriedades com a conjunção lógica, como associatividade , comutatividade e idempotência .

Linguagem natural

Tal como acontece com outras noções formalizadas na lógica matemática, a conjunção lógica e está relacionada com, mas não o mesmo que, a conjunção gramatical e nas línguas naturais.

O "e" inglês tem propriedades não capturadas pela conjunção lógica. Por exemplo, "e" às ​​vezes implica que a ordem tenha o sentido de "então". Por exemplo, "Eles se casaram e tiveram um filho" no discurso comum significa que o casamento veio antes do filho.

A palavra "e" também pode significar a divisão de uma coisa em partes, como "A bandeira americana é vermelha, branca e azul." Aqui, não significa que a bandeira seja ao mesmo tempo vermelha, branca e azul, mas sim que tem uma parte de cada cor.

Veja também

Referências

links externos

• "Conjunção" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Wolfram MathWorld: Conjunção
• "Tabela de propriedades e verdade das proposições AND" . Arquivado do original em 6 de maio de 2017.