2

Let each member of $A$, $B$, ... $Z$ be a proposition sentence. If A and B are proposition sentences then $\neg$ A, (A$\land$B), (A$\lor$B), (A$\to$B) and (A$\iff$B) are proposition sentences. Also propositon symbols $p_0, p_1, p_2 \ldots$ are propositon sentences.

Let $K(A)$ be the number of connectives belonging to $\{\land, \lor, \to, \iff\ \lnot\}$ in A, and $N(A)$ the number of negations in $A$.

Now the number of brackets in $A$ is $2(K(A)-N(A)). $ How could I prove this with induction over natural numbers $n$ and not with induction over structure? Any hints to guide me on right track would be greatly appreciated!

Doug Spoonwood
  • 11,211
Eetu Halme
  • 55
  • @Doug Doesn't the negation belong to the connectives counted in $K(A)$? For example $\leg \leg A $is a proposition sentence and the number of brackets according to the formula would be 2(0 - 2) = -4 which is clearly false. – Eetu Halme Sep 13 '16 at 19:40
  • Counting brackets. – Eetu Halme Sep 13 '16 at 19:45
  • It's from lecturers own assigments. Maybe I should edit it more clearly in the question but we were given that $2(K(A)-N(A))$ where $K(A)$ is the number of connectives and $N(A)$ is the number of negations, is the number of brackets in A. We should find a some statement which we can prove with induction over natural numbers that would prove that $2(K(A) -N(A)$ gives the number of brackets in $A$ – Eetu Halme Sep 13 '16 at 19:53
  • Bracket is '(' or ')' so the total amount of both is the number of brackets in $A$ Our definiton was that is A is a proposition sentence, so is $\neg A$ so negation doesn't add brackets at all – Eetu Halme Sep 13 '16 at 20:03
  • Sorry about that. I do think that $\lnot$ belongs in the connectives for K(A) on second thought. – Doug Spoonwood Sep 13 '16 at 20:06

0 Answers0