Formular pre-anexat
O formulă de logică de ordinul întâi este sub formă de apendice dacă toți cuantificatorii ei ( și ) apar în stânga în acea formulă. Adică, G este într-o formă pre-anexată dacă și numai dacă cu și o formulă fără cuantificatori.
∀{\ displaystyle \ forall}
∃{\ displaystyle \ există}
G=Î1X1Î2X2...ÎnuXnuG′{\ displaystyle G = Q_ {1} x_ {1} Q_ {2} x_ {2} ... Q_ {n} x_ {n} G ^ {\ prime}}
Îeu∈{∀,∃}{\ displaystyle Q_ {i} \ in \ {\ forall, \ există \}}
G′{\ displaystyle G ^ {\ prime}}![G ^ {{\ prime}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d8979dd3bf9e55f5fbf37f3678f13fdd93c218b)
Toate formulele de ordinul întâi sunt în mod logic echivalente cu o formulă în formă de apendice.
Complexitatea unei formule logica de pre-formatat este măsurată prin prima Cuantificator și de numărul de alternanta de blocuri de cuantificatori universale sau existențiale pe care - l urmează și preceda formula fără un cuantificator.
Reguli de transformare
Pentru a pune o formulă logică în formă de apendice, putem folosi următoarele reguli de transformare între formule echivalente:
Glatuvs.he⇒Droeute{\ displaystyle Left \ Rightarrow Right}![{\ displaystyle Left \ Rightarrow Right}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b50a0df04cef240ca1f81348d35b5e2272583498)
#
|
Forma inițială
|
Formular pre-anexat
|
---|
1
|
¬∀XF{\ displaystyle \ lnot \ forall xF}
|
∃X¬F{\ displaystyle \ există x \ lnot F}
|
2
|
(∀XF)∧G{\ displaystyle (\ forall xF) \ land G}
|
∀X(F∧G){\ displaystyle \ forall x (F \ land G)}
|
3
|
(∀XF)∨G{\ displaystyle (\ forall xF) \ lor G}
|
∀X(F∨G){\ displaystyle \ forall x (F \ lor G)}
|
4
|
(∀XF)→G{\ displaystyle (\ forall xF) \ rightarrow G}
|
∃X(F→G){\ displaystyle \ există x (F \ dreapta G)}
|
5
|
G∧(∀XF){\ displaystyle G \ land (\ forall xF)}
|
∀X(G∧F){\ displaystyle \ forall x (G \ land F)}
|
6
|
G∨(∀XF){\ displaystyle G \ lor (\ forall xF)}
|
∀X(G∨F){\ displaystyle \ forall x (G \ lor F)}
|
7
|
G→(∀XF){\ displaystyle G \ rightarrow (\ forall xF)}
|
∀X(G→F){\ displaystyle \ forall x (G \ rightarrow F)}
|
8
|
¬∃XF{\ displaystyle \ lnot \ există xF}
|
∀X¬F{\ displaystyle \ forall x \ lnot F}
|
9
|
(∃XF)∧G{\ displaystyle (\ există xF) \ land G}
|
∃X(F∧G){\ displaystyle \ există x (F \ land G)}
|
10
|
(∃XF)∨G{\ displaystyle (\ există xF) \ lor G}
|
∃X(F∨G){\ displaystyle \ există x (F \ lor G)}
|
11
|
(∃XF)→G{\ displaystyle (\ exists xF) \ rightarrow G}
|
∀X(F→G){\ displaystyle \ forall x (F \ rightarrow G)}
|
12
|
G∧(∃XF){\ displaystyle G \ land (\ există xF)}
|
∃X(G∧F){\ displaystyle \ există x (G \ land F)}
|
13
|
G∨(∃XF){\ displaystyle G \ lor (\ există xF)}
|
∃X(G∨F){\ displaystyle \ există x (G \ lor F)}
|
14
|
G→(∃XF){\ displaystyle G \ rightarrow (\ există xF)}
|
∃X(G→F){\ displaystyle \ există x (G \ rightarrow F)}
|
Variabila x nu trebuie să aibă nicio apariție liberă în G (vezi Calculul predicatelor ). În caz contrar, redenumiți x în prealabil cu o nouă variabilă care nu apare liber în formulele F și G.
Observații
Nu există reguli simple de transformare pentru o formulă care include conectorul, dar aceste reguli sunt suficiente deoarece este un sistem complet de conectori. Prin urmare, pentru a transforma o formulă, putem aplica această abordare:
↔{\ displaystyle \ leftrightarrow}
{¬,∧,∨,→}{\ displaystyle \ {\ lnot, \ land, \ lor, \ rightarrow \}}![{\ displaystyle \ {\ lnot, \ land, \ lor, \ rightarrow \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02e356c1e38f7586ca71efcab461df2fabf4134b)
- Eliminați echivalențele, înlocuindu-le cu implicații;
- Negații de transport în fața formulelor atomice;
- Duceți cuantificatorii la capul formulei, redenumind variabilele dacă este necesar.
Articole similare
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">