Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 franciscogerson10@gmail.com – www.piracuruca.com/profgerson CEFET - UNED - PHB Introdução a Ciência da Computação Unidade IV – Lógica, a Arte de Pensar Prof. Francisco Gerson A. de Meneses Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Conteúdo programático - Introdução - Álgebra Booleana - Operador Lógico “e” (Conjunção) - Operador Lógico “ou” (Disjunção) - Operador Lógico “não” (Negação) - Projeto de Circuitos - Hardware - Portas Lógicas - Lógica de Programação - Software - Operadores Lógicos - Operadores Relacionais - Prioridades - Refinamento de Algoritmos Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Introdução Sendo a lógica um estilo de raciocínio, é possível compará-la com uma arte, a arte de pensar, sem que para isso seja necessário ser um filósofo. A lógica está muito relacionada com o pensamento e estamos interessados em como é possível fazer a máquina “pensar”. Como sabemos, essas máquinas, os computadores digitais binários são projetados para armazenar e manipular informações representadas apenas por dois algarismos ou dígitos distintos, 0 e 1. Obs: como na prática não há máquinas digitais não-binárias, é mais usual simplificar-se o termo computador digital binário, usando apenas o termo computador digital. Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Introdução Em um sistema de computação, uma operação lógica é obtida através da analogia que se faz do 0 e do 1 com: “falso e verdadeiro” ou “fechado e aberto” ou “não e sim” ou “baixo e alto” ou ainda “desligado e ligado”, etc. resolvendo problemas através de um conjunto de várias pequenas operações que juntas proporcionam uma solução para uma determinada necessidade. A lógica é de suma importância para a ciência da computação tanto no aspecto de hardwarehardware através dos projetos de circuitos e suas portas lógicas, como no aspecto do softwaresoftware onde é usada na codificação de programas. Tais fundamentos são baseados em estudos realizados pelo matemático inglês George Boole. Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Álgebra Booleana Álgebra Booleana é uma área da matemática que trata de regras e elementos de lógica. O nome “booleana” é uma retribuição da comunidade científica ao matemático inglês George Boole (1815 - 1864), que desenvolveu uma análise matemática sobre a Lógica e em 1854 publicou um livro no qual propôs os princípios básicos dessa álgebra. Tais princípios baseiam-se em um sistema de álgebra (álgebra das proposições) onde se pode determinar se uma sentença é falsa ou verdadeira utilizando-se para isso as funções ou operadores lógicos: E, OU e NÃO (AND, OR, NOT). Assim: Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Álgebra Booleana Chamaremos qualquer afirmação verbal que possamos dizer se é falsa ou verdadeira (nunca ambas) em proposição. Assim, “choveu ontem à tarde” é um proposição (pode ser falsa ou verdadeira). Porém algumas proposições são compostas de subproposições ligadas por conectivos, no nosso caso representado pelos operadores lógicos: e, ou e não. No caso dessas proposições, o operador lógico usado é que definirá o valor lógico (se verdadeiro ou falso). Vejamos cada um deles: 2 Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Álgebra Booleana Conjunção: Duas proposições podem ser combinadas pelo conectivo “e” para formar uma proposição chamada conjunção das proposições originais. A conjunção das proposições A e B representaremos por: A Λ B (leia-se por A e B). Sejam as proposições: p: Paris está na França q: Paris está na Inglaterra r: 2+2=5 s: 2+2=4 Considerando que a conjunção exige que as duas subproposições sejam verdadeiras para o conjunto ser verdadeiro teremos: Esse operador pode ser representado por AND (representado pelo ponto, “.” da multiplicação aritmética). Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Álgebra Booleana Conjunção: p: Paris está na França q: Paris está na Inglaterra r: 2+2=5 s: 2+2=4 Qual o valor lógico das conjunções? p Λ s = p Λ r = q Λ s = q Λ r = verdadeiro falso falso falso Uma conjunção só será verdadeira se todas as subproposições forem verdadeiras. Um meio conveniente de estabelecer esta conclusão é a utilização de uma tabela verdade (exemplo a e b): FFF FVF FFV VVV a Λ bba Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Álgebra Booleana Disjunção: Duas proposições quaisquer podem ser combinadas com o conectivo “ou” (com sentido de e/ou) para formar uma nova proposição que é chamada de disjunção das duas proposições originais. Designaremos a disjunção de duas proposições A e B por: A V B (leia-se por A ou B). Sejam as proposições: p: Paris está na França q: Paris está na Inglaterra r: 2+2=5 s: 2+2=4 Considerando que na disjunção podemos considerar verdadeira a proposição que contiver pelo menos uma subproposição verdadeira teremos: Esse operador pode ser representado por OR (representado pelo sinal, “+” da adição aritmética). Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Álgebra Booleana Disjunção: p: Paris está na França q: Paris está na Inglaterra r: 2+2=5 s: 2+2=4 Qual o valor lógico das disjunções? p V s = p V r = q V s = q V r = verdadeiro verdadeiro verdadeiro falso Uma disjunção será verdadeira se pelo menos uma das subproposições forem verdadeiras. Um meio conveniente de estabelecer esta conclusão é a utilização de uma tabela verdade (exemplo a e b): FFF VVF VFV VVV a V bba Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Álgebra Booleana Negação: Dada um proposição A qualquer, uma outra proposição, chamada negação de A pode ser formada escrevendo-se: “É falso que...” antes de A ou, se possível, inserindo a palavra “não” em A. Simbolicamente designaremos a negação por: ¬ A (leia-se por não A). Seja a proposição: p: Paris está na França Concluímos que: se p é verdadeiro então ¬ p é falsa; se p é falso então ¬ p é verdadeiro: Esse operador pode ser representado por NOT (representado por uma barra em cima da variável “Ā” ou por apóstrofo à direita da variável A'). Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Álgebra Booleana Negação: p: Paris está na França Qual o valor lógico da negação? ¬ p = falso Utilizando a tabela verdade temos: VF FV ¬ pp 3 Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Álgebra Booleana Exercício 1: Usando a convenção: 1 para verdadeiro e 0 para falso, complete as linhas da tabela abaixo com o valor verdade correspondente: 0 p Λ ( ¬ q ) 00 10 01 11 ¬ ( p Λ ¬ q )qp 1 0 0 1 0 1 1 Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Álgebra Booleana Exercício 2: Seja p= “Ela é alta” e seja q= “Ela é elegante”: Escreva cada uma das proposições abaixo na forma simbólica usando p e q: a-) Ela é alta e elegante p Λ q b-) Ela é alta mas não é elegante p Λ ¬ q c-) É falso que ela é baixa ou elegante ¬ (¬ p V q) d-) Ela não é alta nem elegante ¬(p Λ q) e-) Ela é alta, ou ela é baixa e elegante p V (¬p Λ q) f-) Não é verdade que ela é baixa e não é elegante ¬(¬p Λ ¬q) Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Projeto de Circuitos -Hardware A analogia existente entre a álgebra das proposições e as chaves elétricas será vista a seguir: Considere os circuitos abaixo. Em cada caso, quando é que a lâmpada ficará acesa? Observa-se que em cada circuito tem-se dois interruptores. a) Circuito em série b) Circuito em paralelo Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Projeto de Circuitos - Hardware Seja A e B interruptores elétricos. No caso (a – circuito em série) a lâmpada só ficará acesa no caso dos dois interruptores A e B estarem ligados. No caso (b – circuito em paralelo) a lâmpada ficará acesa se pelo menos um dos interruptores A e B estiver ligado. Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Projeto de Circuitos - Hardware Portanto: A Λ B (conjunção) designa um circuito ligado em série e A V B (disjunção) designa um circuito ligado em paralelo Sendo assim, um circuito elétrico significa, portanto, um arranjo de fios e interruptores que pode ser montado com o uso repetitivo de combinações em série e paralelo. Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Projeto de Circuitos - Hardware Exercício 3: Descreva os circuitos abaixo usando expressões: a) b) A Λ (B V A') Λ C A Λ (C V B') V (B Λ C') 4 Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Projeto de Circuitos - Hardware Exercício 4: Construa um circuito correspondente às expressões: a) b) (A Λ B) V (A' Λ (B' V A V B)) (A V B) Λ C Λ (A' V B' V C ') Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Projeto de Circuitos - Hardware Portas Lógicas: Um porta lógica (gate) é um circuito eletrônico, portanto uma peça de hardware, que se constitui no elemento básico e mais elementar de um sistema de computação. Grande parte do hardware do sistema é fabricado através da adequada combinação de milhões desses elementos, como a UCP, memórias principal e cache, interfaces de E/S e outros. Há diversos tipos bem definidos de portas lógicas, cada uma delas capaz de implementar uma operação ou função lógica específica. Uma operação lógica realizada sobre um ou mais valores lógicos produz um certo resultado (valor lógico), conforme a regra definida para a específica operação lógica. Assim como na álgebra comum, é necessário definir símbolos matemáticos e gráficos para representar as operações lógicas (portas). Vejamos: Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Projeto de Circuitos - Hardware Abaixo, a representação de um conjunto de portas básicas, capazes de implementar as três operações E, OU e NÃO: • A porta E tem duas ou mais entradas e a saída assume o valor 1 se e somente se todas as entradas são 1; logo se as entradas são a e b a saída será: a . b • A porta OU tem duas ou mais entradas e a saída será 1 se uma ou mais de uma entrada for igual a 1; logo as entradas são a e b a saída será: a + b • A porta NÃO só tem uma entrada e sua saída é 1 se a entrada é 0 e será 0 se a entrada é 1; logo se a entrada é: a a saída será a' Observe a equivalência da representação dos conectivos: . Λ E + V OU ' ¬ NÃO Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Projeto de Circuitos - Hardware Exemplo: A função A = T . (H + W) + W' . P está representada abaixo: A = T . (H + W) + W' . P Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Projeto de Circuitos - Hardware Exercício 5: Descreva os circuitos abaixo usando expressões: x . y' + (x'+ z') . z Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Projeto de Circuitos - Hardware Exercício 6: Descreva os circuitos abaixo usando expressões: x . y' + x'. z 5 Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação A lógica de programação propriamente dita dividi-se em quatro partes, a saber: Ação: é um acontecimento que, a partir de um estado inicial, após um determinado período, produz um resultado previsível e bem definido, com o objetivo de obter a solução de parte de um problema. Por exemplo, pode-se dizer que os passos constantes de uma receita de bolo são definidos como estão. Algoritmo: é a descrição de um conjunto de ações que, obedecidas, resulta num programa. Um exemplo bastante comum de algoritmo é a receita de um bolo, em que as ações necessárias para a execução do objetivo final estão descritas passo a passo de forma objetiva. Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Diagrama de blocos: é a representação gráfica de um algoritmo. Tem como objetivo representar por meio de sinais padronizados o desenho de forma de raciocínio utilizada para a solução do problema computacional por meio do algoritmo. Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Codificação: é a tradução de um fluxograma ou de um algoritmo para uma determinada linguagem de programação. Assim como existe no mundo várias línguas para as pessoas se comunicarem, também ocorre com os computadores que passaram a conversar em diversas linguagens. Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Nos códigos de um programa os operadores lógicos ou operadores booleanos são aplicados no tratamento e recuperação da informação, isso, independente do sistema ou linguagem utilizada. Esses operadores permitem a expressão de forma explícita e a relação dos termos entre si. Trecho de código em JAVA Corresponde ao operador lógico “e” Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Operadores LOperadores Lóógicosgicos Eles são também conhecidos como operadores booleanos. Os tipos de operadores lógicos mais utilizados são: .e.; .ou.; .não. e .xou. Quando representamos em português estruturado sempre estarão entre pontos. Assim temos: Vejamos cada um deles: Disjunção (exclusiva).xou. Negação.não. Disjunção (não exclusiva).ou. Conjunção.e. Funções exercidasSímbolos Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Operador LOperador Lóógico:gico: .e..e. Utilizado quando dois ou mais relacionamentos lógicos de uma determinada condição necessitam ser verdadeiros. Observe o diagrama de blocos, como a utilização do operador lógico .e. é apresentada: 6 Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Operador LOperador Lóógico:gico: .ou..ou. Utilizado quando pelo menos um dos relacionamentos lógicos (quando houver mais de um relacionamento) de uma condição necessitar ser verdadeiro. Observe o diagrama de blocos, como a utilização do operador lógico .ou. é apresentada: Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Operador LOperador Lóógico:gico: .não..não. Utilizado quando é necessário estabelecer que uma determinada condição não deve ser verdadeira. Mesmo quando uma for verdadeira, ela será entendida como falsa. Se a condição for falsa será entendida como verdadeira. Observe o diagrama de blocos, como a utilização do operador lógico .não. é apresentada: Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de ProgramaçãoOperador LOperador Lóógico:gico: ..xouxou.. É utilizado quando apenas um dos relacionamentos de uma condição for verdadeiro, ou seja, a outra condição é excluída. A tabela verdade que segue ilustra essa situação: Verdadeira Verdadeira Falsa Falsa Condição 2 FalsoVerdadeira VerdadeiroFalsa VerdadeiroVerdadeira FalsoFalsa ResultudoCondição 1 Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Operador LOperador Lóógico:gico: ..xouxou.. Observe o diagrama de blocos, como a utilização do operador lógico .xou. é apresentada: Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Operador Relacionais:Operador Relacionais: São utilizados para estabelecer relações entre dois valores de mesmo tipo. Esses valores podem ser representados por variáveis, constantes ou expressões aritméticas. A tabela que segue mostra os operadores relacionais: Observe os exemplos que seguem: <= menor ou igual >= maior ou igual a <> diferente de < menor que > maior que = igual a Operadores relacionais Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Operador Relacionais:Operador Relacionais: Exemplos do uso de operadores relacionais em expressões lógicas: a-) 3 X 5 = 30 : 2, em que 15 = 15 verdadeiro b-) 20 : 5 < 9 : 3, em que 4 < 3 falso c-) 3 + (15:3) <= 23 + 8 em que 8 <= 16 verdadeiro 7 Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Operador Relacionais:Operador Relacionais: Em processamento de dados, os sinais matemáticos usados para realizar as quatro operações são diferentes em alguns casos. Veja a tabela: Assim sendo, as expressões anteriormente mostradas passam a ter a seguinte configuração: a-) 3 x 5 = 30 : 2 fica assim: 3 * 5 = 30 / 2 b-) 20 : 5 < 9 : 3 fica assim: 20 / 5 < 9 / 3 c-) 3 + (15 : 3) <= 23 + 8 fica assim: 3 + (15 / 3 ) <= 2 Ç 3 + 8 - Ö subtração- Ö subtração + Ö adição+ Ö adição / Ö divisão: Ö divisão * Ö multiplicação Ç Ö exponenciação (seta para cima) Processamento de dados X Ö multuplicação NeÖ exponenciação Matemática Operadores aritméticos Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Prioridades:Prioridades: Expressões algébricas: Os operadores aritméticos possuem uma hierarquia, isto é, primeiramente resolve-se a exponenciação, depois a multiplicação/divisão, adição e subtração, respectivamente, a não ser que se queira priorizar um dos operandos cuja hierarquia deve ser alterada, neste caso, colocam-se os parênteses, depois os colchetes e as chaves respectivamente. Exemplos: a) 5 + 3 * 7 = 26 b) (5 + 3) * 7 = 56 Expressões lógicas: Os operadores lógicos também possuem uma hierarquia. Primeiro resolvem-se os operadores lógicos que se encontram à esquerda e posteriormente os da direita, assim temos respectivamente: .não.; .e./.ou. e finalmente o .xou. Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Exercício 7: Determine a resultado lógico das expressões que seguem, assinalando se verdadeiro ou falso, considerando que: X = 2 , A = 5 , B = 3 , C = 7 , D = 9. a-) .não. (X>5) ( ) verdadeiro ( ) falso b-) (X<1) .e. .não. (B>D) ( ) verdadeiro ( ) falso c-) (A>B) .ou. (C>B) ( ) verdadeiro ( ) falso d-) (X>=3) ( ) verdadeiro ( ) falso e-) (A<B) .xou. (C>B) ( ) verdadeiro ( ) falso f-) (11>D) .xou. (3<A) ( ) verdadeiro ( ) falso X X X X X X Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Refinamento de Algoritmos:Refinamento de Algoritmos: Um algoritmo é considerado completo quando o destinatário consegue entender as ações nele descritas. Quando ocorrer o fato de um comando não ser do entendimento do destinatário, esse comando deve ser desdobrado em novos comando. Esse processo denomina- se refinamento. Observa-se nesse momento que, após ter analisado o problema de forma global, efetua-se a análise dos seus detalhes, quebrando-o em algumas partes. Cada uma dessas partes pode ser dividida em outras e assim sucessivamente até chegar a um nível mínimo de divisão. Como exemplo desse conceito, observe o problema descrito em seguida: Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Refinamento de Algoritmos:Refinamento de Algoritmos: Elaborar um algoritmo que descreva os passos para que uma pessoa possa embarcar em um ônibus, até o momento de pagar a passagem e ultrapassar a catraca, considerando que ela já esteja no ponto. 1 – visualizar o ônibus que se aproxima. 2 – dar o sinal. 3 – entrar no ônibus. 4 – ir até a catraca. 5 – pagar a passagem 6 – ultrapassar a catraca Nesse exemplo, o problema foi analisado de forma global. Não foram levados em consideração os seguintes aspectos: se o ônibus é o desejado, se a entrada é pela frente ou por trás, se o passageiro estava com o dinheiro na mão, e outros. Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Lógica de Programação Refinamento de Algoritmos:Refinamento de Algoritmos: Nesse caso é necessário efetuar o refinamento do algoritmo, tornando-o mais detalhado e, dessa forma mais eficiente, conforme o que segue: 1 – visualizar o ônibus que se aproxima. 2 – dar o sinal se for o ônibus desejado. 3 – verificar a porta de entrada. 4 – ir até a catraca. 5 – pagar a passagem caso o dinheiro esteja à mão; caso contrário retirá-lo da carteira. 6 – ultrapassar a catraca. Caso o ônibus visualizado não seja o desejado, aguardar o próximo, seguindo instruções a partir do passo 1. 8 Prof. Francisco Gerson A. de Meneses www.piracuruca.com/profgerson CEFET - UNED - PHB Bibliografia GUIMARÃES, Ângelo M; LAGES, Newton A. C.; Introdução a Ciência da Computação. LTC – Livros Técnicos e Científicos. Edição Atualizada. MANZANO, M. I. N. G. & MANZANO, A. L. N.G. Estudo Dirigido de Informática Básica. Érica, 7ª Edição, 2007. Monteiro, Mário A. – Introdução à Organização de Computadores – 4ª Edição – Editora LTC Pesquisas na WEB Notas de aula
Compartilhar