Lógica Formal

Matemática Discreta

Prof° Marcelo Maraschin de Souza

Exercícios

Use lógica proposicional para provar os seguintes

argumentos:

a) 𝐴 ∧ 𝐵 → 𝐶 → 𝐵 → 𝐴 ∧ 𝐶

b) 𝐴 → 𝐵 ∨ 𝐶 ∧ 𝐵′ ∧ 𝐶′ → 𝐴′

c) 𝐴′ ∧ 𝐵 ∧ 𝐵 → 𝐴 ∨ 𝐶 → 𝐶

Exercícios

Use lógica proposicional para provar que o argumento é válido, utilize as

letras sugeridas em cada argumento:

a) Se o programa é eficiente, executa rapidamente; o programa é

eficiente ou tem algum bug. No entanto, o programa não executa

rapidamente. Logo, ele tem algum bug. E,R,B

b) Se Jane é a mais popular, ela será eleita. Se Jane é a mais popular,

então Carlos vai renunciar. Portanto, se Jane é a mais popular, ela

será eleita e Carlor renunciará. J,E,C

Exercícios

c) Se meu cliente fosse culpado, a faca estaria na gaveta. A faca não

estava na gaveta ou Jason Pritchard viu a faca. Se a faca não estava lá no

dia 10 de outubro, segue que Jason Pritchard não viu a faca. Além disso,

se a faca estava lá no dia 10 de outubro, então a faca estava na gaveta e o

martelo estava no celeiro. Mas todos sabemos que o martelo não estava

no celeiro. Portanto, senhoras e senhores do júri, meu cliente é inocente.

Proposições:

A - Cliente inocente

B - Faca na gaveta

C - Jason viu a faca

D - Faca estava no dia 10 de outubro

E - Martelo estava no celeiro

Lógica de primeira ordem

Também chamada de lógica de predicados.

Considere:

“Para todo x, x>0”

Poderíamos considerar essa afirmação verdadeira para os

números inteiros positivos, mas não conseguimos fazer

isso apenas utilizando proposições, conectivos lógicos e

parênteses.

Quantificador Universal

“Para todo x, x>0”

• São frases do tipo: “para todo”, “para cada”, “para

algum”.

• É simbolizado por ∀

• Então a sentença dada de exemplo fica:

“(∀x)(x>0)”

Predicado

“Para todo x, x>0”

• A frase “x>0” descreve uma propriedade da variável x,

neste caso, ser positiva. Chamamos uma propriedade

de predicado.

• É simbolizado por 𝑃 𝑥 , 𝑄 𝑥 ,…

• Então a sentença dada de exemplo fica:

“(∀x)(P(x))”

Conjunto Universo

“Para todo x, x>0”

• O conjunto universo é o domínio dos objetos no qual

estamos nos referindo.

• Neste exemplo, se o conjunto universo fosse os

números inteiros positivos, então o valor lógico da

sentença seria verdadeiro.

• Se o conjunto universo fosse qualquer número inteiro,

então o valor lógico da sentença seria falso.

Exemplo

Considere (∀x)(P(x))

• Conjunto universo: todos os livros da biblioteca.

• P(x): é um predicado de x ter capa vermelha.

• Qual é o valor lógico dessa expressão?

Exercício

Qual o valor lógico da expressão (∀x)(P(x)) em cada

expressão a seguir:

A. P(x) é o predicado em que x é amarelo e o conjunto

universo é o conjunto de todas as flores.

B. P(x) é o predicado em que x é verde e o conjunto

universo é o conjunto de todos os tipos de grama.

C. P(x) é o predicado em que x é positivo ou negativo e o

conjunto universo é o conjunto de todos os números.

Quantificador Existencial

“Existe algum x, x>0”

• São frases do tipo: “existe”, “há pelo menos um”, “existe

algum”,...

• É simbolizado por ∋

• Então a sentença dada de exemplo fica:

(∋ x)(x>0) ou (∋ x)(P(x))

Quantificador Existencial

(∋ 𝐱)(P(x))

Considere o caso da biblioteca:

• Conjunto universo: todos os livros da biblioteca.

• P(x): é um predicado de x ter capa vermelha.

Neste caso, o valor lógico é verdadeiro se tiver pelo

menos um livro de capa vermelha.

Exercício

• Dê um conjunto verdade e o significado de P(x) para

que (∋ 𝑥)(P(x)) tenha valor lógico verdadeiro.

• Dê um conjunto verdade e o significado de P(x) para

que (∀x)(P(x)) tenha valor lógico verdadeiro.

Predicado Binário

Exemplo:

(∀𝑥)(∋ 𝑦)(Q(x,y)) : “para todo x existe um y tal que Q(x,y)”

Considere o conjunto universo consiste dos números

inteiros e Q(x,y) é o predicado x < y.

“Para todo número inteiro existe um inteiro maior”

Valor lógico?

Predicado Binário

Exemplo:

(∋ 𝑦)(∀𝑥)(Q(x,y)) : “existe um y, para todo x, tal que Q(x,y)”

Considere o conjunto universo consiste dos números

inteiros e Q(x,y) é o predicado x < y.

“Existe um inteiro y que é maior que qualquer outro inteiro”

Valor lógico?

Constantes

Exemplo:

(∀𝑥) (Q(x,a)) : “para todo x, Q(x,a)”

Considere o conjunto universo consiste dos números

inteiros e Q(x,a) é o predicado x < a.

Suponha a=7.

Valor lógico?

Fbf’s Predicadas

Exemplo:

• 𝑷 𝒙 ∨ 𝑸 𝒙

• ∀𝒙 [𝑷 𝒙 → 𝑸 𝒙 ]

• ∀𝒙 ( ∋ 𝒚 𝑷 𝒙, 𝒚 ∧ 𝑸 𝒙, 𝒚 → 𝑹(𝒙))

Fbf’s Predicadas

Exemplo interpretativo:

∀𝑥 ∋ 𝑦 𝑃 𝑥, 𝑦 ∧ 𝑄 𝑦, 𝑎

• O escopo de ∋ 𝑦 é 𝑃 𝑥, 𝑦 ∧ 𝑄 𝑦, 𝑎 e o escopo de ∀𝑥 é (∋

Fbf’s Predicadas

Tradução Correta

Exemplo: “Todo papagaio é feio”.

Pode interpretar: “Dada uma coisa, se é papagaio, então é feio”.

Denote os predicados:

Conjunto universo: mundo inteiro

P(x) é a frase “x é um papagaio”

Q(x) é a frase “x é feio”

Temos que:

(∀𝑥)(𝑃 𝑥 → 𝑄(𝑥))

Fbf’s Predicadas

Tradução Incorreta

Exemplo: “Todo papagaio é feio”.

Denote os predicados:

Conjunto universos: mundo inteiro.

P(x) é a frase “x é um papagaio”

Q(x) é a frase “x é feio”

É incorreto:

(∀𝑥)(𝑃 𝑥 ^ 𝑄(𝑥))

Pois estaremos afirmando: “Todos no conjunto universo (mundo inteiro)

são papagaios feios”. (estaria correto só se o conjunto universo fosse

apenas os papagaios)

Fbf’s Predicadas

Tradução Correta

Exemplo: “Existe um papagaio feio”.

Pode interpretar: “Existe alguma coisa que é, ao mesmo tempo,

papagaio e feio”.

Denote os predicados:

Conjunto universo: mundo inteiro

P(x) é a frase “x é um papagaio”

Q(x) é a frase “x é feio”

Temos que:

(∋ 𝑥)(𝑃 𝑥 ^ 𝑄(𝑥))

Fbf’s Predicadas

Tradução Incorreta

Exemplo: “Existe um papagaio feio”.

Denote os predicados:

Conjunto universo: mundo inteiro

P(x) é a frase “x é um papagaio”

Q(x) é a frase “x é feio”

É incorreto: (∋ 𝑥)(𝑃 𝑥 → 𝑄(𝑥))

Essa fbf seria verdadeira se P e Q fossem verdade (1) ou se P fosse

falsa(2). O caso 2 seria possível se não existisse papagaios no mundo.

Fbf’s Predicadas

Ideia!!!

Escrever as frases com os conectivos lógicos e quatificadores.

João ama apenas Maria.

Apenas João ama Maria.

Reescreva:

Se João ama alguma coisa, então essa coisa é Maria.

Se alguma coisa ama Maria, então essa coisa é João.

Exercícios

1) Determine o valor lógico de cada fbf. Considere o conjunto universo

todos números inteiros, I(x) significa “x é ímpar”, L(x) que “x < 0” e

“G(x)” que “x > 9”.

a) ∋ 𝑥 𝐼(𝑥)b) ∀𝑥 𝐼 𝑥c) ∀𝑥 [𝐿 𝑥 → 𝐼(𝑥)]d) ∋ 𝑥 [𝐿 𝑥 → 𝐼(𝑥)]e) ∋ 𝑥 𝐿 𝑥 ^𝐺 𝑥

Exercícios

2) Determine o valor lógico de cada fbf. Onde o conjunto universo são

todos estados do Brasil, Q(x,y) significa “x está ao norte de y”, P(x) que “x

começa com a letra M” e A simboliza “Santa Catarina”

a) ∀𝑥 𝑃 𝑥b) ∋ 𝑦 ∋ 𝑥 𝑄(𝑦, 𝑥)c) ∀𝑥 ∋ 𝑦 𝑃 𝑦 ^ 𝑄 𝑥, 𝑦d) ∋ 𝑦 𝑄(𝐴, 𝑦)

Exercícios

3) Usando os símbolos predicados e quantificadores, escreva cada

declaração como uma fbf predicada. O conjunto universo é o mundo

inteiro.

D(x) é “x é um dia”S(x) é “x é ensolarado”C(x) é “x é chuvoso”

M é “segunda-feira”

T é “terça-feira”

a) Todos os dias são ensolarados.

b) Alguns dias não são chuvosos.

c) Todo dia ensolarado não é chuvoso.

d) Alguns dias são ensolarados e chuvosos.

Exercícios

D(x) é “x é um dia”S(x) é “x é ensolarado”C(x) é “x é chuvoso”

M é “segunda-feira”

T é “terça-feira”

e) Nenhum dia é, ao mesmo tempo, ensolarado e chuvoso.

f) É sempre um dia ensolarado só se for um dia chuvoso.

g) Nenhum dia é ensolarado

h) A segunda-feira foi ensolarada; portanto, todos os dias serão

ensolarados

i) Choveu na segunda-feira e na terça-feira