Výroková logika a algebra

• Název práce v češtině: Výroková logika a algebra
• Název v anglickém jazyce: Propositional logic and algebra
• Akademický rok vypsání: 2006/2007
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: prof. RNDr. Jan Krajíček, DrSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 07.12.2006
• Datum zadání: 07.12.2006
• Datum a čas obhajoby: 10.09.2008 00:00
• Datum odevzdání elektronické podoby: 10.09.2008
• Datum odevzdání tištěné podoby: 10.09.2008
• Datum proběhlé obhajoby: 10.09.2008
• Oponenti: prof. RNDr. Pavel Pudlák, DrSc.

Zásady pro vypracování

Sestrojit důkazy některých známých tautologií v jednom z algebraických důkazových systémů pro výrokovou logiku.

Seznam odborné literatury

S.Buss, R.Impagliazzo, J.Krajicek, P.Pudlak, A.A.Razborov a J.Sgall, Proof complexity in algebraic systems and bounded depth Frege systems with modular counting, Computational Complexity, 6(3), str.256-298, (1996/97).

S.Cook a R.Reckhow, The relative efficiency of propositional proof systems, J. of Symbolic Logic, 44(1), str.36-50, (1979).

J.Krajicek: Bounded arithmetic, propositional logic, and complexity theory, Cambridge U. Press, (1995).

J.Krajicek, Dehn function and lengths of proofs, Int.J. of Algebra and Computation, 13(5), str.525-542, (2003).

Předběžná náplň práce

Obecný pojem výrokového důkazového systému (definován Cookem a Reckhowem) zobecňuje obvyklé výrokové počty. Některé z těchto systémů používají algebru (např. Nullstellensazt). Úkolem práce je sestrojit důkazy konkrétních tautologií v jednom z těchto systémů.

Předběžná náplň práce v anglickém jazyce

The general notion of a propositional proof system (defined by Cook and Reckhow) generalizes usual propositional calculi. Some of these systems are based on algebra (e.g. Nullstellensatz). The goal of the project is to construct proofs of particular tautologies in one of such systems.