Zadání:
1. (VL)
A) P = {p, q, r} P-teorie T má axiomatiku {p, q->r}.
a) Napište formuli v DNF axiomatizující T
b) Napište JKE teorie T
B) P je nekonečná množina prvovýroků. T je teorie s axiomy {not(p) nebo not(q); p, q jsou různé prvovýroky }
a) Jak vypadají modely?
b) Je T konečně axiomatizovatelná?
c) Je množina K P-modelů, v nichž alespoň dva výroky mají pravdivé ohodnocení, konečně axiomatizovatelná?
2. (PL)
A) Jazyk L = <F>.
Struktura A = <{0, 1, 2, 3}, +>; + je sčítání modullo 4. T je L-teorie s axiomem (existuje y)(pro každé x)(F(x, y) =/= x)
a) Platí A |= T?
b) Počet různých automorfismů na A
c) Lze bezparametricky definovat množinu {2}?
d) Velikost množiny Df1(0, A)
e)
B)
a) je T otevřeně axiomatizovatelná?
b) Jazyk L' = L u {c}, T* je L'-teorie s axiomatikou {F(x,c) =/= c}. Je T* otevřená konzervativní extenze T?
c) Možná, že jsem do b) omylem napsal zadání b) a c). Nepamatuji se.
3. (PL)
A)
T teorie ostrého lineárního uspořádání, navíc s rozšířením jazyka o konstanty c0 a c1 a axiomy
chi0: c0 =/= c1
chi1: c0 <= x <= c1
a) I(n, T) pro 2 <= n € N
b)
i) má T algebraický prvomodel?
ii) má T prvomodel?
c) Je T kompletní?
d) Je T otevřeně axiomatizovatelná
e) [NESOUVISÍ S PŘEDCHOZÍM] interval [-2, 2], na něm {1 +- (1/(2^n)), n€N} u {-1 +- (1/(2^n)), n€N} (polopaticky, vezme se 1 / 2^n, a to se přičte a odečte od 1 a -1 a vzniknou dvě množiny bodů, které zleva a zprava konvergují k 1 a -1).
Má se rozhodnout, jestli je {0} množina definovatelná bezparametrickou formulí ve struktuře A = <[VÝŠE POPSANÁ MNOŽINA], <= >, kde <= je obvyklé uspořádání čísel.
B)
a) Je T rozhodnutelná?
b) Kolik má T rozhodnutelných jednoduchých extenzí?
-- možná se někde pletu, 2 A e a 2 B c si nepamatuji --
Řešení:
1 A
a) (p & non q & non r) nebo (p & non q & r) nebo (p & q & r); plyne bezprostředně z množiny modelů, obecně v je model T, jestliže v(p) = 1 a v(q) <= v(r)
b) Teorie jsou ty, které mají jako axiomatiku jednoprvkovou množinu jednoho z disjunktů formule z a). To je proto, že extenze T musí být její podmnožina a kompletní teorie má jediný model.
1B
a) Modely mají nejvýše jeden prvovýrok ohodnocen pravdou. To se dokáže snadno: má-li nějaké v pro p =/= q v(p) = v(q) = 1, potom neplatí axiom (not p nebo not q) a tudíž takové v není modelem T.
b) NE. Dokazatelné sporem: pokud je konečně axiomatizovatelné, pak se v konečné axiomatice vyskytuje konečně mnoho prvovýroků. Tedy tam jistě některé nebudou a taková axiomatika o jejich hodnocení nebude nic říkat.
c) NE. Množina K je komplement M(T). Kritérium říká, že K i -K jsou axiomatizovatelné <=> K je konečně axiomatizovatelné. V b) je dokázáno, že M(T) není. Takže vezmeme K := M(T), -K := naše množina K a hotovo.
2A
a) ANO. Stačí uspokojit ten jediný axiom. Stačí za x dosadit cokoliv kromě 0 a vyjde to (.. a pokud nevyjde, tak jsem tu axiomatiku napsal špatně )
b) 2. Jde o to, že 1 a 3 se chovají "stejně" (1+0 = 1, 3+0 = 3, 1+2 = 3, 3+2 = 1, 1+3 = 3+1 = 0, 1+1 = 2, 3+3 = 2), takže izomorfismy buď prohodí nebo neprohodí 1 a 3
c) ANO. Formule x+x = 0 a (pro každé y) y+x =/= y. (První konjunkt dá {0, 2}, druhý vyloučí nulu).
d) 8 (=23). Mohu definovat "atomické" množiny {0}, {2}, {1,3} (jak, to naznačuje c) ). Booleovskými úpravami pak i kombinace těchto tří.
2B
a) NE. Podle kritéria T je ot. axiomatizovalná <=> (A podmnožina B |= T => A |= T). Stačí za B vzít naše A a za A vzít strukturu < {0}, +>. Ta není modelem teorie T.
b) ANO. Jde o Skolemovu variantu toho jediného axiomu. Ta je s ním podle nějaké věty ekvivalentní. A je otevřená, tzn ta T* je otevřená.
3A
a) 1. Mezi c0 a c1 je v modelu o n prvcích vždy n-2 prvků, což máme zařízeno axiomy, a o uspořádání ostatních prvků axiomy nic jiného neříkají. Takže jsou modely stejné velikosti izomorfní.
b), c), d) Řešil jsem trochu jiné zadání, což mi bylo u zkoušky odpuštěno, ale řešení proto nevím.
e) NE. Poslouží to slavné kritérium o definovatelnosti množiny.
3B
a) ANO. Má rekurzivní kompletaci.
b) omega. Že jich je alespoň omega dokazuje to, že každá teorie Tn, rozšiřující T axiomem "existuje právě n prvků", spolu navíc s Tnekonečno ("existuje nekonečno prvků") je kompletní a má rekurzivní axiomatiku, tedy je rozhodnutelná. Že jich není víc, to nechám na chytřejších, aby vysvětlili.
Zkouška 4.1.2013 (předtermín)
Výroková logika, normální tvary formulí, predikátová logika, věty o úplnosti výrokové a predikátové logiky, prenexní tvary formulí, modely teorií 1. řádu. Meze formální metody, Gödelovy věty.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 15
- Registrován: 11. 1. 2012 13:08
- Typ studia: Informatika Bc.
Re: Zkouška 4.1.2013 (předtermín)
..dále k průběhu: tato písemka byla na hodinu, potom se doc. Mlček s panem Glivickým vrhli na nás a postupně to s námi s jedním za druhým konzultovali. Dlužno podotknout, že p. Glivický byl velice shovívavý, jak je z mého výše popsaného řešení patrné . Celá zkouška zabrala necelou hodinu a půl.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 2
- Registrován: 13. 1. 2012 11:44
- Typ studia: Informatika Bc.
Re: Zkouška 4.1.2013 (předtermín)
Koukám, že test už má i na stránkách:
http://ktiml.mff.cuni.cz/~mlcek/ET-1_12.pdf
http://ktiml.mff.cuni.cz/~mlcek/ET-1_12.pdf
- Přílohy
-
- ET-1_12.pdf
- (59.42 KiB) Staženo 250 x
Zpět na „AIL062 Výroková a predikátová logika“
Přejít na
- Aktuální informace
- ↳ Studijní oddělení
- ↳ Knihovna
- ↳ Studentská komora Akademického senátu (SKAS)
- ↳ Volby na ak. rok 2013/2014
- Všichni
- ↳ Práce
- ↳ Klubovna
- ↳ Toto fórum
- ↳ Státní závěrečná zkouška
- ↳ Bakalářské SZZ
- ↳ Magisterské SZZ
- ↳ Info for foreign students
- ↳ Akce
- ↳ Fotbalový turnaj 2008
- Informatika ZS
- ↳ Výuka ZS 1. ročník
- ↳ DMI002 Diskrétní matematika
- ↳ 2007
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ MAI054 Matematická analýza I
- ↳ 2007
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ MAI057 Lineární algebra I
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG030 Programování I
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ SWI120 Principy počítačů a operačních systémů
- ↳ SWI087 Principy počítačů
- ↳ Ostatní
- ↳ DMI051 Úvod do řešení problémů kombinatorických, mat. i jiných (IPS) II
- ↳ Výuka ZS 2. ročník
- ↳ MAI056 Matematická analýza III
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ OFY016 Fyzika pro nefyziky I - Svět kolem nás
- ↳ SWI089 Ochrana informace I
- ↳ SWI096 Internet
- ↳ TIN061 Algoritmy a datové struktury II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ Ostatní
- ↳ Aplikační software
- ↳ NPRG035 Jazyk C# a platforma .NET
- ↳ NPRG041 Programování v C++
- ↳ AIL062 Výroková a predikátová logika
- ↳ 2007
- ↳ 2006
- ↳ 2005
- ↳ PGR013 Java
- ↳ MAI059 Pravděpodobnost a statistika
- ↳ Výuka ZS 3. ročník
- ↳ SWI099 Administrace Systemu Windows
- ↳ SWI015 Programování v Unixu
- ↳ SWI098 Principy překladačů
- ↳ 2006
- ↳ Ostatní
- ↳ DBI007 Organizace a zpracování dat I
- ↳ 2006
- ↳ MAI062 Algebra I
- ↳ PGR003 Počítačová grafika I
- ↳ SWI090 Počítačové sítě I
- ↳ Výuka ZS NMgr.
- ↳ TIN066 Datové struktury I
- ↳ TIN062 Složitost I
- ↳ TIN064 Vyčíslitelnost I
- ↳ MAI060 Pravděpodobnostní metody
- ↳ SWI004 Operační systémy
- ↳ SWI106 Administrace Unixu
- ↳ Ostatní
- ↳ NTIN090 Základy složitosti a vyčíslitelnosti
- ↳ OPT042 Programování s omezujícími podmínkami
- ↳ AIL002 Neuronové sítě
- ↳ AIL025 Evoluční algoritmy I
- ↳ AIL069 Umělá inteligence I
- ↳ NDBI001 Dotazovací jazyky I
- ↳ TIN070 Testování software
- ↳ NDBI027 Datové sklady a analytické metody pro Business Intelligence
- ↳ NDBI034 Vyhledávání multimediálního obsahu na webu
- ↳ NPRG023 Softwarový projekt
- Informatika LS
- ↳ Výuka LS 1. ročník
- ↳ MAI055 Matematická analýza II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ MAI058 Lineární algebra II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG031 Programování II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ TIN060 Algoritmy a datové struktury I
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ SWI095 Úvod do UNIXu
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ Ostatní
- ↳ Výuka LS 2. ročník
- ↳ SWI071 Ochrana informace II
- ↳ TIN071 Automaty a gramatiky
- ↳ PRG033 Ročníkový projekt - specifikace
- ↳ DMI011 Kombinatorika a grafy I
- ↳ DBI025 Databázové systémy
- ↳ Ostatní
- ↳ SWI036 Programování pro Windows I & II
- ↳ SWI096 Internet
- ↳ PRG005 Neprocedurální programování
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ NSWI143 Architektura počítačů
- ↳ Výuka LS 3. ročník
- ↳ Ostatní
- ↳ PGR004 Počítačová grafika II
- ↳ PRG036 Technologie XML
- ↳ SZZ026 Bakalářská práce
- ↳ PRG003 Metodika programování a filozofie programovacích jazyků
- ↳ MAI064 Matematické struktury
- ↳ MAI042 Numerická matematika
- ↳ SWI021 Počítačové sítě II
- ↳ SWI045 Rodina protokolů TCP/IP
- ↳ NPRG038 Pokročilé programování pro .NET
- ↳ Výuka LS NMgr.
- ↳ SWI109 Konstrukce překladačů
- ↳ NPRG042 Programování v paralelním prostředí
- ↳ SWI117 Technologie vývoje webových aplikací
- ↳ SWI026 Softwarové inženýrství
- ↳ MAI061 Metody matematické statistiky
- ↳ I1 Ostatní Teoretická informatika
- ↳ I2 Ostatní Softwarové systémy
- ↳ I3 Ostatní Matematická lingvistika
- ↳ I4 Ostatní Diskrétní modely a algoritmy
- ↳ AIL026 Evoluční algoritmy II
- ↳ AIL070 Umělá inteligence II
- ↳ NDBI010 Dokumentografické informační systémy
- ↳ NDBI023 Dobývání znalostí
- ↳ NDBI016 Transakce
- ↳ NDBI006 Dotazovací jazyky II
- ↳ NAIL029 Strojové učení
- Matematika
- ↳ Výuka LS 1. ročník
- ↳ Lineární algebra 2
- ↳ Programování 2
- ↳ Matematická analýza 1b
- ↳ Volitelné předměty
- ↳ Výuka LS 2. ročník
- ↳ Pravděpodobnost a statistika
- ↳ Teorie Míry a integrálu II
- ↳ Algebra II
- ↳ Matematická analýza 2b
- ↳ Ostatní
- ↳ Výuka LS 3. ročník
- ↳ Předměty numeriky
- ↳ Úvod do funcionální analýzy
- ↳ Funkcionální analýza I
- ↳ Vybrané partie z funkcionální analýzy
- ↳ Náhodné procesy 2
- ↳ Matematická statistika 2
- ↳ Teorie pravděpodobnosti 2
- ↳ Matematická ekonomie
- ↳ Ostatní
- ↳ LS - Předměty MMIB a pokročilé Algebry
- ↳ Všeobecná diskuse
- ↳ Počítačová algebra
- ↳ Teorie čísel a RSA
- ↳ Aplikovaná kryptografie II
- ↳ Standardy v kryptografii
- ↳ Kryptoanalytické útoky
- ↳ Aplikace bezpečnostních mechanismů
- ↳ Kvantové a DNA počítače
- ↳ Faktorizace velkých čísel
- ↳ Algebraická geometrie v kladné charakteristice
- ↳ Výuka ZS 1. ročník
- ↳ MAA001 Matematická analýza 1a
- ↳ PRM044 Programování I
- ↳ MAA079 Proseminář z kalkulu 1a
- ↳ DMA005 Diskrétní matematika
- ↳ ALG001 Lineární algebra a geometrie I
- ↳ Ostatní
- ↳ Volitelné předměty
- ↳ Výuka ZS 2. ročník
- ↳ MIB
- ↳ Matematická analýza 2a
- ↳ Teorie míry a integrálu
- ↳ Numerika
- ↳ Algebra
- ↳ Předměty finanční matematiky
- ↳ Ostatní
- ↳ Výuka ZS 3. ročník
- ↳ Matematická statistika
- ↳ Teorie pravděpodobnosti
- ↳ Náhodné procesy
- ↳ Optimalizace
- ↳ Předměty numeriky
- ↳ Předměty finanční matematiky
- ↳ Komplexní analýza
- ↳ Funcionální analýza
- ↳ Ostatní
- ↳ ZS - předměty MMIB a pokročilé Algebry
- ↳ Úvod do algebry
- ↳ Složitost pro kryptografii
- ↳ Samoopravné kódy
- ↳ Teoretická kryptografie
- ↳ Aplikovaná kryptografie I
- ↳ Datové a procesní modely
- ↳ Eliptické křivky
- ↳ Členění kryptografických standardů
- ↳ Kryptografické protokoly
- ↳ Úvod do teorie grup
- ↳ Právní aspekty zabezpečení dat
- ↳ Komutativní okruhy
- Fyzika ZS
- ↳ Výuka ZS 1. ročník
- ↳ OFY067 Fyzika v experimentech I
- ↳ MAF027 Lineární algebra I
- ↳ OFY021 Fyzika I (mechanika a molekulová fyzika)
- ↳ OFY056 Programování pro fyziky
- ↳ MAF033 Matematická analýza I
- Oborový mix aktuální
- ↳ Anglický jazyk
- ↳ Tělesná výchova
- ↳ Granty GAUK
- Odkazy
- ↳ Wiki
- ↳ SKAS
- ↳ Spolek Matfyzák
- Matematika Archiv
- ↳ Výuka LS 2006/2007 3. ročník
- ↳ Předměty numeriky
- ↳ Úvod do funcionální analýzy
- ↳ Náhodné procesy 2
- ↳ Matematická statistika 2
- ↳ Teorie pravděpodobnosti 2
- ↳ Matematická ekonomie
- ↳ Výuka LS 2006/2007 2. ročník
- ↳ Pravděpodobnost a statistika
- ↳ Teorie Míry a integrálu II
- ↳ Angličtina
- ↳ Algebra II
- ↳ Matematická analýza 2b
- ↳ Ostatní
- ↳ Výuka LS 2006/2007 1. ročník
- ↳ Volitelné předměty
- ↳ Lineární algebra 2
- ↳ Programování 2
- ↳ Matematická analýza 1b
- Zrušené předměty
- ↳ SWI087 Principy počítačů
- ↳ SWI120 Principy počítačů a operačních systémů
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG029 Programování v C++
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG032 Objektově orientované programování
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ SWI097 Základy operačních systémů
- ↳ NDBI003 Organizace a zpracování dat II
- Roztřídit (resty)
- ↳ Výuka ZS 2005/06 2. ročník
- ↳ Předměty informační bezpečnosti
- ↳ Předměty finanční matematiky
- ↳ Teorie míry a integrálu
- ↳ Numerika
- ↳ Algebra
- ↳ Analýza/kalkulus
- ↳ Matematika obecně
- ↳ Výuka LS 2005/06 2.ročník
- ↳ Základy matematického modelování
- ↳ Finanční management
- ↳ Úvod do optimalizace
- ↳ Numerika
- ↳ Kalkulus
- ↳ Angličtina
- ↳ Diferenciální geometrie
- ↳ Pravděpodobnost a statistika
- ↳ Teorie míry a integrálu II
- ↳ Algebra II
- ↳ Analýza 2b