6
$\begingroup$

When proving that $ab = 0 \implies a = 0 \,\mbox{ or }\,b = 0$ for members $a$ and $b$ of a field, I used an argument like

  1. Suppose $ab = 0$ and $a \ne 0$ ... then $b = 0$.
  2. Now suppose $ab = 0$ and $b \ne 0$ ... then $a = 0$.
  3. Therefore, if $ab = 0$, then $a = 0$ or $b = 0$.

The general form of that argument would, as far as I can tell, be

$ (p \land \lnot q \to r) \land (p \land \lnot r \to q) \to (p \to q \lor r) $

Is that general form indeed a valid argument? How can I know for sure? (Is there a "for sure"?)

  • 0
    @Blue: Then it looks like what you're looking for is _proof systems_ in _formal logic_, which is concerned with syntactic manipulation to prove things. There are several different styles of doing this. In simple cases like this most of them are scarcely more enlightening than truth tables, but they become more interesting when you add rules for quantifiers. For a start take a look at [Hilbert system](http://en.wikipedia.org/wiki/Hilbert_system), [natural deduction](http://en.wikipedia.org/wiki/Natural_deduction), and [Sequent calculus](http://en.wikipedia.org/wiki/Sequent_calculus) on WP.2012-09-04

8 Answers 8

5

There is a brute force method to check whether a logical formula like the one you indicate holds. Namely, make a truth table: http://en.wikipedia.org/wiki/Truth_table. In other words, consider all $8$ possibilities of $p,q,r\in\lbrace T, F\rbrace$.

  • 0
    You may be interested in http://en.wikipedia.org/wiki/Rules_of_inference2012-09-05
4

A simpler approach is to argue that if $a\ne 0$, then $a$ has a multiplicative inverse, and $0_F=a^{-1}0_F=a^{-1}(ab)=(a^{-1}a)b=1_Fb=b\;.$ (I’m assuming that you’ve already proved that $a0_F=0_F$ for every $a\in F$.) The form of this argument is $(p\land\lnot q\to r)\to(p\to q\lor r)\;,$ without the second conjunct on the lefthand side. To check that it’s valid, just look at its truth table:

$\begin{array}{c|c} p&q&r&p\land\lnot q\to r&p\to q\lor r&(p\land\lnot q\to r)\to(p\to q\lor r)\\ \hline T&T&T&T&T&T\\ T&T&F&T&T&T\\ T&F&T&T&T&T\\ T&F&F&F&F&T\\ F&T&T&T&T&T\\ F&T&F&T&T&T\\ F&F&T&T&T&T\\ F&F&F&T&T&T \end{array}$

In fact, you can see that more is true:

$(p\land\lnot q\to r)\leftrightarrow(p\to q\lor r)\;.$

2

Hint $\ $ Your first step suffices: $\rm\: p\to q\lor r\, \equiv\, \lnot p\lor q\lor r \,\equiv\, \lnot (p\land \lnot q)\lor r\,\equiv\, p\land \lnot q\to r $

1

Yes, it is valid. You could use a truth table.

Note that $p \land \lnot q \to r$ is equivalent to $\lnot (p \land \lnot q \land \lnot r)$, and thus to $\lnot(p \land \lnot (q \lor r))$, which is equivalent to $p \to (q \lor r)$. Thus $(p \land \lnot q \to r) \to (p \to (q \lor r))$, so $(p \land \lnot q \to r) \land (p \land \lnot r \to q) \to (p \land \lnot q \to r) \to (p \to (q \lor r))$

0

This is valid, but much more complicated than you need. You already took care of the only part that takes any work in your step 1.

Suppose $ab = 0$ and $a \neq 0$ ... then $b = 0$.

Otherwise, if it is not true that $a \neq 0$, then $a = 0$. So, in either case ($a \neq 0$ or $a = 0$), at least one of $a$ and $b$ is 0. I might write out the argument starting by saying "If $a = 0$, then we are finished. So, assume $a \neq 0$." Now, do the steps to get $b = 0$.

Or, another way to think about why you don't need your Step 2, by commutativity and relabeling, it is exactly the same as your Step 1.

0

What really needs to be proved is that a field does not have zero divisors. That follows from field, by definition, containing the inverses of all of its elements other than 0. I understand that you are asking about logic, but a proof about algebra has to stand on algebra.

0

We can easily prove that the formula is a tautology. Let's replace the inner implications using the equivalence $a\rightarrow b \equiv \lnot a \lor b$. Then we get $ (\lnot(p\land\lnot q)\rightarrow p)\land(\lnot(p\land\lnot r)\rightarrow q)\rightarrow(\lnot p\lor q\lor r) $ and after applying De-Morgan rules $(\lnot p \lor q \lor r)\land(\lnot p\lor r\lor q)\rightarrow (\lnot p\lor q\lor r)$ Now we see that both the antecedents and the consequent are the same. So since $(a\land a)\rightarrow a$ is equivalent to $a\rightarrow a$ and it's true for any $a$, the original formula is also true.

0

The principle you want is valid. Here is a natural deduction / sequent calculus proof of $(p \land \lnot q) \to r \vdash p \to (q \lor r)$ in classical logic.

  1. We invoke the law of excluded middle: $\vdash q \lor \lnot q$

  2. By conjunction introduction and modus ponens, $(p \land \lnot q) \to r, p, \lnot q \dashv r$ and by disjunction introduction, $(p \land \lnot q) \to r, p, \lnot q \vdash q \lor r$

  3. By identity and disjunction introduction, $(p \land \lnot q) \to r, p, q \vdash q \lor r$

  4. By disjunction elimination, $(p \land \lnot q) \to r, p \vdash q \lor r$ and by conditional proof, $(p \land \lnot q) \to r \vdash p \to (q \lor r)$ as required.

Amusingly, the converse $p \to (q \lor r) \vdash (p \land \lnot q) \to r$ is true even in intuitionistic logic. Indeed:

  1. By conjunction elimination and modus ponens, $p \to (q \lor r), p \land \lnot q \vdash q \lor r$

  2. By conjunction elimination and identity, $p \to (q \lor r), p \land \lnot q \vdash \lnot q$ so by modus ponens, $p \to (q \lor r), p \land \lnot q, q \vdash \bot$ but ex falso quodlibet, so: $p \to (q \lor r), p \land \lnot q, q \vdash r$

  3. By identity, $p \to (q \lor r), p \land \lnot q, r \vdash r$

  4. By disjunction elimination, $p \to (q \lor r), p \land \lnot q \vdash r$ whence, by conditional proof, $p \to (q \lor r) \vdash (p \land \lnot q) \to r$ as claimed.