Cap. 1 - Linguagem Matemática e Lógica Informal

Question 1

Princípio da Não Contradição?

Answer 1

Uma proposição não pode ser verdadeira e falsa ao mesmo tempo.

Question 2

Princípio do Terceiro Excluído?

Answer 2

Ou é vdd ou é falsa.

Question 3

Como fica. a equivalência traduzida de símbolo para português?

Answer 3

Se e só se.

Question 4

O que torna uma fórmula bem formulada válida/não válida?

Answer 4

O facto de ser uma tautologia/não ser uma tautologia, ou seja, verdade para qualquer interpretação.

Question 5

O que torna uma fbf inconsistente? Qual é a diferença para uma fbf não válida?

Answer 5

É que seja o simétrico de uma tautologia, ou seja, falsa para qualquer interpretação.

Question 6

Como é que se prova a equivalência entre duas fbfs?

Answer 6

São equivalentes se a sua tabela de verdade for uma tautologia.

Question 7

Modus ponens?

Answer 7

[p ∧ (p ⇒ q)] ⇒ q

Question 8

Modus tollens?

Answer 8

[(p ⇒ q) ∧ ¬q] ⇒ ¬p

Question 9

Silogismo hipotético?

Answer 9

[(p ⇒ q) ∧ (q ⇒ r)] ⇒ (p ⇒ r)

Question 10

Como sabemos se um conjunto é subconjunto próprio de um outro conjunto?

Answer 10

B é subconjunto prórpio de B se B ⊂ A e B ≉ A.

Tal que exista pelo menos um x ∈ A e x ∉ B.

Question 11

O que resulta da diferença simétrica entre dois conjuntos?

Answer 11

Resulta o conjunto formado pelos elementos que estão nos dois conjuntos menos na sua interseção.

Question 12

Que conjunto resulta do produto cartesiano entre dois conjuntos A e B

Answer 12

A × B = {(x, y) : x ∈ A ∧ y ∈ B}

Question 13

Todas as relações binárias são um subconjunto do produto cartesiano entre esses conjuntos em causa.

Answer 13

OK

Question 14

O que faz uma Relação Reflexiva?

Answer 14

Se (x, x) ∈ R.

Question 15

O que faz uma Relação Simétrica?

Answer 15

Se (x, y) ∈ R ⇒ (y, x) ∈ R

Question 16

O que faz uma Relação Anti-Simétrica?

Answer 16

Se [(x, y) ∈ R ∧ (y, x) ∈ R] ⇒ x = y

Question 17

O que faz uma Relação Transitiva?

Answer 17

Se [(x, y) ∈ R ∧ (y, z) ∈ R] ⇒ (x, z) ∈ R

Question 18

O que compõe um relação de ordem parcial?

Answer 18

RAT

Question 19

O que compõe um relação de equivalência?

Answer 19

RST

Question 20

Qual é a definnição de classe de equivalência?

Answer 20

[x] = {y ∈ A : (x, y) ∈ R}

Question 21

O que é o conjunto quociente?

Answer 21

É o conjunto de todas as classes de equivalência de um dado conjunto A.

Question 22

O que são partições de um conjunto?

Answer 22

São subconjuntos das partes de um conjunto.

Question 23

Teorema sobre as relações de equivalência e as suas partições:

Answer 23

Se R é uma relação de equivalência, então o conjunto quociente A/R é uma partição de A.

Question 24

Condição para ser função?

Answer 24

Um elemento do conjnunto de partida corresponder a apenas um elemento do conjunto de chegada.

Question 25

Qual a condição para uma função ser considerada injetiva?

Answer 25

f(x) = f(y) ⇒ x = y

A objetos diferentes correspondem imagens diferentes.

Não podem existir objetos diferentes com a mesma imagem.

Question 26

Qual a condição para uma função ser considerada sobrejetiva?

Answer 26

A todo o elemento no conjunto de chegada corresponde um elemento no conjunto de partida.

Não pode haver um elemento no conjunto de chegada que não tenha um elemento correspondido no conjunto de partida.

Question 27

Qual a condição para que uma função seja invertível?

Answer 27

Tem de ser bijetiva.

Question 28

Passos a tomar para se encontrar a função inversa de uma função?

Answer 28

1. Partir de f(x) = y.
2. Resolver em ordem a x.
3. Substituir y por x.

Question 29

Que condição define conjuntos como equipotentes?

Answer 29

A condição que constata que tem de existir uma bijeção entre os dois conjuntos.

Ou seja é possível establecer um função bijetiva entre os dois conjuntos.

Question 30

O que são conjuntos equipotentes?

Answer 30

Conjuntos com o mesmo número de elementos, ou com o mesmo cardinal.

Question 31

Teorema: Comparação da cardinalidade entre dois conjuntos injetivos entre si.

Answer 31

Dados dois conjuntos A e B, a cardinalidade de A não é superior à de B se existe uma função injetiva entre os dois.

Question 32

Condições para que um conjunto seja numerável?

Answer 32

Seja finito ou equipotente ao conjunto N.

Question 33

O que constata o teorema de Dedekind-Cantor?

Answer 33

Um conjunto é infinito se e só se é equipotente a um
subconjunto próprio.

Ou seja um dado conjunto é infinito se tiver o mesmo número de elementos que um subconjunto próprio.

Question 34

O que constata o teorema de Schröder-Bernstein?

Answer 34

É uma propriedade transitiva entre conjuntos:

Sejam X e Y dois conjuntos.

Se f : X → Y e g : Y → X são
funções injectivas, então existe uma bijecção h : X → Y.

Question 35

Como se define um termo? O que pode ser considerado um termo?

Answer 35

Uma constante, uma variável e funções cujos argumentos sejam termos são consideradas também elas termos.

Exemplos:

1) 12;
2) y;
3) pai de(Luisa).

Question 36

Como se define um predicado?

Answer 36

Um predicado é uma função que a uma dada lista de
constantes faz corresponder um valor lógico.

Exemplo:
Maior(x, y) é um predicado que traduz a relação “x é maior do que y”.

Question 37

Como se define um átomo?

Answer 37

Um átomo é a junção um predicado, ou seja, uma função que relaciona duas constantes, com termos, ou seja, os argumentos do predicados são termos, se assim for essa expressão toda é um átomo.

Question 38

Neste caso identifique o alcançe de cada um dos quantificadores:

(∀ x) (∃ y) (P(x, y)).

Answer 38

Alcance de ∀: (∃ y) (P(x, y)).

Alcance de ∃: P(x, y).

Question 39

Como se identifica uma variaável livre? E uma variável ligada?

Answer 39

Se estiver no alcançe de um qualquer quantificador então essa variável diz-se ligada, se não é livre.

Exemplos

1) ∀ x (P(x, y)); —-> x é ligado, y é livre
2) ∀ x (P(x, y) ∨ ∀ y (Q(y)));; —-> x é ligado, y é ligado e livre
3) ∀ x (P(x)) ⇒ Q(x).; —-> x é ligado e livre

Question 40

Quais são as fórmulas que não podem ser avaliadas?

Answer 40

Fórmulas com variáveis livres.

A menos que se introduza uma função que atribui valores no domínio D às variáveis livres.

Question 41

O que é necessário para que uma fórmula seja consederada válida/inválida?

Answer 41

Uma fórmula F diz-se válida (ou uma tautologia) se é
verdadeira para qualquer das suas possíveis interpretações e diz-se não válida (ou inválida) se não é válida.

Exemplo
A fórmula (∀ x) (P(x) ⇒ P(x)) é válida.

Question 42

O que é necessário para que uma fórmula seja consederada consistente/inconsistente?

Answer 42

Uma fórmula F diz-se inconsistente (ou uma contradição) se é falsa qualquer que seja a sua interpretação e diz-se consistente se não é inconsistente.

Exemplo
A fórmula (∃x) (P(x) ∧ ¬(P(x))) é inconsistente.

Question 43

O que constata o teorema da consequência lógica?

Answer 43

Dadas fórmulas F1(…) e uma fórmula G, a fórmula G é consequência lógica de F1(….) se e só se:

(F1 ∧ F2 ∧ F3 · · · ∧ Fn) ⇒ G

for uma fórmula válida, ou seja, uma tautologia.

Question 44

Que condições são precisas para que uma fórmula esteja na forma normal prenex?

Answer 44

Se estiver na seguinte forma:

(Q1x1)(Q2x2) … (Qnxn) M

Ou seja, todos os quantificadores à esquerda da fórmula em si, dada por M.

Exemplos:
(∀x)(∀y)(P(x, y) ∧ Q(y));
(∀x)(∀y)(¬P(x, y) ∨ Q(y));
(∀x)(∀y)(∃z)(Q(x, y) ∨ R(z));
(∀x)(∀y)(∃z)(Q(x, y) ⇒ R(z)).

Question 45

Qual é a definição de literal?

Answer 45

Um literal é um átomo ou a negação de um átomo.

Dois literais dizem-se complementares quando um é a negação do outro.

Question 46

Qual é a condição para que uma fórmula esteja na fórmula normal conjuntiva?

Answer 46

Seja uma conjunção de fórmulas. ∧

P ∨ ¬Q ∨ R) ∧ (¬P ∨ Q

Question 47

Qual é a condição para que uma fórmula esteja na fórmula normal dijuntiva?

Answer 47

Seja uma dijunção de fórmulas. ∨

P ∧ R) ∨ (¬P ∧ Q

Question 48

O que é uma cláusula?

Answer 48

É uma dijunção (∨) de um conjunto de literais (átomos) finitos:

P(x) ∨ Q(a) ∨ ¬R(y)
¬P(x, f(x)) ∨ Q(x, f(x), g(x))

Question 49

Ligação entre o conjunto de cláusulas e a forma normal conjuntiva?

Answer 49

O conjunto de cláusulas

S = {¬P(x, f(x)) ∨ Q(x, f(x), g(x)), T(x, f(x)), R(y)}

corresponde à fórmula (na forma normal conjuntiva)

(¬P(x, f(x)) ∨ Q(x, f(x), g(x))) ∧ T(x, f(x)) ∧ R(y).

Question 50

Quais são as condições para que uma fórmula esteja na forma normal de Skolem?

Answer 50

É uma conjunção de cláusulas (dijunção (∨) de um conjunto de literais) universalmente quantificadas, ou seja,
sem variáveis livres e sem quantificadores existenciais.

Exemplos:
∀x∀y(P(x) ∨ ¬Q(a, y))
∀y∀z(¬Q(g(y, f(z))) ∨ ¬P(b))

Question 51

Como se procede à redução de fórmulas normais prenex à fórmula normal de Skolem de modo a que possam ser demonstrados Teoremas?

(∀x)(∃y)(∃z)((¬P(x, y) ∨ Q(x, z))

Answer 51

(∀x)(∃y)(∃z)((¬P(x, y) ∨ Q(x, z))

• Uma vez que (∃y) e (∃z) são precedidos por (∀x), as
variáveis y e z são substituídas, respectivamente, pelas
funções de uma variável f(x) e g(x).

• Logo, obtém-se

(∀x)((¬P(x, f(x)) ∨ Q(x, g(x))).

Question 52

Como se procede, usando o princípio de Robinson, à resolução de problemas?

Answer 52

Está no slide 5 do LPO4 o exemplo.

Question 53

Exemplo de substituição de variaveis?

Answer 53

Está no slide 4 da LPO5

Question 54

Exemplo da aplicação do unificador mais geral?

Answer 54

Está no último slide da LPO5

Question 55

Qual é a definição de factor?

Answer 55

Dado o unificador mais geral (σ) de uma cláusula C, então o factor de C é Cσ

Exemplo:
C = P(x) ∨ P(f(y)) ∨ Q(x)
σ = {f(y)/x}.

Então

Cσ = P(f(y)) ∨ Q(f(y))

é um factor de C.

Question 56

Qual é a definição de resolvente binária dadas duas cláusulas?

Answer 56

Dadas duas cláusulas (dijunção (∨) de um conjunto de literais (átomos)) que não tenham variável em comum.

E dois literais, onde L1 e ¬L2 têm o mesmo u.m.g então a seguinte expressão é a resolvente binária das duas cláusulas:

(C1σ − L1σ) ∪ (C2σ − L2σ)

Exemplo:

C1 : P(x) ∨ Q(x); C2 : ¬P(a) ∨ R(y)
L1 : P(x); ¬L2 : P(a)
σ = {a/x}

(C1σ − L1σ) ∪ (C2σ − L2σ) = Q(a) ∨ R(y)

Logo, Q(a) ∨ R(y) é a resolvente binária de C1 e C2.

Question 57

Se existe uma bijeção entre dois conjuntos o que se pode concluir face à sua cardinalidade?

Answer 57

Que são iguais.