subiecte_logica

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


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


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


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 ≡'


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)


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


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= ¬


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= ∨ ∃ ∀ ∧ ∨ ∀


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= ∀ ∃ ¬ ∨ ∧ ∨ ∧ ∧¬


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∈


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)


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


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= ∀ ∃ ∃ ∀ ∃ ∨ ¬ ∧¬


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


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


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= ∃ → ∀


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= ∀ → → ∃ → ∃


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= ∃ → → ¬ ∃


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

subiecte_logica

Documents

Transcript of subiecte_logica