Converse nonimplication

{{short description|Logical connective}} [[File:Venn0010.svg|thumb|240px|Venn diagram of <math>P \nleftarrow Q</math><br>(the red area is true)]]

In logic, '''converse nonimplication'''<ref>Lehtonen, Eero, and Poikonen, J.H.</ref> 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>P \nleftarrow Q</math>, or <math>P \not \subset Q</math>, and is logically equivalent to <math>\neg (P \leftarrow Q)</math> and <math>\neg P \wedge Q</math>.

===Truth table=== The truth table of <math> A \nleftarrow B </math>.<ref name="Knuth">{{harvnb|Knuth|2011|p=49}}</ref>

==Notation== Converse nonimplication is notated <math display="inline">p \nleftarrow q</math>, which is the left arrow from converse implication (<math display="inline"> \leftarrow</math>), negated with a stroke ({{math|size=100%|/}}).

Alternatives include * <math display="inline">p \not\subset q</math>, which combines converse implication's <math>\subset</math>, negated with a stroke ({{math|size=100%|/}}). * <math display="inline">p \tilde{\leftarrow} q</math>, which combines converse implication's left arrow (<math display="inline">\leftarrow</math>) with negation's tilde (<math display="inline">\sim</math>). * M''pq'', 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=== Not P, but Q.

==Boolean algebra== <div id="Definition"> Converse nonimplication in a general Boolean algebra is defined as <math display="inline">q \nleftarrow p=q'p</math>.

<div id="TwoElements"> Example of a 2-element Boolean algebra: the 2 elements {0,1} with 0 as zero and 1 as unity element, operators <math display="inline">\sim</math> as complement operator, <math display="inline">\vee</math> as join operator and <math display="inline">\wedge</math> as meet operator, build the Boolean algebra of propositional logic. {| class="wikitable" style="border:none; background:transparent;text-align:center;" |style="border:none;" | {| class="wikitable" style="border:none; background:transparent;" | <math display="inline">{}\sim x</math> | style="background-color:#DDFFDD"| {{math|size=100%|1}} | style="background-color:#DDFFDD"| {{math|size=100%|0}} |- | {{mvar|size=100%|x}} ! {{math|size=100%|0}} ! {{math|size=100%|1}} |} | style="border:none;" |and |style="border:none;" | {| class="wikitable" style="border:none; background:transparent;text-align:center;" |{{mvar|size=100%|y}} |style="border:none;" | |- !{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} |- !{{math|size=100%|0}} | style="background-color:#DDFFDD"|{{math|size=100%|0}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} |- | style="text-align:center;" |<math display="inline">y_\vee x</math> !{{math|size=100%|0}} !{{math|size=100%|1}} |{{mvar|size=100%|x}} |} | style="border:none;" |and |style="border:none;" | {| class="wikitable" style="border:none; background:transparent;text-align:center;" |{{mvar|size=100%|y}} |style="border:none;" | |- !{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|0}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} |- !{{math|size=100%|0}} | style="background-color:#DDFFDD"|{{math|size=100%|0}} | style="background-color:#DDFFDD"|{{math|size=100%|0}} |- | style="text-align:center;" |<math display="inline">y_\wedge x</math> !{{math|size=100%|0}} !{{math|size=100%|1}} |{{mvar|size=100%|x}} |} | style="border:none;" |then <math>\scriptstyle{y \nleftarrow x}\!</math> means |style="border:none;" | {| class="wikitable" style="border:none; background:transparent;text-align:center;" |{{mvar|size=100%|y}} |style="border:none;" | |- !{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|0}} | style="background-color:#DDFFDD"|{{math|size=100%|0}} |- !{{math|size=100%|0}} | style="background-color:#DDFFDD"|{{math|size=100%|0}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} |- | style="text-align:center;" |<math>\scriptstyle{y \nleftarrow x}\!</math> !{{math|size=100%|0}} !{{math|size=100%|1}} |{{mvar|size=100%|x}} |} |- | style="border:none;" |''(Negation)'' | style="border:none;" | | style="border:none;" |''(Inclusive or)'' | style="border:none;" | | style="border:none;" |''(And)'' | style="border:none;" | | style="border:none;" |''(Converse nonimplication)'' |} </div> <div id="DivisorsOfSix"> {{anchor|s4}} 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>\scriptstyle{ ^{c}}\!</math> (co-divisor of 6) as complement operator, <math>\scriptstyle{_\vee}\!</math> (least common multiple) as join operator and <math>\scriptstyle{_\wedge}\!</math> (greatest common divisor) as meet operator, build a Boolean algebra. {| class="wikitable" style="border:none; background:transparent;text-align:center;" |style="border:none;" | {| class="wikitable" style="border:none; background:transparent;" | <math>\scriptstyle{x^c}\!</math> | style="background-color:#DDFFDD"| {{math|size=100%|6}} | style="background-color:#DDFFDD"| {{math|size=100%|3}} | style="background-color:#DDFFDD"| {{math|size=100%|2}} | style="background-color:#DDFFDD"| {{math|size=100%|1}} |- | {{mvar|size=100%|x}} ! {{math|size=100%|1}} ! {{math|size=100%|2}} ! {{math|size=100%|3}} ! {{math|size=100%|6}} |} | style="border:none;" |and |style="border:none;" | {| class="wikitable" style="border:none; background:transparent;text-align:center;" |{{mvar|size=100%|y}} |style="border:none;" | |- !{{math|size=100%|6}} | style="background-color:#DDFFDD"|{{math|size=100%|6}} | style="background-color:#DDFFDD"|{{math|size=100%|6}} | style="background-color:#DDFFDD"|{{math|size=100%|6}} | style="background-color:#DDFFDD"|{{math|size=100%|6}} |- !{{math|size=100%|3}} | style="background-color:#DDFFDD"|{{math|size=100%|3}} | style="background-color:#DDFFDD"|{{math|size=100%|6}} | style="background-color:#DDFFDD"|{{math|size=100%|3}} | style="background-color:#DDFFDD"|{{math|size=100%|6}} |- !{{math|size=100%|2}} | style="background-color:#DDFFDD"|{{math|size=100%|2}} | style="background-color:#DDFFDD"|{{math|size=100%|2}} | style="background-color:#DDFFDD"|{{math|size=100%|6}} | style="background-color:#DDFFDD"|{{math|size=100%|6}} |- !{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|2}} | style="background-color:#DDFFDD"|{{math|size=100%|3}} | style="background-color:#DDFFDD"|{{math|size=100%|6}} |- | style="text-align:center;" |<math>\scriptstyle{y_\vee x}\!</math> !{{math|size=100%|1}} !{{math|size=100%|2}} !{{math|size=100%|3}} !{{math|size=100%|6}} |{{mvar|size=100%|x}} |} | style="border:none;" |and |style="border:none;" | {| class="wikitable" style="border:none; background:transparent;text-align:center;" |{{mvar|size=100%|y}} |style="border:none;" | |- !{{math|size=100%|6}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|2}} | style="background-color:#DDFFDD"|{{math|size=100%|3}} | style="background-color:#DDFFDD"|{{math|size=100%|6}} |- !{{math|size=100%|3}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|3}} | style="background-color:#DDFFDD"|{{math|size=100%|3}} |- !{{math|size=100%|2}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|2}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|2}} |- !{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} |- | style="text-align:center;" |<math>\scriptstyle{y_\wedge x}</math> !{{math|size=100%|1}} !{{math|size=100%|2}} !{{math|size=100%|3}} !{{math|size=100%|6}} |{{mvar|size=100%|x}} |} | style="border:none;" |then <math>\scriptstyle{y \nleftarrow x}\!</math> means |style="border:none;" | {| class="wikitable" style="border:none; background:transparent;text-align:center;" |{{mvar|size=100%|y}} |style="border:none;" | |- !{{math|size=100%|6}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} |- !{{math|size=100%|3}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|2}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|2}} |- !{{math|size=100%|2}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|3}} | style="background-color:#DDFFDD"|{{math|size=100%|3}} |- !{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|1}} | style="background-color:#DDFFDD"|{{math|size=100%|2}} | style="background-color:#DDFFDD"|{{math|size=100%|3}} | style="background-color:#DDFFDD"|{{math|size=100%|6}} |- | style="text-align:center;" |<math>\scriptstyle{y \nleftarrow x}\!</math> !{{math|size=100%|1}} !{{math|size=100%|2}} !{{math|size=100%|3}} !{{math|size=100%|6}} |{{mvar|size=100%|x}} |} |- | style="border:none;" |''(Co-divisor 6)'' | style="border:none;" | | style="border:none;" |''(Least common multiple)'' | style="border:none;" | | style="border:none;" |''(Greatest common divisor)'' | style="border:none;" | | style="border:none;" |''(x's greatest divisor coprime with y)'' |} </div>

===Properties=== ====Non-associative==== <math>r \nleftarrow (q \nleftarrow p) = (r \nleftarrow q) \nleftarrow p</math> if and only if <math>rp = 0</math> #s5 (In a two-element Boolean algebra the latter condition is reduced to <math>r = 0</math> or <math>p=0</math>). Hence in a nontrivial Boolean algebra converse nonimplication is '''nonassociative'''. <math display="block">\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>rp=0</math>.

====Non-commutative====

* <math>q \nleftarrow p=p \nleftarrow q</math> if and only if <math>q = p</math> #s6. Hence converse nonimplication is '''noncommutative'''.

====Neutral and absorbing elements====

* {{math|size=100%|0}} is a left neutral element (<math>0 \nleftarrow p=p</math>) and a right absorbing element (<math>{p \nleftarrow 0=0}</math>). * <math>1 \nleftarrow p=0</math>, <math>p \nleftarrow 1=p'</math>, and <math>p \nleftarrow p=0</math>. * Implication <math>q \rightarrow p</math> is the dual of converse nonimplication <math>q \nleftarrow p</math> #s7. </div>

<div id="NonCommutative"> {{anchor|s6}} {| style="background-color:white;" !colspan="5"| Converse nonimplication is noncommutative |- ! style="padding-right: 2em;" | Step ! style="text-align: left;" | Make use of ! colspan="3"|Resulting in |- | s.1 | Definition |colspan="3"|<math>\scriptstyle{q\tilde{\leftarrow}p=q'p\,}\!</math> |- | s.2 | Definition |colspan="3"|<math>\scriptstyle{p\tilde{\leftarrow}q=p'q\,}\!</math> |- | s.3 | s.1 s.2 |colspan="3"|<math>\scriptstyle{q\tilde{\leftarrow}p=p\tilde{\leftarrow}q\ \Leftrightarrow\ q'p=qp'\,}\!</math> |- | s.4 | |<math>\scriptstyle{q\,}\!</math> | <math>\scriptstyle{=\,}\!</math> | <math>\scriptstyle{q.1\,}\!</math> |- | s.5 | s.4.right - expand Unit element | | <math>\scriptstyle{=\,}\!</math> | <math>\scriptstyle{q.(p+p')\,}\!</math> |- | s.6 | s.5.right - evaluate expression | | <math>\scriptstyle{=\,}\!</math> | <math>\scriptstyle{qp+qp'\,}\!</math> |- | s.7 | s.4.left = s.6.right |colspan="3"|<math>\scriptstyle{q=qp+qp'\,}\!</math> |- | s.8 | |<math>\scriptstyle{q'p=qp'\,}\!</math> |<math>\scriptstyle{\Rightarrow\,}\!</math> |<math>\scriptstyle{qp+qp'=qp+q'p\,}\!</math> |- | s.9 | s.8 - regroup common factors | |<math>\scriptstyle{\Rightarrow\,}\!</math> |<math>\scriptstyle{q.(p+p')=(q+q').p\,}\!</math> |- | s.10 | style="padding-right: 3em;"| s.9 - join of complements equals unity | |<math>\scriptstyle{\Rightarrow\,}\!</math> |<math>\scriptstyle{q.1=1.p\,}\!</math> |- | s.11 | s.10.right - evaluate expression | |<math>\scriptstyle{\Rightarrow\,}\!</math> |<math>\scriptstyle{q=p\,}\!</math> |- | s.12 | s.8 s.11 |colspan="3"|<math>\scriptstyle{q'p=qp'\ \Rightarrow\ q=p\,}\!</math> |- | s.13 | |colspan="3"|<math>\scriptstyle{q=p\ \Rightarrow\ q'p=qp'\,}\!</math> |- | s.14 |s.12 s.13 |colspan="3"|<math>\scriptstyle{q=p\ \Leftrightarrow\ q'p=qp'\,}\!</math> |- | s.15 | s.3 s.14 |colspan="3"|<math>\scriptstyle{q\tilde{\leftarrow}p=p\tilde{\leftarrow}q\ \Leftrightarrow\ q=p\,}\!</math> |- |} </div> <div id="Dual"> {{anchor|s7}} {| style="background-color:white;" !colspan="5"| Implication is the dual of converse nonimplication |- ! style="padding-right: 2em;" | Step ! style="text-align: left; padding-right: 3em;" | Make use of ! colspan="3"|Resulting in |- | s.1 | Definition |<math>\scriptstyle{\operatorname{dual}(q\tilde{\leftarrow}p)\,}\!</math> |<math>\scriptstyle{=\,}\!</math> |<math>\scriptstyle{\operatorname{dual}(q'p)\,}\!</math> |- | s.2 |s.1.right - .'s dual is + | | <math>\scriptstyle{=\,}\!</math> | <math>\scriptstyle{q'+p\,}\!</math> |- | s.3 | s.2.right - Involution complement | | <math>\scriptstyle{=\,}\!</math> | <math>\scriptstyle{(q'+p)''\,}\!</math> |- | s.4 | style="padding-right: 3em;" | s.3.right - De Morgan's laws applied once | | <math>\scriptstyle{=\,}\!</math> | <math>\scriptstyle{(qp')'\,}\!</math> |- | s.5 | s.4.right - Commutative law | | <math>\scriptstyle{=\,}\!</math> | <math>\scriptstyle{(p'q)'\,}\!</math> |- | s.6 | s.5.right | | <math>\scriptstyle{=\,}\!</math> | <math>\scriptstyle{(p\tilde{\leftarrow}q)'\,}\!</math> |- | s.7 | s.6.right | | <math>\scriptstyle{=\,}\!</math> | <math>\scriptstyle{p\leftarrow q\,}\!</math> |- | s.8 | s.7.right | | <math>\scriptstyle{=\,}\!</math> | <math>\scriptstyle{q\rightarrow p\,}\!</math> |- | s.9 | s.1.left = s.8.right |colspan="3"|<math>\scriptstyle{\operatorname{dual}(q\tilde{\leftarrow}p)=q\rightarrow p\,}\!</math> |- |} </div>

==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.<ref>{{Cite web|url = http://www.codinghorror.com/blog/2007/10/a-visual-explanation-of-sql-joins.html|title = A Visual Explanation of SQL Joins|date = 11 October 2007|access-date = 24 March 2013|archive-date = 15 February 2014|archive-url = https://web.archive.org/web/20140215193839/http://www.codinghorror.com/blog/2007/10/a-visual-explanation-of-sql-joins.html|url-status = dead}}</ref>

==References== {{Reflist}} *{{cite book | last=Knuth| first=Donald E.| author-link=Donald Knuth| year=2011| title=The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1| edition=1st| publisher=Addison-Wesley Professional| isbn=978-0-201-03804-0}}

==External links== *{{Commonscatinline}}

{{DEFAULTSORT:Converse Nonimplication}} Category:Logical connectives