Lógica matemática

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

Lógica Matemática é uma sub-área da matemática que explora as aplicações da lógica formal para a matemática. Basicamente, lógica matemática tem ligações fortes com metamatemática, os fundamentos da matemática e ciência da computação teórica.[1] Os temas unificadores na lógica matemática incluem o estudo do poder expressivo de sistemas formais e o poder dedutivo de sistemas de prova matemática formal.

A lógica matemática é muitas vezes dividida em campos da teoria dos conjuntos, teoria de modelos, teoria da recursão e teoria da prova. Estas áreas compartilham resultados básicos sobre lógica, particularmente lógica de primeira ordem, e definibilidade. Na ciência da computação, especialmente na classificação ACM, onde ACM vem do inglês Association for Computing Machinery, lógica matemática engloba tópicos adicionais não descritos neste artigo; ver lógica em ciência da computação para este tópico anterior.

Desde o seu surgimento, a lógica matemática tem contribuído e motivado pelo estudo dos fundamentos da matemática. Este estudo foi iniciado no final do século 19, com o desenvolvimento de arcabouço axiomático para geometria, aritmética e análise. No início do século XX a lógica matemática foi moldada pelo programa de David Hilbert para provar a consistência das teorias fundamentais. Os resultados de Kurt Gödel, Gerhard Gentzen, e outros, desde resolução parcial do programa, e esclareceu as questões envolvidas em provar a consistência. O trabalho na teoria dos conjuntos mostrou que quase toda a matemática ordinária pode ser formalizada em termos de conjuntos, embora existam alguns teoremas que não podem ser demonstrados em sistemas axiomáticos comuns para a teoria dos conjuntos. O trabalho contemporâneo nos fundamentos da matemática, muitas vezes se concentra em estabelecer quais as partes da matemática que podem ser formalizadas, em particular, sistemas formais (como em matemática reversa) ao invés de tentar encontrar as teorias em que toda a matemática pode ser desenvolvida.


Sub-áreas e escopo O manual de lógica matemática divide a matemática contemporânea em quarto áreas:

  1. teoria dos conjuntos
  2. teoria dos modelos
  3. teoria da recursão
  4. teoria da prova e da matemática construtiva consideradas partes de uma única area.

Cada area tem um foco distinto, apesar de ter várias tecnicas e resultados comuns entre si. A divisão das referidas áreas e os limites que separam a lógica matemática de outros campos de estudo não são bem definidas. A teoria da incompletude de Gödel representa não só um marco na teoria da recursão e teoria da prova, mas também contribuiu para o teorema de Löb da teoria dos modelos. O método do forçamento ("forcing") é aplicada na teoria dos conjuntos, na teoria dos modelos, na teoria da recursão, assim como no estudos da matemática intuiticionística.

O campo matemático conhecido como o da teoria das categorias usa muitos métodos axiomáticos formais nos quais se inclui o estudo da lógica categór, mas essa teoria não é comumente considerada um sub-ramo da lógica. Por causa da sua aplicabilidade em diversos campos da lógica, matemáticos como Saunders Mac Lane propuseram usar a teoria das categorias como fundamentos da matemática, independentemente da teoria dos conjuntos. Essas fundamentações usam topicos que em muito se parecem com modelos generalizados das teorias dos conjuntos, e empregam lógica clássica ou não-clássica.

História[editar | editar código-fonte]

A logica matematica surgiu em meados do século XIX como um sub-ramo da Matemática e independente do estudo tradicional da (Ferreirós 2001, p. 443)(Ferreirós 2001, p. 443). Antes do seu surgimento independente, a lógica foi estudada com a retórica, através do silogismo e a filosofia. Na primeira metade do seculo XX houve uma explosão de resultados fundamentais, acompanhados por debates vigorosos sobre as bases da matematica.

Os estudos sobre o raciocínio foram inicialmente desenvolvidos por filósofos como Parménides e Platão, mas foi Aristóteles quem o elaborou mais detalhadamente e definiu a lógica como se estuda hoje em dia (como se estudava até o século XIX).

Para mostrar que os sofistas (mestres da retórica e da oratória) podiam enganar os cidadãos utilizando argumentos incorretos, Aristóteles estudou a estrutura lógica da argumentação. Revelando, assim, que alguns argumentos podem ser convincentes, embora não sejam corretos. A lógica, segundo Aristóteles, é um instrumento para atingir o conhecimento científico, baseando-se no silogismo.

Seguidores de Aristóteles reuniram seus princípios sobre lógica em um livro intitulado “Organon”, que significa “Instrumento da Ciência”.

História moderna[editar | editar código-fonte]

Teorias logicas foram desenvolvidas em diversas culturas na historia, China, Índia, Grécia e no mundo Islâmico. Na Europa do século XVIII, filósofos matemáticos, como Leibniz e Lambert tentaram representar as operações da lógica formal através de símbolos, de forma algébrica mas seus esforços e trabalhos permaneceram isolados e pouco reconhecidos.

Século XIX[editar | editar código-fonte]

Em meados do século XIX, George Boole e posteriormente Augustus De Morgan apresentaram tratamentos matemáticos sistemáticos. Seus trabalhos, alicerçados em trabalhos de algebristas como George Peacock, tranformaram a doutrina tradicional de aristoteles de forma que se encaixasse no estudo dos foundations of mathematics (Katz 1998, p. 686). Charles Sanders Peirce construiu sobre os estudos de Boole almejando desenvolver uma sistema de relações lógica e quantificadores o qual ele publicou diversas veses entre 1870 e 1885. Gottlob Frege apresentou um desenvolvimento independente da lógica com quantificadores no seu Begriffsschrift, publicado em 1879, um trabalho por muitos considerado como uma reviravolta na histórica da lógica. O trabalho de Frege's permaneceu incerto,pelo menos até Bertrand Russell começar a promovê-lo no iníco da virada do século. As notações bidimensionais desenvolvidas por Frege nunca foram vastamente adotadas e caiu em desuso nos artigos e textos contemporâneos.

De 1890 a 1905, Ernst Schröder publicou o Vorlesungen über die Algebra der Logik em três volumes. Esse trabalho compactava e desenvolvia os trabalhos de Boole, De morgan, e Peirce e se tornou uma grande referencia para logica simbolica, como era conhecida no fim do século XIX.

Fundamentos teoricos[editar | editar código-fonte]

Preocupações com a possivel ausencia de fundamentos matematicos acaretaram o desenvolvimento de sistemas axiomaticos para areas da matematica fundamental como a aritimetica, análise e geometria.

Em lógica o termo aritmético se refere à teoria dos números naturais. Giuseppe Peano (1889) publicou uma série de axiomas para serem usados pela aritmética que hoje carregam seu nome (Axiomas de Peano), usando variações do sistema logico de Boole e Schröder, porém adicionando quantificadores. Peano náo tinha conhecimento do trabalho de Frege. Contemporaneamente Richard Dedekind mostrou que os números naturais são unicamente caracterizados por suas propriedades da indução. Dedekind (1888) propôs a diferente caracterização na qual não existia a essência da logica formal dos axiomas de Peano. Todavia, o trabalho de Dedekind's provou teoremas inacessíveis ao sistema desenvolvido por Peano, como por exemplo a a inclusão da individualidade dos conjuntos de numeros naturais (até o isomorfismo) e as definições recursivas de adição e multiplicação da função sucessor e indução matemática.

No meio do século XIX, foram descobertas falhas nos aximas de Euclides para geometria (Katz 1998, p. 774). Além da independência do postulado paralelo, estabelecido por Nikolai Lobachevsky em 1826 (Lobachevsky 1840), matemáticos descobriram que certos teoremas tomadas como certo por Euclides não eram de fato demonstrável a partir de seus axiomas. Entre eles está o teorema que diz que uma linha contem pelo menos dois pontos, ou que círculos de mesmo raio cujo centro é separado pelo raio devem intersectar. Hilbert (1899) desenvolveu um conjunto completo dos axiomas para geometria, construindo nos [axiomas de Pasch] pelo Pasch (1882). O sucesso axiomatização da geometria motivou Hilbert a encontrar axiomatições completas de outras áreas da matemática, assim como os números naturais e da linha real. Isto proveria a maior área de pesquisa na primeira métade do século XX.

O século 19 viu grandes avanços na teoria da análise real, incluindo as teorias de convergência de funções e série de Fourier. Matemáticos como Karl Weierstrass começaram a construir funções que se estendiam a intuição, como funções contínuas nada-diferenciáveis​​. Concepções anteriores de uma função como uma regra para o cálculo, ou um gráfico bom, já não eram adequados. Weierstrass começou a defender o aritmetização da análise, que procurou axiomatizar análise usando propriedades dos números naturais. O moderno (ε, δ) definição de limite e função contínua s já foi desenvolvido por Bolzano em 1817 ( Felscher 2000), mas permaneceu relativamente desconhecido. Cauchy em 1821 continuidade definida em termos de infinitesimals (ver Cours d'Analyse, página 34). Em 1858, Dedekind propôs uma definição dos números reais em termos de Dedekind cortes dos números racionais (Dedekind 1872), uma definição ainda empregada em textos contemporâneos.

Georg Cantor desenvolveu os conceitos fundamentais da teoria dos conjuntos infinitos. Seus primeiros resultados desenvolveu a teoria da cardinalidade e provou que os reais e os números naturais têm diferentes cardinalidades (Cantor 1874). Ao longo dos próximos 20 anos, Cantor desenvolveu uma teoria de número transfinita s em uma série de publicações. Em 1891, ele publicou uma nova prova do uncountability dos números reais, que introduziu o argumento diagonal, e utilizado este método para provar teorema de Cantor que nenhum conjunto pode ter a mesma cardinalidade como sua powerset. Cantor acredita que todo conjunto pode ser bem ordenado, mas foi incapaz de produzir uma prova para esse resultado, deixando-o como um problema em aberto em 1895 ( Katz 1998, p 807.).

Século XX[editar | editar código-fonte]

No inicio do seculo XX a maiores áreas de estudo eram a teoria dos conjuntos e a logica formal. A descoberta de paradoxos em teorias do conjunto informal incitou alguns pensadores a se perguntar se a matematica em si era inconsistente, incitou também a procura por provas de consistência.

Em 1900, Hilbert apresentava uma famosa lista de [problemas [de Hilbert | 23 problemas]] para o próximo século. Os dois primeiros eram para resolver a Hipótese do continuum e provar a consistência da aritmética elementar, respectivamente, o décimo era produzir um método que poderia decidir se uma equação polinomial multivariada sobre os inteiros tem um solução. Os trabalhos posteriores moldaram a direção da lógica matemática, assim como o esforço para resolver Entscheidungs problem de Hilbert, exposto em 1928. Este problema pediu um procedimento que iria decidir, dado um enunciado matemático formalizado, se a afirmação é verdadeira ou falsa.

Teoria dos conjuntos e paradoxos[editar | editar código-fonte]

[ [ Ernst Zermelo ] ] ([ [# CITEREFZermelo1904 | 1904 ]] ) deu uma prova de que todo conjunto pode ser bem ordenado , um resultado [ [ Georg Cantor ]] tinha sido incapaz de obter. Para conseguir a prova , Zermelo apresentou o [ [ axioma da escolha ]] , que atraiu debate aquecido e pesquisa entre os matemáticos e os pioneiros da teoria dos conjuntos . A crítica imediata do método levou Zermelo a publicar uma segunda exposição do seu resultado , dirigindo-se diretamente as críticas de sua prova ( [ [# CITEREFZermelo1908a | Zermelo 1908a ]] ) . Este trabalho levou à aceitação geral do axioma da escolha na comunidade matemática.

O ceticismo sobre o axioma da escolha foi reforçada por paradoxos descobertos recentemente na teoria ingênua dos conjuntos . [ [ Cesare Burali - Forti ] ] ([ [# CITEREFBurali - Forti1897 | 1897 ]] ) foi o primeiro a afirmar um paradoxo: os [[paradoxo de Burali - Forti] ] mostra que a coleção de todos os [ [ número ordinal ]] s não pode formar um conjunto . Pouco tempo depois , [ [ Bertrand Russell ]] descoberto [ [ paradoxo de Russell ]] em 1901, e [ [ Jules Richard ] ] ([ [# CITEREFRichard1905 | 1905 ]] ) descobriu [ [ paradoxo de Richard ]] .

Zermelo ( [ [# CITEREFZermelo1908b | 1908b ]] ), forneceu o primeiro conjunto de axiomas para a teoria dos conjuntos . Estes axiomas , juntamente com o adicional [ [ axioma da substituição ]] proposto por [ [ Abraham Fraenkel ]] , agora são chamados de [ [teoria dos conjuntos de Zermelo - Fraenkel]] (ZF ) . Axiomas de Zermelo incorporou o princípio da [ [ limitação de tamanho ]] para evitar o paradoxo de Russell.

Em 1910, o primeiro volume da [ [ Principia Mathematica ]] por Russell e [ [ Alfred North Whitehead ]] foi publicado . Este trabalho seminal desenvolveu a teoria de funções e de cardinalidade em um quadro completamente formal da [ [ teoria dos tipos] ], que Russell e Whitehead desenvolveram em um esforço para evitar os paradoxos . Principia Mathematica é considerada uma das obras mais influentes do século 20, embora o formato da teoria dos tipos não ser popular como uma teoria fundamental para a matemática ( [ [# CITEREFFerreir.C3.B3s2001 | Ferreirós 2001 ]] , p . 445).

Fraenkel ( [ [# CITEREFFraenkel1922 | 1922 ]] ) mostrou que o axioma da escolha não pode ser provado a partir dos restantes axiomas da teoria dos conjuntos de Zermelo com [ [ urelements ]] . Mais tarde, o trabalho por [ [ Paul Cohen ( matemático ) | Paul Cohen ] ] ([ [# CITEREFCohen1966 | 1966 ]] ) mostraram que a adição de Urelemento não é necessário, e o axioma da escolha é improvável em ZF . A prova de Cohen desenvolveu o método de [ [ forçamento (matemática) | forçamento ]] , que agora é uma importante ferramenta para o estabelecimento de [ [ resultado independência ]] s na teoria dos conjuntos .

Symbolic logic[editar | editar código-fonte]

Leopold Löwenheim ([ [# CITEREFL.C3.B6wenheim1915 | 1915 ]] ) e Thoralf Skolem ([ [# CITEREFSkolem1920 | 1920]] ) obteveram o teorema Löwenheim - Skolem , que diz: que a lógica de primeira ordem não pode controlar as cardinalidades das estruturas infinitas . Skolem percebeu que este teorema se aplica a formalizações de primeira ordem da teoria dos conjuntos , e que isso implica qualquer que formalização tem uma estrutura contábil (lógica matemática | model]] . Este fato absurdo se tornou conhecido como o paradoxo de Skolem .

Em sua tese de doutorado, Kurt Gödel ( 1929 ) provou a teorema da completude , que estabelece uma correspondência entre sintaxe e semântica em lógica de primeira ordem . Gödel usou o teorema da completude para provar a teorema de compacidade , que demonstra a natureza finitária de primeira ordem, a consequência lógica . Esses resultados ajudaram a estabelecer a lógica de primeira ordem como a lógica dominante usado pelos matemáticos .

Em 1931, Gödel publicou o proposições Formalmente indecidíveis de Principia Mathematica e sistemas relacionados , o que provou a incompletude (em um sentido diferente da palavra) de todos as efetivas teorias suficientemente forte, de primeira ordem. Este resultado , conhecido como teorema da incompletude de Gödel , estabelece limitações severas sobre bases axiomáticas para a matemática , um golpe forte para o programa de Hilbert . Ele mostrou a impossibilidade de fornecer uma prova de consistência da aritmética dentro de qualquer teoria formal da aritmética. Hilbert, no entanto, não reconhece a importância do teorema da incompletude por algum tempo.

Teorema de Gödel mostra que a prova de consistência de qualquer sistema axiomático suficientemente forte, eficaz, não pode ser obtido no próprio sistema , se o sistema é consistente, não pode ser obtido nem mesmo em qualquer sistema. Isso deixa aberta a possibilidade de provas de consistência que não podem ser formalizados dentro do sistema que eles consideram . Gentzen ( 1936 ) provou a consistência da aritmética utilizando um sistema finalístico juntamente com um princípio de indução transfinita . Resultado da Gentzen introduziu as idéias de eliminação corte e prova teórico- ordinal s , que se tornaram ferramentas importantes na teoria da prova . Gödel ( 1958 ) deu uma prova de consistência diferente , o que reduz a consistência da aritmética clássica à da aritmética intuitiva nos tipos mais elevados.

A partir de 1935, um grupo de matemáticos proeminentes colaborou com o pseudônimo de [ [ Nicolas Bourbaki ] ] para publicar uma série de textos de matemática enciclopédicos . Estes textos, escritos em um estilo austero e axiomático , enfatizou apresentação rigorosa e fundações da Teoria Dos Conjuntos . Terminologia cunhada por estes textos , como as palavras [ [ bijection , injeção, e surjection | bijeção , injeção , e sobrejetiva ] ] , e as Fundações da Teoria dos Conjuntos utilizados nos textos , foram amplamente adotadas em toda a matemática

O estudo da computabilidade veio a ser conhecida como teoria da recursão, porque primeiras formalizações de Gödel e Kleene contaram com definições recursivas de funções [2] Quando essas definições foram mostradas equivalentes à formalização de Turing envolvendo máquinas de Turing , ficou claro que um novo conceito – o da [ [função computável ]] - tinha sido descoberto, e que esta definição era robusta o suficiente para admitir caracterizações independentes numerosas. Em seu trabalho sobre os teoremas da incompletude , em 1931 , Gödel faltava um conceito rigoroso de um sistema formal eficaz ; ele imediatamente percebeu que as novas definições de computabilidade pode ser utilizado para este fim , permitindo-lhe indicar os teoremas da incompletude na generalidade, que só poderia ser implícita no artigo original .

Numerosos resultados em teoria da recursão foram obtidos na década de 1940 por Stephen Cole Kleene e [ [ Emil Leon Post] ] . Kleene ( 1943 ) introduziu os conceitos de computabilidade relativa, prenunciado por Turing ( 1939 ) e a hierarquia aritmética . Kleen, mais tarde, generalizou a teoria da recursão para funcionais de ordem superior. Kleene e Kreisel estudaram versões formais da matemática intuicionista , particularmente no contexto da teoria da prova . <- Talvez seja melhor parar essa história por volta de 1950 ->

Sistemas lógicos formais [editar | editar código-fonte]

Na sua essência, a lógica matemática lida com conceitos matemáticos expressos usando formal, sistema lógico s. Estes sistemas, apesar de se diferirem em muitos detalhes, compartilham a propriedade comum de considerar apenas expressões em uma linguagem formal fixa. Os sistemas de lógica proposicional e lógica de primeira ordem são os mais estudados hoje, por causa da sua aplicabilidade a fundamentos da matemática e por causa de suas propriedades desejáveis prova de teoria. [3] lógicas clássicas mais fortes, como [lógica [de segunda ordem.]] ou lógica infinitária também são estudadas, juntamente com lógicas não-clássicas, como lógica intuicionista.]].

Lógica de primeira ordem[editar | editar código-fonte]

Lógica de primeira ordem é um sistema formal de lógica especial. Sua [ [syntax ]] envolve apenas expressões finitas como fórmulas bem formadas , enquanto a sua semântica [[ ]] são caracterizados pela limitação de todos os quantificadores para um fixo domínio do discurso .

Os primeiros resultados de lógica formal estabelecido limitações da lógica de primeira ordem . O [ [ Löwenheim - Skolem teorema ]] (1919 ) mostrou que, se um conjunto de frases em uma linguagem de primeira ordem contáveis ​​tem um modelo de infinito , em seguida, que tem , pelo menos, um modelo de cada cardinalidade infinito. Isto mostra que não é possível para um conjunto de axiomas de primeira ordem para caracterizar os números naturais, os números reais, ou qualquer outra estrutura infinita até [ [ isomorfismo .]] Como o objetivo dos estudos fundamentais início era produzir teorias axiomáticas para todas as partes da matemática , esta limitação foi particularmente gritante.

Teorema da completude de Gödel ( Gödel 1929 ) estabeleceu a equivalência entre as definições semânticas e sintáticas de [ [ consequência lógica ]] em lógica de primeira ordem . Isso mostra que, se uma determinada frase é verdadeira em todos os modelos que satisfaça um determinado conjunto de axiomas , então deve haver uma dedução finito da sentença a partir dos axiomas . O teorema de compacidade apareceu pela primeira vez como um lema na prova do teorema da completude de Gödel , e levou muitos anos antes lógicos agarrou sua importância e começaram a aplicá-la de forma rotineira. Ele diz que um conjunto de penas tem um modelo de se e somente se a cada subconjunto finito tem um modelo , ou por outras palavras, um conjunto inconsistente de fórmulas deve ter um subconjunto inconsistente finito. A integralidade ea compacidade teoremas permitir a análise sofisticada de consequência lógica em lógica de primeira ordem e do desenvolvimento de teoria modelo , e eles são um dos principais motivos para o destaque de primeira ordem lógica em matemática.

Teoremas da incompletude de Gödel ( Gödel 1931 ) estabelecer limites adicionais sobre axiomatizações de primeira ordem. Afirma o ' primeiro teorema da incompletude ' que para qualquer efetivamente determinado sistema suficientemente forte, lógico que existe uma declaração que é verdade, mas não demonstrável dentro desse sistema . Aqui, um sistema lógico é efectivamente determinado se é possível decidir , qualquer dada fórmula na linguagem do sistema , se a fórmula é um axioma . Um sistema lógico é suficientemente forte se pode expressar os axiomas de Peano [[ ]] . Quando aplicado a lógica de primeira ordem , o primeiro teorema da incompletude implica que qualquer teoria de primeira ordem suficientemente forte, consistente e eficaz tem modelos que não são [ [ infra-estrutura elementar | elementarmente equivalente ]] , a limitação mais forte do que o estabelecido pela Löwenheim - Skolem teorema. Afirma o segundo teorema da incompletude que nenhum sistema suficientemente forte, consistente e eficaz axioma para a aritmética pode provar sua própria consistência , o que tem sido interpretado para mostrar que o programa de Hilbert não pode ser concluída .

Lógica Proposicional[editar | editar código-fonte]

Proposições[editar | editar código-fonte]

As proposições são determinadas por sentenças declarativas, pertencentes a uma certa linguagem, que formam um conjunto de palavras ou símbolos e expressam uma ideia. As sentenças declarativas são afirmações que podem receber apenas dois valores, Verdadeiro ou Falso. As proposições devem seguir os seguintes princípios:

  1. Princípio da identidade: garante que uma proposição é igual a ela mesma.
  2. Princípio da não-contradição: uma proposição não pode ser verdadeira e falsa.
  3. Princípio do terceiro excluído: uma proposição é verdadeira ou falsa.

Exemplos:

O cachorro é um animal. - Verdadeiro

2 + 2 = 7 - Falso

Qualquer sentença que não puder receber a atribuição de verdadeira ou falsa não é uma proposição. Sentenças interrogativas, exclamativas e imperativas não são proposições, pois não é possível dizer se são verdadeiras ou falsas.

Exemplos de sentenças que não são proposições:

  • Como foi a aula?
  • O pior atentado nos EUA ocorreu em setembro de 2011?
  • Limpe a cozinha.
  • Que local de trabalho horroroso!
  • Esta sentença não é verdadeira.

Proposições compostas[editar | editar código-fonte]

Proposição composta é a união de proposições simples por meio de um conector lógico. Este conector irá ser decisivo para o valor lógico da expressão.

Precedência de operadores[editar | editar código-fonte]

Em expressões que utilizam vários operadores não é possível saber qual proposição deve-se resolver primeiro.

Exemplo: P Λ Q V R.

Com isso, usar parênteses é fundamental. A expressão do exemplo poderia ficar assim: (P Λ Q) V R ou P Λ (Q V R).

A ordem da precedência de operadores é:

  1. (),, {}
  2. ¬
  3. V, Λ, V

Tabela Verdade[editar | editar código-fonte]

A tabela verdade é construída para determinar o valor lógico de uma proposição composta. Segue uma excelente estratégia para a construção da mesma.

Exemplo de construção da tabela verdade da proposição composta: p Λ q

Primeiramente verifica-se quantas “variáveis”, ou proposições simples que temos na proposição composta do exercício. Neste caso existem duas: p e q.

Em seguida elevamos 2 ao número de variáveis, ou seja, 2². Nossa base do expoente é 2 pelo fato de possuir-se apenas 2 valores lógicos possíveis nas proposições (Verdadeiro ou Falso). O resultado de 2² é 4. Então nossa tabela terá 4 linhas, nessas linhas estarão todos os valores lógicos possíveis da nossa proposição composta.

p
q
p Λ q
- -
-
- -
-
- -
-
- -
-

Esta é a estrutura da tabela, agora para a preencher com os devidos valores lógicos utiliza-se a seguinte técnica: até a metade da primeira coluna coloca-se Verdadeiro, na outra metade Falso. Já na segunda coluna, intercala-se V e F. Desta forma adquira-se a seguinte tabela:

p q
p Λ q
V V
Resultado
V F
Resultado
F V
Resultado
F F
Resultado

Esta é uma das melhores estratégias para a montagem de uma tabela verdade.

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

Proposições podem ser ligadas entre si por meio de conectivos lógicos. Conectores que criam novas sentenças mudando ou não seu valor lógico (Verdadeiro ou Falso). Exemplos dos principais conectores lógicos:

  • “¬” ou “~” (negação);
  • “Λ” (conectivo “e”);
  • “V” (conectivo “ou”);
  • “→” (conectivo “se, então”);
  • “↔” (conectivo “se, e somente se”);
  • V” (conectivo “ou exclusivo”);
  • “↓” (conectivo “negação conjunta”);
  • “↑” (conectivo “negação disjunta”).

Exemplos de sentenças formadas com conectores e proposições:

(2 + 2 = 4) V (1 < 4) - Valor lógico da sentença: Verdadeiro V (ou) Verdadeiro = Verdadeiro

Cachorro é um felino Λ (1 > 0) - Valor lógico da sentença: Falso Λ (e) Verdadeiro = Falso

Conector de Negação (~)[editar | editar código-fonte]

O conectivo de negação (~), nega o valor lógico de uma proposição. Considera-se p como uma proposição de valor lógico igual a verdadeiro, então sua negação é igual a falso. O mesmo seria se a proposição tivesse valor lógico inicial igual a falso, sua negação seria igual a verdadeiro. De acordo com esses conceitos podemos montar a seguinte tabela verdade:

p ~p
V
F
F
V

Exemplo:

Considere p com o valor da seguinte proposição: 2 é um número par. p = Verdadeiro, portanto sua negação: ~p = Falso.

Conector e (Λ)[editar | editar código-fonte]

O conectivo e, também conhecido como AND e representado pelo símbolo “^” junta proposições as quais somente resultarão em Verdadeiro se todos os valores forem Verdadeiros.

Exemplo: Considere as proposições p e q (Conjunção).

p q p Λ q
V V
V
V F
F
F V
F
F F
F

Observação: Veja que nesta tabela consideramos todos os valores lógicos possíveis para p e q, em outras palavras: temos 2 proposições e estamos em uma base binária (0 ou 1, verdadeiro ou falso) então para se saber o número das possibilidades para essas proposições realiza-se o seguinte cálculo 2n, onde n é o número de proposições.

Conector ou (V)[editar | editar código-fonte]

O conectivo ou, também conhecido como OR e representado pelo símbolo “V” une proposições que, apenas uma sendo Verdadeiro é suficiente que a expressão inteira também seja.

Exemplo:

Considere as proposições p e q (Disjunção).

p q p V q
V V
V
V F
V
F V
V
F F
F

Conector condicional (→)[editar | editar código-fonte]

O conectivo condicional, também conhecido como implica e representado pelo símbolo “→” une proposições criando uma estrutura condicional onde apenas uma das possibilidades resulta em F o valor lógico da expressão.

Exemplo:

Considere as proposições p e q (Condição). “Se p então q

p q p → q
V V
V
V F
F
F V
V
F F
V

Conector bi-condicional (↔)[editar | editar código-fonte]

O conectivo bi-condicional, é lido como “se, e somente se” e é representado pelo símbolo “↔”, ele une proposições onde o resultado lógico da expressão é verdadeiro apenas se os valores lógicos forem iguais.

Exemplo:

Considere as proposições p e q (Bi-condicional). “Se p, e somente se q

p q p ↔ q
V V
V
V F
F
F V
F
F F
V

Ou exclusivo (V)[editar | editar código-fonte]

O conectivo ou exclusivo, chamado também de disjunção exclusiva, é representado pelo símbolo “V”. Podemos dizer que ele significa: um ou outro, mas não ambos. Exemplo: Ou o gato é macho ou o gato é fêmea, mas não ambos. A tabela verdade do ou exclusivo esta representada abaixo.

p q p V q
V V
F
V F
V
F V
V
F F
F

Negação Conjunta e Negação Disjunta[editar | editar código-fonte]

A negação conjunta é representada pelo conector ↑, significa a negação de duas proposições envolvendo o conector AND (NAND).

Exemplo: p Λ q ⇔ ¬p ↑ ¬q.

A negação disjunta é representada pelo conector ↓, significa a negação de duas proposições envolvendo o conector OR (NOR).

Exemplo: p v q ⇔ ¬p ↓ ¬q.

Abaixo estão representadas as tabelas verdades das duas negações.

  • Tabela Verdade equivalente ao circuito NAND
p q p ↑ q
V V
F
V F
V
F V
V
F F
V
  • Tabela Verdade equivalente ao circuito NOR
p q p ↓ q
V V
F
V F
F
F V
F
F F
V

Tautologia, Contradição e Contingência[editar | editar código-fonte]

Ao montarmos uma tabela verdade contendo todos os valores lógicos possíveis de uma expressão a poderíamos classificar em tautologia, contradição e contingência.

  • Tautologia: é uma proposição cujo resultado final é sempre verdadeiro.

Exemplo:

p v ~p (p OU não p)

p ~p p V ~p
V F
V
F V
V

Veja que independente do valor de p a expressão sempre resulta em Verdadeiro, pois para o conector OU possuir um verdadeiro já é suficiente para resultar em Verdadeiro, além disso sempre teremos V em todas as combinações da expressão. Por isso a classificamos como uma tautologia.

Vejamos outro exemplo:

F → p (F então p)

Valor lógico constante p F → p
F
F
V
F
V
V

Neste outro caso também se obteve uma tautologia, devido ao fato da última coluna da tabela (resultado da expressão) ter somente Verdadeiro.

  • Contradição: é uma proposição que resulta somente em falso, em outras palavras, a última coluna da sua tabela só possui o valor lógico falso.

Exemplo:

p ^ ~p

p ~p p ^ ~p
V
F
F
F
V
F
  • Contingência: determinamos uma proposição de contingente quando ela não é tautológica nem contraditória, ou seja, ela é indeterminada.

Exemplo:

p V q (p OU q)

p q p V q
V V
V
V F
V
F V
V
F F
F

Percebe-se que a última coluna não possui apenas um valor lógico, por isso a determinamos uma proposição contingente, ou indeterminada.

Implicação lógica ou Inferência[editar | editar código-fonte]

Sejam P e Q duas proposições. Diremos que P implica logicamente a proposição Q, se Q for verdadeiro sempre que P for verdadeiro. Quando isso ocorre, dizemos que temos uma implicação lógica ou inferência e denotamos: P => Q (lemos: “P implica Q”).

Exemplo: P Λ Q implica P V Q?

p q p Λ q p V q
V V
V
V
V F
F
V
F V
F
V
F F
F
F

Neste exemplo podemos dizer que P Λ Q => P V Q, pois onde P Λ Q é verdadeiro P V Q também é.

Exemplo: P V Q implica P → Q?

p q p V q p → q
V V
V
V
V F
V
F
F V
V
V
F F
F
V

Neste exemplo não podemos dizer que P V Q => P → Q, pois temos na segunda linha que onde P V Q é verdadeiro P → Q é falso.

Equivalência lógica[editar | editar código-fonte]

Diremos que P é equivalente a Q, se as duas tabelas verdade foram idênticas. Quando isso ocorre, dizemos que temos uma equivalência lógica ou bi-implicação e denotamos P ⇔ Q (lemos: “P é equivalente a Q”).

Exemplo: ¬(P Λ Q) é equivalente a (¬P V ¬Q)?

P Q ¬P ¬Q P Λ Q ¬(P Λ Q) ¬P V ¬Q
V V
F
F
V
F
F
V F
F
V
F
V
V
F V
V
F
F
V
V
F F
V
V
F
V
V

Neste exemplo podemos dizermos que ¬(P Λ Q) ⇔ (¬P V ¬Q), pois o resultado da tabela verdade das duas expressões é o mesmo.

Exemplo: P → Q é equivalente a Q → P?

P Q P → Q Q → P
V V
V
V
V F
F
V
F V
V
F
F F
V
V

Neste exemplo não podemos dizer que P → Q ⇔ Q → P, pois o resultado das tabelas verdades das expressões são diferentes, nas linhas 2 e 3.

Condições necessárias e suficientes[editar | editar código-fonte]

Temos uma condição suficiente se quando ela ocorrer temos a garantia de que a outra condição ocorrerá. Por exemplo:

“Se o cavalo corre então ele está vivo.”

O cavalo correr é condição suficiente para ele estar vivo,ou seja, se o cavalo corre podemos garantir que ele está vivo.

Por outro lado o cavalo estar vivo não garante que o cavalo corra, pois ele pode estar por exemplo vivo mas descansando, a este tipo de condição dá se o nome de condição necessária. Uma condição é necessária quanto não podemos garantir que a outra condição é valida.

Esta relação entre condição suficiente e condição necessária é encontrada quando utilizamos um conector condicional, ou seja, quando temos uma estrutura condicional. O primeiro argumento(que vem antes do →), chamado de antecedente é uma condição suficiente. O segundo argumento,chamado de consequente é uma condição necessária.

Entretanto em uma estrutura bi-condicional temos uma proposição necessária e suficiente,.

Proposições Associadas a uma Condicional[editar | editar código-fonte]

Pegamos uma condicional qualquer como p → q, existem três tipos de proposições associadas a ela que são:

  • Recíproca: a proposição recíproca de p → q é a proposição q → p.Como podemos ver foi feito uma troca entre a antecedente (p) e a consequente (q) para obter-se a recíproca cuja tabela esta abaixo:
p q p → q q → p
V V
V
V
V F
F
V
F V
V
F
F F
V
V

Exemplo: “Se a Maria é feia então todos são feios.”

A recíproca seria: “Se todos são feios então Maria é feia.”

  • Contrária: a proposição contrária de p → q é a proposição ~p → ~q.Basta negar a antecedente(p) e a consequente(q) para obtermos a proposição contrária.
p q ~p ~q p → q ~p → ~q
V V
F
F
V
V
V F
F
V
F
V
F V
V
F
V
F
F F
V
V
V
V

Exemplo: “Se a Maria é feia então todos são feios.”

A contrária seria: “Se Maria não é feia então todos não são feios.”

  • Contra Positiva: a contra positiva da preposição p → q é ~q → ~p. Para encontramos a contra positiva basta juntar os passos da recíproca e da contrária,ou seja, deve se inverter os lugares do antecedente e do consequente e negar ambos. A proposição contra positiva tem o mesmo resultado que a proposição original.
p q ~p ~q p → q ~q → ~p
V V
F
F
V
V
V F
F
V
F
F
F V
V
F
V
V
F F
V
V
V
V

Exemplo: “Se a Maria é feia então todos são feios.”

A contra positiva seria: “Se todos não são feios então Maria não é feia.”

Referências

  1. Undergraduate texts include Boolos, Burgess, and Jeffrey (2002), Enderton (2001), and Mendelson (1997). A classic graduate text by Shoenfield (2001) first appeared in 1967.
  2. Um estudo detalhado desta terminologia é dada por Soare ( [ [# CITEREFSoare1996 | 1996 ]] ) . .
  3. Ferreirós ( 2001) examina a ascensão da lógica de primeira ordem em relação a outras lógicas formais no início do século 20

Ver também[editar | editar código-fonte]


Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.