Koniunkcja (matematyka)

AND

Koniunkcja to zdanie złożone mające postać p i q , gdzie p, q są zdaniami. W rachunku zadań koniunkcję zapisuje się symbolicznie jako:
. Przez koniunkcję rozumie się też zdanie mające postać p(1) i ... i p(n). Koniunkcję można zdefiniować precyzyjniej jako dwuargumentowe działanie określone w zbiorze zdań, które zdaniom p, q przyporządkowuje zdanie p i q

Działanie to pozostaje w ścisłym związku z działaniem mnożenia zbiorów (patrz algebra zbiorów). Dlatego zdanie utworzone z innych zdań za pomocą koniunkcji jest też nazywane iloczynem logicznym. Koniunkcję zdań uznaje się za prawdziwą wtedy i tylko wtedy, gdy oba zdania p, q są prawdziwe.

Symbol koniunkcji jako bramki logicznej:

Tablica prawdy (1 oznacza zdanie prawdziwe 0 zaś zdanie fałszywe):

0	0	0
0	1	0
1	0	0
1	1	1

Koniunkcja jest operacją dwuargumentową, i charakteryzuje się następującymi cechami:

• przemienność

• łączność

Do onaczenia koniunkcji stosowany jest także angielski spójnik AND.

Przykłady

• Koniunkcja zdań 2+2=4 i 3+1=5 jest fałszywa.

• Koniunkcja zdań 2+2=4 i 3+1=4 jest prawdziwa.

Alternatywa -OR

Alternatywa to zdanie złożone mające postać p lub q, gdzie p i q są zdaniami. W rachunku zdań dla alternatywy stosowany jest zapis
. Przez alternatywę rozumie się też zdanie mające postać p(1) lub p(2) lub ... lub p(n). Alternatywę można zdefiniować bardziej formalnie jako dwuargumentowe działanie określone w zbiorze zdań, które zdaniom p, q przyporządkowuje zdanie p lub q.

Działanie to pozostaje w ścisłym związku z dodawaniem zbiorów (patrz algebra zbiorów). Dlatego zdanie utworzone z innych zdań przy użyciu alternatywy jest też nazywane sumą logiczną. Alternatywa jest prawdziwa, jeżeli którekolwiek z jej zdań składowych jest prawdziwe. W przeciwnym razie alternatywa zdań jest fałszywa.

Symbol alternatywy jako bramki logicznej:

Tablica prawdy dla alternatywy (0 oznacza zdanie fałszywe, 1 - zdanie prawdziwe):

p	q	p v q
0	0	0
0	1	1
1	0	1
1	1	1

Alternatywa jest:

• przemienna

• łączna

W językach programowania dla oznaczenia alternatywy używany jest często angielski spójnik OR.

Przykłady

• Alternatywa zdań: 12 dzieli się przez 3 lub Madryt jest stolicą Hiszpanii jest prawdziwa, bo oba jej zdania składowe są prawdziwe.

• Alternatywa zdań: 10 > 12 lub 10 < 11 jest prawdziwa, bo prawdą jest, że 10 jest liczbą mniejszą niż 11.

Alternatywa wykluczająca

XOR

Alternatywa wykluczająca, inaczej alternatywa rozłączna, XOR, kontrawalencja, różnica symetryczna to w logice jeden ze spójników zdaniowych. Alternatywa wykluczająca zdań
jest prawdziwa tylko wtedy, gdy dokładnie jedno ze zdań p bądź q jest prawdziwe.

Symbol alternatywy wykluczającej jako bramki logicznej:

Tablica prawdy alternatywy wykluczającej:

p	q
0	0	0
0	1	1
1	0	1
1	1	0

Informatyka

W informatyce operację alternatywy wykluczającej stosuje się do par liczb naturalnych wykonując operacje na cyfrach zapisów binarnych tych liczb. Np.:

7 ^ 5 =      (w językach C/C++ alternatywę wykluczającą oznaczamy za pomocą symbolu ^)

= 0000111₂ ^ 00000101₂ =   (liczby w systemie binarnym)

= 0000010₂ =    (efekt operacji na kolejnych cyfrach)

= 2     (wynik w postaci dziesiętnej)

Własności

• Operacja XOR jest przemienna:

Negacja

NOT

Negacja (inaczej zaprzeczenie) to zdanie mające postać nieprawda, że p, gdzie p jest zdaniem. W rachunku zdań negacja zapisywana jest jako:
(lub
). Negację można zdefiniować ściślej jako jednoargumentowe działanie określone w zbiorze zdań, które każdemu zdaniu p przyporządkowuje zdanie nieprawda, że p. Negację zdania p uważa się za prawdziwą, gdy zdanie p jest fałszywe, zaś za fałszywą, gdy zdanie p jest prawdziwe.

Symbol negacji jako bramki logicznej:

Tablica prawdy (1 oznacza zdanie prawdziwe zaś 0 fałszywe):

p	¬ p
0	1
1	0

Do oznaczenia negacji stosowana jest także angielska partykuła NOT

NAND

NAND

NAND - funkcja boolowska realizująca zaprzeczoną koniunkcję (NOT AND) - jej wartością jest fałsz wtedy i tylko wtedy, gdy wartością obu argumentów jest prawda.

NAND jest zanegowaną koniunkcją (stąd nazwa)

a NAND b = NOT (a AND b)

NAND jest również równoważna alternatywie logicznej negacji

a NAND b = (NOT a) OR (NOT b)

Symbol zaprzeczenia koniunkcji jako bramki logicznej:

Tablica prawdy:

A	B	A nand B
0	0	1
0	1	1
1	0	1
1	1	0

Za pomocą funkcji NAND możemy zdefiniować negację:

NOT a = a NAND a

koniunkcję:

a AND b = NOT( a NAND b) = ( a NAND b) NAND ( a NAND b )

alternatywę:

a OR b = ( NOT a ) NAND ( NOT b ) = ( a NAND a ) NAND ( b NAND b )

czyli za pomocą operacji NAND możemy zdefiniować dowolną funkcję logiczną. Dlatego jest ona ważna (podobnie jak NOR)

---