Artykuł został opublikowany także na portalu JustPasteIt (dawniej Eioba).
Wersja z 2019-05-13

Związki logiczne

4

Związki wielu zdań

Gdy rozpatrujemy więcej niż dwa zdania połączone spójnikami koniunkcji i alternatywy, wartość logiczna całości jest możliwa do ustalenia, gdyż związki te są łączne. Jest również zgodna z intuicją. Dlatego też łańcuchowe zapisy p ∧ q ∧ r oraz p ∨ q ∨ r można uznać za jednoznaczne. Takich trójargumentowych koniunkcji i alternatyw nie rozpatruje się w logice klasycznej, jednak w elektronice bramki logiczne And i Or posiadające 3 wejścia (lub więcej) są rzeczą normalną. Możemy więc podać następujące, uogólnione definicji tych dwóch funkcji:

• koniunkcją nazywamy funkcję logiczną, która jest prawdziwa wtedy i tylko wtedy, gdy każdy z jej argumentów jest prawdziwy,
• alternatywą nazywamy funkcję logiczną, która jest prawdziwa wtedy i tylko wtedy, gdy choć jeden z jej argumentów jest prawdziwy (nie wszystkie są fałszywe).

Dla zapisu tego rodzaju funkcji (o dowolnej ilości argumentów, byle tylko większej niż 1) można stosować notację ∧(p,q,r, …) oraz ∨(p,q,r, …), ewentualnie And(p,q,r, …) oraz Or(p,q,r, …). Możemy nawet pominąć nawiasy i przecinki: Andpqr, Orpqr. Tego rodzaju zapis zwany jest notacją polską. Możemy naturalnie umówić się, że np. zamiast And zastosujemy literę K (od Koniunkcja), a zamiast Or literę A (od Alternatywa). Notacja polska dla funkcji dwóch argumentów przyjmie wówczas postać Kpq, Apq, dla trzech argumentów Kpqr, Apqr, itd. W programie Mathematica dla koniunkcji stosuje się notację p ∧ q ∧ r lub p && q && r lub też And [p, q, r], natomiast dla alternatywy notację p ∨ q ∨ r lub p || q || r lub też Or [p, q, r].

Żaden z dwóch zapisów (p ↓ q) ↓ r oraz p ↓ (q ↓ r) (oznaczających każdy co innego) nie odpowiada zdaniu ani… ani… ani… w języku naturalnym, które rozumiane jest jako zaprzeczenie alternatywy: ~(p ∨ q ∨ r) czyli (na mocy drugiego prawa de Morgana) jako koniunkcja zaprzeczeń: ~p ∧ ~q ∧ ~r. Podobnie żaden z dwóch zapisów (p | q) | r oraz p | (q | r) nie odpowiada zdaniu bądź… bądź… bądź… w języku naturalnym, które rozumiane jest jako zaprzeczenie koniunkcji: ~(p ∧ q ∧ r) czyli (na mocy pierwszego prawa de Morgana) jako alternatywa zaprzeczeń: ~p ∨ ~q ∨ ~r. Opierając się na właściwościach języka naturalnego i na praktyce w elektronice możemy więc podać uogólnione definicje dwóch kolejnych funkcji logicznych o dowolnej ilości argumentów (większej niż 1):

• negacją łączną nazywamy funkcję logiczną, która jest prawdziwa wtedy i tylko wtedy, gdy wszystkie jej argumenty są fałszywe,
• dysjunkcją nazywamy funkcję logiczną, która jest prawdziwa wtedy i tylko wtedy, gdy choć jeden z jej argumentów jest fałszywy (nie wszystkie są prawdziwe).

Znaczenie zapisów typu p ↓ q ↓ r, czy p | q | r nie jest więc wcale oczywiste, może być rozumiane rozmaicie, i dlatego powinno się go unikać. Należy zwrócić na to szczególną uwagę, aby uniknąć nieporozumień i dwuznaczności. Dla zapisu tego rodzaju funkcji wygodnie jest natomiast stosować notację ↓(p,q,r, …) oraz |(p,q,r, …), ewentualnie Nor(p,q,r, …) oraz Nand(p,q,r, …), lub krócej Norpqr, Nandpqr. Zamiast Nor możemy zastosować literę B, gdyż jest to jedynie kwestią umowy, podobnie jak stosowanie D zamiast Nand. W programie Mathematica dla negacji łącznej stosuje się notację p ⊽ q ⊽ r lub Nor [p, q, r], natomiast dla dysjunkcji notację p ⊼ q ⊼ r lub Nand [p, q, r]. Zauważmy, że rozszerzenie znaczenia terminu „binegacja” byłoby niesłuszne (łac. bis = dwa razy). Binegacja jest zatem szczególnym przypadkiem negacji łącznej, gdy liczba argumentów wynosi dwa.

Jeszcze większe problemy stwarzają alternatywa wykluczająca oraz równoważność. Związek (p ⇔ q) ⇔ r wykazuje nader ciekawe właściwości, gdyż jest łączny, tj. równoważny związkowi p ⇔ (q ⇔ r), ale jest także równoważny związkom (p ⊻ q) ⊻ r oraz p ⊻ (q ⊻ r). Jest on prawdziwy wówczas, gdy wszystkie trzy zdania składowe są prawdziwe. Jednak w przeciwieństwie do zwykłej równoważności, nie jest on prawdziwy, gdy wszystkie zdania są fałszywe. Jest za to prawdziwy, gdy dokładnie jedno z trzech zdań jest prawdziwe (a dwa pozostałe fałszywe). Mimo łączności, równoważność trzech zdań nie wykazuje właściwości oczekiwanych intuicyjnie, dlatego zapisu typu p ⇔ q ⇔ r (częstego nawet w logice, mimo deklaracji o rozpatrywaniu wyłącznie dwuargumentowych związków logicznych) nie należy w żadnym wypadku utożsamiać z zapisem (p ⇔ q) ⇔ r. Zapis p ⇔ q ⇔ r jest w rzeczywistości tożsamy koniunkcji dwóch równoważności (p ⇔ q) ∧ (q ⇔ r). Trzecia równoważność p ⇔ r jest w takim wypadku oczywista i wynika z omówionej niżej własności przechodniości.

Symbol ≡ informuje, że wyrażenia po obu jego stronach mają tę samą wartość logiczną. Znak równoważności natomiast o tym nie informuje, równoważność bowiem nie musi być prawdziwa. Zapis p ⇔ q ⇔ r może rodzić wątpliwości, ponieważ oceniamy jego wartość logiczną. Natomiast wartości logicznej zapisu p ≡ q ≡ r nie analizujemy.

Podobnie jak w przypadku równoważności, żaden z zapisów (p ⊻ q) ⊻ r oraz p ⊻ (q ⊻ r) nie odpowiada zdaniu albo… albo… albo…, rozumianemu jako wystąpienie dokładnie jednej możliwości z podanych trzech. W języku logiki zdanie takie należałoby zapisać w postaci dość skomplikowanej formuły ((p ⊻ q) ⊻ r) ⊻ ((p ∧ q) ∧ r), lub też w postaci nieco prostszej, lecz mniej regularnej: ((p ⊻ q) ⊻ r) ⊻ (q | r). Nie ma przeszkody, aby uogólnić definicję równoważności, jednak uogólnienie alternatywy rozłącznej na funkcje wiele argumentów rodzi szereg problemów i wiele możliwych rozwiązań. Rozwiązanie zastosowane w programie Mathematica zostanie przedstawione niżej; na razie ograniczymy się do podania określeń 5 następujących funkcji dowolnej ilości argumentów (większej niż 1):

• równoważnością nazywamy funkcję logiczną, która jest prawdziwa wtedy i tylko wtedy, gdy wszystkie jej argumenty mają tę samą wartość logiczną, a więc gdy wszystkie są prawdziwe lub wszystkie fałszywe,
• nierównoważnością nazywamy funkcję logiczną, która jest prawdziwa wtedy i tylko wtedy, gdy nie wszystkie jej argumenty mają tę samą wartość logiczną,
• alternatywą rozłączną (ekskluzją) nazywamy funkcję logiczną, która jest prawdziwa wtedy i tylko wtedy, gdy dokładnie jeden jej argument ma przeciwną wartość logiczną niż pozostałe (dokładnie jeden jest prawdziwy lub dokładnie jeden jest fałszywy),
• alternatywą rozłączną ze względu na prawdę nazywamy funkcję logiczną, która jest prawdziwa wtedy i tylko wtedy, gdy dokładnie jeden jej argument jest prawdziwy, a pozostałe są fałszywe,
• alternatywą rozłączną ze względu na fałsz nazywamy funkcję logiczną, która jest prawdziwa wtedy i tylko wtedy, gdy dokładnie jeden jej argument jest fałszywy, a pozostałe są prawdziwe.

Dla wyrażenia równoważności można użyć zapisu ⇔(p,q,r, …), choć w praktyce przeważa zapis łańcuchowy p ⇔ q ⇔ r. Dla wyrażenia nierównoważności właściwy będzie zapis ↮(p,q,r, …). W ogólnym przypadku nie będzie on równoważny zapisowi ⊻(p,q,r, …), oznaczającemu alternatywę rozłączną; zgodnie z podanymi definicjami alternatywa rozłączna i nierównoważność oznaczają ten sam związek, gdy liczba argumentów nie przekracza 3.

Dla określenia wartości logicznej równoważności wielu argumentów możemy posłużyć się właściwością tego związku, na mocy której (⇔(p,q,r, …)) ≡ ((p ∧ q ∧ r…) ∨ (~p ∧ ~q ∧ ~r…)). Nierównoważność można przedstawić analogicznie, korzystając z praw de Morgana: (↮(p,q,r, …)) ≡ ((p ∨ q ∨ r…) ∧ (~p ∨ ~q ∨ ~r…)).

Dziewięć wymienionych powyżej funkcji zebrano w tabeli:

Nierównoważność oznacza, że nie wszystkie argumenty mają tę samą wartość, to znaczy niektóre są prawdziwe, a niektóre fałszywe. Można też stwierdzić, że tylko niektóre argumenty nierównoważności są prawdziwe, można wreszcie stwierdzić że tylko niektóre argumenty są fałszywe. Nierównoważność jest „silniejszą postacią” alternatywy: alternatywa jest prawdziwa, gdy niektóre argumenty są prawdziwe (a więc także wtedy, gdy prawdziwe są wszystkie argumenty), natomiast nierównoważność jest prawdziwa, gdy tylko niektóre argumenty są prawdziwe. Podobnie nierównoważność jest „silniejszą postacią” dysjunkcji: dysjunkcja jest prawdziwa, gdy niektóre argumenty są fałszywe (a więc także wtedy, gdy fałszywe są wszystkie argumenty), natomiast nierównoważność jest prawdziwa, gdy tylko niektóre argumenty są fałszywe.

Wartości logiczne argumentów mogą wyrażać cyfry 1 i 0 użyte zamiast symboli p, q, r itd. Wówczas zapis (1,0,1) oznacza trzy argumenty p, q, r, z których p jest prawdziwe, q fałszywe, r prawdziwe, a zapis (0,1,1,0) cztery argumenty p, q, r, s, z których tylko q i r są prawdziwe. W poniższej tabeli zebrano wszystkie układy wartości logicznych 2, 3 i 4 argumentów, dla których podane funkcje są prawdziwe bądź fałszywe; każdy inny układ zmienia wartość logiczną funkcji na przeciwną.

Dalsze funkcje logiczne

Zauważmy, że wartości rozpatrywanych w tym rozdziale funkcji nie zależą od tego, który konkretnie argument jest prawdziwy, a który fałszywy, a jedynie od ilości argumentów o określonej wartości logicznej.

Dla funkcji dwóch argumentów można sporządzić następującą tabelę:

Podane w tabeli cyfry oznaczają ilość argumentów prawdziwych konieczną, aby funkcja przybrała wartość logiczną podaną w nagłówku. Na przykład dysjunkcja jest prawdziwa, gdy żadne ze zdań nie jest prawdziwe (0) lub gdy prawdziwe jest jedno zdanie (1), stąd zapis 0, 1. Jednocześnie dysjunkcja jest fałszywa wówczas, gdy oba zdania są prawdziwe, stąd zapis 2 w odpowiedniej komórce tabeli.

Ostatnia kolumna tabeli zawiera sformułowania w języku naturalnym odpowiadające danej funkcji logicznej. Zauważmy, że sformułowanie „istnieją” obejmuje także wypadek „wszystkie”, co w omawianym wypadku znaczy „oba”.

Już przy trzech argumentach pojawiają się nowe funkcje. Poniższa tabela obejmuje tylko najciekawsze z nich.

I tutaj cyfry oznaczają ilość argumentów prawdziwych konieczną, aby funkcja była odpowiednio prawdziwa lub fałszywa. Pozostałe objaśnienia:

• Funkcje oraz ich negacje zestawiono w kolejnych wierszach (np. dysjunkcja jest negacją koniunkcji, negacja łączna jest negacją alternatywy itd.).
• Brak zwykłej ekskluzji (⊻), gdyż w wypadku 3 argumentów ma ona te same własności, co nierównoważność (↮).
• Symbol ⊻_T oznacza ekskluzję ze względu na prawdę, którą zdefiniowano wyżej
• Analogicznie symbol ⊻_F oznacza ekskluzję ze względu na fałsz.
• Symbole ¬⊻_T oraz ¬⊻_F oznaczają negacje obu rodzajów ekskluzji.
• Oznaczenia ψ_T oraz ψ_F wprowadzono na potrzeby tej witryny.

Zauważmy, że w określeniach funkcji obok pojęć „wszystkie” oraz „istnieją” pojawiają się też pojęcia „jeden” („dokładnie jeden”) oraz „co najwyżej jeden”. Logika trzech argumentów rozpatruje więc wypadki:

• „żaden” (0),
• „co najwyżej jeden” (0 lub 1),
• „jeden” (1),
• „nie wszystkie” (0, 1 lub 2),
• „istnieją” (1, 2 lub 3),
• „kilka” (2 lub 3),
• „wszystkie” (3).

Widać też, że określenie „istnieją” znaczy to samo, co „co najmniej jeden”. Takie sformułowanie jest bardziej zrozumiałe w języku naturalnym, choć unikane przez logików. Można też używać mniej ścisłego określenia „pewne”. Z kolei sformułowanie „kilka” oznacza to samo, co „więcej niż jeden”, i obejmuje także przypadek „wszystkie”.

Przy czterech argumentach pojawiają się kolejne funkcje, co ilustruje poniższa tabela.

W przypadku 4 argumentów zwykła ekskluzja (⊻) i nierównoważność (↮) oznaczają różne funkcje, jak zdefiniowano wyżej. Oznaczenia ψ_T, ψ_F, χ_T oraz χ_F wprowadzono na potrzeby tej witryny.

Logika czterech argumentów rozpatruje wypadki:

• „żaden” (0),
• „co najwyżej jeden” (0 lub 1),
• „jeden” (1),
• „tylko niektóre” (1, 2 lub 3),
• „nie wszystkie” (0, 1, 2 lub 3),
• „pewne” = „niektóre” = „co najmniej jeden” (1, 2, 3 lub 4),
• „tylko kilka” (2 lub 3),
• „kilka” = „więcej niż jeden” (2, 3 lub 4),
• „wszystkie” (4).

Szczególne znaczenie pojęcia „jeden” wynika z próby uogólnienia alternatywy rozłącznej, zdefiniowanej dla dwóch argumentów. Związek ten można jednak uogólnić i na inne sposoby. Szczególnie często definiuje się alternatywę modulo 2, która znajduje zastosowanie np. w elektronice. Używa się jej także w programie Mathematica, stosując notację p ⊻ q ⊻ r lub Xor [p, q, r]. Funkcja ta zwraca logiczną wartość prawdy, jeśli prawdziwa jest nieparzysta ilość argumentów, podczas gdy reszta jest fałszywa. Jeśli natomiast prawdziwa jest parzysta ilość argumentów, funkcja Xor zwraca logiczną wartość fałszu. Dzięki takiej definicji jest funkcją przemienną i łączną. Łatwo sprawdzić, że np. Xor [Xor [p, q], r] oznacza to samo co p ⊻ q ⊻ r.

Wszystkie omówione dotąd związki są przemienne (symetryczne). Implikacji dla trzech i większej ilości argumentów zwykle nie definiuje się. Mimo to można umówić się, że związek logiczny o postaci (p ⇒ (q ∧ r…) będziemy uważać za implikację o wielu argumentach; pierwszy argument jest poprzednikiem, pozostałe następnikami. Koniunkcja odpowiednich implikacji tego typu zachowuje jedną z podstawowych właściwości tego związku, tj. ma taką samą wartość logiczną jak równoważność. Np. (p ⇒ (q ∧ r)) ∧ (q ⇒ (p ∧ r)) ∧ (r ⇒ (p ∧ q)) ≡ (⇔(p,q,r)).