Jump to content
Wikipedia The Free Encyclopedia

Converse nonimplication

From Wikipedia, the free encyclopedia
Logical connective
Venn diagram of P ↚ Q {\displaystyle P\nleftarrow Q} {\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 P ↚ Q {\displaystyle P\nleftarrow Q} {\displaystyle P\nleftarrow Q}, or P ⊄ Q {\displaystyle P\not \subset Q} {\displaystyle P\not \subset Q}, and is logically equivalent to ¬ ( P ← Q ) {\displaystyle \neg (P\leftarrow Q)} {\displaystyle \neg (P\leftarrow Q)} and ¬ P ∧ Q {\displaystyle \neg P\wedge Q} {\displaystyle \neg P\wedge Q}.

Truth table

[edit ]

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

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

Notation

[edit ]

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

Alternatives include

  • p ⊄ q {\textstyle p\not \subset q} {\textstyle p\not \subset q}, which combines converse implication's ⊂ {\displaystyle \subset } {\displaystyle \subset }, negated with a stroke (/).
  • p ← ~ q {\textstyle p{\tilde {\leftarrow }}q} {\textstyle p{\tilde {\leftarrow }}q}, which combines converse implication's left arrow ( ← {\textstyle \leftarrow } {\textstyle \leftarrow }) with negation's tilde ( ∼ {\textstyle \sim } {\textstyle \sim }).
  • Mpq, in Bocheński notation

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 q ↚ p = q ′ p {\textstyle q\nleftarrow 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 } {\textstyle \sim } as complement operator, ∨ {\textstyle \vee } {\textstyle \vee } as join operator and ∧ {\textstyle \wedge } {\textstyle \wedge } as meet operator, build the Boolean algebra of propositional logic.

∼ x {\textstyle {}\sim x} {\textstyle {}\sim x} 1 0
x 0 1
and
y
1 1 1
0 0 1
y ∨ x {\textstyle y_{\vee }x} {\textstyle y_{\vee }x} 0 1 x
and
y
1 0 1
0 0 0
y ∧ x {\textstyle y_{\wedge }x} {\textstyle y_{\wedge }x} 0 1 x
then y ↚ x {\displaystyle \scriptstyle {y\nleftarrow x}\!} {\displaystyle \scriptstyle {y\nleftarrow x}\!} means
y
1 0 0
0 0 1
y ↚ x {\displaystyle \scriptstyle {y\nleftarrow 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}}\!} {\displaystyle \scriptstyle {^{c}}\!} (co-divisor of 6) as complement operator, ∨ {\displaystyle \scriptstyle {_{\vee }}\!} {\displaystyle \scriptstyle {_{\vee }}\!} (least common multiple) as join operator and ∧ {\displaystyle \scriptstyle {_{\wedge }}\!} {\displaystyle \scriptstyle {_{\wedge }}\!} (greatest common divisor) as meet operator, build a Boolean algebra.

x c {\displaystyle \scriptstyle {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}\!} {\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}} {\displaystyle \scriptstyle {y_{\wedge }x}} 1 2 3 6 x
then y ↚ x {\displaystyle \scriptstyle {y\nleftarrow 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}\!} {\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 ]

r ↚ ( q ↚ p ) = ( r ↚ q ) ↚ p {\displaystyle r\nleftarrow (q\nleftarrow p)=(r\nleftarrow q)\nleftarrow p} {\displaystyle r\nleftarrow (q\nleftarrow p)=(r\nleftarrow q)\nleftarrow p} if and only if r p = 0 {\displaystyle rp=0} {\displaystyle rp=0} #s5 (In a two-element Boolean algebra the latter condition is reduced to r = 0 {\displaystyle r=0} {\displaystyle r=0} or p = 0 {\displaystyle 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}}} {\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} {\displaystyle rp=0}.

Non-commutative

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

Neutral and absorbing elements

[edit ]
  • 0 is a left neutral element ( 0 ↚ p = p {\displaystyle 0\nleftarrow p=p} {\displaystyle 0\nleftarrow p=p}) and a right absorbing element ( p ↚ 0 = 0 {\displaystyle {p\nleftarrow 0=0}} {\displaystyle {p\nleftarrow 0=0}}).
  • 1 ↚ p = 0 {\displaystyle 1\nleftarrow p=0} {\displaystyle 1\nleftarrow p=0}, p ↚ 1 = p ′ {\displaystyle p\nleftarrow 1=p'} {\displaystyle p\nleftarrow 1=p'}, and p ↚ p = 0 {\displaystyle p\nleftarrow p=0} {\displaystyle p\nleftarrow p=0}.
  • Implication q → p {\displaystyle q\rightarrow p} {\displaystyle q\rightarrow p} is the dual of converse nonimplication q ↚ p {\displaystyle q\nleftarrow 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,円}\!} {\displaystyle \scriptstyle {q{\tilde {\leftarrow }}p=q'p,円}\!}
s.2 Definition p ← ~ q = p ′ q {\displaystyle \scriptstyle {p{\tilde {\leftarrow }}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',円}\!} {\displaystyle \scriptstyle {q{\tilde {\leftarrow }}p=p{\tilde {\leftarrow }}q\ \Leftrightarrow \ q'p=qp',円}\!}
s.4 q {\displaystyle \scriptstyle {q,円}\!} {\displaystyle \scriptstyle {q,円}\!} = {\displaystyle \scriptstyle {=,円}\!} {\displaystyle \scriptstyle {=,円}\!} q .1 {\displaystyle \scriptstyle {q.1,円}\!} {\displaystyle \scriptstyle {q.1,円}\!}
s.5 s.4.right - expand Unit element = {\displaystyle \scriptstyle {=,円}\!} {\displaystyle \scriptstyle {=,円}\!} q . ( p + p ′ ) {\displaystyle \scriptstyle {q.(p+p'),円}\!} {\displaystyle \scriptstyle {q.(p+p'),円}\!}
s.6 s.5.right - evaluate expression = {\displaystyle \scriptstyle {=,円}\!} {\displaystyle \scriptstyle {=,円}\!} q p + q p ′ {\displaystyle \scriptstyle {qp+qp',円}\!} {\displaystyle \scriptstyle {qp+qp',円}\!}
s.7 s.4.left = s.6.right q = q p + q p ′ {\displaystyle \scriptstyle {q=qp+qp',円}\!} {\displaystyle \scriptstyle {q=qp+qp',円}\!}
s.8 q ′ p = q p ′ {\displaystyle \scriptstyle {q'p=qp',円}\!} {\displaystyle \scriptstyle {q'p=qp',円}\!} ⇒ {\displaystyle \scriptstyle {\Rightarrow ,円}\!} {\displaystyle \scriptstyle {\Rightarrow ,円}\!} q p + q p ′ = q p + q ′ p {\displaystyle \scriptstyle {qp+qp'=qp+q'p,円}\!} {\displaystyle \scriptstyle {qp+qp'=qp+q'p,円}\!}
s.9 s.8 - regroup common factors ⇒ {\displaystyle \scriptstyle {\Rightarrow ,円}\!} {\displaystyle \scriptstyle {\Rightarrow ,円}\!} q . ( p + p ′ ) = ( q + q ′ ) . p {\displaystyle \scriptstyle {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 ,円}\!} {\displaystyle \scriptstyle {\Rightarrow ,円}\!} q .1 = 1. p {\displaystyle \scriptstyle {q.1=1.p,円}\!} {\displaystyle \scriptstyle {q.1=1.p,円}\!}
s.11 s.10.right - evaluate expression ⇒ {\displaystyle \scriptstyle {\Rightarrow ,円}\!} {\displaystyle \scriptstyle {\Rightarrow ,円}\!} q = p {\displaystyle \scriptstyle {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,円}\!} {\displaystyle \scriptstyle {q'p=qp'\ \Rightarrow \ q=p,円}\!}
s.13 q = p   ⇒   q ′ p = q p ′ {\displaystyle \scriptstyle {q=p\ \Rightarrow \ q'p=qp',円}\!} {\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',円}\!} {\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,円}\!} {\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 {\operatorname {dual} (q{\tilde {\leftarrow }}p),円}\!} = {\displaystyle \scriptstyle {=,円}\!} {\displaystyle \scriptstyle {=,円}\!} dual ⁡ ( q ′ p ) {\displaystyle \scriptstyle {\operatorname {dual} (q'p),円}\!} {\displaystyle \scriptstyle {\operatorname {dual} (q'p),円}\!}
s.2 s.1.right - .'s dual is + = {\displaystyle \scriptstyle {=,円}\!} {\displaystyle \scriptstyle {=,円}\!} q ′ + p {\displaystyle \scriptstyle {q'+p,円}\!} {\displaystyle \scriptstyle {q'+p,円}\!}
s.3 s.2.right - Involution complement = {\displaystyle \scriptstyle {=,円}\!} {\displaystyle \scriptstyle {=,円}\!} ( q ′ + p ) ″ {\displaystyle \scriptstyle {(q'+p)'',円}\!} {\displaystyle \scriptstyle {(q'+p)'',円}\!}
s.4 s.3.right - De Morgan's laws applied once = {\displaystyle \scriptstyle {=,円}\!} {\displaystyle \scriptstyle {=,円}\!} ( q p ′ ) ′ {\displaystyle \scriptstyle {(qp')',円}\!} {\displaystyle \scriptstyle {(qp')',円}\!}
s.5 s.4.right - Commutative law = {\displaystyle \scriptstyle {=,円}\!} {\displaystyle \scriptstyle {=,円}\!} ( p ′ q ) ′ {\displaystyle \scriptstyle {(p'q)',円}\!} {\displaystyle \scriptstyle {(p'q)',円}\!}
s.6 s.5.right = {\displaystyle \scriptstyle {=,円}\!} {\displaystyle \scriptstyle {=,円}\!} ( p ← ~ q ) ′ {\displaystyle \scriptstyle {(p{\tilde {\leftarrow }}q)',円}\!} {\displaystyle \scriptstyle {(p{\tilde {\leftarrow }}q)',円}\!}
s.7 s.6.right = {\displaystyle \scriptstyle {=,円}\!} {\displaystyle \scriptstyle {=,円}\!} p ← q {\displaystyle \scriptstyle {p\leftarrow q,円}\!} {\displaystyle \scriptstyle {p\leftarrow q,円}\!}
s.8 s.7.right = {\displaystyle \scriptstyle {=,円}\!} {\displaystyle \scriptstyle {=,円}\!} q → p {\displaystyle \scriptstyle {q\rightarrow 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,円}\!} {\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 ]

AltStyle によって変換されたページ (->オリジナル) /