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.

1. Formalizați afirmațiile de mai sus.
2. Găsiți o interpretare (un exemplu de univers, împreună cu valorile predicatelor) în care premisele sunt adevărate, dar concluzia nu.
3. 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).
4. 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.