Definiția. Se spune că formula logică predicată are o formă normală dacă conține doar conjuncții, disjuncții și operații cuantificatoare, iar operația de negare se referă la formule elementare.
Evident, folosind echivalența algebrică a propozițiilor și logica predicatelor, fiecare formulă a logicii predicatelor poate fi redusă la o formă normală. De exemplu, vom reduce formula la forma normală
Utilizarea transformărilor echivalente. avem
Printre formele normale ale formulelor logicii predicatelor, așa-numitele forme normale primordiale (pnf) au o mare importanță. În ele, operațiile cantitative sunt fie complet absente, fie ele sunt utilizate după toate operațiile algebrei logice, adică forma predefinită a formei normale a logicii predicate are forma
unde simbolul A nu conține un cuantificator.
Teorema. Orice formulă a logicii predicatelor poate fi redusă la forma normală prefixată.
Dovada. Vom presupune că formula a fost deja redusă la o formă normală și am arătat că aceasta poate fi redusă la forma normală.
Dacă formula dată este elementară, atunci ea nu conține cuantificatori și, prin urmare, are deja o formă normală prefixată.
Să presupunem acum că teorema este adevărată pentru formulele care conțin cel mult operații k și demonstrăm că, în această ipoteză, ea va ține de asemenea și pentru formule. care conține o operație exactă k + 1.
Să presupunem că formula A conține o operație k 1 și are forma L (x), unde este indicat unul din cuantifiatori.
Deoarece L (x) conține operații k și, prin urmare, poate fi considerată redusă la forma normală normală, atunci toate operațiunile cantitative sunt înaintea ei. Dar atunci formula L (x), evident, are o formă normală predefinită.
Să presupunem că formula A are forma, unde formula L este redusă la forma normală prefixată și conține operații k. Apoi, cu ajutorul echivalențelor 1 și 2, negarea poate fi introdusă sub semnul cuantificatorului și aceasta va conduce formula A la forma normală prefixată.
Să presupunem că formula A are forma, unde și sunt reduse la forma normală prefixată.
Să redenumim variabilele legate de obiect în formula astfel încât în formulele toate variabilele de subiect asociate să fie diferite. În acest caz, formulele trebuie să fie scrise în formular
Folosind echivalența dintre 7 și 1, vom scrie formula A, introducând formula sub semnele cuantificatorului:
Apoi introducem o formulă sub semnele cuantificatorului. Apoi pentru formula A obtinem forma normala prefixata:
Dovada se efectuează în mod similar și în cazul în care formula A are forma .
Notă. Dacă în procesul de reducere a formulei logice predicate la pnf. este necesar să luăm în considerare expresia sau expresia, atunci trebuie să folosim echivalențele 5 și 10.
De exemplu, aducem la normalul anterior
Articole similare
Trimiteți-le prietenilor: