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

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

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

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

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

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

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

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

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

Модус Поненс

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

Модус Толленс

прибавление

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

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

пример

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

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

конъюнкция

Если P и Q - две предпосылки, мы можем использовать правило Conjunction для получения $ 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 $

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

Модус Поненс

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

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

пример

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

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

Поэтому - «Вы можете войти в Facebook»

Модус Толленс

Если $ 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 $

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