Konjunkció (logika)

A matematikai logikában konjunkció (latinul: coniunctio "összekapcsolás, összekötés") vagy más néven logikai és alatt egy olyan kétváltozós logikai műveletet értünk, amelynek a logikai értéke pontosan akkor igaz, ha mind a két operandusának igaz a logikai értéke. Jelben

$A\land B$ igaz akkor és csak akkor, ha $A$ igaz, és $B$ is igaz.

A művelet jele többnyire ∧ , de előfordul ⋅ is. Ez utóbbi a szorzással való kapcsolatára utal.

Kapcsolódó fogalmak:

• A hálókban a legnagyobb alsó korlát.
• Halmazelméletben a metszet művelet.
• A predikátumlogikában az univerzális kvantor.
• A programozásban a rövidzáras és (and).

Jelölés

A konjunkciót rendszerint infix operátor jelöli. A matematikai logikában ∧ , & vagy × ; az elektronikában ⋅ ; programozási nyelvekben &, &&, vagy and. A Jan Łukasiewicz által bevezetett lengyel jelölésben a konjunkció jele K, a lengyel koniunkcja szóból.

Definíció

A p és q ítéletek konjunkcióját a következő igazságtáblázat definiálja:

p	q	∧
igaz	igaz	igaz
igaz	hamis	hamis
hamis	igaz	hamis
hamis	hamis	hamis

ahol $\wedge$ a konjunkció jele.

A konjunkció egységelme az igaz, ami azt jelenti, hogy az és műveletet az igaz elemmel elvégezve visszakapjuk a másik elemet. Így értelmezhető az üres konjunkció, és annak értéke igaz.

Azokban a rendszerekben, ahol a konjunkció nem primitív elem, ott definiálható, mint:

$A\land B=\neg (A\to \neg B)$

vagy

$A\land B=\neg (\neg A\lor \neg B).$

Tulajdonságai

Tetszőleges $A,B,C$ ítéletek esetén teljesülnek a következő állítások:

• A konjunkció idempotens, azaz

$A\wedge A\equiv A$

• A konjunkció kommutatív, azaz

$A\wedge B\equiv B\wedge A$

• A konjunkció asszociatív, azaz

$A\wedge (B\wedge C)\equiv (A\wedge B)\wedge C$

• Igazságőrző, azaz, ha mindkét tényezője igaz, akkor a konjunkció is igaz.
• Hamisságőrző, azaz, ha mindkét tényezője hamis, akkor a konjunkció is hamis.
• A konjunkció disztributív a diszjunkcióra, azaz

$A\wedge (B\vee C)\equiv (A\wedge B)\vee (A\wedge C)$

• A diszjunció disztributív a konjunkcióra, azaz

$A\vee (B\wedge C)\equiv (A\vee B)\wedge (A\vee C)$

• Önmagára és a kizáró vagyra is disztributív.
• A konjunkcióra és a diszjunkcióra teljesülnek az elnyelési tulajdonságok (abszorptivitás), azaz

$A\vee (A\wedge B)\equiv A$, és

$A\wedge (A\vee B)\equiv A$

• A konjunkcióra és a diszjunkcióra teljesülnek a De Morgan azonosságok, azaz

$\neg (A\wedge B)\equiv (\neg A)\vee (\neg B)$, és

$\neg (A\vee B)\equiv (\neg A)\wedge (\neg B)$

• Végül fennáll a dualitás elve, azaz ha felcseréljük a konjunkciót és a diszjunkciót, valamint az igaz és a hamis logikai konstansokat, akkor az állítás igazságértéke megmarad.
• Walsh-spektruma: (1,-1,-1,1)
• Nemlinearitás: 1, ami azt jelenti, hogy annyira különbözik a leneáris és affin függvényektől, amennyire csak lehet.
• Ha az igazat 1, a hamisat 0 jelöli, akkor a konjunkció ugyanaz, mint az aritmetikai szorzás.

Tagadás

Egy $A\land B$ hamissága belátható, ha bizonyítható, hogy $\neg A$ vagy $\neg B$. Jelekkel:

$\neg A\to \neg (A\land B)$

Ez a képlet az

$(A\to C)\to ((A\land B)\to C)$

speciális esetének tekinthető, ahol $C$ hamis.

Ha $A$ implikálja, hogy $\neg B$, akkor $\neg A$ és $A$ esetén is

$(A\to \neg {}B)\to \neg (A\land B)$

Más szavakkal, a konjunkció hamissága belátható akkor is, ha a tényezők igazságtartalma nem ismert, de a köztük levő kapcsolat ismert. Ez a képlet az

$(A\to (B\to C))\to ((A\land B)\to C)$

speciális esetének tekinthető, ahol $C$ hamis.

Venn-diagram

"A és B" Venn-diagramja (a piros rész az igaz rész konjunkció esetén)

Három elem, "A, B és C" konjunkciójának Venn-diagramja (a piros rész az igaz rész konjunkció esetén)

$A\land B\land C$

Bevezetése és kivezetése

A konjunkció bevezetése klasszikusan érvényes, egyszerű érvelési forma. Az érvelésnek két premisszája van, ezeket jelölje A és B. Intuitívan bevezethető a konjunkció:

A,

B.

Tehát A és B.

Logikai operátorokkal:

$A,$

$B$

$\vdash A\land B$

Példa a konjunkció bevezetésére:

Bob szereti az almát.

Bob szereti a narancsot.

Tehát Bob szereti az almát és Bob szereti a narancsot.

A konjunkció kivezetése klasszikusan érvényes, egyszerű érvelési forma. Intuitívan, a konjunkcióból az összes tényező következik:

A és B.

Tehát A.

...vagy alternatívan:

A és B.

Tehát B.

Logikai operátortokkal:

$A\land B$

$\vdash A$

...vagy alternatívan:

$A\land B$

$\vdash B$

A többértékű logikákban

A többértékű logikákban a konjunkciót a permanenciaelv szerint úgy terjesztik ki, hogy minél több tulajdonságát megőrizzék. Ezek közül a legfontosabb az asszociativitás és a kommutativitás. Egy többértékű $T(A,B)$ konjunkciónak ezeknek a tulajdonságoknak kell eleget tennie:

• Kommutativitás: $T(A,B)=T(B,A)$
• Asszociativitás: $T(A,(T(B,C))=T(T(A,B),C)$
• Monotónia: $A>B\Rightarrow T(A,C)\geq T(B,C)$
• Egységelem: $T(1,A)=A$

További értelmes, de nem szükséges tulajdonságok a folytonosság és az idempotencia.

A három értékű logikákban bevezethetők például a következő konjunkciók:

Jan Łukasiewicz Ł3 logikájában (1920) a konjunkció kiterjesztése a minimumfüggvény:

$A$	$B$	$A\land B$
1	1	1
1	0,5	0,5
1	0	0
0,5	1	0,5
0,5	0,5	0,5
0,5	0	0
0	1	0
0	0,5	0
0	0	0

Dimitri Analtoljewitsch Bočvar (1938) B3 logikájában:

$A$	$B$	$A\land B$
1	1	1
1	0,5	0,5
1	0	0
0,5	1	0,5
0,5	0,5	0,5
0,5	0	0,5
0	1	0
0	0,5	0,5
0	0	0

Halmazelméleti megfelelő

A halmazelméleti metszetbe való tartozás logikai éssel fogalmazható meg: x ∈ A ∩ B akkor és csak akkor, ha (x ∈ A) ∧ (x ∈ B). E megfeleltetés alapján a metszet több tulajdonságban is osztozik a logikai konjunkcióval, mint az asszociativitás, kommutativitás és idempotencia.

Természetes nyelv

Az emberi nyelvek logikája nem teljesen feleltethető meg a matematikai logikának. Nincs ez másként az éssel sem.

A logikai konjunkció nem fedi le teljesen az és szó használatát, mivel az kifejezhet időbeli sorrendet is. Például az Összeházasodtak és gyerekük született. mondatot úgy szokás értelmezni, hogy a házasság megelőzte a gyerek születését.

Egy harmadik jelentés szerint az egyes tulajdonságoknak az alany részei felelnek meg. Például Az amerikai zászló piros, kék és fehér. mondat azt fejezi ki, hogy az egyes részek színe piros, fehér vagy kék, és nem az egész zászló bír egyszerre a három színnel.

Kapcsolódó szócikkek

• Diszjunkció
• De Morgan-azonosságok
• Logikai kapu

Források

• Szendrei Ágnes: Diszkrét matematika Logika algebra kombinatorika, Polygon, Szeged (1994)
• https://web.archive.org/web/20050222113037/http://www.inf.u-szeged.hu/oktatas/Tempus/logika.doc
• Hazewinkel, Michiel, ed. (2001) [1994], "Conjunction", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
• Wolfram MathWorld: Conjunction
• Property and truth table of AND propositions. [2000. május 6-i dátummal az eredetiből archiválva].

Fordítás

Ez a szócikk részben vagy egészben a Logical conjunction című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.