Правильная формула

Question

Докажите, что любое выражение (для логики высказываний) с большим количеством левых скобок, чем правых, не является правильно сформированной формулой.

Мои мысли: всякий раз, когда в проблеме говорится «любое выражение», я очень подозреваю, как можно доказать это утверждение. Было бы очень приятно узнать ваши идеи по доказательству этой задачи.

Примечание. Хорошо сформированные формулы логики предикатов 1) Атомарные формулы - это wffs. 2) Если α и β являются wffs, то также (¬α), (α ∧ β), (α ∨ β) и (α → β). 3) Если x - переменная, а α - wff, то (∀x) α и (∃x) α - wffs.

Answer 1

Обратите внимание, что противоположность утверждения, которое мы хотим доказать, такова:

В правильно сформированной формуле левых скобок не больше, чем правых.

Определение правильно построенных формул имеет рекурсивную структуру, которая позволяет использовать индуктивный подход к таким доказательствам. В самом деле, мы докажем немного более сильный результат, что количество левых скобок равно количеству правых скобок в любой правильно построенной формуле.

Базисный шаг в нашей индукции следует тому, как рекурсивно определяются wff s, начиная с "атомарных формул":

1. Атомарные формулы - это wffs.

В логике высказываний атомарные формулы - это пропозициональные переменные, обычно представленные буквами, но технически нам нужен неисчерпаемый запас, поэтому формально логический язык будет иметь бесконечно много доступных пропозициональных переменных.

Однако суть любого языка используются в том , что пропозициональные переменные не содержат ни одного скобок, поэтому нулевые левые скобок равно количество нулевых правых скобок. И это устанавливает базовый шаг.

Теперь о шаге индукции. Логика высказываний дает нам эти операции для преобразования более простых формул в более сложные:

1. Если $α$ и $β$ wffs, значит, тоже $(¬α)$, $(α ∧ β)$, $(α ∨ β)$ и $(α → β)$.

Гипотеза индукции состоит в том, что отдельно wffs $\alpha$ и $\beta$у каждого из них одинаковое количество левых и правых скобок. Поскольку каждое из «производственных правил», показанных в пункте (2), вводит ровно одну левую круглую скобку и одну правую скобку, новые правильно сформированные формулы, генерируемые этими правилами, также будут иметь равное количество левых и правых скобок.

На этом этап индукции завершается, и мы показываем, что у wffs всегда одинаковое количество левых и правых скобок.