(3) Индуктивное замыкание: никаких иных формул нет.
Таким образом, в базисе индукции здесь определяются некоторые стартовые
формулы, с которых начинается построение множества всех формул, а в индуктивном
предположении указываются некоторые правила порождения (отрицание, умножение,
сложение, следование и равенство) из уже построенных формул новых формул. Так,
многократно обращаясь на множество сначала стартовых, а затем все новых формул,
будет прирастать до бесконечности множество формул языка исчисления
высказываний. Здесь мы имеем дело с использованием схемы математической
индукции по отношению к формулам, а не числам. Условие (3) индуктивного
замыкания требует, чтобы среди формул были только такие выражения, которые
можно вывести из первых двух пунктов. В противном случае, если бы пункта (3) не
существовало, то мы бы лишь утверждали, что любое выражение, вытекающее из
пунктов (1) и (2), есть формула, но не наоборот, т.е. могло бы оказаться и так, что не
всякая формула была бы выражением, построенным по правилам (1) и (2), что само по
себе не противоречит этим пунктам.
Пусть, например, у нас в алфавите всего две переменных p и q, и нет констант.
Тогда стартовыми формулами будут всего две формулы: p, q. Затем, согласно
индуктивному предположению, мы можем образовать следующие новые формулы:
(p),(q), ((p)(p)), ((q)(q)), ((p)(q)), ((q)(p)), ((p)+(p)), ((q)+(q)), ((p)+(q)), ((q)+(p)),
((p)(p)), ((q)(q)), ((p)(q)), ((q)(p)), ((p)(p)), ((q) (q)), ((p)(q)), ((q)(p)). Теперь
мы можем прибавить эти формулы к формулам p и q, и вновь применить уже к этому
расширенному множеству все возможные логические операции во всех возможных
комбинациях. Здесь, например, появятся формулы вида (((p))(q)), (((p)(q))+
((q)(q))), и т.д. Поскольку количество всех скобок начинает в этом случае резко
возрастать, то обычно договариваются о сокращении ряда скобок. Например, пишут р
вместо (р), или pq вместо ((p)(q)).
В формальном языке обычно можно проверить только по внешней форме, является
ли та или иная последовательность букв алфавита этого языка его определенным
выражением, или нет. Например, чтобы проверить, является ли формулой языка
исчисления высказываний последовательность букв (p(q+r)) (с учетом сокращений
скобок), мы должны начать проверку с самых элементарных формул, входящих в это
выражение, постепенно поднимаясь все выше, пока не дойдем до всего выражения в
целом. Здесь:
1. Переменные p, q, r являются формулами по базису индукции.