Název: Výroková logika a algebra
Překlad názvu: Výroková logika a algebra
Autoři: Polach, František ; Krajíček, Jan (vedoucí práce) ; Pudlák, Pavel (oponent)
Typ dokumentu: Diplomové práce
Rok: 2008
Jazyk: eng
Abstrakt: Algebraic proof systems of which the most important are the polynomial calculus and the Nullstellensatz proof system are proof systems that use algebraic means for proving propositional tautologies - they are based on polynomial identities over (commutative) rings. Razborov [9] have proved a non-trivial lower bound on degree for polynomia calculus proofs of the tautologies (a set of polynomials) that express the pigeonhole principle over any field. This work gathers present important results for algebraic proof systems and generalizes the Razborov's construction used in his proof of the lower bound to another set of polynomials. We explicitly describe the basis of the vector space of polynomials that are derivable by a small degree polynomial calculus proof from the tautologies that express a variant of the pigeonhole principle (that generalizes the principle for multifunctions).

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/17708

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-294438


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce