Baixe o app para aproveitar ainda mais
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
LÓGICA PARA COMPUTAÇÃO Professora Luciana Conceição Dias Campos 1 Capítulo 11 – Operações Lógicas sobre Sentenças Abertas Até o capítulo 10, apresentou-‐se conteúdos do cálculo proposicional. Agora começaremos um novo conteúdo relacionado ao cálculo de predicados ou lógica de primeira ordem. Neste capítulo, vimos o conceito de Sentenças Abertas. Uma sentença aberta é como uma proposição que contém pelo menos uma variável. Desta forma, não é possível avaliar, por conta desta variável, se esta sentença é verdadeira ou falsa. Contudo, esta variável pertence a um conjunto universo, chamado de domínio da variável. Dentro deste domínio, é possível se estabelecer um conjunto verdade, que corresponde a todos os valores (dentro do domínio) que a variável pode assumir fazendo com que a sentença seja verdadeira. Exemplo: Considere ℕ (conjunto dos números naturais) o universo da variável 𝑋. Dadas as sentenças abertas 𝑝(𝑋): 1. 𝑋 + 1 > 8. 2. 𝑋 + 7 < 5. 3. 𝑋 é divisor de 10. 4. 𝑋 + 3 > 1 Temos que o conjunto verdade destas sentenças, expresso por Vp, é dado por: 1. Vp = {9, 10, 11… } ⊂ ℕ 2. Vp = ∅ ⊂ ℕ 3. Vp = {1, 2, 5, 10} ⊂ ℕ 4. Vp = 1, 2, 3… = ℕ Veja que em uma sentença aberta 𝑝(𝑋) em um universo U pode ocorrer 3 situações: 1. O conjunto verdade coincidir com o universo da variável. Vp = U. Neste caso, diz-‐se que a sentença exprime uma condição universal. 2. O conjunto verdade é vazio. Vp = ∅. Ou seja, a sentença não é verdadeira para nenhum elemento do universo U. Neste caso, diz-‐se que a sentença exprime uma condição impossível. 3. O conjunto verdade é um subconjunto do universo U. Vp ⊂ U. Ou seja, a sentença é verdadeira para alguns elementos do universo. Neste caso, diz-‐se que a sentença exprime uma condição possível. Quando a sentença aberta possui mais de uma variável, do tipo 𝑝(𝑋,𝑌), temos que o universo desta sentença é dado pelo produto cartesiano de UX× Uy. Então, uma sentença aberta 𝑝(𝑋,𝑌) em UX × Uy torna-‐se verdadeira (ou falsa) todas as vezes que as variáveis são substituídas pelo par ordenado (𝑎, 𝑏) com (𝑎, 𝑏) ∈ UX × Uy. Exemplo: Sejam os conjuntos 𝐴 = {1, 2, 3, 4} e 𝐵 = {1, 3, 5}. São sentenças abertas 𝑝 𝑋,𝑌 em 𝐴 × 𝐵: 1. 𝑋 < 𝑌. 2. 𝑌 = 2𝑋. O conjunto verdade destas sentenças são: 1. Vp = 𝑋,𝑌 𝑋 ∈ 𝐴 ∧ 𝑌 ∈ 𝐵 ∧ 𝑋 < 𝑌 = { 1,3 , 1,5 , 2,3 , 2,5 , 3,5 , 4,5 } ⊂ 𝐴×𝐵. 2. Vp = 𝑋,𝑌 𝑋 ∈ 𝐴 ∧ 𝑌 ∈ 𝐵 ∧ 𝑌 = 2𝑋 = ∅ ⊂ 𝐴×𝐵. LÓGICA PARA COMPUTAÇÃO Professora Luciana Conceição Dias Campos 2 A idéia de 2 variáveis pode ser estendida para N variáveis. As operações com os conectivos lógicos vistos no cálculo proposicional podem ser aplicados às sentenças abertas: 1. NEGAÇÃO Seja a sentença aberta 𝑝(𝑋) em um conjunto A. Tem-‐se que a negação desta sentença aberta é a sentença dada por ~𝑝(𝑋) em A. Um elemento 𝑎 ∈ 𝐴 satisfaz a sentença aberta ~𝑝(𝑋), se e somente se, ~𝑝(𝑎) for verdadeira. E isto só ocorre se 𝑝(𝑎) for falsa, ou seja, se o elemento 𝑎 ∈ 𝐴 não satisfaz a sentença 𝑝(𝑋) em A. Portanto, o conjunto verdade da sentença 𝑝(𝑋), denotado por 𝑉~!, é o complemento, em relação a A, do conjunto verdade 𝑉! (𝑉~! = ∁ 𝐴 𝑉!). Exemplo: Sejam a sentença 𝑝(𝑋) em A (conjunto dos números naturais divisíveis por 5): 𝐴 = 5𝑌 𝑌 ∈ 𝑁 = {5, 10, 15, 20,… } 𝑝 𝑋 = 𝑋 termina com o algarismo 5. O conjunto verdade de ~𝑝(𝑋) é dado por: 𝑉~! = 𝑋 ∈ 𝐴 𝑋 termina com o algarismo 0}. 2. CONJUNÇÃO Sejam as sentenças abertas 𝑝(𝑋) e 𝑞(𝑋) em um conjunto A. Tem-‐se que a conjunção destas sentenças abertas é a sentença dada por 𝑝(𝑋) ∧ 𝑞(𝑋) em A. Um elemento 𝑎 ∈ 𝐴 satisfaz a sentença aberta 𝑝(𝑋) ∧ 𝑞(𝑋), se e somente se, 𝑝(𝑎) ∧ 𝑞(𝑎) for verdadeira. E isto só ocorre se 𝑝(𝑎) e 𝑞(𝑎) forem ambas verdadeiras, ou seja, se o elemento 𝑎 ∈ 𝐴 satisfaz ao mesmo tempo as sentenças 𝑝(𝑋) e 𝑞(𝑋) em A. Portanto, o conjunto verdade da sentença 𝑝(𝑋) ∧ 𝑞(𝑋), denotado por 𝑉!∧!, é a interseção dos conjuntos verdades 𝑉! e 𝑉! (𝑉!∧! = 𝑉! ∩ 𝑉!). Exemplo: Sejam as sentenças 𝑝(𝑋) e 𝑞(𝑋) em ℤ (conjunto dos números inteiros): 𝑝 𝑋 = 𝑋! + 𝑋 − 2 = 0 𝑞 𝑋 = 𝑋! − 4 = 0 O conjunto verdade de 𝑝(𝑋) ∧ 𝑞(𝑋) é dado por: 𝑉!∧! = −2,1 ∩ −2,2 = {−2} ⊂ ℤ. 3. DISJUNÇÃO Sejam as sentenças abertas 𝑝(𝑋) e 𝑞(𝑋) em um conjunto A. Tem-‐se que a disjunção destas sentenças abertas é a sentença dada por 𝑝(𝑋) ∨ 𝑞(𝑋) em A. Um elemento 𝑎 ∈ 𝐴 satisfaz a sentença aberta 𝑝(𝑋) ∨ 𝑞(𝑋), se e somente se, 𝑝(𝑎) ∨ 𝑞(𝑎) for verdadeira. E isto só ocorre se 𝑝(𝑎) ou 𝑞(𝑎) forem verdadeiras, ou seja, se o elemento 𝑎 ∈ 𝐴 satisfaz pelo menos uma das sentenças 𝑝(𝑋) ou 𝑞(𝑋) em A. Portanto, o conjunto verdade da sentença 𝑝(𝑋) ∨ 𝑞(𝑋) , denotado por 𝑉!∨! , é a união dos conjuntos verdades 𝑉! e 𝑉! (𝑉!∨! = 𝑉! ∪ 𝑉!). Exemplo: Sejam as sentenças 𝑝(𝑋) e 𝑞(𝑋) em ℤ (conjunto dos números inteiros): 𝑝 𝑋 = 𝑋! + 𝑋 − 2 = 0 LÓGICA PARA COMPUTAÇÃO Professora Luciana Conceição Dias Campos 3 𝑞 𝑋 = 𝑋! − 4 = 0 O conjunto verdade de 𝑝(𝑋) ∨ 𝑞(𝑋) é dado por: 𝑉!∧! = −2,1 ∪ −2,2 = {−2, 1, 2} ⊂ ℤ. 4. CONDICIONAL Sejam as sentenças abertas 𝑝(𝑋) e 𝑞(𝑋) em um conjunto A. Tem-‐se que a condicional destas sentenças abertas é a sentença dada por 𝑝(𝑋) → 𝑞(𝑋) em A. Um elemento 𝑎 ∈ 𝐴 satisfaz a sentença aberta 𝑝(𝑋) → 𝑞(𝑋), se e somente se, 𝑝(𝑎) → 𝑞(𝑎) for verdadeira. Lembrando da regra de equivalência da condicional, temos que a sentença 𝑝(𝑋) →𝑞(𝑋) é equivalente à sentença ~𝑝(𝑋) ∨ 𝑞(𝑋). Assim, se a sentença 𝑝(𝑎) → 𝑞(𝑎) for verdadeira, segue que a sentença ~𝑝(𝑎) ∨ 𝑞(𝑎) também é verdadeira. E isto só ocorre se o elemento 𝑎 ∈ 𝐴 satisfaz pelo menos uma das sentenças ~𝑝(𝑋) ou 𝑞(𝑋) em A. Portanto, o conjunto verdade da sentença 𝑝(𝑋) → 𝑞(𝑋), denotado por 𝑉!→! , é equivalente ao conjunto verdade 𝑉~!∨!, que é a união dos conjuntos verdades 𝑉~! e 𝑉! (𝑉~!∨! = 𝑉~! ∪ 𝑉!). E como foi visto, 𝑉~! é o complemento, em relação a A, do conjunto verdade 𝑉! (𝑉~! = ∁ 𝐴 𝑉!). Exemplo: Sejam as sentenças 𝑝(𝑋) e 𝑞(𝑋) em ℕ (conjunto dos números naturais): 𝑝 𝑋 = 12/𝑋 (12 é divisível por X) 𝑞 𝑋 = 45/𝑋(45 é divisível por X) O conjunto verdade de 𝑝(𝑋) → 𝑞(𝑋) é dado por: 𝑉!→! = 𝑉~!∨! = 𝑉~! ∪ 𝑉! = ∁ ℕ 𝑉! ∪ 𝑉! = ∁ ℕ 1, 2, 3, 4, 6, 12 ∪ 1, 3, 5, 9, 15, 45 = ℕ− {2 , 4, 6, 12}. 5. BICONDICIONAL Sejam as sentenças abertas 𝑝(𝑋) e 𝑞(𝑋) em um conjunto A. Tem-‐se que a bicondicional destas sentenças abertas é a sentença dada por 𝑝(𝑋) ↔ 𝑞(𝑋) em A. Um elemento 𝑎 ∈ 𝐴 satisfaz a sentença aberta 𝑝 𝑋 ↔ 𝑞 𝑋 , se e somente se, 𝑝 𝑎 ↔ 𝑞 𝑎 for verdadeira. Lembrando da regra de equivalência da condicional, temos que a sentença 𝑝 𝑋 ↔𝑞 𝑋 é equivalente à sentença 𝑝 𝑋 → 𝑞 𝑋 ∧ 𝑞 𝑋 → 𝑝 𝑋 ⇔ ~𝑝 𝑋 ∨ 𝑞 𝑋 ∧ ~𝑞 𝑋 ∨ 𝑝 𝑋 ⇔ (~𝑝 𝑋 ∧ ~𝑞 𝑋 ) ∨ (𝑝 𝑋 ∧ 𝑞 𝑋 ). Assim, se a sentença 𝑝(𝑎) ↔ 𝑞(𝑎) for verdadeira, segue que a sentença (~𝑝 𝑎 ∧ ~𝑞 𝑎 ) ∨(𝑝 𝑎 ∧ 𝑞 𝑎 ) também é verdadeira. E isto só ocorre se o elemento 𝑎 ∈ 𝐴 satisfaz pelo menos uma das sentenças (~𝑝 𝑋 ∧ ~𝑞 𝑋 ) ou (𝑝 𝑋 ∧ 𝑞 𝑋 ) em A. Portanto, o conjunto verdade da sentença 𝑝(𝑋) ↔ 𝑞(𝑋), denotado por 𝑉!↔! , é equivalente ao conjunto verdade 𝑉(~!∧~!)∨(!∧!) , que é a união dos conjuntos verdades 𝑉(~!∧~!) e 𝑉(!∧!) (𝑉(~!∧~!)∨(!∧!) = 𝑉(~!∧~!) ∪ 𝑉(!∧!)). E como foi visto, segue que: • 𝑉 ~!∧~! = 𝑉~! ∩ 𝑉~! • 𝑉 !∧! = 𝑉! ∩ 𝑉! • 𝑉~! é o complemento, em relação a A, do conjunto verdade 𝑉! (𝑉~! = ∁ 𝐴 𝑉!). • 𝑉~! é o complemento, em relação a A, do conjunto verdade 𝑉! (𝑉~! = ∁ 𝐴 𝑉!). Portanto, 𝑉!↔! = ∁ 𝐴 𝑉! ∩ ∁ 𝐴 𝑉! ∪ {𝑉! ∩ 𝑉!}. Exemplo: Sejam as sentenças 𝑝(𝑋) e 𝑞(𝑋) em ℕ (conjunto dos números naturais): 𝑝 𝑋 = 6/𝑋 (6 é divisível por X) 𝑞 𝑋 = 15/𝑋 (15 é divisível por X) LÓGICA PARA COMPUTAÇÃO Professora Luciana Conceição Dias Campos 4 O conjunto verdade de 𝑝(𝑋) → 𝑞(𝑋) é dado por: 𝑉!→! = ∁ ℕ 𝑉! ∩ ∁ ℕ 𝑉! ∪ 𝑉! ∩ 𝑉! = ∁ ℕ 1, 2, 3, 6 ∩ ∁ ℕ 1, 3, 5, 15 ∪ 1, 2, 3, 6 ∩1, 3, 5, 15 = ℕ− 1, 2 , 3, 6 ∩ ℕ− 1, 3, 5, 15 ∪ 1, 3 = ℕ− 1, 2 , 3, 5, 6, 15 ∪ 1, 3 =ℕ− 2 , 5, 6, 15 . As propriedades das operações lógicas vistas sobre o cálculo proposicional (álgebra das proposições) se estendem às operações lógicas sobre sentenças abertas.
Compartilhar