Fundamentos Da Logica

Fundamentos da LgicaLgica Proposicional

Antonio Alfredo Ferreira [email protected]

Olga Nikolaevna [email protected]

UFMG/ICEx/DCC MD Fundamentos da Logica Logica Proposicional 1

Fundamentos da lgica:Alguns fatos histricos

Aristteles (384 a.C.322 a.C.), fil-sofo grego. Produziu uma obra rica emultifacetada. Nela encontramos umaexaustiva compilao dos conhecimen-tos do seu tempo, mas tambm, umafilosofia que ainda hoje influncia anossa maneira de pensar.

Responsvel por escrever os primei-ros grandes trabalhos de lgica: Coleo de regras para raciocnio

dedutivo que pode ser usado emqualquer rea do conhecimento.

Gottfried Wilhelm Leibniz (16461716),filsofo e matemtico alemo, provavel-mente mais conhecido por ter inventadoo clculo integral e diferencial indepen-dentemente de Isaac Newton.

Prope o uso de smbolos para meca-nizar o processo de raciocnio dedu-tivo.

George Boole(18151864),matemticoe filsofoingls.

AugustusDe Morgan(18061871),matemticoingls.

Propem as bases da lgica simblicamoderna usando as idias de Leibniz.


Fundamentos da lgica:Atualidade

Pesquisa continua sendo aplicada em reas como: inteligncia artificial; projeto de circuito lgico; teoria de autmatos e computabilidade; teoria de bancos de dados relacionais; teoria de linguagens; teoria de sistemas distribudos.


Forma de um Argumento Seu Contedo

Forma de um argumento: conceito central da lgica dedutiva. Argumento: sequncia de afirmaes para demonstrar a validade de uma

assero.

Como saber que a concluso obtida de um argumento vlida? As afirmaes que compem o argumento

so aceitas como vlidas, ou podem ser deduzidas de afirmaes anteriores.

Em lgica, forma de um argumento 6= seu contedo. Anlise lgica no determina a validade do contedo de um argumento. Anlise lgica determina se a verdade de uma concluso pode ser obtida

da verdade de argumentos propostos.

Lgica: Cincia do Raciocnio.UFMG/ICEx/DCC MD Fundamentos da Logica Logica Proposicional 4


Exemplo 1:se a sintaxe de um programa est errada ouse a execuo do programa resulta em diviso por zeroento o computador ir gerar uma mensagem de erro.... Computador no gera mensagem de erro

Sintaxe do programa est correta eExecuo do programa no resulta em diviso por zero.

Exemplo 2:se x R | x < 2 ou x > 2ento x2 > 4.... x2 4

x 2 e x 2.



Nos exemplos, temos que o contedo dos argumentos diferente. No entanto, a forma lgica a mesma:

se p ou qento r.... no r

no p e no q.

Argumentos na forma lgica so normalmente representados por letras mi-nsculas do alfabeto.Exemplo: p, q, r.

Em geral, as definies da lgica formal esto de acordo com a lgica naturalou intuitiva das pessoas de bom senso.

O formalismo introduzido para evitar ambiguidade e garantir consistncia.UFMG/ICEx/DCC MD Fundamentos da Logica Logica Proposicional 6

Proposies

Em toda teoria matemtica, usam-se termos j definidos na concepo denovas definies.

Mas como fazer com os termos mais primitivos? Termos primitivos ou iniciais no so definidos. Em lgica, os termos sentena, verdadeiro, e falso so os termos iniciais

no definidos.

Definio: uma afirmao ou proposio uma sentena que verdadeira(V) ou falsa (F) mas no ambas.

Exemplo 3: 2 + 2 = 4 2 + 2 = 5so proposies, onde a primeira V e a segunda F.


Proposies

Exemplo 4: Ele um estudante universitrio.no uma proposio j que depende da referncia ao pronome ele.

Exemplo 5: x + y > 0.tambm no uma proposio j que depende dos valores de x e y.

possvel transformar uma sentena como nos exemplos 4 ou 5 numa pro-posio? Sim, atravs de quantificadores, como ser visto em lgica de predicados.


Proposies compostas

Nos exemplos usados daqui para frente, usaremos as letras minsculas (porexemplo, p, q, r) para representar afirmaes.

Os seguintes smbolos podem ser usados para definir expresses lgicasmais complexas a partir de expresses mais simples: ou ou barra sobre a letra ou linha : nop lido como no p e chamado de negao de p.Outras formas: p, p, p

: ep q lido como p e q e chamado de conjuno de p e q.

: oup q lido como p ou q e chamado de disjuno de p e q.


Proposies compostas

um operador unrio e e so operadores binrios. Avaliao na seguinte ordem:

1. (negao);2. , (disjuno, conjuno).

Exemplo 6: p q = (p) q p q r ambguo.

Correto: (p q) r ou p (q r).


Proposies:Traduo de sentenas em linguagens natural e

algbrica para smbolos

Mas e No/nem . . . nemp = Est quente.q = Est ensolarado.

Exemplo 7:(a) No est quente mas est ensolarado.

Mas = ; p q.(b) No est quente nem ensolarado.

Nem A nem B = A B ; p q.


Proposies:Traduo de sentenas em linguagens natural e

algbrica para smbolos

e (), ou (), e desigualdadesSejam trs nmeros reais representados por a, b, e x. x a x < a x = a a x b x a x b 2 x 1 x 2 x 1, que F.

Sejam os predicados:p: x > 0; q: x < 3; r: x = 3.(a) x 3 q r(b) 0 < x < 3 p q(c) 0 < x 3 p (q r)


Proposies e os valores-verdade

Para uma sentena ser uma proposio necessrio ter um valor-verdadebem definido, i.e., V ou F.

Negao () e sua tabela da verdade:p pV FF V

Conjuno () e sua tabela da verdade:p q p qV V VV F FF V FF F F


Proposies e os valores-verdade

Disjuno ()Possveis significados: inclusive: p ou q ou ambos (significado assumido para este operador), e exclusivo: p ou q, mas no ambos.

p q p qV V VV F VF V VF F F


Proposies mais complexas

Exemplo 8:Construa a tabela da verdade para a expresso:

E = (p q) (p q)

p q p q p q (p q) EV V V V F FV F V F V VF V V F V VF F F F V F

E = p q = p xor q (ou exclusivo)

O ponto fundamental em assinalar valores-verdade para proposies com-postas que permite o uso da lgica para decidir a verdade de uma proposi-o usando somente o conhecimento das partes.

A lgica no ajuda a determinar a verdade ou falsidade de uma afirmao emsi, ou seja, seu contedo.UFMG/ICEx/DCC MD Fundamentos da Logica Logica Proposicional 15

Equivalncia lgica

As proposies p q e q p possuem os mesmos valores-verdade.p q p q q pV V V VV F F FF V F FF F F F

Por essa razo, p q e q p so equivalentes logicamente.

Definio: duas proposies P e Q so equivalentes logicamente se e so-mente se os valores-verdade obtidos forem idnticos para cada combinaopossvel das variveis que formam as proposies.


Equivalncia lgica

Como verificar se duas proposies P e Q so equivalentes logicamente?1. Construa a tabela da verdade para P .2. Construa a tabela da verdade para Q usando os mesmos valores de vari-

veis para as afirmaes que formam a proposio.3. Verifique se as tabelas da verdade de P e Q so idnticas para cada

combinao de valores-verdade. Se forem, P e Q so equivalentes logi-camente, caso contrrio no.

Exemplo 9: (p) p (p q) 6 p q


Equivalncia lgicaLeis de De Morgan

Negao de e : Leis de De Morgan.Sejam as afirmaes: p = Joo alto. q = Jos ruivo.A proposio p q verdadeira sse os componentes forem verdadeiros.

Quando a proposio falsa?Quando um dos componentes ou ambos forem falsos, i.e.,

(p q) p q

Mostre as seguintes equivalncias: (p q) p q (p q) p qEssas duas equivalncias so conhecidas como leis de De Morgan que foio primeiro a express-las em termos matemticos.UFMG/ICEx/DCC MD Fundamentos da Logica Logica Proposicional 18

Leis de De Morgan: Exemplos

Exemplo 10:p = Joo tem 2 m de altura e ele pesa pelo menos 90 kg.p = Joo no tem 2 m de altura ou ele pesa menos de 90 kg.Exemplo 11:p = x < 2p = x 6< 2 x 2Exemplo 12:p = 1 < x 4p = (1 < x 4) (x > 1 x 4)

x 6> 1 x 6 4 x 1 x > 4.Exemplo 13:p = Joo alto e Joo magro.p = Joo no alto ou Joo no magro.


Leis de De Morgan: Exemplos

Exemplo 14:t = Joo alto e magro.t = Joo no alto e magro.Em lgica formal os vocbulos e e ou so permitidos somente entre afirma-es completas e no entre partes de uma sentena.

Apesar das leis da lgica serem extremamente teis, elas devem ser usadascomo uma ajuda ao raciocnio e no como um substituto mecnico a inteli-gncia.

Equivalncia lgica muito til na construo de argumentos.


Tautologias e contradies

Uma tautologia uma proposio que sempre verdadeira independente dosvalores-verdade das afirmaes que compem a proposio.

Uma contradio uma proposio que sempre falsa independente dosvalores-verdade das afirmaes que compem a proposio.

De acordo com essas definies, a verdade de uma tautologia ou falsidadede uma contradio se devem a estrutura lgica da proposio em si e soindependentes dos significados das afirmaes que compem a proposio.


Tautologias e contradies

Mostre que a proposio p p uma tautologia e que a proposio p p uma contradio.

Se t uma tautologia e c uma contradio mostre que p t p e p c c


Sumrio da equivalncia lgica

Comutatividade p q q p p q q pAssociatividade (p q) r

p (q r)(p q) r p (q r)

Distributividade p (q r) (p q) (p r)

p (q r) (p q) (p r)

Identidade p t p p c pNegao p p t p p cDupla negao (p) pIdempotncia p p p p p pDe Morgan (p q)

p q(p q) p q

Limite universal p t t p c cAbsoro p (p q) p p (p q) pNegaes t c c t


Equivalncia lgica: Exemplo

Exemplo 15:Mostre que

(p q) (p q) patravs dos axiomas acima.


Proposio condicional ou Implicao

Sejam p e q proposies. Se p ento q (ou p implica q) representado simbolicamente por

p q. p chamado de hiptese e q de concluso.

Essa sentena chamada de condicional.

Sobre o uso tpico de uma proposio condicional ou implicao: Este tipo de sentena usado tanto em linguagem natural quanto em ra-

ciocnio matemtico para dizer que a verdade da proposio q (concluso)est condicionada verdade da proposio p (hiptese).

No entanto, uma proposio condicional (do ponto de vista matemtico) independente de uma relao causa-efeito entre hiptese e concluso.

Exemplo 16: Se (48 divisvel por 6)=[p] ento (48 divisvel por 3)=[q].


Proposio condicional

um conectivo lgico binrio para o qual podem ser definidos valores-verdade.

Determinando a tabela da verdade para (seento). A nica combinao em que a sentena condicional falsa quando a

hiptese V e a concluso F (por definio).

p q p qV V VV F FF V VF F V



Seja a seguinte sentena que descreve uma promessa:Se (voc se apresentar para trabalhar na segunda-feira pelamanh)=[p] ento (voc ter o emprego)=[q].

Em que situao o empregador no falou a verdade, ou seja, a promessa(sentena) falsa?

p = V q = F.

E se a afirmao p no for satisfeita? No justo dizer que a promessa falsa.


Proposio condicional e linguagem natural

Seja a seguinte implicao:Se hoje estiver ensolarado ento ns iremos praia.

Implicao tpica de uma conversao j que h uma relao entre ahiptese e a concluso.

Implicao no considerada vlida quando o dia estiver ensolarado e nsno formos praia.


Proposio condicional e linguagem natural

Seja a seguinte implicao:Se hoje sexta-feira ento 2 + 3 = 5.

Implicao que sempre verdadeira pela definio (tabela da verdade) daproposio condicional.

Por outro lado, a implicao:Se hoje sexta-feira ento 2 + 3 = 6.

verdadeira todos os dias da semana, exceto sexta-feira, apesar de2 + 3 6= 6, ou seja, a concluso ser sempre falsa.

Ns no usaramos essas implicaes em linguagem natural j que noexiste uma relao entre hiptese e concluso.

O conceito matemtico de implicao est baseado na tabela-verdade, ouseja, nos valores que a hiptese e a concluso podem assumir.



Prioridade para o conectivo lgico:

ltimo a ser avaliado em expresses que contm, , .

Exemplo 17:Construa a tabela da verdade para a sentena p q p.

p q q p q p p q pV V F V F FV F V V F FF V F F V VF F V V V V



Exemplo 18:Mostre que p q r (p r) (q r)

p q r p q p r q r p q r (p r) (q r)V V V V V V V VV V F V F F F FV F V V V V V VV F F V F V F FF V V V V V V VF V F V V F F FF F V F V V V VF F F F V V V V

Para todas as combinaes de valores-verdade de p, q e r, a expresso daesquerda tem o mesmo valor-verdade da direita.



possvel representar p q em termos dos conectivos , , ? Sim.

p q p q

Negao:(p q) (p q)

(p) q p q

Exemplo 19:

a: Se o (meu carro est na oficina)=[p] ento (eu no posso ir aula)=[q].a: (Meu carro est na oficina)=[p] e (eu posso ir aula)=[q].


Proposio condicional: Contrapositiva

A proposio contrapositiva de (p q) (q p).p q q p

Exemplo 20:

p q: Se hoje Pscoa ento amanh segunda-feira.q p: Se amanh no segunda-feira ento hoje no Pscoa.


Proposio condicional: Converse

Nota: A converse opinion or statement is one that is the opposite to the one thathas just been stated. Collins Cobuild English Language Dictionary.

O termo converse traduzido em Matemtica Discreta e suas Aplicaes, Kenneth H. Rosen, 6a edio,

por oposta, Fundamentos Matemticos para a Cincia da Computao, Judith L. Gers-

ting, 5a edio, por recproca. Matemtica Discreta, Seymour Lipschutz & Marc Lipson, 2a edio, porconversa.

Nesta disciplina, iremos usar a primeira traduo.

A proposio oposta de (p q) (q p).p q ? q p

No.


Proposio condicional: Inversa

A proposio inversa de (p q) (p q).p q ? p q

No.

Exemplo 21:

Original: Se hoje Pscoa ento amanh segunda-feira.Oposta: Se amanh segunda-feira ento hoje Pscoa.Inversa: Se hoje no Pscoa ento amanh no segunda-feira.


Proposio condicional e proposies derivadas:Sumrio

(p q) (q p) Proposio contrapositiva(p q) 6 (q p) Proposio oposta(p q) 6 (p q) Proposio inversa

(q p) (p q) contrapositivaoposta de (p q) inversa de (p q)


Proposio condicional:Somente se

A sentena p somente se q significa que (acrescentado verbos):p [pode ocorrer] somente se q [ocorre].

... Se q no ocorre ento p no pode ocorrer, i.e.,

Se q ento p Se p ento q ou p q.

Proposies condicionais: p somente se q 6 p se q. p somente se q p q. p se q q p.



Exemplo 22:(48 divisvel por 6)=[p] somente se (48 divisvel por 3)=[q] Se (48 divisvel por 6)=[p] ento (48 divisvel por 3)=[q].

Neste caso, a proposio condicional p q sempre verdadeira j que p eq sempre assumem o valor verdadeiro.

Suponha que x seja um nmero inteiro e a seguinte proposio:(x divisvel por 6)=[p] somente se (x divisvel por 3)=[q] Se (x divisvel por 6)=[p] ento (x divisvel por 3)=[q].

Claramente existem valores para x que fazem com que a proposio sejaverdadeira e outros que seja falsa.



Exemplo 23:A soma de 1 a n [n(n+1)2 ] somente se a soma de 1 a n+1 [

(n+1)(n+2)2 ]

Se a soma de 1 a n [n(n+1)2 ] ento a soma de 1 a n + 1 [

(n+1)(n+2)2 ]

Exemplo 24:Posso comprar o livro de MD somente se tenho dinheiro Se posso comprar o livro de MD ento tenho dinheiro.


Proposio condicional:Bicondicional (se somente se)

A sentena bicondicional entre p e q expressa comop se e somente se q

e representada porp q

e tem a seguinte tabela da verdade:

p q p qV V VV F FF V FF F V



O conectivo tem a mesma prioridade do conectivo.

Exemplo 25:Mostre que p q (p q) (q p)

p q p q q p p q (p q) (q p)V V V V V VV F F V F FF V V F F FF F V V V V



Exemplo 26:Este programa est correto se somente se ele produz a resposta cor-reta para todos os possveis valores de dados de entrada.

Reescrevendo como uma conjuno de duas sentenas seento:Se este programa est correto ento ele produz a resposta corretapara todos os possveis valores de dados de entrada

ese o programa produz a resposta correta para todos os possveis valo-res de dados de entrada ento ele est correto.



p q (p q) (q p).p q p q (p q) (q p) (p q) (q p)V V V V V VV F F F V FF V F V F FF F V V V V


Proposio condicional:Condio necessria & Condio suficiente

Sejam r e s afirmaes.

r uma condio suficiente para s: se r ento s.... A ocorrncia de r suficiente para garantir a ocorrncia de s.

r uma condio necessria para s: se no r ento no s

se s ento r.... Se r no ocorrer ento s tambm no pode ocorrer, i.e., a ocorrncia de r

necessria para se ter a ocorrncia de s.

A fraser uma condio necessria e suficiente para s significa r se somentese s.



Exemplo 27:Considere a sentena condicional p q:

Se Joo elegvel para votar ento ele tem pelo menos 16 anos.p: Joo elegvel para votar.q: Joo tem pelo menos 16 anos. A verdade de p suficiente para garantir a verdade de q, ou seja,

Joo ser elegvel para votar condio suficiente para que ele tenhapelo menos 16 anos.

A condio q necessria para a condio p ser verdadeira, ou seja,Joo ter pelo menos 16 anos condio necessria para que ele sejaelegvel para votar.



Exemplo 28:Converta uma condio suficiente para a forma seento O nascimento de Joo em solo brasileiro uma condio suficiente para

ele ser cidado brasileiro. Se Joo nasceu em solo brasileiro ento ele um cidado brasileiro.

Exemplo 29:Converta uma condio necessria para a forma seento Joo ter 35 anos uma condio necessria para ser presidente do Brasil. Se Joo no tem 35 anos ento ele no pode ser presidente do Brasil. Se Joo pode ser o presidente do Brasil ento ele j tem pelo menos 35

anos.


Argumentos vlidos e invlidos

Alguns fatos sobre argumentos do ponto de vista da matemtica e da l-gica: Um argumento no uma disputa. Um argumento uma sequncia de comandos que termina numa conclu-

so. Um argumento ser vlido significa que a concluso pode ser obtida

necessariamente das afirmaes que precedem.

Argumento (definio): Um argumento uma sequncia de afirmaes. Todas as afirmaes, exceto a ltima, so chamadas de premissas ou su-

posies ou hipteses. A ltima afirmao chamada de concluso. O smbolo .

.., que lido como de onde se conclui normalmente colo-

cado antes da concluso.


Argumentos vlidos e invlidos

Exemplo 30:

Se Scrates um ser humano ento Scrates mortal;Scrates um ser humano;

... Scrates mortal.

Forma simblica:Se p ento q;p;

... q. conveniente pensar em p e q como variveis que podem ser substitudas

por argumentos.

A forma de um argumento vlida ssepara todas as combinaes de argumentos que levam a premissasverdadeiras ento a concluso tambm verdadeira.

A verdade da concluso obtida analisando os valores-verdade da formalgica em si.


Argumentos vlidos e invlidos:Como analisar a validade

A validade da forma de um argumento pode ser feita seguindo os seguintespassos:

1. Identifique as premissas e concluso do argumento.2. Construa a tabela da verdade identificando as colunas das premissas e da

concluso.3. Identifique as linhas onde todas as premissas so verdadeiras (linhas crti-

cas).4. Para cada linha crtica verifique se a concluso do argumento verdadeira.

(a) Se for para todas as linhas crticas ento a forma do argumento vlida.(b) Se existir pelo menos uma linha crtica com concluso falsa ento a

forma do argumento invlida.



Exemplo 31:

p (q r);r;

... p q.

Tabela da verdade:

Premissas Conclusop q r q r p (q r) r p q

1. V V V V V F2. V V F V V V V3. V F V V V F4. V F F F V V V5. F V V V V F6. F V F V V V V7. F F V V V F8. F F F F F V

Para todas linhas crticas a concluso verdadeira. Logo, o argu-mento vlido.

Todas as linhas exceto as linhas crticas so irrelevantes para verificar a vali-dade de um argumento.UFMG/ICEx/DCC MD Fundamentos da Logica Logica Proposicional 50


Exemplo 32 argumento invlido:

p q r;q p r;

... p r; Premissas Concluso

p q r r q r p r p q r q p r p r1. V V V F V V V V V2. V V F V V F V F3. V F V F F V F V4. V F F V V F V V F5. F V V F V F V F6. F V F V V F V F7. F F V F F F V V V8. F F F V V F V V V

Para todas linhas crticas, exceto a 4, a concluso verdadeira. Logo, oargumento invlido.



Exemplo 33:

p q;q r;r p;

... p q r.

Tabela da verdade:

Premissas Conclusop q r p q q r r p p q r

1. V V V V V V V2. V V F V F V3. V F V F V V4. V F F F V V5. F V V V V F6. F V F V F V7. F F V V V F8. F F F V V V F

Existem duas linhas crticas, uma delas com concluso falsa. Logo, o argu-mento invlido.


Argumentos vlidos: Modus Ponens

Seja o seguinte argumento:p q;p;

... q.

e um exemplo dessa forma:Se o ltimo dgito de um no 0 ento este no divisvel por 10.

O ltimo dgito deste no 0.

... Este no divisvel por 10.

Um argumento vlido que tem essa forma chamado de modus ponens emLatim e que significa mtodo de afirmar.


Argumentos vlidos: Modus Ponens

Exemplo 34:

Forma do argumento:

p q;p;

... q.

Premissas Conclusop q p q p q

1. V V V V V2. V F F V3. F V V F4. F F V F


Argumentos vlidos: Modus Tollens

Seja o seguinte argumento:p q;q;

... p.

e um exemplo dessa forma:Se Zeus humano ento Zeus mortal. (1)

Zeus no mortal. (2)

... Zeus no humano.

Suponha que as afirmaes (1) e (2) sejam verdadeiras. Zeus deve ser necessariamente no-humano? Sim! Porque se Zeus fosse humano ento de acordo com (1) ele seria mortal. Mas por (2) ele no mortal. Dessa forma, Zeus no pode ser humano. Um argumento vlido que tem essa forma chamado de modus tollens em

Latim e que significa mtodo de negar.UFMG/ICEx/DCC MD Fundamentos da Logica Logica Proposicional 55

Argumentos vlidos: Exemplos

Exemplo 35:Se existem mais pssaros que ninhosento dois pssaros tero que chocar no mesmo ninho;

Existem mais pssaros que ninhos;

... Dois pssaros chocam no mesmo ninho.

; De acordo com modus ponens.

Exemplo 36:Se este no divisvel por 6ento o no divisvel por 2;

Este no no divisvel por 2;

... Este no no divisvel por 6.

; De acordo com modus tollens.


Outras formas de argumentos vlidos:Adio disjuntiva

As formas de argumentos(a) p;

... p q.

(b) q;... p q.

so vlidas.

Forma do argumento:p;

... p q.

Premissa Conclusop q p p q

1. V V V V2. V F V V3. F V F4. F F F

Essas duas formas servem para fazer generalizaes, i.e.,se p verdadeiro caso (a) ento mais genericamente p q verdadeiropara qualquer afirmao q.


Outras formas de argumentos vlidos:Simplificao conjuntiva

As formas de argumentos(a) p q;

... p.

(b) p q;... q.

so vlidas.

Forma do argumento:p q;

... p.

Premissa Conclusop q p q p

1. V V V V2. V F F3. F V F4. F F F

Essas duas formas servem para fazer particularizaes, i.e.,se p e q so verdadeiros ento em particular p verdadeiropara o caso (a).


Outras formas de argumentos vlidos:Silogismo disjuntivo

Silogismo = deduo formal tal que, postas duas premissas, delas se tira umaconcluso, nelas logicamente implicada.

As formas de argumentos(a) p q;

q;... p.

(b) p q;p;

... q.

so vlidas.Forma do argumento:

p q;q;

... p.

Premissas Conclusop q p q q p

1. V V V F2. V F V V V3. F V V F4. F F F V

Essas formas de argumento expressam a situao onde existem somenteduas possibilidades e uma pode ser excluda o que leva ao fato que a outradeve prevalecer.UFMG/ICEx/DCC MD Fundamentos da Logica Logica Proposicional 59

Outras formas de argumentos vlidos:Silogismo disjuntivo

Exemplo 37:Seja x um nmero inteiro e os seguintes argumentos:

p: x 3 = 0q: x + 2 = 0

p q: Um dos argumentos pode ser eliminado.q: x 6= 2. Sabe-se que x no negativo e por essa razo o argu-

mento a ser eliminado.

... p, de acordo com o silogismo disjuntivo.


Outras formas de argumentos vlidos:Silogismo hipottico

Forma do argumento:p q;q r;

... p r.

vlida.

Premissas Conclusop q r p q q r p r

1. V V V V V V2. V V F V F3. V F V F V4. V F F F V5. F V V V V V6. F V F V F7. F F V V V V8. F F F V V V

Muitos argumentos em matemtica so definidos por cadeias de sentenasseento, onde o primeiro implica no ltimo.


Outras formas de argumentos vlidos:Silogismo hipottico

Exemplo 38:

Se 18.486 divisvel por 18ento 18.486 divisvel por 9;

Se 18.486 divisvel por 9ento a soma dos dgitos de 18.486 divisvel por 9;

... Se 18.486 divisvel por 18

ento a soma dos dgitos de 18.486 divisvel por 9.


Outras formas de argumentos vlidos:Dilema: Prova por diviso em casos

Dilema = raciocnio cuja premissa alternativa, de tal forma que qualquer dosseus termos conduz mesma consequncia.

Forma do argumento:

p q;p r;q r;

... r.

vlida.

Premissas Conclusop q r p q p r q r r

1. V V V V V V V2. V V F V F F3. V F V V V V V4. V F F V F V5. F V V V V V V6. F V F V V F7. F F V F V V8. F F F F V V


Outras formas de argumentos vlidos:Dilema: Prova por diviso em casos

Exemplo 39:

x positivo ou x negativo;

Se x positivo ento x2 > 0;

Se x negativo ento x2 > 0;

... x2 > 0.

Neste caso j foi mostrado que existe uma dicotomia dos nmeros reais: po-sitivos, negativos ou zero. Por silogismo disjuntivo sabe-se x positivo ou x negativo e chega-se concluso acima.


Deduo mais complexa

Exemplo 40:

Voc est saindo para a escola de manh epercebe que no est usando os culos. Aotentar descobrir onde esto os culos voc co-mea a pensar sobre os seguintes fatos queso verdadeiros:

(a) Se os meus culos esto na mesa da co-zinha ento eu os vi no caf da manh;

(b) Eu estava lendo o jornal na sala de estarou eu estava lendo o jornal na cozinha;

(c) Se eu estava lendo o jornal na sala deestar ento meus culos esto na mesado caf;

(d) Eu no vi meus culos no caf da manh;(e) Se eu estava lendo um livro na cama en-

to meus culos esto no criado-mudo;(f) Se eu estava lendo o jornal na cozinha

ento meus culos esto na mesa da co-zinha;

Sejam os seguintes argumentos:

p = Os meus culos esto na mesa da cozi-nha.

q = Eu vi meus culos no caf da manh.r = Eu estava lendo o jornal na sala de estar.s = Eu estava lendo o jornal na cozinha.t = Meus culos esto na mesa do caf.u = Eu estava lendo um livro na cama.v = Meus culos esto no criado-mudo.

Traduo dos fatos para as proposies:

(a) p q (b) r s (c) r t(d) q (e) u v (f) s p


Deduo mais complexa

Traduo dos fatos para as proposies:

(a) p q (b) r s (c) r t(d) q (e) u v (f) s p

As seguintes dedues podem ser feitas:

1. p q; (a)q (d)

... p Modus Tollens

2. s p; (f)p Concluso de 1.

... s Modus Tollens

3. r s; (b)s Concluso de 2.

... r Silogismo disjuntivo

4. r t; (c)r Concluso de 3.

... t Modus Ponens

... t verdadeiro e os culos esto na mesa do caf.


Uso de proposies em especificaes

Traduzir sentenas numa linguagem natural, como o portugus, em expres-ses lgicas uma parte importante da especificao de sistemas computa-cionais (hardware e software).

Profissionais que fazem a especificao de tais sistemas computacionais de-vem traduzir requisitos expressos numa linguagem natural em uma especifi-cao precisa e no ambgua.

Essa especificao pode ser usada como base para o desenvolvimento dosistema.



Exemplo 41:

Requisito:(a) Uma resposta automtica no pode ser enviada se o sistema de arquivos

est cheio.

Proposies:a = Uma resposta automtica no pode ser enviada.b = O sistema de arquivos est cheio.

Traduo do requisito para a proposio:(a) b a



Exemplo 42:

Requisitos:(a) A mensagem de diagnstico armazenada no buffer ou a mensagem de

diagnstico retransmitida.(b) A mensagem de diagnstico no armazenada no buffer.(c) Se a mensagem de diagnstico armazenada no buffer ento a mensa-

gem de diagnstico retransmitida.

Proposies:p = A mensagem de diagnstico armazenada no buffer.q = A mensagem de diagnstico retransmitida.

Traduo dos requisitos para as proposies:(a) p q(b) p(c) p q



Dedues:p q; (a)p (b)

... q Silogismo disjuntivo

q Concluso acima

p (b)p q (c)

... p q p = F e q = V

Os requisitos so consistentes para p = F e q = V

O que acontece com a especificao se o requisito A mensagem de diag-nstico no retransmitida acrescentada?


Falcias

Falcia = erro no raciocnio que resulta num argumento invlido.

Falcias comuns: Usar uma premissa vaga ou ambgua; Assumir como verdadeiro o que deve ser provado; Concluir uma premissa sem uma argumentao adequada; Erro oposto; Erro inverso.

Como mostrar que um argumento invlido? Construir a tabela da verdade e achar uma linha crtica com a concluso

falsa. Achar um argumento com premissas verdadeiras e concluso falsa.

Para um argumento ser vlido, qualquer argumento da mesma forma quetem premissas verdadeiras deve ter uma concluso verdadeira.


Erro oposto

Exemplo 43:

Se Zeca um gnioento Zeca senta na primeira carteira na sala de aula;Zeca senta na primeira carteira na sala de aula;

... Zeca um gnio.

A forma geral do argumento acima :p q;q;

... p.


Erro oposto

Forma do argumento :p q;q;

... p.

Premissas Conclusop q p q q p

1. V V V V V2. V F F F3. F V V V F4. F F V F

Este argumento lembra a forma geral do argumento Modus ponens. Forma deste argumento invlida.


Erro inverso

Exemplo 44:

Se as taxas de juro subiremento os preos das aes iro cair;As taxas de juro no esto subindo;

... Os preos das aes no iro cair.

A forma geral do argumento acima :p q;p;

... q.


Erro inverso

Forma do argumento :p q;p;

... q.

Premissas Conclusop q p q p q

1. V V V F2. V F F F3. F V V V F4. F F V V V

Este argumento lembra a forma geral do argumento Modus tollens. Forma deste argumento invlida.


Validade Verdade Validade uma propriedade da forma de um argumento. Se um argumento vlido

ento tambm todo argumento que tem a mesma forma.

Exemplo 45 Argumento vlido com uma concluso falsa:Se John Lennon era uma estrela do rockento ele tinha cabelo ruivo;John Lennon era uma estrela do rock;

... John Lennon tinha cabelo ruivo. Argumento vlido de acordo com modus ponens. No entanto, a primeira

premissa falsa assim como a concluso.

Exemplo 46 Argumento invlido com uma concluso verdadeira:Se Nova York uma cidade grandeento Nova York tem edifcios altos;Nova York tem edifcios altos;

... Nova York uma cidade grande. Argumento invlido (erro oposto) mas com a concluso verdadeira.UFMG/ICEx/DCC MD Fundamentos da Logica Logica Proposicional 76

Contradies e argumentos vlidos

Regra da contradio:Se pode ser mostrado que a suposio da afirmao p = F leva logi-camente a uma contradio, ento pode-se concluir que p = V.

p c, onde c uma contradio... p.

Tabela da verdade:Premissa Concluso

p p c p c p1. V F F V V2. F V F F


Honestos DesonestosExemplo 47 Uma ilha possui um de dois tipos de pessoas:

A diz: B honesto. B diz: A e eu somos de tipos opostos.

Suponha que A honesto.... O que A diz verdade;

... B tambm honesto;

... O que B diz verdade;

... A e B so de tipos honestos;

... Chegou-se a uma contradio: A e B so honestos e A e B so desonestos.... A suposio falsa;

... A no honesto;

... A desonesto;

... O que A diz falso;

... B no honesto;

... B tambm desonesto.


Regras de inferncia: Sumrio

MODUS PONENSp q;p;

... q.

MODUS TOLLENSp q;q;

... p.

ADIO DISJUNTIVAp;

... p q.

q;... p q.

SIMPLIFICAO CONJUNTIVAp q;

... p.

p q;... q.

ADIO CONJUNTIVAp;q;

... p q.

SILOGISMO DISJUNTIVOp q;q;

... p.

p q;p;

... q.

SILOGISMO HIPOTTICOp q;q r;

... p r.

DILEMAp q;p r;q r;

... r.

CONTRADIOp c;

... p.


Aplicao: Circuito lgico

Claude Shannon (19162001), matemtico americano, considerado o cientista que estabele-ceu os fundamentos da teoria da informao moderna, com a publicao em 1948 do trabalhointitulado Mathematical Theory of Communication. Nesse trabalho ele observa que the fun-damental problem of communication is that of reproducing at one point either exactly or appro-ximately a message selected at another point. Os fundamentos propostos nesse trabalho sousados integralmente hoje em dia em reas como redes de computadores e recuperao dainformao.

Antes disso, Shannon observa a analogia entre operaes de dispositivos de chaveamento(por exemplo, chaves ou interruptores) e operaes de conectivos lgicos. Ele usa essa ana-logia com muito sucesso para resolver problemas de projetos de circuitos lgicos e apresentaos resultados na sua dissertao de mestrado (A Symbolic Analysis of Relay and SwitchingCircuits) do MIT em 1938.



Uma chave pode estar em uma de duas possveis posies:FechadaAberta

Chave fechada: corrente pode passar. Chave aberta: h interrupo de corrente.

Exemplo de uma chave num circuito:+

Lmpada acende sse corrente passa por ela. Isto acontece, sse a chave est fechada.

Observe que nesse modelo est sendo assumido que a bateria tem sempreenergia e a chave e a lmpada nunca falham. Consideraes como essas so importantes sempre que um modelo

proposto.UFMG/ICEx/DCC MD Fundamentos da Logica Logica Proposicional 81


Sejam os circuitos abaixo e os possveis comportamentos:

QP

+

Chaves LmpadaP Q Estado

Fechada Fechada AcesaFechada Aberta ApagadaAberta Fechada ApagadaAberta Aberta Apagada

P

Q+


Fechada Fechada AcesaFechada Aberta AcesaAberta Fechada AcesaAberta Aberta Apagada




Fechada Fechada AcesaFechada Aberta ApagadaAberta Fechada ApagadaAberta Aberta Apagada


Fechada Fechada AcesaFechada Aberta AcesaAberta Fechada AcesaAberta Aberta Apagada

Observe que se as expresses fechada e acesa forem substitudas pelovalor-verdade V e aberta e apagada forem substitudas pelo valor-verdadeF, ento as tabelas da esquerda e da direita correspondem, respectivamente,s expresses lgicas:

P Q (conjuno); P Q (disjuno).


Aplicao: Circuito lgicoA partir da dcada de 1940, rels eletro-mecnicos (chaves) foram substitudos por dispositivoseletrnicos como vlvulas, transistores e circuitos integrados.

Vlvula. O computador mo-derno (primeira gerao) sur-giu a partir da vlvula, que per-mitiu executar uma operaomuito mais rpida que os siste-mas de rel eletro-mecnicos.Abaixo est um sistema devlvulas da IBM de 1946 quepodia multiplicar dois nmerosde 10 algarismos em 1

40s.

Transistor. Dispositivo se-micondutor de estado slidoque passou a ser usado larga-mente na segunda gerao decomputadores a partir do in-cio da dcada de 1960.

Circuito integrado. Tam-bm chamado de microchipou chip uma miniaturiza-o de dispositivos semicon-dutores e componentes passi-vos manufaturados na superf-cie de um substrato extrema-mente fino de um material se-micondutor. Abaixo, uma ima-gem do processador Intel CoreDuo otimizado para aplicaesmulti-threaded e multi-tarefa.



Os estados (fechado e aberto) foram substitudos por outras representaesapropriadas para os novos dispositivos. Por exemplo, diferentes valores de tenso. Ponto importante: modelagem anterior continua vlida!

No projeto de circuitos digitais, os valores lgicos verdadeiro e falso sonormalmente substitudos pelos smbolos 1 e 0. Estes smbolos so chamados de bits (binary digits).



A partir do surgimento dos computadores digitais, uma questo fundamentalpassa a ser a representao (codificao) da informao usando bits.

Por exemplo, como bits so representados/codificados quando esto em: Memria de ferrite? Memria eletrnica? Disco magntico? Disco ptico? Cabo coaxial? Cabo metlico? Cabo de fibra ptica? Canal de comunicao sem fio?


Documents

Fundamentos Da Logica