整形式
右括弧よりも左括弧が多い式（命題論理の場合）は、論理式ではないことを証明します。
私の考え：問題が「あらゆる表現」を述べているときはいつでも、私はこの主張をどのように証明することができるかについて非常に疑わしくなります。このタスクの証明に関するあなたのアイデアを知っていただければ幸いです。
注：述語論理の論理式1）原子論理式はwffsです。2）αとβがwffsの場合、（¬α）、（α∧β）、（α∨β）、（α→β）も同様です。3）xが変数で、αがwffの場合、（∀x）αと（∃x）αはwffsです。
回答
私たちが証明したい声明の対偶は次のとおりであることに注意してください：
論理式には、右括弧よりも左括弧の数が多くありません。
論理式の定義は再帰的な構造を持っており、そのような証明への帰納的アプローチに役立ちます。実際、左括弧の数が任意の論理式の右括弧の数に等しいというわずかに強い結果を証明します。
誘導の基本ステップは、「原子論理式」で始まるwffの再帰的定義方法に従います。
- 原子論理式はwffsです。
命題論理では、原子論理式は命題変数であり、通常は文字で表されますが、技術的には無尽蔵の供給が必要なので、正式には論理言語では無限に多くの命題変数を使用できます。
ただし、使用される言語の要点は、命題変数に括弧が含まれていないことです。したがって、左括弧がゼロの場合は、右括弧がゼロの数に等しくなります。そして、それは基本的なステップを確立します。
さて、帰納法のステップです。命題論理は、より単純な式をより複雑な式に構築するためのこれらの操作を提供します。
- 場合 $α$ そして $β$ wffsです、そしてそうです $(¬α)$、 $(α ∧ β)$、 $(α ∨ β)$ そして $(α → β)$。
帰納法の仮説は、wffsを個別に $\alpha$ そして $\beta$それぞれに同数の左括弧と右括弧があります。（2）に示す各「生成規則」では、左括弧と右括弧が1つずつだけ導入されるため、これらの規則によって生成される新しい論理式にも、左括弧と右括弧の数が等しくなります。
これで帰納法のステップが完了し、wffsには常に右括弧と同じ数の左括弧があることがわかります。