W tej części kursu dowiesz się, z czego składa się język KRZ.
Przypomnijmy sobie na chwilę Excel. W Excelu dane są przechowywane w postaci tabelek i na tych danych można operować za pomocą formuł. Tak na przykład wyrażenia =SUMA(A2:A10), =JEŻELI(C2="Tak";1;2) są dla Excela zrozumiałe - są to sensowne komendy, które Excel "rozumie" i wykonuje w związku z tym operacje zadane przez te wyrażenia. Gdy natomiast wprowadzimy wyrażenie =SUMA(A2="Tak"), Excel go nie "zrozumie" (i wyda sygnał "Błąd!"), ponieważ to wyrażenie jest dla niego bezsensowne, czyli takie, któremu nie odpowiada żadna komenda. Podobnie gdy wprowadzimy wyrażenie =MAMA(A2:A10), Excel go nie "zrozumie" (i wyda sygnał "Błąd!"), ponieważ wyrazu MAMA nie ma w języku Excel - nie odpowiada temu wyrazowi żadna operacja, którą Excel jest w stanie wykonać.
Czyli, by ciąg wyrazów był dla Excela "zrozumiały" - tworzył poprawną formułę napisaną w jego języku - każdy pojedynczy wyraz w tym ciągu musi należeć do alfabetu języka ORAZ wyrażenia w ciągu muszą być ułożone zgodnie z regułami budowy wyrażeń w tym języku (czyli mieć poprawną składnię). Dlatego
=MAMA(A2:A10) nie jest formułą Excel, ponieważ wyrażenie "MAMA" nie należy do jego alfabetu;
=SUMA(A2="Tak") nie jest formułą Excel, ponieważ jest niepoprawnie zbudowane (niezgodnie z regułami składni Excel).
Dokładnie tak samo jest w KRZ (oraz w dowolnym innym formalnym języku): język KRZ posiada swój alfabet (zestaw symboli, które są używane do budowania formuł) oraz reguły budowania formuł (wyrażeń, które dla KRZ są sensowne).
Wyobraźmy sobie, że mamy złośliwego programistę. Napisał on mały program, który dodaje nazwy komórek jako nowe argumenty do =SUMA(A1, A2) w następujący sposób: bierze ostatni argument (na przykład A2), zwiększa w nim liczbę o 1 (powstaje A3) i dopisuje nowy argument do formuły (powstaje =SUMA(A1, A2, A3)). Jasne, że gdyby ten program został uruchomiony, to pisanie formuły =SUMA(A1, A2, [...]) nigdy by się nie skończyło (zawsze byłby ostatni argument, jego liczbę da się zwiększyć o 1, ten nowy argument byłby ostatni, jego liczbę da się zwiększyć o jeden itd). Dlatego ważne, by budowane wyrażenie (z dozwolonych symboli i zgodnie z regułami budowy) było skończone - dopiero wtedy stanowi formułę.
Alfabet KRZ składa się z następujących symboli:
p, q, r, s, p1, q1, r1, s1, ... | zmienne zdaniowe
→ , ∧ , ∨ , ↔, ¬ | spójniki
), ( | nawiasy
Jak widać z punktu 1, alfabet KRZ jest nieskończony, dzięki czemu nigdy nie zabraknie symboli na oznaczenie pojedynczych zdań.
Uwaga: zamiast znaku negacji ¬ można używać znaku negacji ∼ (tyle że konsekwentnie). Wszędzie w testach na tej stronie proszę używać znaku negacji ¬ .
zmienne zdaniowe są formułami;
jeśli α, β są formułami, to formułami również są:
(α)∧(β)
(α)∨(β)
(α)→(β)
(α)↔(β)
¬(α)
nic więcej nie jest uważane za formułę KRZ.
Litery greckie "α" i "β" są użyte w tej definicji jako zmienne, za które można podstawić dowolną formułę KRZ. W taki sposób:
Formuła KRZ - dowolny skończony ciąg symboli alfabetu KRZ zbudowany według reguł budowy 1 i 2.
Zauważmy, że formuły zawsze są zbudowane w taki sposób, że jest jednoznacznie jasne, że zawierają tylko jeden główny spójnik (czyli taki, który nie występuje w argumencie żadnego innego spójnika w tej formule i symbolizuje operację, która jest wykonywana jako ostatnia). Formuły nazywamy według ich głównego spójnika (czyli koniunkcja, alternatywa, implikacja, równoważność, negacja). W implikacji formułę po lewej nazywamy poprzednikiem, formułę po prawej następnikiem. Formuły po obu stronach koniunkcji, alternatywy oraz równoważności nazywamy ich członami.
Ugadujemy się: kiedy chcemy połączyć formuły, w których występują spójniki ∨, →, ∧, ↔ , to te formuły bierzemy w nawiasy. Natomiast pojedyncze zmienne bądź negacje pojedynczych zmiennych nie będziemy brać w nawiasy. Czyli zamiast:
(p)∧(q) będziemy pisali po prostu p∧q;
¬(p)∧(q) będziemy pisali po prostu ¬p∧q;
¬(p) będziemy pisali po prostu ¬p
¬(¬(p)) będziemy pisali po prostu ¬¬p
(p)∧((q)→(r)) będziemy pisali po prostu p∧(q→r)
Również nawiasy będziemy opuszczać, kiedy jest jasne, że negacje dotyczą tej samej formuły, czyli zamiast
¬(¬(p∨q)) będziemy pisali po prostu ¬¬(p∨q)
Używanie nawiasów jest bardzo podobne do tego, co miałeś na matematyce. Załóżmy, że nie wiemy, że dzielenie i mnożenie jest wykonywane najpierw (w pierwszej kolejności, niż dodawanie czy odejmowanie). By zaznaczyć, którą operację należy wykonać jako pierwszą, użylibyśmy nawiasów. W KRZ jest podobnie.
📌Znak negacji ¬ nie łączy formuł (w odróżnieniu od matematycznego znaku "minus"); ciąg znaków taki jak p¬q nie jest formułą.
pojedyncze literki p, q, r, s ... są formułami;
jeśli α i β są pojedynczymi literkami p, q, r, s ... bądź zanegowanymi pojedynczymi literkami ¬p, ¬q, ¬r, ¬s ..., a ⋆ to dowolny spójnik →, ∨, ∧, ↔, to formułami również są α⋆β, ¬α; ¬(α⋆β);
jeśli ¬α jest formułą, to ¬¬α jest formułą;
jeśli ⋆ to dowolny spójnik →, ∨, ∧, ↔ , a α i β są formułami, to (α)⋆(β) jest formułą;
jeśli ⋆ to dowolny spójnik →, ∨, ∧, ↔ , a (α)⋆(β) jest formułą, to ¬((α)⋆(β)) jest formułą.
Pojedynczych literek p, q, r, s ..., zanegowanych pojedynczych literek ¬p, ¬q, ¬r, ¬s ..., zanegowanych zanegowanych pojedynczych literek ¬¬p, ... itp nie bierzemy w nawiasy.
Zmienne zdaniowe:
Dowolna pojedyncza zmienna (np. p, q, r, ...) jest formułą.
2. Spójniki logiczne:
Formuły mogą być połączone spójnikami: ∧ (i), ∨ (lub), → (implikacja), ↔ (równoważność).
3. Negacja:
Negacja może być stosowana do dowolnej formuły i oznaczana jako ¬(α), przy czym nawiasy można opuszczać przy prostych przypadkach, np. ¬p jest formułą.
Podwójna negacja ¬¬p również jest dozwolona.
4. Złożone formuły:
Jeśli α i β są formułami, to wyrażenia typu:
α∧β,
α∨β,
α→β,
α↔β
są również formułami. Tutaj możemy pominąć nawiasy wokół zmiennych zdaniowych lub ich prostych negacji, ale nawiasy muszą być stosowane w bardziej złożonych przypadkach.
5. Złożone negacje:
Negacje spójników, np. ¬(p∨q), są formułami, a jeśli negacja dotyczy złożonej formuły, nie można opuszczać nawiasów.
6. Reguły nawiasowania:
Nawiasy wokół złożonych formuł (tj. tych połączonych spójnikami) są wymagane, aby zapewnić jednoznaczność.
Przykłady:
p→q: Jest formułą (zmienne połączone spójnikiem, bez zbędnych nawiasów).
¬p∨q: Jest formułą (negacja zmiennej p i spójnik ∨ z q).
¬(p∨q): Jest formułą (negacja złożonej formuły p ∨ q, wymaga nawiasów).
p∧(q→r): Jest formułą (poprawne użycie nawiasów przy spójniku →).
¬(p∨(q→r)): Jest formułą (negacja złożonej formuły z poprawnym nawiasowaniem).
p∧¬(q∨r): Jest formułą (spójnik ∧ łączy zmienną p i negację formuły q∨r).
Przykłady niepoprawnych formuł:
p∧q∨r: Nie jest formułą, bo brakuje nawiasów jednoznacznie określających kolejność działań (powinno być np. (p∧q)∨r lub p∧(q∨r)).
p→→q: Nie jest formułą, ponieważ spójnik → wymaga dwóch formuł po stronie lewej i prawej, a ani p→, ani →q nie są formułami;
¬p q: Nie jest formułą, ponieważ nie ma żadnego spójnika łączącego p i q.
Do pisania formuł możesz użyć darmowego narzędzia bądź po prostu kopiować wygenerowane formuły i wstawiać do pól
Przykłady
p→q formuła;
q1426549987 formuła (jest to pojedyncza zmienna zdaniowa);
¬(p∧q) formuła (głównym spójnikiem jest negacja);
¬¬¬p formuła (pojedyncza zmienna jest formułą, negacja formuły jest formułą);
p¬(q→p) NIE formuła, ponieważ znak negacji nie może łączyć formuł;
¬¬¬p∧q formuła (po lewej stronie koniunkcji formuła i po prawej stronie koniunkcji formuła; głównym spójnikiem jest koniunkcja);
¬¬¬p∧q→r NIE formuła (wieloznaczny zapis, nie wiadomo, który spójnik jest główny - czy jest nim koniunkcja, czy implikacja);
(p∧q)? NIE formuła (znak ? nie należy do alfabetu KRZ)
p→q...p→q NIE formuła (wielokropek nie należy do alfabetu KRZ).
Uwaga: w formule jest zawsze tyle samo otwartych nawiasów, ile zamkniętych.