Lógica Matemática

Noções de Lógica Matemática [2]

nenhum

TAUTOLOGIA E CONTRA -TAUTOLOGIA

· TAUTOLOGIA ou FÓRMULA LOGICAMENTE VÁLIDA : Fórmula que possui apenas valor V em sua tabela verdade. Exemplo : p Ú~ p

p ~ p p Ú ~ p
1 V F     V
2 F V     V

 

· CONTRA-TAUTOLOGIA ou FÓRMULA LOGICAMENTE FALSA: Fórmula que possui apenas valor F em sua tabela verdade. Exemplo : p Ù ~ p

 

p ~ p p Ù ~ p
1 V F      F
2 F V     F

 

· CONTINGENTE ou INDETERMINADA: Fórmula que possui valores V e F em sua tabela verdade.
Exemplo : p ® q

p q p ® q
1 V V
V
2 V F
F
3 F V
V
4 F F
V

· REGRAS DE INFERÊNCIA.: A fórmula a implica tautologicamente a fórmula b e indicamos a Þ bse e somente se a fórmula a®bé uma tautologia .

Regras Fórmulas Atômicas Fórmulas Compostas
Modus Ponens  MP p Ù (p ® q) Þ q A, A® B / B
Modus Tollens MT ~ q Ù ( p ® q ) Þ ~ p ~ B, A® B / ~ A
Silogismo Hipotético SH (p® q) Ù ( q ® r) Þ (p ® r) A ® B, B ® C / A ® C
Silogismo Disjuntivo SD (p Ú q) Ù ~ p Þ q ~ A, A Ú B / B
Simplificação SM p Ù q Þ p A Ù B / A
Adição AD p Þ p Ú q A / A Ú B
Eliminação EL (p ® (q Ú r) ) Ù~ q Þ p ®r ~ B , (A ® (BÚ C) / A ® C
Prova por Casos CS (p ® r) Ù ( q ® r) Þ (p Ú q) ® r A ® C, B ® C / (A Ú B ) ® C

· EQUIVALÊNCIAS TAUTOLÓGICAS : As fórmulas a e b são tautologicamente equivalentes e indicamos aÛbse e somente se a fórmula a«bé uma tautologia

Comutativa  p Ù q Û q Ù p p Ú q Û q Ú p
Associativa  (p Ù q)Ù r Û p Ù (q Ù r)  (p Ú q)Ú r Û pÚ (qÚ r)
Idempotente p Ù p Û p p Ú p Û p
Propriedades de V  p Ù V Û p  p Ú V Û V
Propriedades de F  p Ù F Û F p Ú F Û p
Absorção  p Ù ( p Ú r ) Û p p Ú (p Ù r) Û p
Distributivas p Ù (q Ú r) Û (p Ù q ) Ú (p Ù r) p Ú (q Ù r) Û (p Ú q ) Ù (p Ú r)
Distributivas p ® (q Ù r) Û (p® q) Ù (p ® r) p ® (q Ú r) Û (p® q) Ú (p ® r)
Leis de De Morgan ~ (p Ù q) Û~ p Ú ~ q ~ (p Ú q) Û~ p Ù ~ q
Def. implicação p ® q Û ~p Ú q p ® q Û ~ ( p Ù~ q)
Def. bicondicional p « q Û (p ® q) Ù ( q ® p)  p « q Û (~p Ú q) Ù (~q Úp)
Negação ~ (~ p) Û p  
Contraposição p ® q Û ~ q ®~ p  
Exportação(Þ ) Importação (Ü )  (p Ù q) ® r Û p ® ( q ® r )
Troca de Premissas p ® (q ® r ) Û q ® ( p ®r )  

Exemplo : Dadas as fórmulas A: p ® (q Ù r) e B : ~(q Ù r ) ®~ p vamos verificar que A Þ B ou ainda que A / B. Basta verificar, com o uso das tabelas verdade, que A ® B é tautologia.
   p      q        r        ( p ® (q Ù r)) ®(~ (q Ù r ) ® ~ p)

V V V V V V
V V F F V F
V F V F V F
V F F F V F
F V V V V V
F V F V V V
F F V V V V
F F F V V V

Neste exemplo, A Û B pois A « B é tautologia.

As TAUTOLOGIAS são infinitas e desempenham um importante papel nos processos de dedução no Cálculo Proposicional como veremos em próximos tópicos.

FORMAS NORMAIS CONJUNTIVA E DISJUNTIVA

Algumas EQUIVALÊNCIAS TAUTOLÓGICAS dadas acima nos permitem transformar qualquer fórmula em uma fórmula logicamente equivalente, que não contenha os conectivos ®e « , transformando-a em uma FORMA NORMAL CONJUNTIVA (FNC) ou em uma FORMA NORMAL DISJUNTIVA (FND)como segue:

1. substitui-se fórmulas: A® B por ~A Ú B e A « B por (~ A Ú B) Ù (~ B Ú A)
2. elimina-se a negação que precede os parênteses substituindo-se:
~(A Ù B) por ~A Ú~ B e ~(AÚ B) por ~A Ù~ B .
3. eliminam-se as negações múltiplas substituindo ~(~ A) por A.
4. elimina-se o alcance dos conectivos substituindo

para obter a FNC : A Ú (B Ù C) por (A Ú B) Ù (A Ú C)
para obter a FND : A Ù (B Ú C) por (A Ù B) Ú (A Ù C)

Deste modo, uma fórmula está em FORMA NORMAL CONJUNTIVA: FNC ou em FORMA NORMAL DISJUNTIVA: FND se, e somente se:

1. No máximo contém os conectivos~, Ù , Ú.
2. A negação ~ não tem alcance sobre os conectivos Ù e Ú .
3. Não aparecem negações sucessivas.
4. O conectivo Ú não tem alcance sobre Ù na FNC e, o conectivo Ù não tem alcance sobre Ú na FND.

Exemplos:    FNC : (~ p Ú q) Ù (r Ú s Ú p)
                     FND : p Ú (q Ù r) Ú (~ s Ù p)

Exemplo: Determine uma FND e uma FNC equivalente à fórmula
                 ((p Ú q) Ù~ q) ® ( r Ù q) .

1. ((p Ú q) Ù ~ q) ® ( r Ù q) Fórmula dada
2. ~ ((p Ú q) Ù~ q) Ú ( r Ù q) 1. Def. de Implicação
3. (~ (p Ú q) Ú~~ q) Ú (r Ù q) 2. De Morgan
4. (~ p Ù ~ q) Ú q Ú (r Ù q ) 3. Negação e De Morgan
5. (~ p Ù ~ q) Ú q Ú (r Ù q ) 4.FND
6. ((~ p Ú q) Ù (~ q Ú q)) Ú (r Ù q) 5. Distributiva
7. ((~ p Ú q) Ù V) Ú (r Ù q) 6. Tautologia
8. (~ p Ú q) Ú ( r Ù q) 7. Propriedade de V
9. (~ p Ú q Ú r) Ù (~ p Ú q Ú q) 8. Distributiva
10. (~ p Ú q Ú r) Ù (~ p Ú q ) 9. Idempotente e FNC

PROBLEMA DE POST

Como já  observamos podemos construir a tabela verdade de uma fórmula conhecidos os valores verdade das fórmulas que a compõem. O problema recíproco se coloca : para toda tabela verdade, existe uma fórmula que a determina? Este problema é conhecido como PROBLEMA DE POST (Emil Leon Post 1888-1995) e pode ser resolvido obtendo-se uma FNC ou uma FND que satisfaça a tabela verdade dada.

· Para se obter uma FND:

1. Observamos todas as linhas da tabela que possuem V na última coluna;
2. Construimos para cada uma destas linhas as conjunções correspondentes;
3. Fazemos a disjunção destas conjunções obtendo uma fórmula em FND que satisfaz a tabela verdade.

Exemplo: Determine uma fórmula que satisfaça a tabela verdade abaixo:
                                                                  p         q         ?

 

V V V (p Ù q)
V F F  
F V F
F F V (~ p Ù ~ q)

Resposta: Fórmula obtida (p Ù q) Ú (~ p Ù~ q) FND

· Para se obter uma FNC:

1. Observamos todas as linhas da tabela que possuem F na última coluna;
2. Construimos para cada uma destas linhas as disjunções correspondentes;
3. Fazemos a conjunção destas disjunções obtendo uma fórmula em FNC que satisfaz a tabela verdade.

Exemplo: Determine uma fórmula que satisfaça a tabela verdade abaixo:
                                                                     p        q       ?

 

V V V
V F F ~ p Ú q
F V F    p Ú ~ q
F F V

Resposta: Fórmula obtida (~ p Ú q) Ù (p Ú ~ q) FNC

As FND e FNC obtidas como acima são completas ou seja, em cada disjuncto (FND) ou em cada conjuncto (FNC) todas as variáveis proposicionais estão presentes.

Fonte: CELINA ABAR > http://www.pucsp.br

Noções de Lógica Matemática [1]

nenhum

CÁLCULO PROPOSICIONAL
Como primeira e indispensável parte da Lógica Matemática temos o CÁLCULO PROPOSICIONAL ou CÁLCULO SENTENCIAL ou ainda CÁLCULO DAS SENTENÇAS.

CONCEITO DE PROPOSIÇÃO

PROPOSIÇÃO: sentenças declarativas afirmativas (expressão de uma linguagem) da qual tenha sentido afirmar que seja verdadeira ou que seja falsa.

 

· A lua é quadrada.
· A neve é branca.
· Matemática é uma ciência.

 

Não serão objeto de estudo as sentenças interrogativas ou exclamativas.

 

OS SÍMBOLOS DA LINGUAGEM DO CÁLCULO PROPOSICIONAL

· VARIÁVEIS PROPOSICIONAIS: letras latinas minúsculas p,q,r,s,…. para indicar as proposições (fórmulas atômicas) .
Exemplos:

A lua é quadrada : p
A neve é branca : q

 

· CONECTIVOS LÓGICOS: As fórmulas atômicas podem ser combinadas entre si e, para representar tais combinações usaremos os conectivos lógicos :

Ù : e , Ú: ou, ®: se…então, «: se e somente se , ~: não

Exemplos:

·A lua é quadrada e a neve é branca. : p Ù q (p e q são chamados conjunctos)

 

· A lua é quadrada ou a neve é branca. : p Ú q ( p e q são chamados disjunctos)

 

· Se a lua é quadrada então a neve é branca. : p ® q ( p é o antecedente e q o conseqüente)

 

· A lua é quadrada se e somente se a neve é branca. : p « q

 

· A lua não é quadrada. : ~p

· SÍMBOLOS AUXILIARES : ( ) , parênteses que servem para denotar o “alcance” dos conectivos;

Exemplos:

· Se a lua é quadrada e a neve é branca então a lua não é quadrada. :
((p Ù q) ® ~ p)

· A lua não é quadrada se e somente se a neve é branca. :
((~ p) «q))

· DEFINIÇÃO DE FÓRMULA :

1. Toda fórmula atômica 

é uma fórmula.

2. Se A 

e  B 

são fórmulas então (A Ú B)

 , (A Ù B)

, (A ® B)

 , (A « B) 

e (~ A) 

também são fórmulas.3. São fórmulas apenas as obtidas por 1. e 2. .Os parênteses serão usados segundo a seguinte ordem dos conectivos: ~, Ú , Ù , ®, « .

Com o mesmo conectivo adotaremos a convenção pela direita.

Exemplo: a fórmula p Ú q Ù ~ r ® p ® ~ q deve ser entendida como

                  (((p Ú q) Ù (~ r)) ® ( p ® (~ q)))

 

AS TABELAS VERDADE

A lógica clássica é governada por três princípios (entre outros) que podem ser formulados como segue:

 

· Princípio da Identidade: Todo objeto é idêntico a si mesmo.

 

· Princípio da Contradição: Dadas duas proposições contraditórias (uma é negação da outra), uma delas é falsa.

 

· Princípio do Terceiro Excluído: Dadas duas proposições contraditórias, uma delas é verdadeira.

 

Com base nesses princípios as proposições simples são ou verdadeiras ou falsas – sendo mutuamente exclusivos os dois casos; daí dizer que a lógica clássica é bivalente.

 

Para determinar o valor (verdade ou falsidade) das proposições compostas (moleculares), conhecidos os valores das proposições simples (atômicas) que as compõem usaremos tabelas-verdade :

 

1.Tabela verdade da “negação” : ~p é verdadeira (falsa) se e somente se p é falsa (verdadeira).

 

 

p ~p
V F
F V

 

2. Tabela verdade da “conjunção” : a conjunção é verdadeira se e somente os conjunctos são verdadeiros.

 

 

p
q
p Ù q
V
V
V
V
F
F
F
V
F
F
F
F

 

3. Tabela verdade da “disjunção” : a disjunção é falsa se, e somente, os disjunctos são falsos.

 

 

p
q
p Ú q
V
V
V
V
F
V
F
V
V
F
F
F

 

4. Tabela verdade da “implicação”: a implicação é falsa se, e somente se, o antecedente é verdadeiro e o conseqüente é falso.

 

 

p
q
p ® q
V
V
V
V
F
F
F
V
V
F
F
V

 

5. Tabela verdade da “bi-implicação”: a bi-implicação é verdadeira se, e somente se seus componentes são ou ambos verdadeiros ou ambos falsos

 

 

p
q
p « q
V
V
V
V
F
F
F
V
F
F
F
V

 

Exemplo: Construir a tabela verdade da fórmula : ((p Ú q) ® ~p) ® (q Ù p)

 

 

p
q
      ((p Ú q) ® ~p) ® (q Ù p) 
V
V
V
F
F
V
 V
V
F
V
F
F
V
 F
F
V
V
V
V
F
 F
F
F
F
V
V
F
 F

 

· NÚMERO DE LINHAS DE UMA TABELA-VERDADE: Cada proposição simples (atômica) tem dois valores V ou F, que se excluem. Para n atômicas distintas, há tantas possibilidades quantos são os arranjos com repetição de 2 (V e F) elementos n a n. Segue-se que o número de linhas da tabela verdade é 2n. Assim, para duas proposições são 22 = 4 linhas; para 3 proposições são 23 = 8; etc.

Exemplo: a tabela – verdade da fórmula ((p Ù q) ® r) terá 8 linhas como segue :

 

 

p
q
r
((p Ù q) ® r )
V
V
V
V      V
V
V
F
V      F
V
F
V
F     V
V
F
F
F     V
F
V
V
F     V
F
V
F
F     V
F
F
V
F     V
F
F
F
F     V

 

NOTA: “OU EXCLUSIVO” É importante observar que “ou” pode ter dois sentidos na linguagem habitual: inclusivo (disjunção) Ú (“vel”)  e exclusivo Ú  ( “aut”) onde p Ú q significa ((p Ú q) Ù~ (p Ù q)).

 

p
q
 ((p Ú q) Ù ~ (p Ù q))
V
V
        V       F  F     V
V
F
         V      V  V     F
F
V
         V      V  V     F
F
F
         F       F V     F

Fonte: CELINA ABAR > http://www.pucsp.br