Converse nonimplication - Converse nonimplication

Venn-diagram över (det röda området är sant)

{\ displaystyle P \ nleftarrow Q}

I logik är konverserad icke-implikation ett logiskt bindemedel som är negationen av konversation (likvärdigt negationen av konversationen av implikationen ).

Definition

Converse nonimplication noteras , eller , och är logiskt sett ekvivalent med ${\ displaystyle P \ nleftarrow Q}$ ${\ displaystyle P \ not \ subset Q}$ ${\ displaystyle \ neg (P \ leftarrow Q)}$

Sanningstabellen

Den sanningstabell för . ${\ displaystyle P \ nleftarrow Q}$

${\ displaystyle P}$	${\ displaystyle Q}$	${\ displaystyle P \ nleftarrow Q}$
T	T	F
T	F	F
F	T	T
F	F	F

Notation

Converse nonimplication noteras , vilket är den vänstra pilen från converse implication ( ), negerad med en stroke ( $/$ ). ${\ textstyle p \ nleftarrow q}$ ${\ textstyle \ leftarrow}$

Alternativ inkluderar

${\ textstyle p \ not \ subset q}$ , som kombinerar motsatta implikationer , negerade med en stroke ( $/$ ). ${\ displaystyle \ subset}$
${\ textstyle p {\ tilde {\ leftarrow}} q}$ , som kombinerar den omvända implikationens vänsterpil ( ) med negationens tilde ( ). ${\ textstyle \ leftarrow}$ ${\ textstyle \ sim}$
M pq , i Bocheński-notation

Egenskaper

falskhetsbevarande : tolkningen under vilken alla variabler tilldelas ett sanningsvärde "falskt" ger ett sanningsvärde på "falskt" som ett resultat av konverserad icke-implikation

Naturligt språk

Grammatisk

"p från q."

Klassisk passiv aggressiv: "ja, nej"

Retorisk

"inte A utan B"

Vardaglig

Boolesk algebra

Converse Nonimplication i en allmän boolesk algebra definieras som . ${\ textstyle q \ nleftarrow p = q'p}$

Exempel på en boolesk algebra med två element: de 2 elementen {0,1} med 0 som noll och 1 som enhetselement, operatorer som komplementoperator, som anslutningsoperator och som mötesoperator, bygger den booleska algebra av propositionell logik . ${\ textstyle \ sim}$ ${\ textstyle \ vee}$ ${\ textstyle \ wedge}$

${\ textstyle {} \ sim x}$	$1$	$0$
$x$	$0$	$1$

och

$y$
$1$	$1$	$1$
$0$	$0$	$1$
${\ textstyle y _ {\ vee} x}$	$0$	$1$	$x$

och

$y$
$1$	$0$	$1$
$0$	$0$	$0$
${\ textstyle y _ {\ wedge} x}$	$0$	$1$	$x$

sedan medel

{\ displaystyle \ scriptstyle {y \ nleftarrow x} \!}

$y$
$1$	$0$	$0$
$0$	$0$	$1$
${\ displaystyle \ scriptstyle {y \ nleftarrow x} \!}$	$0$	$1$	$x$

(Negation)

(Inklusive eller)

(Och)

(Converse nonimplication)

Exempel på en 4-element boolesk algebra: de fyra delarna {1,2,3,6} av 6 med 1 som noll och 6 som enhetselement, operatorer (koddelare av 6) som komplementoperator, (minst vanlig multipel) som sammanfogning operatör och (största gemensamma delare) som mötesoperatör, bygg en boolsk algebra. ${\ displaystyle \ scriptstyle {^ {c}} \!}$ ${\ displaystyle \ scriptstyle {_ {\ vee}} \!}$ ${\ displaystyle \ scriptstyle {_ {\ wedge}} \!}$

${\ displaystyle \ scriptstyle {x ^ {c}} \!}$	$6$	$3$	$2$	$1$
$x$	$1$	$2$	$3$	$6$

och

$y$
$6$	$6$	$6$	$6$	$6$
$3$	$3$	$6$	$3$	$6$
$2$	$2$	$2$	$6$	$6$
$1$	$1$	$2$	$3$	$6$
${\ displaystyle \ scriptstyle {y _ {\ vee} x} \!}$	$1$	$2$	$3$	$6$	$x$

och

$y$
$6$	$1$	$2$	$3$	$6$
$3$	$1$	$1$	$3$	$3$
$2$	$1$	$2$	$1$	$2$
$1$	$1$	$1$	$1$	$1$
${\ displaystyle \ scriptstyle {y _ {\ wedge} x}}$	$1$	$2$	$3$	$6$	$x$

sedan medel

{\ displaystyle \ scriptstyle {y \ nleftarrow x} \!}

$y$
$6$	$1$	$1$	$1$	$1$
$3$	$1$	$2$	$1$	$2$
$2$	$1$	$1$	$3$	$3$
$1$	$1$	$2$	$3$	$6$
${\ displaystyle \ scriptstyle {y \ nleftarrow x} \!}$	$1$	$2$	$3$	$6$	$x$

(Codivisor 6)

(Minsta gemensamma nämnare)

(Största gemensamma delaren)

(x största delare coprime med y)

Egenskaper

Icke-associativ

${\ displaystyle r \ nleftarrow (q \ nleftarrow p) = (r \ nleftarrow q) \ nleftarrow p}$ om och bara om # s5 (I en boolesk algebra med två element reduceras det senare villkoret till eller ). I en icke-privat boolesk algebra är Converse Nonimplication därför icke associerande . ${\ displaystyle rp = 0}$ ${\ displaystyle r = 0}$ ${\ displaystyle p = 0}$

{\ displaystyle {\ begin {align} (r \ nleftarrow q) \ nleftarrow p & = r'q \ nleftarrow p & {\ text {(per definition)}} \\ & = (r'q) 'p & {\ text { (per definition)}} \\ & = (r + q ') p & {\ text {(De Morgans lagar)}} \\ & = (r + r'q') p & {\ text {(Absorptionslag)} } \\ & = rp + r'q'p \\ & = rp + r '(q \ nleftarrow p) & {\ text {(per definition)}} \\ & = rp + r \ nleftarrow (q \ nleftarrow p) och {\ text {(per definition)}} \\\ slut {justerad}}}

Det är uppenbart att det är associerande om och bara om . ${\ displaystyle rp = 0}$

Icke-kommutativ

${\ displaystyle q \ nleftarrow p = p \ nleftarrow q}$ om och bara om # s6 . Därför är Converse nonimplication icke-kommutativ . ${\ displaystyle q = p}$

Neutrala och absorberande element

$0$ är ett vänster neutralt element ( ) och ett höger absorberande element ( ). ${\ displaystyle 0 \ nleftarrow p = p}$ ${\ displaystyle {p \ nleftarrow 0 = 0}}$
${\ displaystyle 1 \ nleftarrow p = 0}$ , , Och . ${\ displaystyle p \ nleftarrow 1 = p '}$ ${\ displaystyle p \ nleftarrow p = 0}$
Implikation är det dubbla av konverserad icke-implicering # s7 . ${\ displaystyle q \ rightarrow p}$ ${\ displaystyle q \ nleftarrow p}$

Converse Nonimplication är icke-kommutativ
Steg	Använda	Resulterar i
s.1	Definition	${\ displaystyle \ scriptstyle {q {\ tilde {\ leftarrow}} p = q'p \,} \!}$
s.2	Definition	${\ displaystyle \ scriptstyle {p {\ tilde {\ leftarrow}} q = p'q \,} \!}$
s.3	s.1 s.2	${\ displaystyle \ scriptstyle {q {\ tilde {\ leftarrow}} p = p {\ tilde {\ leftarrow}} q \ \ Leftrightarrow \ q'p = qp '\,} \!}$
s.4		${\ displaystyle \ scriptstyle {q \,} \!}$	${\ displaystyle \ scriptstyle {= \,} \!}$	${\ displaystyle \ scriptstyle {q.1 \,} \!}$
s.5	s.4.höger - expandera Enhetselement		${\ displaystyle \ scriptstyle {= \,} \!}$	${\ displaystyle \ scriptstyle {q. (p + p ') \,} \!}$
s.6	s.5.right - utvärdera uttryck		${\ displaystyle \ scriptstyle {= \,} \!}$	${\ displaystyle \ scriptstyle {qp + qp '\,} \!}$
s.7	s.4.vänster = s.6.höger	${\ displaystyle \ scriptstyle {q = qp + qp '\,} \!}$
s.8		${\ displaystyle \ scriptstyle {q'p = qp '\,} \!}$	${\ displaystyle \ scriptstyle {\ Rightarrow \,} \!}$	${\ displaystyle \ scriptstyle {qp + qp '= qp + q'p \,} \!}$
s.9	s.8 - gruppera om vanliga faktorer		${\ displaystyle \ scriptstyle {\ Rightarrow \,} \!}$	${\ displaystyle \ scriptstyle {q. (p + p ') = (q + q'). p \,} \!}$
s.10	s.9 - anslutning av komplement är lika med enhet		${\ displaystyle \ scriptstyle {\ Rightarrow \,} \!}$	${\ displaystyle \ scriptstyle {q.1 = 1.p \,} \!}$
s.11	s.10.right - utvärdera uttryck		${\ displaystyle \ scriptstyle {\ Rightarrow \,} \!}$	${\ displaystyle \ scriptstyle {q = p \,} \!}$
s.12	s.8 s.11	${\ displaystyle \ scriptstyle {q'p = qp '\ \ Rightarrow \ q = p \,} \!}$
s.13		${\ displaystyle \ scriptstyle {q = p \ \ Rightarrow \ q'p = qp '\,} \!}$
s.14	s.12 s.13	${\ displaystyle \ scriptstyle {q = p \ \ Leftrightarrow \ q'p = qp '\,} \!}$
s.15	s.3 s.14	${\ displaystyle \ scriptstyle {q {\ tilde {\ leftarrow}} p = p {\ tilde {\ leftarrow}} q \ \ Leftrightarrow \ q = p \,} \!}$

Implikation är det dubbla av Converse Nonimplication
Steg	Använda	Resulterar i
s.1	Definition	${\ displaystyle \ scriptstyle {\ operatorname {dual} (q {\ tilde {\ leftarrow}} p) \,} \!}$	${\ displaystyle \ scriptstyle {= \,} \!}$	${\ displaystyle \ scriptstyle {\ operatorname {dual} (q'p) \,} \!}$
s.2	s.1.right - .s dubbla är +		${\ displaystyle \ scriptstyle {= \,} \!}$	${\ displaystyle \ scriptstyle {q '+ p \,} \!}$
s.3	s.2.right - Involution komplement		${\ displaystyle \ scriptstyle {= \,} \!}$	${\ displaystyle \ scriptstyle {(q '+ p)' '\,} \!}$
s.4	s.3.right - De Morgans lagar tillämpades en gång		${\ displaystyle \ scriptstyle {= \,} \!}$	${\ displaystyle \ scriptstyle {(qp ')' \,} \!}$
s.5	s.4.right - Kommutativ lag		${\ displaystyle \ scriptstyle {= \,} \!}$	${\ displaystyle \ scriptstyle {(p'q) '\,} \!}$
s.6	s.5.höger		${\ displaystyle \ scriptstyle {= \,} \!}$	${\ displaystyle \ scriptstyle {(p {\ tilde {\ leftarrow}} q) '\,} \!}$
s.7	s.6. rätt		${\ displaystyle \ scriptstyle {= \,} \!}$	${\ displaystyle \ scriptstyle {p \ leftarrow q \,} \!}$
s.8	s.7. rätt		${\ displaystyle \ scriptstyle {= \,} \!}$	${\ displaystyle \ scriptstyle {q \ rightarrow p \,} \!}$
s.9	s.1.vänster = s.8.höger	${\ displaystyle \ scriptstyle {\ operatorname {dual} (q {\ tilde {\ leftarrow}} p) = q \ rightarrow p \,} \!}$

Datavetenskap

Ett exempel för konverserad icke-implikation inom datavetenskap kan hittas när du utför en yttre sammanfogning till höger på en uppsättning tabeller från en databas , om poster som inte matchar kopplingsvillkoret från "vänster" -tabellen utesluts.

Referenser

Knuth, Donald E. (2011). The Computer of Computer Programming , Volume 4A: Combinatorial Algorithms, Part 1 (1st ed.). Addison-Wesley Professional. ISBN 978-0-201-03804-0.

externa länkar

Media relaterade till Converse nonimplication på Wikimedia Commons

Languages

In other projects

Converse nonimplication - Converse nonimplication

Innehåll

Definition

Sanningstabellen

Notation

Egenskaper

Naturligt språk

Grammatisk

Retorisk

Vardaglig

Boolesk algebra

Egenskaper

Icke-associativ

Icke-kommutativ

Neutrala och absorberande element

Datavetenskap

Referenser

externa länkar