Converse nonimplication

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

Definition

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

Truth table

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

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)

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

Natural language

Rhetorical

"not A but B"

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.

_{\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 \nleftarrow x}\! means
_{y}\!
_{1}\! _{0}\! _{0}\!
_{0}\! _{0}\! _{1}\!
_{y \nleftarrow 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 \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 \nleftarrow x}\! _{1}\! _{2}\! _{3}\! _{6}\! _{x}\!
(Codivisor 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}\! 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.

::\begin{align} (r \nleftarrow q) \nleftarrow p &= r'q \nleftarrow p \qquad \qquad \qquad ~~~~ \text{(by definition)} \\ &= (r'q)'p \qquad \qquad \qquad ~~~~~~ \text{(by definition)} \\ &= (r + q')p \qquad \qquad ~~~~~~~~~ \text{(De Morgan's laws)} \\ &= (r + r'q')p \qquad \qquad ~~~~~~~ \text{(Absorption law)} \\ &= rp + r'q'p \\ &= rp + r'(q \nleftarrow p) \qquad ~~~~~~~~ \text{(by definition)} \\ &= rp + r \nleftarrow (q \nleftarrow p) \qquad ~~~~ \text{(by definition)} \\ \end{align}

Clearly, it is associative iff _{rp=0}\!.

Non-commutative

  • _{q \nleftarrow p=p \nleftarrow q\,}\! iff _{q=p\,}\! [6]. Hence Converse Nonimplication is noncommutative.

Neutral and absorbing elements

[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

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]

Notes

  1. ↑ Lehtonen, Eero, and Poikonen, J.H.
  2. ↑ Knuth 2011, p. 49
  3. ↑ http://www.codinghorror.com/blog/2007/10/a-visual-explanation-of-sql-joins.html

References

This article is issued from Wikipedia - version of the Thursday, October 01, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.