GetWiki

{{short description|Logical connective}}File:Venn0010.svg|thumb|240px|Venn diagramVenn diagramIn logic, converse nonimplicationLehtonen, Eero, and Poikonen, J.H. 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 .{{harvnb|Knuth|2011|p=49}}{{2-ary truth table|0|1|0|0|A nleftarrow B}}

Notation

Converse nonimplication is notated p nleftarrow q, which is the left arrow from converse implication ( leftarrow), negated with a stroke ({{math|size=100%|/}}).Alternatives include

• p notsubset q, which combines converse implication's subset, negated with a stroke ({{math|size=100%|/}}).
• p tilde{leftarrow} q, which combines converse implication's left arrow (leftarrow) with negation's tilde (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

{{Empty section|date=February 2011}}

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.{| class="wikitable" style="border:none; background:transparent;text-align:center;"

{| class="wikitable" style="border:none; background:transparent;"| {}sim x	{{math	1}}	{{math	0}}
size=100%|x}}! {{math|size=100%|0}}! {{math|size=100%|1}}

and

{| class="wikitable" style="border:none; background:transparent;text-align:center;"

size=100%|y}}

!{{math|size=100%|1}}!{{math|size=100%|0}}

{{math	1}}	{{math	1}}
{{math	0}}	{{math	1}}
y_vee x!{{math|size=100%|0}}!{{math|size=100%|1}}	size=100%|x}}

and

{| class="wikitable" style="border:none; background:transparent;text-align:center;"

size=100%|y}}

!{{math|size=100%|1}}!{{math|size=100%|0}}

{{math	0}}	{{math	1}}
{{math	0}}	{{math	0}}
y_wedge x!{{math|size=100%|0}}!{{math|size=100%|1}}	size=100%|x}}

then scriptstyle{y nleftarrow x}! means

{| class="wikitable" style="border:none; background:transparent;text-align:center;"

size=100%|y}}

!{{math|size=100%|1}}!{{math|size=100%|0}}

{{math	0}}	{{math	0}}
{{math	0}}	{{math	1}}
scriptstyle{y nleftarrow x}!!{{math|size=100%|0}}!{{math|size=100%|1}}	size=100%|x}}

(Negation)(Inclusive or)(And)(Converse nonimplication){{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 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.{| class="wikitable" style="border:none; background:transparent;text-align:center;"

{| class="wikitable" style="border:none; background:transparent;"| scriptstyle{x^c}!	{{math	6}}	{{math	3}}	{{math	2}}	{{math	1}}
size=100%|x}}! {{math|size=100%|1}}! {{math|size=100%|2}}! {{math|size=100%|3}}! {{math|size=100%|6}}

and

{| class="wikitable" style="border:none; background:transparent;text-align:center;"

size=100%|y}}

!{{math|size=100%|6}}!{{math|size=100%|3}}!{{math|size=100%|2}}!{{math|size=100%|1}}

{{math	6}}	{{math	6}}	{{math	6}}	{{math	6}}
{{math	3}}	{{math	6}}	{{math	3}}	{{math	6}}
{{math	2}}	{{math	2}}	{{math	6}}	{{math	6}}
{{math	1}}	{{math	2}}	{{math	3}}	{{math	6}}
scriptstyle{y_vee x}!!{{math|size=100%|1}}!{{math|size=100%|2}}!{{math|size=100%|3}}!{{math|size=100%|6}}	size=100%|x}}

and

{| class="wikitable" style="border:none; background:transparent;text-align:center;"

size=100%|y}}

!{{math|size=100%|6}}!{{math|size=100%|3}}!{{math|size=100%|2}}!{{math|size=100%|1}}

{{math	1}}	{{math	2}}	{{math	3}}	{{math	6}}
{{math	1}}	{{math	1}}	{{math	3}}	{{math	3}}
{{math	1}}	{{math	2}}	{{math	1}}	{{math	2}}
{{math	1}}	{{math	1}}	{{math	1}}	{{math	1}}
scriptstyle{y_wedge x}!{{math|size=100%|1}}!{{math|size=100%|2}}!{{math|size=100%|3}}!{{math|size=100%|6}}	size=100%|x}}

then scriptstyle{y nleftarrow x}! means

{| class="wikitable" style="border:none; background:transparent;text-align:center;"

size=100%|y}}

!{{math|size=100%|6}}!{{math|size=100%|3}}!{{math|size=100%|2}}!{{math|size=100%|1}}

{{math	1}}	{{math	1}}	{{math	1}}	{{math	1}}
{{math	1}}	{{math	2}}	{{math	1}}	{{math	2}}
{{math	1}}	{{math	1}}	{{math	3}}	{{math	3}}
{{math	1}}	{{math	2}}	{{math	3}}	{{math	6}}
scriptstyle{y nleftarrow x}!!{{math|size=100%|1}}!{{math|size=100%|2}}!{{math|size=100%|3}}!{{math|size=100%|6}}	size=100%|x}}

(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 #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.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}Clearly, it is associative if and only if rp=0.

Non-commutative

• q nleftarrow p=p nleftarrow q if and only if q = p s6. Hence Converse Nonimplication is noncommutative.

Neutral and absorbing elements

• {{math|size=100%|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 s7.

{{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>Definitionscriptstyle{qtilde{leftarrow}p=q'p,}!| s.2#Definition>Definitionscriptstyle{ptilde{leftarrow}q=p'q,}!| s.3| s.1 s.2scriptstyle{qtilde{leftarrow}p=ptilde{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.rightscriptstyle{q=qp+qp',}!| s.8||scriptstyle{q'p=qp',}!|scriptstyle{Rightarrow,}!|scriptstyle{qp+qp'=qp+q'p,}!| s.9| s.8 - regroup common factors||scriptstyle{Rightarrow,}!|scriptstyle{q.(p+p')=(q+q').p,}!| s.10 s.9 - join of complements equals unity||scriptstyle{Rightarrow,}!|scriptstyle{q.1=1.p,}!| s.11| s.10.right - evaluate expression||scriptstyle{Rightarrow,}!|scriptstyle{q=p,}!| s.12| s.8 s.11scriptstyle{q'p=qp' Rightarrow q=p,}!| s.13|scriptstyle{q=p Rightarrow q'p=qp',}!| s.14|s.12 s.13scriptstyle{q=p Leftrightarrow q'p=qp',}!| s.15| s.3 s.14scriptstyle{qtilde{leftarrow}p=ptilde{leftarrow}q Leftrightarrow q=p,}!{{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>Definition|scriptstyle{operatorname{dual}(qtilde{leftarrow}p),}!|scriptstyle{=,}!|scriptstyle{operatorname{dual}(q'p),}!| s.2Duality (mathematics)>dual is +|| scriptstyle{=,}!| scriptstyle{q'+p,}!| s.3Involution (mathematics)>Involution complement|| scriptstyle{=,}!| scriptstyle{(q'+p)'',}!| s.4 s.3.right - De Morgan's laws applied once|| scriptstyle{=,}!| scriptstyle{(qp')',}!| s.5Commutativity> Commutative law|| scriptstyle{=,}!| scriptstyle{(p'q)',}!| s.6| s.5.right|| scriptstyle{=,}!| scriptstyle{(ptilde{leftarrow}q)',}!| s.7| s.6.right|| scriptstyle{=,}!| scriptstyle{pleftarrow q,}!| s.8| s.7.right|| scriptstyle{=,}!| scriptstyle{qrightarrow p,}!| s.9| s.1.left = s.8.rightscriptstyle{operatorname{dual}(qtilde{leftarrow}p)=qrightarrow 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.WEB,weblink A Visual Explanation of SQL Joins, 11 October 2007, 24 March 2013, 15 February 2014,weblink" title="web.archive.org/web/20140215193839weblink">weblink dead,

References

{{Reflist}}

• 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,

External links

{{Logical connectives}}