of 57/57
Predicados e Quantificadores Profa. Sheila Morais de Almeida DAINF-UTFPR-PG junho - 2018 Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 1 / 57

Predicados e Quantificadores - Sheila Almeida€¦ · Predicados e Quanti cadores Profa. Sheila Morais de Almeida DAINF-UTFPR-PG junho - 2018 Sheila Almeida (DAINF-UTFPR-PG) Predicados

  • View
    7

  • Download
    0

Embed Size (px)

Text of Predicados e Quantificadores - Sheila Almeida€¦ · Predicados e Quanti cadores Profa. Sheila...

  • Predicados e Quantificadores

    Profa. Sheila Morais de Almeida

    DAINF-UTFPR-PG

    junho - 2018

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 1 / 57

  • Este material é preparado usando como referências os textos dos seguinteslivros.

    GERSTING, Judith L.,Mathematical Structures For Computer Science:A Modern Approach to Discrete Mathematics, 6th ed., 2007.

    ROSEN, Kenneth H., Discrete Mathematics and its applications, 6thed., 2007.

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 2 / 57

  • Predicados e Quantificadores

    Como expressar a proposição “Para todo número inteiro x , o valor de x épositivo.” usando lógica proposicional?

    Esta proposição contém duas caracteŕısticas distintas das anteriores:

    • predicados,

    • e quantificadores.

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 3 / 57

  • Predicado

    Predicado

    O predicado é uma propriedade ou atributo.

    Exemplo: x > 0

    Predicados podem ser representados por funções das variáveis a que sereferem.

    Exemplo: P(x) : x é azul.

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 4 / 57

  • Predicado

    Exemplo: Considere o predicado: P(x) : x > 3.

    Qual o valor-verdade das proposições a seguir?

    • P(2)

    • P(3)

    • P(4)

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 5 / 57

  • Predicado

    Exemplo: Considere o predicado: P(x) : x > 3.

    Qual o valor-verdade das proposições a seguir?

    • P(2) falso

    • P(3) falso

    • P(4) verdadeiro

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 6 / 57

  • Predicado

    Considere o predicado: R(x , y , z) : x + y = z .

    Qual o valor-verdade das proposições a seguir?

    • R(1, 2, 3) verdadeiro

    • R(3, 2, 1) falso

    • R(0, 0, 1) falso

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 7 / 57

  • Predicado

    Considere o predicado: R(x , y , z) : x + y = z .

    Qual o valor-verdade das proposições a seguir?

    • R(1, 2, 3) verdadeiro

    • R(3, 2, 1) falso

    • R(0, 0, 1) falso

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 8 / 57

  • Quantificadores

    Quantificadores

    Quantificadores são expressões como “para todo”, “para cada”, “paraalgum”, “existe um”, que dizem de alguma forma quantos objetos têmuma certa propriedade.

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 9 / 57

  • Quantificadores

    Quantificador Universal ∀xLê-se: para todo x , para cada x , todo x .

    Exemplo: ∀x(x > 0) representa a senteça:

    ‘Todo número x é positivo.”

    Quantificador Existencial ∃xLê-se: para algum x , existe um x , pelo menos um x .

    Exemplo: ∃x(x > 0) representa a senteça:

    “Existe um número x positivo.”

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 10 / 57

  • Doḿınio

    O valor-verdade de uma expressão depende do doḿınio da variável.

    Exemplo: ∀x(x ≥ 0)

    Doḿınio: números naturais.Valor-verdade: verdadeira.

    Doḿınio: números inteirosValor-verdade: falsa. (Contraexemplo: x = −2, x = −10, entre outros.)

    Exemplo: ∃x(x > 0)

    Se o doḿınio contém um número positivo, então a expressão é verdadeira.Caso contrário, é falsa.

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 11 / 57

  • Doḿınio

    Exemplo: dê o valor-verdade das expressões lógicas a seguir.

    Doḿınio: todos os livros da biblioteca da UTFPR - Ponta Grossa

    P(x) : x tem capa vermelha.

    ∀xP(x) falso

    ∃xP(x) verdadeira (Deve existir algum livro com capa vermelha nabiblioteca!)

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 12 / 57

  • Doḿınio

    Exemplo: dê o valor-verdade das expressões lógicas a seguir.

    Doḿınio: todos os livros da biblioteca da UTFPR - Ponta Grossa

    P(x) : x tem capa vermelha.

    ∀xP(x) falso

    ∃xP(x) verdadeira(Deve existir algum livro com capa vermelha na biblioteca!)

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 13 / 57

  • Doḿınio

    Dê o valor-verdade da expressão lógica:

    • ∀xP(x), onde P(x) : x é um vegetal.Doḿınio: todas as árvores frut́ıferas. verdadeiro

    • ∀xP(x), onde P(x) : x é positivo ou negativo.Doḿınio: números inteiros. falso

    • ∃xP(x), onde P(x) : x > 3. Doḿınio: números reais. verdadeiro

    • ∃xP(x), onde P(x) : x = x + 1. Doḿınio: números reais. falso

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 14 / 57

  • Doḿınio

    Dê o valor-verdade da expressão lógica:

    • ∀xP(x), onde P(x) : x é um vegetal.Doḿınio: todas as árvores frut́ıferas. verdadeiro

    • ∀xP(x), onde P(x) : x é positivo ou negativo.Doḿınio: números inteiros. falso

    • ∃xP(x), onde P(x) : x > 3. Doḿınio: números reais. verdadeiro

    • ∃xP(x), onde P(x) : x = x + 1. Doḿınio: números reais. falso

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 15 / 57

  • Quantificador de Unicidade

    Quantificador de Unicidade

    O quantificador de unicidade indica que existe exatamente um elementoque satisfaz o predicado.

    Denota-se: ∃!xP(x) ou ∃1xP(x).

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 16 / 57

  • Quantificador de Unicidade

    Exemplos

    ∃!x(2x = 0), no doḿınio dos números reais é verdadeira e x = 0.

    ∃1x(x2 < 0), no doḿınio dos números reais é falsa.

    ∃!x(x > 1000), no doḿınio dos números naturais é falsa.

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 17 / 57

  • Quantificador de Doḿınio Restrito

    Pode-se incluir imediatamente após o quantificador uma notação abreviadaque limita o doḿınio.

    Exemplos:

    • ∀x < 0(x2 > 0)

    • ∀y 6= 0(y3 6= 0)

    • ∃z > 0(z2 = 2)

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 18 / 57

  • Quantificador de Doḿınio Restrito

    O quantificador universal de doḿınio restrito pode ser substitúıdo por umconectivo condicional:

    • ∀x < 0(x2 > 0) ≡ ∀x(x < 0→ x2 > 0)

    • ∀y 6= 0(y3 6= 0) ≡ ∀y(y 6= 0→ y3 6= 0)

    O quantificador existencial de doḿınio restrito pode ser substitúıdo poruma conjunção:

    • ∃z > 0(z2 = 2) ≡ ∃z(z > 0 ∧ z2 = 2)

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 19 / 57

  • Prioridade dos Quantificadores

    Os quantificadores tem prioridade sobre qualquer conectivo da lógicaproposicional:

    ∃zz > 0 ∧ z2 = 2 6≡ ∃z(z > 0 ∧ z2 = 2)

    ∃zz > 0 ∧ z2 = 2 ≡ ∃z(z > 0) ∧ z2 = 2

    ∀xP(x) ∨ Q(x) ≡ ∀x(P(x)) ∨ Q(x)

    ∀xP(x) ∨ Q(x) 6≡ ∀x(P(x) ∨ Q(x))

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 20 / 57

  • Equivalências Lógicas Quantificadas

    Cuidado com as equivalências entre expressões quantificadas compostas:

    ∀x(P(x) ∧ Q(x)) ≡ ∀xP(x) ∧ ∀xQ(x)

    ∀x(P(x) ∨ Q(x)) 6≡ ∀xP(x) ∨ ∀xQ(x)

    ∃x(P(x) ∨ Q(x)) ≡ ∃xP(x) ∨ ∃xQ(x)

    ∃x(P(x) ∧ Q(x)) 6≡ ∃xP(x) ∧ ∃xQ(x)

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 21 / 57

  • Fórmulas bem formadas (wffs)

    Expressões devem obedecer regras de sintaxe para serem fórmulas bemformadas:

    • P(x)∀x ∧ ∃y não é uma wff.

    • ∀x(P(x)→ Q(x)) é uma wff.

    • (∃x)S(x) ∨ (∀y)T (y) é uma wff.

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 22 / 57

  • Escopo dos Quantificadores

    Terminologia

    O escopo de um quantificador é o contexto que o mesmo abrange.

    Se não há parênteses, o escopo é o predicado seguinte. Caso contrário, oescopo é determinado pelo próximo parêntese e/ou colchete à direita.

    Exemplos

    ∃xP(X ) ∨ ∀yT (y)

    O escopo de ∃x é P(x) e o escopo de ∀y é T (y).

    ∃x [A(x) ∧ ∀y(B(x , y)→ C (y)]

    O escopo de ∃x é A(x) ∧ ∀y(B(x , y)→ C (y).

    O escopo de ∀y é B(x , y)→ C (y).

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 23 / 57

  • Variáveis livres

    Terminologia

    Se uma variável aparece em alguma fórmula bem formada e não faz partede nenhum quantificador, então é uma variável livre.

    Exemplo: y é uma variável livre em (∀x)[Q(x , y)→ (∃y)R(x , y)],

    porque y ocorre pela primeira vez sem estar acompanhado de umquantificador.

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 24 / 57

  • Variáveis livres

    Exemplo: Considere o doḿınio de todos os números inteiros.

    P(x) : x > 0

    Qual o valor verdade de P(y) ∧ P(5)?

    Qual o valor verdade de P(y) ∨ P(5)?

    Observe que, nos dois casos, y é uma variável livre, não está associada aum quantificador.

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 25 / 57

  • Variáveis livres

    Exemplo: Considere o doḿınio de todos os números inteiros.

    P(x) : x > 0

    Qual o valor verdade de P(y) ∧ P(5)? indefinido

    Qual o valor verdade de P(y) ∨ P(5)? verdade

    Observe que, nos dois casos, y é uma variável livre, não está associada aum quantificador.

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 26 / 57

  • Tradução

    Muitas frases podem ser escritas por predicados lógicos.

    Considere a frase: “Todo papagaio é feio.”

    É o mesmo que dizer: “Para qualquer coisa, se essa coisa é um papagaio,então é feio.”

    Sejam P(x) : x é um papagaio e F (x) : x é feio.

    Simbolicamente: ∀x(P(x)→ F (x)).Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 27 / 57

  • Tradução

    Muitas frases podem ser escritas por predicados lógicos.

    Considere a frase: “Todo papagaio é feio.”

    É o mesmo que dizer: “Para qualquer coisa, se essa coisa é um papagaio,então é feia.”

    Sejam P(x) : x é um papagaio e F (x) : x é feio.

    Simbolicamente: ∀x(P(x)→ F (x)).Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 28 / 57

  • Tradução

    Dica: “o quantificador universal e o conectivo de implicação quase sempreestão juntos.”

    Podeŕıamos substituir, neste contexto, ∀x(P(x)→ F (x)) por∀x(P(x) ∧ F (x))? Não! nem tudo no mundo é papagaio feio!

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 29 / 57

  • Tradução

    Dica: “o quantificador universal e o conectivo de implicação quase sempreestão juntos.”

    Podeŕıamos substituir, neste contexto, ∀x(P(x)→ F (x)) por∀x(P(x) ∧ F (x))? Não! nem tudo no mundo é papagaio feio!

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 30 / 57

  • Tradução

    Considere a frase: “Existe um papagaio feio.”

    É o mesmo que dizer: “Existe uma coisa, que é um papagaio e é feia.”

    Sejam P(x) : x é um papagaio e F (x) : x é feia.

    Simbolicamente: ∃x(P(x) ∧ F (x)).

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 31 / 57

  • Tradução

    Dica: “o quantificador existencial e o conectivo ∧ quase sempre estãojuntos.”

    Podeŕıamos substituir, neste contexto, ∃x(P(x) ∧ F (x)) por∃x(P(x)→ F (x))?

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 32 / 57

  • Tradução

    Podeŕıamos substituir, neste contexto, ∃x(P(x) ∧ F (x)) por∃x(P(x)→ F (x))?

    O que precisa acontecer para que nosso predicado seja verdade?

    Basta não existir papagaios.

    Mas se não existir, então não existe um papagaio feio. (Que é o quequeŕıamos afirmar!).

    A implicação não traduziu exatamente o que queŕıamos dizer.

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 33 / 57

  • Tradução

    Considere: M(x) : x é um maḿıfero, Q(x) : x é quadrúpede,B(x) : x gosta de brincar, onde o doḿınio são todos os animais.

    Escreva predicados bem formados para as seguintes proposições:

    1 Todos os maḿıferos gostam de brincar.∀x(M(x)→ B(x))

    2 Alguns maḿıferos quadrúpedes gostam de brincar.∃x(M(x) ∧ Q(x) ∧ B(x))

    3 Todos que gostam de brincar são maḿıferos não quadrúpedes.∀x(B(x)→ M(x) ∧ ¬Q(x))

    4 Só maḿıferos quadrúpedes gostam de brincar.∀x(B(x)→ M(x) ∧ Q(x))

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 34 / 57

  • Tradução

    Considere: M(x) : x é um maḿıfero, Q(x) : x é quadrúpede,B(x) : x gosta de brincar, onde o doḿınio são todos os animais.

    Escreva predicados bem formados para as seguintes proposições:

    1 Todos os maḿıferos gostam de brincar.∀x(M(x)→ B(x))

    2 Alguns maḿıferos quadrúpedes gostam de brincar.∃x(M(x) ∧ Q(x) ∧ B(x))

    3 Todos que gostam de brincar são maḿıferos não quadrúpedes.∀x(B(x)→ M(x) ∧ ¬Q(x))

    4 Só maḿıferos quadrúpedes gostam de brincar.∀x(B(x)→ M(x) ∧ Q(x))

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 35 / 57

  • Quantificadores Agrupados

    Terminologia

    Dois quantificadores estão agrupados se um está no escopo do outro.

    Exemplo: ∀x∃y(x + y = 0).

    Escopo de ∃y : (x + y = 0).

    Escopo de ∀x : ∃y(x + y = 0).

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 36 / 57

  • Quantificadores Agrupados

    Exemplo: o que significam as seguintes expressões?

    Doḿınio: todos os números reais.

    ∀x∀y(x + y = y + x).A ordem dos termos não altera o resultado.

    ∀x∀y∀z(x + (y + z) = x + (y + z)).A ordem das somas não altera o resultado.

    ∀x∀y((x > 0) ∧ (y < 0)→ xy < 0).Multiplicação de números com paridades distintas é negativa.

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 37 / 57

  • Quantificadores Agrupados

    Exemplo: o que significam as seguintes expressões?

    Doḿınio: todos os números reais.

    ∀x∀y(x + y = y + x).A ordem dos termos não altera o resultado.

    ∀x∀y∀z(x + (y + z) = x + (y + z)).A ordem das somas não altera o resultado.

    ∀x∀y((x > 0) ∧ (y < 0)→ xy < 0).Multiplicação de números com paridades distintas é negativa.

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 38 / 57

  • Ordem dos Quantificadores

    Se os quantificadores não são todos universais (ou todos existenciais)então a ordem dos quantificadores faz diferença na interpretação.

    Exemplo: seja P(x , y) : x + y = y + x e o doḿınio dos números reais.

    Qual o valor verdade para ∀x∀yP(x , y)? verdadeiro

    Qual o valor verdade para ∀y∀xP(x , y)? verdadeiro

    Exemplo: seja Q(x , y) : x + y = 0 e o doḿınio dos números reais.

    Qual o valor verdade para ∀x∃yQ(x , y)? verdadeiro

    Qual o valor verdade para ∃y∀xQ(x , y)? falso

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 39 / 57

  • Ordem dos Quantificadores

    Se os quantificadores não são todos universais (ou todos existenciais)então a ordem dos quantificadores faz diferença na interpretação.

    Exemplo: seja P(x , y) : x + y = y + x e o doḿınio dos números reais.

    Qual o valor verdade para ∀x∀yP(x , y)? verdadeiro

    Qual o valor verdade para ∀y∀xP(x , y)? verdadeiro

    Exemplo: seja Q(x , y) : x + y = 0 e o doḿınio dos números reais.

    Qual o valor verdade para ∀x∃yQ(x , y)? verdadeiro

    Qual o valor verdade para ∃y∀xQ(x , y)? falso

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 40 / 57

  • Valor-verdade das Expressões

    Quando uma expressão ∀xP(x) é falsa?

    Quando existe um x no doḿınio que não satisfaz P(x)

    Quando uma expressão ∃xP(x) é falsa?

    Quando todo x do doḿınio não satisfaz P(x)

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 41 / 57

  • Valor-verdade das Expressões

    Quando uma expressão ∀xP(x) é falsa?

    Quando existe um x no doḿınio que não satisfaz P(x)

    Quando uma expressão ∃xP(x) é falsa?

    Quando todo x do doḿınio não satisfaz P(x)

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 42 / 57

  • Negação com Quantificadores

    Para negar uma expressão ∀xP(x) é suficiente descrever por uma fórmulabem formada quando essa sentença é falsa:

    ¬(∀xP(x)) ≡ ∃x(¬P(X ))

    Para negar qualquer expressão da lógica de predicados é suficientedescrever por uma fórmula bem formada quando essa sentença é falsa:

    ¬(∃xP(x)) ≡ ∀x(¬P(X ))

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 43 / 57

  • Negação com Quantificadores Agrupados

    Escreva a negação de cada uma das sentenças:

    • ∀x∀yP(x , y)∃x∃y¬P(x , y).

    • ∀x∃yP(x , y)∃x∀x¬P(x , y).

    • ∃x∀yP(x , y)∀x∃y¬P(x , y).

    • ∃x∃yP(x , y)∀x∀y¬P(x , y).

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 44 / 57

  • Negação com Quantificadores Agrupados

    Escreva a negação de cada uma das sentenças:

    • ∀x∀yP(x , y)∃x∃y¬P(x , y).

    • ∀x∃yP(x , y)∃x∀x¬P(x , y).

    • ∃x∀yP(x , y)∀x∃y¬P(x , y).

    • ∃x∃yP(x , y)∀x∀y¬P(x , y).

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 45 / 57

  • Negação com Quantificadores Agrupados

    Negue a sentença: ∀x∃y(xy = 1).

    ¬(∀x∃y(xy = 1)) ≡ ∃x¬(∃y(xy = 1))

    ≡ ∃x∀y(xy 6= 1)

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 46 / 57

  • Negação com Quantificadores Agrupados

    Negue a sentença: ∀x∃y(xy = 1).

    ¬(∀x∃y(xy = 1)) ≡ ∃x¬(∃y(xy = 1))

    ≡ ∃x∀y(xy 6= 1)

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 47 / 57

  • Tradução

    Considere C (x) : x tem um computador. e F (x , y) : x e y são amigos.

    Doḿınio: estudantes da UTFPR.

    Traduza: ∀x(C (x) ∨ ∃y(C (y) ∧ F (x , y)).

    Considere F (x , y) : x e y são amigos.

    Doḿınio: estudantes da UTFPR.

    Traduza: ∃x∀y∀z(F (x , y) ∧ F (x , z) ∧ y 6= z → ¬F (y , z)).

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 48 / 57

  • Tradução

    Considere C (x) : x tem um computador. e F (x , y) : x e y são amigos.

    Doḿınio: estudantes da UTFPR.

    Traduza: ∀x(C (x) ∨ ∃y(C (y) ∧ F (x , y)).

    Todos têm um computador ou têm um amigo que tem um computador.

    Considere F (x , y) : x e y são amigos.

    Doḿınio: estudantes da UTFPR.

    Traduza: ∃x∀y∀z(F (x , y) ∧ F (x , z) ∧ y 6= z → ¬F (y , z)).

    Existe um estudante tal que quaisquer dois amigos dele não são amigosentre si.

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 49 / 57

  • Tradução

    Traduza: Se uma pessoa é do sexo feminino e tem filhos, então ela é mãede alguém.

    P(x) : x é do sexo feminino.

    Q(x) : x tem filhos.

    M(x , y) : x é mãe de y .

    ∀x(P(x) ∧ Q(x)→ ∃yM(x , y)).

    Como y não aparece em P(x) ∧ Q(x), podemos reescrever:∀x∃y(P(x) ∧ Q(x)→ M(x , y)).

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 50 / 57

  • Tradução

    Traduza: Se uma pessoa é do sexo feminino e tem filhos, então ela é mãede alguém.

    P(x) : x é do sexo feminino.

    Q(x) : x tem filhos.

    M(x , y) : x é mãe de y .

    ∀x(P(x) ∧ Q(x)→ ∃yM(x , y)).

    Como y não aparece em P(x) ∧ Q(x), podemos reescrever:∀x∃y(P(x) ∧ Q(x)→ M(x , y)).

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 51 / 57

  • Tradução

    Traduza: Se uma pessoa é do sexo feminino e tem filhos, então ela é mãede alguém.

    P(x) : x é do sexo feminino.

    Q(x) : x tem filhos.

    M(x , y) : x é mãe de y .

    ∀x(P(x) ∧ Q(x)→ ∃yM(x , y)).

    Como y não aparece em P(x) ∧ Q(x), podemos reescrever:∀x∃y(P(x) ∧ Q(x)→ M(x , y)).

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 52 / 57

  • Tradução

    Traduza: Se uma pessoa é do sexo feminino e tem filhos, então ela é mãede alguém.

    P(x) : x é do sexo feminino.

    Q(x) : x tem filhos.

    M(x , y) : x é mãe de y .

    ∀x(P(x) ∧ Q(x)→ ∃yM(x , y)).

    Como y não aparece em P(x) ∧ Q(x), podemos reescrever:∀x∃y(P(x) ∧ Q(x)→ M(x , y)).

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 53 / 57

  • Tradução

    Traduza: Todos têm exatamente um melhor amigo.

    P(x , y) : x é o melhor amigo de y . Atenção: não inclua quantificadoresnos predicados!

    ∀y∃1xP(x , y).

    ∀y∃x(P(x , y) ∧ (∃zP(z , y)→ z = x)).

    ∀y∃x(P(x , y) ∧ (∀z(z 6= x → ¬P(z , y)))).

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 54 / 57

  • Tradução

    Traduza: Todos têm exatamente um melhor amigo.

    P(x , y) : x é o melhor amigo de y . Atenção: não inclua quantificadoresnos predicados!

    ∀y∃1xP(x , y).

    ∀y∃x(P(x , y) ∧ (∃zP(z , y)→ z = x)).

    ∀y∃x(P(x , y) ∧ (∀z(z 6= x → ¬P(z , y)))).

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 55 / 57

  • Tradução

    Traduza: Todos têm exatamente um melhor amigo.

    P(x , y) : x é o melhor amigo de y . Atenção: não inclua quantificadoresnos predicados!

    ∀y∃1xP(x , y).

    ∀y∃x(P(x , y) ∧ (∃zP(z , y)→ z = x)).

    ∀y∃x(P(x , y) ∧ (∀z(z 6= x → ¬P(z , y)))).

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 56 / 57

  • Tradução

    Traduza: Todos têm exatamente um melhor amigo.

    P(x , y) : x é o melhor amigo de y . Atenção: não inclua quantificadoresnos predicados!

    ∀y∃1xP(x , y).

    ∀y∃x(P(x , y) ∧ (∃zP(z , y)→ z = x)).

    ∀y∃x(P(x , y) ∧ (∀z(z 6= x → ¬P(z , y)))).

    Sheila Almeida (DAINF-UTFPR-PG) Predicados e Quantificadores junho - 2018 57 / 57

    Predicados e QuantificadoresDomínioOutros QuantificadoresPrioridade dos QuantificadoresFórmulas Bem Formadas (wffs)Escopo dos QuantificadoresTraduçãoQuantificadores Agrupados