5
$\begingroup$

Are there some techniques for checking whether a statement implies another without truth tables?

For example, I was asked whether $P\Longrightarrow P_{1}$ given the following statements:

$$P: [p \land (q \land r)]\lor \neg[p \lor (q \land r)],$$

$$P_{1}: [p \land (q \lor r)]\lor \neg[p\lor(q\lor r)].$$

What I did was to find the logical equivalences of the negations of $\neg[p \lor (q \land r)]$ and $\neg[p\lor(q\lor r)]$, then tested some values, with the negations done, it was slightly easier to see what was happening as I drew 0's and 1's under $p,q,r$. I find that for $p:0,q:1,r:0$, $P$ and $P_{1}$ does not have the same truth statement, so $P\nRightarrow P_{1}$, yet it was still a tedious process.

$\endgroup$
1
3
$\begingroup$

Yes. I always think of using truth tables as a last resort; sometimes it actually pays off because the effort spent constructing the truth table can be considerably less than that using logical deductions, but there is not much at all learned by proving something with a truth table--it's very mechanical.

When trying to prove an implication of the form $\Omega\to\Psi$ without using a truth table, your job is to show that, given $\Omega$, the implication $\Omega\to\Psi$ is a tautology. I will give you two examples of how to check whether or not a statement implies another without a truth table (the first will not be a tautology but the second will be).

Example 1: Given $p$, does $p\to(p\land q)$?

Solution. Notice the following: \begin{align} p\to(p\land q) &\equiv \neg p\lor(p\land q)\tag{since $r\to s\equiv \neg r\lor s$}\\[0.5em] &\equiv \underbrace{(\neg p\lor p)}_{\text{Always true}}\;\;\land\underbrace{(\neg p\lor q)}_{\substack{\text{True if $q$ is true}\\\text{False if $q$ is false}}}\tag{distributivity} \end{align} Hence, the implication $p\to(p\land q)$ is not a tautology since it will be false when $q$ is false.

Example 2: Given $p\land q$, does $(p\land q)\to p$?

Solution. Notice the following: \begin{align} (p\land q)\to p &\equiv \neg(p\land q)\lor p\tag{since $r\to s\equiv \neg r\lor s$}\\[0.5em] &\equiv (\neg p\lor\neg q)\lor p\tag{DeMorgan}\\[0.5em] &\equiv \underbrace{(\neg p\lor p)}_{\text{Always true}}\lor\neg q.\tag{associativity of $\lor$} \end{align} Since $\neg p\lor p$ is always true, we have that $(p\land q)\to p$ is a tautology, and we proved this without using a truth table.

$\endgroup$
1
$\begingroup$

Yes, there are plenty of other methods. In each of the following, I will provide an example of what a proof of the inference $p \lor q \to r, \neg r \vDash \neg p$ looks like.

  • arguing about interpretations: You assume that the premises are true under some interpretation (valuation function/structure), investigate what truth values the atoms must then take, and use this knowledge to conclude that this valuation will then also make the conclusion formula true. Or you prove by contradiction: assume that there is an interpretation that makes all the premises true but the conclusion false, then find a contradictory claim about truth assignment and conclude that such a counter interpretation can not exist. To show that an inference is not valid, you would show that there does exist such a counter valuation by giving a concrete example.
    Example:

    Assume that for some interpretation $v$, $v(p \lor q \to r) = 1$ and $v(\neg r) = 1$ but $v(\neg p) = 0$. Since $v(\neg p) = 0$, $v(p) = 1$. But then $v(p \lor q) = 1$. Since, by assumption, $v(\neg r) = 1$ and hence $v(r) = 0$, with $v(p \lor q) = 1$ and $v(r) = 0$ we have that $v(p \lor q \to r) = 0$. Contrdadiction to the assmption, hence such a $v$ can not exist, and the inference holds.

  • equivalence rewriting: Make use of basic laws of logic to transform the formulas into logically equivalent ones, which make it easier to see if truth is preserved under all interpretations -- see Daniel W. Farlow's answer.

  • tableaux aka truth trees: A formal proof system particularly useful to check the validity of formulas or inferences; this system can (though in the case of FOL not always) also tell when an inference is not valid. A nice feature about tableaus is that they give a straightforward way to extract counter models if an inference is not valid.
    enter image description here

  • natural deduction: A formal proof system in which one can prove that an inference holds (but not that it doesn't hold.) Natural deduction is interesting in that it is designed to closely resemble the way one would reason informally, and more than the other mechanical procedures (truth tables, tableaus, resolution) provides insights as to why, rather than just that, an inference holds.
    enter image description here

  • resolution: A formal proof system with the advantage that is relatively easy for computers to do.

enter image description here

All of these methods have the advantage that they also work for predicate logic, where truth tables don't exist.

$\endgroup$
10
  • $\begingroup$ Ha! Once again you did all the work for me. I was going to do this very list, with maybe DPLL added. I also would note that 'checking' sounds like 'deciding', and unless you do some further work to make it into one, Natural Deduction isn't really a decision procedure. $\endgroup$ – Bram28 Jul 23 '20 at 17:33
  • $\begingroup$ OMG! That's funny ... I was just about to add equivalences ... :) .. althpugh once again you'd need to do some work to make it into a full decision procedure ... but it can be done $\endgroup$ – Bram28 Jul 23 '20 at 17:34
  • $\begingroup$ @Bram28 What does DPLL stand for, could this be something I don't know about yet? Concerning your second remark, this is of course right, but where did I write about "checking" in the context of ND? $\endgroup$ – lemontree Jul 23 '20 at 17:37
  • $\begingroup$ I mean Davis-Putnam. And yes, I see you explicitly mention that ND does not demonstrate non-consequence .... $\endgroup$ – Bram28 Jul 23 '20 at 17:39
  • $\begingroup$ This actually is the first time hearing of DPLL for me, so feel free to add that as an answer; thanks for making me aware of its existence. $\endgroup$ – lemontree Jul 23 '20 at 18:02
0
$\begingroup$

Examining

$$P: [p \land (q \land r)]\lor \neg[p \lor (q \land r)]$$

$$P_{1}: [p \land (q \lor r)]\lor \neg[p\lor(q\lor r)]$$

we consider the case that p is FALSE:

$$P: [\text{FALSE} \land (q \land r)]\lor \neg[\text{FALSE} \lor (q \land r)]$$

$$P_{1}: [\text{FALSE} \land (q \lor r)]\lor \neg[\text{FALSE}\lor(q\lor r)]$$

which reduces to

$$P: \neg[(q \land r)]$$

$$P_{1}: \neg[(q\lor r)]$$

So to check $P\Longrightarrow P_{1}$ consider

$ \quad [(q \land r)] \lor \neg[(q\lor r)]$

When plugging in $q = \text{TRUE}$ and $r = \text{FALSE}$ we get a $\text{FALSE}$ statement.

So we are done. But if we arrived at a tautology after substituting $p = \text{FALSE}$ we would have to check the next case, $p = \text{TRUE}$.

$\endgroup$
-1
$\begingroup$

You could write a proof instead. Suppose $P$.

If $p\land q\land r$, then $p\land(q\lor r)$. Therefore $P_1$ tautologically.

Otherwise $\neg[p \lor (q \land r)]\Leftrightarrow \neg p \land \neg(q\land r)$. Then $p$ being true contradicts $P$, so $P\Rightarrow P_1$ in that case. In the case that $p$ is false, $P$ reduces to $\neg q \lor \neg r$ and $P_1$ reduces to $\neg q \land \neg r$. If $\neg q\not= \neg r$, then $P$ and not $P_1$, so $P\not\Rightarrow P_1$; otherwise $P$ and $P_1$ are both true or both false, so $P\Rightarrow P_1$.

Therefore $P\Rightarrow P_1$ exactly when $p$ is true or $q=r$, and $P\not\Rightarrow P_1$ exactly when $p$ is false and $q\not=r$.

$\endgroup$
1
  • $\begingroup$ Did I screw up here? $\endgroup$ – StevenClontz Mar 10 '15 at 19:03

Your Answer

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