Converse nonimplication

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 ${\displaystyle P\nleftarrow Q}$, or ${\displaystyle P\not \subset Q}$, and is logically equivalent to ${\displaystyle \neg (P\leftarrow Q)}$ and ${\displaystyle \neg P\wedge Q}$.

Truth table

The truth table of ${\displaystyle A\nleftarrow B}$.^[2]

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\nleftarrow B}$
F	F	F
F	T	T
T	F	F
T	T	F

Notation

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

Alternatives include

• ${\textstyle p\not \subset q}$, which combines converse implication's ${\displaystyle \subset }$, negated with a stroke (/).
• ${\textstyle p{\tilde {\leftarrow }}q}$, which combines converse implication's left arrow (${\textstyle \leftarrow }$) with negation's tilde (${\textstyle \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 ${\textstyle 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 ${\textstyle \sim }$ as complement operator, ${\textstyle \vee }$ as join operator and ${\textstyle \wedge }$ as meet operator, build the Boolean algebra of propositional logic.

${\textstyle {}\sim x}$ 1 0 x 0 1	and	y 1 1 1 0 0 1 ${\textstyle y_{\vee }x}$ 0 1 x	and	y 1 0 1 0 0 0 ${\textstyle y_{\wedge }x}$ 0 1 x	then ${\displaystyle \scriptstyle {y\nleftarrow x}\!}$ means	y 1 0 0 0 0 1 ${\displaystyle \scriptstyle {y\nleftarrow x}\!}$ 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 ${\displaystyle \scriptstyle {^{c}}\!}$ (co-divisor of 6) as complement operator, ${\displaystyle \scriptstyle {_{\vee }}\!}$ (least common multiple) as join operator and ${\displaystyle \scriptstyle {_{\wedge }}\!}$ (greatest common divisor) as meet operator, build a Boolean algebra.

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

Properties

Non-associative

${\displaystyle r\nleftarrow (q\nleftarrow p)=(r\nleftarrow q)\nleftarrow p}$ if and only if ${\displaystyle rp=0}$ #s5 (In a two-element Boolean algebra the latter condition is reduced to ${\displaystyle r=0}$ or ${\displaystyle p=0}$). Hence in a nontrivial Boolean algebra Converse Nonimplication is nonassociative.

$${\displaystyle {\begin{aligned}(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{aligned}}}$$

Clearly, it is associative if and only if ${\displaystyle rp=0}$.

Non-commutative

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

Neutral and absorbing elements

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

Converse Nonimplication is noncommutative
Step	Make use of	Resulting in
s.1	Definition	${\displaystyle \scriptstyle {q{\tilde {\leftarrow }}p=q'p\,}\!}$
s.2	Definition	${\displaystyle \scriptstyle {p{\tilde {\leftarrow }}q=p'q\,}\!}$
s.3	s.1 s.2	${\displaystyle \scriptstyle {q{\tilde {\leftarrow }}p=p{\tilde {\leftarrow }}q\ \Leftrightarrow \ q'p=qp'\,}\!}$
s.4		${\displaystyle \scriptstyle {q\,}\!}$	${\displaystyle \scriptstyle {=\,}\!}$	${\displaystyle \scriptstyle {q.1\,}\!}$
s.5	s.4.right - expand Unit element		${\displaystyle \scriptstyle {=\,}\!}$	${\displaystyle \scriptstyle {q.(p+p')\,}\!}$
s.6	s.5.right - evaluate expression		${\displaystyle \scriptstyle {=\,}\!}$	${\displaystyle \scriptstyle {qp+qp'\,}\!}$
s.7	s.4.left = s.6.right	${\displaystyle \scriptstyle {q=qp+qp'\,}\!}$
s.8		${\displaystyle \scriptstyle {q'p=qp'\,}\!}$	${\displaystyle \scriptstyle {\Rightarrow \,}\!}$	${\displaystyle \scriptstyle {qp+qp'=qp+q'p\,}\!}$
s.9	s.8 - regroup common factors		${\displaystyle \scriptstyle {\Rightarrow \,}\!}$	${\displaystyle \scriptstyle {q.(p+p')=(q+q').p\,}\!}$
s.10	s.9 - join of complements equals unity		${\displaystyle \scriptstyle {\Rightarrow \,}\!}$	${\displaystyle \scriptstyle {q.1=1.p\,}\!}$
s.11	s.10.right - evaluate expression		${\displaystyle \scriptstyle {\Rightarrow \,}\!}$	${\displaystyle \scriptstyle {q=p\,}\!}$
s.12	s.8 s.11	${\displaystyle \scriptstyle {q'p=qp'\ \Rightarrow \ q=p\,}\!}$
s.13		${\displaystyle \scriptstyle {q=p\ \Rightarrow \ q'p=qp'\,}\!}$
s.14	s.12 s.13	${\displaystyle \scriptstyle {q=p\ \Leftrightarrow \ q'p=qp'\,}\!}$
s.15	s.3 s.14	${\displaystyle \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	${\displaystyle \scriptstyle {\operatorname {dual} (q{\tilde {\leftarrow }}p)\,}\!}$	${\displaystyle \scriptstyle {=\,}\!}$	${\displaystyle \scriptstyle {\operatorname {dual} (q'p)\,}\!}$
s.2	s.1.right - .'s dual is +		${\displaystyle \scriptstyle {=\,}\!}$	${\displaystyle \scriptstyle {q'+p\,}\!}$
s.3	s.2.right - Involution complement		${\displaystyle \scriptstyle {=\,}\!}$	${\displaystyle \scriptstyle {(q'+p)''\,}\!}$
s.4	s.3.right - De Morgan's laws applied once		${\displaystyle \scriptstyle {=\,}\!}$	${\displaystyle \scriptstyle {(qp')'\,}\!}$
s.5	s.4.right -  Commutative law		${\displaystyle \scriptstyle {=\,}\!}$	${\displaystyle \scriptstyle {(p'q)'\,}\!}$
s.6	s.5.right		${\displaystyle \scriptstyle {=\,}\!}$	${\displaystyle \scriptstyle {(p{\tilde {\leftarrow }}q)'\,}\!}$
s.7	s.6.right		${\displaystyle \scriptstyle {=\,}\!}$	${\displaystyle \scriptstyle {p\leftarrow q\,}\!}$
s.8	s.7.right		${\displaystyle \scriptstyle {=\,}\!}$	${\displaystyle \scriptstyle {q\rightarrow p\,}\!}$
s.9	s.1.left = s.8.right	${\displaystyle \scriptstyle {\operatorname {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.^[3]

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.

External links

• Media related to Converse nonimplication at Wikimedia Commons

This page was last edited on 2 March 2024, at 23:40