Converse nonimplication

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

Definition

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

Truth table

The truth table of $_{p\not \subset q}\!$.

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

Venn diagram

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

Properties

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

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

Rhetorical

"not A but B"

Boolean algebra

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

Non-associative

$_{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{aligned}(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{aligned}}$

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

Non-commutative

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

Neutral and absorbing elements

• $_{0}\!$ is a left neutral element ($_{0\nleftarrow p=p}\!$) and a right absorbing element ($_{p\nleftarrow 0=0}\!$).
• $_{1\nleftarrow p=0}\!$, $_{p\nleftarrow 1=p'}\!$, and $_{p\nleftarrow p=0}\!$.
• Implication $_{q\rightarrow p}\!$ is the dual of Converse Nonimplication $_{q\nleftarrow p}\!$ ^[7].

^[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

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.

References

• 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. {{cite book}}: Invalid |ref=harv (help)