Skip to main content
LibreTexts - Ukrayinska

Розділ 07: Доказно-теоретичні поняття

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

    • \( \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}}\)

    Ми будемо використовувати символ '', щоб вказати, що доказ можливий. Цей символ називається турнікетом. Іноді його називають єдиним турнікетом, щоб підкреслити той факт, що це не символ подвійного турнікета (), який ми використовували для представлення смислового тягнення в гл. 5.

    Коли ми пишемо {\(\mathcal{A}\)1,\(\mathcal{A}\) 2,...} Так\(\mathcal{B}\), це означає, що можна дати доказ\(\mathcal{B}\) з\(\mathcal{A}\) 1,\(\mathcal{A}\) 2,... як приміщення. З лише однією передумовою, ми залишаємо фігурні дужки\(\mathcal{A}\), так що\(\mathcal{B}\) означає, що є доказ\(\mathcal{B}\) з\(\mathcal{A}\) як передумова. Природно, `\(\mathcal{C}\)означає, що є доказ того\(\mathcal{C}\), що не має приміщення.

    Часто логічні докази називають похідними. Таким\(\mathcal{A}\) чином,\(\mathcal{B}\) можна читати як «\(\mathcal{B}\)є похідним від»\(\mathcal{A}\).

    Теорема - це речення, яке можна вивести без будь-яких передумов; тобто\(\mathcal{T}\) є теоремою тоді і тільки тоді, коли\(\mathcal{T}\).

    Це не дуже важко показати, що щось є theorem— ви просто повинні дати докази цього. Як ви могли показати, що щось не є теоремою? Якщо його заперечення є теоремою, то ви могли б надати доказ. Наприклад, легко довести ¬ (\(Pa\)&¬\(Pa\)), що показує, що (\(Pa\)&¬\(Pa\)) не може бути теоремою. Однак для речення, яке не є ні теоремою, ні запереченням теореми, немає простого способу показати це. Вам доведеться продемонструвати не лише те, що певні стратегії доказів зазнають невдачі, але й те, що докази неможливі. Навіть якщо ви не спробуваєте довести речення тисячею різних способів, можливо, доказ є занадто довгим і складним для вас.

    Два речення\(\mathcal{A}\) і\(\mathcal{B}\) є доказово еквівалентними тоді і лише тоді, коли кожне може бути похідним від іншого; тобто,\(\mathcal{A}\)\(\mathcal{B}\)\(\mathcal{B}\) і\(\mathcal{A}\)

    Відносно легко показати, що два речення є доказово equival— це просто вимагає пари доказів. Показати, що речення не є доказово еквівалентними, було б набагато складніше. Це було б так само важко, як показати, що речення не є теоремою. (Насправді ці проблеми взаємозамінні. Чи можете ви придумати речення, яке було б теоремою тоді і лише тоді, коли\(\mathcal{A}\) і\(\mathcal{B}\) були доказово еквівалентними?)

    Сукупність речень {\(\mathcal{A}\)1,\(\mathcal{A}\) 2,...} є доказово суперечливою тоді і лише тоді, коли з нього випливає протиріччя; тобто для деякого речення\(\mathcal{B}\) {\(\mathcal{A}\)1,\(\mathcal{A}\) 2,...}\(\mathcal{B}\) і {\(\mathcal{A}\) 1,\(\mathcal{A}\) 2,...} ¬\(\mathcal{B}\).

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