# A confusion about truth table of logical implication

1. Jun 3, 2009

### kof9595995

In logical implication (p implies q), if p is false, then no matter q is true or false, p implies q is true. But I think the negative of "p implies q" is "p implies not q", if so, if p is false, both "p implies q" and its negative are true, which is not possible. So is the negative of "p implies q" "p does not imply q"?

2. Jun 4, 2009

### SW VandeCarr

I think the reason no one has responded to your post is that no one can follow your reasoning or the meaning of your question. I certainly can't. What you say in the first sentence is correct. If P(F) and Q(T) then P-->Q (T) and if P(F) and Q(F) then P-->Q (T). Are you trying to argue that this is incorrect?

3. Jun 4, 2009

### kof9595995

Sorry, my words seemed to be messed up, let me state it this way:
1.P(F)=>Q(T) is true
$$\neg$$Q is false
and
2.P(F)=>$$\neg$$Q(F) is also true.

But I think 2 is the negation of 1, how can they both be true?

Last edited: Jun 4, 2009
4. Jun 4, 2009

### CRGreathouse

The negation of P → Q is
¬(P → Q), which can also be written
¬(¬P ∨ Q) or
P ∧ ¬Q.

5. Jun 4, 2009

### kof9595995

but not p or q is material conditional, I know it shares the same truth table of with logical implication(p=>q), I can understand the "not p or q" case but not the logical implication

6. Jun 5, 2009

### SW VandeCarr

Perhaps I'm misunderstanding something here but isn't P^not Q the same as P(T) and Q(F)? In that case P--> Q (F). This is straightforward material implication. If your talking about modal logic (strict implication) you need the possibility operator.

EDIT: A strict implication would be P==>Q iff not$(P^not Q) where$ is the possibility operator.

Last edited: Jun 5, 2009
7. Jun 5, 2009

### honestrosewater

2 is not the negation of 1.
That two formulas share the same truth table is another way of saying that they are two names for the same object. The formulas "P -> Q" and "~P v Q" both refer to the same case x:

$$\begin{array}{|c|c|c|} \hline \mathbf P&\mathbf Q&\mathbf x\\ \hline T&T&T\\ \hline T&F&F\\ \hline F&T&T\\ \hline F&F&T\\ \hline\end{array}$$

The rules for using the negation, disjunction, and conjunction operators (~, v, and &) are probably easier to remember and implement for a lot of people because of the familiarity and nice symmetry in the way that negation distributes over the latter two:

~(P & Q) <=> ~P v ~Q
~(P v Q) <=> ~P & ~Q

You can try to figure out how to distribute negation over implication by considering the definition of the implication operator, -> (which operates on truth values):

->(v1, v2) = {
F iff v1 = T and v2 = F;
T otherwise}​

and looking at the possibilities in a truth table:

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \mathbf P&\mathbf \neg P&\mathbf Q&\mathbf \neg Q &{\mathbf P \rightarrow \neg Q }&{\mathbf Q \rightarrow \neg P} &{\mathbf P \rightarrow Q }&{\mathbf \neg Q \rightarrow \neg P} &{\mathbf \neg P \rightarrow \neg Q }&{\mathbf Q \rightarrow P} &{\mathbf \neg P \rightarrow Q }&{\mathbf \neg Q \rightarrow P}\\ \hline T&F&T&F&F&F&T&T&T&T&T&T\\ \hline T&F&F&T&T&T&F&F&T&T&T&T\\ \hline F&T&T&F&T&T&T&T&F&F&T&T\\ \hline F&T&F&T&T&T&T&T&T&T&F&F\\ \hline\end{array}$$

Here are all formulas of the form t1 -> t2, where the set of terms t are {P, Q, ~P, ~Q} and t1 != t2. Note that all formulas of this form are false in only one case and true in the other three, so a negation of any of these formulas will be true in only one case and false in the other three, and so you cannot express the negation of this form of formula using this form of formula, i.e., negation does not 'distribute' in this sense. I suspect there is a general rule regarding this.

If you really want one, you are free to define an operator, say <-, where t1 <- t2 <=> ~(t1 -> t2).

I wonder why you thought 2 was the negation of 1. Did you read any rules for manipulating these symbols, or were you trying to figure out how others were using them?

8. Jun 5, 2009

### SW VandeCarr

The OP uses the term "logical implication" as distinct from material implication. Could he or she be thinking of strict implication (modal logic)? (see post 6).

Last edited: Jun 5, 2009
9. Jun 5, 2009

### honestrosewater

Perhaps. It sounded like they were talking about the classical interpretation of formulas containing an implication symbol. But some clarification would be helpful. Implication is central to logic and shows up in many ways. To me, it could mean several things:

1) You have an implication symbol in your formal language, usually denoted by a right-arrow ->, which is used to mechanically build strings by a rule like this: if f1 and f2 are formulas, then f1 -> f2 is also a formula. An implication could mean a formula of this form (where the last rule applied in its formation was this implication rule).

2) The truth-functional operation that I mentioned, usually also denoted by a right-arrow. It is associated with the implication symbol in that this operation is what the symbol is taken to mean when your formal language is given an interpretation. This interpretation is signified by truth tables.

3) A syntactic/proof-theoretic implication relation on formulas and sets of formulas, which tells you what formulas are provable from what other formulas, often denoted by a turnstile |-.

4) A semantic/model-theoretic implication relation on formulas and sets of formulas, which tells you how interpreted formulas are related by truth, often denoted by a double-turnstile |= or double-right-arrow =>.

All of these "implications" are also variously called conditionals, entailments, and inferences. This general concept that two things x and y are connected in a way such that if you have x, in the most general sense of 'having', you also have y also underlies the idea of inference rules. So it helps to be clear about what type of objects you're dealing with (symbol, formula, operation, syntactic relation, semantic relation). So far, "material conditional", "logical implication", "p implies q", "~P v Q", "P → Q", "P => Q", and interpretations of implication have all been taken to be similar or the same, without saying which is the case. That and statements like
invite confusion.

10. Jun 5, 2009

### SW VandeCarr

As I understand it, strict implication uses a "possibility operator" usually represented by a vertically elongated diamond (since I don't have that option I'm using $). If you use modal logic, you get a different result: P=>Q iff -$(P^notQ). In plain language P implies Q if and only if P^notQ is not possible (indicated by the minus sign). Material implication says P->Q if any of three conditions exist: P,Q; notP,Q; notP,notQ. Strict implication has application in some electronic logic networks.

Last edited: Jun 5, 2009
11. Jun 5, 2009

### honestrosewater

I get what you're saying, but again, a little care could avoid confusion. What is material logic? The definitions above are part of classical logic. In classical logic, P -> Q does not have any meaning or make any claims; it is an uninterpreted formula, a string of symbols. If I is a classical interpretation of this formula,

I(P -> Q) = {
F iff I(P) = T and I(Q) = F;
T otherwise}​

and P -> Q is accordingly assigned a value of T or F under a given interpretation or class of interpretations. The facts that you refer to regarding the values of formulas under all classical interpretations are not your object language's formulas or their interpretations; they involve a semantic implication relation and can be stated thusly: {P, Q} |= P -> Q and {~P} |= P -> Q.

The original problem seemed to only be a question of how to negate P -> Q, but a need for more attention to terminology and notation is evident:
Obviously, the negation of "p implies q" is "p does not imply q", but the negation was first stated as "p implies not q", and "does not imply" is not a common symbol or operator and is not defined anywhere or used again.

The negation of a formula f can mean a few things:

1) The formula formed by applying a negation rule to f, which would usually be the formula ~f.
2) The interpretation of ~f.
3) Any of the formulas that are equivalent in some sense to (1) or (2).

(1) is straightforwardly ~(P -> Q). (2) is obtained just as easily by swapping the truth values of I(P -> Q). Examples of (3) were given in a reply, but there seems to still be confusion about the interaction of negation and implication as symbols and operators. Other than this negation, the OP's reasoning is correct.

12. Jun 5, 2009

### SW VandeCarr

Thanks for your comprehensive reply, but the quote you responded to contained an error. It should have been 'material implication' instead of 'material logic'. This has been corrected. The reason I brought up strict implication is because I couldn't follow the OP's argument and thought
he was possibly confusing material implication with strict implication.

EDIT: Modes like possibility/ impossibility are are not synonymous with affirmation/negation. This can be shown by trying to express strict implication without the modal operator: P=>Q iff not(P^notQ). This reduces to (P=>Q) iff (notP^Q) which violates the definition of strict implication. Under strict implication P implies Q iff (P^not Q) is not possible. Modal logic is not reducible to "classical" logic. (P^Q), (notP^Q), and (notP^notQ)are not strong enough to support strict implication.

Last edited: Jun 6, 2009
13. Jun 8, 2009

### kof9595995

Thanks for the detailed answers, I think I understand it now.