Сибирский Математический Журнал

Номера
2019:	1
2018:	1	2	3	4	5	6
2017:	1	2	3	4	5	6
2016:	1	2	3	4	5	6
2015:	1	2	3	4	5	6
2014:	1	2	3	4	5	6
2013:	1	2	3	4	5	6
2012:	1	2	3	4	5	6
2011:	1	2	3	4	5	6
2010:	1	2	3	4	5	6
2009:	1	2	3	4	5	6
2008:	1	2	3	4	5	6
2007:	1	2	3	4	5	6
2006:	1	2	3	4	5	6
2005:	1	2	3	4	5	6
2004:	1	2	3	4	5	6
2003:	1	2	3	4	5	6
2002:	1	2	3	4	5	6
2001:	1	2	3	4	5	6
2000:	1	2	3	4	5	6
1999:	1	2	3	4	5	6
1998:	1	2	3	4	5	6
1997:	1	2	3	4	5	6
1996:	1	2	3	4	5	6
1995:	1	2	3	4	5	6
1994:	1	2	3	4	5	6
1993:	1	2	3	4	5	6

СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ

АННОТАЦИИ

Алексанян С. Р., Чубарян А. А. О полиномиальных ограничениях сложностей выводов в системах Фреге // Том 50 (2009), Номер 2, стр. 243–249

Ранее одним из авторов
было введено понятие определяющего множества переменных пропозициональной
формулы, позволившее выделить множество {\it трудноопределяемых} тавтологий,
сложности выводов которых в ряде систем доказательств классического исчисления
высказываний (секвенциальной системе без правила сечения, системе резолюций,
системе, основанной на методе расщепления, системе неравенств <>,
ограниченных системах Фреге) оцениваются снизу экспонентой от длины выводимой
формулы. В настоящей работе доказывается, что для получения суперполиномиальной
нижней оценки шагов (длины) выводов в системах Фреге наличия свойства
трудноопределяемости недостаточно: приводится пример последовательности
трудноопределяемых формул, имеющих полиномиально ограниченные сложности выводов
в любой системе Фреге.

СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ АННОТАЦИИ

СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ

АННОТАЦИИ