Доказательство свойств формул по индукции
Представим, что про определенное свойство формул известно следующее:
- каждый атом обладает этим свойством,
- для любой формулы F если F обладает этим свойством, то также обладает и ¬F,
- для любых формул F, G и любой бинарной связки Д: если F и G обладает этим свойством, то также обладает и (F Д G).
Тогда множество формул с данным свойством замкнуто относительно правил построения, и мы по определению формулы можем заключить, что это свойство выполняется для всех формул. Про доказательства такого типа говорят ``по структурной индукции''.*
2.5 Число левых скобок в формуле равно числу правых.
Определение 9 (Префикс). Префикс строки a1···an – это строка вида a1···am, где 0 Ј m Ј n.
2.6 В любом префиксе формулы число левых скобок больше или равно числу правых скобок. см. Указания
Назад