Отрицание

Отрицание
НЕТ
Определение
Таблица истинности
Логический вентиль
Нормальные формы
Дизъюнктивный
соединительный
Полином Жегалкина
Решетки постовые
0-сохраняющий	нет
1-сохраняющий	нет
монотонный	нет
Аффинный	да
Самодвойственный	да
	v ; т ; и ;

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

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

Определение

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

Таблица истинности $\neg P$ заключается в следующем:

$P$	$\neg P$
Истинный	ЛОЖЬ
ЛОЖЬ	Истинный

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

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

Обозначения

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

Обозначения	Обычный текст	Вокализация
$\neg p$	¬p , 7р ^[4]	Не п
${\mathord {\sim }}p$	~р	Не п
$-p$	-п	Не п
$Np$		И п
$p'$	п'	п премьер, p дополнение
${\overline {p}}$	̅p	п бар, Бар п
$!p$	!п	Бэнг п Не п

Обозначения $Np$ это польское обозначение .

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

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

Приоритет

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

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

Оператор	Приоритет
$\neg$	1
$\land$	2
$\lor$	3
$\to$	4
$\leftrightarrow$	5

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

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

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

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

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

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

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

\neg (P\lor Q)\equiv (\neg P\land \neg Q)

, и

\neg (P\land Q)\equiv (\neg P\lor \neg Q)

.

Линейность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

if (!(r == t))
{
    /*...statements executed when r does NOT equal 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"выдает истину)

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;
}

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

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

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

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

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

См. также

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

Ссылки

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

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

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

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

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

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

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

[1] Вайсштейн, Эрик В. «Отрицание» . mathworld.wolfram.com . Проверено 2 сентября 2020 г.

[2] «Логические и математические утверждения – рабочие примеры» . www.math.toronto.edu . Проверено 2 сентября 2020 г.

[:21-3] Перейти обратно: ^а ^б Билл, Джеффри К. (2010). Логика: основы . Основы (1. изд.). Лондон: Рутледж. п. 57. ИСБН 978-0-203-85155-5 .

[4] Используется как временное решение в ранних публикациях о пишущих машинках, например Ричард Э. Ладнер (январь 1975 г.). «Проблема со значением схемы — пространство журнала заполнено для P». Новости ACM SIGACT . 7 (101): 18–20. дои : 10.1145/990518.990519 .

[5] О'Доннелл, Джон; Холл, Корделия; Пейдж, Рекс (2007), Дискретная математика с использованием компьютера , Springer, с. 120, ISBN 9781846285981 .

[6] Иган, Дэвид. «Оператор двойного отрицания, преобразующий в логическое значение в C» . Заметки разработчиков .

[7] Рэймонд, Эрик и Стил, Гай. Новый словарь хакера , стр. 18 (MIT Press, 1996).

[8] Мунат, Джудит. Лексическое творчество, Тексты и контекст , с. 148 (Издательство Джона Бенджамина, 2007).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v т и Общие логические связи
Tautology/True $\top$
Alternative denial (NAND gate) $\uparrow$ Converse implication $\leftarrow$ Implication (IMPLY gate) $\rightarrow$ Disjunction (OR gate) $\lor$
Negation (NOT gate) $\neg$ Exclusive or (XOR gate) $\not \leftrightarrow$ Biconditional (XNOR gate) $\leftrightarrow$ Statement (Digital buffer)
Joint denial (NOR gate) $\downarrow$ Nonimplication (NIMPLY gate) $\nrightarrow$ Converse nonimplication $\nleftarrow$ Conjunction (AND gate) $\land$
Contradiction/False $\bot$
Philosophy portal