Pe scurt
Logica predicatelor de ordinul I extinde logica propozițională prin introducerea variabilelor individuale, a predicatelor (funcții propoziționale) și a cuantificatorilor universal (∀) și existențial (∃). O funcție propozițională devine propoziție logică doar când variabila este înlocuită cu un obiect dintr-un domeniu specificat, iar ordinea cuantificatorilor influențează valoarea de adevăr a formulei.
Funcții propoziționale și variabile
O funcție propozițională \( P(x) \) este o expresie care devine o propoziție logică doar atunci când variabila \( x \) este înlocuită cu un obiect dintr-un domeniu specificat.
- Exemplu: \( F(x) = \) „\( x \) este un număr par”
- Pentru \( x = 2 \), propoziția devine
adevărată
- Pentru \( x = 3 \), propoziția devine falsă
Variabilele pot fi
- Legate – cuantificate (de exemplu, \( \forall x \) sau \( \exists x \))
- Libere – necuantificate
Cuantificatorii principali
Cuantificatorul universal (\( \forall \), „pentru orice”)
- Formula \( \forall x \, P(x) \) este adevărată dacă și numai dacă \( P(x) \) este adevărată pentru fiecare element \( x \) din domeniu.
Cuantificatorul existențial (\( \exists \), „există cel puțin un”)
- Formula \( \exists x \, P(x) \) este adevărată dacă există cel puțin un element \( x \) din domeniu pentru care \( P(x) \) este adevărată.
Interdependența cuantificatorilor
Ordinea cuantificatorilor influențează semnificația formulei
- \( \forall x \, \exists y \, R(x,y) \) este diferit de \( \exists y \, \forall x \, R(x,y) \)
Exemplu pe domeniul numerelor naturale
- \( \forall x \, \exists y \, (y > x) \) este adevărat – pentru orice număr există unul mai mare
- \( \exists y \, \forall x \, (y > x) \) este fals – nu există un număr mai mare decât toate
Reguli de negare a cuantificatorilor
- \( \neg (\forall x \, P(x)) \equiv \exists x \, \neg P(x) \)
- \( \neg (\exists x \, P(x)) \equiv \forall x \, \neg P(x) \)
Forma prenexă
În forma prenexă, toți cuantificatorii sunt plasați la începutul formulei.
Exemple concrete
Exemplul 1: Domeniul numerelor întregi, predicatul \( P(x) = \) „\( x \) este par”
- \( \forall x \, P(x) \) este falsă – nu toate numerele întregi sunt pare
- \( \exists x \, P(x) \) este adevărată – de exemplu, pentru \( x = 2 \)
- Negarea: \( \neg (\forall x \, P(x)) = \exists x \, \neg P(x) \) = „există un număr întreg care nu este par” – adevărată (exemplu: \( x = 3 \))
Exemplul 2: Predicatul \( Q(x,y) = \) „\( x < y \)” pe domeniul numerelor naturale
- \( \forall x \, \exists y \, Q(x,y) \): pentru orice număr natural \( x \), există un \( y \) mai mare (de exemplu \( y = x+1 \)) → adevărat
- \( \exists y \, \forall x \, Q(x,y) \): „există un \( y \) mai mare decât toate numerele naturale” → fals (nu există un număr natural maxim)
Exemplul 3: \( R(x) = \) „\( x \) este materie obligatorie la Bac”, domeniul = mulțimea disciplinelor școlare
- \( \neg (\forall x \, R(x)) \equiv \exists x \, \neg R(x) \) traduce „nu este adevărat că toate materiile sunt obligatorii” prin „există cel puțin o materie care nu este obligatorie”
Concepte cheie
- Funcție propozițională (predicat) și variabilă liberă/legată
- Cuantificator universal (\( \forall \)) și existențial (\( \exists \))
- Echivalențe logice: \( \neg \forall x \, P(x) \equiv \exists x \, \neg P(x) \), \( \neg \exists x \, P(x) \equiv \forall x \, \neg P(x) \)
- Forma prenexă și ordinea cuantificatorilor
- Interpretarea pe domenii concrete (numere, obiecte etc.)
Verifică-te!
- Ce este o funcție propozițională și în ce condiții devine o propoziție logică?
- Care este diferența dintre formulele \( \forall x \, \exists y \, R(x,y) \) și \( \exists y \, \forall x \, R(x,y) \)?
- Cum se neagă o formulă cuantificată universal și una cuantificată existențial?