Skip to main content
LibreTexts - Ukrayinska

2.5: Стратегії доказування

  1. Last updated
  2. Save as PDF
  • Page ID
    65234

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    Стратегії доказування

    Пошук доказів - це дуже те саме, що і рішення головоломки, яка говорить вам початкову позицію і мету, і дає конкретні правила про те, які саме кроки вам дозволено зробити, щоб виконати завдання. На кожному кроці (доказ або пазл) є кілька варіантів того, що робити, і потрібно правильно вибрати. Немає простого рецепту, який завжди підкаже вам, що робити; для успіху потрібні ті ж навички, які вам потрібні, щоб вирішити лабіринт.

    Вправа\(\PageIndex{1}\)

    Знайдіть шлях через кожен лабіринт від верхнього лівого кута до правого нижнього кута.

    mazes.PNG

    Практика не замінює, але ось кілька пропозицій та стратегій, про які слід пам'ятати, роблячи докази.

    Працюйте вперед від того, що у вас є. Подивіться на гіпотези (і будь-які інші твердження, які ви вивели до цих пір). Подумайте про правила усунення основних операторів в цих твердженнях. Вони підкажуть вам, які у вас варіанти. Наприклад:

    • Якщо у вас є\(P \& Q\), то можна відразу отримати і те,\(P\) і інше\(Q\).
    • Якщо у вас є і те\(P \Rightarrow Q\),\(P\) і інше, ви можете використовувати\(\Rightarrow\) -elimination для отримання\(Q\).
    • Якщо у вас є\(P \lor Q\), вам слід розглянути можливість використання доказу за випадками.
    Вправа\(\PageIndex{2}\)

    Дайте двоколонковий доказ відрахування\[\text{$A \Rightarrow (B \& C)$, $A$, \ $\therefore C$}\]

    Працюйте назад від того, що ви хочете. Кінцева мета - вивести висновок. Подивіться на висновок і запитайте, що таке правило введення для його головного логічного оператора. Це дає вам уявлення про те, де ви хочете бути безпосередньо перед останнім рядком доказу. Тоді ви можете ставитися до цієї лінії так, ніби це ваша мета; ми називаємо її підметою, оскільки вона являє собою частковий прогрес до справжньої мети. Запитайте, що ви могли б зробити, щоб вивести підмету. Наприклад:

    • Якщо ваш висновок є\(A\&B\), то вам потрібно придумати спосіб довести\(A\) і спосіб довести\(B\).
    • Якщо ваш висновок умовний\(A\Rightarrow B\), плануйте використовувати правило\(\Rightarrow\) -intro. Це вимагає запуску піддоказ, в якому ви припускаєте. У піддоказ, ви хочете вивести.
    • Останній з чотирьох лабіринтів у Вправі 2.5.1 легко, якщо ви працюєте назад від фінішу, а не вперед від початку.
    Вправа\(\PageIndex{3}\)

    Дайте двоколонковий доказ відрахування\[\text{$(P \lor Q) \Rightarrow (R \& S)$, $(R \lor S) \Rightarrow (P \& Q)$, $\therefore P \Rightarrow Q$}\]

    Спробуйте розбити доказ на випадки. Якщо схоже, вам потрібна додаткова гіпотеза (\(A\)), щоб довести, чого ви хочете, спробуйте розглянути два випадки: оскільки\(A \lor \lnot A\) це тавтологія («Закон виключеного середнього»), досить довести, що\(A\) і\(\lnot A\) кожен дає бажане висновок.

    Вправа\(\PageIndex{4}\)

    [Pr.BasicProofargPqrs-s] Дайте двоколонковий доказ відрахування\[\text{$P \Rightarrow Q$, $\lnot P \Rightarrow R$, $(Q \lor R) \Rightarrow S$, $\therefore S$}\]

    Шукайте корисні підцілі. Робота назад - це один із способів визначити гідну підмету, але є й інші. Наприклад, якщо у вас є\(A \Rightarrow B\), ви повинні подумати про те, чи зможете ви отримати\(A\) якось, щоб ви могли застосувати\(\Rightarrow\) -elimination.

    Вправа\(\PageIndex{5}\)

    P" label="pr.basicproofargPQRS-R->P">[Pr.BasicProofargPQRS-R->P] Дайте двоколонковий доказ відрахування\[\text{$(R \lor S) \Rightarrow (P \lor Q)$, $\lnot Q$, \ $\therefore R \Rightarrow P$}\]

    Змініть те, що ви дивитеся. Правила заміни часто можуть полегшити ваше життя; якщо доказ здається неможливим, спробуйте кілька різних замін. Наприклад:

    • Правила заперечення повинні стати другою натурою; вони часто можуть перетворити твердження в більш корисну форму.
    • Пам'ятайте, що кожен підтекст логічно еквівалентний його контрапозитиву. Контрапозитив може бути легше довести як висновок, і це може бути більш корисним як гіпотеза.
    Вправа\(\PageIndex{6}\)

    Дайте двоколонковий доказ відрахування\[\text{$P$, $\lnot (P \& Q)$, $Q \lor R$, \ $\therefore R$ }\]

    Не забувайте докази протиріччям. Якщо ви не можете знайти спосіб показати щось безпосередньо, спробуйте припустити його заперечення, а потім шукайте протиріччя. Наприклад, замість того, щоб доводити\(A \lor B\) безпосередньо, можна припустити і те\(\lnot B\),\(\lnot A\) і інше, що, швидше за все, полегшить роботу.

    Вправа\(\PageIndex{7}\)

    Дайте двоколонковий доказ відрахування\[\text{$P \Rightarrow Q$, $Q \Rightarrow \lnot P$, \ $\therefore \lnot P$ }\]

    Повторюйте в міру необхідності. Після того, як ви досягли певного прогресу, або виводячи деякі нові твердження, або прийнявши рішення про нову мету, яка буде представляти значний прогрес, подивіться, що пропонують вищезазначені стратегії у вашій новій ситуації.

    Перист. Спробуйте різні речі. Якщо один підхід не вдається, спробуйте щось інше. При вирішенні складного лабіринту слід очікувати, що доведеться кілька разів відступити, і те ж саме вірно при виконанні доказів.

    Вправа\(\PageIndex{8}\)

    Дайте двоколонковий доказ кожного з цих відрахувань.

    1. \((P \& \lnot Q) \Rightarrow (Q \lor R)\),\(\therefore (P \& \lnot Q) \Rightarrow (R \lor S)\)
    2. \(P \Rightarrow (Q \lor R)\),\(Q \Rightarrow \lnot P\),\(R \Rightarrow S\),\(\therefore P \Rightarrow S\)