Lógica de Predicados

Quantificadores

Conteúdo

� Correção de Exercício� Quantificadores – Rosen (pg 33)� Tradução Português – Lógica – Rosen (pg 42)

Exercícios Rosen – pg 46

1) Considere P(x) como o predicado “x� 4”. Quais são os valores verdade das proposições abaixo?

a) P(0)b) P(4)c) P(6)

Exercícios Rosen – pg 46

1) Considere P(x) como o predicado “x� 4”. Quais são os valores verdade das proposições abaixo?

a) P(0) é Verdadeb) P(4) é Verdadec) P(6) é Falso

Exercícios Rosen – pg 46

2) Considere P(x) como o predicado “a palavra x contém a letra a”. Quais são os valores verdade das proposições abaixo?

a) P(orange)b) P(lemon)c) P(true)d) P(false)

Exercícios Rosen – pg 46

2) Considere P(x) como o predicado “a palavra x contém a letra a”. Quais são os valores verdade das proposições abaixo?

a) P(orange) é Verdadeb) P(lemon) é Falsoc) P(true) é Falsod) P(false) é Verdade

Exercícios Rosen – pg 46

3) Considere Q(x,y) como o predicado “x é a capital de y”. Quais são os valores verdade das proposições abaixo?

a) Q(Denver, Colorado)

Exercícios Rosen – pg 46

3) Considere Q(x,y) como o predicado “x é a capital de y”. Quais são os valores verdade das proposições abaixo?

a) Q(Denver, Colorado) é Verdadeb) Q(Detroit, Michigan)

Exercícios Rosen – pg 46

3) Considere Q(x,y) como o predicado “x é a capital de y”. Quais são os valores verdade das proposições abaixo?

a) Q(Denver, Colorado) é Verdadeb) Q(Detroit, Michigan) é Falso capital é Lansingc) Q(Massachusetts, Boston)

Exercícios Rosen – pg 46

3) Considere Q(x,y) como o predicado “x é a capital de y”. Quais são os valores verdade das proposições abaixo?

a) Q(Denver, Colorado) é Verdadeb) Q(Detroit, Michigan) é Falso capital é Lansingc) Q(Massachusetts, Boston) é Verdaded) Q(Nova York, Nova York)

Exercícios Rosen – pg 46

3) Considere Q(x,y) como o predicado “x é a capital de y”. Quais são os valores verdade das proposições abaixo?

a) Q(Denver, Colorado) é Verdadeb) Q(Detroit, Michigan) é Falso capital é Lansingc) Q(Massachusetts, Boston) é Verdaded) Q(Nova York, Nova York) é F capital é Albany

Quantificadores

� São frases do tipo:� “para todo”� “para cada”� “para algum”

� Ou seja, frases que dizem quantos objetos, em algum sentido, têm uma determinada propriedade.

Quantificadores - Tipos

� Universal: � considera todos os elementos de um conjunto

� Existencial:� Existe um ou mais elementos de um conjunto.

Quantificador Universal

� Propriedade é verdadeira para todos os valores de uma variável em um determinado domínio, ou seja, todos os elementos do domínio tornam o predicado verdadeiro.

� Domínio = Conjunto Verdade

� Símbolo Usado: ∀

Quantificador Universal

� Notação:� (∀ x ∈ A) (P(x)) � ∀ x ∈ A, P(x)� ∀ x ∈ A: P(x) � (∀ x ) P(x)� ∀ x, P(x)� ∀ x: P(x)� ∀ x P(x)

Quantificador Universal

� Seja A = {a1,a2, ... , an} o domínio considerado para o predicado P(x).

� Então ∀x P(x) equivale à conjunção das proposições.

∀ x P(x) � P(a1)^ P(a2) ^ ... P(an)

Quantificador Universal

� Seja A = {a1,a2, ... , an} o domínio considerado para o predicado P(x).

� Então ∀ x P(x) equivale à conjunção das proposições.

∀ x P(x) � P(a1)^ P(a2) ^ ... ^P(an)

� Sendo assim ao usarmos o quantificador universal no predicado este torna se uma proposição pois tem um valor verdade.

Quantificador Universal

� Exemplo:A= {3,5,7}P(x) = “x é primo”∀ x P(x) é ???

Quantificador Universal

� Exemplo:A= {3,5,7}P(x) = “x é primo”∀ x P(x) é Verdade

� Um elemento para o qual P(x) é falsa é chamado de contra exemplo para ∀ x P(x) e torna ∀ x P(x) falso também.

Quantificador Universal

� Exemplo:

P(x) = “x +1 > x”Domínio: o conjunto dos números reais.

∀ x P(x) é ?

Quantificador Universal

� Exemplo:

P(x) = “x +1 > x”Domínio: o conjunto dos números reais.

∀ x P(x) é Verdade

Quantificador Universal

� Exemplo:

Q(x) = “x < 2”Domínio: o conjunto dos números reais

∀ x Q(x) é ???

Quantificador Universal

� Exemplo:

Q(x) = “x < 2”Domínio: o conjunto dos números reais

Q(3) é Falso logo ∀ x Q(x) é Falso

Contra exemplo

Quantificador Existencial

� Propriedade é verdadeira para pelo menos um valor de uma variável em um determinado domínio, ou seja, existe um elemento do domínio que torna o predicado verdadeiro.

� Símbolo Usado: ∃

Quantificador Existencial� Exemplo

P(x) = “x é aluno de fundamentos 1 que tem N1=10.0”

Domínio = {alunos desta sala}

Podemos escrever que: ∃ x P(x)

Quantificador Existencial

� Notação:� (∃ x ∈ A) (P(x)) � ∃ x ∈ A, P(x)� ∃ x ∈ A: P(x) � (∃ x ) P(x)� ∃ x, P(x)� ∃ x: P(x)� ∃ x P(x)

Quantificador Existencial

� Seja A = {a1,a2, ... , an} o domínio considerado para o predicado P(x).

� Então ∃ x P(x) equivale à disjunção das proposições.

∃ x P(x) � P(a1) v P(a2) v ... v P(an)

Quantificador Existencial

� Seja A = {a1,a2, ... , an} o domínio considerado para o predicado P(x).

� Então ∃ x P(x) equivale à disjunção das proposições.

∃ x P(x) � P(a1) v P(a2) v ... v P(an)

� Sendo assim ao usarmos o quantificador existencial no predicado este torna se uma proposição pois tem um valor verdade.

Quantificador Existencial

Exemplo: P(x) = “x > 3”Domínio: conjunto dos números reais.Temos que 4 > 3 logo ∃ x P(x) é V

Quantificador Existencial

� ∃ x P(x) será falso quando o conjunto verdade for vazio.

� Exemplo:(∃ n ∈N) (n+4<8)

O Conjunto Verdade = {0,1,2,3}, logo a proposição é verdadeira

∃ x P(x) é Verdade

Quantificador Existencial

� ∃ x P(x) será falso quando o conjunto verdade for vazio.

� Exemplo:(∃ n ∈N) (n+4 < 4)

O Conjunto Verdade = { }, logo o predicado é falso

∃ x P(x) é Falso

Quantificadores

� Existe um número não limitado de quantificadores que podemos definir tais como:� “existem exatamente dois” � “existem não mais de três”� “existe um único x tal que P(x) é verdadeiro”

Quantificadores

� Existe um número não limitado de quantificadores que podemos definir tais como� “existem exatamente dois” � “existem não mais de três”� “existe um único x tal que P(x) é verdadeiro”

Quantificador de Unicidade

Quantificadores

� Existe um número não limitado de quantificadores que podemos definir tais como� “existem exatamente dois” � “existem não mais de três”� “existe um único x tal que P(x) é verdadeiro”

Quantificador de Unicidade

∃!x P(x) ou ∃1x P(x)

Traduzindo do Português

Todo estudante desta classe estudou lógica.

Como podemosrepresentar isso na lógica?

Traduzindo do Português

� Todo estudante desta classe estudou lógica.

1) Definir o predicadoC(x) = “x estudou lógica”

Traduzindo do Português

� Todo estudante desta classe estudou lógica.

1) Definir o predicadoC(x) = “x estudou lógica”

2) Definir o domínioDomínio = {estudantes desta classe}

Traduzindo do Português

� Todo estudante desta classe estudou lógica.

1) Definir o predicadoC(x) = “x estudou lógica”

2) Definir o domínioDomínio = {estudantes desta classe}

3) Escrever a proposição: ∀x C(x)

Traduzindo do Português

� Todo estudante desta classe estudou lógica.

1) Definir o predicadoC(x) = “x estudou calculo”

2) Definir o domínioDomínio = {estudantes desta classe}

3) Escrever a proposição: ∀x C(x)

Existem várias maneiras de tradução!!!!

Negando Expressões Quantificadas

� Não é o caso de todos os estudantes desta classe terem feito aulas de lógica.

~ ∀∀∀∀x P(x)

Negando Expressões Quantificadas

� Não é o caso de todos os estudantes desta classe terem feito aulas de lógica.

~ ∀∀∀∀ x P(x)

� Existe um estudante desta classe que não teve aula de lógica.

∃x ~P(x)

Podemos reformular a frase para:

Negando Expressões Quantificadas

� Não é o caso de todos os estudantes desta classe terem feito aulas de lógica.

~∀x P(x)� Existe um estudante desta classe que não

teve aula de lógica.∃x ~P(x)

~ ∀ x P(x) � ∃ x ~P(x)

Ilustramos que:

Negando Expressões Quantificadas

� Existe um estudante na classe que teve aulas de calculo.

∃ x P(x)� Não é o caso de existir um estudante na

classe que teve aulas de calculo.~ ∃ x P(x)

Negando Expressões Quantificadas

� Não é o caso de existir um estudante na classe que teve aulas de calculo.

~ ∃ x P(x)

� Todo os estudantes nesta classe não tiveram aulas de calculo.

∀x ~P(x)

Podemos reformular a frase para:

Negando Expressões Quantificadas

� Não é o caso de existir um estudante na classe que teve aulas de calculo.

~ ∃ x P(x)Todo os estudantes nesta classe não tiveram

aulas de calculo.∀x ~P(x)

~ ∃ x P(x) � ∀x ~P(x) Ilustramos que:

Negando Expressões Quantificadas

� As regras para negações de quantificadoressão chamadas de Leis de De Morgan para quantificadores.

~ ∀ x P(x) � ∃x ~P(x)~ ∃ x P(x) � ∀ x ~P(x)

Rosen Pg 46 Ex. 5

� Considere P(x) como o predicado “x passa mais do que cinco horas em aula todos os dias”, em que o domínio de x são todos os estudantes. Expresse cada uma dessas quantificações em português.

a) ∃ x P(x) b) ∀ x P(x)c) ∃ x ~P(x) d) ∀ x ~P(x)

Exercícios

1) Quais as negações de:a) “Existe um político honesto”b) “Todos os brasileiros comem churrasco”

2) Negar ∀x (x2 > x)3) Negar ∃x (x2 = x)

Exercício 1)

1) “Existe um político honesto”H(x) = “x é honesto”Domínio = {todos os políticos}

Como fica a proposição???

Exercício 1)

1) “Existe um político honesto”H(x) = “x é honesto”Domínio = {todos os políticos}

∃x H(x)

Exercício 1)

1) “Existe um político honesto”H(x) = “x é honesto”Domínio = {todos os políticos}

∃ x H(x) negando ~ ∃ x H(x)

Exercício 1)

1) “Existe um político honesto”H(x) = “x é honesto”Domínio = {todos os políticos}

∃ x H(x) negando ~ ∃ x H(x) Sabemos que ~ ∃ x H(x) � ∀x ~H(x)Então podemos dizer que: ....

Exercício 1)

1) “Existe um político honesto”H(x) = “x é honesto”Domínio = {todos os políticos}

∃ x H(x) negando ~ ∃ x H(x) Sabemos que ~ ∃ x H(x) � ∀x ~H(x)Então podemos dizer que: Todos os políticos são desonestos.

Exercício 1b

“Todos os brasileiros comem churrasco”

C(x) = “x como churrasco”Domínio = {todos os brasileiros}

Como fica a proposição???

Exercício 1b

“Todos os brasileiros comem churrasco”C(x) = “x como churrasco”Domínio = {os brasileiros}

∀∀∀∀x P(x)

Exercício 1b

“Todos os brasileiros comem churrasco”P(x) = “x como churrasco”Domínio = {todos os brasileiros}

x P(x) ~ ∀∀∀∀x P(x)

Exercício 1b

“Todos os brasileiros comem churrasco”P(x) = “x como churrasco”Domínio = {todos os brasileiros}

∀∀∀∀x P(x) ~ ∀∀∀∀x P(x) � ∃x ~P(x)

Exercício 1b

“Todos os brasileiros comem churrasco”P(x) = “x como churrasco”Domínio = {todos os brasileiros}

∀∀∀∀x P(x) ~ ∀∀∀∀x P(x) � ∃x ~P(x)

Existe pelo menos um brasileiro que não come churrasco.Algum brasileiro não come churrasco.

2) Negar ∀∀∀∀x (x2 > x)

2) Negar ∀∀∀∀x (x2 > x)~ ∀∀∀∀x (x2 > x) � ????

2) Negar ∀∀∀∀x (x2 > x)~ ∀∀∀∀x (x2 > x) � ∃x ~ (x2 > x) � ????

2) Negar ∀∀∀∀x (x2 > x)~ ∀∀∀∀x (x2 > x) � ∃x ~ (x2 > x) � ????∃x (x2 � x)

Qual????

Exercícios

Negar ∃x (x2 = x)

Exercícios

Negar ∃x (x2 = x)~ ∃x (x2 = x) � ????

Exercícios

Negar ∃x (x2 = x)~ ∃x (x2 = x) � ∀∀∀∀x ~(x2 = x) � ????

Exercícios

Negar ∃x (x2 = x)~ ∃x (x2 = x) � ∀∀∀∀x ~(x2 = x) � ????∀∀∀∀x (x2 � x)

É Verdade?

Exercícios – Rosen(47 e 48)

� 6 � 11� 12� 13� 14� 34