Дискретная математика - правила вывода

Чтобы вывести новые утверждения из утверждений, истинность которых нам уже известна, Rules of Inference используются.

Для чего нужны правила вывода?

Математическая логика часто используется для логических доказательств. Доказательства - это действительные аргументы, которые определяют истинность математических утверждений.

Аргумент - это последовательность утверждений. Последнее утверждение является заключением, а все предшествующие ему утверждения называются предпосылками (или гипотезами). Перед заключением ставится символ «$ \ поэтому $» (читать поэтому). Действительный аргумент - это аргумент, заключение которого следует из истинности посылок.

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

Таблица правил вывода

Правило вывода	название	Правило вывода	название
$$ \ begin {matrix} P \\ \ hline \, следовательно, P \ lor Q \ end {matrix} $$	Дополнение	$$ \ begin {matrix} P \ lor Q \\ \ lnot P \\ \ hline \, следовательно, Q \ end {matrix} $$	Дизъюнктивный силлогизм
$$ \ begin {matrix} P \\ Q \\ \ hline \, следовательно, P \ land Q \ end {matrix} $$	Соединение	$$ \ begin {matrix} P \ rightarrow Q \\ Q \ rightarrow R \\ \ hline \, следовательно, P \ rightarrow R \ end {matrix} $$	Гипотетический силлогизм
$$ \ begin {matrix} P \ land Q \\ \ hline \ поэтому P \ end {matrix} $$	Упрощение	$$ \ begin {matrix} (P \ rightarrow Q) \ land (R \ rightarrow S) \\ P \ lor R \\ \ hline \, следовательно, Q \ lor S \ end {matrix} $$	Конструктивная дилемма
$$ \ begin {matrix} P \ rightarrow Q \\ P \\ \ hline \ поэтому Q \ end {matrix} $$	Modus Ponens	$$ \ begin {matrix} (P \ rightarrow Q) \ land (R \ rightarrow S) \\ \ lnot Q \ lor \ lnot S \\ \ hline \ поэтому \ lnot P \ lor \ lnot R \ end {matrix} $$	Разрушительная дилемма
$$ \ begin {matrix} P \ rightarrow Q \\ \ lnot Q \\ \ hline \ поэтому \ lnot P \ end {matrix} $$	Modus Tollens

Дополнение

Если P является предпосылкой, мы можем использовать правило сложения, чтобы получить $ P \ lor Q $.

$$ \ begin {matrix} P \\ \ hline \, следовательно, P \ lor Q \ end {matrix} $$

пример

Пусть P будет утверждением: «Он очень усердно учится» верно

Поэтому - «Либо он очень много учится, либо очень плохо учится». Здесь Q - предложение «он очень плохой ученик».

Соединение

Если P и Q - две предпосылки, мы можем использовать правило конъюнкции, чтобы получить $ P \ land Q $.

$$ \ begin {matrix} P \\ Q \\ \ hline \, следовательно, P \ land Q \ end {matrix} $$

пример

Пусть П - «Он очень много учится»

Пусть Q - «Он лучший мальчик в классе»

Поэтому - «Он очень много учится и лучший мальчик в классе».

Упрощение

Если $ P \ land Q $ является предпосылкой, мы можем использовать правило упрощения, чтобы получить P.

$$ \ begin {matrix} P \ land Q \\ \ hline \ поэтому P \ end {matrix} $$

пример

«Он очень много учится и лучший мальчик в классе», $ P \ land Q $

Поэтому - «Он очень много учится».

Modus Ponens

Если P и $ P \ rightarrow Q $ - две посылки, мы можем использовать Modus Ponens для вывода Q.

$$ \ begin {matrix} P \ rightarrow Q \\ P \\ \ hline \ поэтому Q \ end {matrix} $$

пример

«Если у вас есть пароль, то вы можете войти в facebook», $ P \ rightarrow Q $

«У вас есть пароль», П

Поэтому - «Вы можете авторизоваться на фейсбуке».

Modus Tollens

Если $ P \ rightarrow Q $ и $ \ lnot Q $ - две посылки, мы можем использовать метод Толленса для вывода $ \ lnot P $.

$$ \ begin {matrix} P \ rightarrow Q \\ \ lnot Q \\ \ hline \ поэтому \ lnot P \ end {matrix} $$

пример

«Если у вас есть пароль, то вы можете войти в facebook», $ P \ rightarrow Q $

«Вы не можете войти в facebook», $ \ lnot Q $

Поэтому - «У вас нет пароля».

Дизъюнктивный силлогизм

Если $ \ lnot P $ и $ P \ lor Q $ - две посылки, мы можем использовать дизъюнктивный силлогизм для вывода Q.

$$ \ begin {matrix} \ lnot P \\ P \ lor Q \\ \ hline \, следовательно, Q \ end {matrix} $$

пример

«Мороженое без запаха ванили», $ \ lnot P $

«Мороженое со вкусом ванили или шоколада», $ P \ lor Q $

Поэтому - «Мороженое со вкусом шоколада».

Гипотетический силлогизм

Если $ P \ rightarrow Q $ и $ Q \ rightarrow R $ - две посылки, мы можем использовать гипотетический силлогизм для вывода $ P \ rightarrow R $

$$ \ begin {matrix} P \ rightarrow Q \\ Q \ rightarrow R \\ \ hline \, следовательно, P \ rightarrow R \ end {matrix} $$

пример

«Если пойдет дождь, я не пойду в школу», $ P \ rightarrow Q $

«Если я не пойду в школу, мне не нужно будет делать домашнее задание», $ Q \ rightarrow R $

Поэтому - «Если пойдет дождь, мне не нужно будет делать домашнее задание».

Конструктивная дилемма

Если $ (P \ rightarrow Q) \ land (R \ rightarrow S) $ и $ P \ lor R $ являются двумя предпосылками, мы можем использовать конструктивную дилемму для вывода $ Q \ lor S $.

$$ \ begin {matrix} (P \ rightarrow Q) \ land (R \ rightarrow S) \\ P \ lor R \\ \ hline \, следовательно, Q \ lor S \ end {matrix} $$

пример

«Если пойдет дождь, я уйду», $ (P \ rightarrow Q) $

«Если на улице жарко, пойду в душ», $ (R \ rightarrow S) $

«Либо будет дождь, либо на улице жарко», $ P \ lor R $

Поэтому - «пойду в отпуск или пойду в душ».

Разрушительная дилемма

Если $ (P \ rightarrow Q) \ land (R \ rightarrow S) $ и $ \ lnot Q \ lor \ lnot S $ - две посылки, мы можем использовать деструктивную дилемму для вывода $ \ lnot P \ lor \ lnot R $.

$$ \ begin {matrix} (P \ rightarrow Q) \ land (R \ rightarrow S) \\ \ lnot Q \ lor \ lnot S \\ \ hline \ поэтому \ lnot P \ lor \ lnot R \ end {matrix} $$

пример

«Если пойдет дождь, я уйду», $ (P \ rightarrow Q) $

«Если на улице жарко, пойду в душ», $ (R \ rightarrow S) $

«Либо я не пойду в отпуск, либо не пойду в душ», $ \ lnot Q \ lor \ lnot S $

Поэтому - «Либо не дождь, либо на улице не жарко»