Lógica proposicional

Origem: Wikipédia, a enciclopédia livre.

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:

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

 1Abstração e aplicações
 2Descrição genérica de um cálculo proposicional
o 2.1Descrição
o 2.2Tabelas Verdade
 2.2.1Negação
 2.2.2Conjunção
 2.2.3Disjunção
 2.2.4Implicação ou Condicional
 2.2.5Bi-implicação ou Equivalência
 3Exemplo 1. Sistema axiomático simples
 4Exemplo 2. Sistema de Dedução Natural
o 4.1Regra de Demonstração Condicional (RDC)
 5Correção e completude das regras
 6Um cálculo alternativo
o 6.1Axiomas
o 6.2Regra de inferência
o 6.3Meta-regra de inferência
o 6.4Exemplo de uma prova
 7Outros cálculos lógicos
 8Referências
 9Ver também
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  cujas fórmulas são construídas da

seguinte maneira:

 O conjunto alfa  é 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  também referidos
como fórmulas atômicas ou elementos terminais. Nos
exemplos a seguir, os elementos de  são tipicamente as
letras  em diante.
 O conjunto omega  é um conjunto finito de elementos
chamados símbolos de operadores ou conectivos
lógicos. O conjunto  é dividido entre os seguintes
conjuntos distintos:

Nesta divisão,  é o conjunto dos símbolos

de aridade 
Nos cálculos proposicionais mais familiares,  é
tipicamente particionado em termos de:
 Uma opção frequentemente adotada é tratar os
valores lógicos constantes como operadores
de aridade zero. Assim:
Alguns autores usam o til (~) ao invés de (¬); e
alguns usam o (&) ou () 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 { }.

 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  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  é

fórmula de 
2. Passo (a). Se  é uma fórmula, então ¬ é uma
fórmula.
3. Passo (b). Se  e  são fórmulas, então ( ∧ ), ( ∨ ),
( → ), e ( ↔ ) são fórmulas.
4. Fechado. Nada mais é uma fórmula de 

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

Por exemplo:

1. Pela regra 1,  é uma fórmula.

2. Pela regra 2, ¬ é uma fórmula.
3. Pela regra 1,  é uma fórmula.
4. Pela regra 3, (¬ ∨ ) é uma fórmula.
 O conjunto 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  é um conjunto finito de pontos
iniciais que são chamados de axiomas quando eles
recebem interpretações lógicas.

Tabelas Verdade

Seja  uma linguagem que contenha as proposições   e 

O que podemos dizer sobre a proposição  Para começar, segundo o princípio de

bivalência, ela é ou verdadeira ou falsa. Isto representamos assim:

Agora, o que podemos dizer sobre as proposições  e  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   e  é 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   ou  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 sub-

fórmulas de uma fórmula e a própria fórmula. Por
exemplo, a fórmula  tem o seguinte conjunto de
sub-fórmulas: 
 2.  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 é  sendo  o número de valores que o sistema permite (sempre 2 no

caso do CPC) e  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  temos:

P∧ (P∧Q) → ¬((P∧Q)→
P Q R
Q R R)

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 ", "Não é o caso de ", "A

proposição '' é falsa".

Assim, em uma linguagem  na qual  significa "Sócrates é mortal",  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  significa
"Sócrates é mortal",  pode ser interpretada como "Sócrates é imortal". Por outro lado,
em uma linguagem  na qual  significa "João é bom jogador", a proposição "João é mau
jogador" não é a melhor interpretação para  (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

“ ” significa “ ” é falsa.

“ ” significa “” é falsa.

E assim por diante.

Repare que  é equivalente a  assim como  é equivalente a 

A negação múltipla traz alguns problemas de interpretação. Interpretando mais uma

vez  por "Sócrates é mortal", podemos perfeitamente interpretar  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∧
P Q
Q

V V V

V F F

F V F
F F F

 Interpretação: "" pode ser interpretada como " e ",

"Tanto  quanto ", "Ambas proposições '' e '' são
verdadeiras" etc.

Assim, em uma linguagem  na qual  significa "Sou cidadão brasileiro" e  significa "Sou

estudante de filosofia",  pode ser interpretada como "Sou cidadão brasileiro e estudante
de filosofia"; o que só é verdade se  é verdadeira e  é verdadeira.

Repare que a conjunção é comutável, ou seja,  é equivalente a  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  na qual  significa "João foi atropelado"
e  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: 

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∨
P Q
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: "" pode ser interpretada como " ou ",

"Entre as proposições  e  ao menos uma é verdadeira".

Assim, se  significa "Fulano estuda filosofia" e  significa "Fulano estuda

matemática",  pode ser interpretada como "Fulano estuda filosofia ou matemática"; o
que só é falso se nem  nem  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: "" pode ser interpretada como

"Se  então ", " implica ", "Se a proposição '  ' é
verdade, então a proposição '  ' também é verdade", "A
partir de '' inferimos '' ", " satisfaz ", " é condição
suficiente de ".

Assim, se, em uma linguagem   significa "O botão vermelho foi apertado" e  significa
"O lugar inteiro explode",  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 ) e o lugar inteiro não explodir, este resultado é falso (falsidade de ):

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,  não implica  (  é 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: "" pode ser interpretada como " se e

somente se ", " é equivalente a ", " e  possuem o mesmo
valor de verdade".

Assim, se  significa "O número natural é divisível por cinco" e  significa "'O último
algarismo do número natural é zero ou cinco",  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  onde  são definidos como:

 O conjunto  é um conjunto finito de símbolos que é

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

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  particionado em:

Um sistema axiomático descoberto por Jan

Łukasiewicz formula um cálculo
proposicional na linguagem a seguir. Os
axiomas em  são todos instâncias de
substituição de:

A regra de inferência em  é 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  onde  são definidos a seguir:

 O conjunto  é um conjunto
finito de símbolos suficiente
para suprir a necessidade de
uma dada discussão, por
exemplo:
 O conjunto  consiste em:

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, 
 O conjunto de
regras de
transformação,  é
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.
Int
rod
uçã
o
da
dis
jun
ção
De p, infere-se (p ∨ q)
De p, infere-se (q ∨ p).
Eli
min
açã
o da
disj
unç
ão
De (p ∨ q), (p → r), (q → r), infere-se r.
Introdu
ção do
Bicondi
cional
De (p → q), (q → p), infere-se (p ↔ q).
Eliminação
do
Bicondicion
al
De (p ↔ q), infere-se (p → q);
De (p ↔ q), infere-se (q → p).
Modus
ponens (eliminaç
do condicional)
De p, (p → q), infere-se q.
Demonstração
Condicional (intr
ão do condicional
Se p for aceito como prova de q, infere-se (p → q).

For
ma
s
de
Ar
gu
me
nto
s
Bás
ico
se
De
riv
ado
s
Em seguida, det
última regra, dita
hipotética.
Regra de
Demonstraçã
Condicional
Um dos principa
de um cálculo
proposicional, em
aplicações lógica
determinação de
relações de equi
lógica entre fórm
proposicionais. E
relações são
determinadas em
das regras de
transformação
disponíveis. Seq
de regras estabe
que chamamos
"derivação" ou
"demonstração".
Na discussão a s
uma demonstraç
apresentada com
sequência de lin
enumeradas, em
cada linha consis
uma única fórmu
seguida por
uma razão ou ju
para introduzir e
fórmula. Cada pr
do argumento, q
assumida como
hipótese do argu
listada no começ
sequência e é ju
simplesmente co
"premissa". A co
é listada na últim
Uma demonstraç
completa se cad
segue das anteri
pela aplicação co
uma regra de inf
Exemplo de
demonstração
condicional

 Para mostrar
que A → A.
 Uma demons
possível para
pode ser obti
seguinte form

Exe
mpl
o de
pro
va
Interprete A ] A c
"Assumindo A, in
se A". Leia ] A →
"Sem assumir na
que A implica A,
uma tautologia
que A implica A,
sempre verdade
que A implica A.

Correção e
completude
regras
As propriedades
desse conjunto d
são que elas
são corretas e co
Informalmente is
dizer que as regr
corretas e que n
preciso acrescen
outras regras. Fa
uma abordagem
formal disto logo
Definimos uma a
de verdade como
função matemáti
mapeia variáveis
proposicionais p
valores verdade
so. Informalmen
atribuições pode
entendidas como
descrição de um
estado das coisa
qual certas asse
são verdadeiras
não são. A semâ
das fórmulas pod
formalizada pela
definição de qua
"estados das coi
quais elas são
consideradas
verdadeiras, que
é feito pela defin
seguir.
Definimos quand
atribuição v satis
certa fórmula be
formada com as
seguintes regras

 v satisfaz a v
proposicional
somente se v
= verdadeiro
 v satisfaz ¬φ
somente se v
satisfaz φ
 v satisfaz (φ
somente se v
ambos φ e ψ
 v satisfaz (φ
somente se v
pelo menos φ
 v satisfaz (φ
e somente se
o caso em
que v satisfaz
não ψ
 v satisfaz (φ
e somente
se v satisfaz
ψ ou não sati
nenhum dele
Com esta definiç
podemos formali
agora o que que
uma fórmula φ s
implicada por ce
conjunto  de fórm
Informalmente, is
caso se em todo
possível das cois
qual vale o conju
fórmulas  vale ta
fórmula φ. Isso le
a seguinte defini
formal: Nós dize
um conjunto  de
fbfs semanticam
ligadas implicam
uma certa fbf φ s
as atribuições
verdadeiras que
 satisfazem as
fórmulas  também
satisfazem φ.
Finalmente nós d
uma "relação de
consequência sin
tal que φ é conse
sintática de  se e
somente se nós
derivar com as re
inferência que fo
apresentadas ac
um número finito
passos. Isso nos
formular exatam
que quer dizer p
conjunto de regr
inferência ser co
completo:
Correção lógica
Se o conjunto de fbfs  tem como consequência
sintática a fbf φ, então  tem como
consequência semântica φ.
Completude lóg
Se o conjunto de fbfs  tem como consequência
semântica a fbf φ então  tem como
consequência sintática φ.
Para o conjunto
acimas este é, e

Um cálculo
alternativo
É possível defini
do cálculo propo
define a maior pa
dos operadores
termos de axiom
somente uma re
inferência.
Axiomas
Seja φ, χ e ψ sím
fórmulas bem for
em si não contêm
grega, mas some
romanas maiúsc
operadores cone
parênteses.) Ent
são os seguintes

Nome

ENTÃO-
1

ENTÃO-
2

E-1

E-2

E-3

OU-1

OU-2

OU-3
 NÃO-1

NÃO-2

NÃO-3

SSE-1

SSE-2

SSE-3

O axioma ENTÃ
considerado com
"propriedade dis
implicação com r
implicação."
Os axiomas E-1
correspondem à
conjunção". A re
e E-2 reflete a co
do operador da c
O axioma E-3 co
"introdução da c
Os axiomas OU-
correspondem à
disjunção." A rel
 e OU-2 reflete a
do operador da d
O axioma NÃO-1
"redução ao abs
O axioma NÃO-2
pode ser deduzid
contradição."
O axioma NÃO-3
"tertium non datu
há uma terceira
a valoração sem
fórmula proposic
fórmula pode ter
verdade verdade
Não há um terce
verdade, pelo me
lógica clássica. L
intuicionista não
NÃO-3.
Regra de infe
A regra de inferê
ponens:
Meta-regra d
Seja uma demon
representada po
sequência, com
esquerda do sím
consequência fo
conclusões à dir
o teorema da de
definido como:
Se a sequência
foi demonstrada, então também é possível
demonstrar a sequência
Esse teorema de
formulado por m
proposicional: nã
teorema da lógic
um teorema sob
proposicional. Ne
meta-teorema, c
teoremas sobre
completude da ló
Por outro lado, o
simplificar o proc
 sintática que pod
usado como uma
inferência qualqu
modus ponens. N
corresponde à re
condicional que
versão do cálcul
introduzida neste
A recíproca do T
Se a sequência
foi demonstrada, então também é possível
demonstrar a sequência
De fato, a valida
trivial comparada
Se
então
1: 
2: 
e de (1) e (2) se pode deduzir
3: 
por meio do modus ponens, Q.E.D.
A validade do TD
para converter u
exemplo, o axiom
pode ser transfo
dedução na regr
que é a eliminaç
usadas na prime
proposicional.
Exemplo de u
A seguir, há um
envolvendo apen
Provar: A → A (
Prova:
1. (A → ((B → A
Axioma ENTÃO-2 com φ = A, χ = B → A, ψ
= A
2. A → ((B → A
Axioma ENTÃO-1 com φ = A, χ = B → A
3. (A → (B → 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álc
Lógica proposici
lógico em qualqu
amplamente utili
vista mais simple
lógica proposicio
diversas formas.
A forma mais im
complexo é pela
detalhes estrutur
"sentenças atôm
em termos, variá
à lógica de prime
ordem, que man
adiciona alguma
mamíferos" pode
mamífero".
Com as ferramen
várias teorias, ta
de inferência, teo
cálculos lógicos.
exemplos incluem
As lógicas moda
que não podem
exemplo, de "Ne
De p podemos in
As lógicas poliva
valores além de 
exemplo, nenhum
do contínuo" per
verdade de um n

Referências
 Bedregal, Be
(2002), Lógic
Natal, RN.
 GORSKY, Sa
seu interesse
UNICAMP. 2
 Lógica e Filos
filosofia tais c
e de outros p
história da filo

Ver também

Categoria: 
 Lógica
 Esta página foi ed
 Este texto é dispo
Não Adaptada (C
condições adicion