Finding logical equvilances only using v and ~ as connectives

63 Views Asked by At

Hello I'm currently looking to create logical equivalence of the following sentence using the logical connectives of "v" and "~"

The sentence is as follows: ∼(A ⊃ ∼B)

I'm not sure how I would go about this. My first step was to create a truth table but that did not seem to get me to find an answer. What steps would I use to solve similar problems such as these?

2

There are 2 best solutions below

0
On

Any logical expression, no matter how complex, and no matter what logical connectives is uses, can always be expressed with just $\lor$, and $\neg$.

Your generation of a truth-table is actually very helpful in order to find such an expression. For example, suppose we have an expression $\phi$ involving atomic propositions $P$, $Q$, and $R$, and whose truth-conditions are given by the following table:

\begin{array}{ccc|c} P&Q&R&\phi\\ \hline T&T&T&F\\ T&T&F&T\\ T&F&T&F\\ T&F&F&T\\ F&T&T&T\\ F&T&F&F\\ F&F&T&F\\ F&F&F&F\\ \end{array}

The truth table shows that $\phi$ is true in rows 2,4, and 5, and thus we generate the terms $P \land Q \land \neg R$, $P \land \neg Q \land \neg R$, and $\neg P \land Q \land R$ respectively. Disjuncting them gives us:

$$(P \land Q \land \neg R) \lor (P \land \neg Q \land \neg R) \lor (\neg P \land Q \land R) \tag{*}$$

A second's thought should tell you that this expression does capture $\phi$

OK, but the expression still uses $\land$'s, and w want just $\lor$'s and $\neg$'s. How to do that?

Easy.

Remember by DeMorgan that:

$$P \land Q \Leftrightarrow \neg (\neg P \lor \neg Q)$$

Using this, we can take the expression in $(*)$, and replace all $\land$'s with $\lor$'s:

$$\neg (\neg P \lor \neg Q \lor \neg \neg R) \lor \neg (\neg P \lor \neg \neg Q \lor \neg \neg R) \lor \neg (\neg \neg P \lor \neg Q \lor \neg R)$$

The resulting expression may not be the most efficient way to capture the original expression, but it does only use $\lor$'s and $\neg$'s.

Can you do the same for your expression? It invlves only two atomic propositions, $A$, and $B$, and so it should be a little easier. Good luck!

0
On

Recall that $X\supset Y$ is equivalent to ${\sim} X\lor Y$ by the rule of Implication Equivalence.