1

Logică matematica si computaţională

33

Care dintre următoarele enunţuri este adevărat?

a. o mulţime compatibilă de formule H este un sistem deductiv dacă este punct fix al operatorului de

deductibilitate;

b. o mulţime compatibilă de formule H este un sistem deductiv dacă şi numai dacă este punct fix al

operatorului de deductibilitate

c. o mulţime compatibilă de formule H este un sistem deductiv dacă şi numai dacă este punct fix al

operatorului de inferenţă.

b

25

După aplicarea regulilor de inferenţă formulele rezultate au adâncime:

a. mai mare;

b. mai mică;

c. nemodificată

b

38

Enunţul “mulţimea de formule H este consistentă dacă şi numai dacă este finit validabilă” constituie:

a. teorema de consistenţă a calculului cu propoziţii;

b. teorema de completitudine a limbajului calculului cu propoziţii;

c. teorema de compacitate a limbajului calculului cu propoziţii.

c

35

Enunţul “orice formulă demonstrabilă a limbajului calculului cu propoziţii este tautologie” constituie:

a. teorema Herbrand;

b. teorema de consistenţă a calculului cu propoziţii; c. teorema de completitudine a limbajului calculului cu propoziţii;

d. teorema Lindenbaum Tarski .

c

29

Enunţul “orice teoremă este tautologie” constituie:

a. teorema deducţiei;

b. teorema de consistenţă a calculului cu propoziţii;

c. teorema de inferenţă.

b

20

{ }

( ){ }H

H

α

α

⇒ Γ ∪

∪ ⇒ Γeste o:

a. regulă de deducţie Gentzen;

b. regulă de deducţie Herbrand;

c. regulă de inferenţă Herbrand;

d. regulă de inferenţă Gentzen.

d

16

Fie FORMΓ ⊂ ; atunci:

A. { },α β |Γ dacă ( ){ }α β∧ |Γ

B. ( ){ }α β∧ |Γ dacă { },α β |Γ

a. A b. A+B c. B

b

5

Fie axioma AXIOMα ∈ şi substituţia SUBSTσ ∈ . Atunci, ασ se numeşte:

a. instanţiere a formulei ασ ;

b. instanţiere a axiomei ασ ;

c. instanţiere a substituţiei ασ .

b

2

34

Fie D un sistem deductiv. Care dintre implicaţii este adevărată?

a. D maximal atunci D complet;

b. D complet atunci D maximal;

c. ambele;

d. nici una.

c

1

Fie formula FORMα ∈ şi funcţia :h FORM N→ definită prin:

( ) ( )

( ) ( ){ } { }

0,

1 ,

1 max , , , \

daca V

h h daca

h h daca L

α

α β α β

β γ α βργ ρ

∈

= + =

+ = ∈

Funcţia h reprezintă:

a. adâncimea arborelui de structură corespunzător formulei α;

b. numărul de frunze ale arborelui de structură corespunzător formulei α;

c. numărul maxinm de descendenţi direcţi ai unui nod din arborele de structură

corespunzător formulei α.

a

2

Fie formula FORMα ∈ şi funcţia :h FORM N→ definită prin:

( ) ( )

( ) ( ){ } { }

0,

1 ,

1 max , , , \

daca V

h h daca

h h daca L

α

α β α β

β γ α βργ ρ

∈

= + =

+ = ∈

Funcţia h reprezintă:

a. numărul total de propoziţii elementare care apar în formula α;

b. numărul total de simboluri care apar în formula α;

c. numărul total de conective logice care apar în formula α.

c

4

Fie formula FORMα ∈ şi substituţia SUBSTσ ∈ . Rezultă că:

a. SUBSTασ ∈

b. FORMασ ∈

c. AXIOMασ ∈

b

8

Fie formula FORMα ∈ ; ea se numeşte teoremă dacă 1,..., nFORMα α∃ ∈ astfel încât:

a. ∀ i, 1 ≤ i ≤ n: i

α este o instanţiere a unei axiome

b. ∀ i, 1 ≤ i ≤ n ⇒ ∃ j, k, 1 ≤ j, k ≤ i: ({j

α , k

α }, i

α ) ∈MP

c. ∀ i, 1 ≤ i ≤ n ⇒ ∃ k, 1 ≤ k ≤ i: ({k

α },i

α )∈SUB

d. n

α α=

e. n

α α= , si ∀ i, 1 ≤ i ≤ n: i

α este o instanţiere a unei axiome sau ∃ j, k, 1 ≤ j, k ≤ i: ({j

α ,

k

α }, i

α ) ∈MP sau ∃ k, 1 ≤ k ≤ i: ({k

α },i

α )∈SUB

d

3

36

Fie H ⊂ FORM, finită. Care dintre următoarele afirmaţii este adevărată:

a. H este consistentă dacă nu este compatibilă;

b. H este compatibilă dacă nu este consistentă;

c. H este consistentă dacă şi numai dacă este compatibilă; d. H este fie compatibilă fie consistentă.

c

37

Fie H ⊂ FORM; H este finit validabilă dacă:

A. orice submulţime finită a sa este incompatibilă

B. orice submulţime finită a sa este consistentă C. cel puţin una dintre submulţimile sale finite nu este consistentă

a. B b. A+C c. A+B

a

32

Fie H o mulţime compatibilă de formule; atunci T(H) este:

a. o mulţime de formule inclusă în H;

b. un sistem deductiv;

c. o mulţime validabilă de formule.

b

41

Fie S(α) o reprezentare clauzală. Teorema de bază a rezoluţiei afirmă că: A. dacă S(α) este validabilă, atunci pentru orice literal λ: Rezλ(α) este validabilă

B. dacă există un literal λ astfel încât Rezλ(α) este validabilă, atunci S(α) este validabilă

a. A+B b. A c. B

a

42

Fie S(α) o reprezentare clauzală. Teorema de completitudine a rezoluţiei afirmă că:

a. S(α) este invalidabilă dacă există o S(α)-respingere rezolutivă; b. S(α) este invalidabilă dacă şi numai dacă există o S(α)-respingere rezolutivă.

b

23

Fie secventul H ⇒ Γ ; regula disjuncţiei dreapta este:

a. { }( ){ }

,H

H

α β

α β

⇒ Γ ∪

⇒ Γ ∪ ∨ b.

{ } { }( ){ }

,H H

H

α β

α β

∪ ⇒ Γ ∪ ⇒ Γ

∪ ∨ ⇒ Γ

a

24

Fie secventul H ⇒ Γ ; regula implicaţiei dreapta este:

a. { } { }

( ){ }H

H

α β

α β

∪ ⇒ Γ ∪

⇒ Γ ∪ → b.

{ } { }( ){ }

,H H

H

α β

α β

∪ ⇒ Γ ⇒ Γ ∪

∪ → ⇒ Γ

a

21

Fie secventul H ⇒ Γ ; regula implicaţiei stânga este:

a. { } { }

( ){ },H H

H

β α

α β

∪ ⇒ Γ ⇒ Γ ∪

∪ → ⇒ Γ

b. { } { }

( ){ },H H

H

α β

α β

∪ ⇒ Γ ⇒ Γ ∪

∪ → ⇒ Γ

a

22

Fie secventul H ⇒ Γ ; regula negaţiei dreapta este:

a. { }

( ){ }H

H

α

α

⇒ Γ ∪

∪ ⇒ Γ b.

{ }

( ){ }H

H

α

α

∪ ⇒ Γ

⇒ Γ ∪

b

4

9

Fie H FORM⊂ şi , FORMα β ∈ ; atunci:

a. { }H α β∪ | dacă ( )H α β| →

b. ( )H α β| → dacă { }H α β∪ |

c. A+B

c

3

Mulţimea axiomelor teoriei care modelează raţionamentele în contextul limbajului calculului cu propoziţii,

notată AXIOM, se află în următoarea relaţie cu sortul FORM:

a. AXIOM = FORM

b. AXIOM ⊂ FORM

c. AXIOM ⊃ FORM

b

31

O mulţime compatibilă de formule H este un sistem deductiv dacă:

a. h

Tα∀ ∈ atunci ( )T Hα ∈ c. T(H) ⊂ H

b. T(H) = H d. T(H) ⊃ H

b

26

Pentru o formulă selectată regula de inferenţă este:

A. unică;

B. definită de conectiva principală şi de provenienţa ei;

C. conectiva cea mai din stânga / dreapta pentru regulile la stânga / dreapta.

a. A+B b. A+C c. A+B+C

a

7

Regula modus ponens, MP, este de tip:

a. (1,1) c. (2,1)

b. (1,2) d. (2,2)

c

14

Schema negaţiei, (NN): ∀ α , β ∈FORM :

a. ( )( )

α β

α β

↔

↔ b.

( )

( ) ( )( )α β

β α

→

→ c.

( )) )( )

α β

β α α

→

→ →

b

12

Schema permutării premiselor, (PP): ∀ α , β , γ ∈FORM :

a. ( ) ( )

( )( ),α β α γ

α β γ

→ →

→ → c.

( )( )( )( )

α β γ

β α γ

→ →

→ →

b. ( ) ( )

( )( ),α β β γ

β α γ

→ →

→ →

c

5

15

Schema rezoluţiei, (REZ): ∀ α , β , γ ∈FORM :

a.

( ) ( )( )( )( )

,α β α γ

β γ

→ →

∨ c.

( ) ( )( )( )( )

,α β α γ

β γ

→ ↔

∨

b.

( ) ( )( )( )( )

,α γ α β

β γ

→ →

∨

a

10

Schema silogismului, (RS): ∀ α , β , γ ∈FORM:

a. ( ) ( )

( ),α β β γ

α γ

→ →

→ c.

( ) ( )( )

,α β α γ

γ β

→ →

→

b. ( ) ( )

( ),α β α γ

β γ

→ →

→

a

13

Schema trecerii de la echivalenţă la implicaţie, (EI): ∀ α , β ∈FORM:

A. ( )( )α β

α β

↔

→ B.

( )( )α β

β α

↔

→

a. A b. A+B c. B

b

11

Schema trecerii de la implicaţie la echivalenţă, (IE): ∀ α , β , γ ∈FORM:

a. ( ) ( )

( ),α β α γ

β γ

→ →

↔ c.

( ) ( )( )

,α β β α

α β

→ →

↔

b. ( ) ( )

( ),α β β γ

α γ

→ →

↔

c

6

Se numeşte regulă de inferenţă orice relaţie p q

R FORM FORM⊂ × în care:

a. p=p c. q=p+1

b. p=q+1 d. p,q*

N∈

d

17

Se numeşte secvent o pereche de mulţimi de formule (H, Γ) în care apar numai conective din mulţimea:

a. { }\L ↔ b. { }\L → c. { }\ ,L ∧ ∨ d. { }\L

a

18

Secventul H ⇒ Γ este secvent axiomă dacă:

a. H ∩ Γ = ∅ b. H ∩ Γ ≠ ∅ c. H ⊆ Γ

b

19

Secventul H ⇒ Γ este secvent încheiat dacă:

a. V HΓ ∩ ⊂ b. H V∩ ⊂ Γ c. H V∪ Γ ⊂

c

6

30

Sunt adevărate:

A. enunţul “h

T FORM≠ ”

B. enunţul “ h

Tα∀ ∈ atunci ( ) hTα ∉ “

C. enunţul “pentru FORMα∀ ∈ cel mult una dintre formulele α , ( )α este teoremă”

D. enunţul “ pentru FORMα∀ ∈ cel puţin una dintre formulele α , ( )α este teoremă”

a. A+B+C d. B+D

b. A+B+D e. A+C

c. B+C

a

40

Teorema de completitudine a sistemului deducţiei naturale afirmă că:

a. orice secvent încheiat este secvent valid;

b. orice secvent valid este secvent demonstrabil;

c. orice secvent demonstrabil este secvent valid.

b

39

Teorema de consistenţă a sistemului deducţiei naturale afirmă că:

a. orice secvent încheiat este secvent valid;

b. orice secvent valid este secvent demonstrabil;

c. orice secvent demonstrabil este secvent valid.

c

27

Un arbore de deducţie T este un arbore de demonstraţie pentru secventul etichetă a vârfului rădăcină dacă

orice vârf terminal are ca etichetă un secvent:

a. încheiat;

b. axiomă; c. incheiat sau axiomă

b

28

Un secvent S se numeşte demonstrabil şi se notează cu | S, dacă

a. există T un arbore de demonstraţie cu S eticheta rădăcinii;

b. există T un arbore de demonstraţie cu S eticheta cel puţin a unui nod terminal;

c. există T un arbore încheiat cu S eticheta cel puţin a unui nod terminal;

d. există T un arbore încheiat cu S eticheta rădăcinii.

a