Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Prenexní tvary formulí predikátové logiky

Věta (o ekvivalenci v predikátové logice)

Nechť formule vznikne z nahrazením některých výskytů podformulí po řadě formulemi . Je-li , potom platí i .

Definice (Prenexní tvar)

Formule predikátové logiky je v prenexním tvaru, je-li

kde a je nebo , je otevřená formule a kvantifikované proměnné jsou navzájem různé. je otevřené jádro , část s kvantifikátory je prefix .

Definice (Varianta formule predikátové logiky)

Formule je varianta , jestliže vznikla z postupným nahrazením podformulí (kde je nebo ) formulemi a není volná v . Podle věty o variantách je varianta s původní formulí ekvivalentní.

Lemma (o prenexních operacích)

Pro převod formulí do prenexního tvaru se používají tyto operace (výsledná formule je s původní ekvivalentní). Pro podformule , , kvantifikátor a proměnnou :

1. podformuli lze nahradit nějakou její variantou
3. , pokud není volná v
4. , pokud není volná v
5. , pokud není volná v
6. , pokud není volná v

Věta (o prenexních tvarech)

Ke každé formuli predikátové logiky lze sestrojit ekvivalentní formuli , která je v prenexním tvaru. (Důkaz: indukcí podle složitosti formule a z prenexních operací, někdy je nutné přejmenovat volné proměnné)