Verifying logic without drawing truth tables

Question

Want to know is there a way to solve these sort of problems without drawing truth tables? I found that it's kinda time consuming drawing truth table for each question.

Help pls.

Check the images

Answer 1

You can use DeMorgan's laws:

• $p \vee q$ is equivalent to $\neg (\neg p \wedge \neg q)$
• $p \wedge q$ is equivalent to $\neg (\neg p \vee \neg q)$

Answer 2

You can check some of them easily in your head. In (a), for instance, $p\,\lor\sim q$ is certainly always true whenever $p$ is true, but $p\Rightarrow q$ is not: it’s false when $p$ is true and $q$ is false. Thus, the two expressions cannot be logically equivalent. Similarly, you should recognize the second implication in (e) as the contrapositive of the first, and you should know that these are logically equivalent.

The other three are easily dealt with algebraically. For instance,

$$p\land(\sim p\,\lor q)\equiv(p\,\land\sim p)\lor(p\land q)\equiv p\land q\;,$$

so the expressions in (b) are logically equivalent. (Here I used distributivity of $\land$ over $\lor$ and the fact that $p\,\land\sim p$ is always false.)

Part (d) is similar but even easier, and part (c) is also similar, though you may have to think a little after you expand the lefthand side to see whether it’s equivalent to $q$ or not.

For the second problem, note that you can instantly rule out (a) by verifying that it’s a tautology, while $\Omega$ definitely is not: $(p\land q)\Rightarrow(p\lor q)$ is clearly always true. It’s also easy to dispose of (b): it’s a disjunction of terms of the form $A\land B\land C$, where $A$ is $p$ or $\sim p$, $B$ is $q$ or $\sim q$, and $C$ is $r$ or $\sim r$. Each of these terms corresponds to one line in the truth table with proposition letters $p,q$, and $r$; specifically, they correspond to lines $1,3,5,6$, and $8$ of the truth table in the picture. The disjunction is true precisely when one of these terms is true, and so is $\Omega$: these are precisely the lines of the truth table in which $\Omega$ is true. Thus, $\Omega$ is logically equivalent to (b). Choice (c) is of the same type; can you see why it’s logically equivalent to $\sim\Omega$?

The last two alternatives in the second problem are messier, but you can easily dispose of both by ad hoc techniques. Notice that the expression in (d) is true when $p$ and $q$ are true and $r$ is false: the truth of $p$ makes the first three terms true, the truth of $q$ makes the fourth term true, and the falsity of $r$ makes the last term true. Is $\Omega$ true when $p$ and $q$ are true and $r$ is false? See if you can find a similarly quick way to dispose of (e).

Answer 3

You could write a computer program to solve these problems.

Also, to check if two formulas 'p' and 'q' are equivalent, you can check and see that both Cpq and Cqp (this is Polish notation) are tautologies. A formula is either a tautology or it's not. So, assume that Cpq is not a tautology. This means that there exists some valuation of the variables in 'p' and 'q' such that 'p' holds true and 'q' doesn't hold true. If the assumption that such a valuation exists leads to a contradiction, then Cpq holds as a tautology. Similarly, we can check and see if Cqp holds as a tautology. If they both do, then the formulas 'p' and 'q' qualify as logically equivalent.

For instance, suppose that we wanted to see if CCpqp and p are logically equivalent. Suppose that they're not. Then either CCCpqpp is false or CpCCpqp is false. Suppose that CCCpqpp is false. Then CCpqp is true and p is false. Thus, CCpqp = CC0q0, where 0 indicates falsity. But since C0x = 1, CC0q0 = C10 = 0. Thus, CCpqp is false. Since we have CCpqp as true above, we have a contradiction, and thus, CCCpqpp is true. Suppose that CpCCpqp is false. Then p = 1 and CCpqp = 0. So, CCpqp = CC1q1 = 0. But, Cx1 = 1, and thus CC1q1 = 1 = 0. Which is a contradiction. And thus, CpCCpqp. Therefore, CCCpqpp is true, or equivalently, ECCpqpp is a tautology.