Lógica Matemática e Teoria dos Grafos: História e Paradoxos

Prévia do material em texto

História (apenas lógica matemática e teoria dos grafos)
Lógica matemática
 Aristóteles (384BC-322BC) Sistematização de lógica dedutiva com ampla utilização de linguagem natural. Principio da não-contradição. Organon.
 Gottfried Leibniz (1646-1716) Enfatização da importância de sistemas simbólicos na compreensão das coisas. Idealização de um alfabeto do pensamento humano e de um sistema uniforme e simétrico capaz da gerar idéais mais complexas a partir de idéias mais simples.
 George Boole (1815-1864) Álgebra booleana (base da aritmética computacional). Início da lógica matemática.
 Gottlob Frege (1848-1925) Primeira grande contribuição à lógica desde Aristóteles. Logicismo (sistematização dos anseios de Leibniz). Lógica de predicados.
 David Hilbert (1862-1943) Formalização e "divulgação" do problema da axiomatização da matemática.
 Bertrand Russell (1872-1970) Principia Mathematica (tentativa de axiomatização da matemática). Maior clareza na exposição da lógica de predicados. Paradoxo de Russell
 Kurt Gödel (1906-1978) Teorema da Completude. Teorema da Incompletude. (Clique aqui para ler um texto informal que alerta para possível confusão entre os diferentes significados do termo "completude" nos teoremas de Gödel, por Torkel Franzén)
Teoria dos Grafos
 Leonhard Euler (1707-1783) Seven bridges of Königsberg. 
...em construção...
Um paradoxo é uma declaração que vai contra o senso comum, expectativas ou definições. Na filosofia e na lógica, por exemplo, os paradoxos são importantes argumentos críticos, e já foram responsáveis pela organização ou reorganização de fundamentos de várias áreas do conhecimento. Parece complexo, não? Mas a gente te explica com calma. De uma vastidão de problemas paradoxais da lógica e da matemática, trazemos cinco deles que já deram um nó na cabeça de muita gente. Dá uma olhada:
1. Paradoxo de Russell (e Paradoxo do Barbeiro)
Em 1901, enquanto trabalhava em seu livro Os princípios da Matemática, Bertrand Russell descobriu um paradoxo que expunha uma falha nos fundamentos da Teoria dos Conjuntos, de Georg Cantor – o que abalou o mundo da matemática e levou cientistas a repensarem a lógica moderna. Segundo a teoria de Cantor, um conjunto pode conter outros conjuntos, inclusive a si mesmo. Por exemplo, o conjunto das ideias é uma ideia. Mas isso não é verdade para todos os conjuntos, já que existem alguns que não podem conter a si mesmos. É o caso do conjunto de todos os números, que não é um número, ou do conjunto de todas as frutas, que não é uma fruta.
Aí Russell resolveu complicar a história. O matemático pegou esse conjunto dos conjuntos que não contém a si mesmos (aquele que inclui o conjunto de todos os números e o de todas as frutas) e perguntou: “Esse conjunto pertence a si mesmo?”. Existem duas repostas possíveis: sim, ele pertence a si mesmo, ou não, não pertence a si mesmo. Se a resposta é que ele pertence a si mesmo, ele é um conjunto que não pertence a si mesmo (porque essa é a característica que define os participantes desse conjunto específico). E se a resposta for que ele não pertence a si mesmo, então ele é um conjunto que pertence a si mesmo. Tá aí o paradoxo de Russell: a resposta afirmativa leva a negação, e vice-versa.
Mas esse paradoxo não fica restrito à matemática, e pode ser entendido também no contexto da autorreferência, que é quando uma afirmação faz referência a si mesma. Ele também é conhecido como o Paradoxo do Barbeiro, contado pelo próprio autor para melhor explicar suas ideias: em uma cidade com uma lei rígida quanto ao uso da barba, a regra é que todo homem adulto é obrigado a se barbear diariamente, mas não precisa fazer a própria barba. Existe um barbeiro na cidade para esses casos, para o qual a lei diz que “o barbeiro deverá fazer a barba daqueles que optarem por não fazer a própria barba”. Dessa afirmação, surge o paradoxo, já que como resultado o barbeiro não pode se barbear. Por ser o barbeiro, fazer a própria barba significaria ser barbeado pelo homem que faz a barba só daqueles que optaram por não fazer a própria barba. E ele não pode ir ao barbeiro, pois isso significaria fazer a própria barba, o que não é a função do barbeiro.
 
2. Paradoxo do Mentiroso
Ainda no terreno da autorreferência, há um paradoxo que existe nas mais variadas formas desde os filósofos da Grécia Antiga. Ebulides de Mileto, no século 4 a.C., perguntou: “Um homem diz que está mentindo. O que ele diz é verdade ou mentira?”. Mais uma vez, encontramos uma afirmativa que leva à negação e uma negação que leva à afirmativa. Se o homem estiver mentindo, então ele está falando a verdade. Se o homem estiver falando a verdade, então ele está mentindo. O problema revelado aqui é da ordem do senso comum: o que entendemos por verdade e mentira nos leva a contradições.
O Paradoxo do Mentiroso já foi registrado assumindo diferentes formas, contando diferentes histórias, em diversos tempos e culturas. Uma das mais populares é o Paradoxo do Pinóquio. O personagem da literatura infantil, criado por Carlo Collodi, afirma: “O meu nariz vai crescer”. Quem conhece a história sabe que o nariz do boneco de madeira cresce a cada vez que ele conta uma mentira. Bem, se o nariz do boneco crescer, então a afirmação era verdadeira e nada deveria ter acontecido. Se o nariz não crescer, então a afirmação era uma mentira e o nariz deveria ter crescido.
A partir de uma afirmação derivada da proferida por Ebulides em sua forma mais simples (“Esta afirmação é falsa”), Kurt Gödel demonstrou o Teorema da Incompletude, na lógica moderna. Em linguagem aritmética, o matemático disse que “esta afirmação é indemonstrável”. Se um axioma (princípio matemático que não precisa de demonstração) desenvolvido tendo como base essa estrutura é falso, então ele é falso e demonstrável, o que é incoerente. Se o axioma é verdadeiro, então ele é verdadeiro e indemonstrável, e, portanto, incompleto. Assim, qualquer teoria na qual seja possível formular uma afirmação como essa é necessariamente incompleta.
3. O problema de Monty Hall
No final dos anos 80, o humorista Sérgio Mallandro apresentava o programa infantil Oradukapeta, no SBT. O quadro mais popular do programa era a “Porta dos desesperados”, em que crianças da plateia escolhiam uma entre três portas. Atrás de uma delas havia prêmios, e das outras duas, monstros fantasiados. Agora vamos lá, suponha que você é um participante e escolheu a porta 1. Outro participante escolhe a porta 2 e a abre primeiro, revelando um monstro. Quando o apresentador pergunta se você deseja trocar a porta selecionada, qual seria a melhor decisão?
Muitas pessoas diriam que a chance de encontrar um prêmio é agora de uma chance em duas, e que tanto faz qual for a decisão final. Mas em 1975, nos Estados Unidos, a escritora Marilyn vos Savant disse em sua coluna na revista Parade que, em uma situação similar, o participante deveria optar por trocar de portas. Segundo ela, a troca levaria a uma probabilidade de 2/3 de ganhar o prêmio, enquanto a chance de levar a melhor ao permanecer com a escolha inicial seria de apenas 1/3.
Isso acontece porque, ao escolher uma porta, a chance de acerto é inicialmente de 1/3. Já tendo sido revelada uma porta falsa, caso a troca seja efetuada, deve-se somar ao 1/3 de chance da porta restante, o 1/3 de probabilidade que era conferido à porta revelada, chegando então a duas em três chances de acertar.
Muitos leitores, entre eles especialistas, não foram convencidos pelas explicações da colunista, e escreveram à revista alegando que a proposta deveria estar errada. Com a polêmica, foram conduzidas simulações e provas matemáticas foram desenvolvidas para mostrar que, apesar de fugir ao senso comum, vos Savant estava certa.
O problema de Monty Hall ganhou o nome do apresentador do programa de TV Let’s Make a Deal, que funcionava com uma dinâmica bem próxima à da Porta dos Desesperados, de Sérgio Mallandro. É um paradoxo classificado como verídico pelo sistema do filósofo e lógico Willard Van Orman Quine, jáque apresenta resultados tão pouco intuitivos que parecem absurdos, mas que são demonstrados como verdadeiros.
 
4. Aquiles e a tartaruga
O que aconteceria se uma tartaruga apostasse corrida com um atleta? A resposta parece fácil, mas o filósofo pré-socrático Zeno de Eleia complicou as coisas com um de seus paradoxos do movimento. A história contada para explicar o problema proposto pelo pensador é a seguinte: Aquiles e uma tartaruga decidem apostar uma corrida e, como a velocidade de deslocamento do herói da mitologia grega é muito maior que a do pequeno réptil, ele dá uma vantagem para a tartaruga, que começa a prova à frente.
Quando Aquiles alcança o ponto A, de onde saiu a tartaruga, ela já está à frente, no ponto B. E quando ele chega ao ponto B, a tartaruga já se encontra no ponto C. Ao Aquiles alcançar o ponto C, ela já está em D, e assim sucessivamente. Dessa forma, o guerreiro nunca conseguiria ultrapassar a tartaruga. Matematicamente, seria como pensar em um limite: o limite da expressão teria o espaço entre os dois corredores tendendo a zero – e isso significa dizer que a expressão se aproximaria cada vez mais do número 0, sem nunca alcançá-lo.
Um dos problemas é que Zeno desconsiderou a variável do tempo. O paradoxo supõe que a soma de infinitos intervalos de tempo é infinita, mas a soma dos infinitos intervalos de tempo que Aquiles gasta para se aproximar da tartaruga, na verdade, converge para um valor finito. Então o herói só não conseguiria alcançar a tartaruga em um intervalo de tempo específico. Apesar das incoerências, o paradoxo foi importante para pensarmos os infinitos, a noção de referencial e movimento.
 
5. Paradoxo do enforcamento inesperado
Um juiz decreta a sentença de um homem condenado, e conta para o prisioneiro que ele vai ser enforcado na próxima semana, entre segunda e sexta-feira, em um dia inesperado, ao meio-dia. O homem entende a sentença de tal forma que fica aliviado, certo de que não vai ser executado.
O raciocínio dele é o seguinte: quando chegar a quinta a noite e ainda não houver ocorrido a execução, ele irá saber que esta não pode mais acontecer na sexta, já que isso seria esperado, o que contradiz a sentença – que deixou claro que ele seria enforcado em um dia inesperado. Então, se chegada a quarta-feira e a execução não houver acontecido, a mesma não poderá ser na quinta, pelo mesmo motivo apresentado antes. E assim por diante, não poderá ocorrer na quarta, na terça e nem na segunda. Mas na quarta-feira o prisioneiro é enforcado, uma vez que a lógica desenvolvida por ele tornou a sua execução inesperada.
Os lógicos entendem que o problema do paradoxo está em sua natureza de autorreferência e na sentença contraditória do juiz que, ao estipular um tempo determinado (meio-dia) e contado (uma semana) para o enforcamento, não poderia também falar em inesperado. Para a epistemologia, o paradoxo pode também ser um problema associado ao conhecimento – o que sabemos e o que esperamos entra em jogo.
 
Bônus: Paradoxo do avô
Um viajante no tempo volta ao passado para um momento em que seus avós ainda não se conheciam, mata seu avô e, como consequência, impede o próprio nascimento. O problema é que, sem ter nascido, o viajante não pode voltar no tempo para matar seu avô, o que significa que ele nasceu.
Nem da lógica e nem da matemática, essa é a descrição do Paradoxo do avô, que foi proposto pela primeira vez pelo escritor de ficção científica René Barjavel, em sua obra Le Voyageur imprudent, de 1943. O autor provou que qualquer um pode desenvolver um paradoxo, e que um paradoxo é um olhar crítico sobre como se vê e como se organiza o mundo.
A natureza contraditória do Paradoxo do avô, que mostra a impossibilidade dos eventos ocorrerem como descritos, está associada a uma visão de como é a ligação entre passado e futuro. Em diferentes cenários, com diferentes perspectivas sobre a estrutura temporal, o paradoxo não faria sentido. Por exemplo, a partir da noção de que o passado é imutável, seria impossível matar o avô. Também podemos pensar que a viagem no tempo cria ou se associa a uma linha do tempo alternativa, em um universo paralelo, em que, ao matar o avô, aquele que seria o viajante não chega a nascer.
A lógica matemática surgiu em meados do século XIX como um sub-ramo da Matemática e independente do estudo tradicional da lógica (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 século XX houve uma explosão de resultados fundamentais, acompanhados por debates vigorosos sobre as bases da matemática.
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]
 Mais informações: História da lógica
Teorias lógicas foram desenvolvidas em diversas culturas na história, 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, transformaram a doutrina tradicional de Aristóteles de forma que se encaixasse no estudo dos fundamentos da matemática (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 vezes 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ício 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 referência para lógica simbólica, como era conhecida no fim do século XIX.
Fundamentos teóricos[editar | editar código-fonte]
Preocupações com a possível ausência de fundamentos matemáticos acarretaram o desenvolvimento de sistemas axiomáticos para áreas da matemática fundamental como a aritmética, 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 lógico 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 lógica formal dos axiomas de Peano. Todavia, o trabalho de Dedekind'sprovou teoremas inacessíveis ao sistema desenvolvido por Peano, como por exemplo a inclusão da individualidade dos conjuntos de números 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 axiomas 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 metade do século XX.
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:
Princípio da identidade: garante que uma proposição é igual a ela mesma.
Princípio da não-contradição: uma proposição não pode ser verdadeira e falsa.
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 é:
(),, {}
¬
Λ, 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 desta.
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, 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
Observação: não devemos confundir a operação condicional “→” com o relação implica " => " , pois, enquanto o primeiro representa uma operação entre proposições dando origem a uma outra proposição, o segundo indica apenas uma relação entre proposições dadas.
Relação de implicação ( => ): uma proposição p implica q quando em sua tabelas-verdade, não pode ocorrer 1 e 0 nessa ordem.
	p
	q
	V
	V
	V
	F
	F
	F
p não Implica q, pois, na segunda linha aparece p = V e q = F.
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, masnã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 disjunta é representada pelo conector ↑, significa a negação de duas proposições envolvendo o conector AND (NAND).
Exemplo: p ↑ q ⇔ ¬(p Λ q) ⇔ ¬p v ¬q.
A negação conjunta é representada pelo conector ↓, significa a negação de duas proposições envolvendo o conector OR (NOR).
Exemplo: p ↓ q ⇔ ¬(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.”
Inversa: 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 inversa.
	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 inversa 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
Ir para cima↑ Undergraduate texts include Boolos, Burgess, and Jeffrey (2002), Enderton (2001), and Mendelson (1997). A classic graduate text by Shoenfield (2001) first appeared in 1967.
Carlos Fontes. Definição e Evolução da Lógica; 28 de abril de 2012. Disponível em: http://afilosofia.no.sapo.pt/pag2Def.htm
Grupo iPED. Noções de lógica.Colégio web; 7 de maio de 2012. Disponível em: http://www.colegioweb.com.br/matematica/conectivos-logicos-.html
GERÔNIMO, João Roberto; FRANCO Valdeni Soliane. Fundamentos de matemática: uma introdução à lógica matemática, teoria dos conjuntos, relações e funções. 2º Edição 2008.