Заперечення

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Заперечення в логіці — унарна операція над судженнями, результатом якої є судження (у відомому сенсі) «протилежне» початковому. Позначається знаком ¬ перед або рискою над судженням. Синонім: логічне "НЕ".

Як в класичній, так і в інтуїціоністській логіці «подвійне заперечення» ¬¬A є наслідком судження A, тобто має місце тавтологія:  A \rightarrow \neg \neg A .

В класичній логіці заперечення зазвичай інтерпретують як функцію, що переводить [істина|істину]] в хибність і навпаки. А в інтуїціоністській логіці зазвичай під запереченням твердження P приймається спростування P. Обернене твердження  \neg \neg A \rightarrow A вірно в класичній логіці (закон подвійного заперечення), але не має місця в інтуїціоністській. Тобто, заперечення шуканого твердження не може бути інтуїціоністським доказом, на відміну від класичної логіки. Цю відмінність двох логічних систем зазвичай розуміють головною.

У логіці і математиці заперечення ще називається логічним доповненням. Це операція на пропозиції, істинності значення, або семантичні значення в цілому. Інтуїтивно зрозуміло, що заперечення вірне, коли твердження є хибним, і навпаки. У класичній логіці заперечення, як правило, ототожнюється з істиною функції, яка приймає істину хибністю і навпаки. У семантиці Кріпке, заперечення - це теоретико-множинне доповнення.

Множиною істини заперечення судження є доповнення множини істини самого судження до універсальної множини, з якої вибираються елементи.

Схемотехніка[ред.ред. код]

A \bar A
0 1
1 0

Мнемонічне правило для заперечення звучить так:

На виході буде:

  • «1» тоді і лише тоді, коли на вході «0»,
  • «0» тоді і лише тоді, коли на вході «1»

Визначення[ред.ред. код]

Класичне заперечення - це операція на одне логічне значення, як правило, значення пропозиції, яке виробляє значення істини, якщо його операнд є хибним, і помилкове значення, якщо його операнд є істинним. Таким чином, якщо судження вірно, то ¬ A (вимовляється як "не А"), буде помилковим, і навпаки.

Таблиця істинності ¬p
p ¬p
Правда Неправда
Неправда Правда

Класичне заперечення може бути визначене в термінах інших логічних операцій. Наприклад, ¬ р може бути визначене як р → F, де "→" є логічним наслідком і F - це абсолютна хибність. І навпаки, можна визначити як F & P ¬ р для будь-яких р пропозицій, де "&" є логічне множення. Ідея полягає в тому, що будь-яка суперечність є хибна. Також ми отримаємо подальшу ідентичність: P → Q може бути визначене як ¬ P ∨ Q, де "∨" є логічне додавання: "Не р або q". Алгебраїчно, класичне заперечення відповідає доповненню в булевій алгебрі. Ця алгебра забезпечує семантику для класичної логіки.

Позначення[ред.ред. код]

Заперечення висловлювання р є зафіксованим по-різному в різних контекстах обговорення та області застосування. Серед цих варіантів є наступні:

Позначення Вимовлення
¬p не p
p не p
~p не p
p'\! p просте число,
p доповнення
!p\! не p

В теорії множин також використовується для позначення 'не є членом': U \ A, де U не є членом А. Незалежно від того, чи є він зафіксованим або символом, заперечення ¬ р /-р може бути прочитане як "це не той випадок, що р", "не те, що р", або зазвичай простіше (хоча і не граматично) як "не р" .

Властивості[ред.ред. код]

Подвійне заперечення[ред.ред. код]

В системі класичної логіки, подвійного заперечення, тобто заперечення a пропозиціі р, логічно еквівалентний р. Виражений в символічному плані, ¬¬p ⇔ p. В інтуїційній логіці, пропозиція є його подвійне заперечення, але не навпаки. Це знаменує одна важлива відмінність між класичним та інтуїційним запереченням. Алгебраїчно класичне заперечення називається інволюція періоду два.

Проте, в інтуїційній логіці є еквівалентність  ¬¬¬p і ¬p.

Дистрибутивність[ред.ред. код]

Закони де Моргана забезпечує спосіб поширення заперечення над диз'юнкцією та кон'юнкцією:

\neg(a \vee b) \equiv (\neg a \wedge \neg b),  and
\neg(a \wedge b) \equiv (\neg a \vee \neg b).

Лінійність[ред.ред. код]

В булевої алгебри, лінійна функція є одна з таких, що:

Якщо існує a0, a1, ..., an \in {0,1} що f(b1, ..., bn) = a0 ⊕ (a1 \land b1) ⊕ ... ⊕ (an \land bn), для всіх b1, ..., bn \in {0,1}.

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

Самостійна подвійність[ред.ред. код]

В булевій алгебрі подвійна функція є однією з таких, що:

f(a1, ..., an) = ~f(~a1, ..., ~an) для всіх a1, ..., an \in {0,1}.

Заперечення є самоподвійним логічним оператором.

Правила виведення[ред.ред. код]

Є число еквівалентних способів сформулювати правила для заперечення. Один звичайний спосіб сформулювати класичне заперечення в установці природного вирахування прийняти як примітивні правила виведення заперечення введення (з висновку p, щоб обидва q і ¬q, висновок ¬p; це правило також називають доведення до абсурду), заперечення усунення (з p і ¬p висновок q; це правило також називають подвійним усуненням заперечення). Один отримує правило інтуїційного заперечення так само, але з винятоком ліквідації подвійного заперечення.

Заперечення введення стверджує, що якщо абсурд можна зробити як висновок від p, то p не повинно бути справою (тобто. p неправдиве (класично), або опровержіне (інтуїционістському) або т.п..). Іноді усунення заперечення формулюється за допомогою примітивного абсурду (знак ⊥). В цьому випадку правило говорить, що з p і ¬p слідує абсурд. Разом з ліквідацією подвійного заперечення можна зробити висновок нашому спочатку сформульовану правилу, саме що-небудь з абсурду.

Зазвичай інтуїційне заперечення ¬p з p визначається як р → ⊥. Тоді заперечення впроваджує та усуває лише окремі випадки імплікації введення (умовний доказ) та ліквідації (модус поненс).

Програмування[ред.ред. код]

Як і в математиці, заперечення використовується в інформатиці для побудови логічного висловлювання.

    if (!(r == t))
    {
         /*...statements executed when r does NOT equal t...*/
    }

"!" означає логічне НЕ в B[en], C, і мов,таких як C++, Java, JavaScript, Perl, і PHP. "NOT" є оператором використовується в ALGOL 60[en], BASIC, і мови разом з ALGOL- або BASIC-inspired синтаксису, таких як Pascal, Ada, Eiffel і Seed7. Деякі мови (C++, Perl, і т. д.) забезпечують більше ніж один оператор для заперечення. А кілька мов, як PL/I і Ratfor використовують ¬ для заперечення. Деякі сучасні комп'ютери та операційні системи будуть відображати ¬ як ! на відтворення файлів в ASCII.  Більшість сучасних мов дозволяють вищевказану заяву щоб скоротити від if (!(r == t)) до if (r != t), яка дозволяє іноді, коли компілятор/інтерпретатор не може оптимізувати його, швидше програм.

В інформатиці є також побітове заперечення. Це приймає значення цього та перемикає всі бінарні 1s до 0s і 0s до 1s. Дивись операцію побітового. Це часто використовується для створення зворотнього коду або "~" в C або C++ і в додатковому (просто спрощена до "-" або від'ємний знак, оскільки це рівнозначно тому, що приймаючи від'ємне значення арифметичне від кількості), як це здебільшого створює протилежне (від'ємне значення еквівалентного), або математичний додаток до значення (де обидва значення додаються разом вони створюють в цілому).

Щоб одержати абсолютне (позитивний еквівалент) значення даного цілого числа в наступному буде працювати як "-" змінює його з негативного на позитивний (він негативний, оскільки "x < 0" істина)

    unsigned int abs(int x)
    {
        if (x < 0)
            return -x;
        else
            return x;
    }

Щоб продемонструвати логічне заперечення:

    unsigned int abs(int x)
    {
        if (!(x < 0))
            return x;
        else
            return -x;
    }

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

Ця конвенція іноді поверхнева в письмовій мові, як у комп'ютерній сфері сленгу для ні. Фраза !voting, наприклад, означає " не беруть участь у голосуванні".

Семантика Кріпке[ред.ред. код]

В Семантиці Кріпке, де семантичні значення формули набору можливих світів, заперечення може бути доставлене на увазі теоретико-множинної Комплементації.

(Дивіться також семантика можливих світів.)

Книжки[ред.ред. код]

  • Gabbay, Dov, and Wansing, Heinrich, eds., 1999. What is Negation?, Kluwer.
  • Horn, L., 2001. A Natural History of Negation, University of Chicago Press.
  • G. H. von Wright, 1953–59, "On the Logic of Negation", Commentationes Physico-Mathematicae 22.
  • Wansing, Heinrich, 2001, "Negation," in Goble, Lou, ed., The Blackwell Guide to Philosophical Logic, Blackwell.
  • Marco Tettamanti, Rosa Manenti, Pasquale A. Della Rosa, Andrea Falini, Daniela Perani, Stefano F. Cappa and Andrea Moro (2008). "Negation in the brain: Modulating action representation", NeuroImage Volume 43, Issue 2, 1 November 2008, pages 358–367, http://dx.doi.org/10.1016/j.neuroimage.2008.08.004/

Див. також[ред.ред. код]

Посилання[ред.ред. код]