Test GR: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Nie podano opisu zmian
m Zastępowanie tekstu – „<math> ” na „<math>”
 
(Nie pokazano 110 wersji utworzonych przez 3 użytkowników)
Linia 1: Linia 1:
==Wprowadzenie==
<quiz type="exclusive">


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
</quiz>
równe 2.


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


# "n jest liczbą pierwszą,"
------------------------------


# "n jest liczbą nieparzystą,"


# "n jest równe 2."
1111111111111111111111111111111111111111111


Oznaczmy powyższe zdania przez <math>p,q,r</math> (w takiej właśnie
kolejności). Używając symboli, które zwyczajowo odpowiadają
potocznemu rozumieniu spójników <math>\textbf{jeśli} [..] \textbf{to},
\textbf{lub}</math> oraz powyższych oznaczeń otrzymamy formułę


<center><math>


p \Rightarrow (q \vee r).
1111111111111111111111111111111111111111111
</math></center>
 
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:
 
# <math> p \Rightarrow (q \vee r) </math>,
 
# <math>p </math>,
 
# <math> \neg q </math> (przez <math>\neg</math> oznaczamy negację)
 
to zgodnie z klasycznym rachunkiem (może lepiej z intuicją?) zdań
powinniśmy uznać za prawdziwe zdanie <math>r</math>, czyli "n jest równe
2". Powyższy schemat wnioskowania można również opisać formułą
 
<center><math>
 
\left((p \Rightarrow (q \vee r)) \wedge p \wedge (\neg q)\right) \Rightarrow
q.
</math></center>
 
W powyższej formule spójnik symbol <math>\wedge</math> 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}
 
# zmienna zdaniowa jest formułą (zmienne zdaniowy oznaczamy
zwykle literami alfabetu rzymskiego np. <math>p,q,r</math>)
 
# jeśli <math>\phi</math> oraz <math>\psi</math> są formułami to <math>(\phi
\Rightarrow \psi)</math> jest formułą (spójnik <math>\Rightarrow</math> nazywamy implikacją)
 
# jeśli <math>\phi</math> jest formułą to <math>\neg \phi</math> jest formułą
(spójnik <math>\neg</math> nazywamy negacją)
 
# 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
<math>\Rightarrow</math> oraz <math>\neg</math>.
 
Zgodnie z powyższą definicją nie jest formułą napis <math>p\Rightarrow q</math>,
gdyż brakuje w nim nawiasów. Pomimo, iż poprawnie powinniśmy
napisać <math>(p\Rightarrow q)</math> 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
 
* <math>p \Rightarrow \Rightarrow q</math>
 
* <math>\neg \neg \neg</math>
 
* "ten napis na pewno nie jest formułą"
 
* <math>(p \Rightarrow \neg q))</math>
 
Poniższe napisy są formułami
 
* <math>(p \Rightarrow (r \Rightarrow q))</math>
 
* <math>\neg \neg \neg q</math>
 
* <math>(p \Rightarrow \neg q)</math>
 
ład
 
{{cwiczenie|[Uzupelnij]||
 
Rozmiarem formuły nazwiemy ilość występujących w niej spójników.
Na przykład formuła <math>\neg \neg q</math> ma rozmiar 2, a formuła
<math>(p\Rightarrow q)</math> ma rozmiar 1. Przypuśćmy, że jedyną zmienną zdaniową
jaką wolno nam użyć jest <math>p</math>. Ile można skonstruować rożnych
formuł o rozmiarze 3?
 
; Solution.
: Oznaczmy przez <math>f_n</math> liczbę formuł o rozmiarze <math>n</math> (czyli liczbę
formuł w których jest <math>n</math> spójników). Interesuje nas <math>f_3</math>. Każda
formuła o rozmiarze 3 powstaje albo z dwóch formuł o rozmiarach 1
poprzez połączenie ich spójnikiem <math>\Rightarrow</math> albo z jednej formuły o
rozmiarze 2 poprzez dodanie do niej spójnika <math>\neg</math>. Co
więcej każda taka formuła powstaje tylko w jeden sposób. Wynika
stąd następująca zależność:
 
<center><math>
 
f_3= f_2 + (f_1)^2
</math></center>
 
Wiemy, że są tylko dwie formuły o rozmiarze 1, są to <math>\neg p</math> oraz
<math>p \Rightarrow p</math>. Stąd mamy <math>f_1=2</math>. 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ą <math>\Rightarrow</math>, albo jest zbudowana z formuły o rozmiarze
1 za pomocą negacji. Zauważmy też, że istnieje formuła o rozmiarze
0, jest to <math>p</math>. Mamy więc następujący wzór dla <math>f_2</math>
 
<center><math>
 
f_2= 1 \cdot f_1 + f_1 \cdot 1 +f_1 = 3 \cdot f_1
</math></center>
 
Z dwóch ostatnich wzorów otrzymujemy
 
<center><math>
 
f_3= 3 \cdot f_1 + (f_1)^2= 6+4 = 10
</math></center>
 
Skoro jest ich niewiele to możemy wszystkie wypisać
 
:# <math>\neg \neg \neg p</math>
 
:# <math>\neg \neg (p \Rightarrow p)</math>
 
:# <math>\neg (p \Rightarrow \neg p)</math>
 
:# <math>\neg (p \Rightarrow (p\Rightarrow p))</math>
 
:# <math>\neg (\neg p \Rightarrow  p)</math>
 
:# <math>\neg ((p\Rightarrow p) \Rightarrow  p)</math>
 
:# <math> (\neg p)\Rightarrow  (\neg p)</math>
 
:# <math> (\neg p)\Rightarrow  (p \Rightarrow p)</math>


:# <math> (p \Rightarrow p) \Rightarrow  (\neg p)</math>


:# <math> (p \Rightarrow p)\Rightarrow  (p \Rightarrow p)</math>


}}
22222222222222222222222222222222222222222


Język logiki zdaniowej można równoważnie zdefiniować nie
==Ciągi w przestrzeniach metrycznych. Test==
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
3333333333333333333333333333333333333333333333333333333333333
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===
==Norma. Iloczyn skalarny. Test==


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ń.


# <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math> (formuła ta jest nazywana
444444444444444444444444444444444444444444444444444444444444444
aksjomatem K)


# <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow
==Ciągi i szeregi funkcyjne. Szereg Taylora. Test==
(\phi \Rightarrow \nu) \right)</math> (formuła ta jest nazywana
aksjomatem S)


# <math>(\neg \phi \Rightarrow \psi) \Rightarrow (\neg \phi \Rightarrow \neg
<quiz>
\psi) \Rightarrow \phi</math>
Dany jest ciąg funkcyjny <math>\{f_n\}</math> gdzie
<math>
  f_n(x)=
  \left\{
  \begin{array} {lll}
  1 & \text{dla} & x\in[n,n+1]\\
  0 & \text{dla} & x\in \mathbb{R}\setminus[n,n+1]
  \end{array}
  \right</math>
dla <math>n\in\mathbb{N}</math>
Ciąg ten jest
<rightoption>zbieżny punktowo do <math>f(x)\equiv 0</math></rightoption>
<wrongoption>zbieżny jednostajnie do  <math>f(x)\equiv 0</math></wrongoption>
<wrongoption>zbieżny punktowo do funkcji <math>f(x)=
  \left\{
  \begin{array} {lll}
    1 & \text{dla} & x\geq 1\\
    0 & \text{dla} & x<0
  \end{array}
  \right</math></wrongoption>
</quiz>


Zdania pasujące do powyższych schematów to wszystkie zdania które
  tak, nie, nie
można otrzymać podstawiając w miejsce <math>\phi, \nu, \psi</math> dowolne
formuły.


===Reguła dowodzenia===
<quiz>
Dany jest ciąg funkcyjny <math>\{f_n\}</math> gdzie


Przyglądnijmy się teraz jak posługujemy się implikacją we
<center><math>f_n(x)=
wniskowaniu. W przykładzie z początku wykładu implikacja odpowiadała
  \left\{
konstrukcji językowej:
  \begin{array} {lll}
 
\frac{1-n^{-x}}{1+n^{-x}} & \text{dla} & x>0\\
"'jeśli"' <math>\phi</math> "'to"' <math>\psi</math>.
  \\
 
\frac{2-n^{x}}{2+n^{x}} & \text{dla} & x<0\\
W takim przypadku jeśli akceptujemy powyższą implikacjię jako zdanie
  \\
prawdziwe oraz jeśli zdanie <math>\phi</math> jako prawdziwe to powinniśmy
  0 & \text{dla} & x=0\\
także zaakceptować <math>\psi</math>. Przedstawiony sposób wnioskowania nosi
  \end{array}
nazwę reguły "Modus Ponens" (nazywana też regułą odrywania, często będziemy używać skrótu MP) i jest
  \right.
skrótowo notowany w poniższy sposób
  \quad</math> dla <math>\ n=1,2,\ldots
 
<center><math>
 
\frac{\phi \Rightarrow \psi, \phi}{\psi}.
</math></center>
</math></center>


Reguła modus ponens posłuży nam do uzupełniania zbioru aksjomatów  o
Ten ciąg funkcyjny jest
ich konsekwencje logiczne, które również uznamy za prawdziwe. Aby
<wrongoption>zbieżny jednostajnie</wrongoption>
precyzyjnie zdefiniować zbiór wszystkich konsekwencji logicznych
<rightoption>zbieżny punktowo ale nie jednostajnie</rightoption>
aksjomatów definiujemy poniżej pojęcie dowodu.
<wrongoption>rozbieżny</wrongoption>
</quiz>


Ciąg formuł <math>\phi_0, \dots ,\phi_n</math> jest dowodem formuły <math>\psi</math>
  nie, tak, nie
wtedy i tylko wtedy, gdy:


# <math>\phi_n</math> jest formułą <math>\psi</math>
<quiz>
Dany jest ciąg funkcyjny <math>f_n(x)=\sqrt[n]{x}</math> dla <math>x\ge 0</math> Ten ciąg
<wrongoption>jest zbieżny punktowo i jego granica jest ciągła</wrongoption>
<wrongoption>jest zbieżny jednostajnie i jego granica jest ciągła</wrongoption>
<rightoption>jest zbieżny punktowo i jego granica nie jest ciągła</rightoption>
</quiz>


# dla każdego <math>i\leq n</math> formuła <math>\phi_i</math> jest aksjomatem
  nie, nie, tak
lub istnieją <math>j,k <i</math> takie, że formuła <math>\phi_i</math>
jest wynikiem zastosowania reguły modus ponens do
formuł <math>\phi_j, \phi_k</math>.


W drugim punkcie powyższej definicji jeśli formuła <math>\phi_i</math> nie jest
<quiz>
aksjomatem (a więc powstaje przez zastosowanie MP) to formuły
Dany jest szereg <math>\sum_{n=1}^{\infty}\frac{\sin nx}{2^n(x^2+1)}, \ x\in \mathbb{R}</math> Ten szereg jest
<math>\phi_j,\phi_k</math> muszą pasować do przesłanek reguły MP, a więc
<wrongoption>zbieżny jednostajnie do funkcji <math>f(x)\equiv 0</math></wrongoption>
<math>\phi_j</math> musi być postaci <math>\phi_k \Rightarrow \phi_i</math> lub <math>\phi_k</math> postaci
<rightoption>zbieżny jednostajnie do funkcji <math>f</math> takiej, że <math>0<f(x)<3</math></rightoption>
<math>\phi_j \Rightarrow \phi_i</math>.
<wrongoption>zbieżny jednostajnie do funkcji <math>f(x)=\frac{1}{2(x^2+1)}</math></wrongoption>
</quiz>


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


===Przykład===
<quiz>
Funkcja <math>
    f(x):=\sum_{n=1}^{\infty}\frac{\sqrt[n]{x}}{n(n+1)(x^2+1)}</math>
Granica <math>\lim_{x\to 3}f(x)</math> wynosi
<rightoption><math>\frac{1}{10}</math></rightoption>
<wrongoption><math>\sqrt{3}</math></wrongoption>
<wrongoption><math>0</math></wrongoption>
</quiz>


Zastanówmy się na formułą postaci <math>\phi \Rightarrow \phi</math>. Intuicja
  tak, nie, nie
podpowiada, że taką formułę powinniśmy uznać za prawdziwą. Nie
pasuje ona jednak do żadnego ze schematów aksjomatów
[[##defn:AksjomatyKRZ|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.


# <math>[\phi \Rightarrow [(q \Rightarrow \phi) \Rightarrow \phi)]\Rightarrow [[\phi \Rightarrow (q \Rightarrow \phi)] \Rightarrow [\phi \Rightarrow
<quiz>
\phi]]</math> formuła ta jest aksjomatem zgodnym ze schematem S
Szereg <math>\sum_{n=1}^{\infty}\frac{1}{n(x^4+4)}</math> jest
 
<wrongoption>zbieżny punktowo</wrongoption>
# <math>\phi \Rightarrow [(q \Rightarrow \phi) \Rightarrow \phi]</math> aksjomat zgodny ze
<wrongoption>zbieżny jednostajnie </wrongoption>
schematem K
<rightoption>rozbieżny</rightoption>
 
</quiz>
# <math>(\phi \Rightarrow (q \Rightarrow \phi)) \Rightarrow (\phi \Rightarrow \phi)</math> z modus ponens z
formuł 1 i 2.
 
# <math>\phi \Rightarrow [q \Rightarrow \phi]</math> aksjomat zgodny ze schematem
K
 
# <math>(\phi \Rightarrow \phi)</math> 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
[[##defn:AksjomatyKRZ|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 <math>\phi \Rightarrow (\nu \Rightarrow \psi)</math> jako ",,jeśli prawdziwe jest
<math>\phi</math> i prawdziwe jest <math>\nu</math> to prawdziwe jest <math>\psi</math>"". 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
<math>\mathbb{B}=\{0,1\}</math> w którym 1 jest wyróżnioną wartością prawdy, wraz z
dwoma funkcjami odpowiadającymi za interpretacje spójników
<math>\Rightarrow</math> oraz <math>\neg</math> zdefiniowanymi następująco
 
<center><math>
 
\begintabular {|c|c c|}\hline
& 0 & 1 \\\hline
0 & 1 & 1 \\
1 & 0 & 1 \\\hline
\endtabular  \hspace{1cm}
\begintabular {|c|c|}\hline
</math>p<math> & </math> p<math> \\\hline
0 & 1  \\
1 & 0  \\\hline
\endtabular
</math></center>
 
Wartościowaniem nazywamy funkcję która przypisuje zmiennym
zdaniowym elementy zbioru <math>\mathbb{B}</math>. Wartościowanie zmiennych
można rozszerzyć na wartościowanie formuł interpretując spójniki
<math>\Rightarrow</math> oraz <math>\neg</math> jako funkcje zgodnie z tabelami
[[##eq:tabeleInterpretacjiKRZ|Uzupelnic eq:tabeleInterpretacjiKRZ|]].
 
ład
 
Niech <math>v</math> będzie wartościowaniem zmiennych takim, że <math>v(p)=0,
v(q)=1, v(r)=0</math>. Wtedy
 
* formuła <math>q \Rightarrow p</math> jest wartościowana na
0 (będziemy to zapisywać jako <math>v(q \Rightarrow p)=0</math>),
 
* formuła <math>r \Rightarrow (q \Rightarrow p)</math> jest wartościowana na 1 (czyli <math>v(r \Rightarrow (q \Rightarrow p))=1</math>)
 
* formuła <math>\neg p \Rightarrow r</math> jest wartościowana na  0 (czyli <math>v(\neg p \Rightarrow r)=0</math>)
 
ład
 
{{cwiczenie|[Uzupelnij]||
 
Przy wartościowaniu <math>v</math> z przykładu [[##eg:wartosciowania|Uzupelnic eg:wartosciowania|]] jakie
wartości przyjmują następujące formuły
 
# <math>p \Rightarrow (q \Rightarrow r)</math>
 
# <math>p \Rightarrow (p \Rightarrow q)</math>
 
# <math>\neg \neg q \Rightarrow p</math>
 
# <math>(\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q)</math>
 
; Solution.
: 
 
:# <math>v(p \Rightarrow (q \Rightarrow r))=1</math>
 
:# <math>v(p \Rightarrow (p \Rightarrow q))=1</math>
 
:# <math>v(\neg \neg q \Rightarrow p)=0</math>
 
:# <math>v((\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q))=0</math>
 
}}
 
{{cwiczenie|[Uzupelnij]||
 
# Podaj przykład wartościowania zmiennych tak aby poniższe formuły
były wartościowane na 0
 
## <math>p \Rightarrow (q \Rightarrow r)</math>
 
## <math>(\neg p \Rightarrow q)</math>
 
## <math>(p\Rightarrow q) \Rightarrow q</math>
 
# Podaj przykład wartościowania zmiennych tak aby poniższe formuły
były wartościowane na 1
 
## <math>\neg (p \Rightarrow q)</math>
 
## <math>\neg (\neg p \Rightarrow  \neg q)</math>
 
## <math>(\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q)</math>
 
; Solution.
: Wartościowania będziemy oznaczać przez <math>v</math>
 
:# 
 
:## <math>v(p)=1, v(q)=1, v(r)=0</math>
 
:## <math>v(p)=0,v(q)=0</math>
 
:## <math>v(p)=0,v(q)=0</math>
 
:# 
 
:## <math>v(p)=1,v(q)=0</math>
 
:## <math>v(p)=0,v(q)=1)</math>
 
:## <math>v(q)=1</math>
 
}}
 
===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. <math>p \Rightarrow p</math>).
Takie formuły będziemy nazywać "'tautologiami"'.
 
{{cwiczenie|[Uzupelnij]||
 
Sprawdź czy poniższe formuły są tautologiami
 
# <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math>
 
# <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow
(\phi \Rightarrow \nu) \right)</math>
 
# <math>(\neg \phi \Rightarrow \psi) \Rightarrow (\neg \phi \Rightarrow \neg
\psi) \Rightarrow \phi</math>
 
# <math>((\phi \Rightarrow q) \Rightarrow p) \Rightarrow p</math>
 
{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ń
[[##defn:AksjomatyKRZ|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ń).
 
{{cwiczenie|[Uzupelnij]||
 
Udowodnij że każde twierdzenie klasycznego rachunku zdań jest tautologią.
 
{hint}{1}
; Hint .
: Pokazaliśmy już w zadaniu
[[##zad:aksjomatyTatuologie|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 [[##eq:tabeleInterpretacjiKRZ|Uzupelnic eq:tabeleInterpretacjiKRZ|]]
możemy wprowadzać kolejne spójniki. Często używane spójniki to
koniunkcja (spójnik "'i"') oznaczana przez <math>\wedge</math> oraz
alternatywa (spójnik "'lub"') oznaczana przez <math>\vee</math>, które
będziemy interpretować w następujący sposób:
 
<center><math>
 
\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
</math></center>
 
Zgodnie z intuicją koniunkcja <math>\phi \wedge \psi</math> jest wartościowana
na 1 wtedy i tylko wtedy gdy zarówno <math>\phi</math> jak i <math>\psi</math> są
wartościowane na 1. Alternatywa <math>\phi \vee \psi</math> jest wartościowana
na 1 jeśli przynajmniej jedna z formuł <math>\phi, \psi</math> jest
wartościowana na 1.
 
Formuły <math>\phi</math> oraz <math>\psi</math> są "równoważne" (oznaczamy ten fakt
przez <math>\phi \equiv \psi</math> wtedy i tylko wtedy gdy dla każdego
wartościowania formuła <math>\phi</math> przyjmuje tą samą wartość co
formuła <math>\psi</math>.
 
{{cwiczenie|[Uzupelnij]||
 
Udowodnij, że następujące formuły są równoważne
 
# <math>\phi \vee \psi \equiv \neg \phi \Rightarrow \psi </math>
 
# <math>\phi \wedge \psi \equiv \neg (\phi \Rightarrow \neg \psi)</math>
 
; Solution.
: 
 
:# Lewa strona jest fałszywa jedynie gdy <math>\phi</math> oraz
<math>\psi</math> są wartościowane na 0. Prawa strona jest fałszywa
wtedy i tylko wtedy kiedy <math>\neg \phi</math> jest wartościowane na
1 oraz <math>\psi</math> 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 <math>\phi</math> oraz
<math>\psi</math> są wartościowane na 0, a więc jest równoważna lewej.
 
:# Lewa strona jest prawdziwa jedynie gdy <math>\phi</math> oraz
<math>\psi</math> są wartościowane na 1. Prawa strona jest prawdziwa
wtedy i tylko wtedy kiedy <math>\neg (\phi \Rightarrow \neg \psi)</math> jest wartościowane na
1, więc wtedy gdy <math>(\phi \Rightarrow \neg \psi)</math> jest wartościowane na 0. To z kolei
zdarzyć się może jedynie gdy <math>\phi</math> jest wartościowane na 1
i <math>\neg \psi</math> na 0, a więc wtedy gdy zarówno <math>\phi</math> jak i
<math>\psi</math> 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 <math>\wedge</math> lub <math>\vee</math> można zastąpić równoważną formułą w
której jedynymi spójnikami są <math>\Rightarrow</math> oraz <math>\neg</math>. 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.
 
{{cwiczenie|[Uzupelnij]||
 
Udowodnij następujące równoważności
 
# <math>\neg \neg p \equiv p</math>
 
# <math>p\Rightarrow q \equiv \neg p \vee q</math>
 
# <math>p \Rightarrow (q \Rightarrow r) \equiv (p \wedge q) \Rightarrow r</math>
 
# <math>\neg( p \wedge q) \equiv \neg p \vee \neg q</math>
 
# <math>\neg( p \vee q) \equiv \neg p \wedge \neg q</math>
 
# <math>p \wedge (q \vee r) \equiv (p \wedge q) \vee (p\wedge r)</math>
 
# <math>p \vee (q \wedge r) \equiv (p \vee q) \wedge (p\vee r)</math>
 
# <math>(p \Rightarrow q) \Rightarrow (\neg p \Rightarrow \neg q)</math>
 
; Solution.
: Przedstwiamy przykładowe dowody kilku pierwszych równoważności.
 
:# Jeśli <math>p</math> jest wartościowane na 1, to zgodnie z tabelą dla negacji [[##eq:tabeleInterpretacjiKRZ|Uzupelnic eq:tabeleInterpretacjiKRZ|]]
<math>\neg p</math> jest wartościowane na 0 i <math>\neg \neg p</math> jest wartościowane na 1. Jeśli <math>p</math> jest wartościowane
na 0 to <math>\neg p</math> jest wartościowane na 1 i <math>\neg \neg p</math> jest wartościowane na 0. Formuły przyjmują
te same wartości dla każdego wartościowania więc są równoważne.
 
:# Jedyną możliwością aby lewa strona była fałszywa jest
aby <math>p</math> było wartościowane na 1, a <math>q</math> na 0. Prawa
stona jest fałszywa jedynie gdy <math>\neg p</math> oraz <math>q</math> są wartościowane
na 0. Czyli prawa strona jest fałszywa jedynie
gdy <math>p</math> jest wartościowane na 1 i <math>q</math> na 0. Formuły są więc
równoważne.
 
:# Analogicznie do poprzedniego punktu łatwo się
przekonać, że jedynym wartościowaniem które falsyfikuje lewą
stronę jest takie które wartościuje <math>p</math> i <math>q</math> na 1 oraz <math>r</math>
na 0. Tą samą własność ma formuła po prawej stronie, więc
formuły są równoważne.
 
:# Przykład rozwiązania przez rozważenie wszystkich
możliwości
 
<center><math>
 
\begintabular {|c|c|c|c|c|c|c|}\hline
</math>p<math> & </math>q<math> & </math>p q<math> & </math> (p q)<math>& </math> p<math> & </math> q<math>&  </math>  p  q<math>\\\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}
</math></center>
 
W pierwszych dwóch kolumnach są zapisane wartościowania
zmiennych <math>p</math> i <math>q</math> 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.
 
:# W równoważności z poprzedniego punktu, podstawiąjąc za <math>p</math>
formułę <math>\neg p</math> oraz za <math>q</math> formułę <math>\neg q</math> otrzymamy
równoważność
 
<center><math>
 
\neg( \neg p \wedge \neg q) \equiv \neg \neg p \vee \neg \neg
q.
</math></center>
 
Stosując dwukrotnie równoważność z pierwszego punktu do prawej strony
otrzymujemy
 
<center><math>
 
\neg( \neg p \wedge \neg q) \equiv  p \vee    q.
</math></center>
 
Negując tą równoważność obustronnie otrzymamy
 
<center><math>
 
\neg \neg( \neg p \wedge \neg q) \equiv\neg(  p \vee    q).
</math></center>
 
Stosując równoważność z pierwszego punktu do lewej strony
otrzymamy szukaną równoważność.
 
}}
 
{{cwiczenie|[Uzupelnij]||
 
Sprawdź które z następujących formuł są tautologiami
 
# <math>( (p \vee r)\wedge( q \vee \neg r) )\Rightarrow (p \vee q)</math>
 
# <math>(p \vee q) \Rightarrow ( (p \vee r)\wedge( q \vee \neg r)
)</math>
 
# <math>( (p \wedge r)\vee( q \wedge \neg r) )\Rightarrow (p \wedge
q)</math>
 
# <math>(p \wedge q) \Rightarrow ( (p \wedge r)\vee( q \wedge \neg r)
)</math>
 
; Solution.
: 
 
:# Spróbujmy znaleźć wartościowanie które falsyfikuje tą
formułę. Skoro implikacja ma być fałszywa to formuła <math>(p \vee q)</math> (czyli następnik) musi być
fałszywa. Tak jest tylko wtedy kiedy zarówno <math>p</math> jak i <math>q</math> są
fałszywe. Zobaczmy co się wtedy dzieje z poprzednikim implikacji,
czyli formułą
 
<center><math>
 
(p \vee r)\wedge( q \vee \neg r).
</math></center>
 
Jeśli teraz ustalimy <math>r</math> na fałsz to <math>(p \vee q)</math> będzie
fałszywe a jeśli ustalimy <math>r</math> na
prawdę to <math>( q \vee \neg r)</math> 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ą.
 
:# Formuła nie jest tautologią. Wystarczy wartościować <math>p</math> i
<math>r</math> na prawdę i <math>q</math> na fałsz.
 
:# Formuła nie jest tautologią. Wystarczy wartościować <math>p</math> i
<math>r</math> na prawdę i <math>q</math> na fałsz.
 
:# Przykład rozwiązania przez rozważenie wszystkich
możliwości
 
<center><math>
 
\begintabular {|c|c|c|c|c|c|c|c|}\hline
</math>p<math> & </math>q<math> & </math>r<math> &</math>(p  q)<math> &</math> (p  r)<math>&</math> ( q  r)<math>
&</math> (p  r)( q  r)<math>& </math>(p  q)  ( (p  r)( q  r))<math>\\\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}
</math></center>
 
W kolumnie odpowiadającej badanej formule są same 1, więc
jest ona tautologią.
 
}}
 
Binarne spójniki logiczne interpretowaliśmy jako funkcje z <math>\mathbb{B}
\times \mathbb{B} \rightarrow \mathbb{B}</math>. 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.
 
<center><math>
 
\begintabular {|c|c|c|c|c|c||c|}\hline
Numer & </math>p<nowiki>=</nowiki>0<math> &</math> p<nowiki>=</nowiki>0<math> &</math> p<nowiki>=</nowiki>1<math> &</math> p<nowiki>=</nowiki>1<math> && \\
funkcji& </math>q<nowiki>=</nowiki>0<math> & </math>q<nowiki>=</nowiki>1<math> & </math>q<nowiki>=</nowiki>0<math> & </math>q<nowiki>=</nowiki>1<math> && \\ \hline
0 & 0 & 0 & 0 & 0 && </math>F<math>\\
1 & 0 & 0 & 0 & 1 && \\
2 & 0 & 0 & 1 & 0 && </math>(p  q)<math>\\
3 & 0 & 0 & 1 & 1 && </math>p<math> \\
4 & 0 & 1 & 0 & 0 && </math> (q p)<math> \\
5 & 0 & 1 & 0 & 1 && </math>q<math> \\
6 & 0 & 1 & 1 & 0 && </math>XOR<math> \\
7 & 0 & 1 & 1 & 1 &&  \\
8 & 1 & 0 & 0 & 0 && </math>NOR<math> \\
9 & 1 & 0 & 0 & 1 &&  \\
10& 1 & 0 & 1 & 0 && </math> q<math> \\
11& 1 & 0 & 1 & 1 && </math> q  p<math> \\
12& 1 & 1 & 0 & 0 && </math>  p <math>\\
13& 1 & 1 & 0 & 1 && </math> p  q <math>\\
14& 1 & 1 & 1 & 0 && </math> NAND<math> \\
15& 1 & 1 & 1 & 1 && </math>T <math>\\\hline
\endtabular  \hspace{1cm}
</math></center>
 
Spójnik binarny <math>\circ</math> będziemy nazywać "przemiennym" jeśli zachodzi
następująca równoważność
 
<center><math>
 
p \circ q \equiv q \circ p
</math></center>
 
{{cwiczenie|[Uzupelnij]||
 
Sprawdź następujące równoważności
 
# <math>x NAND y \equiv \neg (x \wedge y)</math>
 
# <math>x NOR y \equiv \neg (x \vee y)</math>
 
# <math>x XOR y \equiv \neg (x \Leftrightarrow y)</math>
 
; Solution.
:  }}
 
{{cwiczenie|[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
 
<center><math>
 
\begintabular {|c|c c|}\hline
& 0 & 1 \\\hline
0 & 0 & 1 \\
1 & 1 & 1 \\\hline
\endtabular .
</math></center>
 
Jaką własność musi posiadać tabela aby spójnik definiowany przez nią był
przemienny?
 
; Solution.
: Dla przemienności spójnika <math>\circ</math> istotne jest aby <math> 1\circ 0 = 0 \circ 1</math>. Dla pozostałych
przypadków wartościowań równoważnośc [[##eq:przemienność|Uzupelnic eq:przemienność|]]
jest zawsze spełniona. Każdy spójnik binarny możemy
zdefiniować za pomocą tabelki kwadratowej, np. alternatywę
zdefiniowaliśmy jako
 
<center><math>
 
\begintabular {|c|c c|}\hline
& 0 & 1 \\\hline
0 & 0 & 1 \\
1 & 1 & 1 \\\hline
\endtabular .
</math></center>
 
Warunek przemienności oznacza, że wartość w polu o
współrzędnych <math>(0,1)</math> jest równa wartości w polu o
współrzędnych <math>(1,0)</math>. Takich tabel jest 8, więc mamy 8
spójników przemiennych. Nietrudno je teraz odnaleźć w tabeli
[[##defn:spójniki|Uzupelnic defn:spójniki|]]. Są to
 
:# <math>F</math>
 
:# <math>\wedge</math>
 
:# <math>XOR</math>
 
:# <math>\vee</math>
 
:# <math>NOR</math>
 
:# <math>\Leftrightarrow</math>
 
:# <math>NAND</math>
 
:# <math>T</math>
 
}}
 
Spójnik binarny <math>\circ</math> będziemy nazywać "łącznym" jeśli zachodzi
następująca równoważność
 
<center><math>
 
p \circ (q \circ r) \equiv    (p \circ q) \circ r.
</math></center>
 
Jeśli spójnik <math>\circ</math> jest łączny to dowolne dwie formuły, które są zbudowane
jedynie ze spójników <math>\circ</math> 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.
 
{{cwiczenie|[Uzupelnij]||
 
Udowodnij, że następujące spójniki są łączne
 
# <math>\vee</math>
 
# <math>\wedge</math>
 
# <math>\Leftrightarrow</math>
 
# <math>XOR</math>
 
; Solution.
: 
 
:# Formuła <math>(p \vee q) \vee r</math> jest fałszywa jedynie
wtedy gdy <math>p</math>,<math>q</math> i <math>r</math> są wartościowane na fałsz. Tak
samo jest dla formuły <math>p \vee( q \vee r )</math> więc są one
równoważne.
 
:# Formuła <math>(p \wedge q) \wedge r</math> jest prawdziwa jedynie
wtedy gdy <math>p</math>,<math>q</math> i <math>r</math> są wartościowane na prawdę. Tak
samo jest dla formuły <math>p \wedge( q \wedge r )</math> więc są one
równoważne.
 
:# Zbadamy równoważność formuł <math>(p \Leftrightarrow q) \Leftrightarrow r</math>
i <math> p \Leftrightarrow(q \Leftrightarrow r)</math> za pomocą tabeli
 
<center><math>
 
\begintabular {|c|c|c|c|c|c|c|}\hline
</math>p<math> &</math> q<math> &</math> r <math>&</math>(p  q)<math> & </math>(p  q)  r<math>& </math>(q  r )<math>&</math> p (q  r)<math>\\\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}
</math></center>
 
Kolumna 4 i 6 są identyczne więc odpowiadające im
formuły są równoważne. Spójnik <math>\Leftrightarrow</math> jest więc łączny.
 
:# ...
 
}}
 
Możemy również rozważać spójniki 3 i więcej argumentowe. Spójnik
<math>k</math>-argumetowy powinien odpowiadać funkcji <math>\mathbb{B}^k \rightarrow \mathbb{B}</math>.
ład
W poniższej tabeli przedstawiamy przykład spójnika trójargumentowego
 
<center><math>
 
\begintabular {|c c c|c||}\hline
</math>p<math> & </math>q<math> & </math>r<math> &</math>(p, q,r)<math> \\\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}
</math></center>
 
ład
 
{{cwiczenie|[Uzupelnij]||
 
Udowodnij, że różnych spójników <math>k</math>-argumentowych jest dokładnie
<math>2^{2^k}</math>.
 
; 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
<math>\mathbb{B}</math>. Na przykład formuła <math>p \Rightarrow (q\Rightarrow r)</math> wyznacza funkcję
<math>f_{p \Rightarrow (q\Rightarrow r)}</math> opisaną poniższą tabelą
 
<center><math>
 
\begintabular {|c|c|c|c|}\hline
p & q & r & </math>f_{p  (q r)}<math> \\\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
</math></center>
 
Mówimy, wtedy że formuła <math>\phi</math> definuje funkcję <math>f_{\phi}</math>.
 
Skończony zbiór funkcji boolowskich <math>\Gamma</math> 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 <math>\Gamma</math>.
 
{{twierdzenie|[Uzupelnij]||
 
Zbiór <math>\{\wedge, \vee, \neg\}</math> jest funkcjonalnie pełny.
}}
 
{{dowod|[Uzupelnij]||
 
}}
 
{{twierdzenie|[Uzupelnij]||
 
Zbiory <math>\{\wedge,  \neg\}</math>, <math>\{\vee,  \neg\}</math> są funkcjonalnie pełne.
}}
 
{{dowod|[Uzupelnij]||
 
}}
 
Udowodnij, że zbiór <math>\{\Rightarrow,  \neg\}</math> jest funkcjonalnie
pełny.
 
{{twierdzenie|[Uzupelnij]||
 
Zbiór <math>\{NOR\}</math> jest funkcjonalnie pełny.
}}
 
Udowodnij, że zbiór <math>\{NAND\}</math> jest funkcjonalnie pełny.
 
{{cwiczenie|[Uzupelnij]||
 
Zdefiniuj alternatywę przy pomocy samej implikacji.
 
; Solution.
: Łatwo sprawdzić że formuła <math>p \Rightarrow (p \Rightarrow q)</math> jest równoważna
formule <math>p\vee q</math>.
}}
 
Jakie funkcje binarne da się zdefiniować przy pomocy samej
implikacji?
 
{{cwiczenie|[Uzupelnij]||
 
Udowodnij, że poniższe zbiory nie są funkcjonalnie pełne
 
# <math>\{\wedge\}</math>
 
# <math>\{\vee\}</math>
 
# <math>\{\Leftrightarrow\}</math>
 
# <math>\{XOR\}</math>
 
; Solution.
: 
 
:# Oznaczmy zbiór formuł w których jedynym spójnikiem jest <math>\wedge</math> przez
<math>F_\wedge</math>. Udowodnimy, że każda formuła z <math>F_\wedge</math> przyjmuje zawsze wartość 1, jeśli jej zmienne są
wartościowane na 1. Rozmiarem formuły będziemy nazywać liczbę wystąpień spójnika <math>\wedge</math> w formule.
Dowód będzie indukcyjny ze względu na
rozmiar formuły.
 
Baza indukcji: Każda formuła z <math>F_\wedge</math> o rozmiarze 0 jest postaci <math>x</math>, gdzie
<math>x</math> jest zmienną. Wobec tego przy wartościowaniu zmiennych na 1 formuła <math>x</math> też jest
wartościowana na 1. A więc każda formuła o rozmiarze 0 ma postulowaną własność.
 
Krok indukcyjny: Ustalmy dowolne <math>n>0</math> i przyjmijmy, że
wszystkie formuły o mniejszym rozmiarze mają postulowaną
własność. Niech <math>\nu</math> będzie dowolną formułą z <math>F_\wedge</math> o rozmiarze
<math>n</math>. Skoro <math>n>1</math> to <math>\nu</math> musi być postaci <math>\phi \wedge
\psi</math>. Rozważmy wartościowanie które wszyskim zmiennym
przypisuje wartość 1. Ponieważ rozmiary <math>\phi</math> oraz <math>\psi</math>
są silnie mniejsze od <math>n</math> to z założenia indukcyjnego
otrzymujemy, że dla naszego wartościowania obie przyjmują
wartość 1. Wobec tego zgodnie z tabelą
[[##eq:tabeleInterpretacjiKRZANDOR|Uzupelnic eq:tabeleInterpretacjiKRZANDOR|]] cała formuła <math>\phi \wedge
\psi</math> też przyjmuje wartość 1. Dowiedliśmy więc, że każda
formuła o rozmiarze <math>n</math> ma postulowaną własność.
 
Wiemy już że każda <math>F_\wedge</math> przyjmuje zawsze wartość 1, jeśli jej zmienne są
wartościowane na 1. Wobec tego niemożliwe jest zdefiniowanie
np. spójnika <math>F</math> gdyż definująca go formuła musiałby
przyjąć wartość 0 na takim wartościowaniu.
 
:# Dowód analogiczny do poprzedniego.
 
}}
 
{{cwiczenie|[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 <math>\Leftrightarrow</math>
}}
 
{{cwiczenie|[Uzupelnij]||
 
(z wykładu prof. P.M.Idziaka)
Niech <math>F_n</math> oznacza ilość boolowskich funkcji <math>n</math> argumetnowych,
a <math>P_n</math> ilość boolowskich funkcji <math>n</math> argumentowych, takich że
przy pomocy każdej z nich da się zdefiniować dowolną funkcję
boolowską (czyli jeśli <math>\circ</math> jest takim spójnikiem to zbiór
<math>\{\circ\}</math> jest funkcjonalnie pełny). Udowdnij istenienie
poniższej granicy i wyznacz jej wartość
 
<center><math>
 
\lim_{n \rightarrow \infty} \frac{P_n}{F_n}
</math></center>
 
; 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
[[##thm:AndOrNegFP|Uzupelnic thm:AndOrNegFP|]] jest w pewnej standartowej postaci - formuła
jest alternatywą formuł które są koniunkcjami literałów.
Przypomnijmy, że dla <math>p \Rightarrow q</math> zbudujemy formułę
 
<center><math>
 
(p \wedge q) \vee (\neg p \wedge q) \vee (\neg p \wedge \neg q).
</math></center>
 
Formuła jest w dyzjunktywnej postaci normalnej (DNF) jeśli jest alternatywą formuł które są koniunkcjami
literałów. Czyli wtedy gdy jest postaci
 
<center><math>
 
\phi_1\vee \dots \vee \phi_n
</math></center>
 
oraz każda z formuł <math>\phi_i</math> jest koniunkcją literałów, czyli jest postaci
 
<center><math>
 
l_1^i \wedge \dots \wedge l_k^i
</math></center>
 
dla pewnych literałów <math>l_1^i, \dots,l_k^i</math>
 
{{twierdzenie|[Uzupelnij]||
 
Dla każedej formuły istnieje równoważna formuła w DNF.
}}
 
{{dowod|[Uzupelnij]||
 
Wynika bezpośrednio z konstrukcji w dowodzie twierdzenia
[[##thm:AndOrNegFP|Uzupelnic thm:AndOrNegFP|]].
}}
 
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.
}}
 
{{dowod|[Uzupelnij]||
 
}}
 
{{cwiczenie|[Uzupelnij]||
 
Jak sprawdzić, czy formuła w CNF jest tautologią?
 
; Solution.
: Niech rozważaną formułą będzie
 
<center><math>
 
\phi_1\wedge \dots \wedge \phi_n
</math></center>
 
Aby była tautologią konieczne jest aby każda z formuł <math>\phi_i</math> była tautologią.
Ponieważ każda z formuł <math>\phi_i</math> jest alternatywą literałów to jest tautologią jedynie wtedy
jeśli istnieje taki literał który występuje w <math>\phi_i</math> zarówno pozytywnie (czyli jako zmienna)
jak i negatywnie (czyli jako zanegowana zmienna).
}}
 
{{cwiczenie|[Uzupelnij]||
 
Dla poniższych formuł wypisz ich najkrótsze równoważne formuły w
CNF
 
# <math>p \Leftrightarrow q</math>
 
# <math>p \Rightarrow (q \Rightarrow p)</math>
 
# <math>(p \Rightarrow q) \Rightarrow p</math>
 
# <math>(p \vee a \vee b) \wedge (\neg q \vee \neg a) \wedge (r \vee \neg b \vee \neg
c) \wedge (c \vee p))</math>
 
# <math>(p \wedge q) \vee (r \wedge s)</math>
 
; 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 <math>\phi</math> jest tautologią wtedy i tylko wtedy kiedy formuła
<math>\neg \phi</math> nie jest spełnialna.
}}
 
{{dowod|[Uzupelnij]||
 
Przypuśćmy, że formuła <math>\phi</math> jest tautologią. Wtedy dla każdego wartościowania <math>v</math> mamy
<math>v(\phi)=1</math>. Stąd otrzymujemy że dla każdego wartościowania <math>v</math> mamy<math>v(\neg \phi)=0</math>, a więc
nie istnieje wartościwanie, które spełnia <math>\neg \phi</math>, czyli formuła ta nie jest spełnialna.
 
Przypuśćmy, że formuła <math>\neg \phi</math> nie jest spełnialna, czyli nie istnieje wartościowanie <math>v</math>
takie, że <math>v(\neg \phi)=0</math>. Wynika stąd, że dla każdego wartościowania mamy <math>v(\phi)=1</math>, a więc <math>\phi</math> jest tautologią.
}}
 
{{cwiczenie|[Uzupelnij]||
 
Sprawdź spełnialność następujących formuł
 
# <math>(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee \neg p)</math>
 
# <math>(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee  p)</math>
 
; 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 <math>I_\Rightarrow</math> to zbiór tych formuł które da się dowodnić
przy pomocy reguły MP z aksjomatów S i K.
Aksjomaty <math>I_\Rightarrow</math>
 
# <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math> (formuła ta jest nazywana
aksjomatem K)
 
# <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow
(\phi \Rightarrow \nu) \right)</math> (formuła ta jest nazywana
aksjomatem S)
 
W pełnej wersji logiki intucjonistycznej
pojawiają się również aksjomaty dla spójników <math>\wedge, \vee</math> oraz <math>\neg</math>.
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ą
<math>\Rightarrow</math> da się udowodnić przy pomocy aksjomatów
[[##defn:AksjomatyIntImp|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ń.
}}
 
{{dowod|[Uzupelnij]||
 
Każdy dowód twierdzenia logiki inuicjonistycznej jest równocześnie dowodem
twierdzenia klasycznego rachunku zdań.
}}
 
Implikacja w drugą stronę nie zachodzi. Istnieją formuły zbudowane
jedynie przy pomocy <math>\Rightarrow</math>, które nie należą do <math>I_\Rightarrow</math> pomimo
że są twierdzeniami klasycznego rachunku zdań. Przykładem takiej formuły jest prawo
Pierce'a:
 
<center><math>
 
((p \Rightarrow q) \Rightarrow p ) \Rightarrow p
</math></center>
 
W zadaniu [[##zad:aksjomatyTatuologie|Uzupelnic zad:aksjomatyTatuologie|]] pokazaliśmy, że formuła ta jest w istocie tautologią
więc w myśl twierdzenia Posta [[##thm:zupełnośćPost|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 [[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]], a więc wymaga
używania spójnika <math>\neg</math>.
 
Aby udowodnić twierdzenie [[##thm:PrawoPiercea|Uzupelnic thm:PrawoPiercea|]] zdefiniujemy
jeszcze jedną logikę którą nazwiemy <math>I_3</math>. Podobnie do
[[##defn:matrycaBool|Uzupelnic defn:matrycaBool|]] zdefiniujemy matrycę tym razem 3-elementową.
 
Matrycą <math>\mathbb{M}_3</math> będziemy nazywać zbiór trójelementowy
<math>M_3=\{0,1,2\}</math> w którym 2 jest wyróżnioną wartością prawdy, wraz z
funkcją odpowiadają za interpretacje <math>\Rightarrow</math> zdefiniowaną następująco
 
<center><math>
 
\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}
</math></center>
 
W przypadku rozważanej matrycy <math>\mathbb{M}_3</math> wartościowanie będzie
funkcją przypisującą zmiennym zdaniowym elementy zbioru <math>M_3</math>.
Podobnie jak dla logiki klasycznej wartościowanie zmiennych
rozszzerzamy na wartościowanie formuł zgodnie z tabelą
[[##eq:tabeleInterpretacjiInt3|Uzupelnic eq:tabeleInterpretacjiInt3|]].
 
ład
Dla wartościowania <math>v</math> takiego, że <math>v(p)=2, v(q)=1, v(r)=0</math>
formuła
 
<center><math>
 
(p \Rightarrow q) \Rightarrow r
</math></center>


przyjmuje wartość 0.
  nie, nie, tak
ład


Tautologią logiki <math>I_3</math> będziemy nazywać każdą formułę
<quiz>
implikacyjną,
Czwarty z kolei wyraz rozwinięcia w szereg Maclaurina funkcji <math>f(x)=\cos 2x</math> to
która przy każdym wartościowaniu zmiennych w <math>M_3</math> przyjmuje
<wrongoption><math>-\frac{2^6}{6!}</math></wrongoption>
wartość 2.
 
<wrongoption><math>\frac{2^6}{6!}x^6</math></wrongoption>
 
<rightoption><math>\frac{-4}{45}x^6</math></rightoption>
</quiz>


{{cwiczenie|[Uzupelnij]||
  nie, nie, tak


Udowodnij, że aksjomaty S i K są tautologiami <math>I_3</math>.
<quiz>
Szósty z kolei wyraz rozwinięcia w szereg Taylora funkcji <math>f(x)=\frac{1}{2+x}</math> o środku w <math>x_0=0</math> wynosi
<wrongoption><math>\frac{-1}{64}x^6</math></wrongoption>
 
<rightoption><math>\frac{-1}{64}x^5</math></rightoption>
 
<wrongoption><math>\frac{1}{2}x^6</math></wrongoption>
</quiz>


; Solution.
   nie, tak, nie
:   }}


{{cwiczenie|[Uzupelnij]||
<quiz>
Sumujemy cztery kolejne wyrazy rozwinięcia w szereg Taylora funkcji <math>\sqrt{x}</math> ośrodku w <math>x_0=1</math> Współczynnik przy <math>x</math> wynosi
<rightoption><math>\frac{15}{16}</math></rightoption>
 
<wrongoption><math>\frac{5}{16}</math></wrongoption>
 
<wrongoption><math>\frac{1}{16}</math></wrongoption>
</quiz>


Udowodnij, że jeśli formuła postaci <math>\phi \Rightarrow \psi</math> oraz formuła <math>\phi</math>
  tak, nie, nie
są tautologiami <math>I_3</math> to formuła <math>\psi</math> jest tautologią <math>I_3</math>.


; Solution.
5555555555555555555555555555555555555555555555555555
:  }}


{{cwiczenie|[Uzupelnij]||
==Szereg potęgowy. Trygonometryczny szereg Fouriera. Test==


Udowodnij, że każde twierdzenie logiki <math>I_\Rightarrow</math> jest
tautologią <math>I_3</math>.


{hint}{1}
101010101010101010101010101010101010101010101010101010101010
; Hint .
: Przeprowadź rozumowanie indukcyjne ze względu na długość dowodu.
Pomocne będą poprzednie zadania.


; Solution.
==Wielowymiarowa całka Riemanna. Test==
:  }}


{{cwiczenie|[Uzupelnij]||


Sprawdź, czy prawo Pierce'a jest tautologią <math>I_3</math>.
1111111111111111111111111111111111111111111111111111
{hint}{1}
; Hint .
: Nie jest.


; Solution.
==Twierdzenie Fubiniego. Twierdzenie o zmianie zmiennych. Test==
: Dla wartościowania <math>v</math> takiego, że <math>v(p)=1</math> i <math>v(q)=0</math> kolejne
fomruły przyjmują następujace wartości


:# <math>v(p\Rightarrow q) =0</math>


:# <math>v((p\Rightarrow q)\Rightarrow p) =2</math>
1212121212121212121212121212121212121212121212121212121212


:# <math>v(((p\Rightarrow q)\Rightarrow p)\Rightarrow p) =1</math>
==Całki krzywoliniowe. Twierdzenie Greena. Test==


Wobec tego prawo Pierce'a nie jest tautologią <math>I_3</math> gdyż
wyróżnioną wartością prawdy <math>I_3</math> w jest 2.
}}


Podsumujmy wyniki powyższych zadań. Wskazaliśmy logikę <math>I_3</math>
1414141414141414141414141414141414141414141414141414
taką, że każda twierdzenie intuicjonizmu jest tautologią <math>I_3</math>.
Skoro prawo Pierce'a nie jest tautologią <math>I_3</math> to nie jest też
twierdzeniem <math>I_\Rightarrow</math>.


UWAGA! W dalszej części będziemy się posługiwać wyłącznie
==Równania różniczkowe zwyczajne -- przegląd metod rozwiązywania. Test==
"'logiką klasyczną"'.
{amsplain}

Aktualna wersja na dzień 22:12, 11 wrz 2023




1111111111111111111111111111111111111111111


1111111111111111111111111111111111111111111


22222222222222222222222222222222222222222

Ciągi w przestrzeniach metrycznych. Test

3333333333333333333333333333333333333333333333333333333333333

Norma. Iloczyn skalarny. Test

444444444444444444444444444444444444444444444444444444444444444

Ciągi i szeregi funkcyjne. Szereg Taylora. Test

Dany jest ciąg funkcyjny {fn} gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle f_n(x)= \left\{ \begin{array} {lll} 1 & \text{dla} & x\in[n,n+1]\\ 0 & \text{dla} & x\in \mathbb{R}\setminus[n,n+1] \end{array} \right} dla n∈ℕ Ciąg ten jest

zbieżny punktowo do f(x)≡0

zbieżny jednostajnie do f(x)≡0

zbieżny punktowo do funkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle f(x)= \left\{ \begin{array} {lll} 1 & \text{dla} & x\geq 1\\ 0 & \text{dla} & x<0 \end{array} \right} 

 tak, nie, nie

Dany jest ciąg funkcyjny {fn} gdzie

fn(x)={1−n−x1+n−xdlax>02−nx2+nxdlax<00dlax=0 dla  n=1,2,…

Ten ciąg funkcyjny jest

zbieżny jednostajnie

zbieżny punktowo ale nie jednostajnie

rozbieżny 

 nie, tak, nie

Dany jest ciąg funkcyjny fn(x)=xn dla x≥0 Ten ciąg

jest zbieżny punktowo i jego granica jest ciągła

jest zbieżny jednostajnie i jego granica jest ciągła

jest zbieżny punktowo i jego granica nie jest ciągła 

 nie, nie, tak

Dany jest szereg ∑n=1∞sin⁡nx2n(x2+1), x∈ℝ Ten szereg jest

zbieżny jednostajnie do funkcji f(x)≡0

zbieżny jednostajnie do funkcji f takiej, że 0<f(x)<3

zbieżny jednostajnie do funkcji f(x)=12(x2+1) 

 nie, tak, nie

Funkcja f(x):=∑n=1∞xnn(n+1)(x2+1) Granica limx→3f(x) wynosi

110

3

0 

 tak, nie, nie

Szereg ∑n=1∞1n(x4+4) jest

zbieżny punktowo

zbieżny jednostajnie

rozbieżny 

 nie, nie, tak

Czwarty z kolei wyraz rozwinięcia w szereg Maclaurina funkcji f(x)=cos⁡2x to

−266!

266!x6

−445x6 

 nie, nie, tak

Szósty z kolei wyraz rozwinięcia w szereg Taylora funkcji f(x)=12+x o środku w x0=0 wynosi

−164x6

−164x5

12x6 

 nie, tak, nie

Sumujemy cztery kolejne wyrazy rozwinięcia w szereg Taylora funkcji x ośrodku w x0=1 Współczynnik przy x wynosi

1516

516

116 

 tak, nie, nie

5555555555555555555555555555555555555555555555555555

Szereg potęgowy. Trygonometryczny szereg Fouriera. Test

101010101010101010101010101010101010101010101010101010101010

Wielowymiarowa całka Riemanna. Test

1111111111111111111111111111111111111111111111111111

Twierdzenie Fubiniego. Twierdzenie o zmianie zmiennych. Test

1212121212121212121212121212121212121212121212121212121212

Całki krzywoliniowe. Twierdzenie Greena. Test

1414141414141414141414141414141414141414141414141414

Równania różniczkowe zwyczajne -- przegląd metod rozwiązywania. Test

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_GR&oldid=82477”