I have this task to solve:

Find (if it exists) such a sentence formula α so that the following formulas are simultaneously tautologies of the propositional calculus: $$ (q \rightarrow \alpha) \leftrightarrow (q \rightarrow (p \wedge r))$$ and $$ (\alpha \rightarrow q) \leftrightarrow (\neg(p \vee r) \rightarrow q) $$

Generally I have idea to solve this task in use of table. So I created a table with 7 columns: $p$,$q$,$r$,$(p \wedge r)$, $(q \rightarrow (p \wedge r)$ $(q \rightarrow \alpha)$, $LS \leftrightarrow RS $ and 8 rows with each case. In last column I get these values: $\alpha$, $\neg \alpha$, $1$, $1$, $\neg \alpha$, $\neg \alpha$, $1$, $1$ So if we consider tautology, both $\alpha$ and $\neg \alpha$ should be $1$ so it can't be done. So $\alpha$ like that does not exists and I don't have to consider second potential tautology. Have I right? Eventually, there are other ways to solve tasks like that?

  • $\begingroup$ Have you compared the values of alpha with the values of other columns? Remember, you're looking for a statement or formula, not necessarily a truth value $\endgroup$ – David Diaz Dec 13 '18 at 20:27
  • $\begingroup$ It should be tautology so $LS \leftrightarrow RS $ must be true value. If I represent this by $\alpha$ it should be true too. The same thing with $\neg \alpha $ $\endgroup$ – user617243 Dec 13 '18 at 20:30
  • 1
    $\begingroup$ One could use the method of analytic tableaux. $\endgroup$ – Shaun Dec 13 '18 at 20:30
  • $\begingroup$ Ok, but my solution is good or not? Thanks for interesting link. $\endgroup$ – user617243 Dec 13 '18 at 20:34
  • $\begingroup$ @VirtualUser Your method of creating a truth-table is fine ... but your conclusion that it cannot be done is not. It can be done. Just see what value, if any, is forced on $\alpha$ to make the truth-values come out right in each row. And then just generate an expression for that. $\endgroup$ – Bram28 Dec 13 '18 at 20:35

You'll eventually get to a correct answer by working out a truth-table (and, as a general method, that is to be preferred over what I'm about to do below), but here is a more direct approach by careful inspection of the statements involved.

First, note that the first conditional holds True whenever $q$ is False, so nothing is required of $\alpha$ in the case where $q$ is False. So the only interesting case is where $q$ is True. And in that case, $\alpha$ needs to have the same truth-value as $p \land r$ in order for the biconditional to be True, i.e. just when $p$ and $r$ are both True.

Likewise, you can immediately see that the second biconditional is True whenever $q$ is True, so here the only interesting case is where $q$ is False, and in that case, the biconditional is True just when $\alpha$ has the same value as $\neg (p \lor r)$, i.e. when both $p$ and $r$ are False.

So, the only cases where $\alpha$ should be True are where $q$, $p$, and $r$ are all True, or when they are all False:

$$\alpha = (q \land p \land r) \lor (\neg q \land \neg p \land \neg r)$$

| cite | improve this answer | |
  • $\begingroup$ Thanks for your reply I think that I have understood this problem, it is interesting alternative for table. $\endgroup$ – user617243 Dec 13 '18 at 20:59
  • 1
    $\begingroup$ @VirtualUser Yes, the statements were 'nice' enough that I was able to derive it this way pretty quickly ... but the Truth-table method will be more general. $\endgroup$ – Bram28 Dec 13 '18 at 21:13

Your Answer

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