A
logica matematica
e uma subarea da
matematica
que explora as aplicacoes da logica formal para a matematica. Basicamente, tem ligacoes fortes com
matematica
, os
fundamentos da matematica
e
ciencia da computacao teorica
.
[
1
]
Os temas unificadores na logica matematica incluem o estudo do poder expressivo de
sistemas formais
e o poder dedutivo de sistemas de
prova matematica
formal.
A logica matematica e muitas vezes dividida em campos da
teoria dos conjuntos
,
teoria de modelos
,
teoria da recursao
e
teoria da prova
. Estas areas compartilham resultados basicos sobre logica, particularmente
logica de primeira ordem
, e
definibilidade
. Na ciencia da computacao, especialmente na classificacao ACM, onde ACM vem do ingles (
Association for Computing Machinery
), logica matematica engloba topicos adicionais nao descritos neste artigo; ver
logica em ciencia da computacao
para este topico anterior.
Desde o seu surgimento, a logica matematica tem contribuido e motivado pelo estudo dos
fundamentos da matematica
. Este estudo foi iniciado no final do seculo XIX, com o desenvolvimento de arcabouco
axiomatico
para
geometria
,
aritmetica
e
analise
. No inicio do seculo XX a logica matematica foi moldada pelo
programa
de
David Hilbert
para provar a consistencia das teorias fundamentais. Os resultados de
Kurt Godel
,
Gerhard Gentzen
, e outros, desde resolucao parcial do programa, e esclareceu as questoes envolvidas em provar a consistencia. O trabalho na teoria dos conjuntos mostrou que quase toda a matematica ordinaria pode ser formalizada em termos de conjuntos, embora existam alguns teoremas que nao podem ser demonstrados em sistemas axiomaticos comuns para a teoria dos conjuntos. O trabalho contemporaneo nos fundamentos da matematica, muitas vezes se concentra em estabelecer quais as partes da matematica que podem ser formalizadas, em particular, sistemas formais (como em
matematica reversa
) ao inves de tentar encontrar as teorias em que toda a matematica pode ser desenvolvida.
O
manual de logica matematica
divide a matematica contemporanea em quatro areas:
- Teoria dos conjuntos
;
- teoria dos modelos
;
- teoria da recursao
;
- teoria da prova e da
matematica construtiva
consideradas partes de uma unica area.
Cada area tem um foco distinto, apesar de ter varias tecnicas e resultados comuns entre si. A divisao das referidas areas e os limites que separam a logica matematica de outros campos de estudo nao sao bem definidas. A
teoria da incompletude de Godel
representa nao so um marco na teoria da recursao e teoria da prova, mas tambem contribuiu para o
teorema de Lob
da teoria dos modelos. O metodo do forcamento ("forcing") e aplicada na teoria dos conjuntos, na teoria dos modelos, na teoria da recursao, assim como no estudos da matematica intuiticionistica.
O campo matematico conhecido como o da teoria das categorias usa muitos metodos axiomaticos formais nos quais se inclui o estudo da logica categorica, mas essa teoria nao e comumente considerada um sub-ramo da logica. Por causa da sua aplicabilidade em diversos campos da logica, matematicos como
Saunders Mac Lane
propuseram usar a teoria das categorias como fundamentos da matematica, independentemente da teoria dos conjuntos. Essas fundamentacoes usam topicos que em muito se parecem com modelos generalizados das teorias dos conjuntos, e empregam logica classica ou nao-classica.
A logica matematica surgiu em meados do seculo XIX como um sub-ramo da Matematica e independente do estudo tradicional da logica (
Ferreiros 2001
, p. 443). Antes do seu surgimento independente, a logica foi estudada com a
retorica
, atraves do
silogismo
e a
filosofia
. Na primeira metade do seculo XX houve uma explosao de resultados fundamentais, acompanhados por debates vigorosos sobre as bases da matematica.
Os estudos sobre o raciocinio foram inicialmente desenvolvidos por filosofos como
Parmenides
e
Platao
, mas foi
Aristoteles
quem o elaborou mais detalhadamente e definiu a logica como se estuda hoje em dia (como se estudava ate o
seculo XIX
).
Para mostrar que os
sofistas
(mestres da
retorica
e da
oratoria
) podiam enganar os cidadaos utilizando argumentos incorretos, Aristoteles estudou a estrutura logica da
argumentacao
. Revelando, assim, que alguns argumentos podem ser convincentes, embora nao sejam corretos. A logica, segundo Aristoteles, e um instrumento para atingir o conhecimento cientifico, baseando-se no
silogismo
.
Seguidores de Aristoteles reuniram seus principios sobre logica em um livro intitulado “
Organon
”, que significa “Instrumento da Ciencia”.
Teorias logicas foram desenvolvidas em diversas culturas na historia,
China
,
India
,
Grecia
e no mundo Islamico. Na Europa do seculo XVIII, filosofos matematicos, como
Leibniz
e
Lambert
tentaram representar as operacoes da logica formal atraves de simbolos, de forma algebrica mas seus esforcos e trabalhos permaneceram isolados e pouco reconhecidos.
Em meados do seculo XIX,
George Boole
e posteriormente
Augustus De Morgan
apresentaram tratamentos matematicos sistematicos. Seus trabalhos, alicercados em trabalhos de algebristas como
George Peacock
, transformaram a doutrina tradicional de Aristoteles de forma que se encaixasse no estudo dos
fundamentos da matematica
(
Katz 1998
, p. 686).
Charles Sanders Peirce
construiu sobre os estudos de Boole almejando desenvolver uma sistema de relacoes logica e quantificadores o qual ele publicou diversas vezes entre 1870 e 1885.
Gottlob Frege
apresentou um desenvolvimento independente da logica com quantificadores no seu
Begriffsschrift
, publicado em 1879, um trabalho por muitos considerado como uma reviravolta na historica da logica. O trabalho de Frege permaneceu incerto, pelo menos ate
Bertrand Russell
comecar a promove-lo no inicio da virada do seculo. As notacoes bidimensionais desenvolvidas por Frege nunca foram vastamente adotadas e caiu em desuso nos artigos e textos contemporaneos.
De 1890 a 1905,
Ernst Schroder
publicou o
Vorlesungen uber die Algebra der Logik
em tres volumes. Esse trabalho compactava e desenvolvia os trabalhos de Boole, De Morgan, e Peirce e se tornou uma grande referencia para logica simbolica, como era conhecida no fim do seculo XIX.
Preocupacoes com a possivel ausencia de fundamentos matematicos acarretaram o desenvolvimento de sistemas axiomaticos para areas da matematica fundamental como a aritmetica, analise e geometria.
Em logica o termo aritmetico se refere a teoria dos
numeros naturais
.
Giuseppe Peano
(
1889
) publicou uma serie de axiomas para serem usados pela aritmetica que hoje carregam seu nome (
Axiomas de Peano
), usando variacoes do sistema logico de Boole e Schroder, porem adicionando quantificadores. Peano nao tinha conhecimento do trabalho de Frege. Contemporaneamente
Richard Dedekind
mostrou que os numeros naturais sao unicamente caracterizados por suas propriedades da
inducao
. Dedekind (
1888
) propos a diferente caracterizacao na qual nao existia a essencia da logica formal dos axiomas de Peano. Todavia, o trabalho de Dedekind's provou teoremas inacessiveis ao sistema desenvolvido por Peano, como por exemplo a inclusao da individualidade dos conjuntos de numeros naturais (ate o isomorfismo) e as definicoes recursivas de adicao e multiplicacao da
funcao sucessora
e inducao matematica.
No meio do seculo XIX, foram descobertas falhas nos
axiomas de Euclides
para geometria (
Katz 1998
, p. 774). Alem da independencia do
postulado paralelo
, estabelecido por
Nikolai Lobachevsky
em 1826 (
Lobachevsky 1840
), matematicos descobriram que certos teoremas tomadas como certo por
Euclides
nao eram de fato demonstravel a partir de seus axiomas. Entre eles esta o teorema que diz que uma linha contem pelo menos dois pontos, ou que circulos de mesmo raio cujo centro e separado pelo raio devem intersectar. Hilbert (
1899
) desenvolveu um conjunto completo dos
axiomas para geometria
, construindo nos [
axiomas de Pasch
] pelo Pasch (
1882
). O sucesso axiomatizacao da geometria motivou Hilbert a encontrar axiomaticoes completas de outras areas da matematica, assim como os numeros naturais e da
linha real
. Isto proveria a maior area de pesquisa na primeira metade do seculo XX.
As proposicoes sao determinadas por sentencas declarativas, pertencentes a uma certa linguagem, que formam um conjunto de palavras ou simbolos e expressam uma ideia. As sentencas declarativas sao afirmacoes que podem receber apenas dois valores, Verdadeiro ou Falso. As proposicoes devem seguir os seguintes principios:
- Principio da identidade
: garante que uma proposicao e igual a ela mesma.
- Principio da nao-contradicao
: uma proposicao nao pode ser verdadeira e falsa.
- Principio do terceiro excluido
: uma proposicao e verdadeira ou falsa.
Exemplos:
O cachorro e um animal. -
Verdadeiro
2 + 2 = 7 -
Falso
Qualquer sentenca que nao puder receber a atribuicao de verdadeira ou falsa nao e uma proposicao.
Sentencas interrogativas, exclamativas e imperativas nao sao proposicoes, pois nao e possivel dizer se sao verdadeiras ou falsas.
Exemplos de sentencas que nao sao proposicoes:
- Como foi a aula?
- O pior atentado nos EUA ocorreu em setembro de 2011?
- Limpe a cozinha.
- Que local de trabalho horroroso!
- Esta sentenca nao e verdadeira.
Proposicao composta e a uniao de
proposicoes simples
por meio de um conector logico. Este conector ira ser decisivo para o
valor logico
da expressao.
Em expressoes que utilizam varios operadores nao e possivel saber qual proposicao deve-se resolver primeiro.
Exemplo: P Λ Q V R.
Com isso, usar parenteses e fundamental. A expressao do exemplo poderia ficar assim: (P Λ Q) V R ou P Λ (Q V R).
A ordem da precedencia de operadores e:
- (), {}
- ￢
- Λ, V,
V
- →
- ↔
A tabela verdade e construida para determinar o valor logico de uma proposicao composta. Segue uma excelente estrategia para a construcao desta.
Exemplo de construcao da tabela verdade da proposicao composta:
p Λ q
Primeiramente verifica-se quantas “variaveis”, ou proposicoes simples que temos na proposicao composta do exercicio. Neste caso existem duas:
p
e
q
.
Em seguida elevamos 2 ao numero de variaveis, ou seja, 2². Nossa base do expoente e 2 pelo fato de possuir-se apenas 2 valores logicos possiveis nas proposicoes (Verdadeiro ou Falso). O resultado de 2² e 4. Entao nossa tabela tera 4 linhas, nessas linhas estarao todos os valores logicos possiveis da nossa proposicao composta.
| p
|
q
|
p Λ q
|
| -
|
-
|
-
|
| -
|
-
|
-
|
| -
|
-
|
-
|
| -
|
-
|
-
|
Esta e a estrutura da tabela, agora para a preencher com os devidos valores logicos utiliza-se a seguinte tecnica: ate a metade da primeira coluna coloca-se Verdadeiro, na outra metade Falso. Ja na segunda coluna, intercala-se V e F. Desta forma adquira-se a seguinte tabela:
| p
|
q
|
p Λ q
|
| V
|
V
|
Resultado
|
| V
|
F
|
Resultado
|
| F
|
V
|
Resultado
|
| F
|
F
|
Resultado
|
Esta e uma das melhores estrategias para a montagem de uma tabela verdade.
Proposicoes podem ser ligadas entre si por meio de conectivos logicos. Conectores que criam novas sentencas mudando ou nao seu valor logico (Verdadeiro ou Falso). Exemplos dos principais conectores logicos:
- “￢” ou “~” (negacao);
- “Λ” (conectivo “e”);
- “V” (conectivo “ou”);
- “→” (conectivo “se, entao”);
- “↔” (conectivo “se, e somente se”);
- “
V
” (conectivo “ou exclusivo”);
- “↓” (conectivo “negacao conjunta”);
- “↑” (conectivo “negacao disjunta”).
Exemplos de sentencas formadas com conectores e proposicoes:
(2 + 2 = 4)
V
(1 < 4) - Valor logico da sentenca: Verdadeiro
V (ou)
Verdadeiro = Verdadeiro
Cachorro e um felino
Λ
(1 > 0) - Valor logico da sentenca: Falso
Λ (e)
Verdadeiro = Falso
O conectivo de negacao (~), nega o valor logico de uma proposicao. Considera-se p como uma proposicao de valor logico igual a verdadeiro, entao sua negacao e igual a falso. O mesmo seria se a proposicao tivesse valor logico inicial igual a falso, sua negacao seria igual a verdadeiro. De acordo com esses conceitos podemos montar a seguinte tabela verdade:
Exemplo:
Considere
p
com o valor da seguinte proposicao: 2 e um numero par.
p = Verdadeiro, portanto sua negacao: ~p = Falso.
O
conectivo e
, tambem conhecido como AND e representado pelo simbolo “^” junta proposicoes as quais somente resultarao em Verdadeiro se todos os valores forem Verdadeiros.
Exemplo: Considere as proposicoes
p
e
q
(Conjuncao).
| p
|
q
|
p Λ q
|
| V
|
V
|
V
|
| V
|
F
|
F
|
| F
|
V
|
F
|
| F
|
F
|
F
|
Observacao: Veja que nesta tabela consideramos todos os valores logicos possiveis para p e q, em outras palavras: temos 2 proposicoes e estamos em uma base binaria (0 ou 1, verdadeiro ou falso) entao para se saber o numero das possibilidades para essas proposicoes realiza-se o seguinte calculo 2
n
, onde n e o numero de proposicoes.
O
conectivo ou
, tambem conhecido como OR e representado pelo simbolo “V” une proposicoes que, apenas uma sendo Verdadeiro e suficiente que a expressao inteira tambem seja.
Exemplo:
Considere as proposicoes
p
e
q
(Disjuncao).
| p
|
q
|
p V q
|
| V
|
V
|
V
|
| V
|
F
|
V
|
| F
|
V
|
V
|
| F
|
F
|
F
|
O
conectivo condicional
, representado pelo simbolo “→” une proposicoes criando uma estrutura condicional onde apenas uma das possibilidades resulta em F o valor logico da expressao.
Exemplo:
Considere as proposicoes
p
e
q
(Condicao). “Se
p
entao
q
”
| p
|
q
|
p → q
|
| V
|
V
|
V
|
| V
|
F
|
F
|
| F
|
V
|
V
|
| F
|
F
|
V
|
Observacao: nao devemos confundir a operacao condicional “→” com o relacao implica " => " , pois, enquanto o primeiro representa uma operacao entre proposicoes dando origem a uma outra proposicao, o segundo indica apenas uma relacao entre proposicoes dadas.
Relacao de implicacao ( => ):
uma proposicao p
implica
q quando em sua tabelas-verdade, nao pode ocorrer 1 e 0 nessa ordem.
p
nao Implica
q, pois, na segunda linha aparece p = V e q = F.
O
conectivo bicondicional
, e lido como “se, e somente se” e e representado pelo simbolo “↔”, ele une proposicoes onde o resultado logico da expressao e verdadeiro apenas se os valores logicos forem iguais.
Exemplo:
Considere as proposicoes
p
e
q
(bicondicional).
“Se
p
, e somente se
q
”
| p
|
q
|
p ↔ q
|
| V
|
V
|
V
|
| V
|
F
|
F
|
| F
|
V
|
F
|
| F
|
F
|
V
|
O
conectivo ou exclusivo
, chamado tambem de disjuncao exclusiva, e representado pelo simbolo “
V
”. Podemos dizer que ele significa: um ou outro, mas nao ambos. Exemplo: Ou o gato e macho ou o gato e femea, mas nao ambos. A tabela verdade do ou exclusivo esta representada abaixo.
| p
|
q
|
p
V
q
|
| V
|
V
|
F
|
| V
|
F
|
V
|
| F
|
V
|
V
|
| F
|
F
|
F
|
A negacao disjunta e representada pelo conector ↑, significa a negacao de duas proposicoes envolvendo o conector
E
(
NAND
).
Exemplo: p ↑ q ⇔ ￢(p Λ q) ⇔ ￢p v ￢q.
A negacao conjunta e representada pelo conector ↓, significa a negacao de duas proposicoes envolvendo o conector
OU
(
NOR
).
Exemplo: p ↓ q ⇔ ￢(p v q) ⇔ ￢p Λ ￢q.
Abaixo estao representadas as tabelas verdades das duas negacoes.
- Tabela verdade equivalente ao circuito
NAND
| p
|
q
|
p ↑ q
|
| V
|
V
|
F
|
| V
|
F
|
V
|
| F
|
V
|
V
|
| F
|
F
|
V
|
- Tabela verdade equivalente ao circuito
NOR
| p
|
q
|
p ↓ q
|
| V
|
V
|
F
|
| V
|
F
|
F
|
| F
|
V
|
F
|
| F
|
F
|
V
|
Ao montarmos uma tabela verdade contendo todos os valores logicos possiveis de uma expressao a poderiamos classificar em tautologia, contradicao e contingencia.
- Tautologia: e uma proposicao cujo resultado final e sempre verdadeiro.
Exemplo:
p v ~p (
p
OU
nao p
)
Veja que independente do valor de p a expressao sempre resulta em Verdadeiro, pois para o conector OU possuir um verdadeiro ja e suficiente para resultar em Verdadeiro, alem disso sempre teremos V em todas as combinacoes da expressao. Por isso a classificamos como uma tautologia.
Vejamos outro exemplo:
F → p (
F
entao
p
)
| Valor logico constante
|
p
|
F → p
|
| F
|
F
|
V
|
| F
|
V
|
V
|
Neste outro caso tambem se obteve uma tautologia, devido ao fato da ultima coluna da tabela (resultado da expressao) ter somente Verdadeiro.
- Contradicao: e uma proposicao que resulta somente em falso, em outras palavras, a ultima coluna da sua tabela so possui o valor logico falso.
Exemplo:
p ^ ~p
- Contingencia: determinamos uma proposicao de contingente quando ela nao e tautologica nem contraditoria, ou seja, ela e indeterminada.
Exemplo:
p V q (
p
OU
q
)
| p
|
q
|
p V q
|
| V
|
V
|
V
|
| V
|
F
|
V
|
| F
|
V
|
V
|
| F
|
F
|
F
|
Percebe-se que a ultima coluna nao possui apenas um valor logico, por isso a determinamos uma proposicao contingente, ou indeterminada.
Sejam P e Q duas proposicoes. Diremos que P implica logicamente a proposicao Q, se Q for verdadeiro sempre que P for verdadeiro. Quando isso ocorre, dizemos que temos uma implicacao logica ou inferencia e denotamos: P => Q (lemos: “P implica Q”).
Exemplo: P Λ Q implica P V Q?
| p
|
q
|
p Λ q
|
p V q
|
| V
|
V
|
V
|
V
|
| V
|
F
|
F
|
V
|
| F
|
V
|
F
|
V
|
| F
|
F
|
F
|
F
|
Neste exemplo podemos dizer que P Λ Q => P V Q, pois onde P Λ Q e verdadeiro P V Q tambem e.
Exemplo: P V Q implica P → Q?
| p
|
q
|
p V q
|
p → q
|
| V
|
V
|
V
|
V
|
| V
|
F
|
V
|
F
|
| F
|
V
|
V
|
V
|
| F
|
F
|
F
|
V
|
Neste exemplo nao podemos dizer que P V Q => P → Q, pois temos na segunda linha que onde P V Q e verdadeiro P → Q e falso.
Diremos que P e equivalente a Q, se as duas tabelas verdade foram identicas. Quando isso ocorre, dizemos que temos uma equivalencia logica ou bi-implicacao e denotamos P ⇔ Q (lemos: “P e equivalente a Q”).
Exemplo: ￢(P Λ Q) e equivalente a (￢P V ￢Q)?
| P
|
Q
|
￢P
|
￢Q
|
P Λ Q
|
￢(P Λ Q)
|
￢P V ￢Q
|
| V
|
V
|
F
|
F
|
V
|
F
|
F
|
| V
|
F
|
F
|
V
|
F
|
V
|
V
|
| F
|
V
|
V
|
F
|
F
|
V
|
V
|
| F
|
F
|
V
|
V
|
F
|
V
|
V
|
Neste exemplo podemos dizermos que ￢(P Λ Q) ⇔ (￢P V ￢Q), pois o resultado da tabela verdade das duas expressoes e o mesmo.
Exemplo: P → Q e equivalente a Q → P?
| P
|
Q
|
P → Q
|
Q → P
|
| V
|
V
|
V
|
V
|
| V
|
F
|
F
|
V
|
| F
|
V
|
V
|
F
|
| F
|
F
|
V
|
V
|
Neste exemplo nao podemos dizer que P → Q ⇔ Q → P, pois o resultado das tabelas verdades das expressoes sao diferentes, nas linhas 2 e 3.
Temos uma
condicao suficiente
se quando ela ocorrer temos a garantia de que a outra condicao ocorrera. Por exemplo:
“Se o cavalo corre entao ele esta vivo.”
O cavalo correr e condicao suficiente para ele estar vivo, ou seja, se o cavalo corre podemos garantir que ele esta vivo.
Por outro lado o cavalo estar vivo nao garante que o cavalo corra, pois ele pode estar por exemplo vivo mas descansando, a este tipo de condicao da se o nome de
condicao necessaria
. Uma condicao e necessaria quanto nao podemos garantir que a outra condicao e valida.
Esta relacao entre condicao suficiente e condicao necessaria e encontrada quando utilizamos um conector condicional, ou seja, quando temos uma estrutura condicional. O primeiro argumento(que vem antes do →), chamado de antecedente e uma condicao suficiente. O segundo argumento, chamado de consequente e uma condicao necessaria.
Entretanto em uma estrutura bicondicional temos uma proposicao
necessaria e suficiente
,.
Pegamos uma condicional qualquer como p → q, existem tres tipos de proposicoes associadas a ela que sao:
- Reciproca: a proposicao reciproca de p → q e a proposicao q → p. Como podemos ver foi feito uma troca entre a antecedente (p) e a consequente (q) para obter-se a reciproca cuja tabela esta abaixo:
| p
|
q
|
p → q
|
q → p
|
| V
|
V
|
V
|
V
|
| V
|
F
|
F
|
V
|
| F
|
V
|
V
|
F
|
| F
|
F
|
V
|
V
|
Exemplo: “Se a Maria e feia entao todos sao feios.”
A reciproca seria: “Se todos sao feios entao Maria e feia.”
- Inversa: a proposicao contraria de p → q e a proposicao ~p → ~q. Basta negar a antecedente(p) e a consequente(q) para obtermos a proposicao inversa.
| p
|
q
|
~p
|
~q
|
p → q
|
~p → ~q
|
| V
|
V
|
F
|
F
|
V
|
V
|
| V
|
F
|
F
|
V
|
F
|
V
|
| F
|
V
|
V
|
F
|
V
|
F
|
| F
|
F
|
V
|
V
|
V
|
V
|
Exemplo: “Se a Maria e feia entao todos sao feios.”
A inversa seria: “Se Maria nao e feia entao todos nao sao feios.”
- Contra positiva: a contra positiva da preposicao p → q e ~q → ~p. Para encontramos a contra positiva basta juntar os passos da reciproca e da contraria, ou seja, deve se inverter os lugares do antecedente e do consequente e negar ambos. A proposicao contra positiva tem o mesmo resultado que a proposicao original.
| p
|
q
|
~p
|
~q
|
p → q
|
~q → ~p
|
| V
|
V
|
F
|
F
|
V
|
V
|
| V
|
F
|
F
|
V
|
F
|
F
|
| F
|
V
|
V
|
F
|
V
|
V
|
| F
|
F
|
V
|
V
|
V
|
V
|
Exemplo: “Se a Maria e feia entao todos sao feios.”
A contra positiva seria: “Se todos nao sao feios entao Maria nao e feia.”
Referencias
- ↑
Undergraduate texts include Boolos, Burgess, and Jeffrey
(2002)
, Enderton
(2001)
, and Mendelson
(1997)
. A classic graduate text by Shoenfield
(2001)
first appeared in 1967.
- Carlos Fontes. Definicao e Evolucao da Logica; 28 de abril de 2012. Disponivel em:
web.archive.org - afilosofia.no.sapo.pt
- Grupo iPED. Nocoes de logica. Colegio web; 7 de maio de 2012. Disponivel em:
colegioweb.com.br
- GERONIMO, Joao Roberto; FRANCO Valdeni Soliane. Fundamentos de matematica: uma introducao a logica matematica, teoria dos conjuntos, relacoes e funcoes. 2º Edicao 2008.
Areas da matematica
|
|---|
| Areas
| |
|---|
| Divisoes
| |
|---|