Limba logicii predicatelor
În definițiile limbilor formale. cum ar fi limbile logice sau limbile de programare, disting două aspecte principale: sintaxa și semantica. Sintaxă \ index<Синтаксис> determină alfabetul. din simbolurile cărora sunt construite expresiile de limbă și regulile care selectează expresiile construite corect din mulțimea tuturor cuvintelor din alfabetul dat. Pentru limbile logice, astfel de expresii sunt numite, de obicei, formule, iar pentru limbile de programare, programele. Semantica \ index<Семантика> este implicat în determinarea semnificației, a semnificației acestor expresii. Pentru formule în majoritatea limbilor logice, valoarea este una dintre valorile adevărului. 1 (adevărat) sau 0 (fals), care este atribuită formulei, în funcție de interpretarea simbolurilor limbajului inclus în ea. De exemplu, valorile formulelor logice propoziționale depind de valorile variabilelor booleene incluse în ele. Valorile formulelor logicii predicate definite în această secțiune vor depinde de interpretarea predicatelor și funcțiilor limbii, precum și de valorile variabilelor care intră în aceste formule.
Sintaxă: formule de logică predicată
Formulele limbajului logicii predicate includ simbolurile (denumirile) predicatelor din unele seturi, simbolurile (numele) funcțiilor dintr-un anumit set, simbolurile (denumirile) constantelor dintr-un set C =
Definim termenul unei semnături date
Definiție 7.1. Termenul. Un termen este o expresie constând din variabile, virgule, paranteze și simboluri ale semnăturii, care pot fi construite conform următoarelor reguli.
- O variabilă de obiect de la Var este un termen.
- Simbolul unei constante în C este un termen.
- Dacă t1. tk sunt termeni. și f (k) este simbolul unei funcții în F. atunci f (t1, tk) este un termen.
Termeni. care nu conține variabile, se va numi închis.
Terme sunt folosite pentru a specifica obiecte. Termenii închise definesc direct obiectele.
Apoi, cel mai simplu mod de a specifica un obiect este acela de a specifica constanta potrivita, de exemplu "Peter", "John", 0, 1, 47. Termenul + (17, 25) stabileste obiectul 42. Termenul best_friend (tatal "Peter") stabilește obiectul - persoana care este cel mai bun prieten al tatălui obiectului "Petru". și salariul pe termen (best_friend (tatăl ("Peter"))) stabilește obiectul - numărul reprezentând salariul acestei persoane. Valorile variabilelor sunt, de asemenea, obiecte. Prin urmare, termenii cu variabile specifică obiecte concrete atunci când substituie valori în locul variabilelor. Dăm câteva exemple ale termenilor date semnătură: x, tată (x), salariu (luchshiy_ fiecare (tată (tată (z)))), + (salariu (luchshiy_ fiecare (tată (z))), + (salariu ( „Olga "), Tatăl (5), + (tatăl (" Olga "), 1000)). Rețineți că ultimii doi termeni sunt construiți în conformitate cu regulile noastre, dar nu este clar care sunt obiectele pe care le pot specifica. Aceasta depinde de definirea funcției tatălui pe numere și de funcția + pe perechi de argumente ale formularului (Face, Număr). Adesea, un set de obiecte include un obiect special "ERROR". care este valoarea funcțiilor pe argumente incorecte.
Expresii x +10, tatăl ("John", "Peter"), + (100)>, best_friend ("Maria") nu sunt termeni ai acestei semnături. (Determinați de ce.)
Definiția 7.2. Formula atomică.
- Dacă t1 și t2 sunt termeni. atunci expresia (t1 = t2) este o formulă atomică.
- Orice predicat 0 simbolul locului lui P este o formulă atomică.
- Dacă P (k) (k> = 1) este un simbol predicat k-loc de la P. și t1. tk sunt termeni. atunci expresia P (t1, tk) este o formulă atomică.
Exemplul 7.2. Luați în considerare o semnătură în care P = <живут_рядом (2). сын (2). дочь (2). родственники (2). человек (1). число (1). <= (2)>. iar funcțiile F și constantele C sunt definite în exemplul de mai sus.
Apoi, următoarele expresii sunt formule atomice. "Petru", "Petru" = 6, tatăl ("Olga") = "Petru", + (3,5) = + ("Ioan", "Olga"), fiica ("Olga", x), rudele (x)) și altele asemenea.
Formulele pentru logica predicatelor sunt construite conform următoarelor reguli:
Definiția 7.3. Formula.
- Fiecare formulă atomică este o formulă.
- Dacă - formula, atunci - formula.
- Dacă u sunt formule, atunci expresiile ,,, sunt și formule.
- Dacă este o formulă, a este o variabilă de obiect. atunci expresiile u sunt formule (în acest caz, ele sunt numite intervalul cuantificatorului sau, respectiv,).
Conceptul unei subformule pentru formulele logicii predicatelor este definit într-un mod natural. În primul rând, formula însăși este subformula sa. În al doilea rând, dacă formulele au forma sau, atunci subformulele ei sunt, de asemenea, toate subformulele formulei și dacă are forma sau, atunci subformulele sale sunt, de asemenea, toate subformulele formulelor și
De asemenea, definim conceptele de variabile libere și libere ale formulei. Apariția variabilei x în formula se numește legată. dacă intră în intervalul unui anumit cuantificator sau. În caz contrar, se numește liberă. Cuantificatorul () asociază în formula () toate aparițiile libere ale variabilei x din subformula
Să presupunem că în unele semnături există două predicate P (2) cu două locații. Q (2). Apoi, în formulă
ambele apariții ale lui x în subformula sunt legate printr-un cuantificator, prima apariție a y este liberă, iar a doua este conectată printr-un cuantificator. Ambele apariții ale lui x în subformula sunt legate printr-un cuantificator.
O variabilă este numită liberă (legată) într-o formulă dacă are cel puțin o apariție liberă (legată) în această formulă. O formulă care nu are variabile libere. se spune că este închis. Rețineți că variabila poate fi simultan conectată și liberă în formula dată.
Exemplul 7.3. Luați în considerare exemplele de formule din semnătura din Exemplul 7.2:
În această formulă, toate aparițiile variabilelor x și y sunt legate și, prin urmare, sunt o formulă închisă. În mod semnificativ, ea susține că fiecare persoană are un vecin-om. Este clar că adevărul acestei afirmații nu depinde de numele variabilelor utilizate în formula.
În formula, toate aparițiile variabilei y sunt legate, prima apariție a lui x este, de asemenea, conectată, iar a doua apariție a lui x este liberă, deoarece nu intră în sfera de cuprindere a cuantificatorului. Astfel, x este legat și liber. Această formulă afirmă că există o persoană care este legată de toată lumea sau nu locuiește lângă x și are un salariu> = 35. Este clar că adevărul acestei formule depinde de valoarea variabilei libere x.
Articole similare
-
Cunoștințe, prelegere, fundamentele tehnicilor de exerciții independente
-
Cunoștințe, prelegere, crearea meniului principal al aplicației
Trimiteți-le prietenilor: