Know-how, prelegere, teoremă a erbrane

Forma normală primară

Se spune că formula este în forma normală, dacă sunt lăsate toți cuantificatorii din ea, adică dacă are forma

unde sunt cuantificatorii universalității sau existenței, sunt variabile și este o formulă fără cuantificator. Această formulă poate avea parametri (dacă formula are alți parametri decât).

Rezultatul principal al acestei secțiuni este că orice formulă (probabilă) este echivalentă cu o anumită formulă în forma normală prefixată (formula prefixată). O vom dovedi, construind simultan o clasificare a formulelor (într-un anumit sens reflectând "complexitatea lor logică"). Ca măsură a complexității, s-ar putea lua numărul de cuantificatori în forma normală prefixată. Dar este mai corect să țineți cont de numărul de grupuri de cuantificatori (presupunând că cuantificatorii cu același nume au unul în fața lor).

Se spune că formula prefixată este o formulă dacă prefixul cuantificator conține grupuri cuantificatoare, cu cuantificatorii existenței fiind primul. Dacă sunt primii cuantificatorii universalității. vorbesc despre clasă. (Notatia similara este folosita in teoria algoritmilor pentru clasificarea seturilor aritmetice, vezi [5]).

Exemplu: formula aparține clasei, formula aparține clasei, iar formula nu este în forma normală deloc.

103. Indicați formula în forma normală prefixată, probabil echivalentă cu ultima dintre formulele de mai sus.

Suntem interesați de ceea ce se întâmplă cu "complexitatea logică" a formulei măsurate în acest fel în cadrul operațiilor logice. Să începem cu observații foarte simple.

• Fiecare formula dintr-o clasă este fie probabil echivalentă cu o formulă dintr-o clasă, cât și cu o formulă dintr-o clasă. De fapt, dacă formula nu are parametru, atunci ea va fi probabil echivalentă cu formulele și (o implicație este o axiomă, cealaltă este obținută din regula Bernays). Astfel, putem adăuga un cuantificator inactiv la începutul cuantificatorului sau la sfârșitul lui; în al doilea caz, trebuie să ne referim la Lemma 2.
• Negarea oricărei formule dintr-o clasă este probabil echivalentă cu o anumită formulă din clasă și invers. De fapt, am văzut că deductibilul este echivalent și invers, astfel încât negarea poate fi transmisă în interior, schimbând cuantificatorii spre cei dublați în cursul chestiunii.

Vom arăta că conjuncția a două formule este echivalentă cu o anumită formulă din. De exemplu, o conjuncție este echivalentă cu o formulă. De fapt, folosind axioma despre cuantificator universal, ne putem retrage din, și să se retragă din, astfel încât conjuncția producției lor, atunci puteți închide două Cuantificator universale. În cealaltă direcție: derivăm formula, aplicăm regula Bernays și așa mai departe.

104. Arătați că puteți salva un cuantificator și puteți folosi formula.

Motivul general (pentru oricare două formule din clasă) este aproape la fel de simplu, este necesar doar să redenumiți variabilele asociate, folosind Teorema 52.