Converse nonimplication

Converse nonimplication

In logic, converse nonimplication is a logical connective which is the negation of the converse of implication.

Contents

Definition

_{p\not\subset q}\! which is the same as _{\sim(p\subset q)}\!

Truth table

The truth table of _{p\not\subset q}\!.

p q _{\not\subset}\!
T T F
T F F
F T T
F F F

Venn diagram

The Venn Diagram of "It is not the case that B implies A" (the red area is true)

Venn0010.svg

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

Symbol

Alternatives for _{p\not\subset q}\! are

  • _{p\tilde{\leftarrow}q}\!: _{\tilde{\leftarrow}}\! combines Converse implication's left arrow(_{\leftarrow}\!) with Negation's tilde(_{\sim}\!).
  • _{Mpq}\!: uses prefixed capital letter.
  • _{p\nleftarrow q}\!: _{\nleftarrow }\! combines Converse implication's left arrow(_{\leftarrow}\!) denied by means of a stroke(_{/}\!).

Natural language

Grammatical

Rhetorical

"not...but"

Colloquial

Boolean algebra

  • Converse Nonimplication in a general Boolean algebra[1] [2] is defined as _{q\tilde{\leftarrow}p=q'p}\! [3][4].
  • _{r\tilde{\leftarrow}(q\tilde{\leftarrow}p)=(r\tilde{\leftarrow}q)\tilde{\leftarrow}p}\! iff _{rp=0}\! [5] (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.
  • _{q\tilde{\leftarrow}p=p\tilde{\leftarrow}q\,}\! iff _{q=p\,}\! [6]. Hence Converse Nonimplication is noncommutative.
  • _{0}\! is a left neutral element (_{0\tilde{\leftarrow}p=p}\!) and a right absorbing element (_{p\tilde{\leftarrow}0=0}\!).
  • _{1\tilde{\leftarrow}p=0}\!, _{p\tilde{\leftarrow}1=p'}\!, and _{p\tilde{\leftarrow}p=0}\!.
  • Implication _{q \rightarrow p}\! is the dual of Converse Nonimplication _{q\tilde{\leftarrow}p}\! [7].

[1]

General Boolean Algebra Operators (ordered by decreasing precedence)
Symbol Meaning Operand(s)
_{'}\! unary complement operator postfix (after operand)
_{.}\! or omitted binary meet operator infix (in between operands)
_{+}\! binary join operator infix (in between operands)
_{\tilde{\leftarrow}}\! binary Converse Nonimplication operator infix (in between operands)

[2]

General Boolean Constants
Symbol Meaning
_{0}\! zero element
_{1}\! unit element

[3] 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.

_{\sim x}\! _{1}\! _{0}\!
_{x}\! _{0}\! _{1}\!
and
_{y}\!
_{1}\! _{1}\! _{1}\!
_{0}\! _{0}\! _{1}\!
_{y_\vee x}\! _{0}\! _{1}\! _{x}\!
and
_{y}\!
_{1}\! _{0}\! _{1}\!
_{0}\! _{0}\! _{0}\!
_{y_\wedge x}\! _{0}\! _{1}\! _{x}\!
then _{y\tilde{\leftarrow}x}\! means
_{y}\!
_{1}\! _{0}\! _{0}\!
_{0}\! _{0}\! _{1}\!
_{y\tilde{\leftarrow}x}\! _{0}\! _{1}\! _{x}\!
(Negation) (Inclusive Or) (And) (Converse Nonimplication)

[4] 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}}\! (codivisor of 6) as complement operator, _{_\vee}\! (least common multiple) as join operator and _{_\wedge}\! (greatest common divisor) as meet operator, build a Boolean algebra.

_{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_\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_\wedge x}\! _{1}\! _{2}\! _{3}\! _{6}\! _{x}\!
then _{y\tilde{\leftarrow}x}\! means
_{y}\!
_{6}\! _{1}\! _{1}\! _{1}\! _{1}\!
_{3}\! _{1}\! _{2}\! _{1}\! _{2}\!
_{2}\! _{1}\! _{1}\! _{3}\! _{3}\!
_{1}\! _{1}\! _{2}\! _{3}\! _{6}\!
_{y\tilde{\leftarrow}x}\! _{1}\! _{2}\! _{3}\! _{6}\! _{x}\!
(Codivisor 6) (Least Common Multiple) (Greatest Common Divisor) (x's greatest Divisor coprime with y)

[5]

Converse Nonimplication is nonassociative
Step Make use of Resulting in
_{s.1 \,}\! Definition _{r\tilde{\leftarrow}q\,}\! _{=\,}\! _{r'q\,}\!
_{s.2 \,}\! _{(s.2)\tilde{\leftarrow}p \,}\! _{(r\tilde{\leftarrow}q)\tilde{\leftarrow}p\,}\! _{=\,}\! _{r'q\tilde{\leftarrow}p\,}\!
_{s.3 \,}\! Definition applied on _{s.2.right\,}\! _{=\,}\! _{(r'q)'p\,}\!
_{s.4 \,}\! De Morgan's laws applied on _{s.3.right \,}\! _{=\,}\! _{(r+q')p\,}\!
_{s.5 \,}\! Distributivity applied _{s.4.right \,}\! _{=\,}\! _{rp+q'p\,}\!
_{s.6 \,}\! _{s.5.right\,}\! - insert Unit element _{=\,}\! _{r.1.p+1.q'p\,}\!
_{s.7 \,}\! _{s.6.right\,}\! - expand Unit element _{=\,}\! _{r(q+q')p+(r+r')q'p\,}\!
_{s.8 \,}\! _{s.7.right\,}\! - expand expressions in brackets _{=\,}\! _{rqp+rq'p+rq'p+r'q'p\,}\!
_{s.9 \,}\! ignore one of two equal terms in _{s.8.right\,}\! (Idempotence) _{=\,}\! _{rqp+rq'p+r'q'p\,}\!
_{s.10 \,}\! _{s.9.right \,}\! - regroup common factors _{=\,}\! _{r(q+q')p+r'q'p\,}\!
_{s.11 \,}\! _{s.10.right \,}\! - join of complements equals unity _{=\,}\! _{r.1.p+r'q'p\,}\!
_{s.12 \,}\! _{s.11.right \,}\! - evaluate expression _{=\,}\! _{rp+r'q'p\,}\!
_{s.13 \,}\! _{s.2.left=s.12.right \,}\! _{(r\tilde{\leftarrow}q)\tilde{\leftarrow}p=rp+r'q'p\,}\!
_{s.14 \,}\! Definition _{q\tilde{\leftarrow}p\,}\! _{=\,}\! _{q'p\,}\!
_{s.15 \,}\! _{r\tilde{\leftarrow}(s.14) \,}\! _{r\tilde{\leftarrow}(q\tilde{\leftarrow}p)\,}\! _{=\,}\! _{r\tilde{\leftarrow}(q'p)\,}\!
_{s.16 \,}\! Definition applied on _{s.15.right\,}\! _{=\,}\! _{r'q'p\,}\!
_{s.17 \,}\! _{s.15.left=s.16.right \,}\! _{r\tilde{\leftarrow}(q\tilde{\leftarrow}p)=r'q'p\,}\!
_{s.18 \,}\! _{s.13\ s.17\,}\! _{(r\tilde{\leftarrow}q)\tilde{\leftarrow}p=r\tilde{\leftarrow}(q\tilde{\leftarrow}p)\,}\! _{\Rightarrow\,}\! _{rp+r'q'p=r'q'p\,}\!
_{s.19 \,}\! _{(s.18).(rp)\,}\! _{\Rightarrow\,}\! _{(rp).(rp)+(r'q'p).(rp)=(r'q'p).(rp)\,}\!
_{s.20 \,}\! _{s.19.right\,}\! - evaluate expression _{\Rightarrow\,}\! _{rp+0=0\,}\!
_{s.21 \,}\! _{s.20.right\,}\! - evaluate expression _{\Rightarrow\,}\! _{rp=0\,}\!
_{s.22 \,}\! _{s.18.left\ \Rightarrow\ s.21.right \,}\! _{(r\tilde{\leftarrow}q)\tilde{\leftarrow}p=r\tilde{\leftarrow}(q\tilde{\leftarrow}p)\ \Rightarrow\ rp=0\,}\!
_{s.23 \,}\! _{s.13 \,}\! _{rp=0\ \Rightarrow\ (r\tilde{\leftarrow}q)\tilde{\leftarrow}p=r'q'p\,}\!
_{s.24 \,}\! _{s.17\ s.23 \,}\! _{rp=0\ \Rightarrow\ (r\tilde{\leftarrow}q)\tilde{\leftarrow}p=r\tilde{\leftarrow}(q\tilde{\leftarrow}p)\,}\!
_{s.25 \,}\! _{s.22\ s.24 \,}\! _{(r\tilde{\leftarrow}q)\tilde{\leftarrow}p=r\tilde{\leftarrow}(q\tilde{\leftarrow}p)\ \Leftrightarrow\ rp=0\,}\!

[6]

Converse Nonimplication is noncommutative
Step Make use of Resulting in
_{s.1 \,}\! Definition _{q\tilde{\leftarrow}p=q'p\,}\!
_{s.2 \,}\! Definition _{p\tilde{\leftarrow}q=p'q\,}\!
_{s.3 \,}\! _{s.1\ s.2 \,}\! _{q\tilde{\leftarrow}p=p\tilde{\leftarrow}q\ \Leftrightarrow\ q'p=qp'\,}\!
_{s.4 \,}\! _{q\,}\! _{=\,}\! _{q.1\,}\!
_{s.5 \,}\! _{s.4.right\,}\! - expand Unit element _{=\,}\! _{q.(p+p')\,}\!
_{s.6 \,}\! _{s.5.right\,}\! - evaluate expression _{=\,}\! _{qp+qp'\,}\!
_{s.7 \,}\! _{s.4.left=s.6.right \,}\! _{q=qp+qp'\,}\!
_{s.8 \,}\! _{q'p=qp'\,}\! _{\Rightarrow\,}\! _{qp+qp'=qp+q'p\,}\!
_{s.9 \,}\! _{s.8 \,}\! - regroup common factors _{\Rightarrow\,}\! _{q.(p+p')=(q+q').p\,}\!
_{s.10 \,}\! _{s.9 \,}\! - join of complements equals unity _{\Rightarrow\,}\! _{q.1=1.p\,}\!
_{s.11 \,}\! _{s.10.right \,}\! - evaluate expression _{\Rightarrow\,}\! _{q=p\,}\!
_{s.12 \,}\! _{s.8\ s.11\,}\! _{q'p=qp'\ \Rightarrow\ q=p\,}\!
_{s.13 \,}\! _{q=p\ \Rightarrow\ q'p=qp'\,}\!
_{s.14 \,}\! _{s.12\ s.13 \,}\! _{q=p\ \Leftrightarrow\ q'p=qp'\,}\!
_{s.15 \,}\! _{s.3\ s.14 \,}\! _{q\tilde{\leftarrow}p=p\tilde{\leftarrow}q\ \Leftrightarrow\ q=p\,}\!

[7]

Implication is the dual of Converse Nonimplication
Step Make use of Resulting in
_{s.1 \,}\! Definition _{dual(q\tilde{\leftarrow}p)\,}\! _{=\,}\! _{dual(q'p)\,}\!
_{s.2 \,}\! _{s.1.right\,}\! - .'s dual is + _{=\,}\! _{q'+p\,}\!
_{s.3 \,}\! _{s.2.right\,}\! - Involution complement _{=\,}\! _{(q'+p)''\,}\!
_{s.4 \,}\! _{s.3.right\,}\! - De Morgan's laws applied once _{=\,}\! _{(qp')'\,}\!
_{s.5 \,}\! _{s.4.right\,}\! - Commutative law _{=\,}\! _{(p'q)'\,}\!
_{s.6 \,}\! _{s.5.right\,}\! _{=\,}\! _{(p\tilde{\leftarrow}q)'\,}\!
_{s.7 \,}\! _{s.6.right\,}\! _{=\,}\! _{p\leftarrow q\,}\!
_{s.8 \,}\! _{s.7.right\,}\! _{=\,}\! _{q\rightarrow p\,}\!
_{s.9 \,}\! _{s.1.left=s.8.right \,}\! _{dual(q\tilde{\leftarrow}p)=q\rightarrow p\,}\!

Computer science

See also