Konwersja Arka 2

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

{tw}{Twierdzenie}[section] {fa}[tw]{Fakt} {AZbioruPustego}{Aksjomat Zbioru Pustego} {APary}{Aksjomat Pary} {ASumy}{Aksjomat Sumy}

{}{0pt} {}{0pt} {}{0in} {}{-0.5in} {}{6.3in} {}{9in}

{cwicz}[section] {obra}[section] {hint}

{thm}{Twierdzenie}[section] {defn}[thm]{Definicja}

{Zadanie}[thm]{Zadanie} {Uwaga}[thm]{Uwaga} {Przykład}[thm]{Przykład} {Rozwiązanie}[thm]{Rozwiązanie} {Hint}[thm]{Hint}

{equation}{section}

{kuba_preamble1} {kuba_preamble2}

Wprowadzenie

Logika zdaniowa jest językiem, który pozwala opisywać zależności pomiędzy zdaniami. Przykładem może być zdanie:

Jeśli n jest liczbą pierwszą to n jest liczbą nieparzystą lub n jest równe 2.

W powyższym zdaniu spójniki "'jeśli"' [..] "'to"', "'lub"' mówią o związkach które zachodzą pomiędzy zdaniami:

  1. "n jest liczbą pierwszą,"
  1. "n jest liczbą nieparzystą,"
  1. "n jest równe 2."

Oznaczmy powyższe zdania przez (w takiej właśnie kolejności). Używając symboli, które zwyczajowo odpowiadają potocznemu rozumieniu spójników Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textbf{jeśli} [..] \textbf{to}, \textbf{lub}} oraz powyższych oznaczeń otrzymamy formułę

Jeśli powyższą formułę uznamy za prawdziwą to może nam ona posłużyć do otrzymania nowych wniosków. Na przykład jeśli o jakiejś liczbie n będziemy wiedzieć, że jest liczbą pierwszą oraz, że nie jest nieparzysta to klasyczny rachunek zdań pozwoli nam formalnie wywnioskować fakt że liczba n jest równa 2. Podsumowując, jeśli uznamy za prawdziwe następujące zdania:

  1. ,
  1. ,
  1. (przez oznaczamy negację)

to zgodnie z klasycznym rachunkiem (może lepiej z intuicją?) zdań powinniśmy uznać za prawdziwe zdanie , czyli "n jest równe 2". Powyższy schemat wnioskowania można również opisać formułą

W powyższej formule spójnik symbol odpowiada spójnikowi "'i"' (oraz).

Dzięki rachunkowi zdań możemy precyzyjnie opisywać schematy wnioskowania i zdania złożone oraz oceniać ich prawdziwość.

Język logiki zdaniowej

Zaczniemy od definicji języka logiki zdaniowej. Składa się on z formuł zdefiniowanych następująco: {formuła logiki zdaniowej}

  1. zmienna zdaniowa jest formułą (zmienne zdaniowy oznaczamy

zwykle literami alfabetu rzymskiego np. )

  1. jeśli oraz są formułami to jest formułą (spójnik nazywamy implikacją)
  1. jeśli jest formułą to jest formułą

(spójnik nazywamy negacją)

  1. nic innego nie jest formułą.

Powyższa definicja mówi, że formułami nazywamy te napisy które dają się skonstruować ze zmiennych zdaniowych przy pomocy spójników oraz .

Zgodnie z powyższą definicją nie jest formułą napis , gdyż brakuje w nim nawiasów. Pomimo, iż poprawnie powinniśmy napisać możemy przyjąć że nie będzie konieczne pisanie nawiasów, jeśli nawiasy można jednoznacznie uzupełnić.

ład Poniższe napisy nie są formułami

  • "ten napis na pewno nie jest formułą"

Poniższe napisy są formułami

ład

Ćwiczenie [Uzupelnij]

Rozmiarem formuły nazwiemy ilość występujących w niej spójników. Na przykład formuła ma rozmiar 2, a formuła ma rozmiar 1. Przypuśćmy, że jedyną zmienną zdaniową jaką wolno nam użyć jest . Ile można skonstruować rożnych formuł o rozmiarze 3?

Solution.
Oznaczmy przez liczbę formuł o rozmiarze (czyli liczbę

formuł w których jest spójników). Interesuje nas . Każda formuła o rozmiarze 3 powstaje albo z dwóch formuł o rozmiarach 1 poprzez połączenie ich spójnikiem albo z jednej formuły o rozmiarze 2 poprzez dodanie do niej spójnika . Co więcej każda taka formuła powstaje tylko w jeden sposób. Wynika stąd następująca zależność:

Wiemy, że są tylko dwie formuły o rozmiarze 1, są to oraz . Stąd mamy . Dla formuł o rozmiarze 2 możemy zauważyć podobną zależność. Każda taka formuła jest albo zbudowana z dwóch formuł z których jedna (niekoniecznie pierwsza) ma rozmiar 1 a druga 0 za pomocą , albo jest zbudowana z formuły o rozmiarze 1 za pomocą negacji. Zauważmy też, że istnieje formuła o rozmiarze 0, jest to . Mamy więc następujący wzór dla

Z dwóch ostatnich wzorów otrzymujemy

Skoro jest ich niewiele to możemy wszystkie wypisać

Język logiki zdaniowej można równoważnie zdefiniować nie używając nawiasów za pomocą Odwrotnej Notacji Polskiej Odwrotna Notacja Polska.

Aksjomatyka Klasycznego Rachunku Zdań

Podobnie jak nie wszystkie zdania języka naturalnego mają sens, nie wszystkie formuły opisują prawdziwe schematy wnioskowania, lub zdania które bylibyśmy skłonni uznać za prawdziwe. W tym rozdziale skupimy się na tym które spośród wszystkich formuł zdaniowych wyróżnić jako prawdziwe.

Aksjomaty

Wielu matematyków zgadza się dzisiaj co do tego że zdania pasujące do poniższych schematów powinny być uznane za prawdziwe: Aksjomaty klasycznego rachunku zdań.

  1. (formuła ta jest nazywana

aksjomatem K)

  1. (formuła ta jest nazywana

aksjomatem S)

Zdania pasujące do powyższych schematów to wszystkie zdania które można otrzymać podstawiając w miejsce dowolne formuły.

Reguła dowodzenia

Przyglądnijmy się teraz jak posługujemy się implikacją we wniskowaniu. W przykładzie z początku wykładu implikacja odpowiadała konstrukcji językowej:

"'jeśli"' "'to"' .

W takim przypadku jeśli akceptujemy powyższą implikacjię jako zdanie prawdziwe oraz jeśli zdanie jako prawdziwe to powinniśmy także zaakceptować . Przedstawiony sposób wnioskowania nosi nazwę reguły "Modus Ponens" (nazywana też regułą odrywania, często będziemy używać skrótu MP) i jest skrótowo notowany w poniższy sposób

Reguła modus ponens posłuży nam do uzupełniania zbioru aksjomatów o ich konsekwencje logiczne, które również uznamy za prawdziwe. Aby precyzyjnie zdefiniować zbiór wszystkich konsekwencji logicznych aksjomatów definiujemy poniżej pojęcie dowodu.

Ciąg formuł jest dowodem formuły wtedy i tylko wtedy, gdy:

  1. jest formułą
  1. dla każdego formuła jest aksjomatem

lub istnieją takie, że formuła jest wynikiem zastosowania reguły modus ponens do formuł .

W drugim punkcie powyższej definicji jeśli formuła nie jest aksjomatem (a więc powstaje przez zastosowanie MP) to formuły muszą pasować do przesłanek reguły MP, a więc musi być postaci lub postaci .

Formułę nazywamy "twierdzeniem klasycznego rachunku zdań" jeśli istnieje jej dowód z aksjomatów klasycznego rachunku zdań Uzupelnic defn:AksjomatyKRZ|.

Przykład

Zastanówmy się na formułą postaci . Intuicja podpowiada, że taką formułę powinniśmy uznać za prawdziwą. Nie pasuje ona jednak do żadnego ze schematów aksjomatów Uzupelnic defn:AksjomatyKRZ|. Formuła ta jest jednak twierdzeniem klasycznego rachunku zdań. Poniżej przedstawiamy jej dowód. Aby łatwiej dopasować formuły do schematów aksjomatów użyliśmy nawiasów kwadratowych dla nawiasów, które pochodzą ze schematów.

  1. formuła ta jest aksjomatem zgodnym ze schematem S
  1. aksjomat zgodny ze

schematem K

  1. z modus ponens z

formuł 1 i 2.

  1. aksjomat zgodny ze schematem

K

  1. z modus ponens z formuł 3 i 4

Podsumowanie

Klasyczny rachunek zdań, czyli zbiór formuł które uznajemy za prawdziwe zdefiniowaliśmy wyróżniając pewne formuły jako aksjomaty Uzupelnic defn:AksjomatyKRZ| i dorzucając do nich wszystkie formuły, które dają się z nich wywnioskować przy pomocy reguły modus ponens. Warto zwrócić uwagę, że pomimo tego iż w doborze aksjomatów i reguł wnioskowania kierowaliśmy się intuicyjnym pojęciem implikacji i konsekwencji, klasyczny rachunek zdań jest teorią syntaktyczną, zbiorem pewnych napisów o których znaczeniu nie musimy nic mówić.

Warto przyglądnąć się przyjętym aksjomatom i zastanowić się jakim zdaniom odpowiadają i czy rzeczywiście bylibyśmy skłonni uznać je za prawdziwe. Pomocne może być interpretowanie formuł postaci jako ",,jeśli prawdziwe jest i prawdziwe jest to prawdziwe jest "". W kolejnych rozdziałach przekonamy się że taka interpretacja jest uzasadniona.

Matryca boolowska

W poprzednim rozdziale zdefiniowaliśmy klasyczny rachunek zdań jako teorię aksjomatyczną. Jeśli pozwolimy sobie na używanie skończonych zbiorów i funkcji, możemy równoważnie zdefiniować klasyczny rachunek zdań za pomocą tzw. matrycy boolowskiej.

Dwuelementową matrycą boolowską nazywamy zbiór dwuelementowy w którym 1 jest wyróżnioną wartością prawdy, wraz z dwoma funkcjami odpowiadającymi za interpretacje spójników oraz zdefiniowanymi następująco

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c c|}\hline & 0 & 1 \\\hline 0 & 1 & 1 \\ 1 & 0 & 1 \\\hline \endtabular \hspace{1cm} \begintabular {|c|c|}\hline } pParser nie mógł rozpoznać (błąd składni): {\displaystyle & } pParser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 0 & 1 \\ 1 & 0 \\\hline \endtabular }

Wartościowaniem nazywamy funkcję która przypisuje zmiennym zdaniowym elementy zbioru . Wartościowanie zmiennych można rozszerzyć na wartościowanie formuł interpretując spójniki oraz jako funkcje zgodnie z tabelami Uzupelnic eq:tabeleInterpretacjiKRZ|.

ład

Niech będzie wartościowaniem zmiennych takim, że . Wtedy

  • formuła jest wartościowana na

0 (będziemy to zapisywać jako ),

  • formuła jest wartościowana na 1 (czyli )
  • formuła jest wartościowana na 0 (czyli )

ład

Ćwiczenie [Uzupelnij]

Przy wartościowaniu z przykładu Uzupelnic eg:wartosciowania| jakie wartości przyjmują następujące formuły

Solution.

Ćwiczenie [Uzupelnij]

  1. Podaj przykład wartościowania zmiennych tak aby poniższe formuły

były wartościowane na 0

  1. Podaj przykład wartościowania zmiennych tak aby poniższe formuły

były wartościowane na 1

Solution.
Wartościowania będziemy oznaczać przez

Twierdzenie o pełności

Zauważmy, że istnieją formuły, które dla każdego wartościowania zmiennych zdaniowych zawsze przyjmują wartość 1 (np. ). Takie formuły będziemy nazywać "'tautologiami"'.

Ćwiczenie [Uzupelnij]

Sprawdź czy poniższe formuły są tautologiami

{hint}{1}

Hint .
Spróbuj poszukać wartościowań dla których formuła przyjmuje

wartość 0

{hint}{1}

Hint .
Można też sprawdzić wszystkie możliwości wartościowań.
Solution.

Nie przez przypadek pierwsze trzy formuły z poprzedniego zadania odpowiadają aksjomatom klasycznego rachunku zdań Uzupelnic defn:AksjomatyKRZ|. Okazuje się że istnieje ścisły związek pomiędzy tautologiami a twierdzeniami klasycznego rachunku zdań. Mówi o tym ważny wynik Emil Post.

Twierdzenie [Uzupelnij]

{Post 1921}

Formuła jest twierdzeniem klasycznego rachunku zdań wtedy i tylko wtedy kiedy jest tautologią.

Dowód powyższego twierdzenia jest przedstawiony na wykładzie Logika dla informatyków

Dzięki powyższemu twierdzeniu możemy w miarę łatwo stwierdzać czy dana formuła jest twierdzeniem klasycznego rachunku zdań sprawdzając czy jest tautologią, co wymaga rozważenia jedynie skończonej (chociaż często niemałej) liczby wartościowań. Co więcej, mamy też możliwość dowodzenia, że jakaś formuła nie jest twierdzeniem klasycznego rachunku zdań. Uzasadnienie, że nie da się jakiejś formuły udowonić z aksjomatów poprzez stosowanie reguły MP wydaje się zadaniem trudnym, znacznie łatwiej jest poszukać wartościowania, które wartościuje formułę na 0 (znowu wystarczy sprawdzić jedynie skończenie wiele wartościowań).

Ćwiczenie [Uzupelnij]

Udowodnij że każde twierdzenie klasycznego rachunku zdań jest tautologią.

{hint}{1}

Hint .
Pokazaliśmy już w zadaniu

Uzupelnic zad:aksjomatyTatuologie|, że aksjomaty są tautologiami. Zacznij od pokazania, że zastosowanie reguły MP do tautologii daje tautologię. {hint}{1}

Hint .
Udowodnij, twierdznie przez indukcję ze względu na długość

dowodu.

Solution.

Inne spójniki

Do tej pory jedynymi rozważanymi spójnikami była implikacja i negacja. W analogiczny sposób do Uzupelnic eq:tabeleInterpretacjiKRZ| możemy wprowadzać kolejne spójniki. Często używane spójniki to koniunkcja (spójnik "'i"') oznaczana przez oraz alternatywa (spójnik "'lub"') oznaczana przez , które będziemy interpretować w następujący sposób:

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c c|}\hline & 0 & 1 \\\hline 0 & 0 & 0 \\ 1 & 0 & 1 \\\hline \endtabular \hspace{1cm} \begintabular {|c|c c|}\hline & 0 & 1 \\\hline 0 & 0 & 1 \\ 1 & 1 & 1 \\\hline \endtabular }

Zgodnie z intuicją koniunkcja jest wartościowana na 1 wtedy i tylko wtedy gdy zarówno jak i są wartościowane na 1. Alternatywa jest wartościowana na 1 jeśli przynajmniej jedna z formuł jest wartościowana na 1.

Formuły oraz są "równoważne" (oznaczamy ten fakt przez wtedy i tylko wtedy gdy dla każdego wartościowania formuła przyjmuje tą samą wartość co formuła .

Ćwiczenie [Uzupelnij]

Udowodnij, że następujące formuły są równoważne

Solution.
  1. Lewa strona jest fałszywa jedynie gdy oraz

są wartościowane na 0. Prawa strona jest fałszywa wtedy i tylko wtedy kiedy jest wartościowane na 1 oraz jest wartościowane na 0 (to jedyna możliwość aby implikacja była fałszywa). Wobec tego prawa strona jest fałszywa wtedy i tylko wtedy kiedy oraz są wartościowane na 0, a więc jest równoważna lewej.

  1. Lewa strona jest prawdziwa jedynie gdy oraz

są wartościowane na 1. Prawa strona jest prawdziwa wtedy i tylko wtedy kiedy jest wartościowane na 1, więc wtedy gdy jest wartościowane na 0. To z kolei zdarzyć się może jedynie gdy jest wartościowane na 1 i na 0, a więc wtedy gdy zarówno jak i są wartościowane na 1. Wobec tego obie formuły są równoważne.

Równie dobrym rozwiązaniem jest sprawdzenie wszystkich możliwości wartościowań i porównanie wyników.

Z powyższego zadania wynika, że każdą formułę w której występują spójniki lub można zastąpić równoważną formułą w której jedynymi spójnikami są oraz . Tak naprawdę więc nowe spójniki nie wprowadzają nic nowego poza użytecznymi skrótami w zapisywaniu formuł.

Aby się oswoić z własnościami spójników prześledzimy szereg ich praw.

Ćwiczenie [Uzupelnij]

Udowodnij następujące równoważności

Solution.
Przedstwiamy przykładowe dowody kilku pierwszych równoważności.
  1. Jeśli jest wartościowane na 1, to zgodnie z tabelą dla negacji Uzupelnic eq:tabeleInterpretacjiKRZ|

jest wartościowane na 0 i jest wartościowane na 1. Jeśli jest wartościowane na 0 to jest wartościowane na 1 i jest wartościowane na 0. Formuły przyjmują te same wartości dla każdego wartościowania więc są równoważne.

  1. Jedyną możliwością aby lewa strona była fałszywa jest

aby było wartościowane na 1, a na 0. Prawa stona jest fałszywa jedynie gdy oraz są wartościowane na 0. Czyli prawa strona jest fałszywa jedynie gdy jest wartościowane na 1 i na 0. Formuły są więc równoważne.

  1. Analogicznie do poprzedniego punktu łatwo się

przekonać, że jedynym wartościowaniem które falsyfikuje lewą stronę jest takie które wartościuje i na 1 oraz na 0. Tą samą własność ma formuła po prawej stronie, więc formuły są równoważne.

  1. Przykład rozwiązania przez rozważenie wszystkich

możliwości

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c|c|c|c|c|c|}\hline } pParser nie mógł rozpoznać (błąd składni): {\displaystyle & } qParser nie mógł rozpoznać (błąd składni): {\displaystyle & } p qParser nie mógł rozpoznać (błąd składni): {\displaystyle & } (p q)Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } pParser nie mógł rozpoznać (błąd składni): {\displaystyle & } qParser nie mógł rozpoznać (błąd składni): {\displaystyle & } p qParser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 0 & 1 & 1 & 0 & 1\\ 1 & 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 1 & 0 & 0 & 0 & 0\\\hline \endtabular \hspace{1cm} }

W pierwszych dwóch kolumnach są zapisane wartościowania zmiennych i a w pozostałych odpowiadające im wartościowania formuł zbudowanych z tych zmiennych. Ponieważ kolumna 4 i 7 są identyczne to formuły z zadania są równoważne.

  1. W równoważności z poprzedniego punktu, podstawiąjąc za

formułę oraz za formułę otrzymamy równoważność

Stosując dwukrotnie równoważność z pierwszego punktu do prawej strony otrzymujemy

Negując tą równoważność obustronnie otrzymamy

Stosując równoważność z pierwszego punktu do lewej strony otrzymamy szukaną równoważność.

Ćwiczenie [Uzupelnij]

Sprawdź które z następujących formuł są tautologiami

Solution.
  1. Spróbujmy znaleźć wartościowanie które falsyfikuje tą

formułę. Skoro implikacja ma być fałszywa to formuła (czyli następnik) musi być fałszywa. Tak jest tylko wtedy kiedy zarówno jak i są fałszywe. Zobaczmy co się wtedy dzieje z poprzednikim implikacji, czyli formułą

Jeśli teraz ustalimy na fałsz to będzie fałszywe a jeśli ustalimy na prawdę to będzie fałszywe. W obu tych przypadkach cały poprzednik jest fałszywy. Wynika stąd, że nie da się dobrać takiego wartościowania że poprzednik jest prawdziwy, a następnik fałszywy więc rozważana formuła jest tautologą.

  1. Formuła nie jest tautologią. Wystarczy wartościować i

na prawdę i na fałsz.

  1. Formuła nie jest tautologią. Wystarczy wartościować i

na prawdę i na fałsz.

  1. Przykład rozwiązania przez rozważenie wszystkich

możliwości

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c|c|c|c|c|c|c|}\hline } pParser nie mógł rozpoznać (błąd składni): {\displaystyle & } qParser nie mógł rozpoznać (błąd składni): {\displaystyle & } rParser nie mógł rozpoznać (błąd składni): {\displaystyle &} (p q)Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} (p r)Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} ( q r)Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} (p r)( q r)Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } (p q) ( (p r)( q r))Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0& 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1& 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0& 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0& 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1& 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 1& 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 1& 1 \\\hline \endtabular \hspace{1cm} }

W kolumnie odpowiadającej badanej formule są same 1, więc jest ona tautologią.

Binarne spójniki logiczne interpretowaliśmy jako funkcje z . Nie trudno przekonać się że takich funkcji jest dokładnie 16. Dla każdej takiej funkcji możemy dodać spójnik, który będzie interpretowany dokładnie jako ta funkcja. W poniższej tabeli zamieszczamy wszystkie takie funkcje wraz ze zwyczajowymi oznaczeniami odpowiadających im spójników.

W poniższej tabeli przedstawiamy wszystkie spójniki binarne.

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c|c|c|c|c||c|}\hline Numer & } p=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} p=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} p=1Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} p=1Parser nie mógł rozpoznać (błąd składni): {\displaystyle && \\ funkcji& } q=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } q=1Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } q=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } q=1Parser nie mógł rozpoznać (błąd składni): {\displaystyle && \\ \hline 0 & 0 & 0 & 0 & 0 && } FParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 1 & 0 & 0 & 0 & 1 && \\ 2 & 0 & 0 & 1 & 0 && } (p q)Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 3 & 0 & 0 & 1 & 1 && } pParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 4 & 0 & 1 & 0 & 0 && } (q p)Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 5 & 0 & 1 & 0 & 1 && } qParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 6 & 0 & 1 & 1 & 0 && } XORParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 7 & 0 & 1 & 1 & 1 && \\ 8 & 1 & 0 & 0 & 0 && } NORParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 9 & 1 & 0 & 0 & 1 && \\ 10& 1 & 0 & 1 & 0 && } qParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 11& 1 & 0 & 1 & 1 && } q pParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 12& 1 & 1 & 0 & 0 && } p Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 13& 1 & 1 & 0 & 1 && } p q Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 14& 1 & 1 & 1 & 0 && } NANDParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 15& 1 & 1 & 1 & 1 && } T Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline \endtabular \hspace{1cm} }

Spójnik binarny będziemy nazywać "przemiennym" jeśli zachodzi następująca równoważność

Ćwiczenie [Uzupelnij]

Sprawdź następujące równoważności

Solution.

Ćwiczenie [Uzupelnij]

Ile spójników binarnych jest przemiennych? Wypisz je wszystkie.

{hint}{1}

Hint .
Wygodnie jest reprezentować spójniki binarne w tabeli

kwadratowej. Na przykład alternatywę zdefiniowaliśmy jako

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c c|}\hline & 0 & 1 \\\hline 0 & 0 & 1 \\ 1 & 1 & 1 \\\hline \endtabular . }

Jaką własność musi posiadać tabela aby spójnik definiowany przez nią był przemienny?

Solution.
Dla przemienności spójnika istotne jest aby . Dla pozostałych

przypadków wartościowań równoważnośc Uzupelnic eq:przemienność| jest zawsze spełniona. Każdy spójnik binarny możemy zdefiniować za pomocą tabelki kwadratowej, np. alternatywę zdefiniowaliśmy jako

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c c|}\hline & 0 & 1 \\\hline 0 & 0 & 1 \\ 1 & 1 & 1 \\\hline \endtabular . }

Warunek przemienności oznacza, że wartość w polu o współrzędnych jest równa wartości w polu o współrzędnych . Takich tabel jest 8, więc mamy 8 spójników przemiennych. Nietrudno je teraz odnaleźć w tabeli Uzupelnic defn:spójniki|. Są to

Spójnik binarny będziemy nazywać "łącznym" jeśli zachodzi następująca równoważność

Jeśli spójnik jest łączny to dowolne dwie formuły, które są zbudowane jedynie ze spójników są równoważne jeśli występuje w nich tyle samo spójników. Dlatego dla łącznych spójników binarnych pomija się często nawiasy.

Ćwiczenie [Uzupelnij]

Udowodnij, że następujące spójniki są łączne

Solution.
  1. Formuła jest fałszywa jedynie

wtedy gdy , i są wartościowane na fałsz. Tak samo jest dla formuły więc są one równoważne.

  1. Formuła jest prawdziwa jedynie

wtedy gdy , i są wartościowane na prawdę. Tak samo jest dla formuły więc są one równoważne.

  1. Zbadamy równoważność formuł

i za pomocą tabeli

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c|c|c|c|c|c|}\hline } pParser nie mógł rozpoznać (błąd składni): {\displaystyle &} qParser nie mógł rozpoznać (błąd składni): {\displaystyle &} r Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} (p q)Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } (p q) rParser nie mógł rozpoznać (błąd składni): {\displaystyle & } (q r )Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} p (q r)Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\hline \endtabular \hspace{1cm} }

Kolumna 4 i 6 są identyczne więc odpowiadające im formuły są równoważne. Spójnik jest więc łączny.

  1. ...

Możemy również rozważać spójniki 3 i więcej argumentowe. Spójnik -argumetowy powinien odpowiadać funkcji . ład W poniższej tabeli przedstawiamy przykład spójnika trójargumentowego

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c c c|c||}\hline } pParser nie mógł rozpoznać (błąd składni): {\displaystyle & } qParser nie mógł rozpoznać (błąd składni): {\displaystyle & } rParser nie mógł rozpoznać (błąd składni): {\displaystyle &} (p, q,r)Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\\hline \endtabular \hspace{1cm} }

ład

Ćwiczenie [Uzupelnij]

Udowodnij, że różnych spójników -argumentowych jest dokładnie .

Solution.

Systemy funkcjonalnie pełne

Każda formuła odpowiada pewnej funkcji przekształcającej wartościowania zmiennych w niej występujących w element zbioru . Na przykład formuła wyznacza funkcję opisaną poniższą tabelą

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c|c|c|}\hline p & q & r & } f_{p (q r)}Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\\hline \endtabular }

Mówimy, wtedy że formuła definuje funkcję .

Skończony zbiór funkcji boolowskich nazywamy funkcjonalnie pełnym, jeśli każdą funkcję boolowską da się zdefiniować przy pomocy formuły zbudowanej wyłącznie ze spójników odpowiadających funkcjom ze zbioru .

Twierdzenie [Uzupelnij]

Zbiór jest funkcjonalnie pełny.

Dowód [Uzupelnij]

End of proof.gif

Twierdzenie [Uzupelnij]

Zbiory , są funkcjonalnie pełne.

Dowód [Uzupelnij]

End of proof.gif

Udowodnij, że zbiór jest funkcjonalnie pełny.

Twierdzenie [Uzupelnij]

Zbiór jest funkcjonalnie pełny.

Udowodnij, że zbiór jest funkcjonalnie pełny.

Ćwiczenie [Uzupelnij]

Zdefiniuj alternatywę przy pomocy samej implikacji.

Solution.
Łatwo sprawdzić że formuła jest równoważna

formule .

Jakie funkcje binarne da się zdefiniować przy pomocy samej implikacji?

Ćwiczenie [Uzupelnij]

Udowodnij, że poniższe zbiory nie są funkcjonalnie pełne

Solution.
  1. Oznaczmy zbiór formuł w których jedynym spójnikiem jest przez

. Udowodnimy, że każda formuła z przyjmuje zawsze wartość 1, jeśli jej zmienne są wartościowane na 1. Rozmiarem formuły będziemy nazywać liczbę wystąpień spójnika w formule. Dowód będzie indukcyjny ze względu na rozmiar formuły.

Baza indukcji: Każda formuła z o rozmiarze 0 jest postaci , gdzie jest zmienną. Wobec tego przy wartościowaniu zmiennych na 1 formuła też jest wartościowana na 1. A więc każda formuła o rozmiarze 0 ma postulowaną własność.

Krok indukcyjny: Ustalmy dowolne i przyjmijmy, że wszystkie formuły o mniejszym rozmiarze mają postulowaną własność. Niech będzie dowolną formułą z o rozmiarze . Skoro to musi być postaci . Rozważmy wartościowanie które wszyskim zmiennym przypisuje wartość 1. Ponieważ rozmiary oraz są silnie mniejsze od to z założenia indukcyjnego otrzymujemy, że dla naszego wartościowania obie przyjmują wartość 1. Wobec tego zgodnie z tabelą Uzupelnic eq:tabeleInterpretacjiKRZANDOR| cała formuła też przyjmuje wartość 1. Dowiedliśmy więc, że każda formuła o rozmiarze ma postulowaną własność.

Wiemy już że każda przyjmuje zawsze wartość 1, jeśli jej zmienne są wartościowane na 1. Wobec tego niemożliwe jest zdefiniowanie np. spójnika gdyż definująca go formuła musiałby przyjąć wartość 0 na takim wartościowaniu.

  1. Dowód analogiczny do poprzedniego.

Ćwiczenie [Uzupelnij]

Czy funkcje binarne zdefiniowane za pomocą formuł zawierającyh jedynie przemienne spójniki muszą być przemienne?

{hint}{1}

Hint .
Przyjrzyj się formułom zbudowanym z

Ćwiczenie [Uzupelnij]

(z wykładu prof. P.M.Idziaka) Niech oznacza ilość boolowskich funkcji argumetnowych, a ilość boolowskich funkcji argumentowych, takich że przy pomocy każdej z nich da się zdefiniować dowolną funkcję boolowską (czyli jeśli jest takim spójnikiem to zbiór jest funkcjonalnie pełny). Udowdnij istenienie poniższej granicy i wyznacz jej wartość

Solution.

Postacie normalne

"Literałem" nazywamy formułę która jest zmienną zdaniową lub negacją zmiennej zdaniowej.

Zauważmy, że formuła konstruowana w dowodzie twierdzenia Uzupelnic thm:AndOrNegFP| jest w pewnej standartowej postaci - formuła jest alternatywą formuł które są koniunkcjami literałów. Przypomnijmy, że dla zbudujemy formułę

Formuła jest w dyzjunktywnej postaci normalnej (DNF) jeśli jest alternatywą formuł które są koniunkcjami literałów. Czyli wtedy gdy jest postaci

oraz każda z formuł jest koniunkcją literałów, czyli jest postaci

dla pewnych literałów

Twierdzenie [Uzupelnij]

Dla każedej formuły istnieje równoważna formuła w DNF.

Dowód [Uzupelnij]

Wynika bezpośrednio z konstrukcji w dowodzie twierdzenia Uzupelnic thm:AndOrNegFP|.

End of proof.gif

Formuła jest w koniunktywnej postaci normalnej (CNF) jeśli jest koniunkcją formuł które są alternatywami literałów.

Twierdzenie [Uzupelnij]

Dla każdej formuły istnieje równoważna formuła w CNF.

Dowód [Uzupelnij]

End of proof.gif

Ćwiczenie [Uzupelnij]

Jak sprawdzić, czy formuła w CNF jest tautologią?

Solution.
Niech rozważaną formułą będzie

Aby była tautologią konieczne jest aby każda z formuł była tautologią. Ponieważ każda z formuł jest alternatywą literałów to jest tautologią jedynie wtedy jeśli istnieje taki literał który występuje w zarówno pozytywnie (czyli jako zmienna) jak i negatywnie (czyli jako zanegowana zmienna).

Ćwiczenie [Uzupelnij]

Dla poniższych formuł wypisz ich najkrótsze równoważne formuły w CNF

Solution.

Spełnialność

Spośród wszystkich formuł wyróżnimy też zbiór formuł spełnialnych.

Formuła jest spełnialna jeśli istenieje takie wartościowanie które wartościuje tą formułę na 1.

Formuły spełnialne są w ścisłym związku z tautologiami.

Twierdzenie [Uzupelnij]

Formuła jest tautologią wtedy i tylko wtedy kiedy formuła nie jest spełnialna.

Dowód [Uzupelnij]

Przypuśćmy, że formuła jest tautologią. Wtedy dla każdego wartościowania mamy . Stąd otrzymujemy że dla każdego wartościowania mamy, a więc nie istnieje wartościwanie, które spełnia , czyli formuła ta nie jest spełnialna.

Przypuśćmy, że formuła nie jest spełnialna, czyli nie istnieje wartościowanie takie, że . Wynika stąd, że dla każdego wartościowania mamy , a więc jest tautologią.

End of proof.gif

Ćwiczenie [Uzupelnij]

Sprawdź spełnialność następujących formuł

Solution.

Logika intuicjonistyczna

Niektórzy logicy mają wątpliwości co do tego czy powinniśmy przyjmować schemat dowodu nie wprost jako aksjomat. Poddanie w wątpliwość tego aksjomatu doprowadziło do powstnia tzw. logiki intuicjonistycznej. Ważnym powodem zajmowania się logiką intuicjonistyczną są jej zadziwiające związki z teorią obliczeń (izomorfizm Curry-Howard).

Implikacyjny fragment logiki intuicjonistycznej, który będziemy oznaczać przez to zbiór tych formuł które da się dowodnić przy pomocy reguły MP z aksjomatów S i K. Aksjomaty

  1. (formuła ta jest nazywana

aksjomatem K)

  1. (formuła ta jest nazywana

aksjomatem S)

W pełnej wersji logiki intucjonistycznej pojawiają się również aksjomaty dla spójników oraz . Dla uproszczenia zajmiemy się jedynie formułami w których jedynym spójnikiem jest implikacja. Dodatkowym argumentem uzasadniającym takie podejście jest fakt, że każde twierdzenie logiki intuicjonistycznej w którym jedynymi spójnikami są da się udowodnić przy pomocy aksjomatów Uzupelnic defn:AksjomatyIntImp|. Zobaczymy, że analogiczne twierdzenie nie jest prawdą dla logiki klasycznej. Logika intuicjonistyczna jest bardziej skomplikowana od logiki klasycznej. W szczególności nie istnieje skończona matryca za pomocą której moglibyśmy rozstrzygać czy dana formuła jest twierdzeniem logiki intuicjonistycznej.

Twierdzenie [Uzupelnij]

Każde twierdzenie logiki intuicjonistycznej jest twierdzeniem klasycznego rachunku zdań.

Dowód [Uzupelnij]

Każdy dowód twierdzenia logiki inuicjonistycznej jest równocześnie dowodem twierdzenia klasycznego rachunku zdań.

End of proof.gif

Implikacja w drugą stronę nie zachodzi. Istnieją formuły zbudowane jedynie przy pomocy , które nie należą do pomimo że są twierdzeniami klasycznego rachunku zdań. Przykładem takiej formuły jest prawo Pierce'a:

W zadaniu Uzupelnic zad:aksjomatyTatuologie| pokazaliśmy, że formuła ta jest w istocie tautologią więc w myśl twierdzenia Posta Uzupelnic thm:zupełnośćPost| również twierdeniem klasycznego rachunku zdań.

W poniższych zadaniach wykażemy poniższe twierdzenie

Twierdzenie [Uzupelnij]

Prawo Pierce'a nie jest twierdzeniem intuicjonizmu.

Zauważmy, że oznacza to również że każdy dowód prawa Pierce'a w logice klasycznej korzysta z aksjomatu 3 Uzupelnic defn:AksjomatyKRZ|, a więc wymaga używania spójnika .

Aby udowodnić twierdzenie Uzupelnic thm:PrawoPiercea| zdefiniujemy jeszcze jedną logikę którą nazwiemy . Podobnie do Uzupelnic defn:matrycaBool| zdefiniujemy matrycę tym razem 3-elementową.

Matrycą będziemy nazywać zbiór trójelementowy w którym 2 jest wyróżnioną wartością prawdy, wraz z funkcją odpowiadają za interpretacje zdefiniowaną następująco

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c c c|}\hline & 0 & 1 & 2\\\hline 0 & 2 & 2 & 2\\ 1 & 0 & 2 & 2\\ 2 & 0 & 1 & 2\\\hline \endtabular \hspace{1cm} }

W przypadku rozważanej matrycy wartościowanie będzie funkcją przypisującą zmiennym zdaniowym elementy zbioru . Podobnie jak dla logiki klasycznej wartościowanie zmiennych rozszzerzamy na wartościowanie formuł zgodnie z tabelą Uzupelnic eq:tabeleInterpretacjiInt3|.

ład Dla wartościowania takiego, że formuła

przyjmuje wartość 0. ład

Tautologią logiki będziemy nazywać każdą formułę implikacyjną, która przy każdym wartościowaniu zmiennych w przyjmuje wartość 2.

Ćwiczenie [Uzupelnij]

Udowodnij, że aksjomaty S i K są tautologiami .

Solution.

Ćwiczenie [Uzupelnij]

Udowodnij, że jeśli formuła postaci oraz formuła są tautologiami to formuła jest tautologią .

Solution.

Ćwiczenie [Uzupelnij]

Udowodnij, że każde twierdzenie logiki jest tautologią .

{hint}{1}

Hint .
Przeprowadź rozumowanie indukcyjne ze względu na długość dowodu.

Pomocne będą poprzednie zadania.

Solution.

Ćwiczenie [Uzupelnij]

Sprawdź, czy prawo Pierce'a jest tautologią . {hint}{1}

Hint .
Nie jest.
Solution.
Dla wartościowania takiego, że i kolejne

fomruły przyjmują następujace wartości

Wobec tego prawo Pierce'a nie jest tautologią gdyż wyróżnioną wartością prawdy w jest 2.

Podsumujmy wyniki powyższych zadań. Wskazaliśmy logikę taką, że każda twierdzenie intuicjonizmu jest tautologią . Skoro prawo Pierce'a nie jest tautologią to nie jest też twierdzeniem .

UWAGA! W dalszej części będziemy się posługiwać wyłącznie "'logiką klasyczną"'. {amsplain}