Tema 3 3 - Lógica Proposicional (Complemento)-Livro

Prévia do material em texto

<p>LÓGICA</p><p>COMPUTACIONAL</p><p>OBJETIVOS DE APRENDIZAGEM</p><p>> Definir lógica proposicional.</p><p>> Construir sentenças declarativas.</p><p>> Reconhecer a linguagem da lógica proposicional.</p><p>Introdução</p><p>A lógica computacional utiliza proposições para estruturar suas sentenças lógicas</p><p>e, com isso, conectivos lógicos podem ser utilizados a fim de testar expressões</p><p>lógicas. Para a construção de sentenças mais complexas, deve-se utilizar a lin-</p><p>guagem da lógica proposicional.</p><p>Neste capítulo, vamos apresentar a definição da lógica proposicional, de que</p><p>forma são construídas as sentenças declarativas e, por fim, utilizar as técnicas</p><p>da linguagem da lógica proposicional para fazer testes e gerar valores lógicos</p><p>em suas saídas.</p><p>Conceitos fundamentais</p><p>Ao trabalharmos com lógica, é necessário que tenhamos ferramentas para</p><p>poder expressar pensamentos mais complexos, e por isso utilizamos as pro-</p><p>posições. Mas de que se trata, de fato, uma proposição? Segundo o dicionário</p><p>Aurélio (FERREIRA, 2014), proposição é definida como o ato ou o efeito de</p><p>propor, como uma expressão verbal do pensamento e como máxima, sentença,</p><p>asserção. Já segundo Carnielli e Epstein (2006), trata-se de um conjunto de</p><p>palavras e de símbolos combinados no intuito de transmitir pensamentos</p><p>completos e não ambíguos, de forma que o resultado da sentença, após</p><p>Lógica proposicional</p><p>Sergio Eduardo Nunes</p><p>interpretada, retorne resultados VERDADEIRO ou FALSO. Para compreender</p><p>melhor, observe os exemplos a seguir.</p><p>� Brasília é a capital do Brasil.</p><p>� 10 < 4.</p><p>� Uva é uma fruta.</p><p>� 17 é um número ímpar.</p><p>Talvez você esteja questionando a segunda proposição, que afirma que o</p><p>número 10 é menor do que quatro. Porém, lembre-se de que os pensamentos</p><p>das sentenças proposicionais podem gerar VERDADEIRO ou FALSO. Nesse</p><p>exemplo, é gerado um valor FALSO.</p><p>Para deixar ainda mais claro, vejamos exemplos de expressões que não</p><p>são proposições.</p><p>� Ele caiu no balcão.</p><p>� Será divertido.</p><p>� O time perdeu.</p><p>Veja que são expressões ambíguas e que, portanto, não permitem retornar</p><p>VERDADEIRO ou FALSO.</p><p>Conforme defendem Carnielli e Epstein (2006), a lógica matemática e com-</p><p>putacional possui três princípios, conhecidos como axiomas (termo utilizado</p><p>por Aristóteles para a ciência do raciocínio lógico). Vejamos.</p><p>1. Princípio da identidade: se uma proposição é VERDADEIRA, ela será</p><p>VERDADEIRA. Podemos dizer que uma coisa é o que ela é e não se</p><p>confunde com qualquer outra.</p><p>2. Princípio de não contradição: uma proposição jamais poderá assumir</p><p>valores VERDADEIRO e FALSO ao mesmo tempo. Em outras palavras,</p><p>não é possível assumir dois estados ao mesmo tempo.</p><p>3. Princípio do terceiro excluído: a afirmação pode ser VERDADEIRA ou</p><p>sua negação é VERDADEIRA. Podemos compreender que uma expressão</p><p>será VERDADEIRA, e se sua negação resultar em VERDADEIRO, então</p><p>essa expressão é FALSA.</p><p>Outra característica da proposição é a utilização de letras para expres-</p><p>sar as proposições. Segundo Silva, Finger e Melo (2017), as proposições são</p><p>Lógica proposicional2</p><p>divididas em simples e complexas, e a representação por meio das letras foi</p><p>convencionada conforme pode ser observado a seguir.</p><p>� Proposição simples: não permite der subdividida em outras expressões.</p><p>Por exemplo, “João é careca”. As proposições simples são representadas</p><p>por letras latinas em caixa-baixa (minúsculas), iniciando pela letra “p”;</p><p>ou seja, são utilizadas as letras p, q, r, s, t, ..., z.</p><p>� Proposição complexa: são expressões formadas pela combinação</p><p>de duas ou mais proposições. Por exemplo, “João é careca e Paula é</p><p>gaúcha”. As proposições complexas utilizam as letras maiúsculas; ou</p><p>seja, P, Q, R, S, T, ..., Z.</p><p>Para melhor compreensão, observe o exemplo a seguir:</p><p>p: Hoje eu vou para a faculdade.</p><p>q: Se chover, então irei ao cinema.</p><p>P: Hoje eu vou para a faculdade; se chover, então irei ao cinema.</p><p>Nesse exemplo, foram declaradas duas proposições simples: p e q. A</p><p>partir das duas proposições simples, foi formada uma proposição composta:</p><p>P. Essa expressão P também é conhecida como fórmula proposicional. Você</p><p>percebeu que, para as duas proposições simples serem combinadas em uma</p><p>composta, foi necessário fazer uma conexão? Isso foi feito pela partícula SE,</p><p>que atua, portanto, como conectivo.</p><p>Conforme afirmam Silva, Finger e Melo (2017), os conectivos são palavras</p><p>utilizadas para formar novas proposições a partir de outras. Conforme o</p><p>dicionário Aurélio (FERREIRA, 2014), o termo conectivo é o que liga ou une,</p><p>um vocábulo que estabelece conexão entre palavras ou entre partes de uma</p><p>frase. Carnielli e Epstein (2006) determinam que os conectivos utilizados nas</p><p>expressões da lógica matemática e computacional são os seguintes.</p><p>� NÃO: utilizado para negar uma expressão proposicional. Por exemplo:</p><p>“O sol é uma estrela; o sol NÃO é uma estrela”.</p><p>� E: também conhecido como conjunção, é utilizado para realizar a co-</p><p>nexão entre duas proposições. Por exemplo: “O número 20 é par E o</p><p>número 13 é ímpar”.</p><p>� OU: utilizado para expressar uma disjunção entre as proposições sim-</p><p>ples. Por exemplo: “No aniversário, eu vou comer doce OU salgado”.</p><p>Lógica proposicional 3</p><p>� SE... ENTÃO: expressa uma condição para que algo ocorra ou não. Por</p><p>exemplo: “SE Iago é cozinheiro, ENTÃO sabe fazer macarrão”.</p><p>� SE E SOMENTE SE: trata-se de uma condição que expressa uma condição</p><p>única de determinada ocorrência. Por exemplo: “Portugal é na Europa</p><p>SE E SOMENTE SE O Sol é uma estrela”.</p><p>Para facilitar a escrita de uma proposição complexa, são utilizados sím-</p><p>bolos. Para expressar os conectivos na lógica matemática e computacional,</p><p>são utilizados os símbolos demonstrados no Quadro 1.</p><p>Quadro 1. Símbolos utilizados para expressar os conectivos lógicos</p><p>Conectivo Símbolo</p><p>NÃO ~</p><p>E ^</p><p>OU v</p><p>SE... ENTÃO →</p><p>SE E SOMENTE SE ↔</p><p>Fonte: Adaptado de Alencar Filho (2002, p. 75).</p><p>Construção de sentenças declarativas</p><p>Agora que você já reconhece os tipos de proposições e os conectivos lógicos,</p><p>é possível avançarmos na construção de sentenças. O intuito, nesse mo-</p><p>mento, é utilizar expressões literais, letras e símbolos, de forma a construir</p><p>as expressões proposicionais.</p><p>Segundo Carnielli e Epstein (2006), a construção das sentenças decla-</p><p>rativas, em que são utilizadas as técnicas e demais ferramentas da lógica</p><p>matemática computacional, demanda atenção a algumas regras, pontuadas</p><p>a seguir.</p><p>� São utilizados símbolos proposicionais (letras minúsculas) para a</p><p>expressão das proposições simples.</p><p>� Podem ser utilizados mais de um conector lógico em uma mesma</p><p>proposição complexa.</p><p>Lógica proposicional4</p><p>� Os parênteses priorizam as proposições em seu interior.</p><p>� Uma fórmula proposicional é composta por afirmações lógicas e co-</p><p>nectivos lógicos.</p><p>A compreensão do raciocínio lógico em que sejam utilizados textos</p><p>(expressões) é uma forma de construir expressões lógicas. Digite,</p><p>em seu motor de busca preferido, “Raciocínio lógico na compreensão de texto”</p><p>para ter acesso a artigo de mesmo nome que demonstra como as sentenças</p><p>são tratadas com as proposições.</p><p>Para que você possa compreender como é efetuada a construção das</p><p>sentenças, observe, abaixo, os exemplos com cada um dos conectivos lógicos.</p><p>1. Conectivo NÃO: a negação de uma proposição é conhecida por um</p><p>~p (deve ser lido como “não p”). Sempre que uma afirmativa for VER-</p><p>DADEIRA, sua negação resultará em uma afirmação FALSA; quando</p><p>uma afirmativa for FALSA, sua negação resultará em uma afirmação</p><p>VERDADEIRA. Acompanhe o exemplo a seguir.</p><p>p: Mateus é jogador de futebol.</p><p>~p: NÃO é verdade que Mateus é jogador de futebol.</p><p>Outra forma de expressar uma negação pode ser observada a seguir.</p><p>~p: É FALSO que Mateus é jogador de futebol.</p><p>2. Conectivo E: trata-se da conjunção de duas proposições p E q, em que o</p><p>resultado sempre será VERDADEIRO quando as proposições p E q forem</p><p>verdadeiras; caso contrário, será FALSA. Observe os exemplos a seguir.</p><p>p: A terra é redonda.</p><p>q: 3 < 15.</p><p>p ^ q: A terra é redonda E 3 < 15, sendo essa sentença VERDADEIRA.</p><p>r: O sol é verde.</p><p>s: Uruguai fica na América do Sul.</p><p>r ^ s: O sol é verde E o Uruguai fica na América</p><p>do Sul, sendo essa sentença FALSA.</p><p>Para que você entenda melhor o conectivo E, observe a Figura 1.</p><p>Lógica proposicional 5</p><p>Figura 1. Diagrama de Venn para o E lógico.</p><p>3. Conectivo OU: efetua a disjunção de duas proposições p OU q. O valor</p><p>lógico gerado será VERDADEIRO quando uma das proposições forem</p><p>verdadeiras. Caso uma das proposições for falsa, então o valor lógico</p><p>gerado será FALSO. Para compreender melhor, observe os exemplos</p><p>a seguir.</p><p>p: Tóquio é a capital da Bolívia.</p><p>q: 0,595 é um número inteiro.</p><p>p v q: Tóquio é a capital da Bolívia OU 0,595 é um número</p><p>inteiro, pois ambas as afirmações são FALSAS.</p><p>r: A água do mar é doce.</p><p>s: 5 + 7 = 12.</p><p>r v s: A água do mar é doce OU 5 + 7 = 12, pois, no caso, a primeira</p><p>afirmação é FALSA e a segunda é VERDADEIRA (uma delas sendo</p><p>VERDADEIRA basta para validar a relação entre as afirmativas).</p><p>4. Conectivo SE... ENTÃO: trata-se de uma proposição para condicionais.</p><p>Lê-se “SE p ENTÃO q”. O valor lógico gerado somente será FALSO se p</p><p>VERDADEIRO e q FALSO; nos demais casos, será sempre VERDADEIRO.</p><p>Observe alguns exemplos.</p><p>p: O ano tem 12 meses.</p><p>q: São Paulo fica no Sul.</p><p>p → q: SE o ano tem 12 meses, ENTÂO São Paulo</p><p>fica no Sul, pois essa sentença FALSA.</p><p>r: 2 é um número real.</p><p>s: Pizza é um alimento.</p><p>r → s: SE 2 é um número real, ENTÂO pizza é um</p><p>alimento, pois essa sentença é VERDADEIRA.</p><p>Lógica proposicional6</p><p>5. Conectivo SE E SOMENTE SE: trata-se de uma bicondicional e deve ser</p><p>lida como “p SE E SOMENTE SE q”. O valor lógico gerado será VERDADEIRO</p><p>quando ambas as sentenças p e q forem verdadeiras ou quando ambas</p><p>forem falsas. Nos demais casos, será sempre FALSO.</p><p>p: Python é uma linguagem de programação.</p><p>q: MySQL é um sistema de gerenciamento de banco de dados.</p><p>p ↔ q: Python é uma linguagem de programação SE E</p><p>SOMENTE SE MySQL é um sistema de gerenciamento de</p><p>banco de dados., sendo essa sentença VERDADEIRA.</p><p>r: 4 é um número par.</p><p>s: 5 / 3 = 3.</p><p>r ↔ s: 4 é um número par SE E SOMENTE SE 5 /</p><p>3 = 3, sendo essa sentença FALSA.</p><p>Você percebeu como são feitas as construções das sentenças declarati-</p><p>vas? Porém, não é muito viável utilizarmos as sentenças para fazer os testes</p><p>lógicos. Isso porque, conforme formos evoluindo nos estudos acerca da</p><p>lógica computacional, carregar frases inteiras e fazer a junção com símbolos</p><p>pode tornar o trabalho muito complicado. Para resolver essa questão, vamos</p><p>compreender como utilizar a linguagem da lógica proposicional.</p><p>Linguagem da lógica proposicional</p><p>Agora que você sabe como as sentenças são construídas, podemos começar a</p><p>substituir as sentenças por letras e, assim, tornar a análise mais simplificada.</p><p>O que faremos, agora, é utilizar simbolismos para criar expressões lógicas, mas</p><p>ainda com a utilização das sentenças para a determinação de seu valor lógico.</p><p>Segundo Souza (2008), a linguagem da lógica proposicional se trata de uma</p><p>linguagem com regras específicas que utiliza as variáveis proposicionais e os</p><p>conectivos lógicos para formar expressões. A fim de se reforçar alguns pontos</p><p>da linguagem lógica proposicional, vejamos algumas de suas características.</p><p>� Uma expressão p conectivo q pode ser representada por uma propo-</p><p>sição composta P.</p><p>� Uma proposição composta P pode fazer parte de uma expressão lógica</p><p>P conectivo Q.</p><p>Lógica proposicional 7</p><p>� Sentenças com mais de um conectivo lógico devem observar a seguinte</p><p>ordem de precedência.</p><p>■ Maior precedência: ~ (NÃO).</p><p>■ Precedência intermediária:^ (E), v (OU).</p><p>■ Menor precedência: →(SE... ENTÃO), ↔ (SE E SOMENTE SE).</p><p>Caso os operadores sejam de mesmo nível de precedência, ou iguais, a</p><p>ordem de precedência segue da esquerda para a direita.</p><p>Na construção das expressões por meio da linguagem da lógica</p><p>proposicional, as ordens de precedência dos conectivos lógicos</p><p>podem interferir no resultado. Por exemplo, p: V, q: V, r: F. Para resolver P: p q</p><p>^ r, deve-se fazer primeiro o q ^ r, e p com o resultado gerado. Dessa forma:</p><p>P: V V ^ F</p><p>P: V V</p><p>P: V</p><p>Agora, se erroneamente foram resolvidas as expressões da esquerda para</p><p>a direita, o resultado gerado será:</p><p>P: V V ^ F</p><p>P: V ^ F</p><p>P: F</p><p>Com isso, para que você compreenda como é utilizada a linguagem da</p><p>lógica proposicional, acompanhe os exemplos a seguir. Para tal, considere</p><p>as proposições simples:</p><p>p: 3 × 5 = 15</p><p>q: 9 / 3 < 2</p><p>r: 14 – 9 = 4</p><p>s: 7 × 7 = 72</p><p>Lógica proposicional8</p><p>Com base nas proposições simples e com o uso da linguagem lógica pro-</p><p>posicional, observe a seguir.</p><p>P: (p v q) ^ ~ r</p><p>Para que isso seja resolvido, vamos, primeiramente, verificar os valores</p><p>lógicos gerados pelas proposições p, q e r:</p><p>p: 3 × 5 = 15. VERDADEIRO</p><p>q: 9 / 3 < 2. FALSO</p><p>r: 14 – 9 = 4. FALSO</p><p>s: 7 × 7 = 72. VERDADEIRO</p><p>Dessa forma, a expressão gerada será:</p><p>P: (VERDAVEIRO v FALSO) ^ ~ FALSO</p><p>P: (VERDADEIRO) ^ VERDADEIRO</p><p>P: VERDADEIRO ^ VERDADEIRO</p><p>P: VERDADEIRO</p><p>Repare que, inicialmente, foi resolvido o teste lógico dentro dos parênteses</p><p>e, na mesma linha, foi resolvido o NÃO lógico; por fim, o teste com o E lógico.</p><p>Para simplificarmos ainda mais, vamos substituir o valor lógico VERDADEIRO</p><p>por V e o valor lógico FALSO por F. Com isso, ainda utilizando as proposições</p><p>simples p, q, r e s, vamos utilizar a linguagem lógica proposicional para mais</p><p>um teste, conforme pode ser observado a seguir.</p><p>P: (s → r)</p><p>Q: (p ↔ q)</p><p>R: Q v ~ P</p><p>Dessa forma, vamos resolver as proposições complexas em separado:</p><p>P: (V → F)</p><p>P: F</p><p>Q: (V ↔ F)</p><p>Q: F</p><p>Lógica proposicional 9</p><p>R: Q v ~ P</p><p>R: F v ~ F</p><p>R: F v V</p><p>R: V</p><p>Portanto, a expressão R: Q v ~ P vai gerar um valor lógico VERDADEIRO.</p><p>A linguagem lógica proposicional é uma ferramenta computacio-</p><p>nal muito aplicada no desenvolvimento de sistemas. Vamos, neste</p><p>exemplo, compreender como ocorre essa relação.</p><p>Determinado programa deve verificar três parâmetros: se o cliente é asso-</p><p>ciado, se possui mais de 60 anos e se a mensalidade está em dia. Se tudo for</p><p>atendido, o desconto será concedido. Para isso, vamos construir um caso com</p><p>determinado cliente:</p><p>p: João é um associado.</p><p>q: João tem 62 anos.</p><p>r: João está com todas as mensalidades em dia.</p><p>s: João terá um desconto de 50%.</p><p>P: (p ^ q ^ r) → s</p><p>Dessa forma, vamos analisar se ele atende aos requisitos nas proposições</p><p>para gerar os valores lógicos:</p><p>p: João é um associado. VERDADEIRO.</p><p>q: João tem 62 anos. VERDADEIRO.</p><p>r: João está com todas as mensalidades em dia. VERDADEIRO.</p><p>s: João terá um desconto de 50%. VERDADEIRO.</p><p>Com isso:</p><p>P: (p ^ q ^ r) → s</p><p>P: (V ^ V ^ V) → V</p><p>P: (V ^ V) → V</p><p>P: V → V</p><p>P: V</p><p>Dessa forma, o programa vai retornar VERDADEIRO, pois o cliente atende a</p><p>todos os requisitos.</p><p>Lógica proposicional10</p><p>Percebeu como a linguagem da lógica proposicional é altamente aplicável</p><p>na área de desenvolvimento? Essa ferramenta da lógica computacional possui</p><p>diversas aplicabilidades e visa facilitar a construção dos algoritmos.</p><p>Referências</p><p>ALENCAR FILHO, E. de. Iniciação à lógica matemática. 2. ed. São Paulo: Nobel, 2002.</p><p>CARNIELLI, W.; EPSTEIN, R. L. Computabilidade, funções computáveis, lógica e os fun-</p><p>damentos matemáticos. São Paulo: UNESP, 2006.</p><p>FERREIRA, A. B. de H. Mini Aurélio: o mini dicionário da língua portuguesa. 8. ed. Rio</p><p>de Janeiro: Positivo, 2014.</p><p>SILVA, F. S. C. da; FINGER, M.; MELO, A. C. V. de. Lógica para computação. 2. ed. São Paulo:</p><p>Cengage Learning, 2017.</p><p>SOUZA, J. N. de. Lógica para ciência da computação: uma instrução concisa. 2ª Ed. – Rio</p><p>de Janeiro: Elsevier, 2008.</p><p>Leitura recomendada</p><p>TASINAFFO, P. M. Um breve histórico do desenvolvimento da lógica matemática e o</p><p>surgimento da teoria da computação. In: ENCONTRO DE INICIAÇÃO CIENTÍFICA E PÓS-</p><p>-GRADUAÇÃO DO ITA, 14., 2008, São José dos Campos. Anais eletrônicos [...]. Disponível</p><p>em: http://www.bibl.ita.br/xivencita/COMP07.pdf. Acesso em: 17 dez. 2020.</p><p>Os links para sites da web fornecidos neste capítulo foram todos</p><p>testados, e seu funcionamento foi comprovado no momento da</p><p>publicação do material.</p><p>No entanto, a rede é extremamente dinâmica; suas</p><p>páginas estão constantemente mudando de local e conteúdo. Assim, os editores</p><p>declaram não ter qualquer responsabilidade sobre qualidade, precisão ou</p><p>integralidade das informações referidas em tais links.</p><p>Lógica proposicional 11</p>