2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Специфические тавтологии логики второго порядка
Сообщение03.05.2016, 21:18 
Интересно, где можно найти тавтологии, характерные для логики предикатов второго порядка? Я пока нашёл только одну (на этом форуме). Эта формула имеет вид $\forall P ( \exists x P(x) \vee \overline{ \exists x P(x)})$.

 
 
 
 Re: Специфические тавтологии логики второго порядка
Сообщение03.05.2016, 21:29 
Подобных этой можно нагенерировать кучу. Берём тавтологию первого порядка, в которой случайно попались функциональные/предикатные символы: $\forall x\forall y.P(x,y)\to\forall x.P(x,x)$. Добавляем кванторы по ним, переосмыслив их как переменные: $\forall P(\forall x\forall y.P(x,y)\to\forall x.P(x,x))$. Тавтология второго порядка готова, приятного аппетита!

Но это только по поводу этой.

 
 
 
 Re: Специфические тавтологии логики второго порядка
Сообщение03.05.2016, 21:36 
arseniiv, спасибо.
Ну, значит, берём любую тавтологию логики предикатов первого порядка и навешиваем кванторы (любые?) по предикатным переменным?
А что-нибудь есть такое, где тавтологии первого порядка не участвуют?

 
 
 
 Re: Специфические тавтологии логики второго порядка
Сообщение03.05.2016, 21:42 
Определённо не скажу. Здесь я просто взял, что плохо лежало. :-)

kernel1983 в сообщении #1120601 писал(а):
Ну, значит, берём любую тавтологию логики предикатов первого порядка и навешиваем кванторы (любые?) по предикатным переменным?
Ага, до замыкания формулы. (И можно, конечно, навешивать кванторы по переменным, которые свободно не входят, но я подумал, что вам были интересны не эти случаи.)

 
 
 
 Re: Специфические тавтологии логики второго порядка
Сообщение03.05.2016, 21:59 
arseniiv в сообщении #1120604 писал(а):
И можно, конечно, навешивать кванторы по переменным, которые свободно не входят


А какой в этом смысл?

 
 
 
 Re: Специфические тавтологии логики второго порядка
Сообщение03.05.2016, 23:09 
Кроме того, что получится другая формула, никакого, вот именно.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group