LOG - Lógica Matemática

27/04/12

(Verso para impresso) Lgica Matemtica

Lgica MatemticaContedoAula 01 - Lgica proposicional1.1 Introduo Lgica Proposicional 1.2 A linguagem da Lgica Proposicional 1.2.1 O vocabulrio da Lgica Proposicional 1.2.2 Sintaxe do clculo proposicional 1.2.3 Semntica da Lgica Proposicional

Aula 02 Linguagem natural e mtodo de tabelas verdade2.1 Lgica Proposicional e linguagem natural 2.2 O mtodo de tabelas verdade

Aula 03 Propriedades semnticas, equivalncia e argumentao3.1 Propriedades semnticas da Lgica Proposicional 3.2 Equivalncia e implicao em frmulas da Lgica Proposicional 3.3 Argumentao na Lgica Proposicional

Aula 04 Inferncia e equivalncias notveis4.1 Inferncia 4.2 Equivalncias notveis

Aula 05 Mtodo dedutivo5.1 Mtodo direto 5.2 Mtodo dedutivo indireto

Aula 01 - Lgica proposicionalNesta Aula, voc aprender a desenvolver a sua primeira linguagem formal, a linguagem proposicional. Trata-se de uma linguagem bastante simples, mas que associada a um sistema dedutivo, consistir num poderoso instrumento de anlise lgica.

1.1 Introduo Lgica ProposicionalA lgica proposicional extremamente til para diver sos domnios. Sua compreenso indispensvel no s para o filsofo e o matemtico, mas tambm para outras reas, por exemplo, para os profissionais da Tecnologia da Informao. A Lgica, como a conhecemos, nasceu h mais de 2000 anos entre os filsofos gregos para a elaborao e avaliao de argumentos. Seres humanos raciocinam e argumentam todo o tempo, de maneira informal ou de maneira formal. Num bate papo entre amigos, se voc quisercatolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 1/43

27/04/12


convenc-los de algo preciso argumentar de forma que suas idias sejam inquestionveis. O mesmo se d, por exemplo, na rea jurdica. Um trabalho tremendo feito por juristas para que as leis no gerem interpretaes erradas, ou seja, para que o raciocnio correto no leve a concluses indesejadas para a sociedade. Ento, a Lgica permite que se identifique melhor a validade ou a circunstncia em que uma argumentao procedente; tambm facilita a elaborao de argumentos e raciocnios corretos. Existem, na verdade, vrias lgicas. Pode-se dizer que a Lgica Proposicional a mais simples delas. Ela nos ajuda a raciocinar com idias simples, como: Quando chove, a rua fica molhada. Ruas molhadas ficam escorregadias e, portanto, ficam mais perigosas. Assim, em caso de chuva, preciso aumentar o cuidado ao se dirigir. Lgicas como a Lgica de Predicado de 1 Ordem e a Lgica Temporal, por exemplo, so necessrias para raciocinar sobre idias que relacionam conceitos ou que lidam com eventos que so falsos ou verdadeiros, dependendo do momento em que so considerados. A Lgica Proposicional no aplicvel nesses casos. No entanto, isso no tira sua importncia. Os computadores atuais no existiriam sem a Lgica de Boole, que , essencialmente, uma forma de se interpretar a Lgica Proposicional. A diferena que na lgica booleana manipula-se 0s e 1s no lugar de Falso e Verdadeiro. A Lgica Proposicional manipula sentenas que expressam idias simples, chamadas de enunciados ou proposies. Proposies podem ser verdadeiras ou falsas, mas cabe a algum associar a elas um desses valores. Por exemplo, a frase Computadores so caros corresponde a uma idia simples, portanto a uma proposio. J a frase Computadores so caros, mas so teis composta de duas idias simples: Computadores so caros e Computadores so teis. Assim, uma proposio pode ser composta de proposies mais simples. Consideremos agora as trs proposies a seguir: Uma hora antes de morrer, Joo estava vivo. Se [ verdade que] quando chove, a grama fica molhada, ento [ verdade que] se a grama no est molhada, porque no h chuva. A Terra redonda. Para convencer algum a respeito da primeira proposio, basta que se conhea o significado das palavras. Dizemos que essa proposio uma verdade lingustica. Ou seja, se chega concluso de que isso bvio! Para se convencer sobre a se da proposio, preciso saber o que significam as estruturas gun lingusticas se ... ento ... e no .... preciso tambm saber que as duas idias contidas na frase,"chove" e "grama molhada", so tambm proposies, isto , podem ser verdadeiras ou falsas. Podemos substituir essas idias por outras quaisquer e a frase continuar verdadeira. Peguemos, por exemplo, as seguintes proposies: estudei e fui aprovado. Inseridas nas estruturas lingusticas citadas, teremos: se verdade que quando estudo, sou aprovado, ento se fui reprovado porque no estudei. Esse tipo de verda lingustica chamada de verdade de lgica. A terceira proposio, no entanto, no uma verdade lingustica, pois ela ex pressa um fato incontestvel. Esse enunciado , portanto, uma verdade factual.

1.2 A linguagem da Lgica Proposicionalcatolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 2/43

27/04/12


Como para qualquer linguagem, a Lgica Proposicional, assim como a Matemtica ou as lnguas naturais, como o Portugus, tem um vocabulrio, ou seja, um conjunto de smbolos para representar seus objetos, um conjunto de regras gramaticais, ou sintaxe, que definem e estrutura correta de suas frases, e uma semntica, que associa os smbolos a idias precisas. Por exemplo, o vocabulrio da Matemtica composto de smbolos como +, -, x, /, , , , =, x, y, z, A, B, ... Existem regras gramaticais que definem frases matemticas corretas ou bem formadas. Assim, a frase x + y = 5 bem formada, enquanto a frase x + = y 5 no . Ou seja, a primeira est sintaticamente correta, enquanto a segunda no. Podemos entender a frase x + y = 5 como sendo a soma de um valor x com um y totalizando o valor 5, no importando o que x e y representam. Podem-se imaginar diversas interpretaes para x e y, ou seja, os valores que eles podem assumir para que essa frase seja verdadeira: (0,5), (1,4), (2,3), (3,2), (4,1) ou (5,0). Assim, a semntica do operador +, para os nmeros Naturais (Inteiros maiores ou iguais a zero), tal que 0 + 5 = 1 + 4 = 2 + 3 = 3 + 2 = 4 + 1 = 5 + 0 = 5. Vejamos agora o vocabulrio, a sintaxe e a semntica da Lgica Proposicional.

1.2.1 O vocabulrio da Lgica ProposicionalA Lgica Proposicional utiliza um vocabulrio formado por smbolos que representem proposies. Assim como na matemtica temos operadores para construir expresses, como os de soma (+), subtrao (-), multiplicao (), diviso (/), entre outros, as idias que a Lgica Proposicional articula so aquelas que se servem dos seguintes operadores: ... e ... (conjuno), ... ou ... (disjuno), verdade que ... (afirmao), no verdade que ... (negao), se ... ento ... (condicional) e ... se e somente se ... (bicondicional). Podemos utilizar letras minscu even las, t ualmente indexadas, e cinco operaes, ou conectivos, para expressar as idias que podem ser tratadas pela Lgica Proposicional, como mostrado na tabela abaixo. nome negao conjuno disjuno condicional bicondicional smbolo usual tipo unrio binrio binrio binrio binrio outros smbolos -, ~, not, no &, ., and, e , or, ou leitura no ... ... e ... ... ou ... se .... ento ... ... se e somente se ... Assim,

Existem muitas variaes de smbolos para representar os mesmos conectivos. dependendo do livro ou material utilizado, preciso verificar o vocabulrio utilizado.

Como dissemos, proposies representam idias que podem ser interpretadas como verdadeiras ou falsas. A verdade lgica citada acima pode ser representada da seguinte maneira: se representarmos a frase simples chove por um smbolo qualquer, p, por exemplo, e a frase a grama fica molhada (ou simplesmente a idia grama molhada) por outro smbolo qualquer, como o q, poderamos representar graficamente as frases Se chove, a grama fica molhada e Se a grama no est molhada, porque no h chuva. Elas poderiam ser representadas da seguinte maneira:catolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 3/43

27/04/12


p e q

q

p

E a frase original Se [ verdade que] quando chove, a grama fica molhada, ento [ ver de da que] se a grama no est molhada, porque no h chuva seria representada por: (p q) ( q p)

Como vimos, essa frmula continua uma verdade lgica, quaisquer que se os enunciados jam representados pelas pro posies p e q. Se p = estudar e q = aprovado, obteremos uma mesma frmula, da mesma forma que, na matemtica, (x + y = 1) (x = 1 y) pode ser empregada em qualquer situao, ou seja, qualquer que seja a interpretao dada para x e y.

1.2.2 Sintaxe do clculo proposicionalComo so formadas as frases em portugus? a partir de um conjunto de palavras vlidas para o portugus e de um conjunto de smbolos de pontuao que se forma o vocabulrio da lngua portuguesa. E a partir das regras gramaticais, ou sintaxe, que se produzem frases corretas ou bem formadas. Vejamos, por exemplo, o seguinte subconjunto das regras gramaticais (RG) da lngua portuguesa: (1) (2) (3) (4) uma frase pode ser composta de um sujeito e de um predicado, um sujeito pode ser formado por um artigo e um substantivo, um predicado pode ser formado por um verbo e um objeto direto e um objeto direto pode ser formado por um artigo e um substantivo.

Elas podem ser representadas da seguinte maneira: RG1: ::= RG2: ::= RG3: ::= RG4: ::= . Para verificar se a frase O gato pulou o muro bem formada, basta verificar se ela pode ser gerada a partir das regras acima. Assim, a partir da RG1, temos: Como o um artigo, gato e muro so substantivos e pulou um verbo, temos:

Podemos utilizar as regras R2 e R4:

catolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s

4/43

27/04/12


E aplicando-se a regra R3, teremos:

E pela regra R1:

Como foi possvel utilizar as regras para mostrar que a frase O gato pulou o muro pode ser reconhecida pelas regras, ento ela uma frase bem formada. A mesma coisa se d com a Matemtica: uma frmula, assim como uma frase, uma reunio de palavras construda segundo certas regras. Vamos considerar a seguintes regras de formao para a gerao de uma frmula matemtica simples: (a) Todo valor numrico uma frmula. Toda varivel uma frmula bem formada. (b) Se A e B so frmulas, ento (A + B), (A B), (A / B) e (A * B) so frmulas bem formadas. (c) Uma frmula bem formada se obtm unicamente a partir das regras (a) e (b). Aparecem nas regras dois novos smbolos: A, B, ( e ). Os parn t eses, aberto e fechado, permitem de t erminar, de certa forma, a ordem na qual as regras foram aplicadas. Por exem na plo, frmula ((x + 2) / y),catolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 5/43

27/04/12


a regra indutiva foi aplicada duas vezes: a primeira aplicao deu lugar fru (x + 2) a partir m la das frmulas x e 2, en quanto que a segunda aplicao deu lu frmula final a partir das gar frmulas (x + 2) e y. A razo fundamental do uso de parnteses a estrutura arborescente das expresses aritm as. t i c Assim, ((x + 2) / y) uma frmula bem formada porque x e y so variveis e, portanto, so frmulas. O mesmo pode ser dito sobre o valor 2. Ento (x + 2) uma frmula bem formada porque sabemos que (A + B) uma frmula bem formada se A e B forem substitudas por frmulas bem formadas. Da mesma forma, ((x + 2) / y) tambm uma frmula bem formada porque sabemos que (x + 2) uma frmula bem formada, assim como y uma frmula bem formada. De uma maneira grfica, podemos representar a equao numa forma arborescente:

Agora, vejamos as regras de formao de frmulas (bem formadas) da Lgica Proposicional: (a) Toda proposio uma frmula. (b) Se A e B so frmulas, ento A, (A B), (A B), (A B), (A (c) Uma frmula se obtm unicamente a partir das regras (a) e (b). B) so frmulas.

Os parnteses so utili dos aqui da mesma maneira que na aritmtica. Assim, da mesma forma za que para as equaes matemticas, a frmula lgica (p (q regras de formao, podemos construir a seguinte rvore: r)) bem formada porque, pelas

Utilizam-se parnteses para distinguir frmulas. Por exemplo, (p (q r)) e ((p q) r)

Do mesmo jeito que, na aritmtica, deve-se distinguir a * (b + c) de (a * b) + c. Mas algumas frmulas no precisam de parntesis, pois no h confuso possvel. Por exemplo, a frmula p entendida. q r ou p q r, assim como a equao aritmtica a + b + c, facilmente

1.2.3 Semntica da Lgica ProposicionalComo vimos, a sintaxe define o conjunto de regras para se escrever corretamente frases em uma lngua, seja ela natural (como o portugus) ou formal (como a Matemtica ou a Lgica). Acatolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 6/43

27/04/12


semntica, por sua vez, atribui significado s frases. Quando estudamos matemtica, aprendemos o significado de cada um de seus smbolos. Por exemplo, sabemos o que significa 1 + 1 = 2 porque sabemos o significado de cada um de seus smbolos (1, 2, + e =). Alm disso, uma frmula x + y pode ser interpretada em diversos conjuntos (Naturais, Inteiros, Reais, ...). Chamamos de semntica o significado de cada uma das frmulas. Todos os smbolos da matemtica tm um significado prprio. O smbolo +, por exemplo, faz com que associemos 1 + 1 com o smbolo 2, uma vez que a soma de 1 com 1 resulta no valor 2. Na lgica proposicional, os nicos valores considerados so Verdadeiro (V) ou Falso (F). comum tambm represen os va t ar lores V e o valor F pelos smbolos 1 e 0, respectivamente. In terpretar uma frmula da lgica proposicional consiste em atribuir-lhe um desses dois valores a cada uma de suas variveis. Assim, a semntica associada ao smbolo o da operao de negao. Ela associa o valor V com o valor F e vice-versa, como mostrado na tabela abaixo. X V F X F V

Se interpretarmos X como verdadeira (X = V), a avaliao de sua negao ser falsa ( X = F), e vise-versa (se X = F, ento X = V). Da mesma forma, existe uma semntica associada a cada um dos demais conectivos da lgica proposicional, como mostrado na tabela abaixo. X V V F F Y V F V F X V F F F Y X V V V F Y X V F V V Y X V F F V Y) seja verdadeira, Y

A frmula (X Y) representa a conjuno (... E ...), ou seja, para que (X preciso que tanto X como Y sejam verdadeiras. A frmula (X Y) representa a disjuno (... OU ...), ou seja, para que (X basta que X ou Y seja verdadeira. A frmula (X

Y) seja verdadeira,

Y) representa a condio (SE ... ENTO ...), ou seja, Y consequncia de X.

Assim, (X Y) s ser falsa, se X for verdadeira e Y for falsa. Ou seja, no se pode concluir coisas falsas a partir de uma afirmao verdadeira. A frmula (X Y) representa a bicondio (... SE E SOMENTE SE ...), ou seja, (X Y) s ser verdadeira, se X e Y forem verdadeiros e se ambos forem falsos. Podemos caracterizar uma frmula em funo de seu operador de maior prioridade. Assim, ascatolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 7/43

27/04/12


frmulas (p

q), (p

(q

r)), ((p

q)

r) so frmulas conjuntivas.

Como esses conectivos so binrios, temos 4 interpretaes possveis para cada um deles: (X = V e Y = V), (X = V e Y = F), (X = F e Y = V) e (X = F e Y = F). Podemos dizer, de maneira mais formal, que o valor lgico (Val) de uma frmula qualquer , para uma interpretao I (ValI( )) o valor lgico gerado por uma frmula pela substituio dos valores lgicos de suas proposies pelos valores de I. Se uma proposio simples, p, por exemplo, Val( ), ou Val(p) assumir o valor de p em I. Caso tenhamos uma proposio composta na forma operador , Val( operador ) = Val( ) operador Val( ).

Por exemplo, calculemos o valor lgico da frmula abaixo para a interpretao I = (Val(p) = V, Val(q) = V, Val(r) = F): = ((p q) r)

Inicialmente, substitumos cada proposio da frmula por seus valores lgicos correspondentes da Interpretao. Val((p q) r) = (Val( = (Val(op. op. ) = Val( ) = Val( ) op. Val( ) op. Val( )) Val(Val(p

q)

Val(r)) Val(q)) F) Val(r))

)) Val(Val(Val(p)

= (Val(p) = V, Val(q) = V, Val(r) = F) Val(Val(V = ( Val(V V) = V) = (Val(VF) = F)

V)

Val(V F q)

F)

Ou seja, o valor lgico da frmula a = ((p = V, Val(r) = F) F (falso).

r) para a interpretao I = (Val(p) = V, Val(q)

Voc acaba de ser introduzido no mundo das linguagens formais, um mundo bastante rico, onde lgica proposicional apenas uma entre vrias possibilidades de linguagens, muitas das quais extremamente poderosas como ferramentas analticas. Nesta unidade voc estudar ainda uma outra linguagem. Mas antes de avanar, pratique os exerccios.

Aula 02 - Linguagem natural e mtodo de tabelas verdadeExiste forma mais direta de anlise de frmulas complexas quanto sua interpretao. No contedo que se segue, iremos abordar uma dessas formas.

2.1 Lgica Proposicional e linguagem naturalOs cinco conectivos da lgica proposicional definidos acima equivalem a apenas um subconjunto dos conectivos da linguagem natural. Isso porque a linguagem natural naturalmente mais rica do que a lgica para expressar nossas idias. Por exemplo, as frases Faz tempo bom ou chove e Chove ou faz tempo bom tm o mesmo significado. Dizemos, nesse caso, que o conectivo ou verificacional. No entanto, no se pode dizer o mesmo das frasescatolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 8/43

27/04/12


Teve medo e atirou no intruso e Atirou no intruso e teve medo Elas tm significados diferentes! Isso porque a palavra (o conectivo) "e" pode representar que alguma coisa aconteceu antes de outra (temporalidade) e que uma consequncia de outra (causalidade). Inmeros outros co nectivos da linguagem natural tambm no so verificacionais. Tomemos o conec da lngua natural "porque". Supo t ivo nhamos que chove (proposio p) e que o cho esteja molhado (proposio q). Aceitamos que q porque p, mas no que p porque q. Na lgica, a disjuno no exclusiva, ou seja, uma disjuno x OU y avaliada como verdadeira se pelo me um de seus dois operandos (x e y) verdadeiro. Na linguagem natural, s vezes o nos "ou" exclusivo. o caso, por exemplo, da disjuno na frase "um nmero inteiro par ou mpar". O condicional (SE antecedente ENTO consequente) expressa a idia de dependncia do consequente em relao ao antecedente. claro que, se o antece dente verda deiro, a condio tem o valor do consequente. Pode, no entanto, surpreender que a implicao seja verdadeira se o antecedente for falso. Se o antecedente for falso, no importa o valor do conseqente, pois tudo se justifica. Assim, por exemplo, que se chove para cima ento o sol quadrado verdadeiro. Portanto, a representao de frases da linguagem natural em frmulas da Lgica muitas vezes requer bom senso. Vamos agora traduzir a Linguagem Natural para a Lgica Proposicional. A traduo de um texto escrito em uma lngua natural qualquer para a linguagem simblica da Lgica Proposicional no segue um padro mecnico. Entretanto, h algumas dicas que, na grande maioria das vezes, funcionam bem. Uma dica de traduo: Sempre traduzir mas, porm, embora (e outros elementos adversativos) como e, utilizando o conectivo . Exemplo: Considere a frase Embora Joo tenha estudado, saiu-se mal na prova.. Se traduzirmos Joo estudou como p e saiu-se mal na prova como q, a frase inicial pode ser traduzida por p Outra dica: Deve-se traduzir a menos que por ou. Exemplo:catolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 9/43

q.

27/04/12


Se considerarmos que Joo morrer pode ser representada por p e (Joo) se alimente corretamente por q, a frase Joo morrer, a menos que (Joo) se alimente corretamente pode ser traduzida por p q. Mais algumas dicas: Se voc encontrar a frase p suficiente para q, ou para que p basta que q, traduzaa por p q. Se voc encontrar a frase p necessrio para q, traduza-a por p q. Se encontrar a frase p necessrio e suficiente para q, traduza-a por p Exemplos: Sendo p = Joo estuda e q = Joo passa de ano, A frase Para que Joo passe de ano basta que (Joo) estude. pode ser representada por p q. A frase Para que Joo passe de ano necessrio que (Joo) estude. pode ser representada por p q. A frase Para que Joo passe de ano necessrio e suficiente que (Joo) estude. pode ser representada por p q. q.

No quadro abaixo, mostramos uma amostra da relao entre expresses da linguagem comum e a representao da Lgica Proposicional. Expresso lgica p q Expresso da linguagem comum p ou q p, q ou ambos p e/ou q Ou p ou q ... p e q p e ento q p embora q p mas q p assim como q p e tambm q p apesar de que tambm q p em adio, q No s p, mas, ainda, q p, sem levar em conta que q p e, alm disso, q No apenas p, como tambm q ... p se e somente se q p se e s se q Se p, ento q, e reciprocamente p condio necessria e suficiente para q p equivalente a q ... No p No se d que p No fato que p No verdade que p No se tem p ... Se p, ento q Se p, isso significa que q Tendo-se p, ento q Sempre que p, q q, sempre que p q resultante decatolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 10/43

p

q

p

q

p

27/04/12


p

q

p q, se p p implica q p acarreta q p s se q p somente se q p apenas se q p, desde que q A menos que p, no q No q, a menos que p p condio suficiente para q q condio necessria para p Uma condio necessria para p q Uma condio suficiente para q p ...

Exerccios de fixao1. Seja p = Ela alta e q = Ela bonita. Escrever cada uma das seguintes proposies na forma simblica: a. b. c. d. e. Ela alta e bonita. Ela alta, mas no bonita. falso que: ela baixa ou bonita. Ela no alta, nem bonita. No verdade que: ela alta ou no bonita.

2. Seja p = Ele rico e q = Ele feliz. Escrever cada uma das seguintes proposies na linguagem natural: a. p b. p c. p d. p Gabarito 1. a. b. c. d. e. 2. a. p b. p c. p d. p q [Ele pobre, mas feliz.] q [Ele no nem rico, nem feliz.] q [Ele rico ou infeliz.] (p q) [Ele pobre ou: rico e infeliz.] Ela alta e bonita. [p q] Ela alta, mas no bonita. [p q] falso que: ela baixa ou bonita. [ ( p q)] Ela no alta, nem bonita. [ p q] No verdade que: ela alta ou no bonita. [p q q q (p

q)

q]

2.2 O mtodo de tabelas verdadeExistem formas mais diretas de anlise de frmulas complexas quanto sua interpretao. Agora, iremos abordar uma dessas formas. O mtodo que ser utilizado bastante prtico e condensa o que foi apresentado.catolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 11/43

27/04/12


As tabelas-verdade so instrumentos para a anlise dos possveis valores de verdade que uma frmula pode ter, dados os valores de verdade de seus smbolos proposicionais e/ou constantes lgicas. As tabelas-verdade apenas colocam em forma tabular aquilo que j foi apresentado nas definies vistas anteriormente (Figuras 4 e 5). Sua forma de apresentao, entretanto, garante uma maior transparncia dos procedimentos de anlise de uma frmula complexa qualquer. De fato, as definies anteriores para a interpretao dos conectivos (operadores) ficam dadas em formato de tabelas-verdade. A partir das tabelas das Figuras 4 e 5, fcil obter o valor de verdade de qualquer proposio complexa baseando-se nos valores de verdade de seus constituintes mais bsicos. Note ainda que tais tabelas esgotam completamente as possibilidades dos valores de verdade possveis (dois para a negao, quatro para os demais). De fato, fcil notar que uma proposio que tenha n smbolos proposicionais diferentes, ter 2n linhas. Basicamente existem duas formas de se construir uma tabela-verdade. Na primeira, coloca-se cada proposio separadamente em colunas e em seguida as unidades que compe a frmula. A ltima a frmula completa. O objetivo resolver a frmula por parte. Por exemplo, a frmula (p q) r contm 3 proposies: p, q e r. Logo, sero necessrias 8 linhas (8 = 23) para combinar todas as possibilidades possveis. Cada uma dessas combinaes uma interpretao para a frmula. Primeiro monte a tabela colocando uma proposio em cada coluna, completando com todas as interpretaes para a frmula, como mostrado abaixo. p V V V V F F F F q V V F F V V F F r V F V F V F V F

Observao: A seqncia dos valores no importante. O que importante que todas as combinaes de valores (todas as 2n combinaes) sejam consideradas. Depois, identifique as subfrmulas da frmula principal. Isso pode ser feito tendo em mente a sua representao arborescente. No exemplo, essa representao a seguinte:


12/43

27/04/12


Quanto maior for o nvel da subfrmula, maior sua prioridade de resoluo. As subfrmulas do nvel 3 (p e q) j esto definidas. No nvel 2, a subfrmula r tambm j est definida, bastando calcular a subfrmula (p q). Finalmente, no nvel 1, ser preciso calcular depois (p A sequncia de preenchimento da tabela a seguinte: [1] p V V V V F F F F [2] Nvel 3 p V V V V F F F F q V V F F V V F F r V F V F V F V F Nvel 2 p V F F F F F F F q Nvel 1 (p q) V F V V V V V V r q V V F F V V F F r V F V F V F V F p V V F F F F F F q (p q) r q) r.

O resultado da frmula dado na coluna que contm a frmula completa. Observe que as colunas utilizadas no clculo da coluna em vermelho esto destacadas em preto.

Exerccio de fixaocatolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 13/43

27/04/12


Construa uma tabela verdade para cada uma das frmulas abaixo. a. p q b. p (q r) Gabarito 1) p p q q p q p q

V

V

F

F

F

V

F

F

V

F

F

V

V

F

F

F 2) p p V V V V F F F F

F (q q V V F F V V F F r)

V

V

V

r V F V F V F V F

q V V V F V V V F

r

p

(q V V V F F F F F

r)

A segunda forma de construir uma tabela verdade mostrada a seguir. O importante neste mtodo identificar o conectivo (operador) que qualifica a frmula, pois nele que dado o resultado. No exemplo anterior, a frmula do tipo condicional, pois o conectivo que determina acatolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 14/43

27/04/12


concluso da frmula o condicional

.

O primeiro passo separar cada elemento que compe a frmula em uma coluna. Para n proposies, considerar o nmero de linhas (interpretaes) igual a 2n. (p q) r

Depois, preencher as colunas das proposies com os valores lgicos de modo a obter todas as interpretaes. (p V V V V F F F F q) V V F F V V F F r V F V F V F V F

Ento, operar os valores lgicos conforme o conectivo (operador) da coluna e de acordo com os nveis de cada subfrmula. Assim, no exemplo, preciso primeiro calcular (p (p V V V V F F V V F F F F q) V V F F V V r V F V F V F15/43

q) ...


27/04/12


F F ... para depois calcular (p q) p V V V V F F F F r.

F F

F F

V F

q) V V F F F F F F V V F F V V F F V F V V V V V V

r V F V F V F V F

Agora que voc j conhece os dois mtodos de construo de tabela verdade, resolva os exerccios a seguir.

Exerccios de fixao1. Resolva os itens do exerccio anterior usando o segundo mtodo. Verifique se os resultados so iguais. 2. Responda as seguintes questes. a. Para que valores de p e q a frmula p que ela falsa? b. Informe o valor lgico da frmula p (q b1) I(p) = V, I(q) = F e I(r) = V b2) I(p) = V b3) I(q) = V e I(r) = F b4) I(p) = V, I(q) = V e I(r) = V b5) I(p) = F, I(q) = F e I(r) = F q verdadeira e quais os valores em r) para as interpretaes a seguir:

Gabarito 2. a. [Verdadeira se V(p,q) = {(F,F)}e Falso se V(p,q) = {(V,V), (V,F), (F,V)}] 2.b. b1) b2) b3) b4) b5) V. F quando q = F e r = F; V para o resto. V quando I(p) = V; F quando I(p) = F. V. F.

Note que esses mtodos so bons quando a frmula pequena. Por exemplo, em uma frmulacatolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 16/43

27/04/12


com 5 diferentes proposies, teramos uma tabela com 32 linhas. Imagine trabalhar com tabela-verdade no clculo de uma frmula com 10 proposies. Seriam necessrias 1024 linhas! Uma forma de lidar com tais frmulas o mtodo algbrico. Este mtodo no ser abordado neste material. Os interessados podem consultar a bibliografia do curso para quaisquer esclarecimentos. Siga para a prxima aula!

Aula 03 - Propriedades semnticas, equivalncia e argumentaoNesta aula voc conhecer as propriedades semnticas da lgica proposicional, equivalncia e sua implicao na lgica proposicional e, ainda, argumentao.

3.1 Propriedades semnticas da Lgica ProposicionalExistem algumas propriedades semnticas bsicas da Lgica Proposicional. Frmulas podem ser consistentes, vlidas ou inconsistentes. Frmulas consistentes so aquelas que so verdadeiras para pelo menos uma interpretao. Por isso elas tambm so chamadas de contingentes. A frmula (p anteriormente, um exemplo de frmula consistente (contingente). q) r, mostrada

Uma frmula vlida, ou uma tautologia, se ela for verdadeira para qualquer interpretao. Vejamos, por exemplo, a seguinte frmula: ((p [1] ((p V V F F V F V V q) V F V F V F F F q) [2] p) V V F F V V V V p) q. [3] q V F V F

Como pode ser observado, qualquer que seja a interpretao, a frmula sempre verdadeira. Uma frmula inconsistente, ou uma contradio, se ela for falsa para qualquer interpretao. Analisemos a seguinte frmula: (p [1] ((p V V F F V F V V q V F V F F F F F q) (p [4] (p V V F F F V F F F V F V q). [3] [2] q) V F V F


17/43

27/04/12


Observem que O passo [2] s a negao de q. O passo [3] a conjuno de p e q. O passo [4] a conjuno entre os resultados dos passos [1] e [3]. Note ainda que os passos [1] e [2], por serem independentes, poderiam ser invertidos. Podemos concluir que, para qualquer interpretao, a frmula sempre falsa.

Exerccios de fixaoDadas as frmulas a seguir, identifique, por meio de tabela verdade, a semntica de cada uma. a. ((p b. (p c. (p Gabarito a. Tautologia b. Contingncia c. Contradio q) q) (p q)) q) ( p p q q)

3.2 Equivalncia e implicao em frmulas da Lgica ProposicionalDiz-se que duas frmulas so equivalentes se elas gerarem os mesmos resultados para as mesmas interpretaes. A representao significa que as frmulas e so equivalentes.

O smbolo no um operador. Logo, nenhum valor lgico pode ser associado a ele. Ele simplesmente uma notao. Assim, por exemplo, as frmulas (p q) e ( p resultados, como podemos ver nas tabelas abaixo. [1] p V V F F V F V V q V F V F e F F V V [1] p V V F F V F V V q), uma vez que elas geram os mesmos

[2] q V F V F

Outra forma para se verificar se duas frmulas uma tautologia. [1] (p q) [4]

so equivalentes verificarmos se frmula

[2] ( p

[3] q)18/43


27/04/12


V V F F

V F V V

V F V F

V V V V

F F V V

V V F F

V F V V

V F V F

Como pode ser observado, houve uma tautologia. Assim, podemos concluir que as duas frmulas so equivalentes.

Exerccios de fixaoDadas as formulas as afirmaes a seguir, verifique se so verdadeiras. a. (p q) equivale a ( q p) b. ( q p) no equivale a (q p) c. (p q) ( q p) d. No verdade que ela feia e deselegante equivale a Ela bonita ou elegante Gabarito a. b. c. d. Verdadeiro Falso Falso Verdadeiro

A implicao entre duas frmulas ocorre quando existe uma relao de conseqncia ente elas. O smbolo utilizado para representar essa relao um smbolo e, por isso, no possui valor lgico. (implica em). Lembre-se que se trata de

A relao de implicao entre duas frmulas e representada por . Para sabermos se duas frmulas tm uma relao de implicao entre elas, devemos construir uma tabela verdade, substituindo o smbolo pelo operador condicional o resultado da tabela for uma tautologia. Assim, se quisermos saber se ((p verificarmos se ((p q) [1] ((p V V F F V F V V q) V F V F F F F V q) F V F V q) q) q) . As duas frmulas sero implicadas se

p (((p

q)

q) implica em

p), basta

p uma tautologia. [3] [2] q) V F V F V V V V F F V V p. [5] [4] P V V F F

Como podemos observar, a frmula ((p

q) implica na frmula p ((p q) q).

Agora vamos verificar o contrrio, ou seja, se


19/43

27/04/12


[1] p F F V V V V F F

[5] ((p V V F V V V F F

[2] q) V F V V V F V F

[4]

[3] q)

F F F V

F V F V

V F V F

Observe que a relao de implicao entre as frmulas e a no verdadeira, pois no obtivemos uma tautologia. Isso vem demonstrar que a relao de implicao no comutativa, ou seja, se implica em , no verdade que implica em .

Exerccio de fixaoDadas as formulas as afirmaes a seguir, verifique se so verdadeiras. a. b. c. d. (p q) p implica em q ( q p p) no implica em q (p q) q p Se A igual a B ento B igual a C e A igual a B, implica em B igual a C.

Gabarito a. b. c. d. Verdadeiro Verdadeiro Falsa Verdadeiro

3.3 Argumentao na Lgica ProposicionalA argumentao um processo de inferncia, isto , de raciocnio. Quando nos colocamos na situao de defendermos algum ponto de vista, idia ou interpretao, o que realmente somos chamados a fazer apresentar nossos motivos para defender estas concluses. Retomamos nossos pontos de partida (as informaes das quais derivamos a idia que queremos defender) e mostramos como deles podemos derivar o que queremos defender. Um argumento , assim, formado por premissas (os pontos de partida) e pela concluso (o ponto de vista que queremos defender). Tiramos, ento, uma inferncia das premissas e chegamos a uma concluso. Mas o simples concatenar de premissas e concluso no faz um argumento correto: faz-se necessrio que a concluso seja uma implicao lgica das premissas. Podemos tomar o exemplo anterior: ((p q) q) p. Nesse argumento, (p q) e q so as premissas e p a concluso. A tabela verdade mostrou que em todas as situaes possveis podemos concluir p, a partir das premissas (p q) e q.

importante notar que as frmulas atmicas de um argumento (no caso acima, p e q) so verdadeiras ou falsas, mas um argumento nunca verdadeiro ou falso. Os argumentos so vlidos (ou corretos) ou invlidos (ou incorretos). No caso do exemplo anterior, a tabela verdade demonstra que a inferncia da concluso a partir das premissas sempre necessria, o que faz do argumento um argumento vlido.


20/43

27/04/12


Como exemplo, consideremos o argumento a seguir: 1. 2. 3. 4. Se estudar, ento serei aprovado. Ou estudo ou vou pra balada. Fui reprovado. Logo, fui pra balada.

O argumento acima conclui que fui para a balada baseado nas premissas 1, 2 e 3. Se o argumento estiver correto, a conjuno das premissas 1, 2 e 3 implicar na concluso. Assim, vamos representar na forma simblica o argumento em questo. Seja p = Estudar, q = Ser aprovado e r = Ir pra balada. Ento, Ser reprovado. p = No estudar e q =

A premissa 1 afirma que Estudar a condio para Ser aprovado. Assim, ela pode ser representada por (p q).

A premissa 2 representa um ou exclusivo, ou seja, e afirmao verdadeira quando s uma delas for verdadeira, ou seja: ( q r) (q r). q. r)) r) q.

Como visto anteriormente, a premissa 3 pode ser representada simplesmente por Assim, frmula a seguir representa o argumento: ((p Construindo a tabela-verdade teremos: [1] ((p V V V V F F F F V V F F V V V V q) V V F F V V F F F V F F F V V F [7] [2] (( F F V V F F V V q V V F F V V F F F F V F F F V F [3] r) V F V F V F V F F V V F F V V F [6] (q V V F F V V F F F V F F F V F F F V F V F V F V [5] [4] r)) V F V F V F V F F F F F F F V F [8] r) V F V F V F V F V V V V V V V V q) (( q r) (q

[10]

[9] q F F F F V V V V V V F F V V F F

Conforme demonstrado, realmente fui pra balada.

Exerccio de fixaoDados os argumentos a seguir, utilize o mtodo da tabela verdade para provar sua validade. a. p q, q p b. p q, q p c. p q, p qcatolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 21/43

27/04/12


d. p q, r q, r p e. Se chove, Marcos fica resfriado. Marcos no ficou resfriado. Logo, no choveu. Obs: - Para resolver os exerccios voc dever substituir as virgulas pelo conectivo de conjuno. - O smbolo tem como leitura LOGO, indica o termo conclusivo do argumento. .

Assim, deve ser substitudo pelo conectivo condicional Gabarito a. b. c. d. e. Vlido Invlido Invlido Vlido Vlido

Aula 04 - Inferncia e equivalncias notveisNesta aula voc ir estudar sobre os processos que permitem obter conhecimento a partir de fatos observveis.

4.1 InfernciaNs, seres humanos, estamos todos os dias absorvendo dados e informaes e tomando decises com base nelas. O computador um equipamento que no pensa por si s; ele necessita que algum faa o processo de obteno dos conhecimentos e formule as regras que lhe permitem auxiliar na difcil tarefa de tomar decises. O processo mental que leva um indivduo a obter novas informaes, conhecimentos (proposies) a partir de dados conhecidos previamente (premissas) chamado de inferncia. A inferncia pode ser dividida em dois tipos: imediatas e mediatas. As inferncias do tipo imediatas so aquelas que chegam a uma concluso a partir de uma nica proposio. So obtidas por meio da oposio ou converso. Por exemplo, por oposio, se p representa O computador est processando, ento p significa O computador est parado (ou travado ...). Por converso, dizer que q = O meu computador tem uma memria de 1024 milhes de bytes o mesmo que dizer q1 = O computador tem uma memria 1 Gbyte. As inferncias do tipo mediatas necessitam de mais de uma proposio para chegar a uma concluso. Por exemplo, o argumento Este animal um gato ou um cachorro. No um gato. _________________________________ Logo, um cachorro. representado pela frmula ((p q) p) q, necessita lidar com duas premissas para se22/43


27/04/12


chegar a uma concluso. So trs os processos mentais (formas de inferncia) para se chegar a uma concluso: analogia, induo e deduo. Esses processos tambm classificam o tipo de argumento. O argumento (definido na aula anterior) pode ser, ento, do tipo analgico, indutivo ou dedutivo. A analogia o processo que permite chegarmos a uma concluso, baseados na equivalncia entre duas outras relaes. Baseia-se na comparao entre objetos de tipos diferentes, mas que guardam uma semelhana. Por exemplo: Os eltrons esto para o tomo, como os planetas est para o sistema solar. Se voc observar, eltrons e planetas so diferentes; porm foi possvel concluir a relao do eltron com o tomo pelo fato de j sabermos qual a relao entre os planetas com o sistema solar. No processo indutivo, a concluso proposta como decorrncia provvel das premissas. O processo dedutivo chega concluso por uma decorrncia logicamente necessria das premissas. O quadro a seguir exemplifica a induo e a deduo de forma clara. Processo indutivo Todos os cavalos at hoje observados tinham corao. Portanto, todos os cavalos tm corao. Processo dedutivo Todo mamfero tem corao. Todos os cavalos so mamferos. Portanto, todos os cavalos tm corao.

Dado que o processo indutivo no tem aplicao direta no estgio da computao que estamos estudando, vamos deix-la para a rea de Inteligncia Artificial e nos concentrar no processo dedutivo. Os argumentos representam um conhecimento especfico e que necessita ser validado. A sua estrutura varia de acordo com o conhecimento que est sendo expresso, por isso, no existe uma forma nica de inferir uma concluso. Baseado, nessa constatao, os matemticos desenvolveram ao longo do tempo relaes entre as proposies que permitiram avaliar os argumentos para testar sua validade. Criou-se, assim, um conjunto de regras de inferncia e as equivalncias. As regras de inferncia so argumentos vlidos simples. Cada regra reconhecida por um nome. Agora vamos conhecer uma srie delas. Para provar a validade do argumento, utilizaremos a tabela verdade. Adio (AD): Se =p e = q, temos: p V V (p V V q) V23/43


27/04/12


V F F

V V V

V F F

V V F

F V F

A conjuno, tambm chamada de incluso da conjuno ou unio, a inferncia que permite juntar duas proposies quaisquer tidas como verdadeiras. Ou seja, se duas proposies so verdadeiras, sua conjuno tambm ser verdadeira. Simplificao (S): Se =p e = q, temos: [1] (p V V F F V F F F q) V F V F V V V V [2] p V V F F /

A simplificao, ou eliminao da conjuno, a inferncia que permite separar as proposies de uma conjuno. Conjuno (CON): Se =p e = q, temos: (p V V F F V F F F q) V F V F e

A conjuno, tambm chamada de incluso da conjuno ou unio, a inferncia que permite juntar duas proposies quaisquer tidas como verdadeiras. Ou seja, se duas proposies so verdadeiras, sua conjuno tambm ser verdadeira. Modus Ponens (MP): (p q) e p q

Modus Ponens, que em latim significa modo que afirma, a inferncia que, a partir de duas premissas, sendo a primeira a condio "se A ento B", e a segunda afirma a veracidade de A, conclui que B deve tambm ser verdadeiara. Se =p e = q, temos: [1] [2] [3]24/43


27/04/12


((p V V F F V F V V

q) V F V F V F F F

p) V V F F V V V V

q V F V F

Consideremos o seguinte argumento: Se correr o bicho pega. Correu ____________________________ O bicho pegou. Se considerarmos que p = Se correr o bicho pega e que q = Correu, ento, pela regra, e tambm pelo nosso senso comum, podemos inferir que O bicho pegou.. Modus Tolens (MT): (p q) e q p

Modus Tonens, que em latim significa modo que nega, a inferncia que, a partir de duas premissas, sendo a primeira a condio "se A ento B", e a segunda a negao da veracidade da conluso B, conclui que A deve tambm ser falsa. Se =p e = q, temos: [1] ((p V V F F V F V V q) V F V F V F F F F F V V [3] [2] q) V V F F V V V V F F V V [5] [4] p V V F F

Consideremos o seguinte argumento: Se chove, ento o cho fica molhado. O cho est seco. ___________________________________________ Logo, no choveu. Se p = Chove e q = Cho fica molhado. Ento, a idia de que se chove o cho fica molhado seria representada pela frmula (p q). Mas, se o cho est seco (ou seja, inferir que no choveu (ou seja, p). Silogismo disjuntivo (SD): (p Se =p e = q, temos: q) e p q / (p q) e q p q), podemos


25/43

27/04/12


[1] ((p V V F F V V V F q) V F V F

[3]

[2] p)

[4] q V V V V V F V F

F F V F

F F V V

V V F F

Esta regra afirma que, se uma das proposies de uma disjuno falsa, necessariamente a outra deve ser verdadeira. Por exemplo: Vou pra balada ou vou estudar. No vou pra balada. ____________________________________ Logo, vou estudar. Silogismo hipottico (SH): (p Se =p e = q, temos: [1] ((p V V V V F F F F V V F F V V V V q) V V F F V V F F V F F F V F V V [3] (q V V F F V V F F V F V V V F V V [2] r)) V F V F V F V F V V V V V V V V [5] (p V V V V F F F F V F V F V V V V [4] r) V F V F V F V F q) e (q r) (p r)

Vejamos o seguinte exemplo: Quando chove, o cho fica molhado. Se o cho fica molhado ento h perigo de escorregar. ________________________________________________________ Logo, quando chove, possvel escorregar. Dilema construtivo (DC): (p Se = p, [1] ((p q) = q, = r e [3] (r q), (r s) e (p r) (q s)

= s, temos: [2] s) [5] (p [4] r)) [7] (q [6] s)26/43


27/04/12


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

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

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

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

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

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

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

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

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

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

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

V V V V V V V V V V V V V V V V

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

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

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

Vejamos o exemplo: Se ficar, o bicho pega. Se correr, o bicho come. ____________________________ Correr ou ficar. Logo, o bicho pega ou come. Dilema destrutivo (DD): (p Se = p, [1] ((p V V V V V V V V V V F F q) V V V V F F V F V V F F = q, = r e [3] (r V V F F V V V F V V V F q), (r s) e ( q s) => ( p r)

= s, temos: [7] s) V F V F V F F F F V F F [4] ( F F F F V V q V V V V F F F V F V V V F V F V F V [6] [5] s)) V F V F V F V V V V V V [11] [8] ( F F F F F F p V V V V V V F F V V F F F F V V F F [10] [9] r) V V F F V V27/43

[2]


27/04/12


V V F F F F F F F F

F F V V V V V V V V

F F V V V V F F F F

F F V F V V V F V V

F F V V F F V V F F

V V V F V V V F V V

V F V F V F V F V F

F F F F F V F F F F

V V F F F F V V V V

F F V V V V F F F F

V V F V F V V V V V

F V F V F V F V F V

V F V F V F V F V F

V V V V V V V V V V

F F V V V V V V V V

V V F F F F F F F F

V V V V V V V V V V

V V F F V V F F V V

F F V V F F V V F F

Um exemplo: Se Lula concorre para a presidncia, ele ser eleito. Se Fernando Henrique concorre para a presidncia, ele ser eleito. _____________________________________________________________________ Lula no ser eleito e Fernando Henrique no ser eleito. Logo, nem Lula nem Fernando Henrique concorrem presidncia. Absoro (ABS): (p Se =p e = q, temos: [1] ((p V V F F Um exemplo: Se trabalho, ganho dinheiro. ____________________________________________________ Logo, se trabalho, ento trabalho e ganho dinheiro. V F V V q) V F V F V V V V [4] (p V V F F V F V V [3] (p V V F F V F F F [2] q) V F V F q) (p (p q))

4.2 Equivalncias notveisVejamos agora a classe de equivalncias chamadas notveis. A importncia dessas equivalncias reside na possibilidade de substituio de uma frmula por outra, possibilitando auxiliar a prova de argumentos e anlise de sua estrutura lgica. Isto porque uma equivalncia tem a forma bicondicional (A B). Como a equivalncia uma tautologia, ento, toda vez que temos um subfrmula A, podemos substitui-la pela subfrmula B, e vice-versa.catolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 28/43

27/04/12


Vejamos algumas das mais conhecidas equivalncias notveis: Dupla negao (DN): Se = p, temos: [2] [1] p V F F V V F p p

Ao negarmos uma sentena negada estamos, na verdade, fazendo uma afirmao. Veja este exemplo de inferncia imediata: No verdade que o Linux no seguro. ____________________________________________ Logo, o Linux seguro. De Morgan (DM): Se =p e = q, temos: [2] (p F V V V Exemplo: No verdade que ela feia e deselegante. ________________________________________________ Logo, ela bonita e elegante. As equivalncias de De Morgan so das mais interessantes e teis em lgica. Observe que a negao da frmula disjuntiva equivale frmula conjuntiva com as proposies negadas, ou seja, ocorre uma troca do conectivo para . O contrrio tambm ocorre, isto , a negao de uma conjuno equivalente disjuno da negao de cada uma das proposies. Comutao (COM): (p q) (q p) / (p q) (q p) / (p q) (q p) V V F F V F F F [1] q) V F V F ( F F V V [2] p V V F F F V V V F V F V [1] q) V F V F (p q) p q/ (p q) p q

Assim como as operaes de soma e multiplicao da Matemtica, onde (x + y) = (y + x) e (x * y) = (y * x), as operaes lgicas Associao (A): p q r , e (p q) so comutativas. r p (q r) / p q r (p q) r p29/43


27/04/12


(q

r) / p

q

r

(p

q)

r

p

(q

r)

Assim como as operaes de soma e multiplicao da Matemtica, onde x + y + z = (x + y) + z = x + (y + z) e x * y * z = (x * y) * z = x * (y * z), as operaes lgicas associativas. Implicao Material (IM): (p q) ( p q) , e so

tambm chamada de Equivalncia do condicional. A frmula condicional equivalente disjuno entre a negao da proposio antecedente e a proposio conseqente. Se =p e = q, temos: [1] (p V V F F V F V V q) V F V F [1] ( F F V V q p V V F F (p V F V V q) [2] q) V F V F (q p)

Primeira equivalncia do bicondicional (B1): p Se =p e = q, temos: [1] (p V V F F V F F V q) V F V F (p V V F F V F V V [1]

[3] q) V F V F q V F F V (p q) (q V F V F

[2] p) V V F V ( p q) V V F F

Segunda equivalncia do bicondicional (B2): p Se =p e [1] (p V V F F V F F V q) V F V F (p V V F F V F F F = q, temos: [1] q) V F V F V F F V

[5]

[2] ( F V F V q V F V F

[4]

[3] p)

F F F V

F F V V

V V F F


30/43

27/04/12


Transposio ou Contraposio (TRANS): (p Se =p e = q, temos: [1] (p V V F F V F V V q) V F V F (q r) (p [2] ( F V F V q) (p

q)

( q

p)

[4] q V F V F V F V V r) / p

[3] p) F F V V (q r) V V F F (p q) (p r)

Distribuio (DIS): p Se = p,

= q e c = r, temos: [2] [1] (q V V V F F F F F [2] V V F F V V F F V V V F V V V F [1] (q V V V V V F F F V V F F V V F F V F F F V F F F r) V F V F V F V F (p V V V V F F F F V V V V V V F F r) V F V F V F V F (p V V V V F F F F V V F F F F F F [5] q) V V F F V V F F V V V V V F F F [5] q) V V F F V V F F V V V F F F F F [4] (p V V V V F F F F V V V V V F V F [4] (p V V V V F F F F V F V F F F F F [1] r) V F V F V F V F [1] r) V F V F V F V F

(p V V V V F F F F

(p V V V V F F F F


31/43

27/04/12


Identidade (ID): p Se = p, temos:

V

p/p

F

p

[1] (p V F Eliminao (EL): p Se = p, temos: [1] (p V F Opostos (OP): p Se = p, temos: [1] (p V F F F F V p) V F (p V F F F F F/p F) F F V V (p V F F V F F/p V) V V V V (p V F

[5] F) V F F F

[5] V) V V V V

[5] p) V V F V V F

Vimos nesta aula o conceito de Inferncia, e as suas regras. Na prxima aula voc conhecer os mtodos dedutivo direto e indireto. Agora faa o exerccio referente a essa aula. Qualquer dvida compartilhe com os colegas

Exerccio de fixaoO exerccio a seguir visa trein-los no reconhecimento das inferncias. a. b. c. d. e. f. g. h. i. p q, (p q) r p (q r), p p q, q r, p r p (q r), p, q r (q r) p, p, (q r) p q, r s, (p q) (r s) (p r) ( p r), ( p r), p q p q r, p p (q r) (x + y = z) (y + x = z), (x + y = z), (y + x = z)32/43


27/04/12


Gabarito a. Adio (AD). Observe que a proposio r foi introduzida na concluso. b. Simplificao (S). Trata-se de uma frmula conjuntiva e. a concluso um dos dois termos da frmula. c. Silogismo Hipottico (SH). d. Modus Ponens (MP). A proposio p vem confirmar a regra anterior que diz que se p ocorrer a concluso (q r). e. Modus Tolens (MT). A proposio p nega a concluso da regra anterior, assim, o termo anterior da primeira regra fica negado. f. Conjuno (CON). Houve simplesmente a introduo da conjuno entre as proposies. g. Silogismo Disjuntivo (SD). O termo ( p r) nega (anula) o segundo termo da primeira premissa. h. Absoro (ABS). Observe que o termo antecedente do condicional na primeira premissa, passa a fazer parte do termo posterior na concluso do argumento. i. Modus Ponens (MP). Para entender melhor, substitua cada termo por uma letra, sendo os termos iguais pela mesma letra.

Aula 05 - Mtodo dedutivoEsta aula uma aplicao dos conhecimentos adquiridos at o momento. Veremos aqui o Mtodo Dedutivo aplicado em argumentos no condicionais e condicionais. At o momento, temos utilizado a tabela verdade para validar um argumento. Existem outros mtodos que tambm permitem a validao de argumentos, como inferncia, tableaux e deduo natural. A tabela verdade tem srias limitaes. Uma delas, e talvez a mais importante, o fato de no permitir desenvolver novos conhecimentos a partir dos existentes. O outro problema que ela vai ficando mais difcil de ser operacionalizada medida que o nmero de proposies vai aumentando. O mtodo dedutivo permite voc verificar a validade do argumento utilizando-se as regras de inferncias e as equivalncias de forma rpida. So dois os mtodos dedutivos, o mtodo dedutivo Direto e o Indireto.

5.1 Mtodo diretoNo Mtodo Direto desenvolvemos a demonstrao a partir das premissas e geramos novas concluses at que o conhecimento gerado seja igual concluso que queremos chegar. Seja P a concluso do argumento e P1, P2, P3,..., Pn as premissa do argumento. Se Pn for igual a P, ento pode-se dizer que o argumento foi provado. Se durante o desenvolvimento encontramos uma contradio, significa dizer que o argumento falho. O mtodo para desenvolver a demonstrao simples. So trs colunas. A primeira coluna contm a ordem das premissas (1, 2, 3, ...). A segunda coluna contm as premissas. A terceira coluna contm a inferncia utilizada justifica a concluso. Vamos provar p, dadas as premissas abaixo. Pi P1 Proposies q r Justificativas Premissa33/43


27/04/12


P2 P3

p q

r

Premissa Premissa

As linhas P1, P2 e P3 so as premissas deste argumento. Observe que a linha P3 a ltima linha, isto , n = 3. Nela, se encontra a premissa q, e como a concluso almejada p, Pn no coincide com a concluso. Devemos ento manipular as premissas (P1, P2 e P3) por meio da utilizao das regras e equivalncias para tentarmos chegar concluso desejada. Vejamos ento: Pi P1 P2 P3 P4 P5 p q r p C.Q.D. A linha P4 o resultado da aplicao da regra do Silogismo Disjuntivo (SD) entre as premissas das linhas P1 e P3. Proposies q r r Justificativas Premissa Premissa Premissa SD 1,3 MT 2,4

Recordemos SD: (

)e = q e = r, enquanto na linha P3

Em nosso exemplo, quando olhamos a linha P1 temos temos = q.

Uma dvida que pode surgir aqui a seguinte: mas SD uma disjuno ( ), enquanto a premissa em P1 uma conjuno q r, onde a primeira proposio ( q) uma negao. O contrrio ocorre com a premissa P3 onde temos q, enquanto a segunda premissa de SD uma negao ( )! Como posso entender a linha P1 como uma aplicao do SD?

Lembre-se de que e so smbolos de frmulas lgicas e indicam qualquer fbf (frmula bem formada). Assim, na premissa da linha P1 ( q r), q uma fbf e tem para com r, a mesma relao de . O Silogismo Disjuntivo afirma que dada uma disjuno (OU) e a negao de uma das duas proposies que a formam, podemos com certeza deduzir (derivar) a outra proposio. Como no seguinte exemplo: O ru culpado ( ) ou ( ) o ru inocente ( ). As provas mostram que o ru no culpado ( ). ____________________________________________ Logo, o ru inocente ( ).


34/43

27/04/12


Assim, com a ajuda de parnteses, no caso da linha P1, a forma ( ) premissa ( q) (r), onde repetimos que = = qe = r.

( ) a mesma da

Da mesma forma, se em P1 negao de q q=q(

q, ento, em P3 a negao de = q). , isto ,

a negao de

q, e a

O resultado da aplicao de SD entre as linhas P1 e P3 que colocamos na linha P4.

= r, que justamente o

Colocamos tambm na 3 coluna a identificao da regra (SD) e as linhas em foi aplicada (1 e 3). Mas ainda no chegamos ao resultado pretendido ( p). Aplicamos ento, a regra do Modus Tollens (MT) entre as linhas P2 e P4. Recordemos MT: e =p e = r, enquanto na linha P4 temos = r.

Quando examinamos a linha P2, notamos que P2 p

Temos aqui a mesma situao da passagem anterior. Em MT, temos

e a premissa na linha

r, com a proposio consequente negativa. Como aplicar o Modus Tollens?

O raciocnio o mesmo. MT afirma que se tivermos uma proposio condicional estabelecida ( ) e a negao de seu consequente, podemos negar o antecedente. Veja o exemplo visto anteriormente: Se correr ( ), ento ( ) o bicho pega ( ).

O bicho no pegou ( ). _____________________________________ Ento, no correu ( ). Novamente com a ajuda dos parnteses temos o seguinte: na linha P2 a premissa (p) e tem a mesma forma de ( ) = ( ); ao passo que, se = r = r na premissa da linha P4. . Se = p, ento temos na linha P5 ( r)

r na premissa da linha P2, ento

O resultado da aplicao de MT entre as linhas P2 e P4 a negao de , isto p.

Esta a concluso que espervamos ser provada. Logo, o argumento vlido, pois a partir das premissas dadas chegamos concluso desejada. Agora vamos provar t dadas as premissas: Pi P1 P2 P3 (s Proposies P P r) s q t Justificativas premissa premissa premissa35/43


27/04/12


P4 P5 P6 P7 P8 P9 P10

Q p s q r s t

r

premissa S2 MP 1,5 S2 MP 7,4

r

CON 6,8 MP 9,3

C.Q.D. Observe que foi necessrio utilizar mais inferncias que no exemplo anterior. Se fssemos provar este argumento utilizando a tabela verdade, seriam necessrias 32 linhas. A linha P5 resultado da aplicao da regra da Simplificao (S) na premissa da linha P2, assim como tambm a linha P7. Lembrando S: ou q( ), podemos tirar desta premissa a

Como na linha P2 temos a premissa de conjuno p afirmao de = p em P5, e de

= q em P7, a partir do uso de S.

A linha P6 resultado da aplicao da regra do Modus Ponens (MP) nas linhas P1 e P5. Relembremos MP: e s com a mesma forma encontrada em MP: .

Na linha P1 temos a premissa condicional p J na linha P5 temos p ( ento, o resultado na linha P6, que s ( ).

), que a afirmao do antecedente do condicional em P1. Temos

Como apresentado, na linha P7 temos tambm o resultado da aplicao da regra da Simplificao (S) em P2, isto , q. Na linha P8 temos outra aplicao de Modus Ponens (MP) nas linhas P4 (q resulta r. Na linha P9 (s (s) e P8 (r). Lembremos a Conjuno (CON): e r) e P7 (q), de onde

r) temos o resultado da aplicao da regra de Conjuno (CON) nas linhas P6

Ainda no chegamos concluso pretendida, ento nos possvel aplicar mais uma vez o Modus Ponens (MP), agora nas linhas P3 [(s chegamos concluso.catolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 36/43

r)

t] e P9 (s

r). Com mais esta aplicao

27/04/12


Neste caso, na linha P3(s r) = e t = , da a equivalncia com . E na linha P9, s r = a afirmao do antecedente da proposio condicional na linha P3, o que permite a afirmao do conseqente como determina MP em P10: t= , que a concluso almejada.

Exerccio de fixaoProve, usando as regras de inferncias, os argumentos a seguir. a. p b. p Gabarito a. Provar p s: 1. p q - Premissa 2. q r - Premissa 3. s r - Premissa 4. q - S 1 5. r - SD 4,2 6. s - MT 3,5 7. p S 1 8. p s CON 7,6 C.Q.D b. Provar r (p q): 1. p q - Premissa 2. q r - Premissa 3. p s - Premissa 4. s - Premissa 5. p - MT 2,4 6. q - SD 1,5 7. r - MP 2,6 8. r (p q) - CON 7,1 C.Q.D. q, q r, s r, p q, q r, p s, s, r s (p

q)

Argumentos de concluses condicionaisOs argumentos que demonstramos at agora so do tipo no condicional. Um argumento do tipo no condicional aquele cuja premissa a ser provada no condicional. Um argumento dito condicional se a concluso a ser provada do tipo condicional, p s. A concluso do tipo condicional, a ser provada, diferente da no condicional pelo fato do termo conseqente ser dependente do termo antecedente. Supondo a proposio condicional: Se ligar a impressora, ento ela imprime. (p r).


37/43

27/04/12


Observe que a comprovao do termo conseqente r est condicionada ao termo antecedente p. A falta do termo antecedente pode invalidar o argumento a ser provado, pois no poderemos afirmar que a impressora vai imprimir se no for garantido que ela esteja ligada. Por esse motivo, a validao de argumentos condicionais trabalha com o que chamamos raciocnio hipottico. Se a concluso a que queremos chegar, ou que temos de provar, uma proposio condicional (p q), isto quer dizer que q ocorrer se p ocorrer.

Imagine o seguinte exemplo em que seu amigo machucou o tornozelo, mas deseja participar de uma corrida prxima, e voc lhe diz: se voc continuar correndo, ento voc no conseguir participar da corrida (p q). Ele te pede uma prova deste condicional e voc lhe diz algo como:

Olha, suponhamos que voc continue correndo. O seu tornozelo est muito inchado. Se ele est muito inchado e voc continuar correndo, ele no vai sarar em uma semana. Se ele no sarar em uma semana, ento voc no estar apto para disputar a corrida. Deste modo, voc no estar apto para disputar a corrida. Este um exemplo de um raciocnio hipottico onde voc solicita que se faa uma suposio (justamente o antecedente da concluso desejada p q), uma hiptese, para demonstrar que dela deriva a concluso condicional que voc deseja atingir. Na formalizao e prova de um argumento podemos utilizar o mesmo expediente, supondo uma hiptese que o antecedente (p) da concluso condicional (p q) a que queremos chegar, e demonstrando que a partir dela e da utilizao das regras e equivalncias, chegamos ao conseqente da concluso (q). O termo antecedente faz parte da demonstrao como premissa provisria (PP) ou hiptese (H). Ela entra logo aps a linha da ltima premissa do argumento. Da em diante, a demonstrao normal, at encontrarmos o termo consequente. O exemplo a seguir esclarece a alterao no processo de validao. Vamos provar (c dadas as premissas: Pi P1 P2 P3 P4 P5 P6 P7 c d d d Proposies b (d c b b c b) Justificativas premissa premissa PP ou H MT 3,1 DM 2 SD 4,5 Prova do Condicional (PC) de P3 a P6 d)

C.Q.D. Na demonstrao acima, como a concluso a que pretendemos chegar uma proposio condicional (c d), logo aps as linhas P1 e P2 onde esto as premissas do argumento,38/43


27/04/12


acrescentamos a linha P3 que tem o antecedente da concluso condicional (c); isto , em P3 temos a premissa provisria (PP) ou hiptese (H). Procedemos ento aplicao das regras. A aplicao do Modus Tollens nas premissas das linhas P1 (b d). Logo depois, aplicamos uma equivalncia: a de De Morgan (DM). Lembremos DM: ( ) ( ) ou ) ( ) b)), como tambm a 1 parte da = d e = b. Como vimos )) expressa uma relao entre b)), assim podemos ter c, onde =b e = c) e P3 (c, onde = c) resulta na linha P4 ( d, onde =

A premissa na linha P2 a negao de uma conjuno ( (d equivalncia DM ( ( )), assim temos o seguinte: anteriormente, a 1 parte da equivalncia De Morgan ( ( b= , apesar do aparecimento do conectivo de negao ( ).

proposies que a mesma encontrada na premissa da linha P2 ( (d

Com a aplicao de DM, temos que a premissa na linha P2 ( (d

b)), que uma negao ( )

de conjuno ( ), equivalente afirmao de uma disjuno ( ) entre a negao ( ) dos dois termos da premissa na linha P2, que o que encontramos na linha P5: a negao de d ( d) em disjuno ( ) com a negao de b( b = b), ento d b.

Na linha P6 temos o resultado da aplicao do Silogismo Disjuntivo (SD) nas linhas P4 e P5. Lembrando SD novamente: ( Na linha P5 temos a disjuno linha P4 temos d ), b que possui a forma , ento = d e = b. Como na

, temos que com a negao (na linha P4) de um dos termos da disjuno (na linha P5) temos a afirmao do outro termo na linha P6, que d. Chegamos ento aonde queramos, pois a concluso pretendida era a proposio condicional c d, e para chegar a ela levantamos como hiptese (H) / premissa provisria (PP) na linha P3, o antecedente do condicional, c. Aps a aplicao de um conjunto de regras e equivalncias chegamos, na linha P6, ao conseqente da concluso condicional pretendida, hiptese c, isto nos levar a d, logo, se c, ento d. Em outras palavras, se tomarmos como d (c d). d) com a

b que pode ser entendido como

Finalizamos com mais uma linha (P7) para indicarmos a concluso pretendida (c desenvolveu at a linha P6 (3-6). Vamos a mais um exemplo de validao de argumento condicional. Agora vamos provar (a b) dada as premissas.

indicao de que chegamos a uma Prova do Condicional (PC), que partiu da linha P3 e se


39/43

27/04/12


Pi P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 j

Proposies (a j) ( g j a a g j g j B A b (g h h) j b g h)

Justificativas premissa premissa premissa Premissa Provisria (PP) ou Hiptese (H) AD 4 MP 1,5 DM 2 AD 6 MT 8,7 SD 3,9 Prova do Condicional (PC) de P4 a P10

C.Q.D. Esse exemplo explora bem os recursos da utilizao de inferncias. A demonstrao comea com a colocao na linha P4 do antecedente (a) da concluso pretendida (a b); a premissa provisria (PP).

Logo aps a introduo da PP, na linha P5 temos o resultado de aplicarmos a regra da Adio (AD) na linha P4. Lembremos da AD: O que a regra da Adio nos informa que dada uma proposio qualquer, no caso a, podemos fazer sua disjuno com qualquer outra proposio. Neste caso, decidimos escolher a proposio j como o novo termo para a disjuno, isto porque j ir nos ajudar numa seqncia de aplicaes de regras e equivalncias para liberarmos a proposio b, que justamente o conseqente da concluso a que queremos chegar (a b). Assim ficaremos com a proposio a j na linha P5. e )

Na linha P6 teremos g, que o resultado da aplicao do Modus Ponens (MP = nas linhas P1 ((a j) g) e P5 (a j). Perceba que em P1 = (a j) e

= g. Como em P5, a

j pode ser entendida como (lembre-se de que os smbolos , , etc., devem ser entendidos como fbfs e a j uma fbf), ento temos em P5 a afirmao do antecedente (a j) da condicional em P1 ((a j) g), da resultando a afirmao do conseqente em P6 (g).

Chegamos ento, linha P7, e aqui temos a aplicao de uma equivalncia em parte da premissa da linha P2: De Morgan (DM = ( ) ( ( g ) ou ( ) ( )). Repare que em P2 temos uma premissa condicional (j h)) e que seu consequente uma40/43


27/04/12


conjuno ( g )= (

h). Sabemos por DM que podemos transformar uma conjuno em disjuno e g h equivale a (g h) (pois o caso de que ( (g h).

vice-versa; na linha em questo,

)). Temos ento como resultado em P7 da aplicao de DM na linha P2, j

A linha P8 mais uma vez a aplicao da Adio (AD =

), agora na linha P6. Em P6 h, que nos ser til

temos g e introduzimos a disjuno na linha P8 com o acrscimo da proposio h; novamente aqui, a escolha de h conveniente, pois permite a criao da conjuno g j na prxima linha. Na linha P9, temos o resultado da aplicao do Modus Tollens (MT = linhas P7 (j (g h)) e P8 (g (g h). Ora, em P8, g conseqente de j

e

) nas

h justamente a negao do

h) na linha P7. Da, podermos concluir na linha P9, a negao do

antecedente do condicional ( j). Chegamos ento, em P10, aplicao da regra do Silogismo Disjuntivo (SD = ( ) e ) s linhas P3 e P9. Em P3 temos a disjuno j b, e em P9 temos j, que justamente a negao de uma das proposies/termos da disjuno j b. SD nos garante, ento, que uma vez negado um dos termos da disjuno, podemos afirmar o outro. Neste caso, o outro justamente b, o conseqente da concluso condicional que pretendemos provar (a b).

Derivamos a partir das premissas e da premissa provisria (PP = a) o conseqente da concluso condicional (b), o que nos permite afirmar que a hiptese a, em conjuno com as premissas, leva a b. Temos a prova de que a concluso a linha final P11, onde indicamos a concluso (a Condicional (PC) das linhas P4 a P10 (4-10). b deriva das premissas. Acrescentamos uma b) e informamos que foi obtida por Prova do

Agora que voc viu como funciona o processo de prova direta de validade do argumento, refaa cada um dos exemplos aqui apresentados, passo a passo, e veja se ficou alguma dvida.

5.2 Mtodo dedutivo indiretoNem sempre o mtodo direto a forma mais apropriada para provar argumentos. Por exemplo, vamos supor que voc quer provar a um amigo que o seu time melhor que o dele. Como fazer isso de forma que ao final ele fique convencido? Suponha que voc esteja defendendo um poltico,... e assim em diante. Por serem temas polmicos, a prova direta torna-se mais difcil. A prova indireta, ou prova por contradio, utiliza o princpio da no contradio para atingir o seu objetivo. Vimos nos captulos anteriores que um argumento vlido quando a conjuno das premissas condicionais com o ltimo termo (conclusivo) leva a uma tautologia. Se ocorrer uma contradio, o argumento falho. O mtodo dedutivo indireto consiste em partir do pressuposto que a sua afirmao (tese) falsa. Por exemplo, se voc quer provar que o seu time o melhor, ento suponha que isso no verdade. Para isso, negue a sua tese. Se p = O meu time o melhor a tese, a sua negao ou anttese p, ou seja, O meu no o melhor. Se a argumentao gerada a partir da anttese resultar em uma contradio, ento a tese original est correta, caso contrrio, infelizmente o seu time realmente no o melhor. Vamos ver o exemplo a seguir. Aproveitado a demonstrao passada, vamos provarcatolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s

t utilizando41/43

27/04/12


o mtodo indireto. Para tanto, iniciamos a demonstrao negando a tese,

t. Assim, temos

(

t) tpela inferncia da dupla negao (DD). Essa nova premissa passa ser chamada de Premissa Provisria (PP) e deve ser includa na demonstrao. Pi P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 P13 P14 P15 r t C.Q.D. Conforme o quadro acima, a demonstrao tem incio com a negao de tese a ser provada e recebe a descrio de PP, linha 5. Em seguida foi aplicada a inferncia Dupla Negao. Da em diante, a demonstrao ocorre normalmente at a linha 14, onde ocorre uma contradio. Podemos ento afirmar que o argumento no vlido. Ento, se com a incluso da negao de tese ocorre uma contradio, porque a tese verdadeira. Observe que em nenhum momento fizemos referncia tese a ser provada, t, mas sua afirmao correta, uma vez que, a sua negao falsa. A linha 15 reafirma a tese e tem como descrio o Mtodo Indireto (MI) utilizado desde o ponto de partida at o momento da contradio. Obs.: A contradio pode ocorrer com qualquer uma das proposies da demonstrao. Para o caso de teses condicionais, vale a mesma regra. Devemos negar a tese e coloc-la como PP na demonstrao e, se ocorrer uma contradio, significa que a anttese falsa, confirmando a tese inicialmente proposta. Como exerccio de fixao, prove o argumento, j demonstrado anteriormente, agora pelo mtodocatolicavirtual.br/conteudos/graduacao/cursos/tec_informacao/html/1o_semestre//index.php?_s 42/43

Proposies p p (s q r) r s q t

Justificativas premissa premissa premissa premissa PP DD 5

( t) t (s s p s r q r r r)) r

MT 3,6 DM 7 S2 MP 1,9 SD 8,10 S2 MP 4,12 COM 11,13 MI 5-14

27/04/12


indireto. D continuidade na demonstrao a seguir e prove (c Pi P1 P2 ... Proposies b (d ... c b)

d).

Justificativas Premissa Premissa ...

Exerccio de fixao.Prove, pelo mtodo indireto, os argumentos a seguir. a. p b. r Gabarito a. Provar (p s). A soluo aqui proposta uma soluo possvel, existem outras. q, q r, s t, t s, (r r, p s) s q, (p

(p

q))

1. p q - premissa 2. q r - premissa 3. s r - premissa 4. (p s) - PP 5. p s - DM 4 6. p - S 1 7. q - S 1 8. r - SD 2,7 9. s - MT 3,8 10. p - SD 5,9 11. p p - CON 10,6 12. (p s) - MI 4-11 b. Provar (p (p q))

1. r t - Premissa 2. t s - Premissa 3. (r s) q - Premissa 4. (p p q) - PP 5. ( p (p q)) - IM 4 6. p (p q) - DM 5 7. p - S 6 8. ( p q) - S 6 9. r s - SH 1,2 10. q - MP 3,9 11. p q) - DM 8 12. p - SD 11,10 13. p p - CON 12,7 14. p (p q) - MI 4-13


43/43

Documents

LOG - Lógica Matemática