How to do logical proofs with counter example

Question

I am trying to give a prove if this is a tautology, or give a counter example if it is not a tautology. $$ p ⇒ ¬q ≡ (q ≢ r) ⇒ ¬p ≡ p ⇒ ¬r $$ I tried to place the parentheses like this $$(((p⇒(¬q))≡((q≢r)⇒(¬p)))≡(p⇒(¬r))$$ and tried to reduce the left side to the right side but failed. Then I realized if it wasn't a tautology I could just give a counter example but then again I have no idea how to do that. I am currently stuck and need a set of fresh eyes.

Answer 1

I am trying to give a prove if this is a tautology, or give a counter example if it is not a tautology. $$ p ⇒ ¬q ≡ (q ≢ r) ⇒ ¬p ≡ p ⇒ ¬r $$ I tried to place the parentheses like this $$(((p⇒(¬q))≡((q≢r)⇒(¬p)))≡(p⇒(¬r))$$

OK, your 'tried' makes me a little nervous. Are you sure the parentheses go there?

First of all, you have one more '$($' than '$)$', so I assume you meant:

$$((p⇒(¬q))≡((q≢r)⇒(¬p)))≡(p⇒(¬r))$$

And second: this is where the parentheses would go if $\Rightarrow$ has precedence over $\equiv$ ... I would make sure that that is compatible with what your textbook/teacher says.

Anyway, let's work what you cam up with (but without the extra '$($' ).

OK, so for a counterexample, you just have to find a possible assignment of truth-values to the variables so that the claim evaluates to false.

How do you find such a counterexample? Well, you could of course just try some assignments and see what happens. However, there are some more systematic ways to try and find such counterexamples, such as semantic tableaux. But, for beginners, probably your best best is to do a truth-table, which simply systematically exhausts all possible truth-assignments. So, if there is a counterexample, you are bound to find it.

The other good news is that if you cannot find such an assignment with a truth-table, then you know for sure there is no such counterexample ... and hence this statement would be a tautology.

Well, let's see what happens:

\begin{array}{ccc|cccccccccc} p&q&r&((p& \to & (\neg q))& \equiv& ((q \not \equiv r) & \to & (\neg p)))&\equiv &(p & \to & (\neg r))\\ \hline T&T&T&T&F&F&F&F&T&F&\color{red}T&T&F&F\\ T&T&F&T&F&F&T&T&F&F&\color{red}T&T&T&T\\ T&F&T&T&T&T&F&T&F&F&\color{red}T&T&F&F\\ T&F&F&T&T&T&T&F&T&F&\color{red}T&T&T&T\\ F&T&T&F&T&F&T&F&T&T&\color{red}T&F&T&F\\ F&T&F&F&T&F&T&T&T&T&\color{red}T&F&T&T\\ F&F&T&F&T&T&T&T&T&T&\color{red}T&F&T&F\\ F&F&F&F&T&T&T&F&T&T&\color{red}T&F&T&T\\ \end{array}

OK, so it is a tautology!

(P.s. I am using $\to$ instead of $\Rightarrow$, since $\Rightarrow$ is more typically used for logical implication, rather than material implication)

Indeed, the great advantage of truth-tables is that you are bound to find an answer either way. On the other hand, when you tried to reduce one side to the other, and weren't able to do so ... then that really doesn't mean much: maybe you couldn't find the reduction because the statement was not a tautology ... but another possibility is that the statement really is a tautology, but you were just unable to find the steps to show this. And apparently it's the latter that happened. Not surprisingly, really, given the complexity of the statement: with all those $\equiv$'s, you get a really long statement when converting to $\land$'s, $\lor$'s, and $\neg$'s, and it's easy to make a mistake or just not see the right step to continue.

Still, here is something you can do to convince yourself you are dealing with a tautology. First, notice that $\equiv$ is associative, meaning that $p \equiv (q \equiv r) = (p \equiv q) \equiv r$. Because of that, you can actually write $p \equiv q \equiv r$. So, your statement can be written as:

$$(p \to (\neg q)) \equiv ((q \not \equiv r) \to (\neg p)) \equiv (p \to (\neg r))$$

Now, applying Contraposition on the middle term gives us:

$$(p \to (\neg q)) \equiv (p \to (q \equiv r)) \equiv (p \to (\neg r))$$

OK, so now we see we have three conditionals, with $p$ as the anteceddent for each of them. So, we consider two cases:

$p$ is false. Well, then all conditionals will be True, and hence you get $T \equiv T \equiv T$, which is $T$

$p$ is True. Then the antecedents are all satisfied, and we can reduce the statement to:

$$\neg q \equiv (q \equiv r) \equiv \neg r$$

Now, the $\equiv$ is not only associative, but also commutative, and so this statement is equivalent to:

$$(q \equiv r) \equiv \neg q \equiv \neg r$$

adding parentheses back in:

$$(q \equiv r) \equiv (\neg q \equiv \neg r)$$

and since $\neg q \equiv \neg r = q \equiv r$ (I sometimes call this 'Biconditional Contraposition'), we get:

$$(q \equiv r) \equiv (q \equiv r)$$

which is clearly always True as well.

Answer 2

Well, the first case has nothing to do with $r$. So maybe we can get a case were the first is true of false whereas the second will be true or false depending on where $r$ is true or false.

$p \implies \lnot q$ is false if $p$ and $q$ and true all other cases.

If $p$ and $q$ then $(q\not \equiv r)\implies \not p$ will be true if $(q \equiv r)$ but false if $q\not \equiv r$. If $p$ is false then $(q\not \equiv r)\implies \not p$ will be true, If $p$ is true but $q$ is false then $(q\not \equiv r)\implies \not p$ will be true if $(q\equiv r)$ but false if $q\not \equiv r$

So $p,q,r$ all true; and $p,r $ true while q$ false will be counter examples.

we can do the same for the last statement which has no reference to $q$

Answer 3

There are several approaches one could take to finding a counter example, but the essence of such a proof is to find one example, or "case," in which the statement you're disproving is false.

By definition, a tautology is a statement that is always true. So, in order to disprove the statement above, you merely need to find one assignment of truth values for $p$ and $q$ that renders the statement false - thereby showing that it cannot always be true. Since you are only dealing with two component propositions, I suggest constructing a truth table to do this.