Logica computationala

Multiple Choice
Identify the letter of the choice that best completes the statement or answers the question.

____ 1. Fie formula α∈ FORM şi funcţia h : FORM Æ N definită prin:

 0, daca α ∈ V

h(α ) =  1 + h( β ), daca α = β
1 + max{ 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 α.
____ 2. Fie formula α∈ FORM şi funcţia h : FORM Æ N definită prin:
 0, daca α ∈ V

h(α ) =  1 + h( β ), daca α = β
1 + max{ 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 α.
____ 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
____ 4. Fie formula α ∈ FORM şi substituţia σ ∈ SUBST. Rezultă că:

a. ασ ∈ SUBST
b. ασ ∈ FORM
c. ασ ∈ AXIOM
____ 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 ασ.
____ 6. Se numeşte regulă de inferenţă orice relaţie R ⊂ FORMp x FORMq, în care:

a. p=p
b. p=q+1
c. q=p+1
d. p,q ∈ N *
____ 7. Regula modus ponens, MP, este de tip:

a. (1,1)
b. (1,2)
c. (2,1)
d. (2,2)
____ 8. Fie formula α ∈ FORM; ea se numeşte teoremă dacă ∃ α1, … , αn ∈ FORM 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
____ 9. Fie H ⊂ FORM şi α , β ∈ FORM; atunci:

a. H ∪ {α} | β dacă H | (α → β)
b. H | (α → β) dacă H ∪ {α} | β
c. A+B
____ 10. Schema silogismului, (RS): ∀ α , β , γ ∈ FORM:

a. (α → β ), ( β → γ )
(α → γ )
b. (α → β ), (α → γ )
(β → γ )
c. (α → β ), (α → γ )
(γ → β )
____ 11. Schema trecerii de la implicaţie la echivalenţă, (IE): ∀ α , β , γ ∈ FORM:

a. (α → β ), (α → γ )
(β ↔ γ )
b. (α → β ), ( β → γ )
(α ↔ γ )
c. (α → β ), ( β → α )
(α ↔ β )
____ 12. Schema permutării premiselor, (PP): ∀ α , β , γ ∈ FORM:

a. (α → β ), (α → γ )
(α → ( β → γ ))
b. (α → β ), ( β → γ )
( β → (α → γ ))
c. (α → ( β → γ ))
( β → (α → γ ))
____ 13. Schema trecerii de la echivalenţă la implicaţie, (EI): ∀ α , β ∈ FORM:
A. (α ↔ β )
(α → β )
 B. (α ↔ β )
(β → α )
a. A
b. A+B
c. B
____ 14. Schema negaţiei, (NN): ∀ α , β ∈ FORM:

a. ( α ↔ β )
(α ↔ β )
b. (α → β )
((  β ) → ( α ))
c. ( α → β )
( β → α ) → α ))
____ 15. Schema rezoluţiei, (REZ): ∀ α , β , γ ∈ FORM:

a. ((α → β ) , ((  α ) → γ ))
(β ∨ γ )
b. ((α → γ ) , ((  α ) → β ))
(β ∨ γ )
c. ((α → β ) , ((  α ) ↔ γ ))
(β ∨ γ )
____ 16. Fie Γ ⊂ FORM; atunci:
A. {α , β} | Γ dacă {(α ∧ β)} | Γ
B. {(α ∧ β)} | Γ dacă {α , β} | Γ

a. A
b. A+B
c. B
____ 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 \ {→ }
L \ {∧ , ∨}
c.
L\{}
d.
____ 18. Secventul H ⇒ Γ este secvent axiomă dacă:

a. H ∩ Γ = ∅
b. H ∩ Γ ≠ ∅
c. H ⊆ Γ
____ 19. Secventul H ⇒ Γ este secvent încheiat dacă:

a. Γ ∩ V ⊂ H
b. H ∩ V ⊂ Γ
c. H ∪ Γ ⊂ V
____ 20. H ⇒ Γ ∪ {α } este o:
H ∪ {(  α )} ⇒ Γ

a. regulă de deducţie Gentzen;

b. regulă de deducţie Herbrand;
c. regulă de inferenţă Herbrand;
d. regulă de inferenţă Gentzen.
____ 21. Fie secventul H ⇒ Γ; regula implicaţiei stânga este:

a. H ∪ {β } ⇒ Γ, H ⇒ Γ ∪ {α }
H ∪ {( α → β )} ⇒ Γ
b. H ∪ {α } ⇒ Γ, H ⇒ Γ ∪ {β }
H ∪ {( α → β )} ⇒ Γ
____ 22. Fie secventul H ⇒ Γ; regula negaţiei dreapta este:

a. H ⇒ Γ ∪ {α }
H ∪ {(  α )} ⇒ Γ
b. H ∪ {α } ⇒ Γ
H ⇒ Γ ∪ {(  α )}
____ 23. Fie secventul H ⇒ Γ; regula disjuncţiei dreapta este:

a. H ⇒ Γ ∪ {α , β }
H ⇒ Γ ∪ {( α ∨ β )}
b. H ∪ {α } ⇒ Γ, H ∪ {β } ⇒ Γ
H ∪ {( α ∨ β )} ⇒ Γ
____ 24. Fie secventul H ⇒ Γ; regula implicaţiei dreapta este:

a. H ∪ {α } ⇒ Γ ∪ {β }
H ⇒ Γ ∪ {( α → β )}
b. H ∪ {α } ⇒ Γ, H ⇒ Γ ∪ {β }
H ∪ {( α → β )} ⇒ Γ
____ 25. După aplicarea regulilor de inferenţă formulele rezultate au adâncime:

a. mai mare;
b. mai mică;
c. nemodificată.
____ 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
____ 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ă
____ 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.
____ 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ţă.
____ 30. Sunt adevărate:
A. enunţul “Th ≠ FORM
B. enunţul “ ∀ α ∈ Th atunci ( α) ∉ Th “
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
b. A+B+D
c. B+C
d. B+D
e. A+C
____ 31. O mulţime compatibilă de formule H este un sistem deductiv dacă:

a. ∀ α ∈ Th atunci α ∈ T(H)
b. T(H) = H
c. T(H) ⊂ H
d. T(H) ⊃ H
____ 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.
____ 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ţă.
____ 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.
____ 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 .
____ 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ă.
____ 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
____ 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.
____ 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.
____ 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.
____ 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
____ 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ă.