Algebrai logika feladatok



Vissza az előadás indexlapjára


  • 1. feladat Bizonyítsuk be, hogy egy háló pontosan akkor disztributív, ha rendelkezik a kongruenciakiterjesztési tulajdonsággal (CEP)!
  • 2. feladat Bizonyítsuk be, hogy egy U halmaz feletti (azaz a hatványhalmazán értelmezett) f lezárási operátor pontosan akkor teljesen additív, ha van U-n olyan unér algebra, ahol a ,,részalgebra-generálás'' operátor éppen f!
  • 3. feladat Mutassuk meg, hogy nem létezik megszámlálhatóan végtelen szigma-teljes Boole-algebra!
  • 4. feladat Bizonyítsuk be, hogy van adekvát Hilbert típusú kalkulus a következő logikai rendszerekhez:
    a) negációmentes nulladrendű logika;
    b) negáció-, 0- és 1-mentes nulladrendű logika;
    c) csoportok logikája!
  • 5. feladat Mutassuk meg, hogy a negációmentes nulladrendű logika esetén nem érvényes Beth tétele (azaz ha alkalmas Q kijelentésváltozó-halmazt kiegészítünk néhány (alkalmas sok) további pi kijelentésváltozóval, akkor található olyan formulahalmaz, mely implicite definiálja a pi-k jelentését Q-ból, de explicite nem)!
  • 6. feladat Rajzoljunk minél szebben négy általános helyzetű halmazt!
  • 7. feladat Mutassuk meg, hogy véges relációs típus esetén, ha veszünk egy olyan struktúrát, ahol a relációjelek interpretáltjai is végesek, abban minden automorfizmus-invariáns reláció elsőrendű formulával kifejezhető!
  • 8. feladat Bizonyítsuk be, hogy $\mbox{\large$\alpha\geq \omega$}$-ra az $\mbox{\large$\alpha$}$ dimenziós kockán reprezentálható $\mbox{\large$\sf CA$}$-k osztálya nem axiomatizálható!
  • 9. feladat Az $\mbox{\large$x_1, x_2, \dots$}$ elemekkel generált szabad Boole-algebrát $\mbox{\large${\sf CA}_\omega$}$ típusú algebrává bővítjük a következőképp: legyen $\mbox{\large${\sf d}_{ij} = x_i \otimes x_j$}$, ill. $\mbox{\large${\sf c}_i$}$ hasson úgy az $\mbox{\large$x_1, x_2, \dots$}$ változók egy adott $\mbox{\large$k$}$ Boole-kifejezésén, hogy $\mbox{\large$x_i$}$ valamely előfordulását 1-re cseréli, ha ezen előfordulás $\mbox{\large$k$}$-beli negációmélysége páros, és 0-ra, ha páratlan (ahol az előfordulás $\mbox{\large$k$}$-beli negációmélységén $\mbox{\large$k$}$ azon részkifejezéseinek számát értjük, melyek tartalmazzák az előfordulást és komplementációval kezdődnek)(ez jóldefiniált lesz). Keressünk olyan elsőrendű struktúrát, aminek épp az így kapott algebra a jelentésalgebrája!

  • 10. feladat Mutassunk példát elsőrendű struktúrák pszeudoaxiomatizálható, de egzisztenciális másodrendű formulákkal nem axiomatizálható osztályára!
  • 11. feladat Tekintsük a következő logikai rendszert: a Boole-konnektívák mellé felvesszük még az $\mbox{\large$\alpha$}$, $\mbox{\large$\alpha^*$}$ unér konnektívákat. A formulák ezekbol képződnek a szokásos módon. Egy modellhez először is megadandó egy $\mbox{\large$\< U, A, A^*\csname rangle\endcsname $}$ hármas, ahol $\mbox{\large$U$}$ nemüres halmaz, $\mbox{\large$A$}$ egy binér reláció $\mbox{\large$U$}$-n, $\mbox{\large$A^*$}$ pedig $\mbox{\large$A$}$ reflexív-tranzitív lezártja. $\mbox{\large$\mathscript P(U)$}$-n ekkor adódik egy, a mi konnektíváinkat használó extra-Boole algebrai struktúra: $\mbox{\large$X\subseteq U$}$ esetén $\mbox{\large$\alpha(X) = \{u\in U: \exists v\in X\ \ \< u,v\csname rangle\endcsname \in A\}$}$, ill. hasonlóképp $\mbox{\large$\alpha^*$}$ és $\mbox{\large$A^*$}$ viszonylatában. Ezután a modell megadása abból áll, hogy a kijelentésváltozókhoz hozzárendeljük valahogy $\mbox{\large$U$}$ némely részhalmazát. A modell jelentésfüggvénye ezen hozzárendelésnek a formulaalgebrára való homomorf kiterjesztéseként adódik, és persze egy formula érvényes a modellben, ha jelentése $\mbox{\large$U$}$. Mutassuk meg, hogy ez a logikai rendszer nem kompakt (van végtelen kielégíthetetlen formulahalmaz, aminek minden véges része kielégíthető)!
  • 12. feladat
    a) Legyenek $\mbox{\large$f$}$ és $\mbox{\large$g$}$ egyváltozós függvények egy Boole-algebrán, úgy, hogy ún. konjugált párt alkotnak, azaz $\mbox{\large$x\land f(y)= 0\iff g(x)\land y= 0$}$. Mutassuk meg, hogy ekkor $\mbox{\large$f$}$ és $\mbox{\large$g$}$ additívak (azaz pl. $\mbox{\large$f(x\lor y)= f(x) \lor f(y)$}$)!
    b) Tegyük fel, hogy egy Boole-algebrán $\mbox{\large$c$}$ egy unér extenzív függvény ( $\mbox{\large$x\leq c(x)$}$). Bizonyítsuk be, hogy ekkor a kövtkezők ekvivalensek:
      (i) $\mbox{\large$c$}$ idempotens, additív, komplementált ( $\mbox{\large$c(x)= c(c(x))$}$, $\mbox{\large$c(x\lor y)= c(x)\lor c(y)$}$, $\mbox{\large$c(-c(x))= -c(x)$}$);
      (ii) $\mbox{\large$c(0)=0$}$, $\mbox{\large$c(x\land c(y))= c(x)\land c(y)$}$.
  • 13. feladat Mutassunk nem egyszeresen összefüggő véges topologikus teret! Keressük meg univerzális fedőterét is!
  • 14. feladat Ágyazzuk be a megszámlálhatóan végtelen sok elemmel generált szabad Boole-algebra Boole-terét a valós számok terébe!
  • 15. feladat Legyen $\mbox{\large$\bf B$}$ Boole-algebra, $\mbox{\large$f: {\bf B}^n \longrightarrow {\bf B}$}$ additív normális függvény, $\mbox{\large$R$}$ a neki megfelelő atomreláció (ha $\mbox{\large$\langle U_1,\dots U_n, V \rangle$}$ ultraszűrők $\mbox{\large$n+1$}$-ese, $\mbox{\large$\langle U_1,\dots U_n, V \rangle \in R$}$, ha $\mbox{\large$f^\supset(U_1, \dots, U_n)\subseteq V$}$). Legyen $\mbox{\large$x\in B$}$. Mutassuk meg, hogy ha
    a) $\mbox{\large$n=1$}$, akkor $\mbox{\large$R^{-1}(\overset\~x)$}$ zárt!;
    b) $\mbox{\large$n\geq 2$}$, akkor alkalmasan választott $\mbox{\large$\bf B$}$, $\mbox{\large$f$}$, $\mbox{\large$x$}$ mellett $\mbox{\large$R^{-1}(\overset\~x)$}$ nem zárt!
  • 16. feladat Mutassuk meg, hogy kettőnél nagyobb dimenzióban az orto-cilindrifikációk felcserélhetőségéből nem következik a konszonancia! (Van $\mbox{\large$R$}$ háromváltozós reláció és $\mbox{\large${\bf A} \leq \langle R, c_0^\perp, c_1^\perp, c_2^\perp\rangle$}$, hogy $\mbox{\large$\bf A$}$-ban felcserélhetők az orto-cilindrifikációk, de $\mbox{\large$\bf A$}$ nem konszonáns.)
  • 17. feladat Legyen t az az algebrai típus, amely egyetlen kétváltozós függvényjelből áll. Mutassunk olyan t típusú varietást, amely nem axiomatizálható véges sok változót használó kvantormentes formulahalmazzal!
  • 18. feladat Mutassuk meg, hogy $\mbox{\large$n < \omega$}$ esetén az $\mbox{\large${\bf S} \{ \langle R, {\sf c}_0^\perp,\dots {\sf c}_{n-1}^\perp \rangle: R\ n \mbox{ v\'altoz\'os rel\'aci\'o} \} $}$ varietás nem diszkriminátorvarietás, de generálják a benne levő diszkriminátoros algebrák!
  • 19. feladat Bizonyítsuk be, hogy egy struktúraosztály pontosan akkor zárt a részstruktúra-képzésre, ha axiomatizálható kvantormentes végtelen formulákkal (esetleg osztálynyi sokkal)! (Végtelen formulán a következőt értjük: rögzítjük változók egy $\mbox{\large$\{x_\xi: \xi \mbox{ rendsz\'am}\} $}$ osztályát, és ezek használatával képzünk olyan formulákat, melyekben az elsőrendű konnektívákon túl szerepelhet végtelen (halmaznyi méretű) konjunkció és diszjunkció is.)
  • 20. feladat Egy teljes relációalgebra nem más, mint valamely $\mbox{\large$U$}$ halmaz mellett a $\mbox{\large${\bf P}(U\times U)$}$ Boole-algebra kiegészítése a binér relációkompozíció és unér reláció-inverz műveletekkel, ill. a diagonális konstanssal. A halmaz-relációalgebrák pedig a teljes relációalgebrák részalgebrái. A reprezentálható relációalgbrák pedig a halmaz-relációlagebrák osztályának $\mbox{\large$\bf {SP}$}$-lezártjának elemei.
    a) Jellemezzük a halmaz-, ill. a reprezentálható relációalgebrák atomstruktúráit!
    b) Mutassuk meg, hogy a reprezentálható relációalgebrák varietást alkotnak, s hogy e varietásnak rekurzíve felsoroható az azonosságelmélete!




    Levél az előadónak (Henk Csaba)

    Vissza
    Vissza a főoldalra