Отрицание

Логическая операция

В логике отрицание , также называемое логическим «нет» или логическим дополнением , представляет собой операцию , которая переводит предложение в другое предложение «не », обозначающее « не верно», написанное или . Интуитивно оно интерпретируется как истинное, когда ложное, и ложное, когда истинное. ^{[1] [2]} Таким образом, отрицание является унарной логической связкой . Его можно применять как операцию над понятиями , предложениями , значениями истинности или семантическими значениями в более общем смысле. В классической логике отрицание обычно отождествляется с функцией истинности , которая переводит истину в ложность (и наоборот). В интуиционистской логике , согласно интерпретации Брауэра-Хейтинга-Колмогорова , отрицанием предложения является предложение, доказательства которого являются опровержениями . ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle \neg P}$ ${\displaystyle {\mathord {\sim }}P}$ ${\displaystyle {\overline {P}}}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle P}$

Определение

Классическое отрицание — это операция над одним логическим значением , обычно значением предложения , которая дает значение true , когда его операнд ложный, и значение false , когда его операнд истинен. Таким образом, если утверждение истинно, то (произносится как «не Р») будет ложным; и наоборот, если истинно, то будет ложно. ${\displaystyle P}$ ${\displaystyle \neg P}$ ${\displaystyle \neg P}$ ${\displaystyle P}$

Таблица истинности выглядит следующим образом: ${\displaystyle \neg P}$

Отрицание можно определить с точки зрения других логических операций. Например, можно определить как (где — логическое следствие , а — абсолютная ложь ). И наоборот, можно определить как для любого предложения Q (где – логическая конъюнкция ). Идея здесь в том, что любое противоречие ложно, и хотя эти идеи работают как в классической, так и в интуиционистской логике, они не работают в паранепротиворечивой логике , где противоречия не обязательно ложны. В классической логике мы также получаем дальнейшее тождество, которое можно определить как , где – логическая дизъюнкция . ${\displaystyle \neg P}$ ${\displaystyle P\rightarrow \bot }$ ${\displaystyle \rightarrow }$ ${\displaystyle \bot }$ ${\displaystyle \bot }$ ${\displaystyle Q\land \neg Q}$ ${\displaystyle \land }$ ${\displaystyle P\rightarrow Q}$ ${\displaystyle \neg P\lor Q}$ ${\displaystyle \lor }$

Алгебраически классическое отрицание соответствует дополнению в булевой алгебре , а интуиционистское отрицание — псевдодополнению в алгебре Гейтинга . Эти алгебры обеспечивают семантику классической и интуиционистской логики.

Обозначения

Отрицание предложения p обозначается по-разному, в разных контекстах обсуждения и областях применения. В следующей таблице описаны некоторые из этих вариантов:

Обозначения польские . _ ${\displaystyle Np}$

В теории множеств также используется для обозначения «не в множестве»: это набор всех членов U , которые не являются членами A. ${\displaystyle \setminus }$ ${\displaystyle U\setminus A}$

Независимо от того, как оно обозначено или символизировано , отрицание можно прочитать как «это не тот случай, что Р », «не то Р » или обычно проще как «не Р ». ${\displaystyle \neg P}$

Приоритет

Чтобы уменьшить количество необходимых скобок, можно ввести правила приоритета : ¬ имеет более высокий приоритет, чем ∧, ∧ выше, чем ∨, и ∨ выше, чем →. Так, например, это сокращение от ${\displaystyle P\vee Q\wedge {\neg R}\rightarrow S}$ ${\displaystyle (P\vee (Q\wedge (\neg R)))\rightarrow S.}$

Вот таблица, показывающая часто используемый приоритет логических операторов. ^[4]

Характеристики

Двойное отрицание

В системе классической логики двойное отрицание, то есть отрицание отрицания предложения , логически эквивалентно . Выражаясь в символических терминах, . В интуиционистской логике предложение подразумевает двойное отрицание, но не наоборот. Это отмечает одно важное различие между классическим и интуиционистским отрицанием. Алгебраически классическое отрицание называется инволюцией второго периода. ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle \neg \neg P\equiv P}$

Однако в интуиционистской логике более слабая эквивалентность имеет место. Это потому, что в интуиционистской логике это просто сокращение от , и у нас также есть . Составление этого последнего импликации с помощью тройного отрицания означает, что . ${\displaystyle \neg \neg \neg P\equiv \neg P}$ ${\displaystyle \neg P}$ ${\displaystyle P\rightarrow \bot }$ ${\displaystyle P\rightarrow \neg \neg P}$ ${\displaystyle \neg \neg P\rightarrow \bot }$ ${\displaystyle P\rightarrow \bot }$

В результате в пропозициональном случае предложение является классически доказуемым, если его двойное отрицание интуиционистски доказуемо. Этот результат известен как теорема Гливенко .

Дистрибутивность

Законы де Моргана позволяют распределить отрицание над дизъюнкцией и конъюнкцией :

${\displaystyle \neg (P\lor Q)\equiv (\neg P\land \neg Q)}$, и

${\displaystyle \neg (P\land Q)\equiv (\neg P\lor \neg Q)}$.

Линейность

Пусть обозначает логическую операцию xor . В булевой алгебре линейной функцией называется такая, что: ${\displaystyle \oplus }$

Если существует , , для всех . ${\displaystyle a_{0},a_{1},\dots ,a_{n}\in \{0,1\}}$ ${\displaystyle f(b_{1},b_{2},\dots ,b_{n})=a_{0}\oplus (a_{1}\land b_{1})\oplus \dots \oplus (a_{n}\land b_{n})}$ ${\displaystyle b_{1},b_{2},\dots ,b_{n}\in \{0,1\}}$

Другой способ выразить это состоит в том, что каждая переменная всегда влияет на истинное значение операции или никогда не имеет значения. Отрицание — это линейный логический оператор.

Самостоятельный двойной

В булевой алгебре самодвойственная функция — это такая функция, что:

${\displaystyle f(a_{1},\dots ,a_{n})=\neg f(\neg a_{1},\dots ,\neg a_{n})}$для всех . Отрицание — это самодвойственный логический оператор. ${\displaystyle a_{1},\dots ,a_{n}\in \{0,1\}}$

Отрицания кванторов

В логике первого порядка есть два квантора: один — квантор всеобщности (означает «для всех»), а другой — квантор существования (означает «существует»). Отрицанием одного квантора является другой квантор ( и ). Например, предикат P как « x смертен» и областью x как совокупность всех людей означает «человек x среди всех людей смертен» или «все люди смертны». Отрицание этого слова означает: «Во всех людях существует человек x , который не смертен», или «есть кто-то, кто живет вечно». ${\displaystyle \forall }$ ${\displaystyle \exists }$ ${\displaystyle \neg \forall xP(x)\equiv \exists x\neg P(x)}$ ${\displaystyle \neg \exists xP(x)\equiv \forall x\neg P(x)}$ ${\displaystyle \forall xP(x)}$ ${\displaystyle \neg \forall xP(x)\equiv \exists x\neg P(x)}$

Правила вывода

Существует ряд эквивалентных способов формулировки правил отрицания. Один из обычных способов сформулировать классическое отрицание в условиях естественной дедукции — это принять в качестве примитивных правил вывода отрицание ( из вывода к обоим и вывести ; это правило также называется доведением до абсурда ), устранение отрицания (из и вывести ; это правило также называется ex falso quodlibet ) и устранением двойного отрицания (из infer ). Правила интуиционистского отрицания получаются тем же путем, но исключая устранение двойного отрицания. ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle \neg Q}$ ${\displaystyle \neg P}$ ${\displaystyle P}$ ${\displaystyle \neg P}$ ${\displaystyle Q}$ ${\displaystyle \neg \neg P}$ ${\displaystyle P}$

Введение отрицания утверждает, что если в качестве вывода можно сделать абсурд, то это не должно иметь место (т. е. является ложным (классически) или опровержимо (интуиционистски) и т. д.). Устранение отрицания утверждает, что все следует из абсурда. Иногда устранение отрицания формулируется с помощью примитивного знака абсурда . В данном случае правило гласит, что из и вытекает абсурд. Вместе с устранением двойного отрицания можно вывести наше первоначально сформулированное правило, а именно: из абсурда все следует. ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle \bot }$ ${\displaystyle P}$ ${\displaystyle \neg P}$

Обычно интуиционистское отрицание определяется как . Тогда введение и устранение отрицания — это всего лишь частные случаи введения импликации ( условное доказательство ) и исключения ( modus ponens ). В этом случае необходимо также добавить в качестве примитивного правила ex falso quodlibet . ${\displaystyle \neg P}$ ${\displaystyle P}$ ${\displaystyle P\rightarrow \bot }$

Язык программирования и обычный язык

Как и в математике, в информатике отрицание используется для построения логических утверждений.

if ( ! ( r == t )) { /*...операторы выполняются, когда r НЕ равно t...*/ }    

Восклицательный знак " !" означает логическое НЕ в B , C и языках с синтаксисом, вдохновленным C, таких как C++ , Java , JavaScript , Perl и PHP . " NOT" — это оператор, используемый в ALGOL 60 , BASIC и языках с синтаксисом, основанным на ALGOL или BASIC, таких как Pascal , Ada , Eiffel и Seed7 . Некоторые языки (C++, Perl и т. д.) предоставляют более одного оператора отрицания. Некоторые языки, такие как PL/I и Ratfor, используют ¬отрицание. Большинство современных языков позволяют сократить приведенный выше оператор с if (!(r == t))до if (r != t), что иногда позволяет, когда компилятор/интерпретатор не может его оптимизировать, создавать более быстрые программы.

В информатике также существует побитовое отрицание . Это принимает заданное значение и переключает все двоичные 1 на 0 и 0 на 1. См. побитовую операцию . Это часто используется для создания дополнения до единиц или " ~" в C или C++ и дополнения до двух (просто упрощено до " -" или отрицательного знака, поскольку это эквивалентно принятию арифметического отрицательного значения числа), поскольку по сути оно создает противоположное ( эквивалент отрицательного значения) или математическое дополнение значения (когда оба значения складываются вместе, они образуют целое).

Чтобы получить абсолютное (положительный эквивалент) значение данного целого числа, будет работать следующее: " -" меняет его с отрицательного на положительное (оно отрицательно, потому что " x < 0" дает true)

unsigned int abs ( int x ) { if ( x < 0 ) return - x ; иначе вернуть х ; }            

Чтобы продемонстрировать логическое отрицание:

unsigned int abs ( int x ) { if ( ! ( x < 0 )) return x ; иначе возврат - х ; }            

Инвертирование условия и обращение результатов создает код, который логически эквивалентен исходному коду, т.е. будет иметь идентичные результаты для любого ввода (в зависимости от используемого компилятора фактические инструкции, выполняемые компьютером, могут отличаться).

Это соглашение иногда встречается в обычной письменной речи, как компьютерный сленг , обозначающий «не» . Например, фраза !votingозначает «не голосовать». Другим примером является фраза !clue, которая используется как синоним слов «без понятия» или «невежественный». ^{[5] [6]}

Семантика Крипке

В семантике Крипке , где семантические значения формул представляют собой наборы возможных миров , отрицание может пониматься как теоретико-множественное дополнение ^{( подробнее см} . Также семантику возможных миров ).

Смотрите также

• Утверждение и отрицание (грамматическая полярность)
• Амфек
• Апофазис
• Бинарная оппозиция
• Побитовое НЕ
• Противопоставление
• Циклическое отрицание
• Отрицание как неудача
• НЕ ворота
• Платоновая борода
• Площадь оппозиции

Рекомендации

1. Вайсштейн, Эрик В. «Отрицание». mathworld.wolfram.com . Проверено 2 сентября 2020 г.
2. «Логические и математические утверждения - рабочие примеры». www.math.toronto.edu . Проверено 2 сентября 2020 г.
3. Используется как временное решение в ранних публикациях о пишущих машинках, например, Ричард Э. Ладнер (январь 1975 г.). «Проблема со значением схемы — пространство журнала заполнено для P». Новости ACM SIGACT . 7 (101): 18–20. дои : 10.1145/990518.990519.
4. О'Доннелл, Джон; Холл, Корделия; Пейдж, Рекс (2007), Дискретная математика с использованием компьютера, Springer, стр. 120, ISBN 9781846285981.
5. Рэймонд, Эрик и Стил, Гай. Новый словарь хакера, стр. 18 (MIT Press, 1996).
6. Мунат, Джудит. Лексическое творчество, Тексты и контекст, с. 148 (Издательство Джона Бенджамина, 2007).

дальнейшее чтение

• Габбай, Дов и Вансинг, Генрих, ред., 1999. Что такое отрицание? , Клювер .
• Хорн, Л. , 2001. Естественная история отрицания , University of Chicago Press .
• Г.Х. фон Райт , 1953–59, «О логике отрицания», Commentationes Physico-Mathematicae 22 .
• Вансинг, Генрих, 2001, «Отрицание», в книге Гобл, Лу, изд., « Руководство Блэквелла по философской логике» , Блэквелл .
• Теттаманти, Марко; Маненти, Роза; Делла Роза, Паскуале А.; Фалини, Андреа; Перани, Даниэла; Каппа, Стефано Ф.; Моро, Андреа (2008). «Отрицание в мозгу: модуляция представления действий». НейроИмидж . 43 (2): 358–367. doi : 10.1016/j.neuroimage.2008.08.004. PMID  18771737. S2CID  17658822.

Внешние ссылки

• Хорн, Лоуренс Р.; Вансинг, Генрих. "Отрицание". В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии .
• «Отрицание», Математическая энциклопедия , EMS Press , 2001 [1994]
• НЕ, в MathWorld

Таблицы истинности сложных предложений

• «Таблица истинности для предложения НЕ, примененного к КОНЕЧНОМУ предложению». Архивировано из оригинала 1 марта 2000 года.
• «Предложение НЕ КОНЕЧНОГО предложения». Архивировано из оригинала 1 марта 2000 года.
• «Предложение НЕ предложения ИЛИ». Архивировано из оригинала 17 января 2000 года.
• «Предложение NOT периода IF...THEN». Архивировано из оригинала 1 марта 2000 года.