Srie Apontamentos Maria doCarmo Nicoletti ACARTILHADA. LGICA Universidade Federal de So CarlosEdUfSCar UNIVERSIDADEFEDERALDESOCARLOS Oswaldo Baptista Duarte Filho Reitor Maria Stella Coutinho de Alcntara Gil Vice-Reitora Oswaldo Mrio SerraTruzzi Diretor daEditora da UFSCar EdUFSCar - Editora daUniversidade Federal de So Carlos ConselhoEditorial Joo Eduardo dos Santos Jos Renato Coury Nivaldo Nale PauloRealiNunes Oswaldo Mrio SerraTruzzi (Presidente) Maria Cristina Priore Secretria Executiva Universidade FederaldeSoCarlos EditoradaUniversidade Federalde So Carlos Via Washington Lus,km235- 13565-905 - So Carlos, SP.Brasil Telefax[16)3351-8137 E-mailedufscar @ufscar.br http://www.editora.ufscar.br Mariado CarmoNicoletti Acartilhadalgica SoCarlos EdUFSCar 2008 2008Maria do Carmo Nicoletti Coordenao Editorial Luis Gustavo Sousa Sguissardi Preparao e Reviso de Texto Marina Venncio Grandolpho Ingrid Pereira de Souza Favoretto Editorao Eletrnica Vtor Massola Gonzales Lopes Impresso e Acabamento Departamento de Produo Grfica da Universidade Federal de So Carlos Ficha catalogrfica elaborada pelo DePT da Biblioteca Comunitria da UFSCar N643c Nicoletti, Maria do Carmo. A cartilha da lgica I Maria do Carmo Nicoletti -- So Carlos : EdUFSCar,2008. 205p. ISBN - 978-85-7600-117-1 1.Lgica.2.Lgicaproposicional.3. Lgica de primeira ordem.4.lgebrabooleana.5.Interpretao. 6.Modelo de Herbrand.1.Ttulo. CDD - 160 (20) CDU-16 A professora Maria do Carmo Nicoletti docente do Departamento de Computao da UFSCar. Todos os direitos reservados. Nenhuma parte desta obra pode ser reproduzida ou transmitida por qualquer formae/ou quaisquer meios(eletrnicos ou mecnicos, incluindo fotocpiae gravao) ou arquivada em qualquer sistema de dados sem permisso escrita da editora. SUMRIO PREFCI0 .............................................................................................................................................7 1. ALGICA PROPOSICIONAL ...........................................................................................................8 1.1 INTRODUO ........................................................................................................................................8 1.2 FRMULASBEM-FORMADAS (WFF)E INTERPRETAO ................................................................ 10 1.3 VALIDADE E INCONSISTNCIA ...................................................................................................1.7 1.4 CONSEQNCIALGICAE EQUIVALNCIALGICA ....................................................................... 23 1.5 LGEBRA DALGICAPROPOSICIONAL .................................. ~1..6 FORMASNORMAIS----- 33 1.6.1 FORMA NORMAL CONJUNTIVA -------34 1.6.2 FORMA NORMAL DISJUNTIVA ...................................................................................................................... 35 1.6.3 OBTENODA FNC SEMO USODE TABELA-VERDADE .......................................................................... 37 1.6.4 ANOTAO CLAUSAL .................................................................................................................................... 40 1.7 INFERNCIA LGICAE SISTEMAS DEDERIVAO ......................................................................... 43 1.8 PROVA AUTOMTICA DE TEOREMAS- ALGORITMODE WANG .................................................... 57 1.9 RESOLUOE PROCEDIMENTOS DEPROVAPORRESOLUO .................................... 66 2. A LGEBRA DEBOOLE ................................................................................................................ 78 2.1 CONCEITOSINICIAIS ............................................................................................................................ 78 2.2 FUNESBOOLEANAS ........................................................................................................................ 81 2.3 FRMULASBOOLEANAS ..................................................................................................................... 86 2.4 MINIMIZAO DEEXPRESSES BOOLEANAS ................................................................................. 95 2.4.1 CONSIDERAES INICIAIS ........................................................................................................................... 96 2.4.2 O ALGORITMO DEQUINE-McCLUSKEY ......................................................................................................100 2.4.3 MAPAS DEKARNAUGH ............................................................................................................................... 109 3. A LGICADEPREDICADOS ...................................................................................................... 114 3.1 CONCEITOSBSICOS ................................................................................................................. 114 3.2 A LGICADEPREDICADOS COMOLINGUAGEMDEREPRESENTAODE CONHECIMENTO .... 126 3.2.1 USANDO LGICADEPREDICADOS PARAREPRESENTARSENTENAS EMLNGUA NATURAL ....... 126 3.2.2 EXEMPLOSDE TRADUODE SENTENASPARAEXPRESSESDALGICADEPREDICADOS.... 128 3.3 INTERPRETAES E MODELOS .............................................................. - . 133 4. SUBSTITUIO,UNIFICAO E FORMANORMAL.. ................................................................ 143 4.1 O PROCESSO DE SUBSTTTUI0 ...................................................................................................... 143 4.2 O PROCESSO DE UNIFICAO ...................................................... '. ................................................... 147 4.2..1 EXEMPLOS DO PROCESSODEUNIFICAO - O PROCEDIMENTOUNIFY ........................................... 148 4.2.2 IMPLEMENTAOPROLOGDO ALGORITMOUNIFY ...............................................................................154 4.3 O PROCESSODECONVERSOPARA A FORMA CLAUSAL ........................................................... 157 5.RESOLUOEMLGICA DEPREDICADOS ............................................................................ 162 5.1 CONSIDERAES INICIAIS ................................................................................................................ 162 5.2 UMEXEMPLO ......................................................................................................................................162 5.3 USANDORESOLU0 ........................................................................................................................ 164 5.4 ESTRATGIAS DE CONTROLEPARA MTODOS DERESOLUO ................................................ 171 5A.1 ESTRATGIA EMLARGURA ......................................................................................................................... 172 5.4.2 ESTRATGIA DO INPUT LINEAR ................................................................................................................. 172 5.4.3 ESTRATGIA DO CONJUNTO SUPORTE ..................................................................................................... 173 5.4.4 ESTRATGIA DA PREFERNCIA POR CLUSULASUNITRIAS .............................................................. 174 6. UNIVERSO,INTERPRETAO E MODELODEHERBRAND .................................................... 176 6.1 CONSIDERAES INICIAIS ................................................................................................................ 176 6.2 O UNIVERSO E A BASE DEHERBRAND ........................................................................................... 176 6.3 INTERPRETAOE MODELODEHERBRAND ................................................................................. 179 1 LISTA DEEXERCCIOS ............................................................................................................... 186 2 LISTA DE EXERCCIOS ................................................................................................... 189 3 LISTA DEEXERCCIOS ............................................................................................................... 192 4 LISTADEEXERCCIOS ............................................................................................................... 194 5 LISTA DE EXERCCIOS .............................................................................................................. 196 6 LISTA DEEXERCCIOS ............................................................................................................... 198 7 LISTA DE EXERCCIOS ............................................................................................................... 200 BIBLIOGRAFIA E REFERNCIAS ............................................................................................... 204 PREFCIO ALgicadesempenhaumpapelcentralemmuitasreasdeconhecimento,particularmenteem Matemtica e Computao. A estreita ligao entre Lgica e Computao est principalmente rela-cionada aodesenvolvimento de linguagens para modelar situaes e problemas encontrados, com vistas ssuas solues.Raciocinar sobre essassituaes significa construir argumentossobre elas - oobjetivofazerissoformalmente,demaneiraquea provadavalidadedeargumentospossa ser automatizada.Para a especificao e o desenvolvimento deargumentosdemaneira rigorosa preciso primeirooestabelecimentodeumalinguagem naqualsepossaexpressarsentenasevi-denciandosuaestruturalgica.ALgicaProposicionaleaLgicadePredicados,osprincipais assuntos tratados nestes Apontamentos, so duas dessas linguagens formais. AprincipalmotivaoparaaelaboraodesteApontamentofoiadedisponibilizarmaterial impressoparaoacompanhamentodasaulasdadisciplinaIntroduoLgica,quefazparte do elencodedisciplinasintrodutriasdoscursosdeBachareladoemCinciasdaComputaoede Engenharia da Computao da Universidade FederaldeSo Carlos.Os assuntos tratados seguem a ementa da disciplina. Acredito que a disponibilidade de material impresso sobre os assuntos dis-cutidos em classe contribui para o melhor entendimento de conceitos apresentados; permite que a ateno seja direcionada ao que est sendo discutido/apresentado em sala de aula; d segurana ao aprendizado, uma vez que se toma uma referncia dos conceitos discutidos; abre perspectivas para novas discusses/questes, por meio dos exemplos fornecidos e dos exerccios propostos. Osconceitoseresultadosdescritos podemser eencontradosem diversas refernciassobreos assuntostratados.A teoriadescritanoCaptulo2,sobrelgebradeBoole,foisubstancialmente fundamentada em notao e definiesencontradas em Berztiss (1975), publicao que,apesar da idade avanada (como referncia a assuntos computacionais), precisa e formal em muitos deseus captulos, o que a permite ser,at os dias de hoje, altamente apreciada e respeitada. So Carlos, maro 2008 Maria do Carmo Nicoletti 1. A LGICAPROPOSICIONAL A Lgica Proposicional(ouClculoProposicional)um dosmaissimplesformalismoslgicos existentes e pode ser considerada a formalizaodeformassimples de raciocnio. Apesar de sim-plesesemrecursosparaarepresentaodemuitosproblemas/situaesdomundoreal,ainda assimaLgicaProposicional,comoservisto,convenienteepoderosaosuficienteparalidar com muitos problemas e formalizar precisamente a busca de suas solues. Este captulo aborda os principais elementos da Lgica Proposicional, tendo como objetivo, alm de fornecer e discutir os fundamentosda Lgica Proposicional, estabelecer a conceituao necessria para a compreenso dos captulos que o seguem. ALgicaProposicionallidaapenascomenunciadosdeclarativos,chamadosproposies.As sentenas exclamativas, imperativas e interrogativas so, pois, excludas. 1.1 INTRODUO Definio1.1Uma proposio uma sentena declarativa que pode assumir os valores'.' verdade v (como significado deque a proposio verdadeira) ouf (com o significado dequea proposio falsa),um excluindo o outro. Exemplo 1.1Exemplos de proposies: 1.A soma dos nmeros 5 e 6 igual a11. 2.O nome do menino Pedro. 3.O programa tem problemas. 4.As refeies so saborosas e caras. 5.Um tringulo ABC retngulo se e somente se tem um ngulo reto. 6.Seeucomo muito ento eu engordo. 7.A mesa de madeira ou o chapu de palha. Exemplo 1.2As quatro sentenas a seguir no so tratadas na Lgica Proposicional, uma vez que as duas primeiras so interrogativas, a terceira imperativa e a quarta exclamativa. 1.Quando voc pretende viajar? 2.Que horas so? 3.Que Deus a acompanhe. 4.O relato desua viagem incrvel! A cartilha da lgica9 Observao1.1importantemencionarquemuitassentenascomumenteutilizadasnodiaa dianosocompletamenteverdadeetampoucosocomplementefalsas.Porexemplo,seum programa computacional teve como sada um resultado inesperado, freqentemente no est claro seo resultadofoiefetivamente causado por um problema no programa ou sefoiconseqncia de problemasem programassubjacentes.A LgicaProposicional,entretanto,lidaapenascom pro-posiesverdadeirasou falsas;qualquerproposioquenoseadequaraessabivalnciano considerada. Observao 1.2Asproposies1,2 e3 doExemplo1.1so proposies atmicas(outomos), uma vez quenelas noaparecem os conectivose,ou,se .. ento e se e somente se, tratadosa se-guir. As proposies 4, 5, 6 e 7 so proposies compostas justamente porque nelas tais conectivos aparecem. Toda proposio composta contm pelo menos um conectivo lgico. Observao 1.3 A Lgica Proposicionallidaapenas com proposies quetm valores-verdade v ou f,isto ,segue o princpio do terceiro excludo ou, equivalentemente, considerada uma lgica bivalente.Qualquerproposioquenotenhaovalor-verdadevnecessariamenteterquetero valor-verdade f. Observao 1.4 [Grassmann & Tremblay,1996] Freqentemente sentenas em lngua natural (i .e. , portugus,ingls,francs,espanhol,etc.)soambguasumavezquealgumaspalavrasusadas nassentenaspodemtermaisdoqueumsignificado.Aespecificaodalinguagemlgicatem como objetivoevitar essaambigidade. Alm disso,osconectivos demuitaslnguasnaturaisre-fletempreocupaocomcausalidade,inteno,nfase,crenasetemporalidade.A palavra "se", por exemplo, freqentemente implica algum tipo de causalidade. A lgica clssica, por outro lado, apenaslida com verdadee falsidade,o quesignifica que a noo decausalidade no possvel de ser expressa. Por essa razo, so introduzidos smbolos matemticos para representar os conectivos da lgica.Esses smbolos podem ento ser definidos de maneira no ambgua. Definio1.2 O alfabeto da Lgica Proposicional constitudo por: Smbolos depontuao:() Smbolos de verdade: verdade, falso Smbolos proposicionais atmicos: p, q,r,s, t,u,... Conectivos lgicos:--,, /\, v, ~ H 1OEdUFSCar -Apontamentos 1.2 FRMULASBEM-FORMADAS (WFF)E INTERPRETAO ComoestabelecidonaObservao1.2,novasproposiespodemser construdascom baseem outras, por meio douso de conectivos lgicos. Essas novas proposies, bem como as proposies atmicas, so chamadas de frmulas bem-formadas (wff-well-formedformulas), desde que satis-faam a Definio1.3. Observao 1.5 Para representar proposies gerais (sejam elas atmicas ou compostas) so usa-das metavariveis proposicionais, representadas por letras do alfabeto grego:,x,o,E,etc. Definio 1.3 Uma wff definida recursivamente como segue: 1.os smbolos de verdade (i.e., verdade e falso,como especificados em Definio1.2) so wffs; 2.um tomo uma wff; 3.se aeP so wffs,ento as proposies compostas listadas na Tabela1.1tambm so wffs; 4.as nicas wffs so as definidas nos itens1,2 e3 acima. Tabela 1.1Regras para a formao dewffs. wfflida comowff chamada de (--a)no anegao (a /\p)a epconjuno (a vp)aou pdisjuno (a ._ se aento pcondicional (ap)ase e somente sebicondicional Observao 1.6 O operador --(no) um operador unrio, ou seja, aplicado a um nico operando. Quando ooperando em questoforum tomo (p, por exemplo), tantootomo quantootomo ne-gado (ou seja,tantopquanto --p), denominado literal.Os conectivos/\, v, so conectivos binrios, pois so usados para conectar duas wffs. Observao l.7Se cuidados no forem tomados, expresses lgicas podem ser ambguas. Consi-dere, por exemplo, as trs proposies atmicas: p definida como "Maria termina o relatrio" q definida como "Maria est feliz"e r definida como "Maria vaiao cinema". Censidere a proposio composta p-t qvr.Sem oestabelecimento de uma regra precisa, essa exp-o pode ser interpretada de duas maneiras: A cartilha da lgica11 ( 1) podesignificar (p q)vr que,parafraseada emlngua natural,expressa "se Maria termina o relatrio, Maria est felize ir,em qualquer circunstncia, aocinema"; (2) pode significar p (qvr)que,parafraseada emlngua natural,expressa "se Maria termina o . relatrio Maria est felize Maria ir ao cinema". Portanto, a expresso p q vr ambgua. Uma maneira deevitar ambigidade por meio do ',/:,,.. :lif estabelecimento de regras, como as da Definio1.3, que define a sintaxe da Lgica Proposicional. expresso lgica que segue as regras da Definio1.3no ambgua . .f,.Observao1.8importanteenfatizarqueaDefinio1.3recursiva,ouseja,paraqueuma seja uma wff preciso que suas "partes" tambm sejam wffs.Na expresso (_,a),a con-)_siderada o escopo da negao e o conectivo_, chamado deconectivo principal daexpresso _,a. Emuma conjuno,i.e., uma expressolgica da forma(a /\ o conectivoprincipal o /\ e ae Pso chamados respectivamente deescopo esquerda e escopo direita daconjuno.Uma no-meao similar seaplica sexpresses (a ve (a Os escopos podem, por sua vez, ser expresses compostas e, portanto, os conectivos encontrados nos escopos so subconectivos da expresso emquesto.Por exemplo, na exp;esso (p/\ q) r o conectivo principal e o sub-conectivo doescopo esquerda /\.O escopo direita doconectivo principal no tem conectivo. Note que o /\ o conectivo principal doescopo esquerda. Exemplo 1.3 Considere o procedimento para verificar se uma dada frmula a bem-formada ou no. (a) Suponha que a frmula aseja ((p tt q)v(r /\ (-.s))) tt (-.p). O conectivo principal de a tt. SeguindoasregrasapresentadasnaTabela1.1,paraqueasejabem-formada,precisomostrar que ((p tt q)v(r /\ -.s)) e que (-.p) so bem-formadas. Para mostrar que ((p tt q)v(r /\ -.s)), cujo conectivo principal v, bem-formada, preciso evidenciar que tanto (p tt q) quanto (r /\ -.s) so bem-formadas. Note que (p tt q) bem-formada uma vez que p bem-formada ( um tomo), q bem-formada (umtomo)eacomposiodeduasfrmulasbem-formadas,usandooconectivott bem-formada (regra da Tabela1.1 ). Note quena frmula(r/\(-,s))afrmular bem-formada, uma vez que umtomoe (...,.,s) tambmbem-formada,umavezqueanegaodeumtomo.Dadoqueambas,tantorquanto (-.s),sobem-formadas,(r /\(-.s)) bem-formada pois uma conjunodeduasfrmulasbem-formadas. Como ambas,(ptt q)e (r/\(-.s)),so bem-formadas, tambmo ser a disjuno dessasduas frmulas,((ptt q)v(r /\(-.s))).Por outrolado, a frmula (-.p) bem-formada, pois a negao 12EdUFSCar -Apontamentos deumtomo.Dadoqueambassobem-formadas,afrmulacompostadeduasfrmulasbem-formadas por meio do uso do conectivo tt tambm bem-formada. Cb)Suponha que a frmulaaseja CCP~ q)tt CPv)). Note que o conectivo principal dea tt, e para aser bem-formada, de acordo com a Tabela 1.1, ambas asfrmulas, CP~ q) e CPv ), precisam ser bem-formadas. A frmula P ~ q) bem-formada uma vez quepe q so frmulasatmicas e a frmula resul-tante, que a implicao P ~ q), bem-formada. Dado que v o conectivo principal da frmula CPv ),talfrmulasseriaprovadaserbem-formadaseoconectivoestivesseconectandoduas frmulasbem-formadas.No caso,uma dasfrmulasafrmulaatmica p,que bem-formada. Noentanto,noexisteasegundaoutrafrmula,oquecaracterizaCPv)comonobem-formada e,conseqentemente,afrmulaanobem-formada.Outrosexemplosdefrmulasnobern-formadas: CCp~ ~ q)Vs) CCP~ /\ q) s) CCpVC-.Cp~ q))/\vq)) Definio 1.4 Seja auma frmula da Lgica Proposicional. Uma subfrmula de a definida por: 1.a subfrmula de a; 2.se a: C.....,p)entop uma subfrmula de a; 3.se a urna frmula em qualquer dos padres: CP/\ y),CPVy), P ~ y)ou CPtt y) ento p e y so subfrmulas de a; 4.se a uma subfrmula de p ento toda subfrmula asubfrmula dep. Informalmente,urnasubfrmuladeurnafrmulaaumapartedeaqueumafrmulaCde acordo com a Definio1.3). Exemplo 1.4 Considere a frmulaa: CP~ q)tt r.Asfrmulas CP~ q), p, qe r so todas subfr-mulas dea. Observao1.9Comopodeserevidenciadonasvriasrefernciasbibliogrficasaofinaldessa publicao,poucosautoresusamexpresseslgicascompletamenteparentizadas,dadoquetais expresses podem ser bastante longas e, freqentemente, so difceis de serem lidas. Os parntes podem ser omitidos quando sua eliminao no introduzir ambigidade. A cartilha da lgica13 Particularmente, os parnteses externos deuma expressolgica so, quase sempre,omitidos. Por exemplo, ao invs deescrever (pvq)escreve-se p vq;aoinvs de escrever ((p vq) Hverda-de)escreve-se (pvq) Hverdade. Ao eliminar tais parnteses, no entanto, no deve ser esquecido que eles devem voltar a ser introduzidos se a expresso em questo for composta com alguma outra expresso. Parnteses dentro de uma expresso tambm podem ser omitidos. A leitura da expresso resul-tantefeitausandoaschamadasregrasdeprioridade,queestabelecemumahierarquiaentreos conectivos. A conveno quea maioria dosautores estabelece para os conectivos lgicossegue a ordem decrescente deprecedncia especificada na Tabela1.2. Tabela 1.2 Precedncia de conectivos lgicos. ~ ~ ~ ~ . ~ ~ ~ ~ ~maior V Hmenor O conectivo-. tem sempre a maior precedncia. Por essa razo, a expresso lgica -.p vq deve ser entendida como (-.p) vq e no como -.(p vq). De acordocoma Tabela1.2, na expresso p/\q vr,o Atem precednciasobre ovquando da especificao de subexpresses. Portanto, p /\ q vr deve ser entendida como (p/\ q)vr.De manei-ra semelhante, p~ qvr deve ser entendida como p~ (qvr),umavez queo vtem precedncia sobre o ~ . O conectivo Htem a precedncia mais baixa detodas,o quesignifica quep Hp ~ r deveser entendido como p H(p~ r). Em algumas expresses, entretanto, as regras de prioridade no so suficientes para remover to-das as ambigidades. Por exemplo, a expresso p ~ q ~ r pode ser entendida ou como (p ~ q)~ r ou como p~ ( q ~ r). A escolha da interpretao usada depender da associatividade do conectivo ~ . T o d o s osconectivos lgicos binrios so associativos esquerda, e, conseqentemente, p~ q ~ r deve ser entendido como (p ~ q)~ r. Definio1.5Cadaumadasexpressesenvolvendoae~ naDefinio1.3chamada de forma sentenciai. Uma forma sentenciai uma especificao abstrata da sintaxe de um nmero infinito de wffs compostas de smbolos que representam proposies atmicas. Uma wff que sintaticamente se ajusta a uma formasentenciai chamada de uma instncia desubstituio da forma sentencia/. Exemplo1.5A wff (pA(q~ r)) uma instncia desubstituio dequalquer uma dasseguintes formassentenciais: 14EdUFSCar - Apontamentos 1.a, tal que a (p A(q r)). 2.(a Af3),tal que a pef3( q r). 3.(a A(13 y)),talque a p, f3qe y r. Definio1.6 Asemntica - ousignificado - deumawff ovalor-verdadeaelaassociado por meio de uma interpretao. Uma interpretao Ina Lgica Proposicional uma funocujo con-tradomnio possui apenas dois elementos, como mostra a Figura1.1, tal que: o domnio de I oconjunto das wffs da Lgica Proposicional; o contradomnio de I oconjunto{v,f}; os smbolos de verdade do alfabeto, verdade efalso,so interpretados por 1 como I[ verdade] =ve !(falso] =f; Dado um smbolo proposicional p, I[p]E{ v,f}. Figura 1.1lnterpretao de frmulas como uma funo em{v,f}. Observao 1.10 A interpretao dos smbolos verdade fixa, ou seja, para qualquer interpretao 1, I[ verdade] =ve I[ falso]=f. Definio l. 7 Seja y uma wff e considere uma interpretao I.O significado de y dado por 1,notado por I[y ),determinado pelas regras: 1.Se y:p, tal que p um smbolo proposicional, ento I [y]=I[p]e l[p]E{ v,f}. 2.Se y:verdade ento l[y]=v.Se y:falso, ento I[y]=f. 3.Seja 13uma wff.Se y:-,13,ento l[y)= l[-,j3)=v se I[f3]=f I[y]=l[-,f3J =f se I[j3]=v 4.Sejam ae13duas wffs.Se y:(a Aj3),ento I[y]=I[(a Aj3)]= vse I[a] = v eI[j3)=v {I[a] =v el[j3]=f I[y]= I[(a" j3)]= fseI[a] =f el[j3]=v I[a] =f el[j3]=f 5.Sejam aej3duas wffs.Se y:(a vj3),ento {I[a] =vel[j3]=v I[y]= I[(a vj3)]= vseI[a] =vel[j3]=f I[ a] =f e I[j3] =V l[y]= I[(a vj3)]= fse I[a] =f e I[j3]= f 6.Sejam aej3duaswffs.Se y: j3), ento {I[ a] =V e I[j3] =V I(y]= j3)]= vseI[a] =f el[j3]=v I[a] =f el[j3]=f I[y]= I[(aj3)]= fseI[a] = v e I[j3]= f 7.Sejam aej3duaswffs. Se y:(a tt j3),ento I[y]= I[(aj3)]= vse{I[a] =vel[j3]=v I[ a] =f e I[j3] =f I[y]= I[(aj3)]= fse{I[a] =vel[j3]=f I[ a] = f e I[j3] = v A cartilha da lgica15 Exemplo 1.6 Considere a frmula a: ((-.p) "q) interpretao 1 dada por: qr 1ff Para determinar o significado semntico de adeacordo com I (i.e., I[a]), considere: pq IVfVfV ou seja, I[a] = v. Exemplo1.7Considere a frmula a: ((-,p) vq) ((-,r)(-,s)) e uma interpretao Idada por: 16EdUFSCar -Apontamentos pqrs lVVfV Para determinar o significado semntico de ade acordo com l(i.e., l[a]), considere: pqrs-.p-.r-.s(-.p) vq(-.r)(-.s)a lVVfVfVfVff ou seja, I[a] =f. Definio 1.8 Dada uma wff a, a tabela-verdadedeamostra a semntica de asob todas as pos-sveisinterpretaes;cadalnhada tabela associada auma possvel interpretao.Onmero de possveis interpretaes funodonmerodetomos presentes em a. A tabela-verdade de uma frmula acom n tomos tem 2 possveis interpretaes, ou seja, 2nlinhas. Exemplo J.8 Considere a frmula a: ((-.p) vq) ((-.r) (-.s)). A Tabela 1.3 a tabela-verdade de a. Note que atem quatro tomos (p, q, r e s)e, portanto, sua tabela-verdade tem 24 =16poss-veis interpretaes. Tabela 1.3 As16possveis interpretaes da expresso a : ((--,p)vq) ((-.r) (-.s)). pqrs-.p-.r-,s(-.p) Vq(-.r)(-.s)a l, VVVVfffVVV 12 VVVfffVVff 13 VVfVfVfVff 14 VVfffVVVVV 15 VfVVffffVV 16 VfVfffVffV 17 VffVfVfffV 18 VffffVVfVV 19 fVVVVffVVV 110 fVVfVfVVff I" fVfVVVfVff 1,2 fVffVVVVVV 113 ffVVVffVVV 1,4 ffVfVfVVff 1,5 fffVVVfVff 116 ffffVVVVVV A cartilha da lgica17 Note, na Tabela 1.3, que as16 possveis interpretaes foram geradas sistematicamente, seguin-do o padro adotado na literatura. Ageraosistemtica permite ocontrole eafcilidentificao de umaparticularinterpretao.AinterpretaolconsideradanoExemplo1.6ainterpretao nomeada 13 na Tabela 1.3. Observao1.11OsconectivosA,ve~ sosimtricosnosentidodequeaordemdasduas expressesconectadas por eles noafetaovalor-verdadedaexpressoresultante.Noentanto,o conectivo ~ no simtrico, pois as expresses p~ q e q ~ p tm diferentes valores-verdade em uma mesma interpretao. Os valores-verdade de todos os conectivos esto sumarizados na Tabela 1.4, usando duas wffs atmicas. Tabela1.4 Resumo dos conectivos. pq---,p--,q p /\qpvq ~ q ~ ql,VVffVVVV 12 VffVfVff 13 fVVffVVf 14 ffVVffVV 1.3 VALIDADEE INCONSISTNCIA O valor-verdade - ou simplesmente valor - de uma frmula sempre diz respeito a uma determina-da interpretao. A Definio1.9estabelece um;i terminologia que se baseia no valor associado s frmulas. Definio1.9 1.Se umaf nnula atem valor vem uma certa interpretao l, diz-se que a verdadeira na interpretao I. 2.Uma frmulaasatisfatvel (ouconsistente)seexiste pelo menos uma interpretao ltal que l[a] =v. 3.Uma frmula denominada vlida quando for verdadeira em todas as interpretaes poss-veis. Essas frmulasso conhecidas tambm como tautologias. 4.Se uma frmula atem valor f em uma certa interpretao l , diz-se que a falsa na interpre-tao I. 5.Uma frmulaa invlida se existe pelo menos uma interpretao I tal que I[a] =f. 6.Uma frmulaainsatisfatvel (ouinconsistente)quandoforfalsaem todas asinterpreta-es possveis. Essas frmulasso conhecidas tambm como contradies. 18EdUFSCar -Apontamentos 7.NaLgica Proposicional,asfrmulasquenosonemtautologiasnemcontradiesso comumente chamadas de contingentes. 8.Dada uma frmula ae uma interpretao 1, ento 1 satisfaz ase l[a] =v. 9.UmconjuntodefrmulasC={a1,a2,a3, an}satisfatvelseesomenteseexisteuma interpretao 1 tal que l[a,] = l[a2]= I[a3]= ...= I[an]= v.Neste caso, 1 satisfaz o conjunto de frmulasc. Exemplo 1.9Considere a frmulaa: (pvq)-4 (p"q).Comoessafrmulapossui doistomos, ela admite 22 = 4 interpretaes, como mostra a Tabela1.5. Tabela 1.5 Tabela-verdade da frmula a: (p vq)(p /\ q). pq(pvq)(p/\q)a 11 VVVVV 12 VfVff 13 fVVff 14 ffffV Com relao frmula a, pode-se dizer que: verdadeira nas interpretaes 11 e 14; satisfatvel, dado que existe pelo menos uma (neste caso, existem duas) interpretao cuja frmula v; falsa nas interpretaes 12 e 13; invlida, dado que falsa nas interpretaes 12 e 13; umafrmula contingente, dado que no uma tautologia e tampouco uma contradio. Exemplo 1.10 Considere a(p/\ q /\ r)-4 r.Como essa frmula possui trs ela admite 23 = 8 interpretaes, como mostra a Tabela1.6. Tabela 1.6 Tabela-verdade da frmulaj3:(p/\ q /\r) r. pqr P" q (pAqAr)

I, VVVVVV 12 VVfVfV 13 VfVffV 14 VffffV 15 fVVffV 16 fVfffV A cartilha da lgica19 Tabela1.6 Continuao ... pqrpAq(p /\ q /\ r)p 17 ffVffV 18 fffffV Como para qualquer interpretao l i,i= 1, ... ,8, IJPJ v,a frmula em questo uma tautologia. Exemplo1.11Considere a frmula y: (pv--,p) ( q/\--.q).Como essa frmulapossuidoisto-mos, ela admite 22 = 4interpretaes,como mostra a Tabela1. 7. Tabela 1.7 Tabela-verdade da frmula y:(pv--,p) (p/\ --,q). pq--,p--,qpV--,pq /\ --,qy II VVffVff 12 VffVVff 13 fVVfVff 14 ffVVVff Como para qualquer interpretao li, i= 1, ... ,4,IJPJ f, a frmula em questo uma contradio. Exemplo 1.12Considere o conjunto defrmulas C={al' a2,a3,a4} ,tal que: a 2: ((-,p) /\ (--.q)) a3:((-,q) /\ p) Oconjunto C no satisfatvel,pois, como podeser vistona Tabela1.8, noexiste umainter-pretao, entre as quatro possveis, que toma as quatro frmulassimultaneamente v. Tabela1.8Conjunto C={a" a2,a3,a4}, talquea, : (p q), a2:((--,p)/\(--,q)), a3:((--,q)/\ p)e a4:pno so satisfatveis. pq --,p--,q 1 234 II VVffVffV 12 VffVffVV 13 fVVfVfff 14 ffVVVVff ;Exemplo 1.13Considere o conjunto defrmulas C={a1,a2,a3,a4}, tal que: 20EdUFSCar -Apontamentos 1: (p q) a2:(r v(---,q)) a3:(sv(--.r)) O conjunto C satisfatvel, pois, como pode ser visto na Tabela 1.9, existe uma interpretao {11) que torna todas as quatro frmulas v. Tabela 1.9 Conjunto C={a1,a2,a3,a4}, talque a1:(p----)- q),a2:(r v(--,q)),a3:(sv(--,r))e a4:pso satis-fatveis. pqrs---,q---,r 1234 I,VVVVffVVVV 12 VVVfffVVfV 13 VVfVfVVfVV 14 VVfffVVfVV 15 VfVVVffVVV 16 VfVfVffVfV 17 VffVVVfVVV 18 VfffVVfVVV 19 fVVVffVVVf I,o fVVfffVVff 111 fVfVfVVfVf 1,2 fVfffVVfVf 113 ffVVVffVVf 114 ffVfVffVff 115 fffVVVfVVf 116 ffffVVfVVf Exemplo 1.14 A Tabela1.10 evidencia que a wff (--,(p/\ q)vq) uma tautologia. Tabela 1.10 Tabela-verdade da wff (--,(pAq) vq). pq(p/\ q)---,(p/\ q)(---,(p/\ q)Vq) I,VVVfV 12 VffVV A cartilha da lgica21 Tabela 1.10 Continuao ... pq(p /\q)-,(p /\ q)(-,(p /\ q)Vq) 13 fVfVV 14 fffVV Exemplo 1.15A frmulatautolgica(pv(P)) tempor tabela-verdadea Tabela1.11.Essafr-mula chamada de lei domeio excludo, que estabelece que ou p verdade ou falso e todo o resto excludo.A Tabela1.11provaessaleimostrandoqueinterpretada vsob toda possvelinter-pretao. Comoafrmula tem apenasumtomo,o nmero depossveisinterpretaes para essa frmula apenas 2 1 =2. Tabela 1.11Tabela-verdade dawff (p v(--,p)). p(-,p)(p V(p)) II VfV 12 fVV Exemplo 1.16 Duas frmulas a1: p) e a2: verdade) so evidenciadas como tautologias na Tabela1.12. Tabela 1.12 Tabela-verdade das wffsaJ.: p) e a,= ( verdade). p p) verdade) VVV fVV ObservaoJ.12Seaforumatautologiaquecontmumasubfrmulaj3,umanovaexpresso lgicaa ' pode ser construda por meiodasubstituiodetodasasocorrnciasdeuma ex-pressoarbitrria.Aexpressolgicaresultantea' continuasendoumatautologia.Considerea wfftautolgica a: (p v(-,p)) do Exemplo1.15(Tabela1.11).Considere a substituio de todasas ocorrncias de p em apor qualquer wff arbitrria, por exemplo, (pAq). A nova wff,a'= ((p/\q) v(-,(p Aq))) tambm tautolgica, como mostra a Tabela1.13. Tabela 1.13 Tabela-verdade dawff a' = ((p /\ q) v(-.(p /\ q))). pq(p/\q)(P Aq) a' II VVVfV 12 VffVV 13 fVfVV 14 fffVV 22EdUFSCar -Apontamentos Substituies semelhantes podem ser feitas em qualquer outra tautologia. Isso se deve ao fato deque,naavaliaodovalor-verdade dequalquerexpresso,apenasovalor-verdadedesuas subexpressesimediatastemefeito.Ofatodeovalor em questotersidoobtidodiretamente pela interpretao ou por algum outro tipo de avaliao anterior irrelevante. Definio 1.10 (O princpio de substituio) Se afor uma frmula tendoJ3como subfrmula, o valor de ano muda se 13for substituda por uma expresso que tenha os mesmos valores-verdade que13.Se aforuma tautologia,apermanece uma tautologia independentemente da interpretao deJ3ser v ou f. Exemplo 1.17 Considere a wff a: ((p vq) /\ (p vr)).Considere a subfrmula J3:(p vq) e considere a frmula a': (({-,p) ~ q) /\ (p vr)) obtida pela substituio de 13por uma frmula com os mesmos valores que J3em cada interpretao, no caso, afrmula13 '= ( (-,p) ~ q).A Tabela1.14evidencia que asfrmulasaea' tm omesmo valor sob cada uma das oito interpretaes, evidenciando o princpio de substituio. Tabela 1.14 Tabela-verdade das wffs ae a', evidenciando o princpio da substituio. pqr-,p - , p ) ~ q (p vq)(pVr)aa' II VVVfVVVVV I2 VVffVVVVV I3 VfVfVVVVV I4 VfffVVVVV Is fVVVVVVVV I6 fVfVVVfff I7 ffVVffVff Is fffVfffff Exemplo 1.18Ofatodea wff a: (-,(p /\q)vq)ser tautolgica (ver Exemplo1.14) permite dizer que a wff a': (-,((p vq)/\ r)vq) tambm tautolgica, como evidenciado na Tabela1.15. Obser-veque a formasentenciai associada aambas (-,(a1 /\ a2)va2).Na frmula a, a1:pe a2:q.Na frmulaa', a1:(p vq) e a2:r. Tabela 1.15 Tabela-verdade das wffs ae a', com atautolgica e y:---,((pvq)/\ r). pqr(pvq)(pVq) /\ ryaa' II VVVVVfVV 12 VVVVVfVV I3 VffVfVVV A cartilha da lgica23 Tabelal.15 Continuao ... pqr(p vq)(p Vq) /\ fyaa' 14 VffVfVVV 15 fVVVVfVV 16 fVVVVfVV 17 fffffVVV 18 fffffVVV 1.4 CONSEQNCIALGICAE EQUIVALNCIA LGICA Definio 1.11Dadasasfrmulasp1,p2,f33, ... ,Pneuma frmulaa, diz-se que aconseqncia lgica de p1,p2,f33, ,Pnse esomente se em qualquer interpretao em que p1,f32,(33, ... ,pnforem simultaneamente v,a tambm v.Se aconseqncia lgica de P,,f32,f33, ,Pn'diz-se que ase-gue logicamente de f31,(32,f33, ., PnPara indicar esse fato, a seguinte notao usada: Exemplo 1.19 Como pode ser comprovado na Tabela 1.16, a frmula (p vq) conseqncia lgica da frmula p, ou seja, toda interpretao que torna p v, torna (p vq) v tambm. De maneira anloga, pode-se dizer que (p vq) conseqncia lgica da frmula q,ou seja, toda interpretao que toma q v,torna (pvq) v tambm. t Tabela 1.16 Tabela-verdade que evidencia pj=(pvq) e tambm q 1=(p vq). pq(p Vq) VVV VfV fVV fff Exemplo 1.20 Considere as frmulasa: (p ~ q), p:(r ~ s) e y:(p vr) ~ (q vs). Verificar se a, p I= y,isto , se y conseqncia lgica de aep.Para essa verificao, considere a Tabela1.17, com todas as16 possveis interpretaes. Tabela l.17 Evidenciando a conseqncia lgica (p~ q),(r ~ s)1=(pvr)~ (q vs). pqrs(p ~ q) r ~ s)(pVr)(q Vs)(pvr)~ (q vs) II VVVVVVVVV +-12 VVVfVfVVV 24EdUFSCar-Apontamentos Tabela 1.17 Continuao ... pqrs(p q) s)(p Vr)(qVS)(p Vr) ( q VS) 13 VVfVVVVVV14 VVffVVVVV15 VfVVfVVVV 16 VfVfffVff 17 VffVfVVVV 18 VffffVVff 19 fVVVVVVVV110 fVVfVfVVV 111 fVfVVVfVV112 fVffVVfVVI13 ffVVVVVVV114 ffVfVfVff I,s fffVVVfVVr16 ffffVVffVNote na Tabela1.17que, nas interpretaes nas quais ambas ae13so interpretadas v(ou seja, interpretaes 11, I3,14,111, 112, I13, 115e116'assinaladas na tabela com uma flecha), a frmula y tam-bm interpretada v.Isto permite dizer que y uma conseqncia lgica de ae13,ou seja, escrever a, 13i= y.Por meio dainspeoda Tabela1.17 pode-se dizer que afrmulaa/\p no conseqncia lgica da frmula y.Isso se deve ao fatode existirem interpretaes que tomam y v e,nessas mesmas interpretaes, a/\p no v(interpretaes I2,15,17 e 110). Definio 1.12 Diz-se que uma frmula alogicamente equivalente(=) a uma frmula 13se e so-mente se afor conseqncia lgica de 13e13for conseqncia lgica de a, isto : a==13se esomente se a!=13e13!=a Exemplo1.21UsandoaDefinio1.12,mostreque(p q)==(-.pvq).Paratal,preciso mostrar que: (1)(p q)!=(-.p vq),ou seja, que (-.p vq) conseqncialgica de (pq). (2) (-.p vq) !=(p q), ou seja, que (p q) conseqncia lgica de (-.p vq). Mostrar (1) mostrar que,sempre que (pq) for interpretada v,(-,p vq) tambminterpre-tada v.Isso est evidente na Tabela1.18. A cartilha dalgica25 Tabela 1.18 Tabela-verdade que evidencia (p ~ q)i= (--.pvq). pq p ~ q)--.p(--.pVq) II VVVfV~I2 Vffff I3 fVVVV~I4 ffVVV~Como podeser vistona Tabela1.18,afrmula(p~ q)interpretada vnasinterpretaes 11, I3 e I4Note que nessasinterpretaes afrmula(--.pvq)tambminterpretada v,o que permite escrever (p ~ q)i= (--,pvq). Mostrar (2) mostrar que,sempre que (--,pvq)forinterpretada v,(p~ q) tambm interpre-tada v. Isso est evidente na Tabela1.19. Tabela 1.19 Tabela-verdade que evidencia (---,pv q)i= (p~ q). pq -,p(--.pVq)(p ~ q )II VVfVV~I2 Vffff 13 fVVVV~14 ffVVV~Como pode ser vistona Tabela1.19,afrmula(-,p vq) interpretada vnasinterpretaes 11, 13 eI4. Notequenessasinterpretaesafrmula(p~ q)tambminterpretada v,oquepermite escrever que (--,pvq) i= (p ~ q).Considerando que (1) e (2) foram provadas, pode-se escrever que (p~ q):: (--,pVq). Teorema1.1Dadasasfrmulas131,132,133, ... ,130 eumafrmulaa, diz-sequeaconseqncia lgica de131,132,j33, ... , 130 se e somente se a frmula 131 /\ 132 /\133 /\ /\130 ~ afor uma tautologia. Prova (1) Sejam as frmulas 131,132, 133, .. ., 130 e ae considere que aseja conseqncia lgica de 131,j32,133, .. ., 130Seja I uma interpretao qualquer.Duas situaes podem ocorrer: (1.1)se 131,132'Pr., 13Jorem todas interpretadas vem 1,ento a tambm vem 1,dado que conseqncia lgica dos131,j32,133, .. .,130Portanto, 13,/\132/\133/\ .../\130 ~ a vem I. (1.2)se um dos pi (i= 1,.. . , n) for f em I, 13,/\132 /\ 133 /\ .../\ 130 ser tambm f em I. Independen-temente deo valor de aem Iser vou f,a frmula13,/\132 /\j33 /\/\130 ~ a vem I, dado queuma implicao sempreinterpretada vse seu antecedente forinterpretado f. 26EdUFSCar -Apontamentos De (1.1)e (1.2) tem-se que J3,/\J32 /\ J33 /\ /\ J3n~ a vem qualquer interpretao, ou seja,J31 /\ J32 /\ J33 /\ /\ J3n~ a uma tautologia. (2) Do fato de J3,/\ J32 /\ J33 /\ /\ J3n~ aser uma tautologia, tem-se que J31 /\ J32 /\ J33 /\ /\ J3n~ a vem qualquer interpretao. Para que isso acontea, se J31 /\ J32 /\ J33 /\ /\ J3nfor vem 1, atambm deve servem 1,ou seja, a conseqncia lgica de J31,J32,J33, ,J3n. Exemplo 1.22Considere novamente que (p~ q) = (-,p vq)(ou seja,que (p~ q)1=(-,p vq)e que(-,p vq)1=(p~ q))s que,desta vez,usando oresultado estabelecido pelo Teorema1.1.O problema novamente mostrar que (p ~ q) =(-,p vq).Para tal, preciso mostrar que: 1.(p~ q)i=(-,p vq)oque,pelo Teorema1.1,significa mostrar que (p~ q)~ (-,p vq) uma tautologia (ver Tabela1.20). 2.(-,p vq)1=(p~ q)oque,pelo Teorema1.1,significa mostrar que (-,p vq)~ (p~ q) uma tautologia (ver Tabela1.21). Tabela 1.20 Tabela-verdade que evidencia a tautologia (p~ q)~ (---,pvq). pq(p~ q)-,p(-,p Vq)(p~ q)~ (-,p Vq) 11 VVVfVV 12 VffffV 13 fVVVVV 14 ffVVVV Tabela 1.21Tabela-verdade que evidencia a tautologia (---,pvq)~ (p~ q). pq -,p(-,p Vq) p ~ q ) (-,p Vq)~ (p~ q) 11 VVfVVV 12 VffffV 13 fVVVVV 14 ffVVVV Observao 1.13A definio de frmulasequivalentes (Definio1.12) pode ser reescrita consi-derando o estabelecido pelo Teorema 1.1. A Definio1.12 estabelece que duas frmulas aeJ3so equivalentes se ambas as conseqncias lgicas a1=J3eJ31=aforem satisfeitas. Considerando oTeorema1.1,a1=J3seesomentesea~ J3foruma tautologia eJ31=ase e somente se 13~ a foruma tautologia.Portanto, duas frmulasaeJ3so equivalentes (a= J3)se e somente se a ~ J3for uma tautologia eJ3~ a for uma tautologia, ou seja, (a = J3)see somente se a~ J3for uma tautologia. A cartilha da lgicaZ1 Diz-seque duasfrmu]asaeP so equiva1entesseesomenteseos valores-verdade deaecoincidirem para qualquer interpretao. Exemplo1.23Considerando a Observao1.13, uma outra abordagem para evidenciar a equi va-lncialgica(p q)= (--,pvq)mostrar que afrmula(p q) (-.p vq) uma tautologia, como feitona Tabela1.22. Tabela1.22 Tabela-verdade que evidencia a tautologia (p q) B(-.p vq). pq(p q)--,p(--,pVq)(p q) (--,pVq) 11 VVVfVV 12 VffffV 13 fVVVVV 14 ffVVVV Teorema1.2Dadasasfrmulasp1,p2,P3, .. .,Pneumafrmulaa, diz-sequeaconseqncia lgica de p1,p2,p3,. .. ,P0 se e somente se a frmula P1 /\ P2 /\ P3 /\ .../\ P0 /\ -.a foruma contradio. ProvaSabe-se pelo Teorema1. 1 que a frmulaa conseqncia lgica das frmulasp1,p2,P3,. , P0 seesomentesep1 /\p2 /\p3 /\ .../\ P0 aforuma tautologia.Equivalentemente,a conse-qncia lgica das frmulasp1,p2,P3, . .. ,Pnse e somente se a negao de p1 /\ p2 /\ p3 /\ .../\ P0 aforuma contradio. Mas, -.(P1/\P2 /\P3/\.../\P a)= -,(-,(pi/\ P2/\ p3/\ .../\ Pn)V a)= ou seja, p1 /\p2 /\P3 /\.../\P0 /\ -,auma contradio. Observao 1.14 No Exemplo1.22, o Teorema1.1foiusado para evidenciar conseqncia lgica como parte do processo de verificao de equivalncia lgica. A seguir, o Teorema1.2 usado com o mesmo propsito, para a mesma equiva1ncia lgica. Tem-se, pois, que: 1.(p q)\= (-.p vq)o que, pelo Teorema1.2, significa mostrar que (p----;q)/\ (--,(--,pvq)) umacontradio (ver Tabela1.23); 2.(--,pvq)\=(p q)o que, pelo Teorema1.2, significa mostrar que (-.p vq)/\(-.(p q)) uma contradio (ver Tabela1.24). 28EdUFSCar -Apontamentos Tabela 1.23 Tabela-verdade que evidencia a contradio (pq) /\ (-, (-,p vq)). pq(p---+q)-,p(-,p Vq)-,(-,p Vq)(p ---+q)/\ (-,(-,p Vq)) II VVVfVff 12 VffffVf 13 fVVVVff 14 ffVVVff Tabela 1.24 Tabela-verdade que evidencia a contradio (-,p vq)/\ (-,(pq)). pq-,p(-,p Vq)(p---+q)-,(p---+ q)(-,p Vq)/\ {-i{p---+q)) I,VVfVVff 12 VffffVf 13 fVVVVff 14 ffVVVff Observao 1.15 Os doismetateoremas anteriores, Teorema1.1e Teorema1.2, so muito impor-tantes.Elesgarantemqueprovar queumafrmulaconseqncialgicadeumconjuntofinito defrmulas equivalente a provar queuma frmula relacionada uma tautologia ou contradio. Para algumas estratgias de provas usa-se o Teorema1.1,chamado de Teorema da Deduo ou de AdmissodePremissas.Outra estratgiade prova, conhecida como Reduo ao Absurdo, esta-belecida pelo Teorema1.2. Observao 1.16 importante deixar claro que os smbolos de conseqncia lgica(!=) e de equi-valncia lgica(=) no so partes do conjunto de smbolos da Lgica Proposicional, mas sim parte dametalinguagem(i.e. ,umalinguagemusadaparadescreveroutra)usadaparadescrevercertas situaes que nela ocorrem. \ Exemplo 1.24 Considere as frmulas a: (p vq)---+r(p---+ r) " (q---+r). A seguir, so abordadas as vrias maneiras de provar que a= A Tabela1.25evidencia osresultados necessrios. Tabela 1.25 Tabela-verdade que evidencia a =p para a: (p vq) r ep: (pr) /\(q r). pqr(pVq)a(p---+r)(q---+r) f3 aA(-.p) P-+aPA(-,a)

1,VVVVVVVVVfVfV 12 VVfVffffVfVfV 13 VfVVVVVVVfVfV 14 VffVffVfVfVfV 15 fVVVVVVVVfVfV A cartilha da lgica29 Tabela1.25 Continuao ... pqr(pvq)a(p ~ r)(qr) 13 a ~ l UA(-,f3)f ~ a f3/\(-.a)a ~ p16 fVfVfVffVfVfV 17 ffVfVVVVVfVfV 18 ffffVVVVVfVfV Usando a definio, a= 13se (a)Pi= a (ou seja, a conseqncia lgica de f3)e (b) ai= p(ou seja, p conseqncia lgica de a). (a) Trs abordagens para evidenciar p i= a: ( a.1)considerando as oito interpretaes (I, , ... , 18), verifica-se na Tabela 1.25 que todas as inter-pretaes que tomam p v (no caso, asinterpretaes 11,13'15,17e18)tomam av tambm. Pode-se dizer, pois, que a conseqncia lgica de 13; (a.2) oTeorema1.1pode ser usadopara estabelecer (ouno)aconseqncia lgica,em que basta verificar sepa uma tautologia (12 coluna da Tabela1.25); (a.3) o Teorema1.2tambm pode ser usado, mostrando quep /\(-.a) uma contradio (13 coluna da Tabela1.25). (b) Trs abordagens para evidenciar ai= 13: (b. l) considerando asoito interpretaes (I, , ... , 18), verifica-se na Tabela 1.25 que todas as inter-pretaes que tomam av (nocaso, asinterpretaes 11,13,15,17e18)tomam 13v tambm. Pode-se dizer, pois, que p conseqncia lgica de a; (b.2) oTeorema1.1podeser usadoparaestabelecer (ouno)aconseqncialgica,emque basta verificar se a~ p uma tautologia ( 1Ocoluna da Tabela1.25); (t.3) o Teorema1.2tambm pode ser usado,mostrando que a/\(---,f3) uma contradio ( 11 coluna da Tabela1.25). Note que a equivalncia a= p tambm pode ser provada (ver Observao 1.13), mostrando que a ~ 13 uma tautologia (ltima coluna da Tabela1.25). Exemplo l.25 Considere as frmulas a: p ~ (q /\ r)e 13:(p ~ q)/\ (p~ r). A seguir, so abordadas as vrias maneiras de mostrar que a=13.A Tabela1.26 evidencia os resultados necessrios. 30EdUFSCar - Apontamentos Tabela 1.26 Tabela-verdade que evidencia a= 13para a: p -4 (q Ar) e 13:(p-4 q) A (p -4 r). pqr(q /\ r)a.(p-t q)(p -t r)j3a.-tj3U/\(-,j3)j3-ta.j3A(-,a.)a.Bj3 II VVVVVVVVVfVfV I2 VVfffVffVfVfV I3 VfVfffVfVfVfV I4 VfffffffVfVfV Is fVVVVVVVVfVfV I6 fVffVVVVVfVfV I7 ffVfVVVVVfVfV I8 ffffVVVVVfVfV Usando a definio, a.= j3se (a)j31= a.(ou seja, a. conseqncia lgica de j3)e (b) a.1=j3(ou seja,j3 conseqncia lgica de a.). (a) Trs abordagens para evidenciar 131==a.: (a.1) considerando as oito interpretaes (I1, ,18), verifica-se na Tabela 1.26 que todas as inter-pretaes que tomam j3v (no caso, asinterpretaes 11,I5,16,I7 e 18)tornam a.v tambm. Pode-se dizer, pois, que a. conseqncia lgica dej3; (a.2) o Teorema1.1podeser usado paraestabelecer (ou no)aconseqncialgica, em que basta verificar sej3-ta. uma tautologia (12-coluna da Tabela1.26); 't> (a.3) o Teorema1.2tambm pode ser usado,mostrando q u e ~ / \ (-.a.) uma contradio (13 coluna da Tabela1.26). (b) Trs abordagens para evidenciar a.1=j3: ~ (b.1) considerandoasoitointerpretaes(I 1, ,18),verifica-sena Tabela1.26quetodasas interpretaes que tornam a.v (no caso, as interpretaes 11,15,16,17 e I8)tornam j3v tam-bm. Pode-se dizer, pois, quej3 conseqncia lgica de a.; (b.2) o Teorema1.1 podeser usadoparaestabelecer (ouno)aconseqncia lgica,emque basta verificar se a.-t j3 uma tautologia (1 Ocoluna da Tabela1.26); (b.3) o Teorema1.2tambm podeser usado,mostrando quea./\ (-.j3) uma contradio ( 11 i coluna da Tabela1.26). Note que a equivalncia a. = j3tambm pode ser provada (ver Observao1.13 ), mostrando que a.~ j3 uma tautologia (ltima coluna da Tabela1.26). A cartilha da lgica31 1.5 LGEBRADALGICAPROPOSICIONAL Aseguir,sodiscutidasequivalnciasimportantesusadasprincipalmenteparaasimplificaoe manipulao de expresses lgicas com vistas prova da validade de argumentos. Algumas dessas equivalncias (s vezes referenciadas como leis) foram j provadas anteriormente usando o mtodo de tabela-verdade. Noteque,com exceo da leida dupla negao,todasasleislistadas na Tabela1.27soabor-dadasem pares, denominados pares duais.Para cada expresso, o dual encontrado substituindo todas asocorrncias dos smbolos verdade e falso por falsoe verdade, respectivamente, bem como substituindo todoconectivo/\ por ve todo conectivo vpor /\. Assubstituies devem ocorrer si-multaneamente. A leida dupla negao seu prprio dual; todas asleis listadas na Tabela1.27 tm um dual, e o mesmo vale para todos os resultados derivados dessas leis. Tabela 1.27 Leis da negao, conjuno e disjuno. LeisNome a/\-,a = falsoLei da contradio av-,a = verdadeLei do meio excludo a/\ verdade = a avfalso= a Leis da identidade a/\ falso = falso avverdade = verdade Leis da dominao a/\a=a Leis idempotentes ava= a --,(-,a) = aLei da dupla negao a/\13=13/\a Leis comutativas avl3=13va (a /\13)/\y =a /\(13/\y) Leis associativas (a V13)Vy = aV(13Vy) a/\ (13vy)=(a/\ 13)v(a/\ y) Leis distributivas av(13/\ y)= (a v13)/\(a vy) --,(a /\13)= -,a v-,13 Leis De Morgan --,(a v13)=-,a /\ -,j3 Observao 1.17 Um procedimento usualmente adotado na manipulao de expresses a substi-tuio(com baseno princpio dasubstituio) deexpresses envolvendo o conectivo condicional ( e o bicondicional ( por suas equivalentes lgicas, como mostra a Tabela1.28. 32EdUFSCar -Apontamentos Tabela 1.28 Equivalncias da condicional e da bicondicional. - -,a v13(1) (aHIJ)- (2) (a Hj3) 13)/\ (13(-.a v13)/\ (-.13va) (3) Asequivalncias(1),(2)e(3)da Tabela1.28soprovadasnasTabelas-verdade1.29,1.30e 1.31respectivamente. Tabela 1.29 Tabela-verdade que evidencia a equivalncia (1) da Tabela1.28. a 13 -,13 13)(-,a V13) 13)B(-.13va) II VVfVfV I2 VfffVV I3 fVVVfV I4 ffVVfV Tabela1.30 Tabela-verdade que evidencia a equivalncia (2) da Tabela1.28. a 13 -,13(a B13) 13)(13 13)/\ (13(aHj3)H -.a ((a ..13)/\(13 II VVffVVVVV I2 VfffffVfV I3 fVVVfVffV I4 ffVVVVVVV 1 Tabela1.31Tabela-verdade que evidencia a equivalncia (3) da Tabela1.28. 13 -,13(a B13)(-.a V13)(-.13va)(-.a v13)/\(-.j3va) (aHl3)H a-,a (-,a v13)/\(-.13va) 11 VVffVVVVV 1i VfffffVfV

fVVVfVffV I,ffVVVVVVV A Tabela1.32 mostra duasimportantesleis(e respectivos duais)quetambm podem ser deri-vadasa partir dasleismostradasna Tabela1.27. AsTabelas1.33e1.34provamasduasleisem questo. A cartilha da lgica33 Tabela1.32 Equivalncias importantes. av(a/\ J3) -aabsoro a/\ (a vJ3) -aabsoro (a/\ J3)v(-,a/\ J3)-f3 (a vf3)/\(-,a vf3) - J3 Tabela1.33 Prova das leis da absoro. av(a/\ f3) a/\ (a vf3) - (a /\ verdade) v(a /\ J3)identidade - a/\ (verdade vJ3) - a/\ verdade = a - (a vfalso)/\ (av J3) - av(falso/\f3) - avfalso - a distributiva dominao identidade identidade distributiva dominao identidade Tabela1.34 Prova dalei(a /\p)v (---.a/\p) =p e sua dual. - ((a/\ f3)v(-.a))/\ ((a/\ 13)v13)distributiva - ((av (-.a))/\ (13v(-,a)))/\ (J3v(a/\ f3)) comutativa (a/\ f3)v(-,a/\ 13) -(verdade/\ (f3v(-.a)))/\ (f3v(f3/\a))meio excludo e comutativa - (f3V(-.a))/\ J3identidade e absoro - 13/\(f3V(-,a))comutativa -f3 absoro ((a vf3)/\(-.a)) v((av J3)/\f3)distributiva -((a v13)/\(-.a)) v((av J3)/\J3)distributiva e comutativa -((a/\ (-.a)) v(J3/\(-.a))) v(f3/\(a vf3))contradio e comutativa -(a vf3)/\(-,a vJ3)(falso v(J3/\(-,a))) vW /\ W va))identidade e absoro -(f3/\(-.a)) Vf3comutativa -J3V(j3/\(-,a))absoro -13 1.6 FORMASNORMAIS possvel observar que h vrias maneiras deescrever uma mesma frmula;asfrmulasequiva-lentes, a seguir, so duas representaes lgicasdo mesmo conceito:(af3)/\y = (-.a vf3)/\ Y: 34EdUFSCar - Apontamentos Muitas vezes, conveniente adotar uma certa padronizao na notao, a fim de poder expressar asfrmulasdeuma maneira nica;apadronizao facilitatantoaidentificaodeumafrmula quanto acomparao entre duas ou mais frmulas. Duas formas,denominadas Formas Normais - FN - , so particularmente utilizadas e conheci-das como Forma Normal Conjuntiva (FNC) e Forma Normal Disjuntiva (FND). Dada uma expres-so da Lgica Proposicional, sempre possvel determinar uma expresso equivalente que esteja representada tanto na Forma Normal Conjuntiva quanto na Forma Normal Disjuntiva. Como ficar mais claro nas sees seguintes, freqentemente necessrio transformar a expresso de uma fr-mula para a forma normal. 1.6.1 FormaNormal Conjuntiva Definio1.13 Diz-se que uma frmula proposicional aest na Forma Normal Conjuntiva (FNC) quando afor uma conjuno f31 /\ f32 /\ f33 /\ /\ f3n,em que cada f3;(1 i n) uma clusula, ou seja, uma disjuno de literais ou um literal. Pode-se ento dizer que uma frmula aest na FNC se e somente se: 1.contm como conectivos apenas /\, ve ---,; 2.---,s opera sobre proposies atmicas, isto , no tem alcance sobre/\ e v; 3.no apresenta operadores de negao sucessivos como---,---,; ., 4.vno tem alcance sobre /\, ou seja, no existem expresses tais como pv( q /\ r). Se f3 uma frmula na Forma Normal Conjuntiva equivalente a a, ento f3 referenciada como FNC(a). Exemplo 1.26 (a) Para a frmula a: (-,p vq) r,tem-se que: FNC(a): (-,p v-,q vr)/\ (p v-,q vr)/\(pvq vr). fcilmostrarqueumaFNCtautolgicaseesomentesecadaelementodaconjunofor tautolgico. (b) As seguintes frmulas da Lgica Proposicional esto na FNC: (b.l)p /\ (q Vr) (b.2) p/\verdade (b.3)---,p/\(-,q V-,r) /\ S A cartilha da lgica35 J aexpresso p/\(r v(p /\ s)) no est na FNC porque adisjuno (r v(p/\s))contm uma conjuno como subfrrnula.Para queuma expresso possaser qualificadacomo umaexpresso na FNC, nenhuma disjuno deve ter uma conjuno como subfrmula. Procedimento 1.1Obteno da FNC. Para aobteno da FNC de uma frmula no tautolgica acom n tomos, procura-se na tabela-verdade de a as interpretaes que avaliam acomo f.Para cada uma dessas interpretaes li ( 1 i ~ 2n)constri-se uma disjuno da seguinte maneira:se na interpretao li o tomo p da frmula a avaliado como v,toma-se -,p e, se for avaliado como f, toma-se p. Em seguida, determina-se aconjuno das disjunes obtidasem cadauma dasinterpretaes l i. Se afrmulaaforuma tautologia, determina-se que FNC(a): pv(:_,p),na qual p uma frmula atmica. Exemplo 1.27 (a) Considere a frmula a: (-.p vq) ~ re sua Tabela-verdade1.35. Tabela 1.35 Tabela-verdade da frmula(---,pvq) ~ r. pqr(--.pVq)~ r 1, VVVV 12 VVff+-13 VfVV 14 VffV Is fVVV 16 fVff+-17 ffVV 18 ffff+-.. Focalizando as interpretaes cujos valores-verdade de aso f,de acordo com oProcedimento 1.1, FNC(a): (-.p v---,qvr)/\(p v-,q vr)/\ (p vq vr). 1.6.2 FormaNormal Disjuntiva Definio1.14 Diz-se que uma frmulaproposicionalaest na Forma Nonnal Disjuntiva (FND) quando afor uma disjuno~vp2 vp3 v...vPn'em que cada ~ i (1~ i ~ n) uma conjuno de literais ou um literal.Pode-se ento dizer que uma frmula aest na FND se esomente se: 1.contm como conectivos apenas A,ve-,; 2.-, s opera sobre proposies atmicas, isto , no tem alcance sobre /\ ev; 3.no apresenta operadores de negao sucessivos como-..,-,; 36EdUFSCar -Apontamentos 4./\no tem alcance sobre v, ou seja, no existem expresses tais como p/\ (q vr). Se B uma frmula na Forma Normal Disjuntiva equivalente a a, ento B referenciada como FND(a). Exemplo 1.28 As seguintes frmulas do Clculo Proposicional esto na FND: pvverdade -,p V(-,q /\ -,r) VS pv(q/\r/\S) (p /\ q) v(r /\ p /\ -,q) v(-.s) J aexpresso-,(p/\q)vrnoest na FND,uma vez queelacontm uma subfrmula (no atmica)negada.Apenassubfrmulasatmicaspodem estar negadas na representao em forma normal. Procedimento 1.2Obteno da FND. Para a obteno da FND de uma frmula no contraditria acom n tomos, procura-se n'a tabela-verdade de aas interpretaes que avaliam acomo v.Para cada uma dessas interpretaes l;( 1 i 2n)constri-se uma conjuno da seguinte maneira: se na interpretao li o tomo p da frmu-la a avaliado como v, toma-se p e, se for avaliado como f,toma-se -,p. Em seguida, determina-se a conjuno das disjunes obtidas em cada uma das interpretaes li.Se a frmula afor uma contradio, determina-se que FND(a): p /\ (-.p), na qual p uma frmula atmica. Exemplo 1.29 Considere uma frmula acuja tabela-verdade seja Tabela1.36. Tabela1.36 Tabela-verdade da frmula a. pqra l,VVVV12 VVfV13 VfVf 14 Vfff 15 fVVf 16 fVff 17 ffVf 18 fffVA cartilha da lgica.... Focalizando as interpretaes cujos valores-verdade de aso v,de acordo com o Procedimento 1.2, FND(a): (p/\ q /\ r)v(p /\ q /\ --,r)v(--.p/\ --,q/\ -.r). 1.6.3 Obteno daFNC sem o uso de tabela-verdade AobtenodaFNCdeumadadafrmulaapodeserconseguidapormeiodasubstituiode subfrmulas deapor suas frmulas equivalentes. Este processo repetido at que a frmula nor-mal desejada seja obtida. Procedimento 1.3 Para aobtenoda formanormalconjuntivade uma frmulaaosseguintes passosdevemser seguidos, quando passveis de serem aplicados. ( 1)repetidamente usar as equivalncias a seguir para a eliminao dos conectivos lgicos tt e ~ .(2) att B=((-,a) v~ /\((--.B)va) a ~ B=((-.a) vB) (a) repetidamenteutilizar aleida dupla negaopara aeliminao denegaes mlti-plas: --,(-.a) = a (b) repetidamente utilizar asleis De Morgan para a reduo do escopo da negao: --,(a/\ B) =-,a v-.B --,(a vB)==-.a /\ -.B (3)quandoaexpressoobtidanotiversubexpressescompostasnegadas,asduasleisa seguir so utilizadas para reduzir o escopo do v. avW /\y)=(a vB)/\(a vy) (a/\ B)vy =(a vy)/\ W vy) As duas leis anteriores seguem das leis comutativa e distributiva. (1.1) (1.2) Exemplo 1.30 A obteno da FNC da expresso lgica --,((pv-.q) A-.r) est mostrada na Tabela 1.37. 38EdUFSCar - Apontamentos Tabela 1.37 Determinao da FNC de -,((p v-,q) /\ -,r). ----,(pV---,q)V---,---,fDe Morgan ----,(pV---,q)Vfdupla negao ---,((pV---,q)/\ ---,f) -(---,p/\ ---,---,q)VrDe Morgan -(---,p/\ q) Vfdupla negao -(--.pvr)/\ (p vr)(l.2) Exemplo1.31AobtenodaFNCda expressolgica(p/\q)v(r /\ (svt))est mostrada na Tabelal.38. Tabela 1.38 Determinao da FNC de (p/\q)v(r /\(svt)). =(p v(r /\ (s vt)))/\ (q v(r /\ (s vt)))(l.2) (p/\ q) v(r /\ (svt)) =(p Vr)/\ (p Vs Vt)/\ (q Vr)/\ (q Vs Vt)(1.1) Exemplo 1.32 A FNC da expresso lgica a: (-.p vq) robtida usando a regra da tabela (Ta-bela1.39) e,na seqncia, obtida usando equivalncias lgicas por meio do Procedimento1.3. Tabela 1.39 Tabela-verdade dafrmula(-,p vq) r. pqr---,p(---,pVq)(---,pVq)-H II VVVfVV 12 VVffVff-13 VfVffV 14 VffffV 15 fVVVVV 16 fVfVVff-17 ffVVVV 18 fffVVff-De acordo com o Procedimento1.1, FNC((-.p vq) r):(--.pv---,qvr)/\ (p v--,qvr) /\ (p v q Vr). A Tabela 1.40 evidencia a equivalncia das duas representaes, ou seja, ( (---,pvq) r) = (---,pv ---,qvr) /\ (p v--.q vr) /\ (p vq vr). Para facilitar a visualizao, a seguinte nomeao foi adotada, a: ((---,pvq) r),p:(---,pv---,qvr),:(p v---,qvr) e:(p vqvr), respectivamente. Tabela 1.40 Tabela-verdade da equivalncia a= p /\ /\ . pqr ---,p---,q ap8p /\/\aB(P /\ 8 /\) 1,VVVffVVVVV 12 VVfffffVVfV A cartilha da lgica39 Tabela 1.40 Continuao ... pqr-.p --,q a 13 8.j3/\/\.aH(l3 /\ /\) 13 VfVfVVVVVVV 14 VfffVVVVVVV 15 fVVVfVVVVVV 16 fVfVffVfVfV 17 ffVVVVVVVVV Is fffVVfVVffV Por outro lado, usandoo Procedimento1.3, aFNC pode ser obtida por meio do uso deequiva-lncias lgicas, como mostra a Tabela1.41. Tabela 1.41Determinao da FNC de((-,p vq) r)usando equivalncias lgicas. - -.(-.p vq)vrequivalncia da implicao ((-.p vq) r)- (-.(-.p) /\ -.q) vrDe Morgan - (p /\ -.q) vrdupla negao - (p vr)/\ (-.q vr)(1.2) A FNC obtida pelo Procedimento1.3, mostrado na Tabela1.40, equivalente FNC obtida por meio deequivalnciaslgicas,mostrada na Tabela1.41- a segunda expresso,entretanto, uma versosimplificadada primeira. A Tabela1.42exibeaequivalncia entreasduasexpresses,ou seja: 13/\ 8 /\.=(p vr)/\( -.q vr) tal que 13:(-.p v-.q vr), 8:(pv-.q vr)e /...:(pvq vr). Tabela 1.42 Tabela-verdade daequivalncia que/\ )= ((p vr)/\ (-,q vr)). 13/\8/\A (p Vr)/\(13/\ /\ .)H pqr--,p--,qpVr--,qVr (--,qVr)((p vr)/\ (-.q vr)) 11 VVVffVVVVV 12 VVffffVffV 13 VfVfVVVVVV 14 VfffVVVVVV 15 fVVVfVVVVV 16 fv.fVfffffV 17 ffVVVVVVVV 18 fffVVffVVV 40EdUFSCar - Apontamentos Existe um procedimento similar ao Procedimento1.3para aobteno da FNC, usando equiva-lncias lgicas.O passo 3 do Procedimento1.3, entretanto, precisa ser alterado para: (3)quando a expresso obtida no tiver subexpresses compostas negadas, as duas leis a seguir so utilizadas para reduzir oescopo do v. 1.6.4 A notao clausal a/\ (J3vy)=(a/\ J3)v(a/\ y) (a vJ3)/\y =(a/\ y)v(J3/\y) (1.3) (1.4) AFNCdeparticularinteressenoentendimentoeusodalinguagemdeprogramaoProlog. Corno visto na Seo 1.6.1, urna frmula arepresentada na FNC uma conjuno de clusulas: Uma clusula, por sua vez, uma disjuno de literais (ou seja, tomo ou tomo negado), isto : Urna das vantagens de se ter a FNC de uma dada frmula a poder garantir que se o valor de a em urna determinada interpretao for v,ento cada clusula tambm, separadamente, interpreta-da v,uma vez que a FNC uma conjuno de clusulas. Este fato torna a frmula mais facilmente manipulvel. Como a FNC de uma frmula ada Lgica Proposicional sempre uma conjuno de clusulas, a ordem em que estas clusulas so escritas irrelevante - pela propriedade associativa da conjun-o(/\). Assim, pode-se dizer que aFNC uma coleo de clusulas. Escreve-se, ento, a FNC de uma frmula acorno: sendo que a conjuno entre as clusulas fica implcita. Nomeia-se de coleo apenas para indicar que a ordem no relevante. Neste sentido, pode-se dizer que qualquer frmula da Lgica Propo-sicional uma coleo de clusulas. Analogamente, uma clusula Ci ter a forma: em que cada Li(1 i k) um literal. Aplicando omesmo raciocnio anterior, pode-se dizer que uma clusula uma coleo de literais na qual a disjuno est implcita, ou seja, Exemplo 1.33Seja Pode-se escrever que: a: ( ( -,p vq) /\ ( -,p vr)) ~ s e seja p a FNC(a), P:(pv-.q vs)/\ (-.p v-.r vs)/\(-,q v-,r vs) C 1 :(p V-,q VS) C2:(-,p v-.r vs) e C3:(-.q v-,r vs) A cartilha da lgica41 A FNC pode ser representada pela coleo das trs clusulas, na qual a conjuno est implcita, isto : Uma possvelconveno escrever a frmulacomo uma clusula aps a outra, lembrando que elas esto conectadas por/\: Comocadaclusulaumacoleodeliteraisqueestoconectadas por v, para cadaclusula pode-se escrever primeiro os literais positivos e,logo aps, os negativos, obtendo-se: Essa separao entre literais positivos e negativos prepara a clusula para a introduo danota-o definida por Kowalski (1974). Na notao,as clusulas so representadas por: CI:s, p~ qC2:s ~ r pCj:s ~ q rsignificando s v p ~ qs ~ r /\ p s ~ q /\ r 42EdUFSCar - Apontamentos ou seja, existe uma disjuno implcita nos literais esquerda d o ~ chamados deconcluses, e umaconjuno implcita nosliterais direta d o ~ chamados de condies (ou premissas).Deve ser observado que a notao anterior equivalente a: Observao 1.18 Uma clusula genrica na notao de Kowalski (1974): equivalente a: que equivalente a: que equivalente a: Dependendo donmero deliterais envolvidos na clusula, os casos especiais mostrados na Ta-bela1.43 podem ocorrer. Tabela 1.43 Tipos de clusulas. m >1as concluses so indefinidas, isto ,h vrias concluses. m :S1 (a) m= 1,n >O (b)m=l,n=O so as chamadas clusulas deHorn, que tm como casos parti-culares (a), (b),(e) e (d). A1 +- B1,B2, ,Bn chamada declusula definida,isto , existe somente uma con-cluso. AI+-chamadadeclusuladefinidaincondicionaloufato.Neste caso,o smbolo +- abandonado. Tabela 1.43 Continuao ... m=O,n>O (c)m=O,n>O+-B"B2, ,Bn conhecida como negao pura de B,, B2, ,Bn. (d) m=O, n =O chamada de clusula vazia e denotada por nil. A cartilha da lgica43 As nicasclusulasque podem ser representadasusando alinguagem de programao Prolog so asclusulas de Horn (os m o l o ~ representado por:- na sintaxe do Prolog deEdinburgh). Em uma situao em que um dado conhecimento pode ser representado utilizando Lgica Propo-sicional, apenas as expresses que forem clusulas de Horn sero passveis de serem representadas em Prolog. 1.7 INFERNCIA LGICAE SISTEMAS DEDERIVAO Padres de raciocnio podem ser expressos de vrias maneiras. Em portugus, por exemplo, a con-cluso tipicamente colocada aps as premissas e "anunciada" por palavras indicativas, tais como: "ento", "logo", "portanto", "como conseqncia", "conclui-se", etc.Um argumento correto sea concluso segue logicamente das premissas, como formalmente estabelecido na Definio1.15. Definio 1.15 Um argumento uma seqncia" a2,a3,an (n ~ 1) de proposies, na qual as proposies ai ( 1 ::;i ::;n-1) so chamadas de premissas e a proposio a0 chamada de concluso. Indica-se um argumento por Um argumento a1,a2' a3,. . ., n-i1- an um argumento vlido se esomente se a frmula 1/\ 2 /\ 3 /\ ../\ n-1~ anfor uma tautologia, ou seja, " a2,a3,. ,an-1 i= an.Essa afirmao justificada pelo Teorema1.1, da Seo1.4. Um argumento vlido pode ser lido como: Para n=1,considera-se por extenso oargumento vlido se e somente se a1 for tautolgica. 44EdUFSCar -Apontamentos Eventualmente, averificao da validade de um argumento por meio de tabelas-verdade pode ser um trabalholongo,dado quedepende do nmero de tomos nele existentes. A verificao da validade de um argumento que envolve sete tomos (ou seja, proposies atmicas), por exemplo, envolve aconstruo deuma tabela-verdade com 27 =128linhas.Outra maneira de evidenciar a validadedeargumentospor meio deumprocedimentodescritopor uma seqncia de passos, que faz uso de argumentos vlidos j conhecidos e de equivalncias, processo que leva noo de derivao ou prova formal. Observao 1.19 Existem diferentes sistemas para a realizao de derivaes. Todos os sistemas tm as seguintes caractersticas em comum: 1.consideram uma lista de argumentos lgicos admissveis, chamada de regras de inferncia. Essa lista referenciada como L; 2.a derivao uma lista de expresses lgicas.Originalmente, essa lista vazia. Expresses podem ser adicionadas lista se forem premissas ou se puderem ser obtidas a partir das ex-presses anteriores, por meio da aplicao de regras de inferncia. Esse processo continua ~at que a concluso seja obtida. Definio 1.16 Considere as frmulas a,, a2,a3, ... ,cx.0 ep da Lgica Proposicional. Diz-se que uma sequncia finitade(rmulas Cl' C2, ... ,Ck uma prova (ou deduoou derivao)depa partir de a1,a2,a3, ... ,a0 (consideradas premissas) see somente se: 1.cada ci for uma premissa aj (1~ ~ n);ou 2.Ci provm das frmulas precedentes, pelo uso de um argumento vlido de L; ou 3.Ci provm do uso do princpio de substituio usado em uma frmula anterior; ou 4.ck p. Diz-se, ento, quep dedutvel a partir de a1,a2,a3, ,a0 ou que P um teorema.Se a seqn-cia puder ser construda, isto , se existir uma derivao para a concluso p, dado que a1,a2,a3, ... , a0 so as premissas edado que L um conjunto de regras de inferncia admissveis, diz-se que o argumento vlido, ou seja, ai' a2,a3, ... ,a0 !- P vlido. Observao 1.20 Na maioria dossistemas para derivaes formaisoconjunto de regrasdeinfe-rncia admissveis fixo- nenhuma outra regradeinferncia pode ser usada a menos queesteja includa em L. Para os exemplos e discusses a seguir, o conjunto L de regras de inferncia consi-derado apresentado na Tabela 1.44. A cartilha da lgica45 Tabela 1.44 Regras de inferncia. RegraNome da regra a, a--t13j=13modus ponens a--tl3, ---,13j=-,amodus tol/ens a--tl3,13--t yi=a--t ysilogismo hipottico (regra da cadeia) av 13,-,a j=13silogismo disjuntivo av 13,---,13i=asilogismo disjuntivo (variante) a/\ 13i=asimplificao a/\ 13i=13 simplificao (variante) a, 13i=a/\13conjuno (ou combinao) a--tj3, -,a--tj3 [=13de casos a[= av13adio 131=UV13 adio (variante) a--t 13,y--t ,aVyj=13Vdilema construtivo a--t 13,y--t 8, ---,13V-,j=-,a V-,ydilema destrutivo a--t13i=-,13--t -,acontraposio a, -,ai= 13da inconsistncia a--t13,13--t a[=aH13introduo da equivalncia aH13[=a--t 13eliminao da equivalncia aH13i=13--tavariante da eliminao da equivalncia A regra da inconsistncia segue do fato de que a/\ -,a sempre avaliada f e, portanto, a, -,a [=13 trivialmente verdade. A lei da inconsistncia tem um grande impacto em sistemas lgicos, pois se uma simples contradio pode ser derivada a partir das premissas (nocaso,a derivao de ae tambm a derivao de -,a), ento toda expresso lgica possvel e imaginvel 13tambm pode ser derivada. fundamental, pois, que as premissas no permitam a derivao de qualquer contradio, caso contr-rio, em um tal sistema, tudo pode ser provado. Regras de inferncia devem ser escolhidas de tal maneira que possam derivar apenas resultados que estejam corretos. Isso significa que L no deve conter qualquer falcia.Uma falcia permite en-contrar uma concluso que no possa ser derivada das premissas e, conseqentemente, no correta. Observao 1.21 Um sistema para derivaes no deve ser apenas correto, mas tambm completo. Por completo entende-se um sistema que viabiliza a derivao de toda concluso que logicamente segue das premissas.Osistema de regrasdescrito na Tabela1.44 no completo.Considere alei do meio excludo av-,a. Essa lei vlida sem qualquer premissa, ou seja,J=av-,a. fcil ver 46EdUFSCar - Apontamentos que,sem qualquer premissa, nenhuma das leis da Tabela1.44 pode ser usada.Conseqentemente, av-,a no pode ser derivada se L for o conjunto de regras da Tabela 1.44. A seguir, so mostrados algunsexemplosdeverificao da validadedeargumentos, usando argumentos vlidos j conhe-cidos e equivalncias. Observao1.22Em Lgica, oquechamado de teoria dado por um conjunto de premissas e por um conjunto de todas asconcluses que podem ser derivadas a partir das premissas. Freqen-temente,aspremissasdeumateoriasochamadasdeaxiomaseasconclusesquepodemser derivadas dos axiomas so chamadas de teoremas. Observao 1.23 Equivalncias representam uma regra especial nas derivaes. Toda equivalncia podeser tratadacomoumaregradeinfernciaquepermitesubstituir cada uma daswffspor sua equivalente ou que permite substituir uma subfrmula de uma wff por sua equivalente. Exemplo 1.34 Considere: Se as uvas caem, ento a raposa ascome. Se a raposa as come, ento esto maduras. As uvas esto verdes ou caem. Logo, A raposa come as uvasse e somente se as uvas caem. Identificando as proposies atmicas nas sentenas em lngua natural escritas neste Exemplo 1.34 e nomeando-as com os smbolos convencionados para tomos na Lgica Proposicional, tem-se: p:as uvas caem q:a raposa come as uvas r:asuvasesto maduras Reescrevendo o enunciado anterior usando a linguagem da Lgica Proposicional, tem-se: ~ qq ~ r-,r Vp logo ~ qA Tabela 1.45exibe a prova da concluso como estabelecida na Definio1.16. A cartilha da lgica47 Tabela1.45 Construo da prova de p Bq. Tem-se c1 p ~ q premissa -c2 q ~ r premissa c3 --,rVppremissa Deduz-se c4 r ~ p (C3:equivalncia) cs q ~ p (C2 + C4 +silogismo hipottico) c6 (p~ q)/\ ( q ~ p)(C1 + C5 +conjuno) c7 (p tt q)(C6:equivalncia) A seqncia C1,C2,C3,C4,C5,C6,C7 uma prova da concluso p tt q e o argumento (p ~ q), (q~ r),(--,r vp)1- (ptt q) vlido. Exemplo 1.35Considere: Gabriel estuda ou no est cansado. Se Gabriel estuda, ento dorme tarde. Gabriel no dorme tarde ou est cansado. Logo, Gabriel est cansado se e somente se estuda. Identificando as proposies atmicas nas sentenas em lngua natural escritas neste Exemplo 1.35 e nomeando-as com ossmbolos convencionados para tomos na Lgica Proposicional, tem-se: p:Gabriel estuda q:Gabriel est cansado r:Gabriel dorme tarde Notequeconvenienteidentificar,comotomos,sentenas quenoenvolvam a negao.No casoparticular desteexemplo,emvezdeidentificarcomotomoasentenaGabriel no dorme tarde,identifica-se como tomo (r) a sentena Gabriel dorme tarde,e a sentena Gabriel no dor-me tarde reescrita em Lgica Proposicional como -.r.Reescrevendo o enunciado anterior usando a linguagem da Lgica Proposicional, tem-se: p V--,q p ~ r1 --,r Vq r. 1 ~logo (r ~ r pttq 48EdUFSCar -Apontamentos A Tabela1.46 exibe a prova da concluso corno estabelecida na Definio1.16. Tabela 1.46 Construo da prova de p Bq. Tem-see] p V--,qpremissa c2 ~ r premissa c3 --,r Vqpremissa Deduz-se c4 q ~ (C1:equivalncia) cs r ~ q (C3:equivalncia) c6 ~ q (C2 + C5 + silogismo hipottico) c7 (p~ q)/\ ( q ~ p)(C6 +C4 +conjuno) cs (pttq)(C7: equivalncia) A seqncia CI'C2,C3,C4,C5,C6,Cr C8 urna prova da concluso ptt qeoargumento (p v---,q),(p~ r),(--,r vq)1- (ptt q)vlido. Exemplo 1.36 Verificar a validade do argumento descrito em lngua natural corno: Se a Terra redonda ento a Lua oval. Se a Lua oval, ento Saturno no tem anis. Se a Terra no redonda ento Saturno no tem anis. Logo Saturno no tem anis. Identificando as proposies atmicas nas sentenas em lngua natural escritas neste Exemplo 1.36 e nomeando-as com os smbolos convencionados para tomos na Lgica Proposicional, tem-se: p:a Terra redonda q:a Lua oval r:Saturno tem anis Reescrevendo o enunciado anterior usando a Lgica Proposicional, tem-se: --,p~ --,r logo --,r A Tabela1.4 7 exibe a prova da concluso corno estabelecida na Definio1.16. A cartilha da lgica49 Tabela 1.47 Construo da prova de -.r. Tem-see, ~ q premissa c2 q ~ -,rpremissa c3 -,p---+ -,rpremissa Deduz-se c4 p---+-,r(C1 + C2 +silogismo hipottico) cs -,r(C3 + C4 +de casos) A seqncia C1,C2,C3,C4,C5 uma prova da concluso -.r e o argumento (p---+q),(q~ -.r), (-.p ---+-.r) 1- -.r vlido. Exemplo 1.37 Identificar a prova da concluso do argumento: -,p ---+q,q --+r,---,rVS,-,S 1- p A Tabela1.48exibe a prova da concluso como estabelecida na Definio1.16. Tabela 1.48 Construo da prova dep. Tem-see,-.p-+ qpremissa c2 q-+ rpremissa c3 -,r VSpremissa c4 -,s premissa Deduz-se cs -,r(C3 + C4 +silogismo disjuntivo) c6 -,q(C2 + C5 + modus tol/ens) c1 -,(-,p)(C2 + C7 + modus tollens) cs p(C7:equivalncia dupla negao) A seqncia C1,C2,C3,C4,C5,C6,C7,C8 uma provadaconcluso pe oargumento -.p--+ q, q --+r,-.r vs, -,s 1- p vlido. Exemplo 1.38 Identificar a prova da concluso doargumento: p~ q, -.q, -,p--+ (r vs),r--+ t, u--+ ---,t,u 1- s A Tabela1.49 exibe a prova da concluso como estabelecida na Definio1.16. Tabela 1.49 Construo da prova des. Tem-se cl p-+ qpremissa c2 -,qpremissa c3 -,p ~ (r vs)premissa 50EdUFSCar - Apontamentos Tabela 1.49 Continuao ... c4 premissa cs premissa c6 upremissa Deduz-se c7 -..,p (c 1+ c2 + modus tol/ens) cs rvs(C3 + C7 +modus ponens) c9 -..,t (C5 + C6 +modus ponens) c, -..,r (C4 + C9 + modus tol/ens) c" s(C8 + C10 +silogismo disjuntivo) A seqncia C1,C2,C3,C4,C5,C6,C7,C8,C9,Cw,C11 uma prova da conclusos e o argumento p q,-.q, -..,p (r vs),rt, u -.t, u1- s vlido. Exemplo 1.39 Identificar a prova da concluso do argumento: p q, r S,( q VS) t, -..,t1- -..,p/\ -..,f A Tabela1.50 exibe a prova da concluso como estabelecida na Definio1.16. Tabela 1.50 Construo da prova de -.p "-.r. Tem-sec, premissa c2 spremissa c3 (q VS) tpremissa c4 -.tpremissa Deduz-se cs -..,(qVs)(C3 + C4 +modus tollens) c6 -..,q/\ -..,s(C5 +equivalncia De Morgan) c7 -..,q(C6 +simplificao) cs -..,s (C6 + simplificao) c9 -..,f(C2 +C8 +modus tollens) c, -..,p (c 1+ c7 +modus tollens) c" -..,p/\-..,r(C10 +C9 +conjuno) AseqnciaC1,C2,C3,C4,C5,C6,C7,C8,C9,Cw C11 uma prova da concluso-..,p/\-.r eo argumento p q, rs, ( q vs)t, -.t 1- -..,p/\ -.r vlido. Observao 1.24 Em Matemtica, para provar que 13,o seguinte argumento informal usado: 1.assuma a, que adicionado ao conjunto de premissas; A cartilha da lgica51 2.prove p, usando ase necessrio; 3.descarte a, significando que no mais necessariamente verdade e conclua p. Exemplo1.40[Grassmann&Tremblay,1996].Umcasaltemummeninoeestesperandouma segunda criana. Prove que se a segunda criana foruma menina ento o casalter ummenino e uma menina. Seja: p:a primeira criana do casal um menino q:a segunda criana do casal uma menina O que se quer provar q(p/\q),dado quea premissa p.De acordo com o Teorema da De-duo (discutido a seguir), a prova pode ser conduzida como: 1.p verdade:a primeira criana do casal ummenino; 2.assuma q:ou seja, assuma que a segunda criana do casal uma menina; 3.com base em p e em q,conclua p/\q, pela regra deinferncia da conjuno; 4.nesseponto,o Teorema daDeduopermiteconcluir queq (p/\q).A suposiodeq pode ser descartada, ou seja, q(p /\ q) verdade mesmo que q seja falso:neste caso, q (p/\ q) trivialmente verdade. clara a razo pela qual esse padro de prova correto. Na prova de a p preciso considerar apenas o caso em que a avaliada v; se afor f, a f3 trivialmente v. Se afor v,ento pode ser adicionada s premissas. Essencialmente,aregraestabelecequeuma suposio podeser convertidanoantecedente de umacondicional;em algumasrefernciaso processodescrito tratado comoumaregradeinfe-rncia chamada de regra deintroduo da condicional.Eladifere das outras porque emprega um raciocniohipottico,isto,umaestratgiadeprovafundamentadaemhiptese,quepodeser considerada uma suposio feitano contexto doargumento,como objetivo de mostrar que deter-minada concJuso segue da suposio. A maneira mais geral para provar uma condicional colocar seuantecedente como hiptese(ouseja,admiti-lo como possibilidade nocontexto doargumento) e ento mostrar que seu conseqente deve se seguir. Exemplo1.41Esteexemplo ea discussosobreeleforamextrados deNolt &Rohatyn(1991)e adaptados.Suponha queumcorredor machucouseu tornozeloumasemanaantesdeumagrande corrida,e aintenoseja persuadi-lo a parar decorrer por algunsdias,a fimdequeseutornozelo sare. Algum pode alert-lo fazendo a seguinte afirmao condicional: "se voc continuar a correr, no estar apto a disputar a corrida". A resposta docorredor eventualmente pode ser:"prove isso". .: ..52EdUFSCar - Apontamentos A maneira maisgeraldeprovar uma condicionalconsiderar seu antecedentecomohiptese (isto,admiti-lonocontextodoargumento)eentomostrar queoconseqentedocondicional deve seseguir.Para fazer isso, o argumento pode ser elaborado da seguinte maneira: Seu tornozelo est muito inchado. Suponhamos que voc continue a correr. Se ele est muito inchado evoccontinuar acorrer,seutornozelonovaisararemwna semana.Seelenosararemwna semana,ento vocno estar aptoa disputar a corrida.Dessemodo,noestaraptoa disputara corrida. Este argumento um argumentohipottico. A palavra "suponhamos" um indicador dehip-tese, assinalando queo enunciado "voc continue a correr" uma hiptese. Dessa hiptese, a con-cluso "voc no estar apto a disputar a corrida" descrita a seguir.O argumento est construdo com base em trs suposies: 1.seu tornozelo est muito inchado; 2.seseu tornozelo est muitoinchadoe voc continuar a correr,entoseu tornozelo no ir sarar em uma semana; 3.seseu tornozelo no sarar em uma semana, ento voc no estar apto a disputar a corrida. As trs suposies anteriores so consideradas verdadeiras - diferentemente da hiptese, que foi assumida em considerao ao argumento. Uma vez admitida as suposies, o argumento hipottico mostra que se a hiptese "voc continuar a correr" for verdadeira, ento a concluso do argumento hipottico, "voc no estar apto a disputar a corrida'', tambm deve ser verdadeira. Assim, mostra-se que a expresso condicional: Se voc continuar a correr, ento voc no estar apto a disputar a corrida. verdadeira,oqueexatamenteoquesequeriaprovar.Aexpressocondicionalfoideduzida colocando como hiptese seu antecedente e mostrando que seu conseqente segue-se do conjunto formado pela hiptese com as premissas. fato que a correo do argumento depende da veracidade das suposies - na vida real, a vera-cidade delas pode ser duvidosa. A correo do argumento, entretanto, no depende da veracidade da hiptese. Considerando as suposies e independentemente de o corredor continuar ou no a correr, deve ainda ser verdade que, se ele continuar correndo, ele no estar apto a disputar a corrida. A hi-ptese adicionada somente para mostrar que, dadas as suposies, ela implica a concluso "voc no estar apto a disputar a corrida". Uma vez provado isso, a hiptese descartada e a expresso condicional que representa a concluso estabelecida somente com base nas suposies. A forma-li7.ao doargumento est na Tabela1.51, com a seguinte simbologia: p:seu tornozelo est muito inchado. q:voc continua a correr. r:seu tornozelo no ir sarar em uma semana. s:voc est apto a disputar a corrida. Oargumento pode ser reescrito em Lgica Proposicional como: p, (p "q) ~ -.r, -.r-,s 1- q~ -,s Tabela 1.51Exemplo de uso da regra deintroduo da condicional. e,ppremissa c2 (p "q)-.rpremissa c3 -,r-,spremissa c4 qhiptese cs p/\ q(C1 +C4 +conjuno) c6 -,r(C2 +C5 +modus ponens) c1 -,s(C3 +C6 +modus ponens) A cartilha da lgica53 cs q~ - s (C 4 - C7 +introduo da condicional) Note na Tabela1.51que,apartir daintroduoda hipteseq(inclusiveela),asfrmulasso endentadas direita na coluna, para indicar a durao do argumento hipottico, ou seja, a parte da prova na qual a hiptese considerada. Como argumentos hipotticos so construdos com a intro-duo de uma hiptese com um escopo de atuao na prova, no que segue a seqncia de frmulas que identifica aprova da concluso noapresentada. A prpria tabela evidencia aprova, com o escopo da validade da hiptese assinalada via deslocamento direita. Observao 1.25 A regra da introduo da condicional pode ser enunciada como: dada a derivao de urna wff j3a partir de urna hiptese a, pode-se descartar a hiptese e inferir a wff a~ j3.A regra estabelecida pelo Teorema da Deduo. Teorema 1.3 (Teorema da Deduo) Sejam ae13duas wffs e 81,82,83, ...premissas. Se juntos a, 81,82,83, ...logicamente implicam 13,ento 1,82,3, ...logicamente implicam~ 13. Observao 1.26 Asregrasdeinferncia da Tabela1.44com oTeorema da Deduo formam um sistema completo. Exemplo 1.42 Usando deduo natural,o argumento a seguir est provado na Tabela1.52. p~ q, q~ r1- p~ r 54EdUFSCar -Apontamentos Tabela 1.52 Prova usando a regra de introduo da condicional. c1 p-;qpremissa c2 q-;rpremissa c3 phiptese cs q(C1 + C3 + modus ponem) c6 r(C2 + C5 + modus ponem) c p-;r(C3 - C6 + introduo da condicional) Exemplo 1.43Considere a prova do argumento (pA q)-; r 1- p-.; ( q -; r). Este exemplo ilustra a situao na qual a concluso a ser derivada uma expresso condicional que tem, como conseqente, outra expresso condicional. A derivao emprega a mesma estratgia anterior.O antecedente da condicional mais externa assumido como hiptese.Como, no caso, o conseqente outra expresso condicional, pode-se assumir como uma nova hiptese o anteceden-te dessa ltima condicional e derivar sua concluso, como mostra a Tabela1.53. Tabela 1.53 Prova usando a regra de introduo da condicional. c1 (pAq)-;rpremissa c2 phiptese c3 qhiptese c4 pA q(C2 + C3 +conjuno) cs r(C,+ C4 + modus ponem) c6 q-; r(C3 - C5 + introduo da condicional) c7 p-;(q-;r)(C2 - C6 +introduo da condicional) Note que C2 o antecedente da concluso, inserido na prova como hiptese. Para derivar a con-cluso (que a condicional q -.; r),a partir desse ponto, coloca-se como hiptese o antecedente da condicional, isto , q.Como uma nova hiptese, ela requer um deslocamento direita para indicar que a segunda hiptese vigente. Como a concluso r derivada (C5), a hiptese q pode ser descar-tada e a condicional q-.; r pode ser inferida pela regra de introduo da condicional. Foi mostrado ento queq -.; r segue da hiptese original p. A hiptese p permanece vigente at ser descartada e a concluso desejada (q-.; r)ser inferida. Observao 1.27 Algumas wffs so passveis de serem provadas sem suposies (premissas)- so osteoremas.A prova deum teoremaseinicia com umaou maishiptesesqueserodescartadas pela introduo da condicional, como mostra o Exemplo1.44. A cartilha da lgica55 Exemplo1.44A Tabela1.54mostraaprova de1- p (pvq)usando aregradeintroduoda condicional. Tabela 1.54 Prova de\-p(p vq). c1 phiptese c2 pvqe,+ adio c3 p (pVq)(C1 - C2 +introduo da condicional) Exemplo1.45A Tabela1.55mostraaprova depvq1- qvpusandoaregradeintroduoda condicional. Tabela 1.55 Prova de p vq \- q vp. c1 p v qpremissa c2 phiptese c3 q v p(C2 +adio) c4 p (qVp)(C2 - C3 +introduo da condicional) cs qhiptese c6 q v p(C5 +adio) c7 q (qVp)(C5 - C6 +introduo da condicional) cs (q Vp)V(qVp)(C1 + C4 + C7 + dilema construtivo) c9 (qVp)(C8 +equivalncia - idempotncia) Exemplo1.46A Tabela1.56mostra a prova de(p/\ q)v(p/\r)1- p/\(qvr)usando a regra de introduo da condicional. Tabela 1.56 Prova de(p "q) v(p /\ r)\- p /\ (qvr). e , (p/\ q)V(p/\ f)premissa c2 (p/\ q)hiptese c3 p(C2 +simplificao) c4 q(C2 +simplificao) cs qvr(C4 +adio) c6 p /\ (q v r)(C3 +C5 +adio) c7 (p/\ q) p /\ (qVr)(C2 - C6 + introduo da condicional) cs (p/\ r)hiptese c9 p(C8 +simplificao) e, r (C8 +simplificao) 56EdUFSCar -Apontamentos Tabela 1.56 Continuao ... c11 qvr(C10 +adio) c12 p/\(qvr)(C11 +adio) c13 (p /\ r)~ p/\ ( q vr)(C8 - C12 + introduo da condicional) c14 p/\(qvr)(C1 +C7 +C13 +dilema construtivo) Observao 1.28 Outra estratgia de prova que usa o raciocnio hipottico conhecida como redu-o ao absurdo ou prova indireta. Para provar uma concluso, a concluso negada inserida como hiptese e a estratgia busca derivar uma contradio - aderivao da contradio evidencia que a hiptese negada falsa,oque permite inferir que aconcluso segue das premissas.Como visto anteriormente, uma contradio qualquer wff no padro a/\ (-,a). A wff pode ser um tomo ou, ento, uma expresso composta. A regra da reduo ao absurdo estabelecida como:dada aderi-vao de uma contradio a partir de uma hiptese a, pode-se descartar a hiptese e inferir -,a. Exemplo 1.47 A Tabela1.57 mostra a prova do argumento p~ q, ---,q1- ---,pusando a reduo ao absurdo. Tabela 1.57 Prova de p ~ q,-.q 1- --,p por reduo aoabsurdo. c1 ~ q premissa c2 ---,q premissa c3 phiptese c4 q(C1 + C3 + modus ponens) cs q/\---,q(C4 + C2 +adio) c6 ---,p(C3 - C5 +reduo ao absurdo) Exemplo 1.48 A Tabela1.58 mostra a prova doargumento p~ q, ---,q1- ---,pusando a reduo ao absurdo. Tabela 1.58 Prova de p ~ q,-.q 1- --,pusando reduo ao absurdo. cl ~ q premissa c2 ---,qpremissa c3 phiptese c4 q(C1 + C3 +modus ponens) cs q /\ ---,q(C4 + C2 +adio) c6 ---,p(C3 - C5 +reduo ao absurdo) A cartilha da lgica57 Observao1.29Quando um esquema deraciocniohipottico usado,algunscuidadosdevem ser tomados: 1.cada hiptese introduz, em uma prova, um deslocamento nas frmulasinferidas a partir de ento, at o ponto de a hiptese ser descartada pela aplicao da introduo da condicional ou da reduo ao absurdo; 2.nenhuma ocorrncia de uma frmuladeslocada pode ser usada em qualquer regra aplicada aps otrmino do deslocamento. Isso garante que afrmula derivada da hiptese no seja usada depois que a hiptese for descartada; 3.se duas ou mais hipteses estiverem ativas simultaneamente, ento a ordem na qual elas so descartadas deve ser a ordem inversa na qual elas foramintroduzidas; 4.uma prova no est completa at que todas as hipteses sejam descartadas. 1.8 PROVA AUTOMTICADE TEOREMAS- ALGORITMODEWANG LgicaeProva AutomticadeTeoremassodesignificativa importncia nareadeInteligncia Artificial- aprimeiraporserumalinguagemformalutilizadanaexpressodeconhecimentoe representao de problemas e, asegunda, por ser uma possvel formade obter solues de muitos desses problemas de maneira automtica. A Lgica Proposicional, embora aplicvel a um nmero restrito de problemas, fornece uma ferra-menta simples, com a qual os conceitos bsicos de prova automtica de teoremas podem ser ilustra-dos. Nesta seo, apresentado o mtodo sinttico para a prova automtica de teoremas da Lgica Proposicional, conhecido como Algoritmo de Wang, proposto e descrito em Wang (1960,1964). ArefernciaMonard&Nicoletti(1990)apresentaediscuteemdetalhesduasconhecidasim-plementaes destealgoritmo(ver Coelho&Cotta (1988)),escritas nalinguagem de programao Prolog, abordando tanto a estrutura de dados utilizada quanto a eficincia deexecuo de cada uma delas, procurando evidenciar seus aspectos positivos e negativos. Com base na discusso, proposta e descrita uma terceiraimplementao em Prolog do algoritmo de Wang, que introduz diversas oti-mizaes em relao s duas outras verses descritas na literatura. As trs implementaes so com-paradas com relao eficincia medida em tempo de execuo, usando um conjunto de 50 teoremas e 21no-teoremas. As medidas obtidas evidenciaram a superioridade da implementao proposta na referncia que, em mdia, executa aproximadamente duas vezes mais rpido que a mais eficiente das outras duas implementaes. O algoritmo de Wang espera como entrada uma wff, e,usando um conjunto deoito regras sintti-cas, conclui-se que a wff fomecida ou no um teorema. Dependendo dos conectivos presentes na wff o algoritmo a quebra em subexpresses que, recursivamente, devem ser provadas teoremas tambm. 58EdUFSCar - Apontamentos Seis das oito regras usadas pelo algoritmo so manipulaes simblicas fundamentadas no co-nectivo principal de subfrmulas. As duas regras restantes regulam os critrios de parada do algo-ritmo:uma detecta quando uma expresso um teorema,eaoutra quandoaexpresso no um teorema. A entrada para o algoritmo pode ser a wff fornecida como um todo ou, ento, j dividida entre as subfrmulas que representam as premissas e as que representam as concluses. Antesda discussodoalgoritmosoapresentadasalgumasequivalnciaslgicas na forma de exemplos,quesubsidiamoentendimentodamotivaoparaoestabelecimentodealgumasdas regras utilizadas no Algoritmo de Wang. Exemplo 1.49 A Tabela1.59 mostra a equivalncia entre asfrmulasa: (p/\ -.q) ~ r ef3:p~ (r vq), evidenciando que a frmula aBf3 uma tautologia. Tabela 1.59 Tabela-verdade da tautologia aB13para a: (p /\ -.q)r e 13:p~ (r vq). pqr-,qp /\ -,qarvq f3 a ~ f 3II VVVffVVVV 12 VVfffVVVV 13 VfVVVVVVV 14 VffVVfffV 15 fVVffVVVV 16 fVffffffV 17 ffVVfVVVV 18 fffVfffVV A Tabela 1.60 mostra a equivalncia entre as frmulas a: p~ (r v-.q) ef3:(p /\ q) ~ r,eviden-ciando que a frmula aBf3 uma tautologia. Tabela 1.60 Tabela-verdade da tautologia aB13para a: p~ (r v -,q) e 13:(p /\ q ~ r. pqr-,qrv-,qaPI\ q f3 aB f3 II VVVfVVVVV ~VVffffVfV J, VfVVVVfVV ; .. " ffVVVfVV 's .. f " VfVVfVV I,.fVfffffVV '1 fr y VVVfVV I,fffVVffVV A cartilha da lgica59 Exemplo 1.50 A Tabela1.61mostra a equivalncia entre as frmulas a: (p vq) ~ r eJ3:(p ~ r) /\ (q ~ r),evidenciando que a frmula a ~ J3 uma tautologia. Tabela 1.61Tabela-verdade da tautologia a ~ f3para a: (pvq)-t r ef3 : (p-t r)A (q-t r). pqrp v qap ~ r q ~ rJ3 a ~ J3 II VVVVVVVVV I2 VVfVffffV I3 VfVVVVVVV I4 VffVffVfV I5 fVVVVVVVV I6 fVfVfVffV I7 ffVfVVVVV I8 ffffVVVVV Exemplo 1.51A Tabela1.62 mostra a equivalncia entre asfrmulasa: p~ (q/\r)eJ3:(p~ q) /\ (p~ r),evidenciando que afrmula aJ3 uma tautologia. Tabela 1.62 Tabela-verdade da tautologia a ~ f3para a: p -t (qAr) e f3:(p -t q)/\ (p -t r). pqrq/\ rap ~ q p ~ rJ3 a ~ J II VVVVVVVVV I2 VVfffVffV I3 VfVfffVfV I4 VfffffffV I5 fVVVVVVVV I6 fVffVVVVV I7 ffVfVVVVV I8 ffffVVVVV Exemplo 1.52A Tabela1.63mostra que afrmulaa: (p/\ q) ~ ( qvr) uma tautologia. Tabela 1.63 Tabela-verdade da tautologia a: (pA q) -t (qvr). pqrp /\ qqvra II VVVVVV I2 VVfVVV I3 VfVfVV 14 VffffV 60EdUFSCar -Apontamentos Tabela 1.63 Continuao ... . pqrp/\ qq vra 15 fVVVVV 16 fVffVV 17 ffVfVV 18 ffffVV O Algoritmo de Wang se aplica a uma expresso no esquema (1.5) no qual: 1.os pi1 (1 in)so identificados como premissas e os cis(1 j k), como concluses; 2.osmbolo aimplicaodeWang,quetema semnticadaimplicaolgicaesintaticamente, funciona como um separador entre as premissas e asconcluses durantea manipula