Post on 04-Jan-2016
description
Bilet numărul 1 1. Algebre booleene
a) Clasa funcţiilor booleene elementare (proiecţiile). Superpoziţia în FB. Noţiunea de M-şir şi de mulţime închisă de funcţii booleene ( ).
(2 puncte) b) Arătaţi următoarele egalităţi de funcţii booleene, fără a folosi tabele de
adevăr: şi . (1 punct)
2. LP
a) Să se demonstreze următoarele echivalente tari: şi
(ultima este adevărata doar pentru acele formule care
sunt contradicţii). (2 puncte) b) Definirea abstractă a unei clase de formule (sistem deductiv, axiome,
reguli de inferenţă, demonstraţie, consecinţă sintactică: şi ).
(1 punct) 3. LP1
a) Substituţii elementare şi substituţia vidă. Substituţii normalizate. Substituţii permise pentru o formulă. (1 punct)
b) Fie formula . Să se găsească o structură
Herbrand care să nu fie model pentru . (2 puncte)
M FB⊆
( )x x y x⋅ + = ( )x x y x+ ⋅ =
( )F F G F∧ ∨ ≡
F G G∨ ≡ F
F� FI �
( ) ( )( ) ( )( )( ), ,F x P x f x Q g b z= ∀ ∧
,= H HH U I F
Bilet numărul 3 1. Algebre booleene
a) Mulţimi complete de funcţii booleene. Baze. Exemple. (1 punct) b) Demonstraţi că orice funcţie booleană se poate reprezenta unic ca o
FNDP. (2 puncte) 2. LP
a) Arătaţi, folosind rezoluţia, că formula următoare este tautologie:
. (2 puncte)
b) Decidabilitatea şi complexitatea problemei SAT (comentarii). (1 punct) 3. LP1
a) Fie formula: şi
structura , unde , , , şi
dacă şi numai dacă . Să se decidă dacă . (1.5 puncte)
b) Definiţia constructiva a lui . (1.5 puncte)
( ) ( ) ( )F B C D B D C D B= ¬ ∧¬ ∧ ∨ ¬ ∧¬ ∨ ∧ ∨
( )( )( ) ( ) ( ) ( ) ( )( ), , , ,F x y z P x y P z y P x z P z x= ∃ ∃ ∀ ∧ ∧ ∧¬
,= S SS U I = ¥SU 0x =S 1y =S2z =S ( ), 1P a b =S
1b a= + FS ‘( )free F
Bilet numărul 5 1. Algebre booleene
a) Arătaţi că este o mulţime închisă de funcţii booleene. (1.5 puncte)
b) Factor, maxfactor n-ar peste . FNCP pentru (
). (1.5 puncte)
2. LP a) Este mulţimea infinită de formule:
satisfiabilă? (2 puncte)
b) Arătaţi că este validă dacă şi numai dacă este contradicţie. (1
punct) 3. LP1
a) „Aduceţi” la o FNSC (închisă) formula:
(2
puncte) b) Simboluri predicative, conectori şi cuantificatori. Definiţia constructivă
a clasei (formule atomice), presupunându-se cunoscută definiţia
clasei a termilor. (1 punct)
0T
X( )nf FB∈
{ }1 2, , ... , nx x x=X
{ }1 2 2 3 3 4 4 5, , , , ... M A A A A A A A A= ∨ ¬ ∨¬ ∨ ¬ ∨¬
F ( )F¬
( )( ) ( )( )( ) ( )( ) ( ) ( )( )( ) ( ) ( )( ) ( ), , ,F x y P x f y x z Q f x f z R t x y P x y= ∀ ∃ ∧ ∀ ∀ ∧ ∧ ∃ ∀
At
T
Bilet numărul 6 1. Algebre booleene
a) Demonstraţi următoarele egalităţi de funcţii booleene, fără a folosi
tabele de adevăr: şi . (2 puncte)
b) Mulţimi complete de funcţii booleene. Baze. Exemple. (1 punct) 2. LP + Sisteme deductive
a) Exemple de sisteme de demonstraţie: SD3, SD0, SD1 (comentarii generale) (1 punct)
b) Demonstraţi următoarele echivalenţe tari: şi
(ultima fiind adevărată dacă şi numai dacă este tautologie). (2
puncte) 3. LP1
a) Formule închise. Închiderea existenţială şi universală pentru .
Legătura dintre , şi (fără demonstraţie). Matricea lui
. (1 punct)
b) Fie formula:
. Să se
găsească o formulă care să fie în FNPR şi să satisfacă condiţia
. (2 puncte)
( )x x y x y⋅ + = ⋅ ( )x x y x y⋅ + = ⋅
( )F F G F∨ ∧ ≡ GGF ≡∧
F
1LPF ∈
F ( )( )F∀∗ ( )( )F∃∗
F
( )( ) ( )( )( ) ( ) ( )( ) ( )( ) ( )( )( ), , , ,F x y P x g y z x Q x z x R f x z z= ∀ ∃ ∨ ¬ ∀ ∧ ∀ ∃ ¬
'FFF ≡'
Bilet numărul 7 1. Algebre booleene
a) Definiţia funcţiilor booleene , , şi . (1 punct)
b) Teorema de descompunere a unei funcţii booleene în sumă de termeni. (2 puncte)
2. LP a) Să se arate, folosind metoda rezoluţiei, că următoarea formulă este
tautologie: . (2 puncte)
b) Sintaxa formală a LP. (1 punct) 3. LP1
a) Variabile şi simboluri funcţionale (inclusiv constante). Definiţia constructivă a lui (mulţimea termilor). Termi de bază. (1.5 puncte)
b) Fie formula . Să se găsească o structură
astfel încât să fie model pentru . (1.5 puncte)
+ ⋅ ⊕ |
( ) ( ) ( ) ( )F A B C A B A C A C A= ∧ ∧ ∨ ∧¬ ∨ ∧¬ ∨ ¬ ∧¬ ∨¬
T
( ) ( )( ) ( )( )( ), ,F x P x f x Q g b z= ∀ ∧
, = S SS U I S F
Bilet numărul 8 1. Algebre booleene
a) Arătaţi că este o mulţime închisă de funcţii booleene. (2 puncte)
b) Termen, maxtermen n-ar peste . FNDP pentru . (1 punct)
2. LP a) Să se studieze satisfiabilitatea formulei:
folosind algoritmul de marcare
Horn. (2 puncte) b) Formule satisfiabile, valide, contradicţii. Consecinţă semantică.
Echivalenţă tare. Echivalenţă slabă. (1 punct) 3. LP1
a) Găsiţi o formulă , aflată în FNSC şi slab echivalentă cu:
. (1.5 puncte)
b) Lema de translaţie (doar baza şi cazul ). (1.5 puncte)
1T
X( )nf FB∈
( ) ( )F A D C A B A B E= ¬ ∧¬ ∧¬ ∧ ¬ ∨ ∧ ¬ ∨¬ ∨
'F
( )( ) ( )( )( ) ( )( ) ( )( )( ) ( )( ), , ,F x y P x f y x z Q x z f y R t= ∀ ∃ ∧ ∀ ∃ ∧
( )F G= ¬
Bilet numărul 9 1. Algebre booleene
a) Să se găsească o FNDP şi FNCP pentru:
(1 punct) b) Definiţia formală a noţiunii de algebră booleană. (2 puncte)
2. LP a) Să se găsească o respingere pornind cu clauzele formulei:
. (1 punct)
b) Algoritmul Horn pentru testarea satisfiabilităţii formulelor Horn.Terminare şi corectitudine. (2 puncte)
3. LP1
a) Să se găsească pentru formula:
. (2 puncte)
b) Apariţii libere şi legate ale unei variabile într-o formulă. Domeniul sintactic al unui cuantificator. (1 punct)
1x 2x 3x ( )1 2 3, ,f x x x
0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1
( ) ( ) ( ) ( )F A B C B C A C B C C= ∨¬ ∨ ∧ ∨ ∧ ¬ ∨ ∧ ∨¬ ∧¬
( )Arb F
( ) ( ) ( ) ( )( ) ( )( ) ( ) ( )( )( )( )( ( , , ,F Q x x y P f x z Q a x R x z g x= ∨ ∃ ∀ ∧ ∨ ∀
Bilet numărul 10 1. Algebre booleene
a) „Axiomă” şi/sau „teoremă” într-o algebră booleană. Metode de verificare a „adevărului” acestora. Dualitate. Principiul dualităţii. (1.5 puncte)
b) Stabiliţi cardinalitatea mulţimii şi justificaţi-o. (1.5
puncte) 2. LP
a) Arătaţi, folosind metoda rezoluţiei, că formula este
consecinţă semantică din mulţimea de clauze:
(1.5 puncte)
b) Definiţi structural şi , unde . (1.5 puncte)
3. LP1 a) Arătaţi ca următoarea formulă este nesatifiabilă:
. (2 puncte)
b) Teorema de redenumire a variabilelor legate (baza şi ceva din pasul constructiv). (1 punct)
( ) ( ), nFB n∈¥
CBAG ∧∧=
{ }, , , F A B B C A C A B C= ¬ ∨ ¬ ∨ ∨¬ ∨ ∨
( )subf F ( )Arb F LPF ∈
( )( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )( )F x y P x Q y P x Q y R z Q y= ∀ ∃ ¬ ∨ ∧ ∨ ∧ ∧¬
Bilet numărul 11 1. Algebre booleene
a) Definiţia unei algebre booleene. Demonstraţi că este
algebră booleană. (1 punct)
b) Termen, maxtermen n-ar peste . (2 puncte)
2. LP a) Definiţia FNDP. (1 punct) b) Să se aplice algoritmul Horn („de marcare”) formulei:
(evident, după ce se aduce la o formă corespunzătoare). (2 puncte)
3. LP1
a) Fie formula . Să se găsească o structură
Herbrand astfel încât să fie model pentru . (2
puncte)
b) Definiţi constructiv . (1 punct)
, , , B= ⋅ +B
{ }1 2, , ... , nx x x=X
( ) ( ) ( )1 2 3 4 5 6 7 7 4 8 1 2 5 2 8F A A A A A A A A A A A A A A A= ∧ → ∧ ∧ ∧ → ∧ ∧ → ∧ ∧ ∧ ∧ ∧¬
F
( ) ( )( ) ( )( )( ), ,F x P x f x Q g b z= ∀ ∧
, = H HH U I H F
( ) , 1subf F F LP∈
Bilet numărul 12 1. Algebre booleene
a) Sa se calculeze numărul total al termenilor şi maxtermenilor peste
. Care este numărul total al funcţiilor aflate în FNDP
(cu argumentele )?. (2 puncte)
b) Definiţiile exacte ale funcţiilor: , , , . (1 punct)
2. LP a) Să se arate, folosind rezoluţia, că formula următoare este
nesatisfiabilă: . (1.5 puncte)
b) Fie şi . Demonstraţi că este
consecinţă semantică din dacă şi numai dacă
este tautologie. (1.5 puncte) 3. LP1
a) Definiţi constructiv , . Se presupun cunoscute definiţiile
pentru şi , unde şi . (1 punct)
b) Fie formula . Să se găsească o structură
astfel încât să nu fie model pentru . (2 puncte)
{ }1 2, , ... , nx x x=X
( )1 2, , ... , nx x x
+ ⋅ ⊕ |
( ) ( ) ( ) ( )F A A B A C A B A B C= ∧ ∨ ∧ ¬ ∨ ∧ ¬ ∨ ∧ ¬ ∨¬ ∨¬
LPG∈ { }1 2, , ... , nH G G G LP= ⊆ G
H GGGG n →∧∧∧ ...21
( )Arb F 1LPF ∈
( )Arb t ( )Arb A t∈T AtA∈
( ) ( )( ) ( )( )( ), ,F x P x f x Q g b z= ∀ ∧
,= S SS U I S F
Bilet numărul 13 1. Algebre booleene
a) Fie mulţimea , unde , ,
. Arătaţi că , este un element
din . (2 puncte)
b) Noţiunile de „axiomă” şi/sau „teoremă” în contextul algebrelor booleene. Metode sintactice şi semantice pentru verificarea veridicităţii acestora. Dualitate în algebre booleene. Principiul dualităţii. (1 punct)
2. LP a) Teorema de substituţie pentru LP (enunţ şi demonstraţie
constructivă). (2 puncte)
b) Arătaţi că funcţia , dată prin , este monotonă.
(1 punct) 3. LP1
a) Definiţia generală, formală, a unei structuri . (1 punct)
b) Fie formula:
. Să se aducă această formulă la FNSC. (2 puncte)
{ }, ,M n s p FB= ⊆ ( )n x x= ( ),s x y x y= + ( ),p x y x y= ⋅
( )4f FB∈ ( ), , ,f x y z t x y x y t z t y z t= ⋅ + ⋅ ⋅ + ⋅ + ⋅ ⋅
M
( )2f FB∈ ( ),f x y x y x= + ⋅
,= SS U SI
( )( )( )( )( ) ( )( ) ( ) ( )( )( )( ), , , ,F x y u t v P x g y b Q u R f v t t= ∀ ∃ ∃ ∀ ∃ ∨ ¬ ∧¬
Bilet numărul 14 1. Algebre booleene
a) „Demonstraţi” următoarele egalităţi de funcţii booleene, fără a folosi tabele de adevăr: şi . (1.5 puncte)
b) Termen n-ar peste . Maxtermen n-ar. Reprezentarea
unei funcţii ca o FNDP. (1.5 puncte) 2. LP
a) Legătura dintre sistemele deductive şi teoriile logice (teoreme de corectitudine şi completitudine). Comentarii generale. (1 punct)
b) Fie formula: . Să se găsească o
FND. (2 puncte) 3. LP1
a) Teorema de substituţie pentru LP1 (să se demonstreze doar baza şi
cazul ). (1.5 puncte)
b) Găsiţi o formulă din LP1, care conţine simbolurile speciale: ,
, (în afară, desigur, de alte simboluri care pot face parte din
alfabetul peste care se construieşte LP1) şi care sa satisfacă condiţia: pentru fiecare structura , avem este model pentru dacă şi
numai dacă este grup. (1.5 puncte)
x x y x y+ ⋅ = + x x y x y+ ⋅ = +
{ }1 2, , ... , nX x x x=
( ) ( ) ( )( ) ( )( )P Q Q R P R Q S→ ∧ ∨ → ∨ →¬ ∨
( )( )F x G= ∀
F 2=∈P
2⋅∈F 01∈F
S S F,= ⋅SSS U
Bilet numărul 16 1. Algebre booleene
a) Fie funcţiile , date respectiv prin şi
. Să se arate că . (1 punct)
b) Să se demonstreze că orice funcţie admite o descompunere în
produs de factori (sume de variabile). (2 puncte) 2. LP
a) Definiţi , , şi , . Ce
legătură există între şi ? Dar între apartenenţa la
şi existenţa unei demonstraţii prin rezoluţie pornind cu
„clauzele care reprezintă ”? (1.5 puncte)
b) Găsiţi valoarea de adevăr a afirmaţiei: „Dacă există petrol în Patagonia, atunci fie experţii au dreptate, fie guvernul minte. Nu există petrol în Patagonia sau experţii greşesc, aşadar guvernul nu minte.”. (1.5 puncte)
3. LP1 a) Găsiţi o structură astfel încât să fie model şi o structură
care să nu fie model pentru , unde . (2
puncte)
b) Definiţi constructiv extensia a unei structuri , doar în
cazul formulelor (se presupune deja cunoscută pentru mulţimea
– a termilor – şi – a formulelor atomice). (1 punct)
( )3,f g FB∈ ( ), ,f x y z x z y= ⋅ +
( ) ( ) ( ), ,g x y z x y y z x y z= + ⋅ + + ⋅ ⋅ f g=
f FB∈
( )Res F ( ) ( ) ( ) nRes F n∈¥ ( )*Res F ( )Resc F F LP∈
( )*Res F ( )Resc F
( )*Res F
F
1S 1S F 2S
F ( ) ( )( ) ( ) ( )( ),F x P x y Q x y= ∀ → ∀
'S ,= S SS U I
'S TtA
Bilet numărul 17 1. Algebre booleene
a) Definiţia formală a unei algebre booleene. (1 punct)
b) Arătaţi că funcţia este autoduală. (2 puncte)
2. LP a) Formule Horn. Decidabilitatea şi complexitatea problemei SAT pentru
clasa formulelor Horn din LP (nu se cere algoritmul, ci doarcomentarii). Reprezentarea clauzelor Horn sub formă implicaţională. (1 punct)
b) Fie formula . Arătaţi că ea este
nesatisfiabilă folosind metoda rezoluţiei. (2 puncte) 3. LP1
a) Demonstraţi că echivalenţele care urmează nu sunt adevărate:
• ;
• .
(1.5 puncte) b) Găsiţi o structură astfel încât să fie model pentru , unde
. (1.5 puncte)
( ), ,f x y z x y z= ⊕ ⊕
( ) ( ) ( )F A B C A A B C A B= ∨ ∨¬ ∧¬ ∧ ∨ ∨ ∧ ∨¬
( )( ) ( )( ) ( )( )x F x G x F G∀ ∨ ∀ ≡ ∀ ∨
( )( ) ( )( ) ( )( )x F x G x F G∃ ∧ ∃ ≡ ∃ ∧
S S F
( ) ( )( ) ( ) ( )( ), ,F x Q x y y Q x y= ∃ → ∀
Bilet numărul 18 1. Algebre booleene
a) Să se demonstreze adevărul afirmaţiei: dacă şi numai
dacă astfel încât (şi aceasta pentru fiecare şi
fiecare valoare a elementelor din ). (2 puncte)
b) Fie . Să se scrie toţi 2-termenii peste şi toţi 2-termenii
maximali peste . Să se justifice numărul lor. (1 punct)
2. LP + Programare Logică a) Programare logică. Descrierea informală a programelor logice ca
reprezentare a realităţii sub formă de mulţimi de „formule”: obiecte, nume generice pentru obiecte, relaţii între obiecte, transformări între obiecte, afirmaţii (formule), interogări. (2 puncte)
b) Arătaţi că în LP există formule satisfiabile dar nevalide, formule valideşi contradicţii. (1 punct)
3. LP1 a) Să se găsească o structură astfel încât să fie model pentru ,
unde: . (2 puncte)
b) Definiţia universurilor Herbrand şi a unei structuri Herbrand. (1 punct)
1 2 ... 0nx x x⋅ ⋅ ⋅ =
[ ]i n∃ ∈ 0ix = , 2n n∈ ≥¥
1 2, , ... , nx x x { }0, 1B =
{ }1 2, X x x= XX
S S F
( ) ( ) ( )( )( ) ( ) ( )( ) ( ) ( )( )( ), ,F x P x Q x y y P y x Q y z= ∀ → → ∃ → ∃
Bilet numărul 19 1. Algebre booleene
a) n-factor peste mulţimea . n-factor maximal peste
aceeaşi mulţime. Unica funcţie care este în reprezentare FNCP peste . (1.5 puncte)
b) Să se arate că formulă este
tautologie. (1.5 puncte) 2. LP
a) Rezoluţie în LP: rezolvent şi rezoluţie într-un pas; - mulţimea
rezolvenţilor „imediaţi” (obţinuţi într-un singur pas) ai unei mulţimi de clauze ; . Rezoluţie în
mai mulţi paşi (demonstraţie prin rezoluţie). (1 punct) b) Să se decidă dacă următoarea formulă este satisfiabilă aplicând
algoritmul „de marcare” Horn, iar în caz de răspuns afirmativ să se găsească şi o structură astfel încât să fie model pentru :
. (2 puncte)
3. LP1 a) Demonstraţi că pentru fiecare formulă există o formulă
care este în FNP şi este tare echivalentă cu (doar cazul
baza şi punctul ). (2 puncte)
b) Să se găsească o structură care să fie model pentru formula
dată de: . (1 punct)
{ }1 2, , ... , nX x x x=
X
( ) ( )( )1 2 3 1 2 3F A A A A A A= ∧ → ↔ → →
( )Res F
F( ) ( ) ( )0 1 *( ), ( ), ( ) ( , 2), ( )kRes F Res F Res F k k Res F∈ ≥¥
S S F
( ) ( )( )F B D E C B B D B= ¬ ∨¬ ∧¬ ∧¬ ∧ ∧ ¬ ∨ ∧
1F LP∈
' 1F LP∈ F( )F G= ¬
S F
( ) ( )( ) ( ) ( ) ( )( )( )( ), ,F x Q x y P x x Q y x= ∃ → → ¬ ∃
Bilet numărul 20 1. Algebre booleene
a) Să se definească funcţiile şi să se arate că
formează o algebră booleană ( ). (1 punct)
b) Să se arate că dacă şi numai dacă pentru fiecare
avem (şi aceasta pentru fiecare şi oricare valori din B
ale variabilelor ). (2 puncte)
2. LP a) Să se ARATE că pentru fiecare există şi astfel
încât este în FNC şi este în FND şi, în plus, şi (prin
inducţie structurală). (2 puncte) b) Rafinări (strategii şi restricţii) ale rezoluţiei (descrieţi măcar trei dintre
ele). (1 punct) 3. LP1
a) Să se găsească o structură astfel încât să fie model pentru ,
unde . (2
puncte)
b) Să se definească extensia Herbrand ( ) pentru o formulă aflată
în FNS (închisă) şi extensia Herbrand generalizată ( ) pentru o
formulă aflată în FNSC (închisă). (1 punct)
, , FB⋅ + ∈ , , , B= ⟨ ⋅ + ⟩B{0, 1}B =
1 2 ... 1nx x x⋅ ⋅ ⋅ = [ ]i n∈
1ix = , 2n n∈ ≥¥
1 2, , ... , nx x x
F LP∈ G LP∈ H LP∈
G H F G≡ F H≡
S S F
( ) ( )( ) ( ) ( )( )( ) ( )( )( ) ( )( ), , ,F x P x x Q x y x y z R x y z= ¬ ∃ ∧ ∀ ↔ ¬ ∀ ∃ ∀
( )E F F( )'E F
F