Lógica 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 é frequentemente 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:

um conjunto de símbolos primitivos, definidos como fórmulas atômicas, proposições atômicas, ou variáveis, e
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:

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

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 ideia 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.

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.

Descrição

Um cálculo proposicional é um sistema formal ${\mathcal {L}}=(\mathrm {A} ,\ \Omega ,\ \mathrm {Z} ,\ \mathrm {I} )$ cujas fórmulas sã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 $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 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, é definida recursiva ou indutivamente pelas seguintes regras:

Base. Qualquer elemento do conjunto alpha $\mathrm {A}$ é fórmula de ${\mathcal {L}}.$
Passo (a). Se ${\mathcal {P}}$ é uma fórmula, então ¬ ${\mathcal {P}},$ é uma fórmula.
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.
Fechado. Nada mais é uma fórmula de ${\mathcal {L}}.$

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

Pela regra 1, ${\mathcal {P}}$ é uma fórmula.
Pela regra 2, ¬ ${\mathcal {P}}$ é uma fórmula.
Pela regra 1, ${\mathcal {Q}}$ é uma fórmula.
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 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:

Uma linha em que estão contidas todas as sub-fó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 sub-fórmulas: $\left\{\left(P\land Q\right)\to R,P\land Q,P,Q,R\right\}$
$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
V	V	V	V
V	V	F	V
V	F	V	F
V	F	F	F
F	V	V	F
F	V	F	F
F	F	V	F
F	F	F	F

Para completar esta tabela precisamos definir os operadores lógicos. Ao fazê-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	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.

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 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ã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 sequê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.

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.

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	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, então o lugar inteiro explode", mas se o botão vermelho for apertado (verdade de $P$ ) e o lugar inteiro não explodir, este resultado é 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, 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, $P$ não implica $Q$ ( $P\to Q$ é falso).

Quando temos na linguagem natural uma proposição que afirma que a partir de um evento (P), o outro (Q) segue inexoravelmente e de fato isto acontece (por exemplo: "Se você sair na chuva sem guarda-chuva ou capa de chuva, então você vai se molhar" ou "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.

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 ser mais difícil, pois facilmente se confunde com a bi-implicação. Deve-se ter em mente que P deve ser condição suficiente para que se tenha Q, mas nã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 for verdadeiro (F), então a implicação é falsa (F)! Por outro lado, no caso de P ser falsa (F), então não há a condição suficiente, mas podem existir outras "causas" para que Q seja verdadeira (V) ou falsa (F). Por isso, 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	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 "O número natural é divisível por cinco" e $Q$ significa "'O último algarismo do número natural é zero ou cinco", $P\leftrightarrow Q$ pode ser interpretada como "O número natural é 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 falsa para que o enunciado se torne falso.

Na linguagem natural o problema está em confundir uma condição necessária como sendo a única possibilidade para se chegar ao resultado verdadeiro. Por exemplo, alguém pode estar chorando por tristeza, mas também porque está a descascar cebola. Para que haja a equivalência o raciocí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ão definidos 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 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 Łukasiewicz formula um cálculo proposicional na linguagem a seguir. Os axiomas em $\mathrm {I}$ 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 $\mathrm {Z}$ é 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çã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, $\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. 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 (p→q), (p→ ¬q), infere-se ¬p.
Eliminação da dupla negação: De ¬¬p, infere-se p.
Introdução da conjunção: De p e q, infere-se (p ∧ q).
Eliminação da conjunção: De (p ∧ q), infere-se p; De (p ∧ q), infere-se q.
Introdução da disjunção: De p, infere-se (p ∨ q); De p, infere-se (q ∨ p).
Eliminação da disjunção: De (p ∨ q), (p → r), (q → r), infere-se r.
Introdução do Bicondicional: De (p → q), (q → p), infere-se (p ↔ q).
Eliminação do Bicondicional: De (p ↔ q), infere-se (p → q);; De (p ↔ q), infere-se (q → p).
Modus ponens (eliminação do condicional): De p, (p → q), infere-se q.
Demonstração Condicional (introdução do condicional): Se p for aceito como prova de q, infere-se (p → q).

Formas de Argumentos Básicos e Derivados
Nome	Sequência	Descrição
Modus 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 verdadeiros separadamente; consequentemente eles são verdadeiros conjuntamente
Adição	p → (p ∨ q)	p é verdadeiro; consequentemente a disjunção (p or q) é verdadeira
Composição	((p → q) ∧ (p → r)) → (p → (q ∧ r))	Se p então q; e se p então r; consequentemente se p é verdadeiro então q e r são verdadeiros
Teorema 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 como consequência (q ou p)
Commutação (2)	(p ∧ q) → (q ∧ p)	(p e q) tem como consequê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 como consequência se não q então não p
Implicação Material	(p → q) → (¬p ∨ q)	Se p então q tem como 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) é verdadeiro
Tautologia (1)	p → (p ∨ p)	p é verdadeiro tem como consequência p é verdadeiro ou p é verdadeiro
Tautologia (2)	p → (p ∧ p)	p é verdadeiro tem como consequê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.

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. Sequências de regras estabelecem o que chamamos "derivação" ou "demonstração".

Na discussão a seguir, uma demonstração é apresentada como uma sequê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 sequê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 A → A.
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	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 "É uma tautologia 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 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 consequência sintática" tal que φ é consequê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 consequência sintática a fbf φ, então $\Gamma$ tem como consequência semântica φ.
Completude lógica: 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 a maior parte da sintaxe dos operadores lógicos em termos de axiomas e usa somente uma regra de inferência.

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" (Latim: "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.

Regra de inferência

A regra de inferência é 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 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ó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 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 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.

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: A → A (Reflexibilidade da implicação).

Prova:

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

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.

Referências

Bedregal, Benjamín René Callejas; Acióly, Benedito Melo (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. Dissertação de mestrado. IFCH-UNICAMP. 2008.
Lógica e Filosofia 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.