Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose a statement form $\varphi$ always has value T or U. Show $\varphi$ is a classical tautology.

share|cite|improve this question
This question is quite badly formulated. What is T? What is U? Do you mean first-order or just propositional? – boumol Feb 10 '11 at 0:34
See – JDH Feb 10 '11 at 0:38
Did you write out the truth table? – Doug Spoonwood Jun 19 '13 at 4:59

Suppose that a statement $\varphi$ of propositional logic (using only $\wedge$, $\vee$ and $\to$) is not a propositional tautology in classical logic. It follows that some row of the truth table for $\varphi$ has value $F$.

Now, consider the truth table of $\varphi$ in Łukasiewicz three-valued logic, which is called Kleene logic on the Wikipedia page. The key observation is that Łukasiewicz three-valued logic agrees with classical logic on classical logic input. In other words, if all the propositional variables of $\varphi$ are given classical T/F values, then the truth value of $\varphi$ will agree with the classical logic value. Thus, since $\varphi$ had a classical row with value $F$, the very same row will have value F in the Łukasiewicz truth table of $\varphi$, contrary to the assumption that $\varphi$ had only values T or U.

share|cite|improve this answer
The Wikipedia page actually has the correct table for Lukasiewicz three-valued logic. – Doug Spoonwood Jun 19 '13 at 4:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.