Test b

\titleLogika dla informatyków \author{Jerzy Tiuryn\and Jerzy Tyszkiewicz\and Paweł Urzyczyn} \date{Sierpień 2006}\maketitle

Wnioskowanie o prawdziwości rozmaitych stwierdzeń jest powszednim zajęciem matematyków i nie tylko matematyków. Dlatego filozofowie i matematycy od dawna zajmowali się systematyzacją metod wnioskowania i kryteriów ich poprawności. Oczywiście ostatecznym kryterium poprawności rozumowania pozostaje zawsze zdrowy rozsądek i przekonanie o słuszności wywodu. Logika, która narodziła się jako nauka o rozumowaniu, jest jednak ważnym i potrzebnym narzędziem, które to przekonanie\boldsymbol{s}}\def\blank{\hbox\mathsf{ Błatwia.

Szczególną rolę wśród rozmaitych działów logiki zajmuje logika matematyczna, poświęcona opisowi i analizie języka matematyki oraz poprawności wnioskowań matematycznych. Jest to dyscyplina w pewnym sensie paradoksalna: będąc sama częścią matematyki, traktuje matematykę jako swój przedmiot zainteresowania. Dla\boldsymbol{s}}\def\blank{\hbox\mathsf{ Bniknięcia ,,błędnego koła musimy więc tutaj zauważyć, że logika formalna nie opisuje rzeczywistych wywodów matematyka, ale ich\boldsymbol{s}}\def\blank{\hbox\mathsf{ Bproszczone modele, które bez zastrzeżeń można\boldsymbol{s}}\def\blank{\hbox\mathsf{ Bważać za zwykłe obiekty matematyczne. Mimo tego ograniczenia, logika matematyczna dostarcza niezwykle ważnych wniosków o charakterze filozoficznym i metamatematycznym.

Logika formalna była kiedyś\Delta\vdashzoteryczną nauką z pogranicza filozofii i matematyki, potem stała się pełnoprawnym działem czystej matematyki. Jeszcze później, wraz z narodzinami informatyki, zaczęła być coraz bardziej postrzegana jako dziedzina matematyki stosowanej, a zwłaszcza podstaw informatyki.

Logika matematyczna stosowana jest dziś szeroko w informatyce. Semantyka i weryfikacja programów, teoria złożoności i teoria automatów, programowanie funkcyjne i programowanie w logice --- to tylko niektóre z działów informatyki, w których metody logiki formalnej stały się standardowym narzędziem zarówno badacza jak i praktyka.

Rachunek zdań

Jak powiedzieliśmy wyżej, logika matematyczna zajmuje się badaniem rozmaitych systemów formalnych, modelujących rzeczywiste sposoby wnioskowania matematycznego. Do najprostszych takich systemów należą różne warianty logiki zdaniowej zwanej też rachunkiem zdań. Język rachunku zdań jest bardzo prosty. Nie ma w nim wyrażeń stwierdzających jakiś stan rzeczy, zajście jakichś faktów, czy też wyrażeń orzekających o własnościach obiektów. Przedmiotem naszego zainteresowania są tu tylko możliwe zależności pomiędzy stwierdzeniami \begin{eqnarray*}zdaniami orzekającymi\end{eqnarray*}, oraz to w jaki sposób prawdziwość zdań złożonych zależy od prawdziwości ich składowych. Sens samych składowych pozostaje tu całkowicie dowolny i nieistotny. Dlatego w rachunku zdań odpowiadają im po prostu zmienne zdaniowe. Zdania złożone budujemy ze zmiennych za pomocą spójników logicznych takich jak alternatywa\/ $\vee$, koniunkcja $\wedge$, negacja $\neg$, czy \rightarrowlikacja $\to$. Wygodne są też stałe logiczne $\bot$ \begin{eqnarray*}fałsz\end{eqnarray*} i $\top$ \begin{eqnarray*}prawda\end{eqnarray*}, które można\boldsymbol{s}}\def\blank{\hbox\mathsf{ Bważać za zeroargumentowe spójniki logiczne. Dlatego nasza pierwsza definicja jest taka:

Definicja

Ustalamy pewien przeliczalnie nieskończony zbiór Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \\mbox{\small ZZ}} symboli, które będziemy nazywać zmiennymi zdaniowymi i zwykle oznaczać literami $p$, $q$, itp. Pojęcie formuły zdaniowej definiujemy przez indukcję:

• Zmienne zdaniowe oraz $\bot$ i $\top$ są formułami zdaniowymi;
• Jeśli napis Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} jest formułą zdaniową, to także napis

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \neg\var\varphi} jest formułą zdaniową;

• Jeśli napisy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} i $\psi$ są formułami zdaniowymi to

napisy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}\var\varphi\to\psi\end{eqnarray*}} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}\var\varphi\vee\psi\end{eqnarray*}} i Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}\var\varphi\wedge\psi\end{eqnarray*}} też są formułami zdaniowymi.

Inaczej mówiąc, formuły zdaniowe to\Delta\vdashlementy najmniejszego zbioru napisów Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \\F_{{\sc Z}}} , zawierającego Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \\mbox{\small ZZ}\cup\{\bot,\top\}} i takiego, że dla dowolnych</math>\var\varphi,\psi\in\\F_Szablon:\sc ZParser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle także} \neg\var\varphi,\begin{eqnarray*}\var\varphi\to\psi\end{eqnarray*}, \begin{eqnarray*}\var\varphi\vee\psi\end{eqnarray*}, \begin{eqnarray*}\var\varphi\wedge\psi\end{eqnarray*}</math> należą do Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \\F_{{\sc Z}}} .

Konwencje notacyjne: Dla pełnej jednoznaczności składni nasze formuły są w pełni nawiasowane. W praktyce wiele nawiasów pomijamy, stosując przy tym następujące priorytety:

1. Negacja;

1. Koniunkcja i alternatywa;

1. Implikacja.

Zatem na przykład wyrażenie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \neg\var\varphi\vee\psi\to\vartheta} oznacza Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}\begin{eqnarray*}\neg\var\varphi\vee\psi\end{eqnarray*}\to\vartheta\end{eqnarray*}} , ale napis Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\vee\psi\wedge \vartheta} jest niepoprawny.

Znaczenie formuł

formuły jest wartość logiczna tj. ,,prawda \begin{eqnarray*}1\end{eqnarray*} lub ,,fałsz \begin{eqnarray*}0\end{eqnarray*}. Aby określić wartość formuły zdaniowej trzeba jednak najpierw\boldsymbol{s}}\def\blank{\hbox\mathsf{ Bstalić wartości zmiennych.

Definicja

Przez wartościowanie zdaniowe rozumiemy dowolną funkcję $\varrho$, która zmiennym zdaniowym przypisuje wartości logiczne 0 lub 1. Wartość formuły zdaniowej Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} przy wartościowaniu $\varrho$ oznaczamy przez Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wfz\var\varphi\varrho} i określamy przez indukcję:

• Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wfz\bot\varrho=0} oraz Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wfz\top\varrho=1} ;
• Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wf\prooftree p \justifies \varrho \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree=\varrho\begin{eqnarray*}p\end{eqnarray*}} , gdy $p$ jest symbolem zdaniowym;
• Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wfz{\neg\var\varphi}\varrho=1-\wfz{\var\varphi}\varrho} ;
• </math>\wf\prooftree \var\varphi\vee\psi \justifies \varrho \using \text{\begin{eqnarray*}W\end{eqnarray*

\endprooftree=\max\{\wf\prooftree \var\varphi \justifies \varrho \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree,

\wf\prooftree \psi \justifies \varrho}\ \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree</math>;

• </math>\wf\prooftree \var\varphi\wedge\psi \justifies \varrho \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree=\min\{\wf\prooftree \var\varphi \justifies \varrho \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree,

\wf\prooftree \psi \justifies \varrho}\ \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree</math>;

• Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wf\prooftree \var\varphi\to\psi \justifies \varrho \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree=0} , gdy

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wfz\var\varphi\varrho=1} i Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wfz\psi\varrho=0} ;

• Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wfz{\var\varphi\to\psi}\varrho=1} , \wpp.

}}

Łatwo można zauważyć, że</math>\wf\prooftree \var\varphi\to\psi \justifies \varrho \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree = \max\{\wfz\psi\varrho,1-\wfz\var\varphi\varrho\}</math>, czyli Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wfz{\var\varphi\to\psi}\varrho=\wfz{\neg\var\varphi\vee\psi}\varrho} , dla dowolnego $\varrho$. A zatem zamiast formuły Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\to\psi} moglibyśmy z równym powodzeniem\boldsymbol{s}}\def\blank{\hbox\mathsf{ Bżywać wyrażenia Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \neg\var\varphi\vee\psi} , lub też odwrotnie: zamiast alternatywy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\vee\psi} pisać Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \neg\var\varphi\to\psi} . Nasz wybór spójników nie jest więc ,,najoszczędniejszy, w istocie w logice klasycznej wystarczy\boldsymbol{s}}\def\blank{\hbox\mathsf{ Bżywać np. \rightarrowlikacji i fałszu \begin{eqnarray*}Ćwiczenie #udacczleka\end{eqnarray*}. Czasem i my będziemy korzystać z tego wygodnego\boldsymbol{s}}\def\blank{\hbox\mathsf{ Bproszczenia, przyjmując, że ,,oficjalnymi spójnikami są tylko \rightarrowlikacja i fałsz, a pozostałe to skróty notacyjne, tj. że napisy \begin{tabbing} \hspace{3.0cm}\quad \= Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \neg\var\varphi} \qquad \= oznaczają odpowiednio \quad \=Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\to\bot} ;\\ \hspace{2.0cm}\ \ \ \> $\top$\> \ \ \ \ \> $\neg \bot$;\\ \hspace{2.0cm}\ \ \ \> Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\vee\psi} \> \ \ \ \ \> Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \neg\var\varphi\to\psi} ;\\ \hspace{2.0cm}\ \ \ \> Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\wedge\psi} \> \ \ \ \ \> Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \neg\begin{eqnarray*}\var\varphi\to\neg\psi\end{eqnarray*}} . \end{tabbing} Będziemy też czasem pisać Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\\leftrightarrow\psi} zamiast Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}\var\varphi\to\psi\end{eqnarray*}\wedge\begin{eqnarray*}\psi\to\var\varphi\end{eqnarray*}} . Zauważmy, że Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wfz{\var\varphi\\leftrightarrow\psi}\varrho=1} \wtw, gdy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wfz{\var\varphi\to\psi}\varrho=\wfz{\psi\to\var\varphi}\varrho} .

Często stosowanym skrótem jest notacja Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \bigvee_{i\in I}\var\varphi_i} oznaczająca alternatywę wszystkich formuł Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi_i} , gdzie $i$ przebiega skończony zbiór $I$. Analogicznie stosuje się zapis Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \bigwedge_{i\in I}\var\varphi_i} .

Notacja i terminologia: Jeśli Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \kl\var\varphi_\varrho=1} to piszemy też Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \varrho\models\var\varphi} lub Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \models\var\varphi[\varrho]} i mówimy, że Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} jest spełniona przez wartościowanie $\varrho$. Jeśli $\Gamma$ jest zbiorem formuł zdaniowych, oraz $\varrho \models \gamma$ dla wszystkich $\gamma \in \Gamma$, to piszemy $\varrho \models \Gamma$. Wreszcie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Gamma\models\var\varphi} oznacza, że każde wartościowanie spełniające wszystkie formuły z $\Gamma$ spełnia także formułę Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} . Mówimy wtedy, że Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} jest semantyczną konsekwencją zbioru $\Gamma$. Jeśli $\Gamma =\emptyset$ to zamiast Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Gamma\models\var\varphi} piszemy po prostu Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \models\var\varphi} . Oznacza to, że formuła Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} jest spełniona przez każde wartościowanie. Na koniec powiedzmy jeszcze, że formułami równoważnymi nazywamy takie formuły Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} i $\psi$, których wartości przy każdym wartościowaniu są takie same \begin{eqnarray*}tj. takie, że równoważność Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\\leftrightarrow\psi} jest tautologią --- patrz niżej\end{eqnarray*}.

Definicja

Formuła Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} jest spełnialna, gdy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \varrho\models\var\varphi} zachodzi dla pewnego wartościowania $\rho$. Jeśli zaś Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \models\var\varphi} to mówimy, że Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} jest tautologią \begin{eqnarray*}klasycznego\end{eqnarray*} rachunku zdań. Oczywiście Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \neg\var\varphi} jest spełnialna \wtw, gdy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} nie jest tautologią.

Tautologie rachunku zdań

Niech $S$ będzie funkcją przypisujacą symbolom zdaniowym pewne formuły. Jeśli Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} jest formułą zdaniową, to przez Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle S\begin{eqnarray*}\var\varphi\end{eqnarray*}} oznaczymy formu\lę otrzymaną z Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} przez jednoczesną zamianę każdego wystąpienia zmiennej zdaniowej $p$ na formu\lę Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle S\begin{eqnarray*}p\end{eqnarray*}} . Mówimy, że formuła Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle S\begin{eqnarray*}\var\varphi\end{eqnarray*}} jest instancją schematu zdaniowego Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} . Używamy oznaczenia Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle S\begin{eqnarray*}\Gamma\end{eqnarray*} = \{S\begin{eqnarray*}\psi\end{eqnarray*}\ |\ \psi\in\Gamma\}} .

Fakt

Jeżeli $\Gamma$ jest zbiorem formu\l\ rachunku zdań i Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Gamma\models\var\varphi} , to także Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle S\begin{eqnarray*}\Gamma\end{eqnarray*}\models S\begin{eqnarray*}\var\varphi\end{eqnarray*}} . W szczególności, jeśli Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} jest tautologią to Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle S\begin{eqnarray*}\var\varphi\end{eqnarray*}} jest też tautologią.

Dowód

{{{3}}}

Przykład

Następujące formuły \begin{eqnarray*}i wszystkie ich instancje\end{eqnarray*} są tautologiami rachunku zdań:% Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}\neg q\to\neg p\end{eqnarray*}\to \begin{eqnarray*}p\to q\end{eqnarray*}} ; Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}p\to r\end{eqnarray*}\to\begin{eqnarray*}\begin{eqnarray*}q\to r\end{eqnarray*}\to\begin{eqnarray*}p\vee q \to r\end{eqnarray*}\end{eqnarray*}} ; Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}r\to p\end{eqnarray*}\to\begin{eqnarray*}\begin{eqnarray*}r\to q\end{eqnarray*}\to\begin{eqnarray*}r\to\begin{eqnarray*}p\wedge q\end{eqnarray*}\end{eqnarray*}\end{eqnarray*}} ; \begin{eqnarray*}p\leftrightarrow\begin{eqnarray*}q\leftrightarrow r\end{eqnarray*}\end{eqnarray*}</math>; Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle p\wedge\top\\leftrightarrow p} .

Dowód

{{{3}}}

Niektóre z powyższych formu\l\ wskazują na analogię pomiędzy \rightarrowlikacją i\boldsymbol{s}}\def\blank{\hbox\mathsf{ Bporządkowaniem \begin{eqnarray*}np. zawieraniem zbiorów\end{eqnarray*}. Implikację $p\to q$ można odczytać tak: ,,warunek $p$ jest silniejszy \begin{eqnarray*}mniejszy lub równy\end{eqnarray*} od $q$. Formu\lę \begin{eqnarray*}#1\end{eqnarray*} czytamy wtedy: ,,fałsz jest najsilniejszym warunkiem \begin{eqnarray*}najmniejszym\Delta\vdashlementem\end{eqnarray*}. Formuły \begin{eqnarray*}#8\end{eqnarray*} stwierdzają, że alternatywa $p\vee q$ jest najsilniejszym warunkiem, który wynika zarówno z $p$ jak i z $q$ \begin{eqnarray*}czyli jest kresem górnym pary $\{p,q\}$, jak suma zbiorów\end{eqnarray*}. Formuły \begin{eqnarray*}#9\end{eqnarray*} wyrażają dualną własność koniunkcji: to jest kres dolny, czyli najsłabszy warunek \rightarrowlikujący oba argumenty. Prawa de Morgana \begin{eqnarray*}#11,#12\end{eqnarray*} wskazują też na analogie koniunkcja -- iloczyn, alternatywa -- suma, negacja -- dopełnienie. Ta ostatnia widoczna jest też w prawach wyłączonego środka \begin{eqnarray*}#5\end{eqnarray*}, podwójnej negacji \begin{eqnarray*}#6\end{eqnarray*} i kontrapozycji \begin{eqnarray*}#7\end{eqnarray*}.

O ile \begin{eqnarray*}#9\end{eqnarray*} wskazuje na analogię pomiędzy koniunkcją i iloczynem mnogościowym, o tyle warto zauważyć, że koniunkcja ma też własności podobne do iloczynu kartezjańskiego. Jeśli zbiór funkcji z $A$ do $B$ oznaczymy przez $[A\to B]$, to mamy \begin{eqnarray*}bardzo naturalną\end{eqnarray*} równoliczność $[A\times B\to C]\sim [A\to [B\to C]]$. Podobieństwo tego związku do formuły \begin{eqnarray*}#10\end{eqnarray*} nie jest wcale przypadkowe. Wrócimy do tego w Rozdziale #logint.

Formuła \begin{eqnarray*}#12a\end{eqnarray*} wyraża \rightarrowlikację z pomocą negacji i alternatywy i jest często bardzo przydatna, gdy np. chcemy przekształcić jakąś formułę do prostszej postaci.

Formuła \begin{eqnarray*}#2\end{eqnarray*} mówi, że dodatkowe założenie można zawsze zignorować. Formuła \begin{eqnarray*}#3\end{eqnarray*} \begin{eqnarray*}prawo Frege\end{eqnarray*} wyraża dystrybutywność \rightarrowlikacji względem siebie samej i może być odczytywana tak: jeśli $r$ wynika z $q$ w kontekście $p$, to ten kontekst może być włączony do założenia i konkluzji. Formuła \begin{eqnarray*}#4\end{eqnarray*} \begin{eqnarray*}prawo Peirce'a\end{eqnarray*} wyraża przy pomocy samej \rightarrowlikacji zasadniczą własność logiki klasycznej: możliwość rozumowania przez zaprzeczenie. Sens prawa Peirce'a widać najlepiej gdy $q$ jest fałszem, otrzymujemy wtedy prawo Claviusa: Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}\neg p\to p\end{eqnarray*}\to p} .

Warto zauważyć, że formuły w parach \begin{eqnarray*}#6\end{eqnarray*} i \begin{eqnarray*}#7\end{eqnarray*} nie są wcale tak symetryczne jak się wydaje na pierwszy rzut oka. Na przykład, pierwsza z formu\l \begin{eqnarray*}#6\end{eqnarray*} to w istocie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle p \to \begin{eqnarray*}\begin{eqnarray*}p\to\bot\end{eqnarray*}\to\bot\end{eqnarray*}} . Wiedząc, że $p$ i $p\to \bot$, natychmiast zgadzamy się na $\bot$. Intuicyjne\boldsymbol{s}}\def\blank{\hbox\mathsf{ Bzasadnienie drugiej formuły jest zaś w istocie związane z prawem \begin{eqnarray*}#5\end{eqnarray*}.

Własnością, która często\boldsymbol{s}}\def\blank{\hbox\mathsf{ Bchodzi naszej\boldsymbol{s}}\def\blank{\hbox\mathsf{ Bwagi, jest łączność równoważności \begin{eqnarray*}#13\end{eqnarray*}. W zwiazku z tym, wyrażenie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi \\leftrightarrow \psi \\leftrightarrow \vartheta} można z czystym sumieniem pisać bez nawiasów. Zwróćmy jednak\boldsymbol{s}}\def\blank{\hbox\mathsf{ Bwagę na to, że oznacza ono zupełnie co innego niż stwierdzenie że Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} , $\psi$ i $\vartheta$ są sobie nawzajem równoważne!

Ostatnie na liście są dwie równoważności wyrażające taką myśl: fałsz jest ,,elementem neutralnym dla alternatywy, a prawda dla koniunkcji. Dlatego $\bot$ możemy\boldsymbol{s}}\def\blank{\hbox\mathsf{ Bważać za ,,pustą alternatywę a $\top$ za ,,pustą koniunkcję. Powyżej pominięto dobrze znane prawa: łączność i przemienność koniunkcji i alternatywy, ich wzajemną dystrybutywność, przechodniość, zwrotność \rightarrowlikacji itp.

Postać normalna formuł

Definicja

{{{3}}}

\def\blank{\hbox\mathsf{ Btożsamiamy w myśl

Przykładu #taut-rz\begin{eqnarray*}#14\end{eqnarray*} ze stałą $\top$, a stała $\bot$ to tyle co koniunkcja z jednym pustym składnikiem. }}

Fakt

Dla każdej formuły zdaniowej istnieje równoważna jej formuła w koniunkcyjnej postaci normalnej.

<span id="

Dowód jest przez indukcję \zwn długość formuły. Symbole zdaniowe są oczywiście w postaci normalnej. Zgodnie z naszą definicją, także stałe logiczne są postaciami normalnymi. Jeśli Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} jest w postaci \begin{eqnarray*}*\end{eqnarray*}, to Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \neg\var\varphi} można przekształcić w koniunkcyjną postać normalną stosując prawa De Morgana i prawa dystrybutywności:

\hfil</math>\psi\vee\begin{eqnarray*}\vartheta\wedge\zeta\end{eqnarray*}\\leftrightarrow \begin{eqnarray*}\psi\vee\vartheta\end{eqnarray*}\wedge\begin{eqnarray*}\psi\vee\zeta\end{eqnarray*}</math>\hfil </math>\psi\vee\begin{eqnarray*}\vartheta\vee\zeta\end{eqnarray*}\\leftrightarrow \begin{eqnarray*}\psi\vee\vartheta\end{eqnarray*}\vee\begin{eqnarray*}\psi\vee\zeta\end{eqnarray*}</math>.

Podobnie postępujemy z alternatywą dwóch formuł w postaci normalnej.\footnote{Ta procedura jest niestety wykładnicza \begin{eqnarray*}Ćwiczenie [[#wziawszy}\end{eqnarray*}.]] Przypadek koniunkcji jest oczywisty, a \rightarrowlikację \Delta\vdashliminujemy z pomocą prawa #taut-rz\begin{eqnarray*}#12a\end{eqnarray*}. Szczegóły pozostawiamy Czytelnikowi. " style="font-variant:small-caps">Dowód

{{{3}}}

\subsection*{Ćwiczenia}\begin{small}

1. 1. Zbadać, czy następujące formuły są tautologiami rachunku zdań

i czy są spełnialne:

1. 1. 1. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}p\to r\end{eqnarray*}\wedge\begin{eqnarray*}q\to s\end{eqnarray*}\wedge\begin{eqnarray*}\neg p\vee \neg s\end{eqnarray*}\to \begin{eqnarray*}\neg p\vee \neg q\end{eqnarray*}} ;
      2. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}p\to q\end{eqnarray*}\vee\begin{eqnarray*}q\to r\end{eqnarray*}} ;
      3. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}\begin{eqnarray*}p\to q\end{eqnarray*}\to r\end{eqnarray*}\wedge\neg\begin{eqnarray*}\begin{eqnarray*}\begin{eqnarray*}q\to r\end{eqnarray*}\to r\end{eqnarray*}\to r\end{eqnarray*}\end{eqnarray*}} ;
      4. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}p\to q\end{eqnarray*}\wedge\begin{eqnarray*}\neg p\to r\end{eqnarray*}\to \begin{eqnarray*}r\to\neg q\end{eqnarray*}} ;
      5. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}\begin{eqnarray*}\neg p\to q\end{eqnarray*}\to r\end{eqnarray*}\to \neg\begin{eqnarray*}p\to q\end{eqnarray*}} ;
      6. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle p\vee\begin{eqnarray*}\neg p\wedge q\end{eqnarray*}\vee\begin{eqnarray*}\neg p\wedge\neg q\end{eqnarray*}} ;
      7. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}p\to q\end{eqnarray*}\vee \begin{eqnarray*}p\to \neg q\end{eqnarray*}} ;
      8. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle q\vee r\to \begin{eqnarray*}p\vee q\to p\vee r\end{eqnarray*}} ;
      9. </math>\begin{eqnarray*}p\vee q\vee r\end{eqnarray*}\wedge\begin{eqnarray*}q\vee\begin{eqnarray*}\neg p\wedge s\end{eqnarray*}\end{eqnarray*}\wedge \begin{eqnarray*}\neg s\vee q\vee r\end{eqnarray*}

\to q</math>.

1. Czy następujące zbiory formuł są spełnialne?
   1. $\{p\to \neg q,q\to \neg r,r\to \neg p\}$;
   2. $\{p\to q,q\to r,r\vee s\leftrightarrow \neg q\}$;
   3. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \{\neg\begin{eqnarray*}\neg q\vee p\end{eqnarray*}, p\vee\neg r, q\to\neg r\}} ;
   4. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \{s\to q, p\vee\neg q, \neg\begin{eqnarray*}s\wedge p\end{eqnarray*}, s\}} .

\item Czy zachodzą następujące konsekwencje?

1. $p\wedge q\to \neg r,p\models r\to \neg q$;
2. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle p\to q, p\to\begin{eqnarray*}q\to r\end{eqnarray*}\models p\to r} ;
3. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle p\to\begin{eqnarray*}q\to r\end{eqnarray*}, p\to q\models q\to r} ;
4. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}p\to q\end{eqnarray*}\to r, \neg p\models r} ;
5. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{eqnarray*}p\to q\end{eqnarray*}\to r, \neg r\models p} ;
6. $p\to q,r\to \neg q\models r\to \neg p$.

\item Dla dowolnej formuły Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} niech Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \hat{\var\varphi}} oznacza dualizację formuły Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} , tzn. formułę powstającą z Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} przez zastąpienie każdego wystąpienia $\wedge$ symbolem $\vee$ oraz każdego wystąpienia $\vee$ symbolem $\wedge$. \begin{renumerate} \item Dowieść,że Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} jest tautologią wtw, gdy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \neg\hat{\var\varphi}} jest tautologią. \item Dowieść, że Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\\leftrightarrow\psi} jest tautologią wtw, gdy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \hat{\var\varphi}\\leftrightarrow\hat{\psi}} jest tautologią. \end{renumerate}

\item Znależć formułę zdaniową Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} , która jest spełniona dokładnie przy wartościowaniach $\varrho$ spełniających warunki:

1. Dokładnie dwie spośród wartości Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \varrho\begin{eqnarray*}p\end{eqnarray*}} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \varrho\begin{eqnarray*}q\end{eqnarray*}}

i Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \varrho\begin{eqnarray*}r\end{eqnarray*}} są równe 1.

1. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \varrho\begin{eqnarray*}p\end{eqnarray*} = \varrho\begin{eqnarray*}q\end{eqnarray*} \not= \varrho\begin{eqnarray*}r\end{eqnarray*}} .

Rozwiązanie: Można to robić na różne sposoby, ale najprościej po prostu wypisać alternatywę koniunkcji, np</math>\begin{eqnarray*}p\wedge q\wedge \neg r\end{eqnarray*} \vee\begin{eqnarray*}p \wedge\neg q \wedge r\end{eqnarray*}</math>.

\item Udowodnić, że dla dowolnej funkcji $f:\{0,1\}^{k}\to \{0,1\}$ istnieje formuła Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} , w której występują tylko spójniki $\to$ i $\bot$ oraz zmienne zdaniowe ze zbioru $\{p_{1},\ldots ,p_{k}\}$, o tej własności, że dla dowolnego wartościowania zdaniowego $\varrho$ zachodzi równość Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wfz\var\varphi\varrho = f\begin{eqnarray*}\varrho\begin{eqnarray*}p_1\end{eqnarray*},\ldots, \varrho\begin{eqnarray*}p_k\end{eqnarray*}\end{eqnarray*}} . \begin{eqnarray*}Inaczej mówiąc, formuła Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} definiuje funkcję zerojedynkową $f$.\end{eqnarray*}

Wskazówka: Indukcja \zwn $k$.

\item Niech $X$ będzie dowolnym zbiorem niepustym. Dowolną funkcję Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \warpi:\\mbox{\small ZZ}\to\pot X} nazwijmy wartościowaniem w zbiorze Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \pot X} . Każdej formule zdaniowej Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} przypiszemy teraz pewien podzbiór Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wfz\var\varphi\warpi} zbioru $X$, który nazwiemy jej wartością przy wartościowaniu Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \warpi} .

• Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wfz\bot\warpi=\emptyset} oraz Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wfz\top\warpi=X} ;
• Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wf\prooftree p \justifies \warpi \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree=\warpi\begin{eqnarray*}p\end{eqnarray*}} , gdy $p$ jest symbolem zdaniowym;
• Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \wfz{\neg\var\varphi}\warpi= X-\wfz{\var\varphi}\warpi} ;
• </math>\wf\prooftree \var\varphi\vee\psi \justifies \warpi \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree=\wf\prooftree \var\varphi \justifies \warpi \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree\cup

\wf\prooftree \psi \justifies \warpi \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree</math>;

• </math>\wf\prooftree \var\varphi\wedge\psi \justifies \warpi \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree=\wf\prooftree \var\varphi \justifies \warpi \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree\cap

\wf\prooftree \psi \justifies \warpi \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree</math>;

• </math>\wf\prooftree \var\varphi\to\psi \justifies \warpi}= \begin{eqnarray*}X-\wfz{\var\varphi \using \text{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree\warpi\end{eqnarray*}

\cup\wfz\psi\warpi</math>.

Udowodnić, że formuła Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} jest tautologią rachunku zdań \wtw, gdy jest prawdziwa w Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \pot X} , tj. gdy dla dowolnego Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \warpi} jej wartością jest cały zbiór $X$.%%Rozwiazanie

\item Uzupełnić szczegóły dowodu Faktu #pania. Pokazać, że długość postaci normalnej może wzrosnąć wykładniczo w stosunku do rozmiaru formuły początkowej.

\item Niech formuła Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\to\psi} będzie tautologią rachunku zdań. Znaleźć taką formułę $\vartheta$, że:

• Zarówno Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\to\vartheta} jak i $\vartheta \to \psi$ są

tautologiami rachunku zdań.

• W formule $\vartheta$ występują tylko te zmienne zdaniowe,

które występują zarówno w Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} jak i w $\psi$.

\item Niech Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\begin{eqnarray*}p\end{eqnarray*}} będzie pewną formułą, w której występuje zmienna zdaniowa $p$ i niech $q$ będzie zmienną zdaniową nie występującą w Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\begin{eqnarray*}p\end{eqnarray*}} . Przez Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\begin{eqnarray*}q\end{eqnarray*}} oznaczmy formułę powstałą z Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\begin{eqnarray*}p\end{eqnarray*}} przez zamianę wszystkich $p$ na $q$. Udowodnić, że jeśli

\hfil Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\begin{eqnarray*}p\end{eqnarray*}, \var\varphi\begin{eqnarray*}q\end{eqnarray*} \models p\leftrightarrow q} \hfil

to istnieje formuła $\psi$, nie zawierająca zmiennych $p$ ani $q$, taka że

\hfil Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi\begin{eqnarray*}p\end{eqnarray*}\models p\leftrightarrow\psi} .\hfil

\end{small}