2
$\begingroup$

I'll define my terminology via the following BNF grammar for implicational logical expressions:

<clause> ::= "(" <premise> <conclusion> ")"
<conclusion> ::= any variable
<premise> ::= (<clause> "$\rightarrow$")*

(In other words, the premise of a clause is any number of sub-clauses, separated from themselves and from the last variable of the clause by the right-associative implication connective, "$\rightarrow$".)

Example: $(((p \rightarrow q) \rightarrow r) \rightarrow (r \rightarrow p) \rightarrow (s) \rightarrow p)$ is a clause with premise clauses $((p \rightarrow q) \rightarrow r)$, $(r \rightarrow p)$, and $(s)$, and a conclusion of $p$.

I wrote a program to enumerate the classical implicational propositional tautologies, and noticed an interesting pattern that is true for (at least) the first 120,957,915 tautologies (i.e. all tautologies having up to 19 characters when converted to polish notation).

The pattern is as follows: every tautology's conclusion is the same variable as the conclusion of at least one of its premise clauses.

Does this pattern extend to every tautology in existence, and is there a proof of it?

$\endgroup$
  • $\begingroup$ Does "premise clause" mean direct premises or does a premise of a premise, etc., count? For example, if you had $\bot$, then $((A\to\bot)\to\bot)\to A$ would be a counterexample if we were considering direct premises but not if we counted the (trivial) conclusion of a premise of a premise of premise. $\endgroup$ – Derek Elkins May 4 at 3:49
  • 1
    $\begingroup$ @DerekElkins a premise of a premise does not count. Also, the falsum operand "$\bot$" is not allowed by my grammar, only variables and the "$\rightarrow$" connective. $\endgroup$ – Hans Brende May 4 at 3:55
3
$\begingroup$

Yes, and here's the proof: Suppose you have a clause with conclusion $p$, but $p$ is not the conclusion of any of its premises. Then if $p$ is false but every other propositional variable is true, we have that each premise of the clause is true, while the conclusion is false. So the clause is false under this valuation of the propositional variables, and hence the clause is not a tautology.

$\endgroup$
  • $\begingroup$ As my comment indicated, a key thing here is that there are no contradictions in the implicational fragment of classical propositional logic because everything is either a proposition variable, which is not a contradiction, or an implication whose conclusion is a proposition variable, and when it is assigned true, the whole implication will be true regardless of its premises. $\endgroup$ – Derek Elkins May 4 at 4:51
  • $\begingroup$ I think your proof suggests that for an implication with any connective whatsoever, if the variable of the 'conclusion' is not in any of the 'premises', then two of the premises must necessarily contradict each other for a given valuation of the variables. Otherwise, the premises could all be true, and the conclusion could be false. $\endgroup$ – Doug Spoonwood May 5 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.