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 P ↚ Q {\displaystyle P\nleftarrow Q} , or P ⊄ Q {\displaystyle P\not \subset Q} , and is logically equivalent to ¬ ( P ← Q ) {\displaystyle \neg (P\leftarrow Q)} and ¬ P ∧ Q {\displaystyle \neg P\wedge Q} .
Truth table
The truth table of A ↚ B {\displaystyle A\nleftarrow B} .2
| A {\displaystyle A} | B {\displaystyle B} | A ↚ B {\displaystyle A\nleftarrow B} |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | F |
| T | T | F |
Notation
Converse nonimplication is notated p ↚ q {\textstyle p\nleftarrow q} , which is the left arrow from converse implication ( ← {\textstyle \leftarrow } ), negated with a stroke (/).
Alternatives include
- p ⊄ q {\textstyle p\not \subset q} , which combines converse implication's ⊂ {\displaystyle \subset } , negated with a stroke (/).
- p ← ~ q {\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 q ↚ p = q ′ p {\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.
| and |
| and |
| then y ↚ x {\displaystyle \scriptstyle {y\nleftarrow x}\!} means |
| ||||||||||||||||||||||||||||||||||||||||||
| (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 c {\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.
| and |
| and |
| then y ↚ x {\displaystyle \scriptstyle {y\nleftarrow x}\!} means |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (Co-divisor 6) | (Least common multiple) | (Greatest common divisor) | (x's greatest divisor coprime with y) |
Properties
Non-associative
r ↚ ( q ↚ p ) = ( r ↚ q ) ↚ p {\displaystyle r\nleftarrow (q\nleftarrow p)=(r\nleftarrow q)\nleftarrow p} if and only if r p = 0 {\displaystyle rp=0} #s5 (In a two-element Boolean algebra the latter condition is reduced to r = 0 {\displaystyle r=0} or p = 0 {\displaystyle p=0} ). Hence in a nontrivial Boolean algebra Converse Nonimplication is nonassociative. ( r ↚ q ) ↚ p = r ′ q ↚ p (by definition) = ( r ′ q ) ′ p (by definition) = ( r + q ′ ) p (De Morgan's laws) = ( r + r ′ q ′ ) p (Absorption law) = r p + r ′ q ′ p = r p + r ′ ( q ↚ p ) (by definition) = r p + r ↚ ( q ↚ p ) (by definition) {\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 r p = 0 {\displaystyle rp=0} .
Non-commutative
- q ↚ p = p ↚ q {\displaystyle q\nleftarrow p=p\nleftarrow q} if and only if q = p {\displaystyle q=p} #s6. Hence Converse Nonimplication is noncommutative.
Neutral and absorbing elements
- 0 is a left neutral element ( 0 ↚ p = p {\displaystyle 0\nleftarrow p=p} ) and a right absorbing element ( p ↚ 0 = 0 {\displaystyle {p\nleftarrow 0=0}} ).
- 1 ↚ p = 0 {\displaystyle 1\nleftarrow p=0} , p ↚ 1 = p ′ {\displaystyle p\nleftarrow 1=p'} , and p ↚ p = 0 {\displaystyle p\nleftarrow p=0} .
- Implication q → p {\displaystyle q\rightarrow p} is the dual of converse nonimplication q ↚ p {\displaystyle q\nleftarrow p} #s7.
| Converse Nonimplication is noncommutative | ||||
|---|---|---|---|---|
| Step | Make use of | Resulting in | ||
| s.1 | Definition | q ← ~ p = q ′ p {\displaystyle \scriptstyle {q{\tilde {\leftarrow }}p=q'p\,}\!} | ||
| s.2 | Definition | p ← ~ q = p ′ q {\displaystyle \scriptstyle {p{\tilde {\leftarrow }}q=p'q\,}\!} | ||
| s.3 | s.1 s.2 | q ← ~ p = p ← ~ q ⇔ q ′ p = q p ′ {\displaystyle \scriptstyle {q{\tilde {\leftarrow }}p=p{\tilde {\leftarrow }}q\ \Leftrightarrow \ q'p=qp'\,}\!} | ||
| s.4 | q {\displaystyle \scriptstyle {q\,}\!} | = {\displaystyle \scriptstyle {=\,}\!} | q .1 {\displaystyle \scriptstyle {q.1\,}\!} | |
| s.5 | s.4.right - expand Unit element | = {\displaystyle \scriptstyle {=\,}\!} | q . ( p + p ′ ) {\displaystyle \scriptstyle {q.(p+p')\,}\!} | |
| s.6 | s.5.right - evaluate expression | = {\displaystyle \scriptstyle {=\,}\!} | q p + q p ′ {\displaystyle \scriptstyle {qp+qp'\,}\!} | |
| s.7 | s.4.left = s.6.right | q = q p + q p ′ {\displaystyle \scriptstyle {q=qp+qp'\,}\!} | ||
| s.8 | q ′ p = q p ′ {\displaystyle \scriptstyle {q'p=qp'\,}\!} | ⇒ {\displaystyle \scriptstyle {\Rightarrow \,}\!} | q p + q p ′ = q p + q ′ p {\displaystyle \scriptstyle {qp+qp'=qp+q'p\,}\!} | |
| s.9 | s.8 - regroup common factors | ⇒ {\displaystyle \scriptstyle {\Rightarrow \,}\!} | q . ( p + p ′ ) = ( q + q ′ ) . p {\displaystyle \scriptstyle {q.(p+p')=(q+q').p\,}\!} | |
| s.10 | s.9 - join of complements equals unity | ⇒ {\displaystyle \scriptstyle {\Rightarrow \,}\!} | q .1 = 1. p {\displaystyle \scriptstyle {q.1=1.p\,}\!} | |
| s.11 | s.10.right - evaluate expression | ⇒ {\displaystyle \scriptstyle {\Rightarrow \,}\!} | q = p {\displaystyle \scriptstyle {q=p\,}\!} | |
| s.12 | s.8 s.11 | q ′ p = q p ′ ⇒ q = p {\displaystyle \scriptstyle {q'p=qp'\ \Rightarrow \ q=p\,}\!} | ||
| s.13 | q = p ⇒ q ′ p = q p ′ {\displaystyle \scriptstyle {q=p\ \Rightarrow \ q'p=qp'\,}\!} | |||
| s.14 | s.12 s.13 | q = p ⇔ q ′ p = q p ′ {\displaystyle \scriptstyle {q=p\ \Leftrightarrow \ q'p=qp'\,}\!} | ||
| s.15 | s.3 s.14 | q ← ~ p = p ← ~ q ⇔ q = p {\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 | dual ( q ← ~ p ) {\displaystyle \scriptstyle {\operatorname {dual} (q{\tilde {\leftarrow }}p)\,}\!} | = {\displaystyle \scriptstyle {=\,}\!} | dual ( q ′ p ) {\displaystyle \scriptstyle {\operatorname {dual} (q'p)\,}\!} |
| s.2 | s.1.right - .'s dual is + | = {\displaystyle \scriptstyle {=\,}\!} | q ′ + p {\displaystyle \scriptstyle {q'+p\,}\!} | |
| s.3 | s.2.right - Involution complement | = {\displaystyle \scriptstyle {=\,}\!} | ( q ′ + p ) ″ {\displaystyle \scriptstyle {(q'+p)''\,}\!} | |
| s.4 | s.3.right - De Morgan's laws applied once | = {\displaystyle \scriptstyle {=\,}\!} | ( q p ′ ) ′ {\displaystyle \scriptstyle {(qp')'\,}\!} | |
| s.5 | s.4.right - Commutative law | = {\displaystyle \scriptstyle {=\,}\!} | ( p ′ q ) ′ {\displaystyle \scriptstyle {(p'q)'\,}\!} | |
| s.6 | s.5.right | = {\displaystyle \scriptstyle {=\,}\!} | ( p ← ~ q ) ′ {\displaystyle \scriptstyle {(p{\tilde {\leftarrow }}q)'\,}\!} | |
| s.7 | s.6.right | = {\displaystyle \scriptstyle {=\,}\!} | p ← q {\displaystyle \scriptstyle {p\leftarrow q\,}\!} | |
| s.8 | s.7.right | = {\displaystyle \scriptstyle {=\,}\!} | q → p {\displaystyle \scriptstyle {q\rightarrow p\,}\!} | |
| s.9 | s.1.left = s.8.right | dual ( q ← ~ p ) = q → p {\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
- 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
References
Lehtonen, Eero, and Poikonen, J.H. ↩
Knuth 2011, p. 49 - 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. ↩
"A Visual Explanation of SQL Joins". 11 October 2007. Archived from the original on 15 February 2014. Retrieved 24 March 2013. https://web.archive.org/web/20140215193839/http://www.codinghorror.com/blog/2007/10/a-visual-explanation-of-sql-joins.html ↩