Lógica proposicional

Fonte: SAPO Saber, a enciclopédia portuguesa livre.

(Redirecionado de Cálculo Proposicional)

Em lógica e matemática, uma lógica proposicional (ou cálculo sentencial) é um sistema formal no qual as fórmulas representam proposições que podem ser formadas pela combinação de proposições atômicas usando conectivos lógicos, e um sistema de regras de derivação que permite que certas fórmulas sejam estabelecidas como "teoremas" do sistema formal.

Em termos gerais, um cálculo é freqüentemente apresentado como um sistema formal que consiste em um conjunto de expressões sintáticas (fórmulas bem formadas, ou fbfs), um subconjunto distinto dessas expressões, e um conjunto de regras formais que define uma relação binária específica, que se pretende interpretar como 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, as expressões devem ser interpretadas como asserções matemáticas, e as regras, conhecidas como regras de inferência, normalmente são preservadoras da verdade. Nessa configuração, as regras (que podem incluir axiomas) podem então ser usadas para derivar "inferir" fórmulas representando asserções verdadeiras.

O conjunto de axiomas pode ser vazio, um conjunto finito não vazio, um conjunto finito enumerável, ou pode ser dado por axiomas esquemáticos. Uma gramática formal define recursivamente as expressões e fórmulas bem formadas (fbfs) da linguagem. Além disso, pode se apresentar uma semântica para definir verdade e valorações (ou interpretações).

A linguagem de um cálculo proposicional consiste em:

  1. um conjunto de símbolos primitivos, definidos como fórmulas atômicas, 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) é qualquer fórmula atômica ou qualquer fórmula que pode ser construída a partir de fórmulas atômicas, usando conectivos de acordo com as regras da gramática.

O que segue define um cálculo proposicional padrão. Existem muitas formulações diferentes as quais são todas mais ou menos equivalentes mas que 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

[editar] Abstração e aplicações

Embora seja possível construir um cálculo abstrato formal que não tem uso prático imediato e praticamente nenhuma aplicação óbvia, o nome cálculo indica que esta espécie de sistema formal tem sua origem na utilidade de seus membros protó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 objetos formais, e tipicamente com o objetivo de facilitar as computações e inferê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 sua denotação pretendida, isto é, dos objetivos formais que se pretende denotar com as fórmulas do cálculo.

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

[editar] 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 o que é uma proposição considere a frase “1 mais 1 é igual a 10” ou simbolicamente, “1 + 1 = 10”. Esta frase é uma proposição no sentido de que ela é uma asserção declarativa, ou seja, afirma ou nega um fato, e tem um valor de verdade, que pode ser verdadeiro ou falso. Neste caso, num sistema de numeração de base 2, a proposição anterior seria verdadeira, enquanto que no sistema decimal seria falsa. Um outro exemplo é a afirmação “hoje é um dia quente” cujo valor de verdade vai depender de vários fatores: o local sobre o qual implicitamente se está falando, os instrumentos de medidas e de comparação (quais os dados estatísticos de temperatura dessa região), e principalmente de quem está avaliando (duas pessoas, mesmo considerando as 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, que mesmo num contexto interpretativo claro e não ambíguo, para as quais não é possível estabelecer de forma inquestionável sua veracidade ou falsidade (pelo menos com o conhecimento atual da humanidade). Mas, em lógica, o importante não é o valor de verdade que uma proposição possa tomar num determinado contexto interpretativo, mas a possibilidade de que “em princípio” seja possível atribuir um valor de verdade, e que seja possível raciocinar com estas proposições.

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


[editar] Descrição

Um cálculo proposicional é um sistema formal \mathcal{L} =  (\Alpha,\ \Omega,\ \Zeta,\ \Iota) cujas fórmulas são construídas da seguinte maneira:

  • O conjunto alfa \Alpha\! é 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 \Alpha\! 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 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 freqüentemente adotada é tratar os valores lógicos constantes como operadores de aridade zero. Assim:
\Omega_0 = \{\bot, \top \} \,.
Alguns autores usam o til (~) ao invés de (¬); e algums 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, é definida recursiva ou indutivamente pelas seguintes regras:

  1. Base. Qualquer elemento do conjunto alpha \Alpha\! é 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órmulas complexas. 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 \Zeta\! é 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 \Iota\! é um conjunto finito de pontos iniciais que são chamados de axiomas quando eles recebem interpretações lógicas.

[editar] Tabelas de 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 o princípio de bivalência, ela é ou verdadeira ou falsa. Isto representamos assim:

P
V
F


Agora, o que podemos dizer sobre as proposições P\,\! e Q\,\! ? Oras, ou ambas 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 V
V F
F V
F F


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

P Q R
V V V
V V F
V F V
V F F
F V V
F V F
F F V
F F F

Cada linha da tabela (fora a primeira que contém as fórmulas) representa uma valoração.

Agora, o que dizer sobre fórmulas moleculares, tais como \neg P\,\!, Q\lor R\,\! ou \left(Q\land R\right)\to \left(P\leftrightarrow Q\right) ? Para estas, podemos estabelecer os valores que elas recebem em vista do valor de cada fórmula atômica que as compõe. Faremos isto por meio das tabelas de verdade.

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

1º) Uma linha em que estão contidas todas as subfórmulas de uma fórmula e a própria fórmula. Por exemplo, a fórmula \neg \left(\left( P\land Q\right)\to R \right) tem o seguinte conjunto de subfó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 as proposições atômicas podem receber e os valores recebidos pelas fórmulas moleculares a partir dos valores destes átomos.

O número de linhas é l = n^t\!\, , sendo n\!\, o número de valores que o sistema permite (sempre 2 no caso do CPC) e t\!\, o número de átomos que a fórmula contém. Assim, se uma fórmula contém 2 átomos, o número de linhas que expressam a permutações entre estes será 4: um caso de ambos serem verdadeiros (V V), dois casos de apenas um dos átomos ser verdadeiro (V F , F V) e um caso no qual ambos serem falsos (F F). Se a fórmula contiver 3 átomos, o número de linhas que expressam a permutações entre estes será 8: um caso de todos os átomos serem verdadeiros (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 ser verdadeiro (V F F , F V F , F F V) e um caso no qual todos átomos são falsos (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 V
V V F
V F V
V F F
F V V
F V F
F F V
F F F

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

[editar] Negação

A negação tem o valor inverso da fórmula negada. A saber:
P ¬ P
V F
F 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ócrates não é mortal", e, se o primeiro é verdadeiro, o segundo é falso; e se o primeiro é 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 é perfeitamente aplicável, ou seja, se P\!\, significa "Sócrates é mortal", \neg P\!\, pode ser interpretada como "Sócrates é imortal". Por outro lado, em uma linguagem \mathcal{L}\!\, na qual Q\!\, significa "João é bom jogador", a proposição "João é mau jogador" não é a melhor interpretaçã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 F
F 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. Interpretando mais uma vez P \,\! por "Sócrates é mortal", podemos perfeitamente interpretar \neg \neg P \,\! de diversar formas: "Não é o caso de que Só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 uma proposiçã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 fiz nada hoje" etc.

[editar] Conjunção

A conjunção entre duas fórmulas só é verdadeira quando ambas são verdadeiras. A saber:
P Q P∧Q
V V V
V F F
F V F
F 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 "Sou cidadão brasileiro" e Q\!\, significa "Sou estudante de filosofia", P\land Q\!\, pode ser interpretada como "Sou cidadão brasileiro e estudante de filosofia"; o que só é verdade se P\!\, é verdadeira e Q\!\, é verdadeira.

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

P Q P∧Q Q∧P
V V V V
V F F F
F V F F
F F F F

A comutatividade da conjunção traz um problema para formalizar proposições da linguagem natural no Cálculo Proposicional Clássico, pois a ordem em que as orações aparecem pode sugerir uma seqüê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ão acomete 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ássico por meio de uma conjunção.

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

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

[editar] 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 V
V F V
F V V
F F F

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

P Q P∨Q Q∨P
V V V V
V F V V
F V V V
F 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 de fórmulas quanto na formalização de proposições, pois na linguagem natural muitas vezes os disjuntos são excludentes. Por exemplo: "Uma moeda ao ser lançada resulta em cara ou coroa", "Nestas férias eu vou 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.

[editar] Implicação

A implicação entre duas fórmulas só é falsa se a da esquerda (antecedente) for verdadeira e da direita (conseqüente) for falsa. A saber:
P Q P→Q
V V V
V F F
F V V
F F V

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

P Q P→Q Q→P
V V V V
V F F V
F V V F
F 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ão vermelho foi apertado" e Q\!\, significa "O lugar inteiro explode", P\to Q\!\, pode ser interpretada como "Se o botão vermelho foi apertado, o lugar inteiro explode", o que só é falso se o botão vermelho for apertado (verdade de P\!\,) e o lugar inteiro não explodir (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, o lugar explodir, mas uma coisa não tiver nada a ver com a outra?".

Basicamente, o que se deve observar é que "O botão vermelho ser apertado" é condição suficiente para se deduzir que "O lugar inteiro explodiu", isto é, quando o botão é apertado, o lugar deve explodir. Se o botão for apertado e o lugar não explodir, algo está errado, ou seja, Falhou ao verificar gramática (Executável texvc não encontrado; Consulte math/README para instruções da configuração.): P\!\

não implica Falhou ao verificar gramática (Executável texvc não encontrado; Consulte math/README para instruções da configuração.): Q \!\ 
( P\to Q\!\, é falso).

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

Mas o contrário, ou seja, interpretar uma implicação na linguagem natural é problemático. Podemos estar lidando com uma implicação cujo antecedente e cujo conseqüente não têm relação alguma. Basta, contudo que o antecedente seja falso ou o conseqüente seja verdadeiro para que a implicação seja verdadeira. Nestes casos, é bem difícil dar uma interpretação satisfatória para a implicação.

[editar] Bi-implicação

A bi-implicação entre duas fórmulas é verdadeira quando ambas são verdadeiras ou ambas são falsas.
P Q P↔Q
V V V
V F F
F V F
F F V

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

P Q P↔Q Q↔P
V V V V
V F F F
F V F F
F 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 "As luzes estão acesas" e Q\!\, significa "O interruptor está voltado para cima", P\leftrightarrow Q pode ser interpretada como "As luzes estão acesas se e somente se o interruptor está voltado para cima", o que só é falso se as luzes estiverem acesas e o interruptor não estiver voltado para cima (verdade de P\!\, falsidade de Q\!\,), ou se as luzes não estiverem acesas e o interruptor estiver voltado para cima (falsidade de P\!\, e verdade de Q\!\,)

[editar] Exemplo 1. Sistema axiomático simples

Seja \mathcal{L}_1 = (\Alpha,\ \Omega,\ \Zeta,\ \Iota), onde \Alpha,\ \Omega,\ \Zeta,\ \Iota são definidos como:

  • O conjunto \Alpha \! é um conjunto finito de símbolos que é grande o suficiente para suprir as necessidades de uma dada discussão, por exemplo:
\Alpha = \{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 ser definidos em termos deste e da negação (¬). Certamente, todos os conectivos lógicos podem ser definidos em termos de um único operador. 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 um cá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álculo proposicional na linguagem a seguir. Os axiomas em \Iota \! são todos 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 \Zeta \! é modus ponens (isto é, de p e (pq), infere-se q). Então ab é definido como ¬ab, ab é definido como ¬(a → ¬b).

[editar] Exemplo 2. Sistema de Dedução Natural

Seja \mathcal{L}_2 = \mathcal{L}\ (\Alpha,\ \Omega,\ \Zeta,\ \Iota), onde \Alpha,\ \Omega,\ \Zeta,\ \Iota são definidos a seguir:

  • O conjunto \Alpha \! é um conjunto finito de símbolos suficiente para suprir a necessidade de uma dada discussão, por exemplo:
\Alpha = \{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ção devem ser interpretadas como as regras de inferência do chamado sistema de dedução natural. O sistema particular apresentado aqui não possui pontos iniciais, o que significa que sua interpretação para aplicações lógicas deriva seus teoremas a partir de um conjunto de axiomas vazio.

  • O conjunto de pontos iniciais é vazio, ou seja, \Iota = \varnothing \,.
  • O conjunto de regras de transformação, \Zeta ,\!, é descrito a seguir:

Nosso cálculo proposicional possui dez regras de inferência. Essas regras nos permitem derivar outras fórmulas verdadeiras a partir de um conjunto de fórmulas assumidas como verdadeiras. As primeiras nove regras dizem simplesmente que podemos inferir certas fbfs de outras fbfs. A última regra, no entanto, usa o raciocínio hipotético no sentido de que, na premissa da regra, assumimos temporariamente uma hipótese (não demonstrada) como parte do conjunto de fórmulas inferidas a fim de descobrir se podemos inferir uma certa outra fórmula. Como as nove primeiras 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 (introdução da negação) 
De (pq), (p→ ¬q), infere-se ¬p.
Dupla eliminação da negação 
De ¬¬p, infere-se p.
Introdução da conjunção 
De p e q, infere-se (pq).
Eliminação da conjunção 
De (pq), infere-se p
De (pq), infere-se q.
Introdução da disjunção 
De p, infere-se (pq)
De p, infere-se (qp).
Eliminação da disjunção 
De (pq), (pr), (qr), infere-se r.
Introdução do Bicondicional 
De (pq), (qp), infere-se (pq).
Eliminação do Bicondicional 
De (pq), infere-se (pq);
De (pq), infere-se (qp).
Modus ponens (eliminação do condicional) 
De p, (pq), infere-se q.
Demonstração Condicional (introdução do condicional) 
Se p for aceito como prova de q, infere-se (pq).

Formas de Argumentos Básicos e Derivados
Nome Seqüência Descrição
Modus Ponens ((pq) ∧ p) ├ q Se p então q; p; conseqüentemente q
Modus Tollens ((pq) ∧ ¬q) ├ ¬p Se p então q; não q; conseqüentemente não p
Silogismo Hipotético ((pq) ∧ (qr)) ├ (pr) Se p então q; se q então r; conseqüentemente, se p então r
Silogismo Disjuntivo ((pq) ∧ ¬p) ├ q p ou q; não p; conseqüentemente, q
Dilema Construtivo ((pq) ∧ (rs) ∧ (pr)) ├ (qs) Se p então q; e se r então s; mas p ou r; conseqüentemente q ou s
Dilema Destrutivo ((pq) ∧ (rs) ∧ (¬q ∨ ¬s)) ├ (¬p ∨ ¬r) Se p então q; e se r então s; mas não q ou não s; conseqüentemente não p ou não r
Simplificação (pq) ├ p p e q são verdadeiros; conseqüentemente p é verdadeiro.
Conjunção p, q ├ (pq) p e q são verdadeiros separadamente; conseqüentemente eles são verdadeiros conjuntamente
Adição p ├ (pq) p é verdadeiro; conseqüentemente a disjunção (p or q) é verdadeira
Composição ((pq) ∧ (pr)) ├ (p → (qr)) Se p então q; e se p então r; conseqüentemente se p é verdadeiro então q e r são verdadeiros
Teorema de De Morgan (1) ¬(pq) ├ (¬p ∨ ¬q) A negação de (p e q) tem como conseqüência (não p ou não q)
Teorema de De Morgan (2) ¬(pq) ├ (¬p ∧ ¬q) A negação de (p ou q) tem como conseqüência (não p e não q)
Commutação (1) (pq) ├ (qp) (p ou q) tem como conseqüência (q ou p)
Commutação (2) (pq) ├ (qp) (p e q) tem como conseqüência (q e p)
Associatividade (1) (p ∨ (qr)) ├ ((pq) ∨ r) p ou (q ou r) tem como conseqüência (p ou q) ou r
Associatividade (2) (p ∧ (qr)) ├ ((pq) ∧ r) p e (q e r) tem como conseqüência (p e q) e r
Distributividade (1) (p ∧ (qr)) ├ ((pq) ∨ (pr)) p e (q ou r) tem como conseqüência (p e q) ou (p e r)
Distributividade (2) (p ∨ (qr)) ├ ((pq) ∧ (pr)) p ou (q e r) tem como conseqüência (p ou q) e (p ou r)
Dupla Negação p ├ ¬¬p p tem como conseqüência a negação de não p
Transposição (pq) ├ (¬q → ¬p) Se p então q tem como conseqüência se não q então não p
Implicação Material (pq) ├ (¬pq) Se p então q tem como conseqüência não p ou q
Equivalência Material (1) (pq) ├ ((pq) ∧ (qp)) (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) (pq) ├ ((pq) ∨ (¬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) (pq) ├ ((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 ((pq) → r) ├ (p → (qr)) 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 → (qr)) ├ ((pq) → r) De (se p então (q então r) é verdadeiro) podemos demonstrar que ((pq) → r) é verdadeiro
Tautologia (1) p ├ (pp) p é verdadeiro tem como conseqüência p é verdadeiro ou p é verdadeiro
Tautologia (2) p ├ (pp) p é verdadeiro tem como conseqüência p é verdadeiro e p é verdadeiro
Tertium non datur (Lei do Terceiro Excluído) ├ (p ∨ ¬ p) p ou não p é verdadeiro

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

[editar] Regra de Demonstração Condicional (RDC)

Um dos principais usos de um cálculo proposicional, em aplicações lógicas, é na determinação de relações de equivalência lógica entre fórmulas proposicionais. Essas relações são determinadas em termos das regras de transformação disponíveis. Seqüências de regras establecem o que chamamos "derivação" ou "demonstração".

Na discussão a seguir, uma demonstração é apresentada como uma seqüência de 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 do argumento, é listada no começo da seqüência e é justificada simplesmente como uma "premissa". A conclusão é listada na última linha. Uma demonstração é completa se cada linha segue das anteriores pela aplicação correta de uma regra de inferência.

Exemplo de demonstração condicional

  • Para mostrar que AA.
  • Uma demonstração possível para isso, pode ser obtida da seguinte forma:


Exemplo de prova
Número Fórmula Razão
1 A premissa
2 AA Resumo de (1)
3 AA De (2) pela demonstração condicional


Interprete AA como "Assumindo A, infere-se A". Leia ├ AA como "Sem assumir nada, infira que A implica A," ou "É uma tautologia que A implica A," ou "É sempre verdade que A implica A."

[editar] 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 regras são corretas e que não é preciso acrescentar outras regras. Faremos uma abordagem mais formal disto logo abaixo.

Definimos uma atribuição de verdade como uma função matemática que mapeia variáveis proposicionais para os valores verdadeiro ou falso. Informalmente estas atribuições podem ser entendidas como uma descrição de um possível estado das coisas no qual certas asserções são verdadeiras e outras não são. A semântica das fórmulas pode ser formalizada pela definição de quais são os "estados das 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 bem formada 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 no qual vale o conjunto de fórmulas \Gamma \! vale também a fórmula φ. Isso leva 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 conseqüência sintática" tal que φ é conseqüência sintática de \Gamma \! se e somente se nós podemos derivar com as regras de inferência que foram apresentadas acima em um número finito de passos. Isso nos permite formular exatamente o que quer dizer para um conjunto de regras de inferência ser correto e completo:

Correção lógica 
Se o conjunto de fbfs \Gamma \! tem como conseqüência sintática a fbf φ, então \Gamma \! tem como conseqüência semântica φ.
Completude lógica 
Se o conjunto de fbfs \Gamma \! tem como conseqüência semântica a fbf φ então \Gamma \! tem como conseqüência sintática φ.

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

[editar] Um cálculo alternativo

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

[editar] Axiomas

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

Axiomas
Nome Esquema Axiomático Descrição
ENTÃO-1 φ → (χ → φ) Adiciona a hipótese χ, introdução da implicação
ENTÃO-2 (φ → (χ → ψ)) → ((φ → χ) → (φ → ψ)) Distribui a hipótese φ sobre a implicação
E-1 φ ∧ χ → φ Eliminação da conjunção
E-2 φ ∧ χ → χ Eliminação da conjunção 2
E-3 φ → (χ → (φ ∧ χ)) Introdução da conjunção
OU-1 φ → φ ∨ χ Introdução da disjunção 2
OU-2 χ → φ ∨ χ Introdução da disjunção
OU-3 (φ → ψ) → ((χ → ψ) → (φ ∨ χ → ψ)) Eliminação da disjunção
NÃO-1 (φ → χ) → ((φ → ¬χ) → ¬ φ) Introdução da negação
NÃO-2 φ → (¬φ → χ) Eliminação da negação
NÃO-3 φ ∨ ¬φ Lei do terceiro excluído, lógica clássica
SSE-1 (φ ↔ χ) → (φ → χ) Eliminação da equivalência
SSE-2 (φ ↔ χ) → (χ → φ) Eliminação da equivalência 2
SSE-3 (φ → χ) → ((χ → φ) → (φ ↔ χ)) Introdução da equivalência


O axioma ENTÃO-2 pode ser considerado como sendo uma "propriedade distributiva da implicação com relação à implicação."
Os axiomas E-1 e E-2 correspondem à "eliminação da conjunção". A relação entre 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." A relaçã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" (Latin: "não há uma terceira opção") e reflete a valoração semântica da fórmula proposicional: uma fórmula pode ter um valor de verdade verdadeiro ou falso. Não há um terceiro valor de verdade, pelo menos não na lógica clássica. Lógica intuicionista não aceita o axioma NÃO-3.

[editar] Regra de inferência

A regra de inferência é modus ponens:

  • \phi, \ \phi \rightarrow \chi \vdash \chi.

[editar] Meta-regra de inferência

Seja uma demonstração representada por uma seqüência, com hipóteses à esquerda do símbolo de conseqüência formal \vdash e as conclusões à direita do \vdash. Então o teorema da dedução pode ser definido como:

Se a seqüencia
\phi_1, \ \phi_2, \ ... , \ \phi_n, \ \chi \vdash \psi
foi demonstrada, então também é possível demonstrar a seqüencia
\phi_1, \ \phi_2, \ ..., \ \phi_n \vdash \chi \rightarrow \psi.

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

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

A recíproca do TD também é válida:

Se a seqüencia
\phi_1, \ \phi_2, \ ..., \ \phi_n \vdash \chi \rightarrow \psi
foi demonstrada, então também é possível demonstrar a seqüencia
\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 converter um 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 na regra de inferência

\phi \wedge \chi \vdash \phi

que é a eliminação da conjunção, uma das dez regras de inferência usadas na primeira versão (no presente verbete) do cálculo proposicional.

[editar] Exemplo de uma prova

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

1. (A → ((BA) → A)) → ((A → (BA)) → (AA))
Axioma ENTÃO-2 com φ = A, χ = BA, ψ = A
2. A → ((BA) → A)
Axioma ENTÃO-1 com φ = A, χ = BA
3. (A → (BA)) → (AA)
De (1) e (2) por modus ponens.
4. A → (BA)
Axioma ENTÃO-1 com φ = A, χ = B
5. AA
De (3) e (4) por modus ponens.

[editar] Outros cálculos lógicos

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

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 das sentenças empregadas. Quando as "sentenças atômicas" da lógica proposicional são quebradas em termos, variáveis, predicados, e quantificadores, elas dão origem à lógica de primeira ordem, ou lógica de predicados de primeira ordem, que mantém todas as regras da lógica proposicional e adiciona algumas novas. Por exemplo, de "Todos os cachorros são mamíferos" podemos inferir "Se Totó é um cachorro então Totó é um mamífero".

Com as ferramentas da lógica de primeira ordem é possível formular várias teorias, tanto com axiomas explícitos como através de regras de inferência, teorias que podem elas próprias ser tratadas como cálculos lógicos. A aritmética é o melhor exemplo disso; outros exemplos incluem a teoria dos conjuntos e a mereologia.

As lógicas modais também oferecem uma variedade de inferências que não podem ser capturadas 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 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 "valores extras" padrões; a "lógica do contínuo" permite que cada sentença tenha qualquer grau de verdade de um número infinito de graus entre verdadeiro e falso.

[editar] Referências

Wikibooks
O Wikilivros possui livros ou outros textos didáticos sobre: Lógica

[editar] Ver também

[editar] Níveis lógicos

[editar] Blocos básicos

[editar] Tópicos relacionados

be-x-old:Злічэнне выказванняў

Ferramentas pessoais