Converse nonimplication

Short description: Logical connective

Venn diagram of [math]\displaystyle{ P \nleftarrow Q }[/math]
(the red area is true)

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

Definition

Converse nonimplication is notated [math]\displaystyle{ P \nleftarrow Q }[/math], or [math]\displaystyle{ P \not \subset Q }[/math], and is logically equivalent to [math]\displaystyle{ \neg (P \leftarrow Q) }[/math] and [math]\displaystyle{ \neg P \wedge Q }[/math].

Truth table

The truth table of [math]\displaystyle{ P \nleftarrow Q }[/math].

[math]\displaystyle{ P }[/math]	[math]\displaystyle{ Q }[/math]	[math]\displaystyle{ P \nleftarrow Q }[/math]
True	True	False
True	False	False
False	True	True
False	False	False

Notation

Converse nonimplication is notated [math]\displaystyle{ p \nleftarrow q }[/math], which is the left arrow from converse implication ([math]\displaystyle{ \leftarrow }[/math]), negated with a stroke (/).

Alternatives include

• [math]\displaystyle{ p \not\subset q }[/math], which combines converse implication's [math]\displaystyle{ \subset }[/math], negated with a stroke (/).
• [math]\displaystyle{ p \tilde{\leftarrow} q }[/math], which combines converse implication's left arrow ([math]\displaystyle{ \leftarrow }[/math]) with negation's tilde ([math]\displaystyle{ \sim }[/math]).
• 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.

Boolean algebra

Converse Nonimplication in a general Boolean algebra is defined as [math]\displaystyle{ q \nleftarrow p=q'p }[/math].

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

[math]\displaystyle{ {}\sim x }[/math] 1 0 x 0 1	and	y 1 1 1 0 0 1 [math]\displaystyle{ y_\vee x }[/math] 0 1 x	and	y 1 0 1 0 0 0 [math]\displaystyle{ y_\wedge x }[/math] 0 1 x	then [math]\displaystyle{ \scriptstyle{y \nleftarrow x}\! }[/math] means	y 1 0 0 0 0 1 [math]\displaystyle{ \scriptstyle{y \nleftarrow x}\! }[/math] 0 1 x
(Negation)		(Inclusive or)		(And)		(Converse nonimplication)

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 [math]\displaystyle{ \scriptstyle{ ^{c}}\! }[/math] (co-divisor of 6) as complement operator, [math]\displaystyle{ \scriptstyle{_\vee}\! }[/math] (least common multiple) as join operator and [math]\displaystyle{ \scriptstyle{_\wedge}\! }[/math] (greatest common divisor) as meet operator, build a Boolean algebra.

[math]\displaystyle{ \scriptstyle{x^c}\! }[/math] 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 [math]\displaystyle{ \scriptstyle{y_\vee x}\! }[/math] 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 [math]\displaystyle{ \scriptstyle{y_\wedge x} }[/math] 1 2 3 6 x	then [math]\displaystyle{ \scriptstyle{y \nleftarrow x}\! }[/math] means	y 6 1 1 1 1 3 1 2 1 2 2 1 1 3 3 1 1 2 3 6 [math]\displaystyle{ \scriptstyle{y \nleftarrow x}\! }[/math] 1 2 3 6 x
(Co-divisor 6)		(Least common multiple)		(Greatest common divisor)		(x's greatest divisor coprime with y)

Properties

Non-associative

[math]\displaystyle{ r \nleftarrow (q \nleftarrow p) = (r \nleftarrow q) \nleftarrow p }[/math] if and only if [math]\displaystyle{ rp = 0 }[/math] #s5 (In a two-element Boolean algebra the latter condition is reduced to [math]\displaystyle{ r = 0 }[/math] or [math]\displaystyle{ p=0 }[/math]). Hence in a nontrivial Boolean algebra Converse Nonimplication is nonassociative. [math]\displaystyle{ \begin{align} (r \nleftarrow q) \nleftarrow p &= r'q \nleftarrow p & \text{(by definition)} \\ &= (r'q)'p & \text{(by definition)} \\ &= (r + q')p & \text{(De Morgan's laws)} \\ &= (r + r'q')p & \text{(Absorption law)} \\ &= rp + r'q'p \\ &= rp + r'(q \nleftarrow p) & \text{(by definition)} \\ &= rp + r \nleftarrow (q \nleftarrow p) & \text{(by definition)} \\ \end{align} }[/math]

Clearly, it is associative if and only if [math]\displaystyle{ rp=0 }[/math].

Non-commutative

• [math]\displaystyle{ q \nleftarrow p=p \nleftarrow q }[/math] if and only if [math]\displaystyle{ q = p }[/math] #s6. Hence Converse Nonimplication is noncommutative.

Neutral and absorbing elements

• 0 is a left neutral element ([math]\displaystyle{ 0 \nleftarrow p=p }[/math]) and a right absorbing element ([math]\displaystyle{ {p \nleftarrow 0=0} }[/math]).
• [math]\displaystyle{ 1 \nleftarrow p=0 }[/math], [math]\displaystyle{ p \nleftarrow 1=p' }[/math], and [math]\displaystyle{ p \nleftarrow p=0 }[/math].
• Implication [math]\displaystyle{ q \rightarrow p }[/math] is the dual of converse nonimplication [math]\displaystyle{ q \nleftarrow p }[/math] #s7.

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

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

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 978-0-201-03804-0.