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-11 19:43:00
Udowodnij, że podane zdanie jest tautologią
$$\color{Cyan}
p \land (p \implies q) \implies q
$$
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} p \land (p \implies q) \implies q\\\\ \begin{array}{|c|c|c|c|}\hline p & q & p \implies q & p \land (p \implies q) & p \land (p \implies q) \implies q \\ \hline 1 & 1 & 1 & 1 & \color{#00dd66} 1 \\\hdashline 1 & 0 & 0 & 0 & \color{#00dd66} 1 \\\hdashline 0 & 1 & 1 & 0 & \color{#00dd66} 1 \\\hdashline 0 & 0 & 1 & 0 & \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} p \land (p \implies q)} {\color{Cyan}\implies} \underbrace{\color{Cyan}q}} \\\color{#ff6600} \; \qquad 1 \qquad \qquad \qquad 0 \\\\\color{Cyan} q=0 \end{gather*} Widzimy, że $\color{Cyan} q=0$, 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} p} {\color{Cyan}\land} \underbrace{\color{Cyan}(p \implies q)}}\\\color{#ff6600} \;\;\, 1 \qquad \quad \;\; \, 1 \qquad\\\\\color{Cyan} p=1 \end{gather*} Widzimy, że $\color{Cyan} p=1$, więc: \begin{gather*}\color{#ff6600} 1\\\color{#ff6600} \overbrace{\color{Cyan}1 \implies \underbrace{q}}\\\color{#ff6600} \qquad\;\;\;\;\, 1\\\\\color{Cyan} q=1 \end{gather*} Aby nasza wewnętrzna implikacja była prawdą, $\color{Cyan} q$ musi być równe $1$. 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} p \land (p \implies q) \implies q {\color{#ff6600}\begin{CD}@>{\;\;\textrm{opuszczenie implikacji}\;\;}>>\end{CD}} p \land (\neg p \lor q) \implies q \color{#ff6600}\longrightarrow \\\\\color{Cyan} {\color{#ff6600}\begin{CD}@>{\;\;\substack{\textrm{prawo rozdzielności koniunkcji}\\\textrm{względem alternatywy}}\;\;}>>\end{CD}} (p \land \neg p) \lor (p \land q) \implies q {\color{#ff6600}\begin{CD}@>{\;\;\textrm{sprowadzenie do fałszu}\;\;}>>\end{CD}} 0 \lor (p \land q) \implies q \;\;{\color{#ff6600}\longrightarrow}\;\; (p \land q) \implies q \end{gather*} Zdanie, które otrzymaliśmy na końcu jest niczym innym jak tautologią, znaną pod nazwą „opuszczenie koniunkcji”. Wobec tego, nasze zdanie pierwotne także jest tautologią. $\blacksquare $
Ciekawostka
Tautologia, którą należało dowieść jest określana mianem modus ponens. Jej intuicyjne rozumienie może wyglądać tak:
Jeśli wiemy, że:
- jak jest zima, to z tego wynika, że jest zimno
- jest zima
to z tego wynika, że jest zimno. \begin{gather*}\color{#ff6600} \underbrace{\color{Cyan}p} \quad {\color{Cyan}\land} \quad \underbrace{\color{Cyan}(p \implies q)}\quad {\color{Cyan}\implies} \quad \underbrace{\color{Cyan}q}\\\color{#ff6600} \scriptsize \textrm{jest zima} \;\;\;\;\;\;\; \textrm{jak jest zima, jest zimno} \qquad\quad\;\; \textrm{jest zimno} \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} p \land (p \implies q) \implies q\\\\ \begin{array}{|c|c|c|c|}\hline p & q & p \implies q & p \land (p \implies q) & p \land (p \implies q) \implies q \\ \hline 1 & 1 & 1 & 1 & \color{#00dd66} 1 \\\hdashline 1 & 0 & 0 & 0 & \color{#00dd66} 1 \\\hdashline 0 & 1 & 1 & 0 & \color{#00dd66} 1 \\\hdashline 0 & 0 & 1 & 0 & \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} p \land (p \implies q)} {\color{Cyan}\implies} \underbrace{\color{Cyan}q}} \\\color{#ff6600} \; \qquad 1 \qquad \qquad \qquad 0 \\\\\color{Cyan} q=0 \end{gather*} Widzimy, że $\color{Cyan} q=0$, 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} p} {\color{Cyan}\land} \underbrace{\color{Cyan}(p \implies q)}}\\\color{#ff6600} \;\;\, 1 \qquad \quad \;\; \, 1 \qquad\\\\\color{Cyan} p=1 \end{gather*} Widzimy, że $\color{Cyan} p=1$, więc: \begin{gather*}\color{#ff6600} 1\\\color{#ff6600} \overbrace{\color{Cyan}1 \implies \underbrace{q}}\\\color{#ff6600} \qquad\;\;\;\;\, 1\\\\\color{Cyan} q=1 \end{gather*} Aby nasza wewnętrzna implikacja była prawdą, $\color{Cyan} q$ musi być równe $1$. 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} p \land (p \implies q) \implies q {\color{#ff6600}\begin{CD}@>{\;\;\textrm{opuszczenie implikacji}\;\;}>>\end{CD}} p \land (\neg p \lor q) \implies q \color{#ff6600}\longrightarrow \\\\\color{Cyan} {\color{#ff6600}\begin{CD}@>{\;\;\substack{\textrm{prawo rozdzielności koniunkcji}\\\textrm{względem alternatywy}}\;\;}>>\end{CD}} (p \land \neg p) \lor (p \land q) \implies q {\color{#ff6600}\begin{CD}@>{\;\;\textrm{sprowadzenie do fałszu}\;\;}>>\end{CD}} 0 \lor (p \land q) \implies q \;\;{\color{#ff6600}\longrightarrow}\;\; (p \land q) \implies q \end{gather*} Zdanie, które otrzymaliśmy na końcu jest niczym innym jak tautologią, znaną pod nazwą „opuszczenie koniunkcji”. Wobec tego, nasze zdanie pierwotne także jest tautologią. $\blacksquare $
Jeśli wiemy, że:
- jak jest zima, to z tego wynika, że jest zimno
- jest zima
to z tego wynika, że jest zimno. \begin{gather*}\color{#ff6600} \underbrace{\color{Cyan}p} \quad {\color{Cyan}\land} \quad \underbrace{\color{Cyan}(p \implies q)}\quad {\color{Cyan}\implies} \quad \underbrace{\color{Cyan}q}\\\color{#ff6600} \scriptsize \textrm{jest zima} \;\;\;\;\;\;\; \textrm{jak jest zima, jest zimno} \qquad\quad\;\; \textrm{jest zimno} \end{gather*}