Отрицание

Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Март 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Отрицание

НЕТ
Определение	${\ displaystyle {\ overline {x}}}$
Таблица истинности	${\ displaystyle (10)}$
Логический вентиль
Нормальные формы
Дизъюнктивный	${\ displaystyle {\ overline {x}}}$
Конъюнктивный	${\ displaystyle {\ overline {x}}}$
Полином Жегалкина	${\ displaystyle 1 \ oplus x}$
Решетки столба
0-сохраняющий	нет
1-консервирующий	нет
Монотонный	нет
Аффинный	да
v т е

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

Определение [ править ]

Не существует согласия относительно возможности определения отрицания, относительно его логического статуса, функции и значения, относительно области его применимости и относительно интерпретации отрицательного суждения (FH Heinemann 1944). ^[4]

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

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

${\ displaystyle P}$	${\ displaystyle \ neg P}$
Истинный	Ложь
Ложь	Истинный

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

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

Обозначение [ править ]

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

Обозначение	Простой текст	Вокализация
${\displaystyle \neg p}$	¬p	Не п
${\displaystyle {\mathord {\sim }}p}$	~ р	Не п
${\displaystyle -p}$	-п	Не п
N p		En p
${\displaystyle p'}$	п'	p простое, p дополнение
${\displaystyle {\overline {p}}}$	п	p бар, Бар p
${\displaystyle !p}$	!п	Bang p Не п

Обозначение N p - это обозначение Лукасевича .

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

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

Свойства [ править ]

Двойное отрицание [ править ]

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

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

Распределительность [ править ]

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

${\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\}}$

Отрицания кванторов [ править ]

В логике первого порядка есть два квантора: один - универсальный квантор (означает «для всех»), а другой - квантор существования (означает «существует»). ^[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)}$

Правила вывода [ править ]

Есть несколько эквивалентных способов сформулировать правила отрицания. Один из обычных способов сформулировать классическое отрицание в установке естественного вывода состоит в том, чтобы принять в качестве примитивных правил введение отрицания вывода (от вывода к обоим и , вывод ; это правило также называется reductio ad absurdum ), исключения отрицания (от и выводить ; это правило также называется 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 использования¬для отрицания. Некоторые современные компьютеры и операционные системы будут отображаться ¬как !файлы, закодированные в ASCII . ^{[ требуется пояснение ]} Большинство современных языков позволяют сокращать приведенный выше оператор с if (!(r == t))до if (r != t), что иногда позволяет, когда компилятор / интерпретатор не может его оптимизировать, более быстрые программы.

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

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

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

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

беззнаковый  int  abs ( int  x ) {  если  ( ! ( x  <  0 ))  return  x ;  иначе  возврат  - х ; }

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

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

Семантика Крипке [ править ]

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

См. Также [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме отрицания .

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

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

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