Converse nonimplication

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In logic, converse nonimplication[1] is a logical connective which is the negation of the converse of implication.

Definition[edit]

_{p\not\subset q}\! which is the same as _{\sim(p\subset q)}\!

Truth table[edit]

The truth table of _{p\not\subset q}\!.[2]

p q _{\not\subset}\!
T T F
T F F
F T T
F F F

Venn diagram[edit]

The Venn Diagram of "It is not the case that B implies A" (the red area is true)

Venn0010.svg

Properties[edit]

falsehood-preserving: The interpretation under which all variables are assigned a truth value of 'false' produces a truth value of 'false' as a result of converse nonimplication

Symbol[edit]

Alternatives for _{p\not\subset q}\! are

  • _{p\tilde{\leftarrow}q}\!: _{\tilde{\leftarrow}}\! combines Converse implication's left arrow(_{\leftarrow}\!) with Negation's tilde(_{\sim}\!).
  • _{Mpq}\!: uses prefixed capital letter.
  • _{p\nleftarrow q}\!: _{\nleftarrow }\! combines Converse implication's left arrow(_{\leftarrow}\!) denied by means of a stroke(_{/}\!).

Natural language[edit]

Grammatical[edit]

Rhetorical[edit]

"not A but B"

Colloquial[edit]

Boolean algebra[edit]

Converse Nonimplication in a general Boolean algebra is defined as _{q \nleftarrow p=q'p}\!.

Example of a 2-element Boolean algebra: the 2 elements {0,1} with 0 as zero and 1 as unity element, operators _{\sim}\! as complement operator, _{_\vee}\! as join operator and _{_\wedge}\! as meet operator, build the Boolean algebra of propositional logic.

_{\sim x}\! _{1}\! _{0}\!
_{x}\! _{0}\! _{1}\!
and
_{y}\!
_{1}\! _{1}\! _{1}\!
_{0}\! _{0}\! _{1}\!
_{y_\vee x}\! _{0}\! _{1}\! _{x}\!
and
_{y}\!
_{1}\! _{0}\! _{1}\!
_{0}\! _{0}\! _{0}\!
_{y_\wedge x}\! _{0}\! _{1}\! _{x}\!
then _{y \nleftarrow x}\! means
_{y}\!
_{1}\! _{0}\! _{0}\!
_{0}\! _{0}\! _{1}\!
_{y \nleftarrow x}\! _{0}\! _{1}\! _{x}\!
(Negation) (Inclusive Or) (And) (Converse Nonimplication)

[4] Example of a 4-element Boolean algebra: the 4 divisors {1,2,3,6} of 6 with 1 as zero and 6 as unity element, operators _{ ^{c}}\! (codivisor of 6) as complement operator, _{_\vee}\! (least common multiple) as join operator and _{_\wedge}\! (greatest common divisor) as meet operator, build a Boolean algebra.

_{x^c}\! _{6}\! _{3}\! _{2}\! _{1}\!
_{x}\! _{1}\! _{2}\! _{3}\! _{6}\!
and
_{y}\!
_{6}\! _{6}\! _{6}\! _{6}\! _{6}\!
_{3}\! _{3}\! _{6}\! _{3}\! _{6}\!
_{2}\! _{2}\! _{2}\! _{6}\! _{6}\!
_{1}\! _{1}\! _{2}\! _{3}\! _{6}\!
_{y_\vee x}\! _{1}\! _{2}\! _{3}\! _{6}\! _{x}\!
and
_{y}\!
_{6}\! _{1}\! _{2}\! _{3}\! _{6}\!
_{3}\! _{1}\! _{1}\! _{3}\! _{3}\!
_{2}\! _{1}\! _{2}\! _{1}\! _{2}\!
_{1}\! _{1}\! _{1}\! _{1}\! _{1}\!
_{y_\wedge x}\! _{1}\! _{2}\! _{3}\! _{6}\! _{x}\!
then _{y \nleftarrow x}\! means
_{y}\!
_{6}\! _{1}\! _{1}\! _{1}\! _{1}\!
_{3}\! _{1}\! _{2}\! _{1}\! _{2}\!
_{2}\! _{1}\! _{1}\! _{3}\! _{3}\!
_{1}\! _{1}\! _{2}\! _{3}\! _{6}\!
_{y \nleftarrow x}\! _{1}\! _{2}\! _{3}\! _{6}\! _{x}\!
(Codivisor 6) (Least Common Multiple) (Greatest Common Divisor) (x's greatest Divisor coprime with y)

Properties[edit]

Non-associative[edit]

_{r \nleftarrow (q \nleftarrow p)=(r \nleftarrow q) \nleftarrow p}\! iff _{rp=0}\! [5] (In a two-element Boolean algebra the latter condition is reduced to _{r=0}\! or _{p=0}\!). Hence in a nontrivial Boolean algebra Converse Nonimplication is nonassociative.


::\begin{align}
(r \nleftarrow q) \nleftarrow p &= r'q \nleftarrow p \qquad \qquad \qquad ~~~~ \text{(by definition)} \\
&= (r'q)'p \qquad \qquad \qquad ~~~~~~ \text{(by definition)} \\
&= (r + q')p \qquad \qquad ~~~~~~~~~ \text{(De Morgan's laws)} \\
&= (r + r'q')p \qquad \qquad ~~~~~~~ \text{(Absorption law)} \\
&= rp + r'q'p \\
&= rp + r'(q \nleftarrow p) \qquad ~~~~~~~~ \text{(by definition)} \\
&= rp + r \nleftarrow (q \nleftarrow p) \qquad ~~~~ \text{(by definition)} \\
\end{align}

Clearly, it is associative iff _{rp=0}\!.

Non-commutative[edit]

  • _{q \nleftarrow p=p \nleftarrow q\,}\! iff _{q=p\,}\! [6]. Hence Converse Nonimplication is noncommutative.

Neutral and absorbing elements[edit]


[6]

Converse Nonimplication is noncommutative
Step Make use of Resulting in
_{s.1 \,}\! Definition _{q\tilde{\leftarrow}p=q'p\,}\!
_{s.2 \,}\! Definition _{p\tilde{\leftarrow}q=p'q\,}\!
_{s.3 \,}\! _{s.1\ s.2 \,}\! _{q\tilde{\leftarrow}p=p\tilde{\leftarrow}q\ \Leftrightarrow\ q'p=qp'\,}\!
_{s.4 \,}\! _{q\,}\! _{=\,}\! _{q.1\,}\!
_{s.5 \,}\! _{s.4.right\,}\! - expand Unit element _{=\,}\! _{q.(p+p')\,}\!
_{s.6 \,}\! _{s.5.right\,}\! - evaluate expression _{=\,}\! _{qp+qp'\,}\!
_{s.7 \,}\! _{s.4.left=s.6.right \,}\! _{q=qp+qp'\,}\!
_{s.8 \,}\! _{q'p=qp'\,}\! _{\Rightarrow\,}\! _{qp+qp'=qp+q'p\,}\!
_{s.9 \,}\! _{s.8 \,}\! - regroup common factors _{\Rightarrow\,}\! _{q.(p+p')=(q+q').p\,}\!
_{s.10 \,}\! _{s.9 \,}\! - join of complements equals unity _{\Rightarrow\,}\! _{q.1=1.p\,}\!
_{s.11 \,}\! _{s.10.right \,}\! - evaluate expression _{\Rightarrow\,}\! _{q=p\,}\!
_{s.12 \,}\! _{s.8\ s.11\,}\! _{q'p=qp'\ \Rightarrow\ q=p\,}\!
_{s.13 \,}\! _{q=p\ \Rightarrow\ q'p=qp'\,}\!
_{s.14 \,}\! _{s.12\ s.13 \,}\! _{q=p\ \Leftrightarrow\ q'p=qp'\,}\!
_{s.15 \,}\! _{s.3\ s.14 \,}\! _{q\tilde{\leftarrow}p=p\tilde{\leftarrow}q\ \Leftrightarrow\ q=p\,}\!

[7]

Implication is the dual of Converse Nonimplication
Step Make use of Resulting in
_{s.1 \,}\! Definition _{dual(q\tilde{\leftarrow}p)\,}\! _{=\,}\! _{dual(q'p)\,}\!
_{s.2 \,}\! _{s.1.right\,}\! - .'s dual is + _{=\,}\! _{q'+p\,}\!
_{s.3 \,}\! _{s.2.right\,}\! - Involution complement _{=\,}\! _{(q'+p)''\,}\!
_{s.4 \,}\! _{s.3.right\,}\! - De Morgan's laws applied once _{=\,}\! _{(qp')'\,}\!
_{s.5 \,}\! _{s.4.right\,}\! - Commutative law _{=\,}\! _{(p'q)'\,}\!
_{s.6 \,}\! _{s.5.right\,}\! _{=\,}\! _{(p\tilde{\leftarrow}q)'\,}\!
_{s.7 \,}\! _{s.6.right\,}\! _{=\,}\! _{p\leftarrow q\,}\!
_{s.8 \,}\! _{s.7.right\,}\! _{=\,}\! _{q\rightarrow p\,}\!
_{s.9 \,}\! _{s.1.left=s.8.right \,}\! _{dual(q\tilde{\leftarrow}p)=q\rightarrow p\,}\!

Computer science[edit]

An example for converse nonimplication in computer science can be found when performing a right outer join on a set of tables from a database, if records not matching the join-condition from the "left" table are being excluded.[3]

Notes[edit]

References[edit]

  • Knuth, Donald E. (2011). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1 (1st ed.). Addison-Wesley Professional. ISBN 0-201-03804-8.