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ů

### Dokazatelnost

Definice (Axiomy výrokové logiky)

Pro redukovaný jazyk výrokové logiky (po snížení počtu log. spojek na základní ( )) jsou axiomy výrokové logiky (schémata axiomů) všechny formule následujících tvarů:

- (A1 - implikace sebe sama)
- (A2 - roznásobení)
- (A3 - obrácená negace implikace)

Definice (Odvozovací pravidlo výrokové logiky)

Výroková logika má jediné odvozovací pravidlo - modus ponens:

Definice (Důkaz ve výrokové logice)

Důkaz je konečná posloupnost formulí , jestliže a pro každé je buď axiom, nebo je odvozená z předchozích pravidlem modus ponens. Existuje-li důkaz formule , pak je tato dokazatelná ve výrokové logice (je větou výrokové logiky - ).

Definice (Důkaz z předpokladů)

Důkaz formule z předpokladů je posloupnost formulí taková, že a je axiom, nebo prvek množiny předpokladů , nebo je odvozena z přechozích pravidlem modus ponens. Existuje-li důkaz z , pak je dokazatelná z - .

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

Pro množinu formulí a formule platí:

právě když

Definice

Množina formulí je sporná, pokud je z předpokladů dokazatelná libovolná formule, jinak je bezesporná. je maximální bezesporná množina, pokud je bezesporná a navíc jediná její bezesporná nadmnožina je samo. Množina všech formulí dokazatelných z se značí .

Věta (Lindenbaumova)

Každou bezespornou množinu formulí výrokové logiky lze rozšířit na maximální bezespornou , .

Věta (o bezespornosti a splnitelnosti)

Množina formulí výrokové logiky je bezesporná, právě když je splnitelná.

Věta (Věta o úplnosti výrokové logiky)

Je-li množina formulí a formule, pak platí:

1. právě když
2. právě když ( je větou výrokové logiky, právě když je tautologie)

Tedy výroková logika je bezesporná a jsou v ní dokazatelné právě tautologie.

Věta (o kompaktnosti)

Množina formulí výrokové logiky je splnitelná, právě když je splnitelná každá její konečná podmnožina.

Definice (Formální systém predikátové logiky)

Pracujeme s redukovaným jazykem (jen s log. spojkami a jen s kvantifikátorem ). Schémata Axiomů predikátové logiky vzniknou z těch ve výrokové logice prostým dosazením libovolných formulí predikátové logiky za výrokové proměnné. Modus ponens platí i v pred. logice. Další axiomy a pravidla:

- schéma(axiom) specifikace:
- schéma přeskoku: , pokud proměnná nemá volný výskyt v .
- pravidlo generalizace:

Toto je formální systém pred. logiky bez rovnosti. S rovností přibývá symbol a další tři axiomy.

Poznámka (Vlastnosti formulí predikátové logiky)

1. Je-li instance formule , pak jestliže platí , platí i . (Věta o instancích)
2. Je-li uzávěr formule , pak platí právě když . (Věta o uzávěru)

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

Nechť je množina formulí pred. logiky, je uzavřená formule a lib. formule, potom právě když .

Definice (Teorie, model)

Pro nějaký jazyk prvního řádu je množina formulí tohoto jazyka teorie prvního řádu. Formule z jsou speciální axiomy teorie . Pro interpretaci jazyka je model teorie ( ), pokud jsou všechny speciální axiomy pravdivé v . Formule je sémantickým důsledkem : , jestliže je pravdivá v každém modelu teorie .

Věta (o korektnosti)

Je-li teorie prvního řádu a formule, potom platí:

1. Jestliže , potom .
2. Speciálně jestliže , potom .

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

Nechť je teorie s jazykem prvního řádu . Je-li lib. formule jazyka , pak platí:

1. právě když
2. je bezesporná, právě když má model.

Definice (Úplná teorie)

Teorie s jazykem prvního řádu je úplná, je-li bezesporná a pro libovolnou uzavřenou formuli je jedna z formulí dokazatelná v .

Věta (o kompaktnosti)

Teorie s jazykem prvního řádu má model, právě když každý její konečný fragment má model. Tj. pro libovolnou formuli jazyka platí: právě když pro nějaký konečný fragment .