Baixe o app para aproveitar ainda mais
Prévia do material em texto
LÓGICA MATEMÁTICA Definições Básicas Na linguagem escrita utilizam-se símbolos elementares (algarismos, letras, sinais de operações, etc), os quais sozinhos carecem de significado, mas que ao serem agrupados formam expressões que podem ter ou não significado. Para que tenham significado, usualmente, devem obedecer a certa grámatica. Exemplo: Simbolos: ,5(,,2),,,x não tem significado Expressoes: 25 x , x +y=10 já tem significado As duas principais expressões com significado são: Terminologia Básica Designações, nomes ou termos - representam o ser existente, por exemplo: 32 ; Matemática; 4,3,2,1 e 532 Sentença: Frase, expressão que encerra um sentido geral. As sentenças podem ser declarativas, interrogativas, exclamativas e mperativas, Numa Linguagem de programação, uma senteça equivale a uma intrução ou uma parte dela. No caso das instruções condicionais, deve ser necessariamente declarativa. Proposições Denomina-se proposição a toda sentença, expressa em palavras ou símbolos, que exprima um juízo ao qual se possa atribuir, dentro de certo contexto, somente um de dois valores lógicos possíveis: verdadeiro ou falso. Somente as sentenças declarativas podem-se atribuir valores de verdadeiro ou falso, o que ocorre quando a sentença é, respectivamente, confirmada ou negada. Quando uma proposição é verdadeira, atribuímos-lhe o valor lógico V; quando ela é falsa, atribuímos-lhe o valor lógico F. Em Álgebra de Boole, usa-se os valores 1 e 0, para indicar Verdadeiro ou falso. Exemplo: p: 923 ; q: A Matemática é uma ciência; r: 4,3,2,12 ; s: 25532 Observe que cada uma das proposições foi identificada com as letras p, q, r e s. As proposições verificam as regras fundamentais da lógica, as quais estão expressas nos dois princípios seguintes: Princípio da unicidade uma proposição só pode ser verdadeira ou falsa. Princípio da não contradição: uma proposição não pode ser simultaneamente verdadeira e falsa; Princípio do terceiro excluído: uma proposição é verdadeira ou falsa (verifica- se sempre uma destas situações e não uma terceira). Assim, a cada proposição é possível atribuir um e um só dos valores lógicos: verdade (V ou 1) ou falsidade (F ou 0). O universo dos valores lógicos é ℒ FV , As proposições podem ser simples ou compostas. São simples se envolvem um único fato. São compostas se envolvem mais de uma declaração, nesse caso, as declarações são conetadas pelas expressões, ou, e, não, dentre outras que aprederemos a seguir. 1.1 Equivalência de designações e proposições: Duas designações são equivalentes ou sinónimas se representam o mesmo ser. Para indicar que dois termos são equivalentes escreve-se entre eles o sinal = . Por exemplo, 3654 , porque 54 e 36 representam o mesmo número 9. Duas proposições dizem-se equivalentes se têm o mesmo valor lógico. Exemplo, a) F 72/104 é equivalente a F 3 2 1 5 b) V IN3 é equivalente a V 422 2 Linguagem proposicional e tabelas de verdade 2.1 Linguagem Proposicional Conforme foi visto, na seção anteriror as proposições serão denotadas por uma letra, usualmente p, q, r, s,.... Para dizer que tem o mesmo valor de verdade(equivalentes), simplesmente usaremos o simbolo =. Assim, p = V então p F. Se p = q então q = V. Outra forma de representar os valores de verdade de uma proposição é V(p) = F. Isso quer dizer que o valor de verdade da proposição p é igual a F. A seguir veremos Tabelas de Verdade e Conetores lógicos. As tabelas servirão para identificar todos os valores possíveis de uma proposição composta; Os conectores nos permitirão representar essas proposições compostas. 2.2 Tabelas de Verdade As tabelas de verdade são tabelas que servem para representar todos os casos possíveis quando ligamos duas ou mais proposições. Uma Tabela de Verdade é formada por, pelo menos, “n+1” colunas. Usualmente as “n” primeiras colunas são para cada uma das proposiçoes envolvidas. As restantes para os resultados que desejamos calcular. Além disso teremos 2 n linhas. No caso o número “n” refere-se ao total de proposições. As Tabelas de Verdade serão inicialmente usadas para a verificação da equivalência de proposições compostas. 2.2.1 Preenchimento da Tabela. Primeiro preenchemos as colunas das proposições, de esquerda à direita. A primeira coluna é preenchida, primeira metadae V e segunda metade F. Na seguinte coluna, divide os V´s e os F´s duas metades, cada metade é preenchida com V´s e F´s. Dessa forma, na última coluna das proposições terá V e F de modo alternado. Observe-se que no final estarão representadas todas as combinações dos valores possíveis das proposições envolvidas, sem repetição. n=1 n=2 n=3 P Resultado V F p q Resultado V V V F F V F F p q r Resultado V V V V V F V F V V F F F V V F V F F F V F F F As tabeklas de verdade serão úteis para verificar as propriedades dos conectores lógicos. Via de regra, encontraremos formas alternatuivas de avaliar uma expressão lógica. Se elas de fato são equivalentes, produzem colunas iguais. Quando o resultado, uma coluna, de uma Tabela de Verdade é totalmente V, se diz, que essa operação produz uma tautologia. Quando, ao contrário, o resultado, sempre é F, se diz que essa operação é uma contradição. Se não ocorre, nenhum desses casos, simplemesmente, se diz que se trata de uma contigência. 2.3 Conetores Também chamados operadores lógico. Através do uso deles será possível juntar duas ou mais proposições. As proposições resultantes dessa ligação serão denominadas proposições compostas. O desafio será, a partir dos valores das proposições simples, obter o valor de verdade da nova proposição. Para tanto, será necessário saber como funcionam e quando poderemos usar cda uma delas. Dominada essa técnica, poderemos ligar qualquer tipo de proposição, inclusive duas ou mais compostas. Isso será de extrema importãncia, pois na medida que a complexidade aumente, não serão as proposições simples, as que consigam representá-los. 2.3.1 Negação A negação de uma proposição p é uma nova proposição que se obtém da anterior antepondo-lhe as palavras “não é verdade que.. A negação de p representa-se por p ou ~ p ou p ou p . O perador negação troca o valor de verdade da prosição, assim, se p é verdadeira então ~p será falsa e vice-versa. Exemplos: a) p: Pitágoras era grego p : Não é verdade que Pitágoras era grego Como p:= V então p := F Linguagem corrente: Pitágoras não era grego. b) p: 5 é par. p : Não (5 é par) Como p:= F então p :=V Linguagem corrente: 5 não é par. . As tabelas seguintes, chamadas tabelas de verdade, dão o valor lógico da negação de uma proposição a partir do valor lógico desta. P p V F F V Propriedade: pp 2.3.2 Conjunção Conjunção de duas proposições, p e q, é outra proposição que resulta de ligar p e q pelo símbolo (lê-se e); esta nova proposição é verdadeira quando p e q são simultaneamente verdadeiras. Nos demais casos é Falsa. A conjunção de p e q representa-se por qp Exemplo: p: 11 é número primo q: 11 é númeroímpar qp : 11 é um número primo e 11 é um número ímpar Neste caso, como p e q são proposições verdadeiras, também qp também será V. A tabela de verdade associada à operação é: . p q pq V V V V F F F V F F F F Propriedades: 1. pp = pp = p 2. pV = p 3. pF = F 4. pq = qp Observações 1. Se fizermos a conjunção de p com ele mesmo, se p é V, então pp = V, pois ambos são V e se p = F, então pp =F, pois não temos nenhum verdadeiro, logo, o resultado é o mesmo valor de verdade de p. 2. Neste caso, tendo já um V, o resultado da conjunção só depende de P, Se p e´V, será V, se p é F, será F. 3. Nesse caso, como temos um F na conjunção, independente do valor de p, o resultado será F. 4. Observe-se que a ordem das proposições p e q não altera o resultado final, pois esse apenas depende das duas ser Verdadeiras, para ser verdadeira. 2.3.3 Disjunção Utiliza-se a palavra “ou” para obter a disjunção de duas proposições. O resultado desse conetor é verdadeiro, se pelo menos uma das proposições é Verdaeirso, senão o resultado é falso. p: 11 é número primo q: 9 é número ímpar qp : 11 é um número primo ou 9 é um número ímpar Tabela de verdade associda à operação é: p q p v q V V V V F V F V V F F F Propriedades: 1. pp = pp = p 2. pV = V 3. pF = p 4. pq = qp Observações 1. Se fizermos a disjunção de p com ele mesmo, se p é V, então pp = V, pois temos, pelo menos um V, se p = F, então pp =F, pois não temos nenhum verdadeiro, logo, o resultado é o mesmo valor de verdade de p. 2. Neste caso, tendo já um V, o resultado da disjunção será sempre V, independente do valor de p, pois já temos um V. 3. Nesse caso, precisamos que p seja V, para que o resultado seja V, se p é igual a F, o resultado seria F, pois não teríamos nenhum V. Então, o resultado da disjunção vai coincidir com o valor de p.. 4. Observe-se que a ordem das proposições p e q não altera o resultado final, pois esse apenas depende das duas ser pelo menos uma delas verdadeira,. Verdadeira. A seguir são listadas as propriedades das operações vistas na seção anterior. 2.3.4 Propriedades Propriedades Conjunção Disjunção 1 Idempotência ppp ppp 2 Comutativa pqqp pqqp 3 Associativa rqprqp rqprqp 4 Elemento neutro pVppV pFppF 5 Elemento absorvente pVppV FFppF pFppF VVppV 6 Distributiva rpqprqp prpqprq 7 Negação (lei de Morgan) qpqp qpqp Todas estas propriedades podem ser verificadas de forma relativamente simples, basta construir a tabela de verdade de cada uma das expressões que estão colocadas como iguais. Devem produzir a mesma coluna. Exemplo; Vamos verificar a lei de Morgan p q p q pq (pq) pq pq (pq) pq V V F F V F F V F F V F F V F V V V F F F V V F F V V V F F F F V V F V V F V V No caso, as colunas que correspondem a cada lado da igualdade são iguais. Sempre que isso ocorra, podemos dizer que as expressões são equivalentes. Observe que as operações, quando apresentadas, foram feitas na forma de operação binária. As propriedades 3, 6 e 7, nos permite fazer duas operações simultaneamente. No caso da propriedade 3, associatividade, ela me indica, que a operação, pode ser realizada, por pares, de esquerda à direita ou de esquerda à direita, que o resultado será o mesmo. A propriedade 7 é chamada a Lei de Morgan. Fica como exercício, verificar, usando tabelas de verdade, a validade delas. Para tanto, construa, uma coluna para cada lado da igualdade, ambas as colunas devem dar o mesmo resultado. Essas propriedades devem ser vistas sob o ponto de vista algébrico, isso quer dizer, que essas proposições p, q e r poderão ser sibstituídos por outras proposções, as quais podem ser simples ou compostas. Quando sejam compostas, devem ser usados parêntese, para evitar ambiguidades. 2.3.5 Implicação ou Condicional Dadas duas proposições, p e q, a proposição de implicação corresponde a dizer “se p então q” ou “p implica q”, e denota-se por qp , em que p (antecedente) é a condição suficiente de qp e q (consequente) é a condição necessária. A proposição qp é falsa se p verdadeira e q falsa, e verdadeira nos restantes casos é verdadeira. O resultado deste operador não é tão direto como foram os operadores anteriores, vamos tentar interpretá-lo, através de um exemplo corriqueiro. Se João estuda, então será aprovado.Nossas proposições seriam p: João estuda e q: João foi aprovado. Vejamos, as quatro possibilidades. 1. João estuda é verdadeiro e João foi aprovado. Nossa implicância é verdadeira. 2. João estuda e João e João não é aprovado. Nossa implicância tornou-se Falsa. O antecedente não garantiu o consequente; 3. João não estuda e João é aprovado. Nossa implicância continua sendo verdadeira, pois não afirma que o fato de não estudar, impedirá ao João aprovar. 4. João não estuda e João não é aprovado. Nossa implicância continua sendo verdadeira. Exemplo: p: A televisão funciona qp : Se a televisão funciona então há eletricidade q: Há electricidade Tabela de verdade: p q p q V V V V F F F V V F F V Propriedades: 1 qpqp 2 qpqp 3 pqqp 4 rprqqp é uma tautologia Vamos verificar, usando tabela de Verdade a 1 e usando a lei de Morgan a 2. p p q pq p q V F V V V V F F F F F V V V V F V F V V Observe-se que as colunas de ambas as expressões são iguais, logo, as expressões são equivalentes. Agora vamos ver a 2. qpqp (Propriedade 1 ) qpqp )( (Lei de Morgan ) qpqp Comentário: Logo, a negação da implicância equivale dizer que a proposição p e não são equivalentes. Em linguagem corriqueiro, isto se equivale a p, mas não q. No nosso primeiro exemplo, João estudou, mas não aprovou. 4.3.5 Implicação dupla ou Bicondicional Dadas duas proposições, p e q, a proposição de equivalência ou implicaão dupla corresponde a dizer “p se e só se q”, e denota-se por qp . Outra interpretação, usada em Matemática é “p é condição necessária e suficiente para q”. A equivalência ou bi condicional entre p e q será verdadeira se as proposiçãoe p e q tem o mesmo valor de verdade. Quer dizer, ambas as proposições são verdadeiras ou ambas são falsas. Observe que isso equivale a dizer que qp e pq são ambas verdadeiras. Logo, será falsa se um, exatamente, das duas proposções é falsa. Exemplo: p: A televisão liga q: Há electricidade qp : A televisão liga se e somente se há electricidade A Tabela de verdade associada a ela é a seguinte: p q p q V V V V F F F V F F F V Propriedade Fundamental: qp ou pqqp pqqpqp 5 Fórmulas Bem Formadas Como visto anteriormente, novas proposições podem ser construídas através da combinação de símbolos, que representam proposições, e de conectivos lógicos. Essas proposições — bem como as proposições atômicas — são chamadas fórmulas bem formadas — wff (well-formed formula). Uma wff é definida recursivamente como segue: 1. Um átomo é uma wff. 2. Se e são wff, então as seguintes também são wff. wff lida como não e ou Se então implica se e somente se é equivalente a Cada uma das expressões envolvendo e é chamada de forma sentencial. Uma forma sentencial é uma especificação abstrata da sintaxe de um número infinito de wff compostas de símbolos que representam proposições atômicas. Por exemplo, a wff: p (q r) é uma instância de substituição de qualquer uma das seguintes formas sentenciais: 1. onde = p (q r) 2. onde = p e = q r 3. ( ) onde = p, = q e = r Exercícios 1. Escreva ~p em linguagem corrente e indique seu valor lógico: a) p: A neve é branca b) p: Roma é a capital da França c) p: Realengo pertence à Zona Sul do Rio. 2. Indique o valor lógico de p q considerando os seguintes enunciados: a) p: O enxofre é verde - q: 7 é um número primo b) p: A Lua é uma estrela - q: Saturno é um planeta c) p: Cabral descobriu o Brasil - q: Portugal é um continente 3. Indique o valor lógico de pq considerando os seguintes enunciados a) p: O enxofre é verde - q: 7 é um número primo b) p: A Lua é uma estrela - q: Saturno é um planeta c) p: Cabral descobriu o Brasil - q: Portugal é um continente 4. Indique o valor lógico de pq considerando os seguintes enunciados d) p: O enxofre é verde - q: 7 é um número primo e) p: A Lua é uma estrela - q: Saturno é um planeta f) p: Cabral descobriu o Brasil - q: Portugal é um continente 5. Indique o valor lógico de pq considerando os seguintes enunciados g) p: O enxofre é verde - q: 7 é um número primo h) p: A Lua é uma estrela - q: Saturno é um planeta i) p: Cabral descobriu o Brasil - q: Portugal é um continente 6. Considere as sentenças: p: Tales é filho de Wilson q: Tales é neto de Jonofon. Escreva, na forma simbólica, cada uma das sentenças seguintes: a) Tales não é filho de Wilson. b) Tales é filho de Wilson e neto de Jonofon c) Tales é filho de Wilson e não é neto de Jonofon 7. Sejam as proposições p: Está frio e q: Está chovendo, traduzir pára a linguagem natural as seguintes proposições: a) p b) p q c) p q d) qp e) p q f) p q g) p q h) p q i) p q q 8. Sejam as proposições: p: O rato entrou no buraco. Q: O gato seguiu o rato. Forme sentenças, na linguagem natural, que correspondam às proposições seguintes: ) p a) ~p ~q b) p q c) ~p 9. Demonstre, utilizando tabelas-verdade, as seguintes relações de equivalência: a. p ( p q ) = p b. p ( p q ) = p c. ( p q ) ( p r ) p p r d. p q r = ( p q ) ( p r ) e. p q r ( p q ) ( p r ) f. p q = ( p q ) ~( p q ) g. p q r = p ( q r ) h. p q r = p ( q r ) Tente, usando as propriedades dos operadores provar as mesmas propriedades. 10. Sabendo que os valores lógicos das proposições p e q são, respectivamente V e F, determinar o valor lógico (V ou F) de cada uma das seguintes proposições: a) p q b) p q c) p q d) p (p q) e) p q f) p q 11. Construir a tabela de verdade de cada uma das seguintes proposições: a) ~(p q) ~ (q p) b) [p (~q r)] [ q (p ~r)] c) [(p q) r] [~p (q ~r)] 12. Sabendo que os valores lógicos das proposições ‘p’ e ‘q’ são respectivamente, F e V, determinar o valor lógico (V ou F) da proposição: [p (~q q)] ~[(p ~q) (q ~p)] 13. Determinar o valor lógico de ‘p’, isto é, v (p), sabendo que: a) v(q) = V e v( p q ) = F b) v(q) = V e v( p q) = V 14. Determinar V(p) em cada um dos seguintes casos, sabendo: a) V(q) = F e V(p q) = F b) V(q) = F e V(q q) = V c) V(q) = F e V(p q) = F d) V(q) = F e V(q p) = V e) V(q) = V e V(p q) = F f) V(q) = F e V(q p) = V 14. Determinar V(p) e V(q) em cada um dos seguintes casos, sabendo: a) V(p q) = V e V(p q) = F b) V(p q) = V e V(p q) = F c) V(p q) = V e V(p q) = V d) V(p q) = V e V(p q) = V e) V(p q) = F e V(p q) = V
Compartilhar