--- title: "Logika" lecture_number: 1 has_solutions: true has_exercises: true --- ```{include} ../_includes/sagecell-loader.md ``` # Logika :::{narration} Aby dobrze się komunikować, trzeba ustalić język i zasady w nim obowiązujące: poprawnie sformułować twierdzenie, a następnie -- korzystając z ustalonych zasad -- **udowodnić**, że jest ono prawdziwe. Zajmiemy się logiką klasyczną (dwuwartościową). ::: ## Zdania logiczne :::{prf:definition} **Zdanie logiczne** {index}`zdanie logiczne` to zdanie oznajmujące, któremu można przypisać określoną wartość logiczną. W logice klasycznej zdania dzielimy na: - prawdziwe (przypisujemy im wartość logiczną $1$) - fałszywe (o wartości logicznej $0$). Zdania nieposiadające jednoznacznej wartości logicznej (pytania, rozkazy, zdania z niepodstawioną zmienną, antynomie w rodzaju "To zdanie jest fałszywe") nie są zdaniami logicznymi. ::: ::::{prf:example} 1. "Dwa plus dwa równa się cztery." jest zdaniem logicznym. Na gruncie zwykłej arytmetyki przypiszemy mu wartość logiczną 1. 2. "Ala ma kota." jest zdaniem logicznym. Wartość logiczna tego zdania powinna odzwierciedlać naszą wiedzę na temat tego, czy Ala ma kota. 4. "Czy to jest zrozumiałe?" nie jest zdaniem logicznym - nie jest zdaniem oznajmującym. 5. "Ach, jak tu pięknie!", "Otwórz okno!" również nie są zdaniami logicznymi. 6. Jeśli nie przyjmiemy konkretnej wartości $x\in\rr$, to zdanie "$x > 0$" nie jest zdaniem logicznym. Problem w tym, że nie możemy przypisać mu jednoznacznej wartości logicznej, gdyż zależy ona od wartości zmiennej $x .$ 7. "To zdanie jest fałszywe.", "Ja teraz kłamię." też nie są zdaniami logicznymi. To **antynomie**, czyli zdania prowadzące do sprzeczności logicznej. Istotnie, jeśli przyjąć, że "To zdanie jest fałszywe." ma wartość logiczną 1, to wywnioskujemy z niego, że jest ono fałszywe, czyli ma wartość logiczną 0 -- sprzeczność. Analogicznie nie możemy przypisać temu zdaniu wartości logicznej 0. :::: :::{narration} Zdania logiczne najczęściej oznacza się małymi literami łacińskimi, zaczynając od: $p, q, r, s .$ ::: ## Funktory zdaniotwórcze :::{narration} Zdania złożone budujemy ze zdań prostych za pomocą **spójników logicznych** (**funktorów zdaniotwórczych**) {index}`funktor zdaniotwórczy`. ::: ::::{prf:definition} Dla zdań $p, q$ definiujemy: - **negację**: {index}`negacja` $\quad \Negation p$ ("nieprawda, że $p$") - **koniunkcję**: {index}`koniunkcja` $\quad p\wedge q$ ("$p$ i $q$") - **alternatywę**: {index}`alternatywa` $\quad p\vee q$ ("$p$ lub $q$") - **implikację**: {index}`implikacja` $\quad p \imply q$ ("jeśli $p$, to $q$") - **równoważność**: {index}`równoważność` $\quad p\Leftrightarrow q$ ("$p$ wtedy i tylko wtedy, gdy $q$") których wartościowanie określamy zgodnie z tabelą: :::{list-table} :class: table-auto-width :header-rows: 1 :widths: 8 8 10 10 10 12 12 * - $p$ - $q$ - $\Negation p$ - $p\wedge q$ - $p\vee q$ - $p \imply q$ - $p\Leftrightarrow q$ * - 1 - 1 - 0 - 1 - 1 - 1 - 1 * - 1 - 0 - 0 - 0 - 1 - 0 - 0 * - 0 - 1 - 1 - 0 - 1 - 1 - 0 * - 0 - 0 - 1 - 0 - 0 - 1 - 1 ::: W koniunkcji zdania $p$ i $q$ nazywają się **czynnikami**. {index}`koniunkcja; czynnik` W alternatywie zdania $p$ i $q$ nazywają się **składnikami**. {index}`alternatywa; składnik` W implikacji $p\Rightarrow q$ zdanie: - $p$ nazywamy **poprzednikiem** {index}`implikacja; poprzednik` - $q$ -- **następnikiem**. {index}`implikacja; następnik` Jeśli prawdziwa jest implikacja $p\Rightarrow q$, to mówimy, że: - $p$ jest **warunkiem wystarczającym** {index}`warunek; wystarczający` lub **dostatecznym** {index}`warunek; dostateczny` dla $q$ - $q$ jest **warunkiem koniecznym** {index}`warunek; koniczny` dla $p .$ Dla danej implikacji $p\Rightarrow q$ (którą nazywamy **prostą**) {index}`implikacja; prosta`, implikację $q\Rightarrow p$ nazywamy **odwrotną** {index}`implikacja; odwrotna`. :::: :::{prf:example} Ze zdań prostych "Ala ma kota." i "Jest pochmurno." możemy utworzyć zdania złożone: - "$\Negation$ Ala ma kota.", które możemy odczytać jako "Nieprawda, że Ala ma kota", czyli w skrócie "Ala nie ma kota." - "Ala ma kota. $\wedge$ Jest pochmurno.", czyli w skrócie zdanie "Ala ma kota i jest pochmurno." - "Ala ma kota. $\vee$ Jest pochmurno.", czyli w skrócie zdanie "Ala ma kota lub jest pochmurno." - "Ala ma kota. $\imply$ Jest pochmurno.", czyli w skrócie zdanie "Jeśli Ala ma kota to jest pochmurno.", które możemy też zapisać "To, że Ala ma kota implikuje, że jest pochmurno." - "Ala ma kota. $\Leftrightarrow$ Jest pochmurno.", czyli w skrócie zdanie "Ala ma kota wtedy i tylko wtedy, gdy jest pochmurno." lub "To, że Ala ma kota jest równoważne temu, że jest pochmurno." ::: :::{prf:remark} Budując zdania złożone z wieloma spójnikami, ograniczamy liczbę nawiasów, przyjmując priorytety (od najsilniej wiążącego): $$ \Negation \quad \gg \quad \wedge,\ \vee \quad \gg \quad \imply,\ \Leftrightarrow. $$ ::: :::{prf:example} Dzięki priorytetom zdanie ```{math} (((\Negation p) \wedge q)\imply p)\Leftrightarrow(p\vee q) ``` zapiszemy krócej jako ```{math} (\Negation p \wedge q\imply p)\Leftrightarrow p\vee q. ``` Podstawiając $p=0,\ q=1$ otrzymamy kolejno: ```{math} \begin{aligned} (1\wedge 1\imply 0) & \Leftrightarrow 0\vee 1 \\ (1\imply 0) & \Leftrightarrow 1 \\ 0 & \Leftrightarrow 1 \\ & \;\; 0 \end{aligned} ``` czyli dla tego wartościowania zdanie jest fałszywe. ::: ## Tautologie i prawa rachunku zdań :::{prf:definition} **Prawami rachunku zdań** {index}`prawo rachunku zdań` (lub **tautologiami** {index}`tautologia`) nazywamy formułę zdaniową, która jest prawdziwa dla każdego wartościowania występujących w niej zdań. **Równoważnymi** {index}`zdanie logiczne; równoważne` nazwiemy zdania logiczne $\Phi$ i $\Psi$, jeśli tautologią jest zdanie $\Phi \Leftrightarrow \Psi .$ ::: ::::{prf:example} **Prawo Dunsa Szkota** $\quad p \imply(\Negation p \imply q) \quad$ jest tautologią: :::{list-table} :class: table-auto-width :header-rows: 1 :widths: 8 8 10 14 18 * - $p $ - $ q$ - $\Negation p $ - $\Negation p \imply q$ - $p \imply (\Negation p \imply q)$ * - 0 - 0 - 1 - 0 - 1 * - 0 - 1 - 1 - 1 - 1 * - 1 - 0 - 0 - 1 - 1 * - 1 - 1 - 0 - 1 - 1 ::: W ostatniej kolumnie występują same jedynki, więc formuła jest tautologią. Prawo to mówi, że z dwóch zdań wzajemnie sprzecznych, $p$ oraz $\Negation p$, można wywnioskować dowolne zdanie $q .$ :::: :::{prf:theorem} Dla dowolnych zdań logicznych $p, q,r$ następujące zdania są tautologiami: 1. $(p\wedge p) \Leftrightarrow p \quad$ oraz $\quad p \Leftrightarrow (p\vee p ) \quad$ -- _prawa idempotentności_ 2. $\Negation(\Negation p) \Leftrightarrow p \quad$ -- _prawo podwójnej negacji_ 3. $p\vee (\Negation p)\quad$ -- _prawo wyłączonego środka_ 4. $\Negation(p\wedge(\Negation p)) \quad$ -- _prawo sprzeczności_ 5. **$\Negation(p\wedge q) \Leftrightarrow (\Negation p) \vee (\Negation q) \quad$** oraz **$\quad \Negation(p\vee q)\Leftrightarrow (\Negation p) \wedge(\Negation q) \quad$** -- _prawa de Morgana_ 6. **$(p\Rightarrow q)\Leftrightarrow ((\Negation q)\Rightarrow (\Negation p)) \quad$** -- _prawo kontrapozycji_ 7. **$\Negation(p\Rightarrow q)\Leftrightarrow (p\wedge (\Negation q)) \quad$** -- _prawo negacji implikacji_ 8. $p\wedge q \Leftrightarrow q \wedge p \quad$ oraz $\quad p\vee q \Leftrightarrow q \vee p \quad$ -- _prawa przemienności_ 9. $p\wedge (q\wedge r) \Leftrightarrow (p\wedge q)\wedge r \quad$ oraz $\quad p\vee (q\vee r) \Leftrightarrow (p\vee q)\vee r \quad$ -- _prawa łączności_ 10. **$p\wedge (q\vee r) \Leftrightarrow (p\wedge q)\vee (p\wedge r) \quad$** -- _prawo rozdzielności koniunkcji względem alternatywy_ 11. **$p\vee (q\wedge r) \Leftrightarrow (p\vee q)\wedge (p\vee r) \quad$** -- _prawo rozdzielności alternatywy względem koniunkcji_ 12. $((p\Rightarrow q)\wedge(q\Rightarrow r))\Rightarrow(p\Rightarrow r) \quad$ -- _prawo przechodniości implikacji_ 13. **$(p \Leftrightarrow q) \Leftrightarrow ((p \imply q) \wedge (q \imply p))$** ::: ## Postać normalna :::{prf:definition} Formułę zdaniową zapisaną w postaci ```{math} p _1\vee p _2 \vee \cdots \vee p _k, \qquad \text{gdzie} \qquad p _i=p_{i1}\wedge p_{i2}\wedge \cdots \wedge p_{in_i}, ``` a $p_{ij}$ są zdaniami prostymi lub ich zaprzeczeniami, nazywamy **postacią normalną alternatywno-koniunkcyjną** {index}`postać normalna; alternatywno-koniunkcyjna` (**dysjunkcyjną**). ::: :::{prf:theorem} Korzystając z praw rachunku zdań, każdą formułę zdaniową można sprowadzić do postaci normalnej alternatywno-koniunkcyjnej. ::: :::{exercise} :class: [exercise] Sprowadźmy formułę $ \Negation \big( (p \imply q) \land (r \Leftrightarrow \Negation s) \big) $ do postaci normalnej alternatywno-koniunkcyjnej. ::: :::{solution-without-reference} :class: [solution] dropdown Poniżej wykonujemy przekształcenia, za każdym razem otrzymując formuły równoważne: $$ \begin{aligned} & \Negation \big( (p \imply q) \land (r \Leftrightarrow \Negation s) \big) \\ & \Negation \big( (\Negation p \lor q) \land ((r \land \Negation s) \lor (\Negation r \land s)) \big) \\ & \Negation (\Negation p \lor q) \lor \Negation ((r \land \Negation s) \lor (\Negation r \land s)) \\ & (\Negation \Negation p \land \Negation q) \lor (\Negation (r \land \Negation s) \land \Negation (\Negation r \land s)) \\ & (p \land \Negation q) \lor ((\Negation r \lor \Negation \Negation s) \land (\Negation \Negation r \lor \Negation s)) \\ & (p \land \Negation q) \lor ((\Negation r \lor s) \land (r \lor \Negation s)) \\ & (p \land \Negation q) \lor ((\Negation r \land r) \lor (\Negation r \land \Negation s) \lor (s \land r) \lor (s \land \Negation s)) \\ & (p \land \Negation q) \lor (0 \lor (\Negation r \land \Negation s) \lor (r \land s) \lor 0) \\ & (p \land \Negation q) \lor (\Negation r \land \Negation s) \lor (r \land s) \end{aligned} $$ W kolejnych krokach: 1. Eliminujemy spójniki: Zastępujemy implikację alternatywą ($p \imply q \equiv \Negation p \lor q$) oraz rozbijamy równoważność na alternatywę dwóch koniunkcji. 2. Stosujemy I prawo de Morgana: Zamieniamy negację głównej koniunkcji na alternatywę zanegowanych składników. 3. Ponownie wykorzystujemy prawa de Morgana: Wprowadzamy negację do wnętrza nawiasów, zmieniając spójniki na przeciwne (koniunkcję na alternatywę i odwrotnie). 4. Upraszczamy podwójną negację: Usuwamy powtarzające się zaprzeczenia przy zmiennych $p$, $r$ oraz $s$, przywracając ich pierwotną formę. 5. Stosujemy prawo rozdzielności: Rozdzielamy koniunkcję względem alternatywy („mnożymy nawiasy”), aby uzyskać strukturę sumy iloczynów. 6. Redukujemy sprzeczności: Wykreślamy człony typu $a \land \Negation a$ (fałsz), ponieważ nie zmieniają one wyniku całej alternatywy. 7. Otrzymujemy postać normalną: Zapisujemy finalną formułę jako alternatywę trzech koniunkcji. ::: ## Formy zdaniowe :::{narration} Niech $X$ będzie zbiorem niepustym (o zbiorach będziemy jeszcze mówić -- na razie zadowolimy się intuicyjnym rozumieniem pojęć zbioru, elementu zbioru, należenia do zbioru $\in$). ::: :::{prf:definition} **Formą zdaniową** {index}`forma zdaniowa` lub **funkcją zdaniową** {index}`funkcja zdaniowa` zmiennej $x\in X$ nazywamy takie wyrażenie $\varphi (x)$, które staje się zdaniem logicznym (prawdziwym lub fałszywym), gdy za $x$ podstawiamy elementy ze zbioru $X .$ **Zakresem zmienności** {index}`forma zdaniowa; zakres zmienności` formy zdaniowej $\varphi(x)$ jest zbiór $X .$ Element $x_0\in X$ **spełnia** {index}`forma zdaniowa; spełniona` formę zdaniową $\varphi(x)$, jeśli $\varphi(x_0)$ jest zdaniem prawdziwym. ::: :::{prf:example} 1. Napis "$x+2$" nie jest formą zdaniową zmiennej $x\in X$ (bez względu na to jaki to zbiór), gdyż po wstawieniu za $x$ konkretnego elementu nie otrzymamy zdania logicznego. 2. Zdanie logiczne "$3 > 7$" możemy uznać za formę zdaniową zmiennej $x\in X$ (bez względu na to jaki to zbiór), choć _explicite_ nie występuje w niej zmienna $x .$ Oczywiście jest to zdanie logiczne fałszywe. ::: :::{prf:definition} **Wykresem** {index}`forma zdaniowa; wykres` formy zdaniowej w zbiorze $X$ nazywamy zbiór wszystkich elementów $x\in X$ spełniających formę zdaniową $\varphi (x)$ i oznaczmy przez ```{math} \PredicateGraph[X] \varphi = \Set{x\in X : \varphi(x)} ``` ::: :::{prf:example} Rozważmy formę zdaniową $$ \varphi(x): \ x < 0 \imply x^2 \geq 4 $$ zmiennej $x\in \rr .$ Możemy zastosować do niej prawa rachunku zdań: ```{math} \begin{aligned} x < 0 & \imply x^2 \geq 4 \\ (\Negation x < 0) & \vee x^2 \geq 4 \\ x \geq 0 & \vee |x| \geq 2 \\ x \geq 0 & \vee x \leq -2 \vee x \geq 2 \\ x \geq 0 & \vee x \leq -2. \end{aligned} ``` Stąd $ \quad \PredicateGraph \varphi = \Set{x\in \rr : \varphi(x)} =(-\infty, -2]\cup [0, +\infty); $ ::: :::{narration} Niech $X_1, X_2, \ldots, X_n$ będą zbiorami niepustymi. ::: :::{prf:definition} **Formą zdaniową** {index}`forma zdaniowa` lub **funkcją zdaniową** {index}`funkcja zdaniowa` zmiennych $x_1\in X_1,\ \ldots,\ x_n\in X_n$ nazywamy takie wyrażenie $\varphi (x_1, \ldots, x_n)$, które staje się zdaniem logicznym (prawdziwym lub fałszywym), gdy za $x_1,\ldots,x_n$ podstawiamy odpowiednio elementy zbiorów $X_1,\ldots, X_n .$ **Zakresem zmienności** {index}`forma zdaniowa; zakres zmienności` zmiennej $x_i$ jest zbiór $X_i .$ ::: :::{prf:example} Forma zdaniowa $$\varphi(x,y):\ x^2 + y^2 \leq 4 \Leftrightarrow x + y > 0$$ dwóch zmiennych $x, y \in \rr$ ::: ## Kwantyfikatory :::{prf:definition} **Kwantyfikator ogólny** {index}`kwantyfikator ogólny`, oznaczany symbolem **$\forall$**, oznacza "dla każdego ...": Zdanie "$\forall x \in X\; \varphi(x)$" jest prawdziwe, jeśli wyrażenie $\varphi(x)$ jest prawdziwe dla wszystkich $x \in X$, czyli $$ \{x \in X \colon \varphi(x)\} = X. $$ ::: :::{prf:definition} **Kwantyfikator egzystencjalny** {index}`kwantyfikator egzystencjalny`, oznaczany symbolem **$\exists$**, oznacza "istnieje ...": Zdanie "$\exists x \in X\; \varphi(x)$" jest prawdziwe, jeśli wyrażenie $\varphi(x)$ jest prawdziwe dla przynajmniej jednego $x \in X$, czyli $$ \{x \in X \colon \varphi(x)\} \neq \emptyset. $$ ::: :::{prf:example} 1. Zdanie $\quad \Forall {x \in \rr} x^2\geq 0 \quad$ jest prawdziwe -- każda liczba rzeczywista podniesiona do kwadratu jest nieujemna. 2. Zdanie $\quad \Exists{x\in \rr} x^2 + 1 = 0 \quad$ jest fałszywe -- wielomian $x^2 + 1$ nie ma pierwiastków rzeczywistych. ::: :::{prf:remark} Gdy zakres zmienności $X$ formy zdaniowej zmiennej $x$ jest określony, to: ```{math} \begin{aligned} \Forall{x} \varphi(x) & \quad \text{oznacza} \quad \forall x\in X \;\varphi(x) \\ \Exists{x} \varphi(x) & \quad \text{oznacza} \quad \exists x\in X \;\varphi(x). \end{aligned} ``` ::: :::{prf:definition} **Prawem rachunku kwantyfikatorów** {index}`prawo rachunku kwantyfikatorów` nazywamy formułę zawierającą symbole kwantyfikatorów, która jest zdaniem prawdziwym dla dowolnej interpretacji symboli i form zdaniowych w niej występujących. ::: :::{prf:theorem} Dla dowolnego zbioru niepustego $X$ i zmiennej $x\in X$, następujące formuły są prawami rachunku kwantyfikatorów: 1. $\Forall{x} \varphi(x) \Rightarrow \exists x\; \varphi(x)$ 2. **$\Negation (\Forall{x} \varphi(x)) \Leftrightarrow \exists x\; (\Negation \varphi(x))$** **$\Negation (\Exists{x} \varphi(x)) \Leftrightarrow \forall x\; (\Negation \varphi(x))$** -- _prawa de Morgana_ 3. $\Exists{x} (\varphi(x)\vee \psi (x)) \Leftrightarrow \Exists{x} \varphi(x) \vee \Exists{x} \psi(x)$ **$\Exists{x} (\varphi(x)\wedge \psi (x)) \Rightarrow \Exists{x} \varphi(x) \wedge \Exists{x} \psi(x)$** -- _prawa rozdzielności kwantyfikatora szczegółowego_ 4. $\Forall{x} (\varphi(x)\wedge \psi (x)) \Leftrightarrow \Forall{x} \varphi(x) \wedge \Forall{x} \psi(x)$ **$\Forall{x} \varphi(x) \vee \Forall{x} \psi(x) \Rightarrow \Forall{x} (\varphi(x)\vee \psi (x))$** -- _prawa rozdzielności kwantyfikatora ogólnego._ ::: :::{prf:theorem} :label: lec-01-th-05 Dla dowolnych zbiorów niepustych $X, Y$ i zmiennych $x\in X$, $y\in Y$, mamy następujące prawa przemienności kwantyfikatorów: 1. $\Exists{x} \Exists{y} \varphi(x,y) \Leftrightarrow \Exists{y} \Exists{x} \varphi(x,y)$ 2. $\Forall{x} \Forall{y} \varphi(x,y) \Leftrightarrow \Forall{y} \Forall{x}\varphi(x,y)$ 3. **$\Exists{x} \Forall{y} \varphi(x,y) \Rightarrow \Forall{y} \Exists{x} \varphi(x,y)$**. ::: :::{prf:example} W punkcie 3. z {prf:ref}`lec-01-th-05` implikacja przeciwna nie musi być prawdziwa: - zdanie $\quad \Forall {y\in \rr} \Exists{ x\in \rr} x > y \quad$ jest prawdziwe -- dla danego $y$ wystarczy wziąć $x=y+1$ - zdanie $\quad \Exists {x\in \rr} \Forall {y\in \rr} x > y \quad$ jest fałszywe -- nie istnieje liczba rzeczywista większa od wszystkich innych. ::: ## Dowodzenie twierdzeń :::{narration} Typowe **twierdzenie** ma postać implikacji **$ P \imply Q $**, gdzie **$P$** to **założenie**, a **$Q$** -- **teza**. {index}`twierdzenie; założenie` {index}`twierdzenie; teza` ::: ### Dowód wprost ($P \imply Q$) :::{narration} **Dowód wprost** to najbardziej naturalna metoda dowodzenia. Zakładamy w nim prawdziwość założenia **$P$** i używając logicznych kroków, algebry lub definicji, dochodzimy bezpośrednio do wniosku **$Q$**. ::: ::::{prf:example} :::{prf:proposition} Jeśli $n$ jest liczbą nieparzystą, to $n^2$ jest liczbą nieparzystą. ::: :::{proof} :class: [proof] dropdown 1. **Zakładamy $P$:** Niech $n$ będzie dowolną liczbą nieparzystą. Z definicji możemy zapisać $n = 2k + 1$ dla pewnej liczby całkowitej $k .$ 2. **Obliczamy $n^2$:** $$n^2 = (2k + 1)^2 = 4k^2 + 4k + 1$$ 3. **Przekształcamy wzór:** Wyciągamy dwójkę przed nawias z pierwszych dwóch składników: $$n^2 = 2(2k^2 + 2k) + 1$$ 4. **Wniosek ($Q$):** Ponieważ $(2k^2 + 2k)$ jest liczbą całkowitą, to $n^2$ ma postać $2 \cdot (\text{liczba całkowita}) + 1$, czyli z definicji **jest liczbą nieparzystą**. ::: :::: ### Dowód przez transpozycję ($\Negation Q \imply \Negation P$) ::::{narration} **Dowód przez transpozycję** polega na udowodnieniu zdania **$P \imply Q$** poprzez udowodnienie zdania do niego równoważnego: **$\Negation Q \imply \Negation P$**. Zamiast pokazywać, że :::{container} center-text *Jeśli zachodzi $P$, to zachodzi $Q$*, ::: pokazujemy, że :::{container} center-text *Jeśli nie zachodzi $Q$, to nie zachodzi $P$*. ::: :::: :::::{prf:example} :::{prf:proposition} Jeśli $n^2$ jest liczbą nieparzystą, to $n$ jest liczbą nieparzystą. ::: ::::{proof} :class: [proof] dropdown Zamieniamy twierdzenie na zdanie przeciwstawne: :::{container} center-text **Jeśli $n$ jest liczbą parzystą ($\Negation Q$), to $n^2$ jest liczbą parzystą ($\Negation P$).** ::: 1. Zakładamy, że $n$ jest parzyste. Z definicji możemy zapisać $n = 2k$ dla pewnej liczby całkowitej $k .$ 2. Podnosimy obie strony do kwadratu: $$n^2 = (2k)^2 = 4k^2 = 2(2k^2)$$ 3. Ponieważ $2k^2$ jest liczbą całkowitą, to $n^2$ wyraża się jako wielokrotność liczby 2 -- a więc **$n^2$ jest liczbą parzystą**. Wykazanie zdania $\Negation Q \imply \Negation P$ automatycznie dowodzi prawdziwości pierwotnego twierdzenia $P \imply Q .$ :::: ::::: ### Dowód nie wprost :::{narration} **Dowód nie wprost** (_reductio ad absurdum_) polega na założeniu, że twierdzenie **$\alpha$**, które chcemy udowodnić, jest **fałszywe**, a następnie wywiedzeniu z tego założenia nieprawdy. Owa nieprawda najczęściej przyjmuje w dowodzie postać sprzeczności **$\Negation \beta \wedge \beta$**, dla pewnego zdania **$\beta$**. Formalnie, korzystamy z tego, że jeśli zdanie $$ \emphmath{\Negation \alpha \imply (\Negation \beta \wedge \beta)} $$ jest prawdziwe, to koniecznie **$\Negation \alpha$** jest fałszywe, a więc **$\alpha$** jest prawdziwe. ::: ::::{prf:example} :::{prf:lemma} Liczba $\sqrt{2}$ jest niewymierna. ::: :::{proof} :class: [proof] dropdown 1. **Zakładamy nieprawdę:** Załóżmy nie wprost, że $\sqrt{2}$ **jest liczbą wymierną**. Oznacza to, że da się ją zapisać w postaci ułamka nieskracalnego: $$\sqrt{2} = \frac{a}{b}$$ gdzie $a$ i $b$ są dodatnimi liczbami całkowitymi, a ułamek jest maksymalnie uproszczony -- czyli $a$ i $b$ **nie mają wspólnych dzielników** oprócz 1 (są względnie pierwsze). 2. **Przekształcamy równanie:** Podnosimy obie strony do kwadratu: $$2 = \frac{a^2}{b^2} \implies a^2 = 2b^2$$ 3. **Wnioskujemy o liczbie $a$:** Ponieważ $a^2 = 2b^2$, to $a^2$ jest liczbą parzystą. Z właściwości liczb całkowitych wynika, że skoro kwadrat liczby jest parzysty, to sama liczba **$a$ również musi być parzysta**. Możemy więc zapisać $a = 2k$ dla pewnej liczby całkowitej $k .$ 4. **Podstawiamy $a = 2k$ do równania:** $$(2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2$$ 5. **Wnioskujemy o liczbie $b$:** Skoro $b^2 = 2k^2$, to $b^2$ jest liczbą parzystą. Stąd wynika, że sama liczba **$b$ również jest parzysta**. 6. **Sprzeczność:** Otrzymaliśmy wynik, że **zarówno $a$, jak i $b$ są liczbami parzystymi** (dzielą się przez 2). To jest **sprzeczne z założeniem z punktu 1**, w którym przyjęliśmy, że ułamek $\frac{a}{b}$ jest nieskracalny (że $a$ i $b$ nie mają wspólnych dzielników). **Wniosek:** Nasze wstępne założenie, że $\sqrt{2}$ jest liczbą wymierną, doprowadziło do logiki bez wyjścia. Zatem $\sqrt{2}$ musi być liczbą **niewymierną**. ::: :::: ### Dowód niekonstruktywny :::{narration} Dla niektórych twierdzeń nie da się znaleźć bezpośredniego dowodu wprost ani kontrapozycji -- wtedy często stosuje się inne techniki, np. **dowód przez wyczerpanie przypadków** (wykorzystując prawo wyłączonego środka). ::: :::::{prf:example} :::{prf:theorem} Istnieją liczby niewymierne $a$ i $b$ takie, że $a^b$ jest liczbą wymierną. ::: ::::{proof} :class: [proof] dropdown Aby to udowodzić, rozważmy zdanie $p$: :::{container} center-text $\sqrt{2}^{\sqrt{2}}$ jest liczbą wymierną. ::: Z prawa $p \vee \Negation p$ wnioskujemy, że zdanie $p$ jest prawdziwe albo fałszywe. - Jeśli $p$ jest prawdziwe, wystarczy wziąć $a = b = \sqrt{2} .$ - Jeśli $p$ jest fałszywe (czyli $\sqrt{2}^{\sqrt{2}}$ jest niewymierna), to biorąc $a = \sqrt{2}^{\sqrt{2}},\ b=\sqrt{2}$, mamy $$ \left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}=\sqrt{2}^{\sqrt{2}\cdot \sqrt{2}}=\sqrt{2}^2=2\in \qq, $$ więc znów znaleźliśmy szukaną parę. W obu przypadkach odpowiedź brzmi TAK -- ale dowód jest **niekonstruktywny**: nie rozstrzyga, która z liczb $a$ faktycznie działa, tzn. czy $\sqrt{2}^{\sqrt{2}}$ jest wymierna czy nie. :::: :::::