Converse nonimplication
In-game article clicks load inline without leaving the challenge.
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}.
| 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
Not P, but Q.
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.
| ∼ x {\textstyle {}\sim x} 1 0 x 0 1 | and | y 1 1 1 0 0 1 y ∨ x {\textstyle y_{\vee }x} 0 1 x | and | y 1 0 1 0 0 0 y ∧ x {\textstyle y_{\wedge }x} 0 1 x | then y ↚ x {\displaystyle \scriptstyle {y\nleftarrow x}\!} means | y 1 0 0 0 0 1 y ↚ x {\displaystyle \scriptstyle {y\nleftarrow x}\!} 0 1 x |
| ∼ x {\textstyle {}\sim x} | 1 | 0 | ||||
| x | 0 | 1 | ||||
| y | ||||||
| 1 | 1 | 1 | ||||
| 0 | 0 | 1 | ||||
| y ∨ x {\textstyle y_{\vee }x} | 0 | 1 | x | |||
| y | ||||||
| 1 | 0 | 1 | ||||
| 0 | 0 | 0 | ||||
| y ∧ x {\textstyle y_{\wedge }x} | 0 | 1 | x | |||
| y | ||||||
| 1 | 0 | 0 | ||||
| 0 | 0 | 1 | ||||
| y ↚ x {\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 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.
| x c {\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 y ∨ x {\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 y ∧ x {\displaystyle \scriptstyle {y_{\wedge }x}} 1 2 3 6 x | then y ↚ x {\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 y ↚ x {\displaystyle \scriptstyle {y\nleftarrow x}\!} 1 2 3 6 x |
| x c {\displaystyle \scriptstyle {x^{c}}\!} | 6 | 3 | 2 | 1 | ||
| x | 1 | 2 | 3 | 6 | ||
| y | ||||||
| 6 | 6 | 6 | 6 | 6 | ||
| 3 | 3 | 6 | 3 | 6 | ||
| 2 | 2 | 2 | 6 | 6 | ||
| 1 | 1 | 2 | 3 | 6 | ||
| y ∨ x {\displaystyle \scriptstyle {y_{\vee }x}\!} | 1 | 2 | 3 | 6 | x | |
| y | ||||||
| 6 | 1 | 2 | 3 | 6 | ||
| 3 | 1 | 1 | 3 | 3 | ||
| 2 | 1 | 2 | 1 | 2 | ||
| 1 | 1 | 1 | 1 | 1 | ||
| y ∧ x {\displaystyle \scriptstyle {y_{\wedge }x}} | 1 | 2 | 3 | 6 | x | |
| y | ||||||
| 6 | 1 | 1 | 1 | 1 | ||
| 3 | 1 | 2 | 1 | 2 | ||
| 2 | 1 | 1 | 3 | 3 | ||
| 1 | 1 | 2 | 3 | 6 | ||
| y ↚ x {\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
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.
- Knuth, Donald E. (2011). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1 (1sted.). Addison-Wesley Professional. ISBN978-0-201-03804-0.
External links
- Media related toConverse nonimplicationat Wikimedia Commons