Zapisz do kolekcji
Zaloguj się, aby dodać zadanie do kolekcji.
Zgłoś zadanie
Dziękuję za przesłanie zgłoszenia!
Twoje zaangażowanie pomaga mi rozwijać tę stronę i tworzyć miejsce z jeszcze lepszymi materiałami.
Data publikacji: 2025-10-12 15:14:00
Udowodnij, że podane zdanie jest tautologią
$$\color{Cyan}
\neg q \land (p \implies q) \implies \neg p
$$
Rozwiążemy to zadanie na trzy sposoby, które nieco różnią się trudnością i czasochłonnością.
Tabelka
To najprostrza metoda, lecz w bardziej skomplikowanych przykładach może zająć dużo czasu, a także wiązać się z większym ryzykiem popełnienia błędu.
Polega ona na rozważeniu z osobna każdego przypadku (dla różnych wartości zdań prostych $\color{Cyan} p$ i $\color{Cyan} q$) i rozbiciu zdania złożonego na mniejsze fragmenty.
Zawsze zaczynamy od narysowania kolumn dla zdań prostych, a następnie uwzględniamy kolejne operatory logiczne pomiędzy nimi tak, aby w ostatniej kolumnie otrzymać zdanie wyjściowe. W naszym przypadku musimy rozważyć 4 przypadki:
1. $\color{Cyan} \; p=1$ i $\color{Cyan} q=1$
2. $\color{Cyan} \; p=1$ i $\color{Cyan} q=0$
3. $\color{Cyan} \; p=0$ i $\color{Cyan} q=1$
4. $\color{Cyan} \; p=0$ i $\color{Cyan} q=0$
więc będą nam potrzebne 4 wiersze. \begin{gather*}\color{Cyan} \neg q \land (p \implies q) \implies \neg p\\\\ \begin{array}{|c|c|c|c|}\hline p & q & \neg p & \neg q & p \implies q & \neg q \land (p \implies q) & \neg q \land (p \implies q) \implies \neg p \\ \hline 1 & 1 & 0 & 0 & 1 & 0 & \color{#00dd66} 1 \\\hdashline 1 & 0 & 0 & 1 & 0 & 0 & \color{#00dd66} 1 \\\hdashline 0 & 1 & 1 & 0 & 1 & 0 & \color{#00dd66} 1 \\\hdashline 0 & 0 & 1 & 1 & 1 & 1 & \color{#00dd66} 1 \\ \hline \end{array} \end{gather*} Widzimy, że w ogólnym rozrachunku, nieważne jakie wartości $\color{Cyan} p$ i $\color{Cyan} q$ przyjmiemy, otrzymamy prawdę. Wykazaliśmy tym sposobem, że podane zdanie złożone jest tautologią. $\blacksquare $
Nie wprost
Metoda ta polega na założeniu, że zdanie nie jest tautologią. Innymi słowy, zakładamy, że istnieje $\color{Cyan} p$ i $\color{Cyan} q$, dla których całe zdanie przyjmuje wartość $0$ (czyli fałsz). Wówczas, jeśli dojdziemy do sprzeczności, będzie to oznaczało, iż zdanie jest tautologią.
Zastanówmy się w jakim przypadku całe zdanie byłoby fałszywe. W naszym przykładzie występuje implikacja, a wiemy, że jest tylko jeden przypadek, dla którego zdanie typu $L \implies P$ przyjmuje 0 – gdy $L = 1 \land P = 0$: \begin{gather*}\color{#ff6600} 0\\\color{#ff6600} \overbrace{\underbrace{\color{Cyan} \neg q \land (p \implies q)} {\color{Cyan}\implies} \underbrace{\color{Cyan}\neg p}} \\\color{#ff6600} \;\; \qquad 1 \qquad \qquad \qquad \; 0 \end{gather*} \begin{align*}\color{Cyan} \neg p&\color{Cyan}\;=0 \\\color{Cyan} p&\color{Cyan}\;=1 \end{align*} Widzimy, że $\color{Cyan} p=1$, ale idźmy dalej.
Zastanawiamy się w jakim przypadku lewa strona wyrażenia jest równa $1$. Koniunkcja jest prawdą tylko gdy lewa i prawa strona jest prawdą, więc: \begin{gather*}\color{#ff6600} 1\\\color{#ff6600} \overbrace{\underbrace{\color{Cyan} \neg q} {\color{Cyan}\land} \underbrace{\color{Cyan}(p \implies q)}}\\\color{#ff6600} \;\;\, 1 \qquad \quad \;\; \, 1 \qquad \end{gather*} \begin{align*}\color{Cyan} \neg q&\color{Cyan}\;=1 \\\color{Cyan} q&\color{Cyan}\;=0 \end{align*} Widzimy, że $\color{Cyan} q=0$, więc: \begin{gather*}\color{#ff6600} 1\\\color{#ff6600} \overbrace{\underbrace{\color{Cyan}p} \implies 0}\\\color{#ff6600} 0 \qquad \quad \; \\\\\color{Cyan} p=0 \end{gather*} Aby nasza wewnętrzna implikacja była prawdą, $\color{Cyan} p$ musi być równe $0$. Widzimy jednak, że stoi to w sprzeczności z wcześniejszym wnioskiem. Nie istnieje zatem $\color{Cyan} p$ i $\color{Cyan} q$, dla których zdanie z polecenia przyjmie wartość $0$. $\blacksquare $
Przekształcenia
W tym sposobie użyjemy innych tautologii oraz praw, aby drogą przekształceń otrzymać prawdę. Ta metoda wymaga nieco lepszej znajomości ważniejszych tautologii, więc jeśli dopiero zaczynasz przygodę z logiką, nie przejmuj się jeśli ten dowód nie będzie do końca jasny.
Wychodząc od zdania zadanego w poleceniu, będziemy przekształcać „najbardziej zagnieżdżone” fragmenty na równoważne im wyrażenia. \begin{gather*}\color{Cyan} \neg q \land (p \implies q) \implies \neg p {\color{#ff6600}\begin{CD}@>{\;\;\textrm{opuszczenie implikacji}\;\;}>>\end{CD}} \neg q \land (\neg p \lor q) \implies \neg p \;\;\color{#ff6600}\longrightarrow \\\\\color{Cyan} {\color{#ff6600}\begin{CD}@>{\;\;\substack{\textrm{prawo rozdzielności koniunkcji}\\\textrm{względem alternatywy}}\;\;}>>\end{CD}} (\neg q \land \neg p) \lor (\neg q \land q) \implies \neg p {\color{#ff6600}\begin{CD}@>{\;\;\textrm{sprowadzenie do fałszu}\;\;}>>\end{CD}} (\neg q \land \neg p) \lor 0 \implies \neg p \;\;{\color{#ff6600}\longrightarrow}\;\; (\neg q \land \neg p) \implies \neg p \end{gather*} Zdanie, które otrzymaliśmy na końcu jest tautologią, znaną pod nazwą „opuszczenie koniunkcji”. Aby to pokazać, wprowadźmy $\color{#4400cc} r$ i $\color{#4400cc} s$: \begin{gather*}\color{#4400cc} r = \neg p \\\color{#4400cc} s = \neg q \\\\\color{Cyan} (\neg q \land \neg p) \implies \neg p \;\; \equiv \;\; \color{#4400cc} (s \land r) \implies s \end{gather*} Wobec tego, nasze zdanie pierwotne także jest tautologią. $\blacksquare $
Ciekawostka
Tautologia, którą należało dowieść jest określana mianem modus tollens. Jej intuicyjne rozumienie może wyglądać tak:
Jeśli wiemy, że:
- jak jest zima, to z tego wynika, że jest zimno
- nie jest zimno
to z tego wynika, że nie ma zimy. \begin{gather*}\color{#ff6600} \underbrace{\color{Cyan}\neg q} \quad {\color{Cyan}\land} \quad \underbrace{\color{Cyan}(p \implies q)}\quad {\color{Cyan}\implies} \quad \underbrace{\color{Cyan}\neg p}\\\color{#ff6600} \scriptsize \textrm{nie jest zimno} \;\;\;\;\;\;\; \textrm{jak jest zima, jest zimno} \qquad \textrm{nie ma zimy} \end{gather*}
Polega ona na rozważeniu z osobna każdego przypadku (dla różnych wartości zdań prostych $\color{Cyan} p$ i $\color{Cyan} q$) i rozbiciu zdania złożonego na mniejsze fragmenty.
Zawsze zaczynamy od narysowania kolumn dla zdań prostych, a następnie uwzględniamy kolejne operatory logiczne pomiędzy nimi tak, aby w ostatniej kolumnie otrzymać zdanie wyjściowe. W naszym przypadku musimy rozważyć 4 przypadki:
1. $\color{Cyan} \; p=1$ i $\color{Cyan} q=1$
2. $\color{Cyan} \; p=1$ i $\color{Cyan} q=0$
3. $\color{Cyan} \; p=0$ i $\color{Cyan} q=1$
4. $\color{Cyan} \; p=0$ i $\color{Cyan} q=0$
więc będą nam potrzebne 4 wiersze. \begin{gather*}\color{Cyan} \neg q \land (p \implies q) \implies \neg p\\\\ \begin{array}{|c|c|c|c|}\hline p & q & \neg p & \neg q & p \implies q & \neg q \land (p \implies q) & \neg q \land (p \implies q) \implies \neg p \\ \hline 1 & 1 & 0 & 0 & 1 & 0 & \color{#00dd66} 1 \\\hdashline 1 & 0 & 0 & 1 & 0 & 0 & \color{#00dd66} 1 \\\hdashline 0 & 1 & 1 & 0 & 1 & 0 & \color{#00dd66} 1 \\\hdashline 0 & 0 & 1 & 1 & 1 & 1 & \color{#00dd66} 1 \\ \hline \end{array} \end{gather*} Widzimy, że w ogólnym rozrachunku, nieważne jakie wartości $\color{Cyan} p$ i $\color{Cyan} q$ przyjmiemy, otrzymamy prawdę. Wykazaliśmy tym sposobem, że podane zdanie złożone jest tautologią. $\blacksquare $
Zastanówmy się w jakim przypadku całe zdanie byłoby fałszywe. W naszym przykładzie występuje implikacja, a wiemy, że jest tylko jeden przypadek, dla którego zdanie typu $L \implies P$ przyjmuje 0 – gdy $L = 1 \land P = 0$: \begin{gather*}\color{#ff6600} 0\\\color{#ff6600} \overbrace{\underbrace{\color{Cyan} \neg q \land (p \implies q)} {\color{Cyan}\implies} \underbrace{\color{Cyan}\neg p}} \\\color{#ff6600} \;\; \qquad 1 \qquad \qquad \qquad \; 0 \end{gather*} \begin{align*}\color{Cyan} \neg p&\color{Cyan}\;=0 \\\color{Cyan} p&\color{Cyan}\;=1 \end{align*} Widzimy, że $\color{Cyan} p=1$, ale idźmy dalej.
Zastanawiamy się w jakim przypadku lewa strona wyrażenia jest równa $1$. Koniunkcja jest prawdą tylko gdy lewa i prawa strona jest prawdą, więc: \begin{gather*}\color{#ff6600} 1\\\color{#ff6600} \overbrace{\underbrace{\color{Cyan} \neg q} {\color{Cyan}\land} \underbrace{\color{Cyan}(p \implies q)}}\\\color{#ff6600} \;\;\, 1 \qquad \quad \;\; \, 1 \qquad \end{gather*} \begin{align*}\color{Cyan} \neg q&\color{Cyan}\;=1 \\\color{Cyan} q&\color{Cyan}\;=0 \end{align*} Widzimy, że $\color{Cyan} q=0$, więc: \begin{gather*}\color{#ff6600} 1\\\color{#ff6600} \overbrace{\underbrace{\color{Cyan}p} \implies 0}\\\color{#ff6600} 0 \qquad \quad \; \\\\\color{Cyan} p=0 \end{gather*} Aby nasza wewnętrzna implikacja była prawdą, $\color{Cyan} p$ musi być równe $0$. Widzimy jednak, że stoi to w sprzeczności z wcześniejszym wnioskiem. Nie istnieje zatem $\color{Cyan} p$ i $\color{Cyan} q$, dla których zdanie z polecenia przyjmie wartość $0$. $\blacksquare $
Wychodząc od zdania zadanego w poleceniu, będziemy przekształcać „najbardziej zagnieżdżone” fragmenty na równoważne im wyrażenia. \begin{gather*}\color{Cyan} \neg q \land (p \implies q) \implies \neg p {\color{#ff6600}\begin{CD}@>{\;\;\textrm{opuszczenie implikacji}\;\;}>>\end{CD}} \neg q \land (\neg p \lor q) \implies \neg p \;\;\color{#ff6600}\longrightarrow \\\\\color{Cyan} {\color{#ff6600}\begin{CD}@>{\;\;\substack{\textrm{prawo rozdzielności koniunkcji}\\\textrm{względem alternatywy}}\;\;}>>\end{CD}} (\neg q \land \neg p) \lor (\neg q \land q) \implies \neg p {\color{#ff6600}\begin{CD}@>{\;\;\textrm{sprowadzenie do fałszu}\;\;}>>\end{CD}} (\neg q \land \neg p) \lor 0 \implies \neg p \;\;{\color{#ff6600}\longrightarrow}\;\; (\neg q \land \neg p) \implies \neg p \end{gather*} Zdanie, które otrzymaliśmy na końcu jest tautologią, znaną pod nazwą „opuszczenie koniunkcji”. Aby to pokazać, wprowadźmy $\color{#4400cc} r$ i $\color{#4400cc} s$: \begin{gather*}\color{#4400cc} r = \neg p \\\color{#4400cc} s = \neg q \\\\\color{Cyan} (\neg q \land \neg p) \implies \neg p \;\; \equiv \;\; \color{#4400cc} (s \land r) \implies s \end{gather*} Wobec tego, nasze zdanie pierwotne także jest tautologią. $\blacksquare $
Jeśli wiemy, że:
- jak jest zima, to z tego wynika, że jest zimno
- nie jest zimno
to z tego wynika, że nie ma zimy. \begin{gather*}\color{#ff6600} \underbrace{\color{Cyan}\neg q} \quad {\color{Cyan}\land} \quad \underbrace{\color{Cyan}(p \implies q)}\quad {\color{Cyan}\implies} \quad \underbrace{\color{Cyan}\neg p}\\\color{#ff6600} \scriptsize \textrm{nie jest zimno} \;\;\;\;\;\;\; \textrm{jak jest zima, jest zimno} \qquad \textrm{nie ma zimy} \end{gather*}