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ů

## Normální tvary výrokových formulí, prenexní tvary formulí predikátové logiky

Poznámka (Vlastnosti log. spojek)

Platí:

1. ;
2. ;
3. je idempotentní, komutativní a asociativní.
5. DeMorganovy zákony: ;
6. je monotonní ( ), idempotentní, komutativní a asociativní.
7. a jsou navzájem distributivní.

Věta (o ekvivalenci ve výrokové logice)

Jestliže jsou podformule formule ekvivalentní s ( ) a vytvořím nahrazením místo , je i ekvivalentní s . (Důkaz indukcí podle složitosti formule, rozborem případů tvaru , )

Lemma (o důkazu rozborem případů)

Je-li množina formulí a formule, pak platí právě když a .

Definice (Normální tvary)

Výrokovou proměnnou nebo její negaci nazveme literál. Klauzule budiž disjunkce několika literálů. Formule v normálním konjunktivním tvaru (CNF) je konjunkce klauzulí. Formule v disjunktivním tvaru (DNF) je disjunkce konjunkcí literálů.

Věta (o normálních tvarech)

Pro každou formuli lze sestrojit formule v konjunktivním, resp. disjunktivním tvaru tak, že , . (Důkaz z DeMorganových formulí a distributivity, indukcí podle složitosti formule)

Subsections

- Prenexní tvary formulí predikátové logiky