How do we prove the following formula for all natural numbers $n$ in propositional calculus
$[(q_{1}\vee q_{2}...q_{n})\wedge((q_{1}\Longrightarrow r)\wedge(q_{2}\Longrightarrow r)...(q_{n}\Longrightarrow r))]\Longrightarrow r$
$\begingroup$
$\endgroup$
-
$\begingroup$ That is not a formula in propositional calculus. You can't prove this in any propositional calculus, since "..." is not part of any vocabulary for any propositional calculus, and thus your statement does not follow the formation rules for a well-formed formula. $\endgroup$ – Doug Spoonwood Mar 16 '15 at 13:26
-
1$\begingroup$ This is a meta theorem in propositional calculus and in the meta language, you are allowed to use induction. $\endgroup$ – Kostas Lamogiannis Mar 21 '15 at 15:23
$\begingroup$
$\endgroup$
Induction works here. If $n=1$, then you have $$ (q_1\wedge (q_1\rightarrow r))\rightarrow r. $$ This is an application of modus ponens. Then you can assume the truth of the statement for $n-1$ and prove the statement for $n$ by using or-elimination: You can split up $q_1\vee q_2\vee \cdots \vee q_n$ into $$ (q_1\vee\cdots \vee q_{n-1})\vee q_n. $$
EDIT: In answer to the question in the comments: You need both or-elimination and modus ponens to prove that. Use or-elimination and you have to prove two statements: $(q_1\wedge (q_1\to r))\to r$ and $(q_2\wedge (q_2\to r))\to r$. Each of these is proved using modus ponens.
answered Mar 15 '15 at 15:26
-
$\begingroup$ for $n=2$ we have the following formula: $[(q_{1}\vee q_{2})\wedge ((q_{1}\Longrightarrow r)\wedge(q_{2}\Longrightarrow r))]\Longrightarrow r$ How do we prove that? Surely we can not prove that by using only M. Ponens $\endgroup$ – Kostas Lamogiannis Mar 15 '15 at 15:35
-
$\begingroup$ @KostasLamogiannis I added the answer to your question above. $\endgroup$ – Joe Johnson 126 Mar 15 '15 at 15:51
