Lesson test: Proof with quantifiers

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Proof with quantifiers

1.[3p]
Universal introduction requires that the name being generalised

occurs in no premise and in no assumption still open

Correct

occurs in at least one premise

The answer is: occurs in no premise and in no assumption still open

has never appeared before in the proof

The answer is: occurs in no premise and in no assumption still open

names an object in the domain

The answer is: occurs in no premise and in no assumption still open

2.[3p]
Existential elimination requires a fresh name that

does not occur in the premises, in earlier available lines, or in the conclusion drawn

Correct

occurs in the conclusion drawn

The answer is: does not occur in the premises, in earlier available lines, or in the conclusion drawn

is the same as the name used for every other existential premise

The answer is: does not occur in the premises, in earlier available lines, or in the conclusion drawn

has been introduced by universal elimination first

The answer is: does not occur in the premises, in earlier available lines, or in the conclusion drawn

3.[3p]
From $\exists x O x$ and $\exists x E x$ , someone derives $\exists x (O x \land E x)$ . Which restriction was broken?

The same name was taken as witness for both existentials, breaking freshness

Correct

Universal introduction was applied to a name in a premise

The answer is: The same name was taken as witness for both existentials, breaking freshness

The conclusion contains a fresh name

The answer is: The same name was taken as witness for both existentials, breaking freshness

Existential introduction cannot replace all occurrences of a name

The answer is: The same name was taken as witness for both existentials, breaking freshness

4.[3p]
Put these steps in the order they occur in the derivation of $\forall x (S x \to F x)$ from $\forall x (M x \to F x)$ and $\forall x (S x \to M x)$ .

Generalise to $\forall x (S x \to F x)$
Derive $M a$ , then $F a$
Assume $S a$
Close the subproof and write $S a \to F a$

Show the answer

a, b, c, d

5.[2p]
$\exists y \forall x R x y$ entails $\forall x \exists y R x y$ .

True

Correct

False

The answer is: True

6.[2p]
$\forall x \exists y R x y$ entails $\exists y \forall x R x y$ .

True

The answer is: False

False

Correct

7.[2p]
In an existential elimination subproof, what must the assumed name be? One word.

CorrectNot quite: fresh

8.[3p]
Completeness and undecidability together mean that

every valid formula has a proof, but no procedure says in advance whether the search will succeed

Correct

some valid formulas have no proof

The answer is: every valid formula has a proof, but no procedure says in advance whether the search will succeed

proofs cannot be checked mechanically

The answer is: every valid formula has a proof, but no procedure says in advance whether the search will succeed

validity can be decided given enough time

The answer is: every valid formula has a proof, but no procedure says in advance whether the search will succeed

9.[3p]
Why does almost every existential elimination end by applying existential introduction inside the subproof?

It removes the fresh name, so the conclusion may leave the subproof

Correct

It shortens the proof

The answer is: It removes the fresh name, so the conclusion may leave the subproof

Existential introduction is the only rule allowed inside a subproof

The answer is: It removes the fresh name, so the conclusion may leave the subproof

The fresh name must appear in the conclusion

The answer is: It removes the fresh name, so the conclusion may leave the subproof

1.[3p] Universal introduction requires that the name being generalised

2.[3p] Existential elimination requires a fresh name that

3.[3p] From ∃xOx and ∃xEx, someone derives ∃x(Ox∧Ex). Which restriction was broken?

4.[3p] Put these steps in the order they occur in the derivation of ∀x(Sx→Fx) from ∀x(Mx→Fx) and ∀x(Sx→Mx).

5.[2p] ∃y∀xRxy entails ∀x∃yRxy.

6.[2p] ∀x∃yRxy entails ∃y∀xRxy.

7.[2p] In an existential elimination subproof, what must the assumed name be? One word.

8.[3p] Completeness and undecidability together mean that

9.[3p] Why does almost every existential elimination end by applying existential introduction inside the subproof?

1.[3p]
Universal introduction requires that the name being generalised

2.[3p]
Existential elimination requires a fresh name that

3.[3p]
From $\exists x O x$ and $\exists x E x$ , someone derives $\exists x (O x \land E x)$ . Which restriction was broken?

4.[3p]
Put these steps in the order they occur in the derivation of $\forall x (S x \to F x)$ from $\forall x (M x \to F x)$ and $\forall x (S x \to M x)$ .

5.[2p]
$\exists y \forall x R x y$ entails $\forall x \exists y R x y$ .

6.[2p]
$\forall x \exists y R x y$ entails $\exists y \forall x R x y$ .

7.[2p]
In an existential elimination subproof, what must the assumed name be? One word.

8.[3p]
Completeness and undecidability together mean that

9.[3p]
Why does almost every existential elimination end by applying existential introduction inside the subproof?