Отрицание

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

В логике отрицание , также называемое логическим не или логическим дополнением , — это операция , которая переводит одно предложение в другое предложение «не », что означает « не является истинным», записанное как , или . Оно интуитивно интерпретируется как истинное, когда является ложным, и ложное, когда является истинным. ^{[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}$

Операндом отрицания является отрицание ^[3] или отрицание [ ^3] .

Определение

Классическое отрицание — это операция над одним логическим значением , обычно значением предложения , которая производит значение true , когда его операнд ложен, и значение false , когда его операнд истинен. Таким образом, если утверждение истинно, то (произносится как «не P») будет ложным; и наоборот, если истинно, то будет ложным. ${\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}$

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

Приоритет

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

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

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

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

В системе классической логики двойное отрицание, то есть отрицание отрицания предложения , логически эквивалентно . Выражаясь символически, . В интуиционистской логике предложение подразумевает свое двойное отрицание, но не наоборот. Это отмечает одно важное различие между классическим и интуиционистским отрицанием. Алгебраически классическое отрицание называется инволюцией периода два. ${\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)}$

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

Существует ряд эквивалентных способов формулировки правил для отрицания. Один из обычных способов формулировки классического отрицания в естественной дедукции — взять в качестве примитивных правил вывода введение отрицания (из вывода к и , infer ; это правило также называется reductio ad absurdum ), устранение отрицания (из и infer ; это правило также называется 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), что иногда позволяет, когда компилятор/интерпретатор не может его оптимизировать, ускорять программы.

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

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

беззнаковое целое число abs ( int x ) { если ( x < 0 ) вернуть -x ; иначе вернуть x ; }            

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

беззнаковое целое число abs ( int x ) { если ( ! ( x < 0 ) ) вернуть x ; иначе вернуть -x ; }            

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

В языке C (и некоторых других языках, произошедших от C) двойное отрицание ( !!x) используется как идиома для преобразования xв каноническое логическое значение, т. е. целое число со значением 0 или 1 и никаким другим. Хотя любое целое число, отличное от 0, является логически истинным в языке C, а 1 не является чем-то особенным в этом отношении, иногда важно гарантировать, что используется каноническое значение, например, для печати или если число впоследствии используется для арифметических операций. ^[6]

Конвенция использования !для обозначения отрицания иногда всплывает в обычной письменной речи, как компьютерный сленг для not . Например, эта фраза !votingозначает «не голосует». Другим примером является фраза !clue, которая используется как синоним для «no-clue» или «clueless». ^{[7] [8]}

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

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

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

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

Ссылки

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

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

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

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

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

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

• "Таблица истинности для предложения NOT, примененного к предложению END". Архивировано из оригинала 1 марта 2000 г.
• "NOT-предложение END-предложения". Архивировано из оригинала 1 марта 2000 г.
• "NOT-предложение предложения OR". Архивировано из оригинала 17 января 2000 г.
• "NOT clause of an IF...THEN period". Архивировано из оригинала 1 марта 2000 года.