Zkonstruovat nový důkazový systém pro výrokovou logiku, který by byl popsán kombinatoricky či algebraicky a který by byl alespoň tak silný, jako obvyklý výrokový počet.
Seznam odborné literatury
S.Cook a R.Reckhow, The relative efficiency of propositional proof systems, J. of Symbolic Logic, 44(1), str.36-50, (1979).
J.Krajíček: Bounded arithmetic, propositional logic, and complexity theory, Cambridge U. Press, (1995).
Předběžná náplň práce
Obecný pojem výrokového důkazového systému (definován Cookem a Reckhowem) zobecňuje obvykle výrokové počty. Málo z těchto potenciálně mnohem silnějších systému (ve smyslu simulace) má ale explicitní kombinatorický či algebraický popis. Úkolem práce je nějaký takový nový systém najít.
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. However, only few of these possibly much stronger systems (in terms of a simulation) allows for an explicit combinatorial or algebraic description. The goal of the project is to describe a new system having these properties.
- zadáno a potvrzeno stud. odd.