Modificação dos nossos Termos de Uso:Por favor, comente sobre uma proposta de alteração relativa a ediçõespagas não reveladas.<http://meta.wikimedia.org/wiki/Terms_of_use/Paid_contributions_amendment>[ Ajuda-nos com as traduções! ]<http://meta.wikimedia.org/w/index.php?title=Special:Translate&group=Centralnotice-tgroup-ChangeToU2014_v1&filter=>

fechar <#>

Lógica proposicional

Origem: Wikipédia, a enciclopédia livre.Ir para: navegação <#mw-navigation>, pesquisa <#p-search>Ambox rewrite.svg <http://pt.wikipedia.org/wiki/Wikip%C3%A9dia:Reciclagem>

*Esta página precisa ser reciclada<http://pt.wikipedia.org/wiki/Wikip%C3%A9dia:Reciclagem> de acordo com olivro de estilo<http://pt.wikipedia.org/wiki/Wikip%C3%A9dia:Livro_de_estilo>* (desdefevereiro de 2010).Sinta-se livre para editá-la para que esta possa atingir um nível dequalidade superior<http://pt.wikipedia.org/wiki/Wikip%C3%A9dia:Livro_de_estilo/Como_escrever_um_bom_artigo>.

Em lógica e matemática, uma *lógica proposicional* (ou cálculosentencial) é um sistema formal<http://pt.wikipedia.org/wiki/Sistema_formal> no qual as fórmulasrepresentam /proposições<http://pt.wikipedia.org/wiki/Proposi%C3%A7%C3%A3o>/ que podem serformadas pela combinação de proposições atômicas usando /conectivoslógicos/ e um sistema de /regras de derivação/, que permite que certasfórmulas sejam estabelecidas como "teoremas<http://pt.wikipedia.org/wiki/Teorema>" do sistema formal.

Em termos gerais, um cálculo é frequentemente apresentado como umsistema formal que consiste em um conjunto de expressões sintáticas(fórmulas bem formadas, ou fbfs <http://pt.wikipedia.org/wiki/FBF>), umsubconjunto distinto dessas expressões, e um conjunto de regras formaisque define uma relação binária específica, que se pretende interpretarcomo a noção de equivalência lógica, no espaço das expressões.

Quando o sistema formal tem o propósito de ser um sistema lógico, asexpressões devem ser interpretadas como asserções matemáticas, e asregras, conhecidas como /regras de inferência/, normalmente sãopreservadoras da verdade. Nessa configuração, as regras (que podemincluir axiomas) podem então ser usadas para derivar "inferir" fórmulasrepresentando asserções verdadeiras.

O conjunto de axiomas pode ser vazio, um conjunto finito não vazio, umconjunto finito enumerável, ou pode ser dado por axiomas esquemáticos.Uma gramática formal define recursivamente as expressões e fórmulas bemformadas (fbfs <http://pt.wikipedia.org/wiki/FBF>) da linguagem. Alémdisso, pode se apresentar uma semântica para definir verdade evalorações (ou interpretações<http://pt.wikipedia.org/wiki/Estrutura_%28l%C3%B3gica%29>).

A linguagem de um cálculo proposicional consiste em:

1. um conjunto de símbolos primitivos, definidos como /fórmulas atômicas <http://pt.wikipedia.org/wiki/F%C3%B3rmula_at%C3%B4mica>/, proposições atômicas, ou variáveis, e 2. um conjunto de operadores, interpretados como /operadores lógicos/ ou /conectivos lógicos/.

Uma fórmula bem formada (fbf <http://pt.wikipedia.org/wiki/FBF>) équalquer fórmula atômica ou qualquer fórmula que pode ser construída apartir de fórmulas atômicas, usando conectivos de acordo com as regrasda gramática.

O que segue define um cálculo proposicional padrão. Existem muitasformulações diferentes as quais são todas mais ou menos equivalentes masque diferem nos detalhes:

1. de sua linguagem, que é a coleção particular de símbolos primitivos e operadores, 2. do conjunto de axiomas, ou fórmulas distinguidas, e 3. do conjunto de regras de inferência.

Índice

[esconder <#>]

* 1 Abstração e aplicações <#Abstra.C3.A7.C3.A3o_e_aplica.C3.A7.C3.B5es> * 2 Descrição genérica de um cálculo proposicional <#Descri.C3.A7.C3.A3o_gen.C3.A9rica_de_um_c.C3.A1lculo_proposicional> o 2.1 Descrição <#Descri.C3.A7.C3.A3o> o 2.2 Tabelas Verdade <#Tabelas_Verdade> + 2.2.1 Negação <#Nega.C3.A7.C3.A3o> + 2.2.2 Conjunção <#Conjun.C3.A7.C3.A3o> + 2.2.3 Disjunção <#Disjun.C3.A7.C3.A3o> + 2.2.4 Implicação ou Condicional <#Implica.C3.A7.C3.A3o_ou_Condicional> + 2.2.5 Bi-implicação ou Equivalência <#Bi-implica.C3.A7.C3.A3o_ou_Equival.C3.AAncia> * 3 Exemplo 1. Sistema axiomático simples <#Exemplo_1._Sistema_axiom.C3.A1tico_simples> * 4 Exemplo 2. Sistema de Dedução Natural <#Exemplo_2._Sistema_de_Dedu.C3.A7.C3.A3o_Natural> o 4.1 Regra de Demonstração Condicional (RDC) <#Regra_de_Demonstra.C3.A7.C3.A3o_Condicional_.28RDC.29> * 5 Correção e completude das regras <#Corre.C3.A7.C3.A3o_e_completude_das_regras> * 6 Um cálculo alternativo <#Um_c.C3.A1lculo_alternativo> o 6.1 Axiomas <#Axiomas> o 6.2 Regra de inferência <#Regra_de_infer.C3.AAncia> o 6.3 Meta-regra de inferência <#Meta-regra_de_infer.C3.AAncia> o 6.4 Exemplo de uma prova <#Exemplo_de_uma_prova> * 7 Outros cálculos lógicos <#Outros_c.C3.A1lculos_l.C3.B3gicos> * 8 Referências gerais <#Refer.C3.AAncias_gerais> * 9 Ver também <#Ver_tamb.C3.A9m> o 9.1 Níveis lógicos <#N.C3.ADveis_l.C3.B3gicos> o 9.2 Blocos básicos <#Blocos_b.C3.A1sicos> o 9.3 Tópicos relacionados <#T.C3.B3picos_relacionados>

Abstração e aplicações

Embora seja possível construir um cálculo abstrato formal que não temuso prático imediato e praticamente nenhuma aplicação óbvia, o nome/cálculo <http://pt.wikipedia.org/wiki/C%C3%A1lculo>/ indica que estaespécie de sistema formal tem sua origem na utilidade de seus membrosprotópicos no cálculo prático. Em geral, qualquer cálculo matemático écriado com a intenção de representar um certo domínio de objetosformais, e tipicamente com o objetivo de facilitar as computações einferências que precisam ser realizadas sobre esta representação. Assim,antes de se desenvolver o próprio cálculo, deve-se dar uma idéia da suadenotação pretendida, isto é, dos objetivos formais que se pretendedenotar com as fórmulas do cálculo.

Visto ao longo de seu desenvolvimento histórico, um cálculo formal paraqualquer tópico de estudo normalmente surge através de um processo deabstração gradual, refinamento passo-a-passo, e síntese por tentativa eerro a partir de um conjunto de sistemas notacionais informais prévios,cada um dos quais tratando do mesmo domínio de objetos apenas em parteou de um ângulo em particular.

Descrição genérica de um cálculo proposicional

A lógica proposicional tem como objetivo modelar o raciocínio humano,partindo de frases declarativas (proposições). Para entender melhor oque é uma proposição considere a frase “1 mais 1 é igual a 10” ousimbolicamente, “1 + 1 = 10”. Esta frase é uma proposição no sentido deque ela é uma asserção declarativa, ou seja, afirma ou nega um fato, etem um /valor de verdade<http://pt.wikipedia.org/wiki/Valor_de_verdade>/, que pode serverdadeiro ou falso. Neste caso, num sistema de numeração de base 2, aproposição anterior seria verdadeira, enquanto que no sistema decimalseria falsa. Um outro exemplo é a afirmação “hoje é um dia quente” cujovalor de verdade vai depender de vários fatores: o local sobre o qualimplicitamente se está falando, os instrumentos de medidas e decomparação (quais os dados estatísticos de temperatura dessa região), eprincipalmente de quem está avaliando (duas pessoas, mesmo considerandoas mesmas condições nos itens anteriores, podem avaliar diferentemente).Ou seja, o valor verdade de uma proposição não é um conceito absoluto,mas depende de um contexto interpretativo. Há inclusive proposições, quemesmo num contexto interpretativo claro e não ambíguo, para as quais nãoé possível estabelecer de forma inquestionável sua veracidade oufalsidade (pelo menos com o conhecimento atual da humanidade). Mas, emlógica, o importante não é o valor de verdade que uma proposição possatomar num determinado contexto interpretativo, mas a possibilidade deque “em princípio” seja possível atribuir um valor de verdade, e queseja possível raciocinar com estas proposições.

A lógica proposicional estuda *como* raciocinar com afirmações que podemser verdadeiras ou falsas, ou ainda *como* construir a partir de umcerto conjunto de hipóteses (proposições verdadeiras num determinadocontexto) uma demonstração de que uma determinada conclusão é verdadeirano mesmo contexto. Assim, são fundamentais as noções de proposição,verdade, dedução e demonstração. A lógica proposicional clássica é umdos exemplos mais simples de lógica formal. Esta lógica leva em conta,somente, os valores de verdade verdadeiro e falso e a forma dasproposições. O estudo detalhado dessa lógica é importante porque elacontém quase todos os conceitos importantes necessários para o estudo delógicas mais complexas.

Descrição

*Um cálculo proposicional* é um sistema formal {\mathcal{L}}=(\mathrm{A} ,\ \Omega ,\ \mathrm{Z} ,\ \mathrm{I} ) cujas fórmulassão construídas da seguinte maneira:

* O /conjunto alfa/ \mathrm{A} \! é um conjunto finito de elementos chamados /símbolos de proposição/, ou /variáveis proposicionais/ ou simplesmente /átomos/. Sintaticamente falando, estes são os elementos mais básicos da linguagem formal {\mathcal {L}}, também referidos como /fórmulas atômicas/ ou /elementos terminais/. Nos exemplos a seguir, os elementos de \mathrm{A} \! são tipicamente as letras {\mathcal {P}},\ {\mathcal {Q}},\ {\mathcal {R}}, em diante. * O /conjunto omega/ \Omega \! é um conjunto finito de elementos chamados /símbolos de operadores/ ou /conectivos lógicos/. O conjunto \Omega \! é dividido entre os seguintes conjuntos distintos:

\Omega =\Omega _{0}\cup \Omega _{1}\cup \ldots \cup \Omega _{j}\cup \ldots \cup \Omega _{m}\,.

Nesta divisão, \Omega _{j}\! é o conjunto dos símbolos de /aridade <http://pt.wikipedia.org/wiki/Aridade>/ j\!.

Nos cálculos proposicionais mais familiares, \Omega \! é tipicamente particionado em termos de:

\Omega _{1}=\{\lnot \}\,,

\Omega _{2}\subseteq \{\land ,\lor ,\rightarrow ,\leftrightarrow \}\,.

Uma opção frequentemente adotada é tratar os valores lógicos constantes como operadores de /aridade <http://pt.wikipedia.org/wiki/Aridade>/ zero. Assim:

\Omega _{0}=\{\bot ,\top \}\,.

Alguns autores usam o til (~) ao invés de (¬); e alguns usam o (&) ou (\cdot ) ao invés de (∧). A notação varia ainda mais para o conjunto de valores lógicos, com símbolos como {falso, verdadeiro}, {F, V}, ou {0, 1} todos sendo usados em vários contextos ao invés de {\bot , \top }.

* Dependendo da gramática formal específica que se está usando, auxiliares sintáticos tais como o parêntese esquerdo, “(”, e o parêntese direito, “)”, podem ser necessários para completar a construção das fórmulas.

A /linguagem/ de {\mathcal {L}}, também conhecida como o seu conjunto de/fórmulas/, /fórmulas bem formadas/ ou /fbfs<http://pt.wikipedia.org/wiki/FBF>/, é definida recursiva ouindutivamente pelas seguintes regras:

1. Base. Qualquer elemento do conjunto alpha \mathrm{A} \! é fórmula de {\mathcal {L}}. 2. Passo (a). Se {\mathcal {P}} é uma fórmula, então ¬{\mathcal {P}}, é uma fórmula. 3. Passo (b). Se {\mathcal {P}} e {\mathcal {Q}} são fórmulas, então (/{\mathcal {P}}/ ∧ /{\mathcal {Q}}/), (/{\mathcal {P}}/ ∨

/{\mathcal {Q}}/), (/{\mathcal {P}}/ → /{\mathcal {Q}}/), e (/{\mathcal {P}}/ ↔ /{\mathcal {Q}}/) são fórmulas. 4. Fechado. Nada mais é uma fórmula de {\mathcal {L}}.

Aplicações relacionadas dessas regras permitem a construção de fórmulascomplexas. Por exemplo:

1. Pela regra 1, /{\mathcal {P}}/ é uma fórmula. 2. Pela regra 2, ¬/{\mathcal {P}}/ é uma fórmula. 3. Pela regra 1, /{\mathcal {Q}}/ é uma fórmula. 4. Pela regra 3, (¬/{\mathcal {P}}/ ∨ /{\mathcal {Q}}/) é uma fórmula.

* O /conjunto zeta/ \mathrm{Z} \! é um conjunto finito de /regras de transformação/ que são conhecidas como /regras de inferência/ do ponto de vista das aplicações lógicas. * O /conjunto iota/ \mathrm{I} \! é um conjunto finito de /pontos iniciais/ que são chamados de /axiomas/ quando eles recebem interpretações lógicas.

Tabelas Verdade

Seja {\mathcal {L}} uma linguagem que contenha as proposições P\,\!,Q\,\! e R\,\!.

O que podemos dizer sobre a proposição P\,\! ? Para começar, segundo oprincípio de bivalência, ela é ou verdadeira ou falsa. Istorepresentamos assim:

*P*VF

Agora, o que podemos dizer sobre as proposições P\,\! e Q\,\! ? Oras, ouambas são verdadeiras, ou a primeira é verdadeira e a segunda é falsa,ou a primeira é falsa e a segunda é verdadeira, ou ambas são falsas.Isto representamos assim:

*P* *Q*V VV FF VF F

Como você já deve ter reparado, uma tabela para P\,\!, Q\,\! e R\,\! éassim:

*P* *Q* *R*V V VV V FV F VV F FF V VF V FF F VF F F

Cada linha da tabela (fora a primeira que contém as fórmulas) representauma *valoração<http://pt.wikipedia.org/w/index.php?title=Valora%C3%A7%C3%A3o&action=edit&redli

nk=1>*.

Agora, o que dizer sobre fórmulas moleculares, tais como \neg P\,\!,Q\lor R\,\! ou \left(Q\land R\right)\to \left(P\leftrightarrowQ\right) ? Para estas, podemos estabelecer os valores que elas recebemem vista do valor de cada fórmula atômica que as compõe. Faremos istopor meio das *tabelas de verdade<http://pt.wikipedia.org/wiki/Tabela_verdade>*.

Os primeiros passos para construir uma tabela de verdade consistem em:

1�) Uma linha em que estão contidas todas as sub-fórmulas de uma fórmulae a própria fórmula. Por exemplo, a fórmula \neg \left(\left(P\landQ\right)\to R\right) tem o seguinte conjunto de sub-fórmulas:{\left(P\land Q\right)\to R , P\land Q , P\!\, , Q\!\, , R\!\,}

2�) l\!\, linhas em que estão todos os possíveis valores que asproposições atômicas podem receber e os valores recebidos pelas fórmulasmoleculares a partir dos valores destes átomos.

O número de linhas é l=n^{t}\!\, , sendo n\!\, o número de valores que osistema permite (sempre 2 no caso do CPC) e t\!\, o número de átomos quea fórmula contém. Assim, se uma fórmula contém 2 átomos, o número delinhas que expressam a permutações entre estes será 4: um caso de ambosserem verdadeiros (V V), dois casos de apenas um dos átomos serverdadeiro (V F , F V) e um caso no qual ambos serem falsos (F F). Se afórmula contiver 3 átomos, o número de linhas que expressam apermutações entre estes será 8: um caso de todos os átomos seremverdadeiros (V V V), três casos de apenas dois átomos serem verdadeiros(V V F , V F V , F V V), três casos de apenas um dos átomos serverdadeiro (V F F , F V F , F F V) e um caso no qual todos átomos sãofalsos (F F F).

Então, para a fórmula \neg \left(\left(P\land Q\right)\to R\right), temos:

*P* *Q* *R* *P∧Q* *(P∧Q) → R* *¬((P∧Q)→ R)*V V VV V FV F VV F FF V VF V FF F VF F F

Para completar esta tabela precisamos definir os operadores lógicos. Aofazê-lo, vamos aproveitar para explicar como interpretá-los.

Negação

A negação tem o valor inverso da fórmula negada. A saber:

*P* *¬ P*V FF V

* *Interpretações*: "Não P\!\,", "Não é o caso de P\!\,", "A proposição 'P\!\,' é falsa".

Assim, em uma linguagem {\mathcal {L}}\!\, na qual P\!\, significa"/Sócrates é mortal/", \neg P\!\, pode ser interpretada como "/Sócratesnão é mortal/", e, se o primeiro é verdadeiro, o segundo é falso; e se oprimeiro é falso, o segundo é verdadeiro.

Interpretar a negação por meio de antônimos também é uma alternativa,mas deve-se ter cautela, pois nem sempre é aplicável em todos os casos.No exemplo acima a interpretação por meio de antônimos é perfeitamenteaplicável, ou seja, se P\!\, significa "/Sócrates é mortal/", \neg P\!\,pode ser interpretada como "/Sócrates é imortal/". Por outro lado, emuma linguagem {\mathcal {L}}\!\, na qual Q\!\, significa "/João é bomjogador/", a proposição "/João é mau jogador/" não é a melhorinterpretação para \neg Q\!\, (João poderia ser apenas um jogador mediano).

Pode-se adicionar indefinidamente o operador de negação:

*P* *¬ P* *¬¬ P* *¬¬¬ P*V F V FF V F V

“\neg \neg P\,\!” significa “‘\neg P\,\!’ é falsa”.

“\neg \neg \neg P\,\!” significa “‘\neg \neg P\,\!’ é falsa”.

E assim por diante.

Repare que \neg \neg P\,\! é equivalente a P\,\!, assim como \neg \neg\neg P\,\! é equivalente a \neg P\,\!.

A negação múltipla traz alguns problemas de interpretação. Interpretandomais uma vez P\,\! por "/Sócrates é mortal/", podemos perfeitamenteinterpretar \neg \neg P\,\! de diversar formas: "/Não é o caso de queSócrates não é mortal/", "/Não é o caso de que Sócrates é imortal/", "/Éfalso que Sócrates não é mortal/", "/É falso que Sócrates é imortal/"etc. Contudo, nem sempre na língua portuguesa a dupla negação de umaproposição equivale à afirmação desta. Muitas vezes a dupla negação éapenas uma ênfase na negação. Exemplos: "/Não veio ninguém/", "Não fiznada hoje" etc.

Conjunção

A conjunção entre duas fórmulas só é verdadeira quando ambas são verdadeiras. A saber:

*P* *Q* *P∧Q*V V VV F FF V FF F F

* *Interpretação*: "P\land Q\!\," pode ser interpretada como "P\!\, e Q\!\,", "Tanto P\!\, quanto Q\!\,", "Ambas proposições 'P\!\,' e 'Q\!\,' são verdadeiras" etc.

Assim, em uma linguagem {\mathcal {L}}\!\, na qual P\!\, significa "/Soucidadão brasileiro/" e Q\!\, significa "/Sou estudante de filosofia/",P\land Q\!\, pode ser interpretada como "/Sou cidadão brasileiro eestudante de filosofia/"; o que só é verdade se P\!\, é verdadeira eQ\!\, é verdadeira.

Repare que a conjunção é comutável, ou seja, P\land Q\,\! é equivalentea Q\land P\,\!, a saber:

*P* *Q* *P∧Q* *Q∧P*V V V VV F F FF V F FF F F F

A comutatividade da conjunção traz um problema para formalizarproposições da linguagem natural no Cálculo Proposicional Clássico, poisa ordem em que as orações aparecem pode sugerir uma sequência temporal.Por exemplo "/Isabela se casou e teve um filho/" é bem diferente de"/Isabela teve um filho e se casou/". Repare que o mesmo problema nãoacomete a proposição "/Isabela é casada e tem filhos/", que éequivalente a "/Isabela tem filhos e é casada/". Esta sentença é,portanto, perfeitamente formalizável no Cálculo Proposicional Clássicopor meio de uma conjunção.

Proposições que levam a palavra "/mas/" também podem ser formalizadaspela conjunção. Por exemplo, em uma linguagem {\mathcal {L}}\!\, na qualR\!\, significa "/João foi atropelado/" e D\!\, significa "/Joãosobreviveu ao atropelamento/", as sentenças "/João foi atropelado esobreviveu/" e "/João foi atropelado, mas sobreviveu/" podem ambas serformalizadas assim: R\land D\,\!

Afinal, ambas as proposições afirmam os mesmos eventos na mesmasequência: o atropelamento e a sobrevivência de João. A única diferençaentre ambas é que aquela que leva "mas" expressa que uma expectativasubjetiva não foi satisfeita o que não importa para a lógica clássica.

Disjunção

A disjunção entre duas fórmulas só é verdadeira quando ao menos uma delas é verdadeira. A saber:

*P* *Q* *P∨Q*V V VV F VF V VF F F

Repare que a disjunção também é comutativa:

*P* *Q* *P∨Q* *Q∨P*V V V VV F V VF V V VF F F F

* *Interpretação*: "P\lor Q\!\," pode ser interpretada como "P\!\, ou Q\!\,", "Entre as proposições P\!\, e Q\!\,, ao menos uma é verdadeira".

Assim, se P\!\, significa "/Fulano estuda filosofia/" e Q\!\, significa"/Fulano estuda matemática/", P\lor Q\!\, pode ser interpretada como"/Fulano estuda filosofia ou matemática/"; o que só é falso se nem P\!\,nem Q\!\, forem verdadeiras.

Com a disjunção é preciso tomar muito cuidado tanto na interpretação defórmulas quanto na formalização de proposições, pois na linguagemnatural muitas vezes os disjuntos são excludentes. Por exemplo: "/Umamoeda ao ser lançada resulta em cara *ou* coroa/", "/Nestas férias euvou viajar *ou* ficar em casa/".

Para estes casos usamos a *disjunção exclusiva* ou a *bi-implicação*combinada com a *negação*, como veremos mais adiante.

Implicação ou Condicional

A implicação, ou condicional (SE-ENTÃO), entre duas fórmulas só é falsa se a da esquerda (antecedente) for verdadeira e da direita (consequente) for falsa. A saber:

*P* *Q* *P→Q*V V VV F FF V VF F V

Repare que a implicação *não* é comutativa:

*P* *Q* *P→Q* *Q→P*V V V VV F F VF V V FF F V V

* *Interpretação*: "P\to Q\!\," pode ser interpretada como "/Se P\!\,, então Q\!\,/", "/P\!\, implica Q\!\,/", "/Se a proposição ' P\!\, ' é verdade, então a proposição ' Q\!\, ' também é verdade/", "A partir de 'P\!\,' inferimos 'Q\!\,' /", "P\!\, satisfaz Q\!\,", "P\!\, é condição suficiente de Q\!\,"./

Assim, se, em uma linguagem {\mathcal {L}} , P\!\, significa "/O botãovermelho foi apertado/" e Q\!\, significa "/O lugar inteiro explode/",P\to Q\!\, pode ser interpretada como "/Se o botão vermelho foiapertado, então o lugar inteiro explode/", mas se o botão vermelho forapertado (verdade de P\!\,) e o lugar inteiro não explodir, esteresultado é falso (falsidade de Q\!\,):

A interpretação da implicação é uma das mais complicadas. Talvez vocêtenha estranhado que a implicação seja verdadeira quando o antecedente éfalso. Ou ainda, você poderia objetar "mas e se o botão for apertado, olugar explodir, mas uma coisa não tiver nada a ver com a outra?".

Basicamente, o que se deve observar é que "/O botão vermelho serapertado/" é condição suficiente para se deduzir que "/O lugar inteiroexplodiu/", isto é, quando o botão é apertado, o lugar deve explodir. Seo botão for apertado e o lugar não explodir, algo está errado, ou seja,P\!\, não implica Q\!\, ( P\to Q\!\, é falso).

Quando temos na linguagem natural uma proposição que afirma que a partirde um evento (P), o outro (Q) segue inexoravelmente e de fato istoacontece (por exemplo: "/Se você sair na chuva sem guarda-chuva ou capade chuva, então você vai se molhar/" ou "/Se todo número par é divisívelpor 2, então nenhum número par maior que 2 é primo/"), podemosseguramente formalizar estas proposições por meio da implicação.

No caso contrário, o evento ou proposição anterior (P), de fato, não écondição suficiente, então interpretar em linguagem natural pode sermais difícil, pois facilmente se confunde com a bi-implicação. Deve-seter em mente que P deve ser condição suficiente para que se tenha Q, masnão se pode afirmar nada sobre P a partir de Q. Se P é verdadeiro (V),então Q tem de ser verdadeiro! Ora, se com P verdadeiro (V), Q não forverdadeiro (F), então a implicação é falsa (F)! Por outro lado, no casode P ser falsa (F), então não há a condição suficiente, mas podemexistir outras "causas" para que Q seja verdadeira (V) ou falsa (F). Porisso, se P é falsa (F), então "tanto faz" se Q é verdadeira ou falsa,que a condição de suficiência de P não é invalidada.

Fica mais fácil lembrar a regra assim: só é falsa se P acontecer e Q não.

Bi-implicação ou Equivalência

A bi-implicação, ou equivalência (SE, SOMENTE SE), entre duas fórmulas é verdadeira quando ambas são verdadeiras ou ambas são falsas.

*P* *Q* *P↔Q*V V VV F FF V FF F V

Repare que a bi-implicação é comutativa:

*P* *Q* *P↔Q* *Q↔P*V V V VV F F FF V F FF F V V

* *Interpretação*: "P\leftrightarrow Q" pode ser interpretada como "/P\!\, se e somente se Q\!\,/", "/P\!\, é equivalente a Q\!\,/", "/P\!\, e Q\!\, possuem o mesmo valor de verdade/".

Assim, se P\!\, significa "/O número natural é divisível por cinco/" eQ\!\, significa "'O último algarismo do número natural é zero oucinco/", P\leftrightarrow Q pode ser interpretada como "/O númeronatural é divisível por 5 se, e somente se, o seu último algarismo ézero ou cinco/". Basta que uma das proposições ou condições seja falsapara que o enunciado se torne falsa./

Na linguagem natural o problema está em confundir uma condiçãonecessária como sendo a única possibilidade para se chegar ao resultadoverdadeiro. Por exemplo, alguém pode estar chorando por tristeza, mastambém porque está a descascar cebola. Para que haja a equivalência oraciocínio deve ser verdadeiro nos dois sentidos.

Exemplo 1. Sistema axiomático simples

Seja {\mathcal {L}}_{1}=(\mathrm{A} ,\ \Omega ,\ \mathrm{Z} ,\\mathrm{I} ), onde \mathrm{A} ,\ \Omega ,\ \mathrm{Z} ,\ \mathrm{I} sãodefinidos como:

* O conjunto \mathrm{A} \! é um conjunto finito de símbolos que é

grande o suficiente para suprir as necessidades de uma dada discussão, por exemplo:

\mathrm{A} =\{p,q,r,s,t,u\}\,.

Entre os 3 conectivos para conjunção, disjunção e implicação (∧, ∨, e→), um pode ser tomado como primitivo e os outros dois podem serdefinidos em termos deste e da negação (¬). Certamente, todos osconectivos lógicos podem ser definidos em termos de um único operador<http://pt.wikipedia.org/wiki/Completude_funcional>. O bicondicional (↔)pode, é claro, ser definido em termos de conjunção e implicação com a ↔b sendo definido como (a → b) ∧ (b → a).

Adotando negação e implicação como as duas operações primitivas de umcálculo proposicional é equivalente a ter o conjunto omega \Omega=\Omega _{1}\cup \Omega _{2} particionado em:

\Omega _{1}=\{\lnot \}\,.

\Omega _{2}=\{\rightarrow \}\,.

Um sistema axiomático descoberto por Jan Tukasiewicz formula um /cálculoproposicional/ na linguagem a seguir. Os axiomas em \mathrm{I} \! sãotodos instâncias de substituição de:

* p\to (q\to p)

* (p\to (q\to r))\to ((p\to q)\to (p\to r))

* (\neg p\to \neg q)\to (q\to p)

A regra de inferência em \mathrm{Z} \! é modus ponens<http://pt.wikipedia.org/wiki/Modus_ponens> (isto é, de /p/ e (/p/ →/q/), infere-se /q/). Então /a/ ∨ /b/ é definido como ¬/a/ → /b/, /a/ ∧/b/ é definido como ¬(/a/ → ¬/b/).

Exemplo 2. Sistema de Dedução Natural

Seja {\mathcal {L}}_{2}={\mathcal {L}}\ (\mathrm{A} ,\ \Omega ,\\mathrm{Z} ,\ \mathrm{I} ), onde \mathrm{A} ,\ \Omega ,\ \mathrm{Z} ,\\mathrm{I} são definidos a seguir:

* O conjunto \mathrm{A} \! é um conjunto finito de símbolos suficiente para suprir a necessidade de uma dada discussão, por exemplo:

\mathrm{A} =\{p,q,r,s,t,u\}\,.

* O conjunto \Omega =\Omega _{1}\cup \Omega _{2} consiste em:

\Omega _{1}=\{\lnot \}

\Omega _{2}=\{\land ,\lor ,\rightarrow ,\leftrightarrow \}.

No exemplo de cálculo proposicional a seguir, as regras de transformaçãodevem ser interpretadas como as regras de inferência do chamado /sistemade dedução natural<http://pt.wikipedia.org/wiki/Dedu%C3%A7%C3%A3o_natural>/. O sistemaparticular apresentado aqui não possui pontos iniciais, o que significaque sua interpretação para aplicações lógicas deriva seus teoremas

<http://pt.wikipedia.org/wiki/Teorema> a partir de um conjunto deaxiomas vazio.

* O conjunto de pontos iniciais é vazio, ou seja, \mathrm{I} =\varnothing \,. * O conjunto de regras de transformação, \mathrm{Z} ,\!, é descrito a seguir:

Nosso cálculo proposicional possui dez regras de inferência. Essasregras nos permitem derivar outras fórmulas verdadeiras a partir de umconjunto de fórmulas assumidas como verdadeiras. As primeiras noveregras dizem simplesmente que podemos inferir certas fbfs de outrasfbfs. A última regra, no entanto, usa o raciocínio hipotético no sentidode que, na premissa da regra, assumimos temporariamente uma hipótese(não demonstrada) como parte do conjunto de fórmulas inferidas a fim dedescobrir se podemos inferir uma certa outra fórmula. Como as noveprimeiras regras não fazem isso, são normalmente descritas como regras/não hipotéticas/, e a última é dita uma regra /hipotética/.

Redução ao absurdo<http://pt.wikipedia.org/wiki/Redu%C3%A7%C3%A3o_ao_absurdo> (introduçãoda negação) De (/p/→/q/), (/p/→ ¬/q/), infere-se ¬/p/.Eliminação da dupla negação<http://pt.wikipedia.org/wiki/Elimina%C3%A7%C3%A3o_da_dupla_nega%C3%A7%C3%A3o> De ¬¬/p/, infere-se /p/.Introdução da conjunção<http://pt.wikipedia.org/wiki/Introdu%C3%A7%C3%A3o_da_conjun%C3%A7%C3%A3o> De /p/ e /q/, infere-se (/p/ ∧ /q/).Eliminação da conjunção<http://pt.wikipedia.org/wiki/Elimina%C3%A7%C3%A3o_da_conjun%C3%A7%C3%A3o> De (/p/ ∧ /q/), infere-se /p/ De (/p/ ∧ /q/), infere-se /q/.Introdução da disjunção<http://pt.wikipedia.org/wiki/Introdu%C3%A7%C3%A3o_da_disjun%C3%A7%C3%A3o> De /p/, infere-se (/p/ ∨ /q/) De /p/, infere-se (/q/ ∨ /p/).Eliminação da disjunção<http://pt.wikipedia.org/wiki/Elimina%C3%A7%C3%A3o_da_disjun%C3%A7%C3%A3o> De (/p/ ∨ /q/), (/p/ → /r/), (/q/ → /r/), infere-se /r/.Introdução do Bicondicional<http://pt.wikipedia.org/wiki/Introdu%C3%A7%C3%A3o_do_Bicondicional> De (/p/ → /q/), (/q/ → /p/), infere-se (/p/ ↔ /q/).Eliminação do Bicondicional<http://pt.wikipedia.org/wiki/Elimina%C3%A7%C3%A3o_do_Bicondicional> De (/p/ ↔ /q/), infere-se (/p/ → /q/); De (/p/ ↔ /q/), infere-se (/q/ → /p/).Modus ponens <http://pt.wikipedia.org/wiki/Modus_ponens> (eliminação docondicional) De /p/, (/p/ → /q/), infere-se /q/.Demonstração Condicional<http://pt.wikipedia.org/w/index.php?title=Demonstra%C3%A7%C3%A3o_Condicional&action=edit&redlink=1>(introdução do condicional) Se /p/ for aceito como prova de /q/, infere-se (/p/ → /q/).

Formas de Argumentos Básicos e DerivadosNome Sequência DescriçãoModus Ponens ((/p/ → /q/) ∧ /p/) → /q/ Se /p/ então /q/; /p/;consequentemente /q/

Modus Tollens ((/p/ → /q/) ∧ ¬/q/) → ¬p Se /p/ então /q/; não /q/;consequentemente não /p/Silogismo Hipotético ((/p/ → /q/) ∧ (/q/ → /r/)) → (/p/ → /r/) Se /p/então /q/; se /q/ então /r/; consequentemente, se /p/ então /r/Silogismo Disjuntivo ((/p/ ∨ /q/) ∧ ¬/p/) → /q/ /p/ ou /q/; não /p/;consequentemente, /q/Dilema Construtivo ((/p/ → /q/) ∧ (/r/ → /s/) ∧ (/p/ ∨ /r/)) → (/q/ ∨/s/) Se /p/ então /q/; e se /r/ então /s/; mas /p/ ou /r/;consequentemente /q/ ou /s/Dilema Destrutivo ((/p/ → /q/) ∧ (/r/ → /s/) ∧ (¬/q/ ∨ ¬/s/)) → (¬/p/ ∨¬/r/) Se /p/ então /q/; e se /r/ então /s/; mas não /q/ ou não /s/;consequentemente não /p/ ou não /r/Simplificação (/p/ ∧ /q/) → /p/ /p/ e /q/ são verdadeiros;consequentemente /p/ é verdadeiro.Conjunção /p/, /q/ → (/p/ ∧ /q/) /p/ e /q/ são verdadeirosseparadamente; consequentemente eles são verdadeiros conjuntamenteAdição /p/ → (/p/ ∨ /q/) /p/ é verdadeiro; consequentemente adisjunção (/p/ or /q/) é verdadeiraComposição ((/p/ → /q/) ∧ (/p/ → /r/)) → (/p/ → (/q/ ∧ /r/)) Se /p/então /q/; e se /p/ então /r/; consequentemente se /p/ é verdadeiroentão /q/ e /r/ são verdadeirosTeorema de De Morgan (1) ¬(/p/ ∧ /q/) → (¬/p/ ∨ ¬/q/) A negação de(/p/ e /q/) tem como consequência (não /p/ ou não /q/)Teorema de De Morgan (2) ¬(/p/ ∨ /q/) → (¬/p/ ∧ ¬/q/) A negação de(/p/ ou /q/) tem como consequência (não /p/ e não /q/)Commutação (1) (/p/ ∨ /q/) → (/q/ ∨ /p/) (/p/ ou /q/) tem comoconsequência (/q/ ou /p/)Commutação (2) (/p/ ∧ /q/) → (/q/ ∧ /p/) (/p/ e /q/) tem comoconsequência (/q/ e /p/)Associatividade (1) (/p/ ∨ (/q/ ∨ /r/)) → ((/p/ ∨ /q/) ∨ /r/) /p/ ou(/q/ ou /r/) tem como consequência (/p/ ou /q/) ou /r/Associatividade (2) (/p/ ∧ (/q/ ∧ /r/)) → ((/p/ ∧ /q/) ∧ /r/) /p/ e(/q/ e /r/) tem como consequência (/p/ e /q/) e /r/Distributividade (1) (/p/ ∧ (/q/ ∨ /r/)) → ((/p/ ∧ /q/) ∨ (/p/ ∧/r/)) /p/ e (/q/ ou /r/) tem como consequência (/p/ e /q/) ou (/p/ e /r/)Distributividade (2) (/p/ ∨ (/q/ ∧ /r/)) → ((/p/ ∨ /q/) ∧ (/p/ ∨/r/)) /p/ ou (/q/ e /r/) tem como consequência (/p/ ou /q/) e (/p/ ou /r/)Dupla Negação /p/ → ¬¬/p/ /p/ tem como consequência a negação de não /p/Transposição (/p/ → /q/) → (¬/q/ → ¬/p/) Se /p/ então /q/ tem comoconsequência se não /q/ então não /p/Implicação Material (/p/ → /q/) → (¬/p/ ∨ /q/) Se /p/ então /q/ temcomo consequência não /p/ ou /q/Equivalência Material (1) (/p/ ↔ /q/) → ((/p/ → /q/) ∧ (/q/ → /p/))(/p/ é equivalente a /q/) significa que, (se /p/ é verdadeiro então /q/é verdadeiro) e (se /q/ é verdadeiro então /p/ é verdadeiro)Equivalência Material (2) (/p/ ↔ /q/) → ((/p/ ∧ /q/) ∨ (¬/q/ ∧ ¬/p/))(/p/ é equivalente a /q/) significa que, (/p/ e /q/ são verdadeiros) ou(ambos /p/ e /q/ são falsos)Equivalência Material (3) (/p/ ↔ /q/) → ((/p/ ∨ ¬/q/) ∧ (/q/ ∨ ¬/p/))(/p/ é equivalente a /q/) significa que ambos (/p/ ou não /q/ éverdadeiro) e (não /p/ ou /q/ é verdadeiro)Exportação ((/p/ ∧ /q/) → /r/) → (/p/ → (/q/ → /r/)) De (se /p/ e /q/são verdadeiros então /r/ é verdadeiro) podemos demonstrar (se /q/ éverdadeiro então /r/ é verdadeiro, se /p/ é verdadeiro)Importação (/p/ → (/q/ → /r/)) → ((/p/ ∧ /q/) → /r/) De (se /p/ então(/q/ então /r/) é verdadeiro) podemos demonstrar que ((/p/ ∧ /q/) → /r/)é verdadeiroTautologia (1) /p/ → (/p/ ∨ /p/) /p/ é verdadeiro tem comoconsequência /p/ é verdadeiro ou /p/ é verdadeiroTautologia (2) /p/ → (/p/ ∧ /p/) /p/ é verdadeiro tem como

consequência /p/ é verdadeiro e /p/ é verdadeiroTertium non datur (Lei do Terceiro Excluído) → (/p/ ∨ ¬ /p/) /p/ ounão /p/ é verdadeiro

Em seguida, detalha-se a última regra, dita hipotética.

Regra de Demonstração Condicional (RDC)

Um dos principais usos de um cálculo proposicional, em aplicaçõeslógicas, é na determinação de relações de equivalência lógica entrefórmulas proposicionais. Essas relações são determinadas em termos dasregras de transformação disponíveis. Sequências de regras estabelecem oque chamamos "derivação" ou "demonstração".

Na discussão a seguir, uma demonstração é apresentada como uma sequênciade linhas enumeradas, em que cada linha consiste em uma única fórmula,seguida por uma /razão/ ou /justificativa/ para introduzir esta fórmula.Cada premissa do argumento, que é assumida como uma hipótese doargumento, é listada no começo da sequência e é justificada simplesmentecomo uma "premissa". A conclusão é listada na última linha. Umademonstração é completa se cada linha segue das anteriores pelaaplicação correta de uma regra de inferência.

Exemplo de demonstração condicional

* Para mostrar que /A/ → /A/. * Uma demonstração possível para isso, pode ser obtida da seguinte forma:

Exemplo de provaNúmero Fórmula Razão1 /A/ premissa2 /A/ ] /A/ Resumo de (1)3 ] /A/ → /A/ De (2) pela demonstração condicional

Interprete /A/ ] /A/ como "Assumindo /A/, infere-se /A/". Leia ] /A/ →/A/ como "Sem assumir nada, infira que /A/ implica /A/," ou "É umatautologia que /A/ implica /A/," ou "É sempre verdade que /A/ implica /A/."

Correção e completude das regras

As propriedades cruciais desse conjunto de regras são que elas são/corretas/ e /completas/. Informalmente isso quer dizer que as regrassão corretas e que não é preciso acrescentar outras regras. Faremos umaabordagem mais formal disto logo abaixo.

Definimos uma /atribuição de verdade<http://pt.wikipedia.org/wiki/Fun%C3%A7%C3%A3o_de_verdade>/ como umafunção matemática que mapeia variáveis proposicionais para os valores*verdadeiro* ou *falso*. Informalmente estas atribuições podem serentendidas como uma descrição de um possível estado das coisas no qualcertas asserções são verdadeiras e outras não são. A semântica dasfórmulas pode ser formalizada pela definição de quais são os "estadosdas coisas" nos quais elas são consideradas verdadeiras, que é o que éfeito pela definição a seguir.

Definimos quando uma atribuição /v/ satisfaz uma certa fórmula bemformada com as seguintes regras:

* /v/ satisfaz a variável proposicional /p/ se e somente se /v/(/p/) = *verdadeiro* * /v/ satisfaz ¬φ se e somente se /v/ não satisfaz φ * /v/ satisfaz (φ ∧ ψ) se e somente se /v/ satisfaz ambos φ e ψ * /v/ satisfaz (φ ∨ ψ) se e somente se /v/ satisfaz pelo menos φ ou ψ * /v/ satisfaz (φ → ψ) se e somente se não for o caso em que /v/ satisfaz φ mas não ψ * /v/ satisfaz (φ ↔ ψ) se e somente se /v/ satisfaz tanto φ e ψ ou não satisfaz nenhum deles

Com esta definição podemos formalizar agora o que quer dizer uma fórmulaφ ser implicada por certo conjunto /\Gamma \!/ de fórmulas.Informalmente, isto é o caso se em todo estado possível das coisas noqual vale o conjunto de fórmulas \Gamma \! vale também a fórmula φ. Issoleva para a seguinte definição formal: Nós dizemos que um conjunto/\Gamma \!/ de fbfs /semanticamente ligadas/ implicam que uma certa fbfφ se todas as atribuições verdadeiras que satisfazem as fórmulas /\Gamma\!/ também satisfazem φ.

Finalmente nós definimos uma "relação de consequência sintática" tal queφ é consequência sintática de /\Gamma \!/ se e somente se nós podemosderivar com as regras de inferência que foram apresentadas acima em umnúmero finito de passos. Isso nos permite formular exatamente o que querdizer para um conjunto de regras de inferência ser correto e completo:

*Correção lógica<http://pt.wikipedia.org/w/index.php?title=Corre%C3%A7%C3%A3o_l%C3%B3gica&action=edit&redlink=1>* Se o conjunto de fbfs /\Gamma \!/ tem como consequência sintática a fbf φ, então /\Gamma \!/ tem como consequência semântica φ.

*Completude lógica <http://pt.wikipedia.org/wiki/Completude_l%C3%B3gica>* Se o conjunto de fbfs /\Gamma \!/ tem como consequência semântica a fbf φ então /\Gamma \!/ tem como consequência sintática φ.

Para o conjunto de regras acimas este é, então, o caso.

Um cálculo alternativo

É possível definir outra versão do cálculo proposicional, que define amaior parte da sintaxe dos operadores lógicos em termos de axiomas e usasomente uma regra de inferência.

Axiomas

Seja φ, χ e ψ símbolos para fórmulas bem formadas. (As fbfs em si nãocontêm nenhuma letra grega, mas somente letras romanas maiúsculas,operadores conectivos, e parênteses.) Então, os axiomas são os seguintes:

AxiomasNome Esquema Axiomático DescriçãoENTÃO-1 φ → (χ → φ) Adiciona a hipótese χ, introdução da implicaçãoENTÃO-2 (φ → (χ → ψ)) → ((φ → χ) → (φ → ψ)) Distribui a hipótese φsobre a implicaçãoE-1 φ ∧ χ → φ Eliminação da conjunçãoE-2 φ ∧ χ → χ Eliminação da conjunção 2E-3 φ → (χ → (φ ∧ χ)) Introdução da conjunçãoOU-1 φ → φ ∨ χ Introdução da disjunção 2

OU-2 χ → φ ∨ χ Introdução da disjunçãoOU-3 (φ → ψ) → ((χ → ψ) → (φ ∨ χ → ψ)) Eliminação da disjunçãoNÃO-1 (φ → χ) → ((φ → ¬χ) → ¬ φ) Introdução da negaçãoNÃO-2 φ → (¬φ → χ) Eliminação da negaçãoNÃO-3 φ ∨ ¬φ Lei do terceiro excluído, lógica clássicaSSE-1 (φ ↔ χ) → (φ → χ) Eliminação da equivalênciaSSE-2 (φ ↔ χ) → (χ → φ) Eliminação da equivalência 2SSE-3 (φ → χ) → ((χ → φ) → (φ ↔ χ)) Introdução da equivalência

O axioma ENTÃO-2 pode ser considerado como sendo uma "propriedadedistributiva da implicação com relação à implicação."Os axiomas E-1 e E-2 correspondem à "eliminação da conjunção". A relaçãoentre E-1 e E-2 reflete a comutatividade do operador da conjunção.O axioma E-3 corresponde à "introdução da conjunção."Os axiomas OU-1 e OU-2 correspondem à "introdução da disjunção." Arelação entre OU-1 e OU-2 reflete a comutatividade do operador da disjunção.O axioma NÃO-1 corresponde à "redução ao absurdo."O axioma NÃO-2 diz que "tudo pode ser deduzido a partir da contradição."O axioma NÃO-3 é chamado "tertium non datur<http://pt.wikipedia.org/wiki/Lei_do_terceiro_exclu%C3%ADdo>" (Latim<http://pt.wikipedia.org/wiki/Latim>: "não há uma terceira opção") ereflete a valoração semântica da fórmula proposicional: uma fórmula podeter um valor de verdade verdadeiro ou falso. Não há um terceiro valor deverdade, pelo menos não na lógica clássica. Lógica intuicionista<http://pt.wikipedia.org/wiki/L%C3%B3gica_intuicionista> não aceita oaxioma NÃO-3.

Regra de inferência

A regra de inferência é modus ponens<http://pt.wikipedia.org/wiki/Modus_ponens>:

* \phi ,\ \phi \rightarrow \chi \vdash \chi .

Meta-regra de inferência

Seja uma demonstração representada por uma sequência, com hipóteses àesquerda do símbolo de consequência formal \vdash e as conclusões àdireita do \vdash . Então o teorema da dedução<http://pt.wikipedia.org/w/index.php?title=Teorema_da_dedu%C3%A7%C3%A3o&action=edit&redlink=1>pode ser definido como:

/Se a sequência/

\phi _{1},\ \phi _{2},\ ...,\ \phi _{n},\ \chi \vdash \psi

/foi demonstrada, então também é possível demonstrar a sequência/

\phi _{1},\ \phi _{2},\ ...,\ \phi _{n}\vdash \chi \rightarrow \psi .

Esse teorema de dedução (TD) não é formulado por meio da lógicaproposicional: não é um teorema /da/ lógica proposicional, mas umteorema /sobre/ a lógica proposicional. Nesse sentido, é ummeta-teorema, comparável aos teoremas sobre a correção ou completude dalógica proposicional.

Por outro lado, o TD é tão útil para simplificar o processo dedemonstração sintática que pode ser considerado e usado como uma outraregra de inferência qualquer acompanhando modus ponens. Neste sentido, oTD corresponde à regra de /demonstração condicional/ que é parte daprimeira versão do cálculo proposicional introduzida neste verbete.

A recíproca <http://pt.wikipedia.org/wiki/Rec%C3%ADproca> do TD também éválida:

/Se a sequência/

\phi _{1},\ \phi _{2},\ ...,\ \phi _{n}\vdash \chi \rightarrow \psi

/foi demonstrada, então também é possível demonstrar a sequência/

\phi _{1},\ \phi _{2},\ ...,\ \phi _{n},\ \chi \vdash \psi

De fato, a validade da recíproca do TD é quase trivial comparada àvalidade do TD:

/Se/

\phi _{1},\ ...,\ \phi _{n}\vdash \chi \rightarrow \psi

/então/

1: \phi _{1},\ ...,\ \phi _{n},\ \chi \vdash \chi \rightarrow \psi 2: \phi _{1},\ ...,\ \phi _{n},\ \chi \vdash \chi

/e de (1) e (2) se pode deduzir/

3: \phi _{1},\ ...,\ \phi _{n},\ \chi \vdash \psi

/por meio do modus ponens, Q.E.D./

A validade do TD tem aplicações poderosas: pode ser usada para converterum axioma numa regra de inferência. Por exemplo, o axioma E-1,

\vdash \phi \wedge \chi \rightarrow \phi

pode ser transformado por meio da recíproca do teorema da dedução naregra de inferência

\phi \wedge \chi \vdash \phi

que é a eliminação da conjunção<http://pt.wikipedia.org/wiki/Elimina%C3%A7%C3%A3o_da_conjun%C3%A7%C3%A3o>,uma das dez regras de inferência usadas na primeira versão (no presenteverbete) do cálculo proposicional.

Exemplo de uma prova

A seguir, há um exemplo de uma demonstração (sintática), envolvendoapenas axiomas ENTÃO-1 e ENTÃO-2:*Provar:* /A/ → /A/ (Reflexibilidade da implicação).*Prova:*

1. (/A/ → ((/B/ → /A/) → /A/)) → ((/A/ → (/B/ → /A/)) → (/A/ → /A/))

Axioma ENTÃO-2 com φ = /A/, χ = /B/ → /A/, ψ = /A/

2. /A/ → ((/B/ → /A/) → /A/)

Axioma ENTÃO-1 com φ = /A/, χ = /B/ → /A/

3. (/A/ → (/B/ → /A/)) → (/A/ → /A/)

De (1) e (2) por modus ponens.

4. /A/ → (/B/ → /A/)

Axioma ENTÃO-1 com φ = /A/, χ = /B/

5. /A/ → /A/

De (3) e (4) por modus ponens.

Outros cálculos lógicos

Lógica proposicional é praticamente o tipo mais simples de cálculológico em qualquer uso. (O cálculo silogístico Aristotélico, que éamplamente utilizado na lógica moderna, é sob /alguns/ pontos de vistamais simples — mas em outros mais complexo — do que a lógicaproposicional.) A lógica proposicional pode ser estendida de diversasformas.

A forma mais imediata de desenvolver um cálculo lógico mais complexo épela introdução de regras que são sensíveis aos detalhes estruturais dassentenças empregadas. Quando as "sentenças atômicas" da lógicaproposicional são quebradas em termos<http://pt.wikipedia.org/w/index.php?title=Termos_singulares&action=edit&redlink=1>,variáveis <http://pt.wikipedia.org/wiki/Vari%C3%A1veis>, predicados<http://pt.wikipedia.org/w/index.php?title=Predicados_%28l%C3%B3gica%29&action=edit&redlink=1>,e quantificadores <http://pt.wikipedia.org/wiki/Quantificador>, elas dãoorigem à lógica de primeira ordem<http://pt.wikipedia.org/wiki/L%C3%B3gica_de_primeira_ordem>, ou lógicade predicados de primeira ordem, que mantém todas as regras da lógicaproposicional e adiciona algumas novas. Por exemplo, de "Todos oscachorros são mamíferos" podemos inferir "Se Totó é um cachorro entãoTotó é um mamífero".

Com as ferramentas da lógica de primeira ordem é possível formularvárias teorias, tanto com axiomas explícitos como através de regras deinferência, teorias que podem elas próprias ser tratadas como cálculoslógicos. A aritmética <http://pt.wikipedia.org/wiki/Aritm%C3%A9tica> é omelhor exemplo disso; outros exemplos incluem a teoria dos conjuntos<http://pt.wikipedia.org/wiki/Teoria_dos_conjuntos> e a mereologia<http://pt.wikipedia.org/w/index.php?title=Mereologia&action=edit&redlink=1>.

As lógicas modais <http://pt.wikipedia.org/wiki/L%C3%B3gica_modal>também oferecem uma variedade de inferências que não podem sercapturadas pelo cálculo proposicional. Por exemplo, de "Necessariamente/p/" podemos inferir que /p/. De /p/ podemos inferir "É possível que /p/".

As lógicas polivalentes<http://pt.wikipedia.org/w/index.php?title=L%C3%B3gica_polivalente&action=edit&r

edlink=1>são aquelas lógicas que permitem outros valores além de /verdadeiro/ e/falso/ são permitidos. Por exemplo, /nenhum/ e /ambos/ são "valoresextras" padrões; a "lógica do contínuo" permite que cada sentença tenhaqualquer grau de verdade de um número infinito de graus entre/verdadeiro/ e /falso/.

Referências gerais

* Bedregal, Benjamín René Callejas <http://pt.wikipedia.org/w/index.php?title=Benjam%C3%ADn_Ren%C3%A9_Callejas_Bedregal&action=edit&redlink=1>, e Aciól�, Benedito Melo <http://pt.wikipedia.org/w/index.php?title=Benedito_Melo_Aci%C3%B3l�&action=edit&redlink=1> (2002), /Lógica para a Ciência da Computação/,Versão Preliminar, Natal, RN.

* GORSKY, Samir. /A semântica algébrica para a lógica modal e seu interesse filosófico <http://samirgorsk�.eu5.org/trabalhos/logicamodal.pdf>/. Dissertação de mestrado. IFCH-UNICAMP. 2008.

* /Lógica e Filosofia <http://samirgorsk�.eu5.org/>/ Site com muitas informações sobre lógica e filosofia tais como links para departamentos de filosofia do Brasil e de outros países, textos acadêmicos filosóficos e tópicos sobre história da filosofia.

Wikilivros <http://pt.wikipedia.org/wiki/Ficheiro:Wikibooks-logo.svg>O Wikilivros <http://pt.wikipedia.org/wiki/Wikilivros> tem um livrochamado /*Lógica <http://pt.wikibooks.org/wiki/Special:Search/L%C3%B3gica>*/

Ver também

Níveis lógicos

* Lógica de primeira ordem <http://pt.wikipedia.org/wiki/L%C3%B3gica_de_primeira_ordem> * Lógica de segunda ordem <http://pt.wikipedia.org/wiki/L%C3%B3gica_de_segunda_ordem> * Lógica de ordem superior <http://pt.wikipedia.org/wiki/L%C3%B3gica_de_ordem_superior>

Blocos básicos

* XOR <http://pt.wikipedia.org/wiki/XOR> * Conjunção lógica <http://pt.wikipedia.org/wiki/Conjun%C3%A7%C3%A3o_l%C3%B3gica> * Disjunção lógica <http://pt.wikipedia.org/wiki/Disjun%C3%A7%C3%A3o_l%C3%B3gica>

* Implicação <http://pt.wikipedia.org/wiki/Implica%C3%A7%C3%A3o> * NAND <http://pt.wikipedia.org/wiki/NAND> * Negação <http://pt.wikipedia.org/wiki/Nega%C3%A7%C3%A3o>

Tópicos relacionados

* Álgebra booleana <http://pt.wikipedia.org/wiki/%C3%81lgebra_booleana> * Anfeque <http://pt.wikipedia.org/wiki/Anfeque> * Axioma <http://pt.wikipedia.org/wiki/Axioma> * Cálculo proposicional implicacional <http://pt.wikipedia.org/wiki/C%C3%A1lculo_proposicional_implicacional> * Completude funcional <http://pt.wikipedia.org/wiki/Completude_funcional>

* Dedução natural <http://pt.wikipedia.org/wiki/Dedu%C3%A7%C3%A3o_natural> * Equivalência lógica <http://pt.wikipedia.org/wiki/Equival%C3%AAncia_l%C3%B3gica> * Forma normal conjuntiva <http://pt.wikipedia.org/wiki/Forma_normal_conjuntiva> * Forma normal disjuntiva <http://pt.wikipedia.org/wiki/Forma_normal_disjuntiva> * Forma normal implicativa <http://pt.wikipedia.org/w/index.php?title=Forma_Normal_Implicativa&action=edit&redlink=1> * Fórmula atômica <http://pt.wikipedia.org/wiki/F%C3%B3rmula_at%C3%B4mica>

* História da lógica <http://pt.wikipedia.org/wiki/Hist%C3%B3ria_da_l%C3%B3gica> * Lógica aristotélica <http://pt.wikipedia.org/wiki/L%C3%B3gica_aristot%C3%A9lica> * Operação <http://pt.wikipedia.org/wiki/Opera%C3%A7%C3%A3o> * Princípio da resolução <http://pt.wikipedia.org/wiki/Princ%C3%ADpio_da_resolu%C3%A7%C3%A3o> * Tabela verdade <http://pt.wikipedia.org/wiki/Tabela_verdade>

Obtida de"http://pt.wikipedia.org/w/index.php?title=Lógica_proposicional&oldid=37651709<http://pt.wikipedia.org/w/index.php?title=L%C3%B3gica_proposicional&oldid=37651709>"

Categorias <http://pt.wikipedia.org/wiki/Especial:Categorias>:

* Lógica <http://pt.wikipedia.org/wiki/Categoria:L%C3%B3gica> * Lógica matemática <http://pt.wikipedia.org/wiki/Categoria:L%C3%B3gica_matem%C3%A1tica>

Categoria oculta:

* !Páginas a reciclar desde Fevereiro de 2010 <http://pt.wikipedia.org/wiki/Categoria:%21P%C3%A1ginas_a_reciclar_desde_Fevereiro_de_2010>

Menu de navegação

Ferramentas pessoais

* Criar conta

<http://pt.wikipedia.org/w/index.php?title=Especial:Entrar&returnto=L%C3%B3gica+proposicional&returntoquer�=printable%3D�es&t�pe=signup> * Entrar <http://pt.wikipedia.org/w/index.php?title=Especial:Entrar&returnto=L%C3%B3gica+proposicional&returntoquer�=printable%3D�es>

Espaços nominais

* Artigo <http://pt.wikipedia.org/wiki/L%C3%B3gica_proposicional> * Discussão <http://pt.wikipedia.org/wiki/Discuss%C3%A3o:L%C3%B3gica_proposicional>

Variantes<#>

Vistas

* Ler <http://pt.wikipedia.org/wiki/L%C3%B3gica_proposicional> * Editar <http://pt.wikipedia.org/w/index.php?title=L%C3%B3gica_proposicional&veaction=edit> * Editar código-fonte <http://pt.wikipedia.org/w/index.php?title=L%C3%B3gica_proposicional&action=edit> * Ver histórico <http://pt.wikipedia.org/w/index.php?title=L%C3%B3gica_proposicional&action=histor�>

Ações<#>

Busca

<http://pt.wikipedia.org/wiki/Wikip%C3%A9dia:P%C3%A1gina_principal>

Navegação

* Página principal <http://pt.wikipedia.org/wiki/Wikip%C3%A9dia:P%C3%A1gina_principal> * Conteúdo destacado <http://pt.wikipedia.org/wiki/Portal:Conte%C3%BAdo_destacado> * Eventos atuais <http://pt.wikipedia.org/wiki/Portal:Eventos_atuais> * Esplanada <http://pt.wikipedia.org/wiki/Wikip%C3%A9dia:Esplanada> * Página aleatória <http://pt.wikipedia.org/wiki/Especial:Aleat%C3%B3ria> * Portais <http://pt.wikipedia.org/wiki/Portal:%C3%8Dndice> * Informar um erro <#>

Colaboração <#>

* Boas-vindas <http://pt.wikipedia.org/wiki/Wikip%C3%A9dia:Boas-vindas> * Ajuda <http://pt.wikipedia.org/wiki/Ajuda:P%C3%A1gina_principal> * Página de testes <http://pt.wikipedia.org/wiki/Wikip%C3%A9dia:P%C3%A1gina_de_testes> * Portal comunitário <http://pt.wikipedia.org/wiki/Wikip%C3%A9dia:Portal_comunit%C3%A1rio>

* Mudanças recentes <http://pt.wikipedia.org/wiki/Especial:Mudan%C3%A7as_recentes> * Manutenção <http://pt.wikipedia.org/wiki/Wikip%C3%A9dia:Manuten%C3%A7%C3%A3o> * Criar página <http://pt.wikipedia.org/wiki/Ajuda:Guia_de_edi%C3%A7%C3%A3o/Como_come%C3%A7ar_uma_p%C3%A1gina> * Páginas novas <http://pt.wikipedia.org/wiki/Especial:P%C3%A1ginas_novas> * Contato <http://pt.wikipedia.org/wiki/Wikip%C3%A9dia:Contato> * Donativos <http://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=20120521SB001&uselang=pt>

Imprimir/exportar <#>

* Criar um livro <http://pt.wikipedia.org/w/index.php?title=Especial:Livro&bookcmd=book_creator&referer=L%C3%B3gica+proposicional> * Descarregar como PDF <http://pt.wikipedia.org/w/index.php?title=Especial:Livro&bookcmd=render_article&arttitle=L%C3%B3gica+proposicional&oldid=37651709&writer=rl>

Ferramentas <#>

* Páginas afluentes <http://pt.wikipedia.org/wiki/Especial:P%C3%A1ginas_afluentes/L%C3%B3gica_proposicional> * Alterações relacionadas <http://pt.wikipedia.org/wiki/Especial:Altera%C3%A7%C3%B5es_relacionadas/L%C3%B3gica_proposicional> * Carregar ficheiro <http://pt.wikipedia.org/wiki/Wikipedia:Carregar_ficheiro> * Páginas especiais <http://pt.wikipedia.org/wiki/Especial:P%C3%A1ginas_especiais> * Ligação permanente <http://pt.wikipedia.org/w/index.php?title=L%C3%B3gica_proposicional&oldid=37651709> * Informações da página <http://pt.wikipedia.org/w/index.php?title=L%C3%B3gica_proposicional&action=info> * Dados de item <http://www.wikidata.org/wiki/Q200694> * Citar esta página <http://pt.wikipedia.org/w/index.php?title=Especial:Citar&page=L%C3%B3gica_proposicional&id=37651709>

Noutras línguas <#>

* Afrikaans <http://af.wikipedia.org/wiki/Proposisionele_logika> * ������� <http://ar.wikipedia.org/wiki/%D8%AD%D8%B3%D8%A7%D8%A8_%D8%A7%D9%84%D9%82%D8%B6%D8%A7%D9%8A%D8%A7> * Беларуская <http://be.wikipedia.org/wiki/%D0%9B%D0%BE%D0%B3%D1%96%D0%BA%D0%B0_%D0%B2%D1%8B%D0%BA%D0%B0%D0%B7%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F%D1%9E> * Беларуская (тарашкевіца)� <http://be-x-old.wikipedia.org/wiki/%D0%97%D1%8C%D0%BB%D1%96%D1%87%D1%8D%D0%BD%D1%8C%D0%BD%D0%B5_%D0%B2%D1%8B%D0%BA%D0%B0%D0%B7%D0%B2%D0%B0%D0%BD%D1%8C%D0%B

D%D1%8F%D1%9E> * Català <http://ca.wikipedia.org/wiki/L%C3%B2gica_proposicional> * Čeština <http://cs.wikipedia.org/wiki/V%C3%BDrokov%C3%A1_logika> * C�mraeg <http://c�.wikipedia.org/wiki/Rhes�meg_osodiadol> * Deutsch <http://de.wikipedia.org/wiki/Aussagenlogik> * English <http://en.wikipedia.org/wiki/Propositional_calculus> * Español <http://es.wikipedia.org/wiki/L%C3%B3gica_proposicional> * Eesti <http://et.wikipedia.org/wiki/Lauseloogika> * Euskara <http://eu.wikipedia.org/wiki/Logika_proposizional> * ����� <http://fa.wikipedia.org/wiki/%D8%AD%D8%B3%D8%A7%D8%A8_%DA%AF%D8%B2%D8%A7%D8%B1%D9%87%E2%80%8C%D8%A7%DB%8C> * Suomi <http://fi.wikipedia.org/wiki/Propositiologiikka> * Français <http://fr.wikipedia.org/wiki/Calcul_des_propositions>תירבע * <http://he.wikipedia.org/wiki/%D7%AA%D7%97%D7%A9%D7%99%D7%91_%D7%A4%D7%A1%D7%95%D7%A7%D7%99%D7%9D> * Mag�ar <http://hu.wikipedia.org/wiki/%C3%8Dt%C3%A9letlogika> * Bahasa Indonesia <http://id.wikipedia.org/wiki/Kalkulus_proposisional> * Italiano <http://it.wikipedia.org/wiki/Logica_proposizionale> * 日本語 <http://ja.wikipedia.org/wiki/%E5%91%BD%E9%A1%8C%E8%AB%96%E7%90%86> * ��� <http://ko.wikipedia.org/wiki/%EB%AA%85%EC%A0%9C_%EB%85%BC%EB%A6%AC> * Кыргызча <http://k�.wikipedia.org/wiki/%D0%9B%D0%BE%D0%B3%D0%B8%D0%BA%D0%B0%D0%BB%D1%8B%D0%BA_%D1%81%D2%AF%D0%B9%D0%BB%D3%A9%D3%A9> * Latina <http://la.wikipedia.org/wiki/Logica_propositionalis> * Lietuvių <http://lt.wikipedia.org/wiki/Teigini%C5%B3_logika> * Nederlands <http://nl.wikipedia.org/wiki/Propositielogica> * Norsk n�norsk <http://nn.wikipedia.org/wiki/Utsegnslogikk> * Norsk bokmål <http://no.wikipedia.org/wiki/Setningslogikk> * Polski <http://pl.wikipedia.org/wiki/Rachunek_zda%C5%84> * Русский <http://ru.wikipedia.org/wiki/%D0%9B%D0%BE%D0%B3%D0%B8%D0%BA%D0%B0_%D0%B2%D1%8B%D1%81%D0%BA%D0%B0%D0%B7%D1%8B%D0%B2%D0%B0%D0%BD%D0%B8%D0%B9> * Simple English <http://simple.wikipedia.org/wiki/Propositional_logic> * Slovenčina <http://sk.wikipedia.org/wiki/V%C3%BDrokov%C3%A1_logika> * Slovenščina <http://sl.wikipedia.org/wiki/Propozicijska_logika> * Српски / srpski <http://sr.wikipedia.org/wiki/%D0%98%D1%81%D0%BA%D0%B0%D0%B7%D0%BD%D0%B8_%D1%80%D0%B0%D1%87%D1%83%D0%BD> * Svenska <http://sv.wikipedia.org/wiki/Satslogik> * ไทย <http://th.wikipedia.org/wiki/%E0%B9%81%E0%B8%84%E0%B8%A5%E0%B8%84%E0%B8%B9%E0%B8%A5%E0%B8%B1%E0%B8%AA%E0%B9%80%E0%B8%8A%E0%B8%B4%E0%B8%87%E0%B8%9B%E0%B8%A3%E0%B8%B0%E0%B8%9E%E0%B8%88%E0%B8%99%E0%B9%8C> * Українська <http://uk.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%BD%D1%8F_%D0%B2%D0%B8%D1%81%D0%BB%D0%BE%D0%B2%D0%BB%D0%B5%D0%BD%D1%8C> * 中文 <http://zh.wikipedia.org/wiki/%E5%91%BD%E9%A2%98%E9%80%BB%E8%BE%91> * Editar ligações <http://www.wikidata.org/wiki/Q200694#sitelinks-wikipedia>

* Esta página foi modificada pela última vez à(s) 11h57min de 16 de dezembro de 2013. * Este texto é disponibilizado nos termos da licença Atribuição-Partilha nos Mesmos Termos 3.0 não Adaptada (CC BY-SA 3.0) <http://creativecommons.org/licenses/b�-sa/3.0/deed.pt>; pode estar sujeito a condições adicionais. Consulte as condições de uso

<http://wikimediafoundation.org/wiki/Condi%C3%A7%C3%B5es_de_Uso> para mais detalhes.

* Política de privacidade <http://pt.wikipedia.org/wiki/Wikip%C3%A9dia:Pol%C3%ADtica_de_privacidade> * Sobre a Wikipédia <http://pt.wikipedia.org/wiki/Wikip%C3%A9dia:Sobre> * Avisos gerais <http://pt.wikipedia.org/wiki/Wikip%C3%A9dia:Aviso_geral> * Programadores <https://www.mediawiki.org/wiki/Special:M�Language/How_to_contribute> * Versão móvel <http://pt.m.wikipedia.org/w/index.php?title=L%C3%B3gica_proposicional&printable=�es>

* Wikimedia Foundation <http://wikimediafoundation.org/> * Powered b� MediaWiki <http://www.mediawiki.org/>