Logică și structuri discrete - Tema 10
1.
Se dau următoarele premise:
- Orice elev e fericit dacă toți prietenii săi reușesc bacalaureatul.
- Orice elev bun își ajută prietenii.
- Oricine e ajutat de cineva reușește tot ce încearcă.
- Orice elev încearcă bacalaureatul.
și concluzia: Orice elev bun e fericit.
- Formalizați afirmațiile de mai sus.
- Găsiți o interpretare (un exemplu de univers, împreună cu valorile predicatelor) în care premisele sunt adevărate, dar concluzia nu.
- Demonstrați că premisele implică concluzia într-un univers format doar din elevi.
(Împreună cu punctul anterior, asta ne arată că nu e corect să formalizăm problema fără predicatul 'elev', presupunând implicit că orice X e elev).
- Modificați una din premise astfel încât concluzia să devină adevărată
(fără vreo altă restricție).
2. Definiți (desenați) un automat care acceptă toate șirurile de 0 și 1 care nu au trei simboluri identice consecutive.
Indicatie: Automatul va avea stări care corespund ultimelor două simboluri întâlnite (sau altfel zis, indică numărul de simboluri identice de la sfârșitul șirului parcurs, și de care fel: 1100100 are la sfârșit două simboluri 0; 1101 are la sfârșit un simbol 1).
3. Pentru expresia regulată de la curs: (0|10)*(1|ε):
a) scrieți toate șirurile de lungime 5 pe care le generează (adică din limbajul descris de expresia regulată)
b) demonstrați cât mai riguros că ea generează orice șir de 0 și 1 care nu are două simboluri 1 consecutive.
Marius Minea
Last modified: Tue Nov 29 20:05:00 EET 2016