Definiția 8. Formula A a logicii predicate se consideră fezabilă în domeniul M dacă există valori ale variabilelor care intră în această formulă și care sunt legate de domeniul M (altfel există un model) pentru care formula A ia valori adevărate.
Definiția 9. Formula A a logicii predicatelor este numită realizabilă. dacă există o zonă pe care această formulă este fezabilă.
Definiția 10. Formula A a logicii predicate se spune că este identică în domeniul M (fezabil) dacă are nevoie de valori adevărate pentru toate valorile variabilelor care intră în această formulă și care sunt legate de această regiune.
Definiția 11. Formula A a logicii predicatelor se numește universal validă. dacă este identic cu cel real în fiecare domeniu (pe orice model).
Dacă două formule echivalente ale logicii predicatelor sunt combinate de semnul echivalenței. atunci formula rezultată va lua valoarea lui AND pentru orice set de variabile în orice regiune, adică vor fi în general valabile.
Acest concept este o generalizare a conceptului de identitate a adevărului formulării logicii propoziționale. Toate legile logice, introduse în formulele logice propozitionale sunt valabile în formulele generale ale logicii predicatelor și exprima, precum și o altă formulă universal valabilă, legile logicii în limbajul logicii predicatelor.
Valoarea generală a formulei logice predicate, de exemplu, F, este notată cu # 9500; F. Toate formulele valide pot fi surse de noi # 9500; formule. De exemplu, substituind predicatul P (x1, ..., xn) pentru legea exterioară excluse, obținem formula P (x1, ..., xn) (x1, ..., xn). Pentru n = 1 avem o formulă validă. și, prin urmare, este o formulă valabilă universal pentru logica predicatelor.
Din formula adevărată a logicii propoziționale, substituind P (x, y) pentru predicatul P (x, y) în loc de x și în loc de predicatul y Q (x, y), obținem o formulă general valabilă,
Definitia 12. Formula A a logicii predicate se spune ca este identica falsa in domeniul M daca are nevoie de o valoare falsa pentru toate valorile variabilelor care intra in aceasta formula si atribuite acestei regiuni (cu alte cuvinte, pe modelul dat).
Definiția 13. Formula A a logicii predicatelor este considerată a fi identică falsă (nerealizabilă) dacă este identică falsă în fiecare domeniu (pe fiecare model).
De exemplu, formula este formula identică (imposibilă) a logicii predicatelor.
Din definițiile de mai sus, este evident că:
1. Dacă formula A este validă, atunci este posibilă pentru fiecare domeniu (model).
2. Dacă formula A este identică în domeniul M, atunci este posibilă și în acest domeniu.
3. Dacă formula A este identic falsă în domeniul M, atunci aceasta nu este fezabilă în această regiune.
4. Dacă formula A nu este fezabilă, atunci este identic fals pe fiecare domeniu (pe fiecare model).
5. Pentru ca formula A a logicii predicatelor să fie valabilă, este necesar și suficient ca negarea ei să nu fie fezabilă.
6. Pentru ca formula A a logicii predicatelor să fie fezabilă, este necesar și suficient ca formula să nu fie universal valabilă.
Exemplul 1. Dovedirea echivalenței (identitate logică):
Observând că în fiecare dintre subformulele cuantificatoare ambele variabile obiective sunt conectate și că, prin urmare, acestea sunt declarații, introducem notația:
B = sau indicând prima și a doua variabilă a subiectului prin n1 și respectiv n2:
În această notație, identitatea definită pentru examinare va arăta astfel :.
Efectuând transformări echivalente, putem verifica validitatea acestei identități:
Dacă caracterizăm expresia ca întreg, vedem că aceasta este o formulă valabilă universal.
Exemplul 2. Determinați tipul de formulă.
Să presupunem că F (x). "Numărul x este egal -" predicatul definit în M = N 2.
Astfel, formula luată în considerare pe acest model este următoarea afirmație: "Printre numerele naturale există atât drepte, cât și ciudate". Evident, această afirmație este adevărată și, astfel, pe modelul dat, formula F este identică.
Cu toate acestea, dacă același predicat este dat pe setul M = N × N, unde N este setul de numere par, atunci formula F pe acest model se dovedește a fi identic falsă.
Având în vedere cele de mai sus, concluzionăm că formula F considerată fezabilă (dar nu este universal valabilă).
Exemplul 3. Pentru o formulă, alegeți un model pe care este identic adevărat (și astfel, în general, fezabil).
Fie P (x, x, y): "x" x = y "sau altceva" x 2 = y "este un predicat definit pe setul de numere naturale, M = N. Apoi, formula în cauză exprimă declarația despre existența unui pătrat natural cu un număr natural, care, evident, este adevărat, adică pe modelul dat, formula este identică, după cum este necesar.
Exemplul 4. Luați în considerare formula. Aceasta este o formulă inteligibilă. Într-adevăr, în cazul în care F (x, y, x): "x + y = x" - suma predicate, atunci există M = N substituție pentru valorile y respective, autorizând valoare de adevăr a formulei. Evident, aceasta este y = 0, pentru că în acest caz ajungem "x = x".
Dacă P (x, y, x): "xy = x" este predicatul produsului, atunci y este 1 pentru această valoare, deoarece cu el primim instrucțiunea adevărată.
Dar acestea sunt singurele permutări care duc la afirmații corecte, care este tocmai valabilitatea formulei date (dar nu a valabilității sale generale).
Exemplul 5. Este formula valabilă :?
Fie P (x, y) un predicat al ordinii (relație binară) "" definit pe un set finit de numere naturale M1. Apoi, atunci când înlocuim o variabilă pentru variabila liberă în formula, obținem declarația adevărată, iar atunci când înlocuim orice altă constanță din setul M1, este falsă. Astfel, formula în cauză nu este universal valabilă.
Exemplul 6. Luați în considerare formula. Vom arăta că este imposibil.
Să presupunem contrariul, adică că este fezabil. Aceasta înseamnă că există un astfel de set M și un astfel de predicat specific în el atunci când. atunci această formulă se transformă într-un astfel de predicat specific. care, la rândul său, se transformă într-o declarație adevărată pentru orice substituire a elementelor din setul M pentru y. Atunci afirmația este adevărată, după cum tocmai am stabilit. În consecință, afirmațiile sunt adevărate.
Din adevărul celei de-a doua afirmații, concluzionăm că afirmația este adevărată (din moment ce "pentru toate variabilele obiective", totuși ele pot fi desemnate). Dar aceasta contrazice adevărul primei vorbe.
Astfel, presupunerea noastră de validitate a formulei este falsă.
Problema solvabilității în logica predicatelor este pusă la fel ca în algebra logică: există algoritmi care permit oricărei formule A a logicii predicate să stabilească ce tip (clasă) îi aparține, adică. dacă este universal valabil, fezabil sau identic fals (imposibil de realizat). Dacă ar exista un astfel de algoritm, atunci, ca și în algebra propozițiilor, ar fi redus la criteriul adevărului identic al oricărei formule a logicii predicatelor. Rețineți că, spre deosebire de algebra logică, în logica predicatelor, nu se aplică metoda enumerării tuturor variantelor valorilor variabilelor incluse în formula, deoarece poate exista un set infinit de astfel de variante.
Calculul predicat este un exemplu al unui sistem formal insolvabil. Insolvabilitatea calculului predicat a fost dovedită în 1936 de către logicianul american Alonzo Church. Teorema pe care a demonstrat-o arată că nu există o procedură eficientă pentru rezolvarea problemei unei formule arbitrare a unui sistem formal care să conțină numere naturale aritmetice, indiferent dacă această formulă este o teoremă.
Articole similare
-
Elemente ale logicii matematice, forme normale de formule ale algebrului logicii
-
Indexarea alimoniei de la a la i este o formulă și o declarație!
Trimiteți-le prietenilor: