Converse nonimplication explained

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

Definition

Converse nonimplication is notated

P \nleftarrow Q , or P \not \subset Q , and is logically equivalent to \neg (P \leftarrow Q) and \neg P \wedge Q .

Truth table

The truth table of

A \nleftarrow B .

Notation

Converse nonimplication is notated $p\; \backslash nleftarrow\; q$, which is the left arrow from converse implication ($\backslash leftarrow$), negated with a stroke .

Alternatives include

\subset , negated with a stroke .

• $p\; \backslash tilde\; q$, which combines converse implication's left arrow ($\backslash leftarrow$) with negation's tilde ($\backslash sim$).
• Mpq, in Bocheński notation

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

Natural language

Grammatical

Example,

If it rains (P) then I get wet (Q), just because I am wet (Q) does not mean it is raining, in reality I went to a pool party with the co-ed staff, in my clothes (~P) and that is why I am facilitating this lecture in this state (Q).

Rhetorical

Q does not imply P.

Colloquial

Boolean algebra

Converse Nonimplication in a general Boolean algebra is defined as $q\; \backslash nleftarrow\; p=q\text{'}p$.

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

	and		and		then \scriptstyle{y \nleftarrow x}\	means
(Negation)		(Inclusive or)		(And)		(Converse nonimplication)

Example of a 4-element Boolean algebra: the 4 divisors of 6 with 1 as zero and 6 as unity element, operators

\scriptstyle{ ^{c} }\! (co-divisor of 6) as complement operator, \scriptstyle{ _{\vee}} (least common multiple) as join operator and \scriptstyle{ _{\wedge}} (greatest common divisor) as meet operator, build a Boolean algebra.

	and		and		then \scriptstyle{y \nleftarrow x}\	means
(Co-divisor 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 if and only if rp = 0

1. s5

(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.

Clearly, it is associative if and only if

rp =0 .

Non-commutative

q \nleftarrow p = p \nleftarrow q if and only if q = p

1. s6

. Hence Converse Nonimplication is noncommutative.

Neutral and absorbing elements

• 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 → p is the dual of converse nonimplication q \nleftarrow p

1. s7

.

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

Implication is the dual of Converse Nonimplication
Step	Make use of	Resulting in
s.1	Definition	\scriptstyle{\operatorname{dual}(q\tilde{\leftarrow}p)}	\scriptstyle{ = }	\scriptstyle{\operatorname{dual}(q'p)}
s.2	s.1.right - .'s dual is +		\scriptstyle{ = }	\scriptstyle{q' + p}
s.3	s.2.right - Involution complement		\scriptstyle{ = }	\scriptstyle{(q' + p)''}
s.4	s.3.right - De Morgan's laws applied once		\scriptstyle{ = }	\scriptstyle{(qp')'}
s.5	s.4.right - Commutative law		\scriptstyle{ = }	\scriptstyle{(p'q)'}
s.6	s.5.right		\scriptstyle{ = }	\scriptstyle{(p\tilde{\leftarrow}q)'}
s.7	s.6.right		\scriptstyle{ = }	\scriptstyle{p\leftarrow q}
s.8	s.7.right		\scriptstyle{ = }	\scriptstyle{q → p}
s.9	s.1.left = s.8.right	\scriptstyle{\operatorname{dual}(q\tilde{\leftarrow}p) = q → 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.^[2]

References

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

Notes and References

1. Lehtonen, Eero, and Poikonen, J.H.
2. Web site: A Visual Explanation of SQL Joins. 11 October 2007. 24 March 2013. 15 February 2014. https://web.archive.org/web/20140215193839/http://www.codinghorror.com/blog/2007/10/a-visual-explanation-of-sql-joins.html. dead.