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

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

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

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

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

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

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

Правило вывода	название	Правило вывода	название
beginmatrixP hline следовательноP lorQ endmatrix $$\ begin {matrix} P \\ \ hline \ следовательно P \ lor Q \ end {matrix}$$	прибавление	beginmatrixP lorQ lnotP hline следовательноQ endmatrix $$\ begin {matrix} P \ lor Q \\ \ lnot P \\ \ hline \ следовательно Q \ end {matrix}$$	Дизъюнктивный силлогизм
beginmatrixPQ hline следовательноP landQ endmatrix $$\ begin {matrix} P \\ Q \\ \ hline \ следовательно P \ land Q \ end {matrix}$$	конъюнкция	beginmatrixP rightarrowQQ rightarrowR hline следовательноP rightarrowR endmatrix $$\ begin {matrix} P \ rightarrow Q \\ Q \ rightarrow R \\ \ hline \ следовательно P \ rightarrow R \ end {matrix}$$	Гипотетический силлогизм
beginmatrixP landQ hline следовательноP endmatrix $$\ begin {matrix} P \ land Q \\ \ hline \ следовательно P \ end {matrix}$$	упрощение	beginmatrix(P rightarrowQ) land(R rightarrowS)P lorR hline следовательноQ lorS endmatrix $$\ begin {matrix} (P \ rightarrow Q) \ land (R \ rightarrow S) \\ P \ lor R \\ \ hline \ следовательно Q \ lor S \ end {matrix}$$	Конструктивная дилемма
beginmatrixP rightarrowQP hline следовательноQ endmatrix $$\ begin {matrix} P \ rightarrow Q \\ P \\ \ hline \ следовательно Q \ end {matrix}$$	Модус Поненс	beginmatrix(P rightarrowQ) land(R rightarrowS) lnotQ lor lnotS hline следовательно lnotP lor lnotR endmatrix $$\ begin {matrix} (P \ rightarrow Q) \ land (R \ rightarrow S) \\ \ lnot Q \ lor \ lnot S \\ \ hline \ следовательно \ lnot P \ lor \ lnot R \ end {matrix}$$	Деструктивная Дилемма
beginmatrixP rightarrowQ lnotQ hline следовательно lnotP endmatrix $$\ begin {matrix} P \ rightarrow Q \\ \ lnot Q \\ \ hline \ следовательно \ lnot P \ end {matrix}$$	Модус Толленс

 beginmatrixP hline следовательноP lorQ endmatrix

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

прибавление

 beginmatrixP lorQ lnotP hline следовательноQ endmatrix

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

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

 beginmatrixPQ hline следовательноP landQ endmatrix

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

конъюнкция

 beginmatrixP rightarrowQQ rightarrowR hline следовательноP rightarrowR endmatrix

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

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

 beginmatrixP landQ hline следовательноP endmatrix

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

упрощение

 beginmatrix(P rightarrowQ) land(R rightarrowS)P lorR hline следовательноQ lorS endmatrix

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

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

 beginmatrixP rightarrowQP hline следовательноQ endmatrix

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

Модус Поненс

 beginmatrix(P rightarrowQ) land(R rightarrowS) lnotQ lor lnotS hline следовательно lnotP lor lnotR endmatrix

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

Деструктивная Дилемма

 beginmatrixP rightarrowQ lnotQ hline следовательно lnotP endmatrix

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

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

прибавление

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

 beginmatrixP hline следовательноP lorQ endmatrix

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

пример

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

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

конъюнкция

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

 beginmatrixPQ hline следовательноP landQ endmatrix

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

пример

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

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

Поэтому — «Он очень усердно учится, и он лучший мальчик в классе»

упрощение

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

 beginmatrixP landQ hline следовательноP endmatrix

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

пример

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

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

Модус Поненс

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

 beginmatrixP rightarrowQP hline следовательноQ endmatrix

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

пример

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

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

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

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

Если P rightarrowQ$P \ rightarrow Q$ и  lnotQ$\ lnot Q$ — две предпосылки, мы можем использовать Модус Толленс для получения  lnotP$\ lnot P$.

 beginmatrixP rightarrowQ lnotQ hline следовательно lnotP endmatrix

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

пример

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

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

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

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

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

 beginmatrix lnotPP lorQ hline следовательноQ endmatrix

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

пример

«Мороженое не ванильное»,  lnotP$\ lnot P$

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

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

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

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

 beginmatrixP rightarrowQQ rightarrowR hline следовательноP rightarrowR endmatrix

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

пример

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

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

Поэтому — «Если идет дождь, мне не нужно делать домашнее задание»

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

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

 beginmatrix(P rightarrowQ) land(R rightarrowS)P lorR hline следовательноQ lorS endmatrix

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

пример

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

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

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

Поэтому — «Я уйду или пойду в душ»

Деструктивная Дилемма

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

 beginmatrix(P rightarrowQ) land(R rightarrowS) lnotQ lor lnotS hline следовательно lnotP lor lnotR endmatrix

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

пример

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

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

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

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