Список правил вывода - List of rules of inference

Это список правила вывода, логические законы, относящиеся к математическим формулам.

Вступление

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

Правила выписки разрешить вывод из субдеривации на основе временного предположения. Ниже обозначения

{ displaystyle varphi vdash psi}

указывает на такое отклонение от временного предположения ${ displaystyle varphi}$ к ${ displaystyle psi}$ .

Правила классического сентенциального исчисления

Сентенциальное исчисление также известно как пропозициональное исчисление.

Правила отрицания

Reductio ad absurdum (или же Отрицание Введение): ${ displaystyle varphi vdash psi}$; ${ displaystyle { underline { varphi vdash lnot psi}}}$; ${ displaystyle lnot varphi}$

Reductio ad absurdum (относящийся к закон исключенного среднего ): ${ Displaystyle lnot varphi vdash psi}$; ${ displaystyle { underline { lnot varphi vdash lnot psi}}}$; ${ displaystyle varphi}$

Исключительное противоречие quodlibet: ${ displaystyle varphi}$; ${ displaystyle { underline { lnot varphi}}}$; ${ displaystyle psi}$

Устранение двойного отрицания: ${ displaystyle { underline { lnot lnot varphi}}}$; ${ displaystyle varphi}$

Введение двойного отрицания: ${ displaystyle { underline { varphi quad quad}}}$; ${ Displaystyle lnot lnot varphi}$

Правила для условных выражений

Теорема дедукции (или же Условное введение ): ${ displaystyle { underline { varphi vdash psi}}}$; ${ displaystyle varphi rightarrow psi}$

Modus ponens (или же Условное исключение): ${ displaystyle varphi rightarrow psi}$; ${ displaystyle { underline { varphi quad quad quad}}}$; ${ displaystyle psi}$

Modus tollens: ${ displaystyle varphi rightarrow psi}$; ${ Displaystyle { подчеркивание { lnot psi quad quad quad}}}$; ${ displaystyle lnot varphi}$

Правила союзов

Пристройка (или же Введение в соединение)

{ displaystyle varphi}

{ displaystyle { underline { psi quad quad }}}

{ displaystyle varphi land psi}

Упрощение (или же Устранение соединения)

{ displaystyle { underline { varphi land psi}}}

{ displaystyle varphi}

{ displaystyle { underline { varphi land psi}}}

{ displaystyle psi}

Правила дизъюнкций

Добавление (или же Дизъюнкция Введение): ${ displaystyle { underline { varphi quad quad }}}$; ${ displaystyle varphi lor psi}$

{ displaystyle { underline { psi quad quad }}}

{ displaystyle varphi lor psi}

Анализ случая (или же Доказательства случаями или же Аргумент по делам или же Устранение дизъюнкции): ${ displaystyle varphi rightarrow chi}$; ${ displaystyle psi rightarrow chi}$; ${ displaystyle { underline { varphi lor psi}}}$; ${ displaystyle chi}$

Дизъюнктивный силлогизм: ${ displaystyle varphi lor psi}$; ${ Displaystyle { подчеркивание { lnot varphi quad quad}}}$; ${ displaystyle psi}$

{ displaystyle varphi lor psi}

{ Displaystyle { подчеркивание { lnot psi quad quad}}}

{ displaystyle varphi}

Конструктивная дилемма: ${ displaystyle varphi rightarrow chi}$; ${ Displaystyle psi rightarrow xi}$; ${ displaystyle { underline { varphi lor psi}}}$; ${ Displaystyle чи лор хи}$

Правила для двухусловных

Двузначное введение: ${ displaystyle varphi rightarrow psi}$; ${ displaystyle { underline { psi rightarrow varphi}}}$; ${ displaystyle varphi leftrightarrow psi}$

Двуусловное исключение: ${ displaystyle varphi leftrightarrow psi}$; ${ displaystyle { underline { varphi quad quad}}}$; ${ displaystyle psi}$

{ displaystyle varphi leftrightarrow psi}

{ displaystyle { underline { psi quad quad}}}

{ displaystyle varphi}

{ displaystyle varphi leftrightarrow psi}

{ Displaystyle { подчеркивание { lnot varphi quad quad}}}

{ Displaystyle lnot psi}

{ displaystyle varphi leftrightarrow psi}

{ Displaystyle { подчеркивание { lnot psi quad quad}}}

{ displaystyle lnot varphi}

{ displaystyle varphi leftrightarrow psi}

{ displaystyle { underline { psi lor varphi}}}

{ displaystyle psi land varphi}

{ displaystyle varphi leftrightarrow psi}

{ Displaystyle { подчеркивание { lnot psi lor lnot varphi}}}

{ Displaystyle lnot psi land lnot varphi}

Правила классической исчисление предикатов

В следующих правилах ${ Displaystyle varphi ( бета / альфа)}$ точно как ${ displaystyle varphi}$ за исключением срока ${ displaystyle beta}$ где бы ${ displaystyle varphi}$ имеет свободную переменную ${ displaystyle alpha}$ .

Универсальное обобщение (или же Универсальное введение ): ${ displaystyle { underline { varphi {( beta / alpha)}}}}$; ${ Displaystyle forall alpha , varphi}$

Ограничение 1: ${ displaystyle beta}$ это переменная, которая не встречается в ${ displaystyle varphi}$ .
Ограничение 2: ${ displaystyle beta}$ не упоминается ни в каких гипотезах или невыполненных предположениях.

Универсальное воплощение (или же Универсальное исключение ): ${ Displaystyle forall alpha , varphi}$; ${ displaystyle { overline { varphi {( beta / alpha)}}}}$

Ограничение: Нет свободного появления ${ displaystyle alpha}$ в ${ displaystyle varphi}$ входит в сферу действия квантора, определяющего количественную оценку переменной, встречающейся в ${ displaystyle beta}$ .

Экзистенциальное обобщение (или же Экзистенциальное введение ): ${ displaystyle { underline { varphi ( beta / alpha)}}}$; ${ Displaystyle существует альфа , varphi}$

Ограничение: Нет свободного появления ${ displaystyle alpha}$ в ${ displaystyle varphi}$ входит в сферу действия квантора, определяющего количественную оценку переменной, встречающейся в ${ displaystyle beta}$ .

Экзистенциальное воплощение (или же Экзистенциальное устранение ): ${ Displaystyle существует альфа , varphi}$; ${ displaystyle { underline { varphi ( beta / alpha) vdash psi}}}$; ${ displaystyle psi}$

Ограничение 1: ${ displaystyle beta}$ это переменная, которая не встречается в ${ displaystyle varphi}$ .
Ограничение 2: не существует ни свободного, ни ограниченного появления ${ displaystyle beta}$ в ${ displaystyle psi}$ .
Ограничение 3: ${ displaystyle beta}$ не упоминается ни в каких гипотезах или невыполненных предположениях.

Правила субструктурная логика

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

Правило ослабления (или монотонность вывода ) (он же теорема о запрете клонирования )

{ displaystyle alpha vdash beta}

{ displaystyle { overline { alpha, alpha vdash beta}}}

Правило сжатия (или идемпотентность следствия ) (он же теорема о запрете удаления )

{ displaystyle { underline { alpha, alpha, gamma vdash beta}}}

{ displaystyle alpha, gamma vdash beta}

Таблица: Правила вывода

Вышеуказанные правила можно обобщить в следующей таблице.^[1] "Тавтология Столбец "показывает, как интерпретировать обозначение данного правила.

Правила вывода	Тавтология	Имя
${ displaystyle { begin {align} p p rightarrow q поэтому { overline {q quad quad quad}} конец {выровнено}}}$	${ Displaystyle (п клин (п rightarrow q)) rightarrow q}$	Modus ponens
${ displaystyle { begin {align} neg q p rightarrow q поэтому { overline { neg p quad quad quad}} конец {выровнено}}}$	${ displaystyle ( neg q клин (p rightarrow q)) rightarrow neg p}$	Modus tollens
${ displaystyle { begin {выровнено} (p vee q) vee r поэтому { overline {p vee (q vee r)}} конец {выровнено}}}$	${ Displaystyle ((п vee q) vee r) rightarrow (p vee (q vee r))}$	Ассоциативный
${ displaystyle { begin {align} p wedge q , следовательно, { overline {q wedge p}} end {align}}}$	${ Displaystyle (п клин q) rightarrow (д клин р)}$	Коммутативный
${ displaystyle { begin {align} p rightarrow q q rightarrow p , следовательно, { overline {p leftrightarrow q}} конец {выровнено}}}$	${ Displaystyle ((п rightarrow q) клин (q rightarrow p)) rightarrow ( p leftrightarrow q)}$	Закон двусмысленных предложений
${ Displaystyle { begin {выровнен} (п клин q) rightarrow r поэтому { overline {p rightarrow (q rightarrow r)}} конец {выровнен}}}$	${ Displaystyle ((п клин q) rightarrow г) rightarrow (р rightarrow (д rightarrow г))}$	Экспорт
${ displaystyle { begin {align} p rightarrow q поэтому { overline { neg q rightarrow neg p}} end {align}}}$	${ Displaystyle (п rightarrow q) rightarrow ( neg q rightarrow neg p)}$	Закон транспозиции или противопоставления
${ displaystyle { begin {align} p rightarrow q q rightarrow r поэтому { overline {p rightarrow r}} конец {выровнено}}}$	${ Displaystyle ((п rightarrow q) клин (д rightarrow г)) rightarrow (р rightarrow г)}$	Гипотетический силлогизм
${ displaystyle { begin {align} p rightarrow q , следовательно, { overline { neg p vee q}} end {align}}}$	${ Displaystyle (п rightarrow q) rightarrow ( neg p vee q)}$	Материальное значение
${ Displaystyle { begin {выровнено} (п vee q) wedge r поэтому { overline {(p wedge r) vee (q wedge r)}} конец {выровнено}} }$	${ Displaystyle ((п vee q) клин г) rightarrow ((п клин г) vee (д клин г))}$	Распределительный
${ displaystyle { begin {align} p rightarrow q поэтому { overline {p rightarrow (p wedge q)}} конец {выровнено}}}$	${ Displaystyle (п rightarrow q) rightarrow (p rightarrow (п клин q))}$	Абсорбция
${ displaystyle { begin {align} p vee q neg p поэтому { overline {q quad quad quad}} конец {выровнено}}}$	${ Displaystyle ((п vee q) клин neg p) rightarrow q}$	Дизъюнктивный силлогизм
${ displaystyle { begin {align} p , следовательно, { overline {p vee q}} end {align}}}$	${ displaystyle p rightarrow (p vee q)}$	Добавление
${ displaystyle { begin {align} p wedge q , следовательно, { overline {p quad quad quad}} конец {выровнен}}}$	${ Displaystyle (п клин q) rightarrow p}$	Упрощение
${ displaystyle { begin {align} p q , следовательно, { overline {p wedge q}} end {align}}}$	${ Displaystyle ((p) клин (q)) rightarrow (p клин q)}$	Соединение
${ displaystyle { begin {align} p , следовательно, { overline { neg neg p}} end {align}}}$	${ displaystyle p rightarrow ( neg neg p)}$	Двойное отрицание
${ displaystyle { begin {align} p vee p , следовательно, { overline {p quad quad quad}} end {align}}}$	${ displaystyle (p vee p) rightarrow p}$	Дизъюнктивное упрощение
${ displaystyle { begin {align} p vee q neg p vee r , следовательно, { overline {q vee r}} конец {выровнено}}}$	${ Displaystyle ((п vee q) клин ( neg p vee r)) rightarrow (q vee r)}$	Разрешение
${ Displaystyle { begin {выровнено} p rightarrow q r rightarrow q p vee r поэтому { overline {q quad quad quad}} end {выровнено}} }$	${ Displaystyle ((п rightarrow q) клин (г rightarrow q) клин (p vee r)) rightarrow q}$	Устранение дизъюнкции

Все правила используют основные логические операторы. Полная таблица «логических операторов» обозначена значком таблица истинности, дающих определения всех возможных (16) функций истинности 2 логические переменные (п, q):

п	q	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Т	Т	F	F	F	F	F	F	F	F	Т	Т	Т	Т	Т	Т	Т	Т
Т	F	F	F	F	F	Т	Т	Т	Т	F	F	F	F	Т	Т	Т	Т
F	Т	F	F	Т	Т	F	F	Т	Т	F	F	Т	Т	F	F	Т	Т
F	F	F	Т	F	Т	F	Т	F	Т	F	Т	F	Т	F	Т	F	Т

где T = true и F = false, а столбцы являются логическими операторами: 0, ложный, Противоречие; 1, НИ, Логическое ИЛИ (Стрела Пирса); 2, Конверс без импликации; 3, ¬p, Отрицание; 4, Существенное отсутствие импликации; 5, ¬q, Отрицание; 6, XOR, Исключительная дизъюнкция; 7, NAND, Логическая И-НЕ (Ход Шеффера); 8, И, Логическое соединение; 9, XNOR, Если и только если, Логическая двусмысленность; 10, q, Функция проекции; 11, если / то, Логическое следствие; 12, п, Функция проекции; 13, то / если, Обратное значение; 14, ИЛИ ЖЕ, Логическая дизъюнкция; 15, истинный, Тавтология.

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

Оператор столбца 14 (ИЛИ) показывает Правило сложения: когда п= T (гипотеза выбирает первые две строки таблицы), мы видим (в столбце 14), что п∨q= Т.
Мы также можем видеть, что с той же предпосылкой верны и другие выводы: столбцы 12, 14 и 15 - T.
Оператор столбца 8 (И) показывает Правило упрощения: когда п∧q= T (первая строка таблицы), видим, что п= Т.
Исходя из этой предпосылки, мы также заключаем, что q= Т, п∨q= T и т.д., как показано в столбцах 9-15.
Оператор столбца 11 (IF / THEN) показывает Правило Modus ponens: когда п→q= T и п= T только одна строка таблицы истинности (первая) удовлетворяет этим двум условиям. В этой строке q тоже верно. Следовательно, если p → q истинно и p истинно, q также должно быть истинным.

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

Пример 1

Рассмотрим следующие предположения: «Если сегодня идет дождь, то мы не пойдем на каноэ сегодня. Если мы не отправимся на каноэ сегодня, то мы отправимся на каноэ завтра». Следовательно (Математический символ для «поэтому» является ${ displaystyle поэтому}$ ), если сегодня пойдет дождь, завтра мы отправимся в поход на каноэ ». Чтобы воспользоваться правилами вывода из приведенной выше таблицы, мы позволили ${ displaystyle p}$ предложение "Если сегодня пойдет дождь", ${ displaystyle q}$ быть «Мы сегодня на каноэ не пойдем» и пусть ${ displaystyle r}$ be «Завтра мы отправимся в поход на каноэ». Тогда этот аргумент имеет вид:

${ displaystyle { begin {align} p rightarrow q q rightarrow r поэтому { overline {p rightarrow r}} конец {выровнено}}}$

Пример 2

Рассмотрим более сложный набор предположений: «Сегодня не солнечно, и холоднее, чем вчера». «Мы будем купаться, только если будет солнечно», «Если мы не будем купаться, то у нас будет барбекю» и «Если у нас будет барбекю, то мы будем дома к закату» приводят к заключению » Мы будем дома к закату ". Доказательство правилом вывода: Пусть ${ displaystyle p}$ быть предложением "Сегодня солнечно", ${ displaystyle q}$ предложение «Холоднее, чем вчера», ${ displaystyle r}$ предложение "Пойдем купаться", ${ displaystyle s}$ предложение «У нас будет шашлык», и ${ displaystyle t}$ предложение «К закату будем дома». Тогда гипотезы становятся ${ displaystyle neg p wedge q, r rightarrow p, neg r rightarrow s}$ и ${ displaystyle s rightarrow t}$ . Используя нашу интуицию, мы предполагаем, что вывод может быть таким: ${ displaystyle t}$ . Используя таблицу правил вывода, мы можем легко доказать гипотезу:

Шаг	Причина
1. ${ displaystyle neg p wedge q}$	Гипотеза
2. ${ displaystyle neg p}$	Упрощение с использованием шага 1
3. ${ displaystyle r rightarrow p}$	Гипотеза
4. ${ displaystyle neg r}$	Modus tollens с использованием шагов 2 и 3
5. ${ displaystyle neg r rightarrow s}$	Гипотеза
6. ${ displaystyle s}$	Modus ponens с использованием шагов 4 и 5
7. ${ displaystyle s rightarrow t}$	Гипотеза
8. ${ displaystyle t}$	Modus ponens с использованием шагов 6 и 7