3
$\begingroup$

I am studying propositional logic and I am trying to solve some exercise related to the following definition:

Given two logical propositions $\alpha$ and $\beta$, we say that $\alpha$ is stronger than $\beta$ if and only if $(\alpha \implies \beta)$ is a tautology. Determine which of the two propositions is stronger in the following cases:

1) True, False

2) True, True

3) False, False

I am a bit confused with this problem. I've seen that for True we always assign the value $1$ and for False, the value $0$. So, (True $\implies$ False) has always value $0$ (actually, there is one possibility) and (False $\implies$ True) has always value $1$ (there is also one possibility). This means that (False $\implies$ True) is a tautology, so False is stronger than True.

I am not sure if what I've said above is correct and I am lost in 2) and 3), I would appreciate some help. Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ You're doing ok, just keep going. What is your question? $\endgroup$ – Andrej Bauer Aug 15 '16 at 11:26
6
$\begingroup$

The notion of strength of a proposition comes from its power to constrain the model. For instance the proposition $P1 : x = 2$ is stronger than $P2 : x \geq 2$ in Arithmetic. And in propositional notation this can be written as $P1 \Rightarrow P2 $.

The stronger the proposition the harder it usually is to prove. On the other hand, if proven it provides more corollaries.

For instance for a signature with 2 propositional symbols $P$ and $Q$ we have the following partial diagram for the Strength relation.

enter image description here

Now to your examples. $\textrm{False}$ happens to be an extreme case. It can never be satisfied. If you are using propositions to constrain your search space for an answer, then $\textrm{False}$ says: "Call off the search and start again". The other extreme is the proposition $\textrm{True}$. It is trivial. It gives absolutely no information on where to look for the answer.

Now we shall use this intuition to tackle your questions:

1) True, False

Since $\textrm{True}$ is a trivial constraint, you would not be able to derive anything non-trivial out of it, this certainly means that you would not be able to derive the extreme constraint $\textrm{False}$.

$\not\vdash \textrm{True} \Rightarrow \textrm{False}$

2) True, True

The propositions have exactly the same strength, they are equivalent

$\vdash \textrm{True} \Rightarrow \textrm{True}$

3) False, False

The propositions have exactly the same strength, they are equivalent

$\vdash \textrm{False} \Rightarrow \textrm{False}$

And an extra case

4) False, True

$\vdash \textrm{False} \Rightarrow \textrm{True}$

Note: there is an issue with saying that proposition $P$ is stronger than $Q$ if $P \Rightarrow Q$ is a tautology since intuitively the relation of being stronger is strict. It would better align with the intuition if we were to say that proposition $P$ is stronger than $Q$ or of equal strength if and only if $P\Rightarrow Q$.

$\endgroup$
  • 1
    $\begingroup$ I'd just add that False=>True - False is stronger than anything and True is weaker than anything. $\endgroup$ – Petr Pudlák Aug 15 '16 at 13:36

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.