Tabela Verdade e Lógica

Prévia do material em texto

<p>Tabela Verdade e Lógica</p><p>Apresentação</p><p>Nesta Unidade de Aprendizagem, estudaremos a análise de proposições e a representação de</p><p>tabela verdade de proposições simples e compostas, utilizando os conectivos e, ou e não, que serão</p><p>aplicados no desenvolvimento de algoritmos.</p><p>Bons estudos.</p><p>Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:</p><p>Construir a tabela verdade dos conectivos lógicos e, ou e não.•</p><p>Usar os conectivos e, ou e não na avaliação de proposições.•</p><p>Avaliar proposições simples e compostas.•</p><p>Desafio</p><p>Considerando que q e r representam proposições básicas e que as expressões q v r e ~(q v r) são</p><p>proposições compostas, em que as proposições representam:</p><p>q : Marlene trouxe sanduíche para o lanche.</p><p>r : Antônio trouxe refrigerante para o lanche.</p><p>a) Baseado nas atribuições acima para q e r, pode-se concluir que ~( q v r) v ( q v r) é sempre (V)</p><p>verdadeiro, não importando se Marlene trouxe ou não sanduíche e Antônio trouxe ou não</p><p>refrigerante para o lanche? Responda sim ou não e justifique sua resposta comprovando-a com a</p><p>construção da tabela verdade para a proposição ~( q v r) v ( q v r).</p><p>b) Baseado nas atribuições acima, pode-se dizer que ~(q ^ r) é equivalente a (~q v ~r) para todas as</p><p>valorações possíveis para a tabela verdade para Marlene e Antônio. Responda sim ou não e</p><p>justifique sua resposta comprovando-a com a construção da tabela verdade para as duas</p><p>proposições.</p><p>Infográfico</p><p>O esquema mostra os principais temas abordados nesta Unidade.</p><p>Conteúdo do Livro</p><p>Para a construção de algoritmos e de programas eficientes e eficazes, precisamos compreender os</p><p>operadores lógicos, além de construir e analisar a tabela verdade para que possamos desenvolver</p><p>algoritmos que avaliam as expressões lógicas de forma correta.</p><p>Para auxiliar no estudo do conteúdo proposto, acompanhe o Capítulo 4 da obra Matemática</p><p>Discreta de Seymour Lipschutz e Marc Lipson. O livro servirá como base para esta Unidade de</p><p>Aprendizagem. No capítulo selecionado, serão apresentados a tabela verdade e os operadores</p><p>lógicos aplicados em pseudolinguagem.</p><p>Boa leitura!</p><p>Terceira edição</p><p>Seymour Lipschutz e Marc Lipson</p><p>Problema</p><p>Resolvido</p><p>A AJUDA PERFEITA PARA SEUS ESTUDOS!</p><p>Mais de 450 problemas resolvidos</p><p>Explicações claras e concisas de todos os conceitos</p><p>Inclui conjuntos, teoria dos grafos, álgebra Booleana,</p><p>cálculo proposicional, máquinas de Turing e muito mais!</p><p>Matemática</p><p>Discreta</p><p>L767m Lipschutz, Seymour.</p><p>Matemática discreta [recurso eletrônico] / Seymour</p><p>Lipschutz, Marc Lars Lipson ; tradução técnica: Adonai</p><p>Schlup Sant’anna. – 3. ed. – Dados eletrônicos. – Porto</p><p>Alegre : Bookman, 2013.</p><p>(Coleção Schaum)</p><p>Editado também como livro impresso em 2013.</p><p>ISBN 978-85-65837-78-1</p><p>1. Matemática. 2. Matemática discreta. I. Lipson, Marc</p><p>Lars. II. Título.</p><p>CDU 51</p><p>Catalogação na publicação: Ana Paula M. Magnus – CRB 10/2052</p><p>SEYMOUR LIPSCHUTZ é docente do Departamento de Matemática da Temple University e lecionou no Polytechnic</p><p>Institute of Brooklyn. Obteve seu Ph.D. no Courant Institute of Mathematical Sciences da New York University, em</p><p>1960. É um dos autores mais prolíficos da Coleção Schaum e escreveu também Probability: Finite Mathematics, 2.ed.;</p><p>Beginning Linear Algebra; Set Theory; Essential Computer Mathematics e Álgebra Linear, 2.ed. (publicado pela Book-</p><p>man Editora).</p><p>MARC LARS LIPSON é docente do Departamento de Matemática da University of Virginia e lecionou na University</p><p>of Georgia. Obteve seu Ph.D. em finanças na University of Michigan, em 1994. É também coautor com Seymour Lips-</p><p>chutz de 2000 Solved Problems in Discrete Mathematics e de Álgebra Linear, 3.ed. (publicado pela Bookman Editora).</p><p>Lógica e Cálculo Proposicional</p><p>Capítulo 4</p><p>4.1 INTRODUÇÃO</p><p>Muitos algoritmos e demonstrações usam expressões lógicas como:</p><p>“SE p ENTÃO q” ou “SE p1 e p2, ENTÃO q1 OU q2”</p><p>Logo, é necessário conhecer os casos nos quais essas expressões são VERDADEIRAS ou FALSAS, ou seja, saber</p><p>o “valor verdade” de tais expressões. Discutimos essas questões neste capítulo.†</p><p>Também investigamos o valor verdade de afirmações quantificadas, as quais são expressões que empregam os</p><p>quantificadores lógicos “para todo” e “existe”.‡</p><p>4.2 PROPOSIÇÕES E SENTENÇAS COMPOSTAS</p><p>Uma proposição (ou sentença) é uma afirmação declarativa que é verdadeira ou falsa, mas não ambas. Considere,</p><p>por exemplo, os seis itens a seguir:</p><p>(i) Gelo flutua na água. (iii) 2 + 2 = 4 (v) Aonde você está indo?</p><p>(ii) A China é na Europa. (iv) 2 + 2 = 5 (vi) Faça seu tema de casa.</p><p>Os quatro primeiros são proposições. Os dois últimos não. Além disso, (i) e (iii) são verdadeiras, mas (ii) e (iv) são</p><p>falsas.</p><p>Proposições compostas</p><p>Muitas proposições são compostas, isto é, formadas por subproposições e vários conectivos discutidos a seguir.</p><p>Tais sentanças são chamadas de proposições compostas. Uma proposição é denominada primitiva se não puder ser</p><p>decomposta em proposições mais simples, ou seja, se não for composta.</p><p>Por exemplo, as proposições acima, de (i) a (iv), são primitivas. Por outro lado, as duas proposições a seguir</p><p>são compostas:</p><p>“Rosas são vermelhas e violetas são azuis.” e “John é esperto ou ele estuda todas as noites.”</p><p>† N. de T.: É importante observar que os autores estão seguindo uma abordagem meramente intuitiva para o cálculo proposi-</p><p>cional clássico. Do ponto de vista da lógica matemática, o objetivo do cálculo proposicional não é estabelecer o “valor verdade”</p><p>de expressões.</p><p>‡ N. de T.: Normalmente o estudo de quantificadores se faz no cálculo de predicados de primeira ordem e não no cálculo pro-</p><p>posicional.</p><p>MATEMÁTICA DISCRETA70</p><p>A propriedade fundamental de uma proposição composta é que seu valor verdade é completamente determi-</p><p>nado pelos valores verdade de suas subproposições, junto com a maneira como elas são conectadas para</p><p>formar as proposições compostas. A seção a seguir explora alguns desses conectivos.</p><p>4.3 OPERAÇÕES LÓGICAS BÁSICAS</p><p>Esta seção discute as três operações lógicas básicas de conjunção, disjunção e negação, as quais correspondem,</p><p>respectivamente, às palavras “e”, “ou” e “não”.</p><p>Conjunção, p ∧ q</p><p>Quaisquer duas proposições podem ser combinadas pela palavra “e” para formar uma proposição composta chama-</p><p>da de conjunção das proposições originais. Simbolicamente,</p><p>p ∧ q</p><p>que se lê “p e q”, denota a conjunção de p e q. Como p ∧ q é uma proposição, ela tem um valor verdade que depen-</p><p>de apenas dos valores verdade de p e q. Especificamente:</p><p>Definição 4.1: Se p e q são verdadeiras, então p ∧ q é verdadeira; caso contrário, p ∧ q é falsa.</p><p>O valor verdade de p ∧ q pode ser definido equivalentemente pela tabela na Fig. 4-1(a). Aqui a primeira linha</p><p>é uma maneira abreviada de dizer que se p é verdadeira e q é verdadeira, então p ∧ q é verdadeira. A segunda linha</p><p>diz que se p é verdadeira e q é falsa, então p ∧ q é falsa. E assim por diante. Observe que há quatro linhas corres-</p><p>pondentes às quatro possíveis combinações de V e F para as duas subproposições p e q. Note que p ∧ q é verdadei-</p><p>ra apenas quando p e q são ambas verdadeiras.</p><p>p e q p ou q não p</p><p>Figura 4-1</p><p>Exemplo 4.1 Considere as quatro proposições a seguir:</p><p>(i) Gelo flutua na água e 2 + 2 = 4. (iii) China é na Europa e 2 + 2 = 4.</p><p>(ii) Gelo flutua na água e 2 + 2 = 5. (iv) China é na Europa e 2 + 2 = 5.</p><p>Apenas a primeira é verdadeira. As outras são falsas, pois pelo menos uma de suas subproposições é falsa.</p><p>Disjunção, p ∨ q</p><p>Duas proposições quaisquer podem ser combinadas pela palavra “ou” para formar uma proposição composta cha-</p><p>mada de disjunção das proposições originais. Simbolicamente,</p><p>p ∨ q</p><p>que se lê “p ou q”, denota a disjunção de p e q. O valor verdade de p ∨ q depende apenas dos valores verdade de p</p><p>e q como se segue.</p><p>CAPÍTULO 4 • LÓGICA E CÁLCULO PROPOSICIONAL 71</p><p>Definição 4.2: Se p e q são falsas, então p ∨ q é falsa; caso contrário, p ∨ q é verdadeira.</p><p>O valor verdade de p ∨ q pode ser definido equivalentemente pela tabela na Fig.</p><p>4-1(b). Observe que p ∨ q é</p><p>falsa apenas no quarto caso, quando p e q são ambas falsas.</p><p>Exemplo 4.2 Considere as quatro sentenças a seguir:</p><p>(i) Gelo flutua na água ou 2 + 2 = 4. (iii) China é na Europa ou 2 + 2 = 4.</p><p>(ii) Gelo flutua na água ou 2 + 2 = 5. (iv) China é na Europa ou 2 + 2 = 5.</p><p>Apenas a última sentença (iv) é falsa. As outras são verdadeiras, uma vez que pelo menos uma de suas subsentenças</p><p>é verdadeira.</p><p>Observação: A palavra “ou” é comumente usada de duas maneiras distintas em português. Às vezes, é empregada</p><p>no sentido de “p ou q, ou ambas”, ou seja, pelo menos uma das duas alternativas acontece; e, às vezes, é usada no</p><p>sentido de “p ou q, mas não ambas”, isto é, somente uma das alternativas ocorre. Por exemplo, a afirmação “Ele irá</p><p>para Harvard ou Yale” utiliza “ou” no último sentido, chamado eventualmente de disjunção exclusiva. A menos que</p><p>seja estabelecido o contrário, “ou” deve ser empregado no primeiro sentido. Essa discussão aponta para a precisão</p><p>conquistada em nossa linguagem simbólica: p ∨ q é definida por sua tabela verdade e sempre significa “p e/ou q”.</p><p>Negação, ¬ p</p><p>Dada qualquer sentença p, outra sentença, chamada de negação de p, pode ser formada escrevendo-se “Não é ver-</p><p>dade que . . .” ou “É falso que . . .” antes de p ou, se possível, inserindo em p a palavra “não”. Simbolicamente, a</p><p>negação de p, que se lê “não p ”, é denotada por</p><p>¬ p</p><p>O valor verdade de ¬ p depende do valor verdade de p como se segue:</p><p>Definição 4.3: Se p é verdadeira, então ¬ p é falsa; e se p é falsa, então ¬ p é verdadeira.</p><p>O valor verdade de ¬ p pode ser definido equivalentemente pela tabela da Fig. 4-1(c). Assim, o valor verdade</p><p>da negação de p é sempre o oposto do valor verdade de p.</p><p>Exemplo 4.3 Considere as seis sentenças a seguir:</p><p>(a1) Gelo flutua na água. (a2) É falso que gelo flutua na água. (a3) Gelo não flutua na água.</p><p>(b1) 2 + 2 = 5 (b2) É falso que 2 + 2 = 5. (b3) 2 + 2 �= 5</p><p>Então, tanto (a2) quanto (a3) são a negação de (a1); e tanto (b2) quanto (b3) são a negação de (b1). Como (a1) é</p><p>verdadeira, (a2) e (a3) são falsas; e como (b1) é falsa, (b2) e (b3) são verdadeiras.</p><p>Observação: A notação lógica para os conectivos “e”, “ou” e “não” não é completamente padronizada. Por exem-</p><p>plo, alguns textos usam:</p><p>ou</p><p>ou</p><p>4.4 PROPOSIÇÕES E TABELAS VERDADE</p><p>Seja P( p, q, . . .) uma expressão construída a partir de variáveis lógicas p, q, . . ., que assumem o valor VERDA-</p><p>DEIRO (V) OU FALSO (F), e a partir dos conectivos lógicos ∧, ∨ e ¬ (bem como outros discutidos adiante). Tal</p><p>expressão é chamada de proposição.</p><p>A principal propriedade de uma proposição P( p, q, . . .) é que seu valor verdade depende exclusivamente dos</p><p>valores verdade de suas variáveis, ou seja, o valor verdade de uma proposição é determinado, uma vez que o valor</p><p>MATEMÁTICA DISCRETA72</p><p>verdade de cada uma de suas variáveis seja conhecido. Uma maneira concisa e simples para mostrar essa relação é</p><p>por meio de uma tabela verdade. Descrevemos abaixo um modo de obter tal tabela verdade.</p><p>Considere, por exemplo, a proposição ¬(p ∧ ¬q). A Fig. 4-2(a) indica como a tabela verdade de ¬(p ∧ ¬q) é</p><p>construída. Observe que as primeiras colunas da tabela são para as variáveis p, q, . . e que há linhas suficientes para</p><p>permitir todas as possíveis combinações de V e F para essas variáveis. (Para duas variáveis, como acima, quatro</p><p>linhas são necessárias; para três variáveis, oito linhas são necessárias; e, no caso geral, para n variáveis, 2n linhas</p><p>são necessárias.) Existe, assim, uma coluna para cada estágio “elementar” da construção da proposição, sendo que</p><p>o valor verdade em cada passo é determinado a partir dos estágios anteriores, pela definição dos conectivos</p><p>∧, ∨ e ¬. Finalmente, obtemos o valor verdade da proposição, o qual aparece na última coluna.</p><p>A tabela verdade finalizada da proposição ¬(p ∧ ¬q) é mostrada na Fig. 4-2(b). Ela consiste precisamente nas</p><p>colunas da Fig. 4-2(a) que aparecem sob as variáveis e sob a proposição; as outras colunas foram meramente usa-</p><p>das na construção da tabela verdade.</p><p>Figura 4-2</p><p>Observação: Para evitar um número excessivo de parênteses, às vezes adotamos uma ordem de precedência para</p><p>os conectivos lógicos. Especificamente,</p><p>¬ precede ∧, o qual tem precedência sobre ∨</p><p>Por exemplo, ¬ p ∧ q significa (¬ p) ∧ q e não ¬(p ∧ q).</p><p>Método alternativo para construir uma tabela verdade</p><p>Outra maneira para construir a tabela verdade para ¬(p ∧ ¬q) é a seguinte:</p><p>(a) Primeiro, construímos a tabela verdade mostrada na Fig. 4-3. Ou seja, primeiro listamos todas as variáveis e as</p><p>combinações de seus valores verdade. Há também uma linha final rotulada “passo”. Em seguida, a proposição</p><p>é escrita na linha do topo e à direita de suas variáveis, com espaço suficiente de modo a existir uma coluna sob</p><p>cada variável e sob cada operação lógica na proposição. Por último, (Passo 1), os valores verdade das variáveis</p><p>são colocados na tabela sob as variáveis na proposição.</p><p>(b) Agora valores verdade adicionais são colocados na tabela verdade, coluna por coluna, sob cada operação lógi-</p><p>ca, como mostrado na Fig. 4-4. Também indicamos o passo no qual cada coluna de valores verdade é colocado</p><p>na tabela.</p><p>A tabela verdade da proposição, portanto, consiste nas colunas originais sob as variáveis e do último passo, ou</p><p>seja, a última coluna é colocada dentro da tabela.</p><p>Passo</p><p>Figura 4-3</p><p>CAPÍTULO 4 • LÓGICA E CÁLCULO PROPOSICIONAL 73</p><p>Passo Passo Passo</p><p>Figura 4-4</p><p>4.5 TAUTOLOGIAS E CONTRADIÇÕES</p><p>Algumas proposições P( p, q, . . .) contêm apenas V na última coluna de suas tabelas verdade ou, em outras pala-</p><p>vras, são verdadeiras para quaisquer valores verdade de suas variáveis. Tais proposições são chamadas de tautolo-</p><p>gias. Analogamente, uma proposição P( p, q, . . .) é dita uma contradição se tiver apenas F na última coluna de sua</p><p>tabela verdade ou, em outras palavras, se for falsa para quaisquer valores verdade de suas variáveis. Por exemplo,</p><p>a proposição “p ou não p ”, isto é, p ∨ ¬ p, é uma tautologia, e a proposição “p e não p”, isto é, p ∧ ¬ p, é uma</p><p>contradição. Isso é verificado, examinando suas tabelas verdade na Fig. 4-5. (As tabelas verdade têm somente duas</p><p>linhas, uma vez que cada proposição conta apenas com uma variável p.)</p><p>Figura 4-5</p><p>Observe que a negação de uma tautologia é uma contradição, pois é sempre falsa. E a negação de uma contradição</p><p>é uma tautologia, uma vez que é sempre verdadeira.</p><p>Agora seja P( p, q, . . .) uma tautologia, e sejam P1( p, q, . . .), P2( p, q, . . .), . . . proposições quaisquer. Como</p><p>P( p, q, . . .) não depende dos valores verdade em particular de suas variáveis p, q, . . ., podemos substituir P1 por p,</p><p>P2 por q, . . . na tautologia P( p, q, . . .) e ainda teremos uma tautologia. Em outros termos:</p><p>Teorema 4.1 (Princípio de Substituição): Se P( p, q, . . .) é uma tautologia, então P( P1, P2, . . .) é uma tautologia</p><p>para quaisquer proposições P1, P2, . . ..</p><p>4.6 EQUIVALÊNCIA LÓGICA</p><p>Duas proposições P(p, q, . . .) e Q(p, q, . . .) são logicamente equivalentes ou, simplesmente, equivalentes ou</p><p>iguais, e se escreve</p><p>P(p, q, . . .) ≡ Q(p, q, . . .)</p><p>se tiverem tabelas verdade idênticas. Considere, por exemplo, as tabelas verdade de ¬(p ∧ q) e ¬p ∨ ¬q que apa-</p><p>recem na Fig. 4-6. Observe que ambas as tabelas verdade são a mesma, isto é, as duas proposições são falsas no</p><p>primeiro caso e verdadeiras nos outros três casos. Consequentemente, podemos escrever</p><p>¬(p ∧ q) ≡ ¬p ∨ ¬q</p><p>Em outras palavras, as proposições são logicamente equivalentes.</p><p>Observação: Sejam p a sentença “Rosas são vermelhas” e q a sentença “Violetas são azuis”. Seja S a declaração:</p><p>“Não é verdade que rosas são vermelhas e violetas são azuis.”</p><p>Então S pode ser escrita na forma ¬(p ∧ q). Contudo, como observado acima, ¬(p ∧ q) ≡ ¬p ∨ ¬q. Consequente-</p><p>mente, S tem o mesmo significado da declaração:</p><p>“Rosas não são vermelhas ou violetas não são azuis.”</p><p>MATEMÁTICA DISCRETA74</p><p>Figura 4-6</p><p>4.7 ÁLGEBRA DE PROPOSIÇÕES</p><p>Proposições satisfazem várias leis que são listadas</p><p>na Tabela 4-1. (Nessa tabela, V e F são restritos aos valores</p><p>verdade “Verdadeiro” e “Falso”, respectivamente.) Estabelecemos esse resultado formalmente.</p><p>Teorema 4.2: Proposições satisfazem as leis da Tabela 4-1.</p><p>(Observe a semelhança entre a Tabela 4-1 e a Tabela 1-1 sobre conjuntos.)</p><p>Tabela 4-1 Leis da álgebra de proposições</p><p>Idempotência (1a) p ∨ p ≡ p (1b) p ∧ p ≡ p</p><p>Associatividade (2a) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (2b) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)</p><p>Comutatividade (3a) p ∨ q ≡ q ∨ p (3b) p ∧ q ≡ q ∧ p</p><p>Distributividade (4a) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) (4b) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)</p><p>Identidade</p><p>(5a) p ∨ F ≡ p (5b) p ∧ V ≡ p</p><p>(6a) p ∨ V ≡ V (6b) p ∧ F ≡ F</p><p>Involução (7) ¬¬p ≡ p</p><p>Complementaridade</p><p>(8a) p ∨ ¬p ≡ V (8b) p ∧ ¬p ≡ V</p><p>(9a) ¬V ≡ F (9b) ¬F ≡ V</p><p>Leis de DeMorgan (10a) ¬( p ∨ q) ≡ ¬p ∧¬q (10b) ¬( p ∧ q) ≡ ¬p ∨¬q</p><p>4.8 SENTENÇAS CONDICIONAIS E BICONDICIONAIS</p><p>Muitas sentenças, especialmente em matemática, são da forma “Se p então q”. Tais sentenças são chamadas de</p><p>condicionais e são denotadas por</p><p>p → q</p><p>A condicional p → q é frequentemente lida como “p implica q” ou “p somente se q”.</p><p>Outra sentença comum é da forma “p se, e somente se, q”. Tais sentenças são conhecidas como bicondicionais</p><p>e são denotadas por</p><p>p ↔ q</p><p>Os valores verdade de p → q e p ↔ q são definidos pelas tabelas na Fig. 4-7(a) e (b). Note que:</p><p>(a) A condicional p → q é falsa apenas quando a primeira parte p é verdadeira e a segunda parte q é falsa. Logo,</p><p>quando p é falsa, a condicional p → q é verdadeira, independentemente do valor verdade de q.</p><p>(b) A bicondicional p ↔ q é verdadeira sempre que p e q têm os mesmos valores verdade e falsa nos demais casos.</p><p>CAPÍTULO 4 • LÓGICA E CÁLCULO PROPOSICIONAL 75</p><p>A tabela verdade de ¬p ∧ q aparece na Fig. 4-7(c). Observe que a tabela verdade de ¬p ∨ q e p → q são idên-</p><p>ticas, ou seja, são ambas falsas apenas no segundo caso. Consequentemente, p → q é logicamente equivalente</p><p>a ¬p ∨ q; ou seja,</p><p>p → q ≡ ¬p ∨ q</p><p>Em outras palavras, a sentença condicional “Se p então q” é logicamente equivalente à sentença “Não p ou q”,</p><p>a qual envolve apenas os conectivos ∨ e ¬ e, assim, já faz parte de nossa linguagem. Podemos considerar p → q</p><p>como uma abreviação para uma sentença recorrente.</p><p>Figura 4-7</p><p>4.9 ARGUMENTOS</p><p>Um argumento (ou inferência) é uma afirmação na qual um dado conjunto de proposições P1, P2, . . . , Pn, chama-</p><p>das de premissas, implica (tem como consequência) outra proposição Q, chamada de conclusão. Tal argumento é</p><p>denotado por</p><p>P1, P2, . . . , Pn � Q</p><p>A noção de “argumento lógico” ou “argumento válido” é formalizada como se segue:</p><p>Definição 4.4: Um argumento P1, P2, . . . , Pn � Q é dito válido se Q é verdadeira se todas as premissas P1, P2, . . .,</p><p>Pn são verdadeiras.</p><p>Um argumento que não é válido é chamado de falácia.</p><p>Exemplo 4.4</p><p>(a) O seguinte argumento é válido:</p><p>p, p → q � q (Modus Ponens)</p><p>A demonstração dessa regra segue da tabela verdade da Fig. 4-7(a). Especificamente, p e p → q são simulta-</p><p>neamente verdadeiras apenas no Caso (linha) 1 e, nesse caso, q é verdadeira.</p><p>(b) O argumento a seguir é uma falácia:</p><p>p → q, q � p</p><p>p → q e q são ambas verdadeiras no Caso (linha) 3 da tabela verdade da Fig. 4-7(a), mas, nesse caso, p é falsa.</p><p>Agora, as proposições P1, P2, . . . , Pn são simultaneamente verdadeiras se, e somente se, a proposição</p><p>P1 ∧ P2 ∧ . . . Pn é verdadeira. Assim, o argumento P1, P2, . . . , Pn � Q é válido se, e somente se, Q é verdadeira</p><p>sempre que P1 ∧ P2 ∧ . . . ∧ Pn for verdadeira ou, equivalentemente, se a proposição (P1 ∧ P2 ∧ . . . ∧ Pn) → Q</p><p>for uma tautologia. Estabelecemos esse resultado formalmente.</p><p>Teorema 4.3: O argumento P1, P2, . . . , Pn � Q é válido se, e somente se, a proposição (P1 ∧ P2 . . . ∧ Pn) → Q é</p><p>uma tautologia.</p><p>Aplicamos esse teorema no exemplo a seguir.</p><p>MATEMÁTICA DISCRETA76</p><p>Exemplo 4.5 Um princípio fundamental de raciocínio lógico diz:</p><p>“Se p implica q e q implica r, então p implica r”</p><p>p</p><p>V</p><p>V</p><p>V</p><p>V</p><p>F</p><p>F</p><p>F</p><p>F</p><p>q</p><p>V</p><p>V</p><p>F</p><p>F</p><p>V</p><p>V</p><p>F</p><p>F</p><p>r</p><p>V</p><p>F</p><p>V</p><p>F</p><p>V</p><p>F</p><p>V</p><p>F</p><p>V</p><p>V</p><p>V</p><p>V</p><p>F</p><p>F</p><p>F</p><p>F</p><p>1</p><p>V</p><p>V</p><p>F</p><p>F</p><p>V</p><p>V</p><p>V</p><p>V</p><p>2</p><p>V</p><p>V</p><p>F</p><p>F</p><p>V</p><p>V</p><p>F</p><p>F</p><p>1</p><p>V</p><p>F</p><p>F</p><p>F</p><p>V</p><p>F</p><p>V</p><p>V</p><p>3</p><p>V</p><p>V</p><p>F</p><p>F</p><p>V</p><p>V</p><p>F</p><p>F</p><p>1</p><p>V</p><p>F</p><p>V</p><p>V</p><p>V</p><p>F</p><p>V</p><p>V</p><p>2</p><p>V</p><p>F</p><p>V</p><p>F</p><p>V</p><p>F</p><p>V</p><p>F</p><p>1</p><p>V</p><p>V</p><p>V</p><p>V</p><p>V</p><p>V</p><p>V</p><p>V</p><p>4</p><p>V</p><p>V</p><p>V</p><p>V</p><p>F</p><p>F</p><p>F</p><p>F</p><p>1</p><p>V</p><p>F</p><p>V</p><p>F</p><p>V</p><p>V</p><p>V</p><p>V</p><p>2</p><p>V</p><p>F</p><p>V</p><p>F</p><p>V</p><p>F</p><p>V</p><p>F</p><p>1</p><p>�( p → q) ∧ (q → r)� → ( p → r)</p><p>Passo</p><p>Figura 4-8</p><p>Ou seja, o argumento a seguir é válido:</p><p>p → q, q → r � p → r (Lei do Silogismo)</p><p>Esse fato é verificado pela tabela verdade na Fig. 4-8, a qual mostra que a seguinte proposição é uma tautologia:</p><p>[(p → q) ∧ (q → r)] → (p → r)</p><p>De forma equivalente, o argumento é válido, uma vez que as premissas p → q e q → r são simultaneamente verda-</p><p>deiras apenas nos Casos (linhas) 1, 5, 7 e 8 e, nesses casos, a conclusão também é verdadeira. (Observe que a tabe-</p><p>la verdade demandou 23 = 8 linhas, pois há três variáveis p, q e r.)</p><p>Agora aplicamos a teoria acima sobre argumentos envolvendo sentenças específicas. Enfatizamos que a vali-</p><p>dade de um argumento não depende dos valores verdade nem do conteúdo das sentenças que surgem no argumento,</p><p>mas da forma particular da inferência. Isso é ilustrado no exemplo a seguir.</p><p>Exemplo 4.6 Considere o seguinte argumento:</p><p>S1: Se um homem é solteiro, ele é infeliz.</p><p>S2: Se um homem é infeliz, ele morre cedo.</p><p>S: Solteiros morrem cedo.</p><p>Aqui a sentença S abaixo da linha denota a conclusão do argumento, e as sentenças S1 e S2 acima da linha corres-</p><p>pondem às premissas. Afirmamos que o argumento S1, S2, � S é válido, pois ele é da forma</p><p>p → q, q → r � p → r</p><p>onde p é “Ele é solteiro”, q é “Ele é infeliz” e r é “Ele morre cedo”; e pelo Exemplo 4.5 essa inferência (Lei do</p><p>Silogismo) é válida.</p><p>4.10 FUNÇÕES PROPOSICIONAIS, QUANTIFICADORES</p><p>Seja A um dado conjunto. Uma função proposicional (ou sentença aberta ou condição) definida sobre A é uma</p><p>expressão</p><p>p(x)</p><p>que tem a propriedade de que p(a) é verdadeira ou falsa para cada a ∈ A. Ou seja, p(x) se torna uma sentença (com</p><p>um valor verdade) sempre que a variável x é substituída por qualquer elemento a ∈ A. O conjunto A é chamado de</p><p>CAPÍTULO 4 • LÓGICA E CÁLCULO PROPOSICIONAL 77</p><p>domínio de p(x), e o conjunto Tp de todos os elementos de A para os quais p(a) é verdadeira é chamado de conjun-</p><p>to verdade de p(x). Em outras palavras,</p><p>Tp = {x | x ∈ A, p(x) é verdadeira} ou Tp = {x | p(x)}</p><p>Frequentemente, quando A é algum conjunto de números, a condição p(x) tem a forma de uma equação ou desi-</p><p>gualdade envolvendo a variável x.</p><p>Exemplo 4.7 Encontre o conjunto verdade para cada função proposicional p(x) definida sobre o conjunto N dos</p><p>inteiros positivos.</p><p>(a) Seja p(x) a fórmula “x + 2 > 7”. Seu conjunto verdade é {6, 7, 8, . . .}, consistindo de todos os inteiros maiores</p><p>do que 5.</p><p>(b) Seja p(x) a fórmula “x + 5 < 3”. Seu conjunto verdade é o conjunto vazio ∅. Isto é, p(x) não é verdade para</p><p>qualquer inteiro em N.</p><p>(c) Seja p(x) a fórmula “x + 5 > 1”. Seu conjunto verdade é N. Ou seja, p(x) é verdadeira para todo elemento de N.</p><p>Observação: O exemplo acima mostra que se p(x) é uma função proposicional definida sobre um conjunto A,</p><p>então p(x) poderia ser verdadeira para todo x ∈ A, para algum (ou alguns) x ∈ A, ou para nenhum x ∈ A. As duas</p><p>subseções a seguir discutem quantificadores relacionados com tais funções proposicionais.</p><p>Quantificador universal</p><p>Seja p(x) uma função proposicional definida sobre um conjunto A. Considere a expressão</p><p>(∀x ∈ A)p(x) ou ∀x p(x) (4.1)</p><p>a qual se lê “Para todo x em A, p(x) é uma sentença verdadeira” ou, simplesmente, “Para todo x, p(x)”. O símbolo</p><p>∀</p><p>que se lê “para todo” é chamado de quantificador universal. A sentença (4.1) é equivalente à afirmação</p><p>Tp = {x | x ∈ A, p(x)} = A (4.2)</p><p>ou seja, à afirmação de que o conjunto verdade de p(x) é o conjunto todo A.</p><p>A expressão p(x) em si é uma sentença aberta ou condição e, portanto, não tem valor verdade. Contudo, ∀x</p><p>p(x), isto é, p(x) precedida pelo quantificador ∀, tem</p><p>um valor verdade que segue da equivalência entre (4.1) e (4.2).</p><p>Especificamente:</p><p>Q1: Se {x | x ∈ A, p(x)} = A, então ∀x p(x) é verdadeira; caso contrário, ∀x p(x) é falsa.</p><p>Exemplo 4.8</p><p>(a) A proposição (∀n ∈ N)(n + 4 > 3) é verdadeira, pois {n | n + 4 > 3} = {1, 2, 3, . . .} = N.</p><p>(b) A proposição (∀n ∈ N)(n + 2 > 8) é falsa, pois {n | n + 2 > 8} = {7, 8, . . .} �= N.</p><p>(c) O símbolo ∀ pode ser usado para definir a interseção de uma coleção indexada {Ai | i ∈ I} de conjuntos Ai</p><p>como se segue:</p><p>∩(Ai | i ∈ I) = {x | ∀i ∈ I, x ∈ Ai}</p><p>Quantificador existencial</p><p>Seja p(x) uma função proposicional definida sobre um conjunto A. Considere a expressão</p><p>(∃x ∈ A)p(x) ou ∃x, p(x) (4.3)</p><p>MATEMÁTICA DISCRETA78</p><p>que se lê “Existe um x em A tal que p(x) é uma sentença verdadeira” ou, simplesmente, “Para algum x, p(x)”. O</p><p>símbolo</p><p>∃</p><p>o qual se lê “existe” ou “para algum” ou “para pelo menos um” é chamado de quantificador existencial. A sentença</p><p>(4.3) é equivalente à sentença</p><p>Tp = {x | x ∈ A, p(x)} �= ∅ (4.4)</p><p>isto é, à afirmação de que o conjunto verdade de p(x) não é vazio. Consequentemente, ∃x p(x), ou seja, p(x)</p><p>precedida pelo quantificador ∃, tem um valor verdade. Especificamente:</p><p>Q2: Se {x | p(x)} �= ∅, então ∃x p(x) é verdadeira; caso contrário, ∃x p(x) é falsa.</p><p>Exemplo 4.9</p><p>(a) A proposição (∃n ∈ N)(n + 4 < 7) é verdadeira, pois {n | n + 4 < 7} = {1, 2} �= ∅.</p><p>(b) A proposição (∃n ∈ N)(n + 6 < 4) é falsa, uma vez que {n | n + 6 < 4} = ∅.</p><p>(c) O símbolo ∃ pode ser usado para definir a união de uma coleção indexada {Ai | i ∈ I} de conjuntos Ai, como se</p><p>segue:</p><p>∪(Ai | i ∈ I) = {x | ∃i ∈ I, x | ∈ Ai}</p><p>4.11 NEGAÇÃO DE SENTENÇAS QUANTIFICADAS</p><p>Considere a sentença: “Todos os bacharéis em matemática são homens”. Sua negação se lê:</p><p>“Não é o caso de que todos os bacharéis em matemática são homens” ou, equivalentemente, “Existe pelo me-</p><p>nos um bacharel em matemática que é mulher (não é homem)”</p><p>Simbolicamente, usando M para denotar o conjunto de bacharéis de matemática, a afirmação acima pode ser escri-</p><p>ta como</p><p>¬(∀x ∈ M)(x é homem) ≡ (∃ x ∈ M) (x não é homem)</p><p>ou, quando p(x) denota “x é homem”,</p><p>¬(∀x ∈ M) p(x) ≡ (∃ x ∈ M) ¬p(x) ou ¬∀xp(x) ≡ ∃x¬p(x)</p><p>Isso é verdade para qualquer proposição p(x). Ou seja:</p><p>Teorema 4.4 (DeMorgan): ¬(∀x ∈ A)p(x) ≡ (∃ x ∈ A)¬p(x).</p><p>Em outras palavras, as duas sentenças a seguir são equivalentes:</p><p>(1) Não é verdade que para todo a ∈ A, p(a) é verdadeira. (2) Existe um a ∈ A tal que p(a) é falsa.</p><p>Há um teorema análogo para a negação de uma proposição que contém o quantificador existencial.</p><p>Teorema 4.5 (DeMorgan): ¬(∃x ∈ A)p(x) ≡ (∀x ∈ A)¬p(x)</p><p>Ou seja, as duas sentenças a seguir são equivalentes:</p><p>(1) Não é verdade que para algum a ∈ A, p(a) é verdadeira. (2) Para todo a ∈ A, p(a) é falsa.</p><p>CAPÍTULO 4 • LÓGICA E CÁLCULO PROPOSICIONAL 79</p><p>Exemplo 4.10</p><p>(a) As sentenças a seguir são negações uma da outra:</p><p>“Para todos os inteiros positivos n temos n + 2 > 8”</p><p>“Existe um inteiro positivo n tal que n + 2 �> 8”</p><p>(b) As sentenças a seguir também são negações uma da outra:</p><p>“Existe uma pessoa (viva) com 150 anos de idade”</p><p>“Toda pessoa viva não tem 150 anos de idade”</p><p>Observação: A expressão ¬p(x) tem o significado óbvio:</p><p>“A sentença ¬p(a) é verdadeira quando p(a) é falsa, e vice-versa”</p><p>Anteriormente, ¬ foi usado como uma operação sobre sentenças; aqui ¬ é usado como uma operação sobre fun-</p><p>ções proposicionais. Analogamente, p(x) ∧ q(x), que se lê “p(x) e q(x)”, é definida por:</p><p>“A sentença p(a) ∧ q(a) é verdadeira quando p(a) e q(a) são verdadeiras”</p><p>Analogamente, p(x) ∨ q(x), que se lê “p(x) e q(x)”, é definida por:</p><p>“A sentença p(a) ∨ q(a) é verdadeira quando p(a) ou q(a) é verdadeira”</p><p>Assim, em termos de conjuntos verdade:</p><p>(i) ¬p(x) é o complemento de p(x).</p><p>(ii) p(x) ∧ q(x) é a interseção entre p(x) e q(x).</p><p>(iii) p(x) ∨ q(x) é a união de p(x) com q(x).</p><p>Podemos também mostrar que as leis para proposições valem igualmente para funções proposicionais. Por</p><p>exemplo, temos as Leis de DeMorgan:</p><p>¬(p(x) ∧ q(x)) ≡ ¬p(x) ∨ ¬q(x) e ¬(p(x) ∨ q(x)) ≡ ¬p(x) ∧ ¬q(x)</p><p>Contraexemplo</p><p>O Teorema 4.6 nos diz que para mostrar que uma sentença ∀x, p(x) é falsa, é equivalente mostrar que ∃ x¬p(x) é</p><p>verdadeira ou, em outros termos, que existe um elemento x0 com a propriedade de que p(x0) é falsa. Tal elemento</p><p>x0 é chamado de contraexemplo da afirmação ∀x, p(x).</p><p>Exemplo 4.11</p><p>(a) Considere a sentença ∀x ∈ R, |x| �= 0. Ela é falsa, pois 0 é um contraexemplo, ou seja, |0| �= 0 não é verdadeira.</p><p>(b) Considere a sentença ∀x ∈ R, x2 ≥ x. Ela não é verdadeira, uma vez que, por exemplo, é um contraexemplo.</p><p>Especificamente, não é verdadeira, isto é,</p><p>(c) Considere a sentença ∀x ∈ N, x2 ≥ x. Ela é verdadeira, onde N é o conjunto de inteiros positivos. Em outras</p><p>palavras, não existe inteiro positivo n para o qual n2 < n.</p><p>MATEMÁTICA DISCRETA80</p><p>Funções proposicionais com mais de uma variável</p><p>Uma função proposicional (de n variáveis) definida sobre um produto cartesiano A = A1 × · · · × An é uma expressão</p><p>p(x1, x2, . . ., xn)</p><p>que tem a propriedade de que p(a1, a2, . . ., an) é verdadeira ou falsa para qualquer n-upla p(a1, . . . , an) de A. Por</p><p>exemplo,</p><p>x + 2y + 3z < 18</p><p>é uma função proposicional sobre N3 = N × N × N. Tal função proposicional não tem valor verdade. Contudo,</p><p>temos o que se segue:</p><p>Princípio básico: Uma função proposicional precedida por um quantificador para cada variável, por exemplo,</p><p>∀x∃y, p(x, y) ou ∃x ∀y ∃z, p(x, y, z)</p><p>denota uma sentença e tem um valor verdade.</p><p>Exemplo 4.12 Seja B = {1, 2, 3, . . . , 9} e considere que p(x, y) denota “x + y = 10”. Então p(x, y) é uma função</p><p>proposicional sobre A = B2 = B × B.</p><p>(a) O que se segue é uma sentença, uma vez que há um quantificador para cada variável:</p><p>∀x∃y, p(x, y), isto é, “Para todo x, existe y tal que x + y = 10”</p><p>Essa sentença é verdadeira. Por exemplo, se x = 1, faça y = 9; se x = 2, faça y = 8; e assim por diante.</p><p>(b) O que se segue também é uma sentença:</p><p>∃y∀x, p(x, y), isto é, “Existe y tal que, para todo x, temos x + y = 10”</p><p>Não existe tal y; logo, essa sentença é falsa.</p><p>Observe que a única diferença entre (a) e (b) é a ordem dos quantificadores. Assim, uma ordenação diferente</p><p>dos quantificadores pode produzir uma sentença diferente. Notamos que, quando traduzimos tais sentenças quan-</p><p>tificadas para o português, a expressão “tal que” frequentemente é seguida por “existe”.</p><p>Negando sentenças quantificadas com mais de uma variável</p><p>Sentenças quantificadas com mais de uma variável podem ser negadas aplicando sucessivamente os Teoremas 4.5</p><p>e 4.6. Assim, cada ∀ é mudado para ∃ e cada ∃ é mudado para ∀, à medida que o símbolo de negação ¬ passa pela</p><p>sentença, da esquerda para a direita. Por exemplo,</p><p>¬[∀x∃y∃z, p(x, y, z)] ≡ ∃x¬[∃y∃z, p(x, y, z)] ≡ ¬∃z∀y[∃z, p(x, y, z)</p><p>≡ ∃x∀y∀z, ¬p(x, y, z)</p><p>Naturalmente, não colocamos todos os passos quando negamos tais sentenças quantificadas.</p><p>Exemplo 4.13</p><p>(a) Considere a sentença quantificada:</p><p>“Todo estudante cursa pelo menos uma disciplina na qual o docente é um professor assistente.”</p><p>Sua negação é a sentença:</p><p>“Existe um estudante tal que, em toda disciplina cursada, o docente não é um professor assistente.”</p><p>CAPÍTULO 4 • LÓGICA E CÁLCULO PROPOSICIONAL 81</p><p>(b) A definição formal de que L é o limite de uma sequência a1, a2, . . . segue abaixo:</p><p>∀ ∈ > 0, ∃ n0 ∈ N, ∀n > n0, temos | an − L| < ∈</p><p>Assim, L não é o limite da sequência a1, a2, . . . quando:</p><p>∃ ∈ > 0, ∀n0 ∈ N, ∃n > n0 tal que | an − L| ≥ ∈</p><p>Problemas Resolvidos</p><p>Proposições e tabelas verdade</p><p>4.1 Seja p a sentença “Está frio” e seja q “Está chovendo”. Dê uma sentença verbal que descreva cada uma das</p><p>sentenças a seguir: (a) ¬p; (b) p ∧ q; (c) p ∨ q; (d) q ∨ ¬p.</p><p>Em cada caso, traduza ∧, ∨ e ∼ como “e”, “ou” e “É falso que” ou “não”, respectivamente, e então simplifique a</p><p>sentença em português.</p><p>(a) Não está frio. (c) Está frio ou está chovendo.</p><p>(b) Está frio e chovendo. (d) Está chovendo ou não está frio.</p><p>4.2 Encontre a tabela verdade de ¬p ∧ q.</p><p>Construa a tabela verdade de ¬p ∧ q</p><p>como na Fig. 4-9(a).</p><p>Figura 4-9</p><p>4.3 Verifique que a proposição p ∨ ¬(p ∧ q) é uma tautologia.</p><p>Construa a tabela verdade de p ∨ ¬(p ∧ q) como mostrado na Fig. 4-9(b). Como o valor verdade de p ∨ ¬(p ∧ q)</p><p>é V para todos os valores de p e q, a proposição é uma tautologia.</p><p>4.4 Mostre que as proposições ¬(p ∧ q) e ¬p ∨ ¬q são logicamente equivalentes.</p><p>Construa as tabelas verdade para ¬(p ∧ q) e ¬p ∨ ¬q, como na Fig. 4-10. Como as tabelas verdade são as mesmas</p><p>(ambas as proposições são falsas no primeiro caso e verdadeiras nos outros três casos), as proposições ¬(p ∧ q) e ¬p ∨</p><p>¬q são logicamente equivalentes e podemos escrever</p><p>¬(p ∧ q) ≡ ¬p ∨ ¬q</p><p>Figura 4-10</p><p>Encerra aqui o trecho do livro disponibilizado para</p><p>esta Unidade de Aprendizagem. Na Biblioteca Virtual</p><p>da Instituição, você encontra a obra na íntegra.</p><p>Dica do Professor</p><p>Conhecer e aplicar os conectivos lógicos, assim como a construção da tabela verdade, é muito</p><p>importante para o desenvolvimento de algoritmos, a fim de que eles possam executar de forma</p><p>correta as operações e expressões definidas pelo programador.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/8bad992d3a99ea7220e8b3370a7b5930</p><p>Exercícios</p><p>1) A proposição é submetida a uma avaliação e tem por objetivo modelar o raciocínio humano.</p><p>As sentenças a serem avaliadas podem ser consideradas como exclamativas, interrogativas</p><p>ou imperativas, mas a lógica proposicional utiliza somente as frases ou sentenças</p><p>declarativas, denominadas de proposição, que podem afirmar ou negar alguma coisa; a</p><p>proposição possui um valor de verdade, que pode assumir como verdadeiro ou falso. As</p><p>proposições podem ser simples ou compostas, necessitando, nas compostas, dos conectivos</p><p>lógicos (e, ou, não) para serem avaliadas. Considerando os conceitos apresentados acima,</p><p>assinale a alternativa que contempla uma proposição.</p><p>A) Vá trabalhar!</p><p>B) Joana é professora de nível superior.</p><p>C) 16 + 17.</p><p>D) Qual a sua cor preferida?</p><p>E) Compre aquele chapéu.</p><p>2) A construção da tabela verdade é muito importante, pois permite representar e avaliar as</p><p>proposições com a aplicação dos seus conectivos lógicos, verificando se a proposição é</p><p>verdadeira ou é falsa.</p><p>Considere para o problema as letras w, x, f e g que representam as proposições, e os</p><p>símbolos ~(não), ^(e) e v(ou) como operadores lógicos. Avalie as alternativas apresentadas a</p><p>seguir.</p><p>I. Dado falso para a proposição w e x, pode-se dizer que a proposição (~ w) v ((~ x) v w)</p><p>também é F - falsa.</p><p>II. Dado verdadeiro para a proposição f e g, pode-se dizer que a proposição (~f) ^ (~ g) ^ f é F</p><p>- falsa.</p><p>III. Dado verdadeiro para a proposição w e falso para a proposição g e x, pode-se dizer que a</p><p>proposição ( w v x ) ^ ( ( g v w ) ^ (~ x) ) é F - falsa.</p><p>Assinale apenas a alternativa correta.</p><p>A) I e II.</p><p>B) II.</p><p>C) I, II e III.</p><p>D) II e III.</p><p>E) I e III.</p><p>3) A cola não autorizada é um problema existente em muitas salas de aula, e a pessoa mais</p><p>prejudicada nesse processo é o aluno. Com a cola, os dados para a análise do professor são</p><p>distorcidos, pois ele verifica, com base nos dados da avaliação, onde estão os pontos ainda não</p><p>desenvolvidos pela turma, para, assim, preparar estratégias que desenvolvam as habilidades que</p><p>ainda apresentaram dificuldades.</p><p>Considere o problema da cola representado nas sentenças abaixo:</p><p>a) Colar é proibido, mas muitos alunos colam.</p><p>b) Colar não é proibido e faz bem ao aprendizado.</p><p>As sentenças acima podem ser representadas através de proposições e conectivos lógicos.</p><p>Considere também que m, x e n representem as proposições listadas na tabela a seguir:</p><p>Com base nas proposições acima, os conectivos estudados e considerando a notação introduzida</p><p>na Unidade de Aprendizagem, analise e julgue as alternativas apresentadas abaixo:</p><p>I - A sentença aa pode ser corretamente representada por m ^ (~ n).</p><p>II - A sentença b pode ser corretamente representada por (~ m) ^ (~ x).</p><p>III - A sentença a pode ser corretamente representada por m ^ n.</p><p>IV - A sentença b pode ser corretamente representada por (~ m) v ( x).</p><p>Assinale a alternativa correta.</p><p>A) I e II.</p><p>B) I e III.</p><p>C) I, II e III.</p><p>D) II e III.</p><p>E) III e IV.</p><p>4) A tabela verdade é uma forma de representarmos e avaliarmos expressões lógicas, as quais</p><p>são utilizadas na programação de algoritmos para avaliar sentenças. Conforme o resultado,</p><p>poderá ser tomada uma decisão, e, assim, um comando ou um conjunto de comandos</p><p>diferentes podem ser executados em situações nas quais a expressão é verdadeira ou falsa.</p><p>Para a avaliação das expressões, deve-se observar os parênteses apresentados na expressão,</p><p>priorizando a sua resolução.</p><p>Considerando a tabela verdade dos conectivos e, ou e não, resolva as seguintes expressões</p><p>lógicas:</p><p>I – não V ou (V e (V ou F))</p><p>II – ((V e V) e não V) ou (não V ou não F)</p><p>III – V e F ou não F</p><p>Assinale a alternativa que representa corretamente o resultado das expressões lógicas acima</p><p>apresentadas.</p><p>A) V, V, V.</p><p>B) F, F, F.</p><p>C) V, F, F.</p><p>D) V, V, F.</p><p>E) F, F, V.</p><p>Para a construção da tabela verdade, devemos calcular o número de linhas necessárias para a</p><p>construção da tabela em questão. O número de linhas é calculado pela representação e 2 na base n</p><p>(2n), em que n representa o número de preposições do problema.</p><p>A proposição a ser avaliada será ( p ^ q ) v (~r ); assim, teremos três preposições: p, q e r. Aplicando</p><p>2n, teremos 23, que é representado por 2 x 2 x 2 = 8, ou seja, 8 linhas são necessárias para a</p><p>construção da tabela verdade para a proposição ( p ^ q ) v (~r ).</p><p>Para facilitar a resolução da expressão, a tabela construída abaixo normalmente é necessária.</p><p>Considerando os conectivos lógicos usuais ~, ^ e v e as proposições lógicas p, q e r, analise e</p><p>preencha a tabela apresentada para 23 proposições, nas quais a coluna correspondente à</p><p>proposição (p ^ q) v (~r ) conterá somente os valores V para Verdadeiro e F para Falso.</p><p>5)</p><p>Para auxiliar e facilitar a avaliação da expressão, quebre em partes; primeiro, deverão ser</p><p>resolvidas as expressões entre os parênteses mais internos. A ordem para o problema proposto</p><p>será:</p><p>Análise 1 – resolva (p ^q)</p><p>Análise 2 – resolva (~r)</p><p>Análise 3 – resolva Resultado Análise 1 V Resultado da Análise 2. Assim, teremos o resultado da</p><p>expressão (p ^ q) v (~r) que será preenchido na tabela a seguir.</p><p>Considerando a valoração de cima para baixo e na sequência, defina a tabela verdade apresentada</p><p>acima para a proposição (p ^ q) v (~r) e assinale a alternativa correta de valoração.</p><p>A) V-V-F-V-F-V-F-V.</p><p>B) V-V-V-V-V-V-V-V.</p><p>C) F-F-F-F-F-F-F-V.</p><p>D) F-F-V-F-V-F-V-F.</p><p>E) F-F-F-V-V-F-V-F.</p><p>Na prática</p><p>A lógica é muito aplicada na arquitetura de computadores, área em que são projetados circuitos</p><p>eletrônicos na construção de programas resolvendo problemas e também aplicando a inteligência</p><p>artificial. Utilizamos a lógica no nosso cotidiano, tomamos decisões, fizemos análises e inferimos se</p><p>é verdadeiro ou falso. Utilizamos argumentos para defender o nosso ponto de vista.</p><p>Por exemplo, se ouvimos a mãe de Pedro, seu amigo, dizer que "Se Pedro for aprovado no</p><p>vestibular, ele terá um carro". E não seria nada estranho se ouvirmos alguém dizer que Pedro foi</p><p>aprovado no vestibular, já que se sabe que ele já possui o carro. Essa é a conclusão que a maioria</p><p>das pessoas chegaria, pois, se Pedro tem um carro, então Pedro teve aprovação no vestibular.</p><p>VEREMOS UM EXEMPLO PRÁTICO PARA PEDRO APÓS INGRESSAR NA UNIVERSIDADE!</p><p>Quando Pedro ingressa na universidade, toma conhecimento das regras de aprovação nas</p><p>disciplinas. Por exemplo, para aprovação, ele deverá ter média acima ou igual a 7 e frequência</p><p>maior ou igual a 75%; caso contrário, estará reprovado. Se Pedro frequentar todas as aulas, mas for</p><p>mal na avaliação e sua nota ficar abaixo de 7, ele poderá ter 100% de frequência e estará reprovado</p><p>mesmo assim. Se ele tirar nota 10 nas avaliações, mas não comparecer</p><p>às aulas, estará reprovado,</p><p>pois temos o operador “e”, que deve ter as duas proposições para fazer a aprovação (p: media maior</p><p>ou igual a 7; q: frequência maior ou igual a 75%) verdadeiras para que ele seja verdadeiro</p><p>(aprovado). Assim como essa, temos milhares de situações em que avaliamos expressões e temos o</p><p>resultado como verdadeiro ou falso.</p><p>Criando a tabela verdade para Pedro, tem-se:</p><p>22 = 4 linhas na tabela verdade</p><p>em que:</p><p>p: média de Pedro deve ser maior ou igual a 7</p><p>q: frequência de Pedro deve ser maior ou igual a 75%</p><p>Analisando a tabela verdade, percebe-se que a proposição somente será verdadeira (APROVADO)</p><p>quando a proposição q e a proposição p forem verdadeiras. Se uma for falsa, ou as duas, ele será</p><p>falso, OU SEJA, será reprovado.</p><p>V e V = V</p><p>V e F = F</p><p>F e V = F</p><p>F e F = F</p><p>Assim, Pedro somente terá aprovação se tiver média maior ou igual a 7 e frequência maior ou igual</p><p>a 75%.</p><p>JÁ IMAGINOU SE O CONECTIVO FOSSE “OU”, O QUE MUDARIA PARA PEDRO?</p><p>EM QUAIS SITUAÇÕES PEDRO ESTARIA APROVADO OU REPROVADO?</p><p>Saiba mais</p><p>Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professor:</p><p>Raciocínio lógico (proposição e tabela verdade) - conectivos</p><p>disjunção exclusiva e condicional.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>Raciocínio lógico (proposição e tabela verdade) - conectivos e,</p><p>ou.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>Raciocínio lógico (proposição e tabela verdade) - lógica</p><p>proposicional.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>Raciocínio lógico (proposição e tabela verdade) - negação de</p><p>preposição e tabela verdade.</p><p>https://www.youtube.com/embed/rjr-RqFM3uc</p><p>https://www.youtube.com/embed/DwfCk1lguTQ</p><p>https://www.youtube.com/embed/GlVa3RA9tKI</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>https://www.youtube.com/embed/6E9P-eVOVFA</p>