Unidade I Aulas 02.pdf

Prévia do material em texto

Lógica para Computação 
Unidade I – Aula 02 
Profª MSc. Patricia Medyna Lauritzen de Lucena Drumond 
patriciamedyna@ufpi.edu.br 
Universidade Federal do Piauí 
Centro de Ensino Aberto e a Distância 
Curso de Sistemas de Informação 
Aula 02 
 
Conectivos e reescrita das 
sentenças 
Conectivos lógicos 
 Um conectivo é uma expressão de uma dada linguagem, 
utilizada para formar sentenças a partir de sentenças 
dadas. Os conectivos utilizados na lógica são os 
seguintes: 
 
– Não ou NOT (negação) 
– E ou AND (conjunção) 
– OU ou OR (disjunção) 
– Se ... Então (implicação) 
– Se e somente se (biimplicação) 
 
Conectivo Não (¬) 
 Essa expressão prefixa uma sentença para formar uma 
nova sentença, a negação da primeira. 
 
Exemplo: ‘Não é o caso que ele é fumante‘ 
 é a negação da sentença 
 ‘Ele é fumante'. 
 
 Variações gramaticais dessa negação: 
 ´Ele é não-fumante’, 
 ´Ele não é fumante’ 
 ´Ele não fuma’. 
Conectivo E () 
 Uma composição constituindo-se de duas sentenças 
ligadas por 'e' chama-se conjunção. 
 Exemplo: Chove e faz calor 
 
 Obs: em linguagem natural, ‘e’ às vezes sugere sequencia 
temporal 
 Ele ganhou na loto e enriqueceu. 
 
 A conjunção também pode ser expressa por palavras 
como: 'mas', 'todavia', 'embora', 'contudo', ‘além do 
mais’, ‘no entanto’, ‘apesar disso’... 
 Chove mas faz calor 
 
Conectivo Ou () 
 Um enunciado composto consistindo de duas sentenças 
ligadas por 'ou' chama-se disjunção. 
 
 Exemplo: Chove ou faz calor 
 
Conectivo Se ... então... () 
 Enunciados do tipo se... então ... chamam-se condicionais 
ou implicações . 
 
 O enunciado subsequente ao 'se' chama-se o antecedente 
e o subsequente ao 'então' chama-se o consequente. 
 
 Forma do condicional: 
 Se antecedente então consequente 
 Ex: Se sinto frio então visto o casaco 
Conectivo Se ... então... () 
 Uma implicação também pode ser expressa na ordem 
inversa. 
 
 Visto o casaco se sentir frio 
 
 mantém a semântica de 
 
 Se sentir frio, visto o casaco 
 Se sentir frio então visto o casaco 
Conectivo Se ... então... () 
 Variações gramaticais da implicação: 
 
– Se P então Q 
– P implica em Q; P, logo Q 
– P só se Q; P somente se Q 
– P apenas se Q; P só quando Q 
– Q se P ; Q segue de P 
Conectivo ...se e somente se... 
() 
 Os enunciados formados com a expressão ...se e somente 
se... são chamados bicondicionais ou biimplicações . 
 
 Exemplo: 
 T é um triângulo se e somente se T é um polígono de três lados 
Conectivo ...se e somente se... 
() 
 Um bicondicional pode ser considerado uma conjunção 
de dois condicionais: 
– P se e somente se Q 
– P se Q e P somente se Q 
– Se Q então P e P somente se Q 
– Se Q então P e Se P então Q 
que equivale a: 
– Se P então Q e Se Q então P 
 
Reescrita de sentenças 
 Seja a sentença: “5 não é ímpar”. 
• A sentença pode ser entendida como “5 é par”. (sentença 
atômica). 
• Por outro lado, a sentença é a negação da sentença “5 é 
ímpar”. (sentença molecular). 
 
 Seja a sentença: “Emiliano e Chagas são casados”. 
• Qual é a intenção da sentença? 
• Não está claro que o objetivo desta sentença seja informar 
que Emiliano tem uma esposa e Chagas tem outra. 
12 
Reescrita de sentenças 
 Regras da Reescrita 
 
• Existem algumas regras básicas que devem ser seguidas 
na construção de sentenças. 
• Deve-se explicitar as sentenças atômicas que compõem a 
sentença final, atribuindo um símbolo (p, q, r, s, t, etc); 
• Os conectivos são também representados por símbolos (, 
, , , ). 
13 
Reescrita de sentenças 
Exemplos 
• “5 não é ímpar, nem é maior que 0” 
 
• É a conjunção “5 não é ímpar e 5 não é maior que 0”. 
• Reescrita: ((¬(5 é ímpar)) Λ (¬(5 é maior que 0))). 
• Simbolicamente: p: (5 é ímpar), q: (5 é maior que 0) 
então (¬(p) Λ¬(q)) 
 
14 
Reescrita de sentenças 
Exemplos 
• “Nathalie e Natasha foram à Barras” 
 
• É a conjunção “Nathalie foi à Barras e Natasha foi à 
Barras”. 
• Reescrita: (Nathalie foi à Barras)  (Natasha foi à 
Barras). 
• Simbolicamente: p: (Nathalie foi à Barras), q: (Natasha 
foi à Barras) então ((p)  (q)) 
 
15 
Reescrita de sentenças 
•
16 
Reescrita de sentenças 
•
17 
Simbologia das Sentenças 
 Passos para simbolização das sentenças: 
 
1. Classificar a sentença como atômica ou molecular. 
2. Classificar todos os conectivos que ocorrem na sentença 
(se for molecular). 
3. Classificar o tipo da sentença em negação, conjunção, 
disjunção, implicação ou biimplicação (se for molecular). 
4. Reescrever a sentença de acordo com as regras de 
reescritas. 
5. Simbolizar a sentença reescrita, substituindo as 
sentenças atômicas pelas letras p, q, r ou s. 
Simbologia das Sentenças 
 “Francisco é feliz”. 
 
1. Atômica. 
2. Não tem conectivos. 
3. Não pode ser classificada. 
4. (Francisco é feliz). 
5. p: Francisco é feliz. 
 
Simbologia: (p) 
Simbologia das Sentenças 
 “Francisco é feliz e Cecília o ama”. 
 
1. Molecular. 
2. Possui o conectivo e. 
3. Conjunção. 
4. ((Francisco é feliz)  (Cecília o ama)). 
5. p: Francisco é feliz e q: Cecília o ama . 
 
Simbologia: ((p) (q)) 
Simbologia das Sentenças 
 “Francisco é feliz caso Cecília o ame”. 
• A sentença deve ser reescrita como “Se Cecília ama 
Francisco, então Francisco é feliz”. 
 
1. Molecular. 
2. Possui o conectivo Se... então.... 
3. Implicação. 
4. ((Cecília ama Francisco)  (Francisco é feliz)). 
5. p: Cecília ama Francisco e q: Francisco é feliz. 
 
Simbologia: ((p)(q)) 
Simbologia das Sentenças 
Alfabeto da Lógica Proposicional 
 
– Definição 1.1 (alfabeto) O alfabeto da Lógica 
Proposicional é constituído por: 
• símbolos de pontuação: (, ); 
• símbolos de verdade: true, false; 
• símbolos proposicionais: P; Q; R; S; P1; Q1; R1; S1; P2; Q2; ...; 
• conectivos proposicionais:  ,  ,  ,  ,  . 
Simbologia das Sentenças 
Alfabeto da Lógica Proposicional 
 
– Definição: (alfabeto) O alfabeto da Lógica Proposicional é 
constituído por: 
• símbolos de pontuação: (, ); 
• símbolos de verdade: true, false; 
• símbolos proposicionais: P; Q; R; S; P1; Q1; R1; S1; P2; Q2; ...; 
• conectivos proposicionais:  ,  ,  ,  ,  . 
Fórmulas da Lógica Proposicional 
 Definição: (fórmula) As fórmulas da linguagem da 
Lógica Proposicional são construídas, de forma indutiva, 
a partir dos símbolos do alfabeto conforme as regras a 
seguir. O conjunto das fórmulas é o menor conjunto que 
satisfaz as regras: 
todo símbolo de verdade é uma fórmula; 
 todo símbolo proposicional é uma fórmula; 
se H é uma fórmula, então (H), a negação de H, é uma 
fórmula; 
Fórmulas da Lógica Proposicional 
Definição: (fórmula) 
se H e G são fórmulas, então a disjunção de H e G; dada por: (H  G); 
é uma fórmula; 
se H e G são fórmulas, então a conjunção de H e G; dada por: (H  G); 
é uma fórmula; 
se H e G são fórmulas, então a implicação de H em G; dada por: 
 (H  G); é uma fórmula. Nesse caso, H é o antecedente e G o 
 consequente da fórmula (H  G); 
 se H e G são fórmulas, então a bi-implicação de H e G; dada por: 
 (H  G); é uma fórmula. Nesse caso, H é o lado esquerdo e G o lado 
 direito da fórmula (H  G). 
Fórmulas da Lógica Proposicional 
• Exemplo: (construção de fórmulas) 
– A partir das fórmulas P e Q, obtemos 
(P  Q) 
Utilizamos as fórmulas (P  Q) e true, obtemos a fórmula 
 
((P  Q)  true)Fórmulas da Lógica Proposicional 
• Exemplo : (construção de fórmulas) 
– As concatenações dos símbolos a seguir não constituem 
fórmulas 
PR 
(R true) 
(true   (R true)) 
Simplificação das Fórmulas 
 Os parênteses externos podem ser omitidos (os 
parênteses ou símbolos de pontuação das fórmulas são 
omitidos quando não há problemas sobre a sua 
interpretação). 
 
(((P  R)  true)  (Q  S)) PR 
 
 pode ser escrita como 
 
((P  R)  true)  (Q  S) 
Simplificação das Fórmulas 
 Os parênteses em torno da negação podem ser retirados, 
porém, se a negação estiver fora dos parênteses fazendo 
referência à sentença que está nos parênteses, então eles 
não devem ser retirados. 
 
– a sentença simbolizada ((¬q)  (p→q))→(¬q) será escrita 
por (¬q  (p→q))→¬q. 
 
– a sentença simbolizada ¬(p  q) não pode ser escrita por 
¬p  q. 
 
Simplificação de Fórmulas 
 Definição: (ordem de precedência) Na Lógica 
Proposicional, a ordem de precedência dos conectivos 
proposicionais é definida por: 
– maior precedência: ; 
– precedência intermediária:  , ; 
– menor precedência:  , . 
 
 Exemplo: Os conectivos → e ↔ têm precedência sobre os 
conectivos  e . 
• a sentença simbolizada ¬q  ((p → q) → ¬p) pode ser escrita por 
 ¬q  (p → q) → ¬p