Conectivo lógico

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Para a lógica, um conectivo lógico (também chamado de operador lógico) é um símbolo ou palavra usado para conectar duas ou mais sentenças (tanto na linguagem formal quanto na linguagem natural) de uma maneira gramaticalmente válida, de modo que o sentido da sentença composta produzida dependa apenas das senteças originais.

Os conectivos lógicos mais comuns são os conectivos binários (também chamados de conectivos diádicos), que juntam duas sentenças, que podem ser consideradas os operandos da função. É também comum considerar negação como um conectivo unário.

Conectivos lógicos e quantificadores são os dois principais tipos de constantes lógicas usadas em sistemas formais como a lógica proposicional e a lógica de predicados.

Linguagens[editar | editar código-fonte]

Linguagem natural[editar | editar código-fonte]

Na gramática das linguagens naturais, duas sentenças podem ser unidas por uma conjunção gramatical para formar uma sentença gramaticalmente composta. Algumas dessas conjunções gramaticais, mas não todas, são funções de verdade. Por exemplo, considere as seguintes sentenças:

A: João subiu a montanha.
B: Pedro subiu a montanha.
C: João subiu a montanha e Pedro subiu a montanha.
D: João subiu a montanha, então Pedro subiu a montanha.

As palavras e e então são conjunções gramaticais unindo as sentenças (A) e (B) para formar as sentenças compostas (C) e (D). O e em (C) é um conectivo lógico, pois o valor verdade de (C) é completamente determinado por (A) e (B): não faria sentido afirmar (A) e (B) e negar (C). No entanto, então em (D) não é um conectivo lógico, pois seria bastante razoável afirmar (A) e (B) e negar (D): talvez Pedro subiu a montanha para buscar um balde d'água, e não porque João subiu a montanha.

Várias palavras e pares de palavras expressam conectivos lógicos, e algumas delas são sinônimos. Exemplos (com o nome da relação em parênteses):

  • "e" (conjunção)
  • "ou" (disjunção)
  • "ou...ou" (disjunção exclusiva)
  • "implica" (implicação)
  • "se...então" (implicação)
  • "se e somente se" (equivalência)
  • "somente se" (implicação)
  • "apenas no caso" (equivalência)
  • "mas" (conjunção)
  • "contudo" (conjunção)
  • "não ambos" (NAND)
  • "nem...nem" (NOR)

A palavra "não" (negação) e as frases "é falso que" (negação) e "não é o caso que" (negação) também expressam um conectivo lógico - mesmo que elas sejam aplicadas a uma única sentença, e não conectem duas sentenças.

Linguagens formais[editar | editar código-fonte]

Em linguagens formais, funções verdade são representadas por símbolos inequívocos. Esses símbolos são chamados "conectivos lógicos", "operadores lógicos", "operadores proposicionais", ou, na lógica clássica, "conectivos de funções de verdade". Veja fórmulas bem formadas para saber as regras que permitem que novas fórmulas bem formadas sejam construídas ao juntar outras fórmulas bem formadas usando conectivos de funções de verdade.

Conectivos lógicos podem ser usados para ligar mais de duas afirmações, então é comum falar sobre "conectivo lógico n-ário".

Conectivos lógicos comuns[editar | editar código-fonte]

Nome / Símbolo Valor verdade Venn
diagrama
P = 0 1
Verdade/Tautologia   1 1 Venn11.svg
Proposição P   0 1 Venn01.svg
Falso/Contradição   0 0 Venn00.svg
Negação ¬   1 0 Venn10.svg
Conectivos binários Q = 0 1 0 1
Conjunção 0 0 0 1 Venn0001.svg
Alternative denial 1 1 1 0 Venn1110.svg
Disjunção 0 1 1 1 Venn0111.svg
Joint denial 1 0 0 0 Venn1000.svg
Condicional material 1 1 0 1 Venn1011.svg
Ou exclusivo \not\leftrightarrow 0 1 1 0 Venn0110.svg
Bicondicional 1 0 0 1 Venn1001.svg
Converse implication 1 0 1 1 Venn1101.svg
Proposition P 0 0 1 1 Venn0101.svg
Proposition Q 0 1 0 1 Venn0011.svg
Mais informações

Lista de conectivos lógicos comuns[editar | editar código-fonte]

Conectivos lógicos comumente usados: Negação (não): ¬, ~ Conjunção (e): ∧, & , ∙ Disjunção (ou): ∨ Implicação material (se...então): → ,⇒,⊃ Bicondicional (se e somente se): ↔,≡ ,=

Nomes alternativos para bicondicional são "sse", "xnor" e "bi-implicação".

Por exemplo, o significado das afirmações está chovendo e eu estou dentro de casa é transformado quando as duas são combinadas com conectivos lógicos:

Está chovendo e eu estou dentro de casa (P ∧ Q) Se está chovendo, então eu estou dentro de casa. (P → Q) Se eu estou dentro de casa, então está chovendo. (Q → P) Eu estou dentro de casa se e somente se está chovendo (Q ↔ P) Não está chovendo (¬P) Para afirmação P = Está chovendo e Q = Eu estou dentro de casa.

É também comum considerar a fórmula sempre verdadeira e a fórmula sempre falsa como sendo conectivos: Verdadeiro (⊤, 1 or T) Falso (⊥, 0, or F)

História das notações[editar | editar código-fonte]

  • Negação: o símbolo ¬ apareceu em Heyting em 1929.[1] [2] (compare ao símbolo Begriffsschrift connective1.svg de Frege em Begriffsschrift); o símbolo ~ apareceu em Russell em 1908;[3] uma notação alternativa é adicionar uma linha horizontal em cima da fórmula, como em \overline{P}; outra notação alternativa é usar uma aspa simples como em P'.
  • Conjunção: o símbolo ∧ apareceu em Heyting em 1929 [1] (compare ao uso de Peano da notação de interseção ∩ em teoria dos conjuntos[4] ); & apareceu pelo menos em Schönfinkel em 1924[5] ; veio da interpretação de Boole da lógica como uma álgebra elementar.
  • Disjunção: o símbolo ∨ apareceu em Russell em 1908 (compare ao uso de Peano da notação de união ∪ em teoria dos conjuntos); o símbolo + também é usado, apesar da ambiguidade decorrente de na álgebra elementar ordinária o + ser considerado um ou exclusivo quando interpretado logicamente em uma aliança de dois elementos; pontualmente na história um + junto com um ponto no canto inferior à direita foi usado por Peirce.
  • Implicação: o símbolo → pode ser visto em Hilbert em 1917; ⊃ foi usado por Russell em 1908 (compare à notação de C invertido de Peano); ⇒ foi usado em Vax.
  • Bicondicional: o símbolo ≡ foi usado ao menos por Russell em 1908; ↔ foi usado ao menos por Tarski em 1940; ⇔ foi usado em Vax; outros símbolos apareceram pontualmente na história como ⊃⊂ em Gentzen, ~ em Schönfinkel ou ⊂⊃ em Chazal.
  • Verdadeiro: o símbolo 1 veio da interpretação de Boole da lógica como uma álgebra elementar como a álbegra booleana de dois elementos; outras notações inclusive \bigwedge foram encontradas em Peano.
  • Falso: o símbolo 0 vem também da interpretação de Boole da lógica como um anel [?]; outras notações inclusive \bigvee foram encontradas em Peano.

Alguns autores usaram letras para conectivos em algum momento da história: u. para conjunção (do Alemão "und", significa "e") e o. para disjunção (do Alemão "oder", significa "ou") nos primeiros trabalhos de Hilbert (1904); N para negação, K para conjunção, A para disjunção, C para implicação, E para bicondicional em Łukasiewicz (1929).

Redundância[editar | editar código-fonte]

O conectivo lógico da implicação recíproca ← é na verdade o mesmo que o condicional material com as premissas trocadas, logo o símbolo da implicação recíproca é redundante. Em alguns cálculos lógicos (notavelmente, na lógica clássica, certas afirmações compostas essencialmente diferentes são logicamente equivalentes. Um exemplo menos trivial de uma redundância é a clássica equivalência entre ¬P ∨ Q e P → Q. Portanto, um sistema lógico de base clássica não precisa do operador condicional "→" se "¬" (não) e "∨" (ou) já são usados, ou pode usar o "→" somente como um açúcar sintático para uma composição que tenha uma negação e uma disjunção.

Existem 16 funções Booleanas associando os valores verdade de entrada P e Q com saídas binárias de 4 dígitos. Estas correspondem às escolhas possíveis de conectivos lógicos binários para a lógica clássica. Uma implementação diferente da lógica clássica pode escolher diferentes subconjuntos funcionalmente completos de conectivos.

Uma abordagem é escolher um conjunto mínimo, e definir outros conectivos por alguma forma lógica, como no exemplo com condicional material acima. A seguir estão os conjuntos mínimos funcionalmente completos de operadores na lógica clássica, cujas aridades não excedem 2:

Um elemento
{↑}, {↓}.
Dois elementos
{\vee, ¬}, {\wedge, ¬}, {→, ¬}, {←, ¬}, {→, \bot}, {←, \bot}, {→, \not\leftrightarrow}, {←, \not\leftrightarrow}, {→, \not\to}, {→, \not\leftarrow}, {←, \not\to}, {←, \not\leftarrow}, {\not\to, ¬}, {\not\leftarrow, ¬}, {\not\to\top}, {\not\leftarrow\top}, {\not\to\leftrightarrow}, {\not\leftarrow\leftrightarrow}.
Três elementos
{\lor, \leftrightarrow, \bot}, {\lor, \leftrightarrow, \not\leftrightarrow}, {\lor, \not\leftrightarrow, \top}, {\land, \leftrightarrow, \bot}, {\land, \leftrightarrow, \not\leftrightarrow}, {\land, \not\leftrightarrow, \top}.

Veja mais detalhes sobre completude funcional.

Outra abordagem é usar conectivos em igualdade de direitos, de um certo conjunto conveniente e funcionalmente completo, mas não mínimo. Essa abordagem requer mais axiomas proposicionais e cada equivalência entre formas lógicas tem que ser ou um axioma ou provada como um teorema.

Mas a lógica intuicionista tem a situação mais complicada. De seus cinco conectivos {∧, ∨, →, ¬, ⊥} somente a negação ¬ tem como ser reduzida a outros conectivos (¬p ≡ (p → ⊥)). Nem conjunção, disjunção, e condicional material tem uma forma equivalente construída dos outros quatro conectivos lógicos.

Propriedades[editar | editar código-fonte]

Alguns conectivos lógicos possuem propriedades que podem ser expressas nos teoremas contendo o conectivo. Algumas dessas propriedades que um conectivo lógico pode ter são:

  • Associatividade: Em uma expressão contendo dois ou mais do mesmo conectivo associativo em uma linha, a ordem das operações não importa enquanto a sequência de operandos não mudar.
  • Comutatividade: Os operandos do conectivo podem ser trocados (um pelo outro) preservando a equivalência lógica da expressão original.
  • Distributividade: Um conectivo denotado por • distribui sobre outro conectivo denotado por +, se a • (b + c) = (ab) + (ac) para todos os operandos a, b, c.
  • Idempotência: Sempre que os operandos de uma operação são iguais, o composto é logicamente equivalente ao operando.
  • Absorção: Um par de conectivos \land, \lor satisfaz a lei da absorção se a\land(a\lor b)=a para todos os operandos a, b.
  • Monotonicidade: Se f(a1, ..., an) ≤ f(b1, ..., bn) para todo a1, ..., an, b1, ..., bn ∈ {0,1} tal que a1b1, a2b2, ..., anbn. Ex., \vee, \wedge, \top, \bot.
  • Afinidade: Cada variável sempre faz uma diferença no valor verdade da operação ou então nunca faz uma diferença. Ex., \neg, \leftrightarrow, \not\leftrightarrow, \top, \bot.


Referências

  1. a b Heyting (1929) Die formalen Regeln der intuitionistischen Logik.
  2. Denis Roegel (2002), Petit panorama des notations logiques du 20e siècle (see chart on page 2).
  3. Russell (1908) Mathematical logic as based on the theory of types (American Journal of Mathematics 30, p222–262, also in From Frege to Gödel edited by van Heijenoort).
  4. Peano (1889) Arithmetices principia, nova methodo exposita.
  5. Schönfinkel (1924) Über die Bausteine der mathematischen Logik, translated as On the building blocks of mathematical logic in From Frege to Gödel edited by van Heijenoort.