Jump to content
Search

Converse nonimplication

From Wikipedia, the free encyclopedia
Venn diagram of {\displaystyle P\nleftarrow Q}
(the red area is true)

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

[edit]

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

[edit]

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

{\displaystyle A}{\displaystyle B}{\displaystyle A\nleftarrow B}
FFF
FTT
TFF
TTF

Notation

[edit]

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

Alternatives include

Properties

[edit]

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

[edit]

Grammatical

[edit]

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

[edit]

Q does not imply P.

Colloquial

[edit]

Not P, but Q.

Boolean algebra

[edit]

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

[edit]

Non-associative

[edit]

{\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

[edit]
  • {\displaystyle q\nleftarrow p=p\nleftarrow q} if and only if {\displaystyle q=p} #s6. Hence converse nonimplication is noncommutative.

Neutral and absorbing elements

[edit]

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

[edit]

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

[edit]
  1. ↑ Lehtonen, Eero, and Poikonen, J.H.
  2. ↑ Knuth 2011, p. 49
  3. ↑ "A Visual Explanation of SQL Joins". 11 October 2007. Archived from the original on 15 February 2014. Retrieved 24 March 2013.
[edit]
  • Wikimedia Commons logo Media related to Converse nonimplication at Wikimedia Commons
Retrieved from "https://en.wikipedia.org/w/index.php?title=Converse_nonimplication&oldid=1335232973"
Converse nonimplication
Add topic
Morty Proxy This is a proxified and sanitized view of the page, visit original site.