Обратная неимпликация

Венна Диаграмма $P\nleftarrow Q$
(красная область соответствует действительности)

В логике обратная неимпликация ^[1] это логическая связка которая является отрицанием обратной импликации (т. е. отрицанием обратной , импликации — ).

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

Обратная неимпликация обозначается $P\nleftarrow Q$ , или $P\not \subset Q$ и логически эквивалентен $\neg (P\leftarrow Q)$ и $\neg P\wedge Q$ .

Таблица истинности [ править ]

Таблица истинности $A\nleftarrow B$ . ^[2]

$A$	$B$	$A\nleftarrow B$
Ф	Ф	Ф
Ф	Т	Т
Т	Ф	Ф
Т	Т	Ф

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

Обратная неимпликация обозначается ${\textstyle p\nleftarrow q}$ , что является стрелкой влево из обратной импликации ( ${\textstyle \leftarrow }$ ), отрицается штрихом ( $/$ ).

Альтернативы включают в себя

${\textstyle p\not \subset q}$ , который сочетает в себе обратную импликацию $\subset$ , отменяется штрихом ( $/$ ).
${\textstyle p{\tilde {\leftarrow }}q}$ , который объединяет стрелку влево обратной импликации ( ${\textstyle \leftarrow }$ ) с тильдой отрицания ( ${\textstyle \sim }$ ).
M pq , в обозначениях Боченского

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

сохранение ложности : интерпретация, при которой всем переменным присваивается значение истинности «ложь», дает значение истинности «ложь» в результате обратной неимпликации.

Естественный язык [ править ]

Грамматический [ править ]

Пример,

Если идет дождь (P), то я промокну (Q), то, что я мокрый (Q), не означает, что идет дождь, на самом деле я пошел на вечеринку у бассейна с сотрудниками совместного обучения, в своей одежде (~P ) и именно поэтому я провожу эту лекцию в этом состоянии (Q).

Риторический [ править ]

Q не подразумевает P.

Разговорный [ править ]

Булева алгебра [ править ]

Обратная неимпликация в общей булевой алгебре определяется как ${\textstyle q\nleftarrow p=q'p}$ .

Пример двухэлементной булевой алгебры: 2 элемента {0,1} с 0 в качестве нуля и 1 в качестве единичного элемента, операторы ${\textstyle \sim }$ как оператор дополнения, ${\textstyle \vee }$ в качестве оператора соединения и ${\textstyle \wedge }$ в качестве оператора встречи постройте булеву алгебру логики высказываний .

${\textstyle {}\sim x}$	$1$	$0$
$х$	$0$	$1$

и

$и$
$1$	$1$	$1$
$0$	$0$	$1$
${\textstyle y_{\vee }x}$	$0$	$1$	$х$

и

$и$
$1$	$0$	$1$
$0$	$0$	$0$
${\textstyle y_{\wedge }x}$	$0$	$1$	$х$

затем

\scriptstyle {y\nleftarrow x}\!

означает

$и$
$1$	$0$	$0$
$0$	$0$	$1$
$\scriptstyle {y\nleftarrow x}\!$	$0$	$1$	$х$

(Отрицание)

(Включительно или)

(И)

(Обратная неимпликация)

Пример 4-элементной булевой алгебры: 4 делителя {1,2,3,6} числа 6, где 1 — ноль, а 6 — единица, операторы $\scriptstyle {^{c}}\!$ (коделитель 6) как оператор дополнения, $\scriptstyle {_{\vee }}\!$ (наименьшее общее кратное) в качестве оператора соединения и $\scriptstyle {_{\wedge }}\!$ (наибольший общий делитель) в качестве оператора встречи постройте булеву алгебру.

$\scriptstyle {x^{c}}\!$	$6$	$3$	$2$	$1$
$х$	$1$	$2$	$3$	$6$

и

$и$
$6$	$6$	$6$	$6$	$6$
$3$	$3$	$6$	$3$	$6$
$2$	$2$	$2$	$6$	$6$
$1$	$1$	$2$	$3$	$6$
$\scriptstyle {y_{\vee }x}\!$	$1$	$2$	$3$	$6$	$х$

и

$и$
$6$	$1$	$2$	$3$	$6$
$3$	$1$	$1$	$3$	$3$
$2$	$1$	$2$	$1$	$2$
$1$	$1$	$1$	$1$	$1$
$\scriptstyle {y_{\wedge }x}$	$1$	$2$	$3$	$6$	$х$

затем

\scriptstyle {y\nleftarrow x}\!

означает

$и$
$6$	$1$	$1$	$1$	$1$
$3$	$1$	$2$	$1$	$2$
$2$	$1$	$1$	$3$	$3$
$1$	$1$	$2$	$3$	$6$
$\scriptstyle {y\nleftarrow x}\!$	$1$	$2$	$3$	$6$	$х$

(коделитель 6)

(Наименьшее общее кратное)

(Наибольший общий делитель)

(наибольший делитель x взаимно прост с y)

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

Неассоциативный [ править ]

$r\nleftarrow (q\nleftarrow p)=(r\nleftarrow q)\nleftarrow p$ тогда и только тогда, когда $rp=0$ #s5 (В двухэлементной булевой алгебре последнее условие сводится к $r=0$ или $p=0$ ). Следовательно, в нетривиальной булевой алгебре обратная неимпликация неассоциативна .

{\begin{aligned}(r\nleftarrow q)\nleftarrow p&=r'q\nleftarrow p&{\text{(by definition)}}\\&=(r'q)'p&{\text{(by definition)}}\\&=(r+q')p&{\text{(De Morgan's laws)}}\\&=(r+r'q')p&{\text{(Absorption law)}}\\&=rp+r'q'p\\&=rp+r'(q\nleftarrow p)&{\text{(by definition)}}\\&=rp+r\nleftarrow (q\nleftarrow p)&{\text{(by definition)}}\\\end{aligned}}

Очевидно, оно ассоциативно тогда и только тогда, когда $rp=0$ .

Некоммутативный [ править ]

$q\nleftarrow p=p\nleftarrow q$ тогда и только тогда, когда $q=p$ #s6 . Следовательно, обратная неимпликация некоммутативна .

Нейтральные и поглощающие элементы [ править ]

$0$ — левый нейтральный элемент ( $0\nleftarrow p=p$ ) и правый поглощающий элемент ( ${p\nleftarrow 0=0}$ ).
$1\nleftarrow p=0$ , $p\nleftarrow 1=p'$ , и $p\nleftarrow p=0$ .
Импликация $q\rightarrow p$ является двойственным к обратной неимпликации $q\nleftarrow p$ #s7 .

Обратная неимпликация некоммутативна.
Шаг	Используйте	В результате чего
с.1	Определение	$\scriptstyle {q{\tilde {\leftarrow }}p=q'p\,}\!$
с.2	Определение	$\scriptstyle {p{\tilde {\leftarrow }}q=p'q\,}\!$
раздел 3	раздел 1 раздел 2	$\scriptstyle {q{\tilde {\leftarrow }}p=p{\tilde {\leftarrow }}q\ \Leftrightarrow \ q'p=qp'\,}\!$
раздел 4		$\scriptstyle {q\,}\!$	$\scriptstyle {=\,}\!$	$\scriptstyle {q.1\,}\!$
с.5	s.4.right - развернуть элемент Unit		$\scriptstyle {=\,}\!$	$\scriptstyle {q.(p+p')\,}\!$
раздел 6	s.5.right - оценить выражение		$\scriptstyle {=\,}\!$	$\scriptstyle {qp+qp'\,}\!$
стр.7	с.4.слева = с.6.справа	$\scriptstyle {q=qp+qp'\,}\!$
стр.8		$\scriptstyle {q'p=qp'\,}\!$	$\scriptstyle {\Rightarrow \,}\!$	$\scriptstyle {qp+qp'=qp+q'p\,}\!$
с.9	s.8 - перегруппировать общие факторы		$\scriptstyle {\Rightarrow \,}\!$	$\scriptstyle {q.(p+p')=(q+q').p\,}\!$
стр.10	п.9 - соединение дополнений равно единице		$\scriptstyle {\Rightarrow \,}\!$	$\scriptstyle {q.1=1.p\,}\!$
стр.11	s.10.right - оценить выражение		$\scriptstyle {\Rightarrow \,}\!$	$\scriptstyle {q=p\,}\!$
стр.12	стр.8 стр.11	$\scriptstyle {q'p=qp'\ \Rightarrow \ q=p\,}\!$
стр.13		$\scriptstyle {q=p\ \Rightarrow \ q'p=qp'\,}\!$
стр.14	стр.12 стр.13	$\scriptstyle {q=p\ \Leftrightarrow \ q'p=qp'\,}\!$
стр.15	стр.3 стр.14	$\scriptstyle {q{\tilde {\leftarrow }}p=p{\tilde {\leftarrow }}q\ \Leftrightarrow \ q=p\,}\!$

Импликация является двойственной обратной неимпликации.
Шаг	Используйте	В результате чего
с.1	Определение	$\scriptstyle {\operatorname {dual} (q{\tilde {\leftarrow }}p)\,}\!$	$\scriptstyle {=\,}\!$	$\scriptstyle {\operatorname {dual} (q'p)\,}\!$
с.2	s.1.right - . двойственно +		$\scriptstyle {=\,}\!$	$\scriptstyle {q'+p\,}\!$
раздел 3	s.2.right - Инволюционное дополнение		$\scriptstyle {=\,}\!$	$\scriptstyle {(q'+p)''\,}\!$
раздел 4	s.3.right - законы Де Моргана применяются один раз		$\scriptstyle {=\,}\!$	$\scriptstyle {(qp')'\,}\!$
с.5	s.4.right - Коммутативный закон		$\scriptstyle {=\,}\!$	$\scriptstyle {(p'q)'\,}\!$
раздел 6	с.5.право		$\scriptstyle {=\,}\!$	$\scriptstyle {(p{\tilde {\leftarrow }}q)'\,}\!$
стр.7	с.6.право		$\scriptstyle {=\,}\!$	$\scriptstyle {p\leftarrow q\,}\!$
стр.8	раздел 7.право		$\scriptstyle {=\,}\!$	$\scriptstyle {q\rightarrow p\,}\!$
с.9	с.1.слева = с.8.справа	$\scriptstyle {\operatorname {dual} (q{\tilde {\leftarrow }}p)=q\rightarrow p\,}\!$

Информатика [ править ]

Пример обратной неимпликации в информатике можно найти при выполнении правого внешнего соединения для набора таблиц из базы данных , если исключаются записи, не соответствующие условию соединения из «левой» таблицы. ^[3]

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

^ Лехтонен, Ээро и Пойконен, Дж. Х.
^ Кнут 2011 , с. 49
^ «Визуальное объяснение SQL-соединений» . 11 октября 2007 г. Архивировано из оригинала 15 февраля 2014 г. Проверено 24 марта 2013 г.

Кнут, Дональд Э. (2011). Искусство компьютерного программирования , Том 4A: Комбинаторные алгоритмы, Часть 1 (1-е изд.). Аддисон-Уэсли Профессионал. ISBN 978-0-201-03804-0 .

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

СМИ, связанные с невмешательством Converse, на Викискладе?

[1] Лехтонен, Ээро и Пойконен, Дж. Х.

[Knuth-2] Кнут 2011 , с. 49

[3] «Визуальное объяснение SQL-соединений» . 11 октября 2007 г. Архивировано из оригинала 15 февраля 2014 г. Проверено 24 марта 2013 г.

[1]

[2]

[3]

v т и Общие логические связи
Тавтология / Правда $\top$
Альтернативное отрицание ( ворота NAND ) $\uparrow$ Обратная импликация $\leftarrow$ Импликация ( ворота IMPLY ) $\rightarrow$ Дизъюнкция ( ворота ИЛИ ) $\lor$
Отрицание ( НЕ ворота ) $\neg$ Эксклюзивное или ( ворота XOR ) $\not \leftrightarrow$ Двуусловный ( ворота XNOR ) $\leftrightarrow$ Оператор ( цифровой буфер )
Совместное отрицание ( ворота NOR ) $\downarrow$ Неимпликация ( ворота NIMPLY ) $\nrightarrow$ Обратная неимпликация $\nleftarrow$ Соединение ( ворота И ) $\land$
Противоречие / Ложь $\bot$
Философский портал