Доказательство свойств формул по индукции

Представим, что про определенное свойство формул известно следующее:

• каждый атом обладает этим свойством,
• для любой формулы F если F обладает этим свойством, то также обладает и ¬F,
• для любых формул F, G и любой бинарной связки Д: если F и G обладает этим свойством, то также обладает и (F Д G).

Тогда множество формул с данным свойством замкнуто относительно правил построения, и мы по определению формулы можем заключить, что это свойство выполняется для всех формул. Про доказательства такого типа говорят ``по структурной индукции''.^*

2.5 Число левых скобок в формуле равно числу правых.

Определение 9 (Префикс). Префикс строки a₁···a_n – это строка вида a₁···a_m, где 0 Ј m Ј n.

2.6 В любом префиксе формулы число левых скобок больше или равно числу правых скобок. см. Указания