Логический вывод: $\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $ без использования таблиц истинности

Aug 18 2020

Докажите справедливость следующего вывода (НЕ используйте таблицы истинности):

$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $$ Я нарисовал таблицу истинности, которая показывает, что утверждение: $((p\implies q) \land (q\implies r)) \implies (p\implies r)$является тавтологией, но не удалось манипулировать предпосылками с помощью правил логического вывода, чтобы показать результат.
Пожалуйста, дайте совет.

Ответы

7 GrahamKemp Aug 19 2020 at 01:51

Используя несколько другие обозначения - последовательное исчисление - мы можем построить следующее дерево доказательства естественного вывода:

$$\dfrac{\dfrac{\dfrac{\dfrac{}{p\vdash p}{\tiny\textsf{ID}}~\dfrac{}{p\to q\vdash p\to q}{\tiny\textsf{ID}}}{p,p\to q\vdash q}{\tiny{\to}\mathsf E}~\dfrac{}{q\to r\vdash q\to r}{\tiny\textsf{ID}}}{p,p\to q,q\to r\vdash r}{\tiny{\to}\mathsf E}}{p\to q,q\to r\vdash p\to r}{\tiny{\to}\mathsf I}$$

Таким образом, мы заключаем, что вывод верен: $$\left\lvert\!\begin{split} &p\to q\\&q\to r\\\hline &p\to r\end{split}\right.$$

Используемые правила - где $\Gamma, \Delta$являются списки заявлений и$\varphi, \psi$ одиночные утверждения - это:

$\textsf{ID}$: Личность (или предположение) $\qquad\begin{split}~\\\hline\Gamma,\varphi&\vdash\varphi\end{split}$

Тривиально: вы можете вывести утверждение, если оно предполагается вместе с дополнительным (возможно, пустым) списком предположений.
${\to}\mathsf E$: Условное исключение: $\qquad\begin{split}\Gamma&\vdash\varphi\\\Delta&\vdash \varphi\to \psi\\\hline\Gamma\cup\Delta&\vdash \psi\end{split}$

Если условное выражение может быть получено из одного списка операторов, а его антецедент может быть получен из другого списка, тогда мы можем сделать вывод, что консеквент может быть получен из объединения списков.
${\to}\mathsf I$: Условное введение: $\qquad\begin{split}\Gamma,\varphi&\vdash \psi\\\hline\Gamma&\vdash\varphi\to\psi\end{split}$

Если консеквент может быть получен из списка операторов, включая антецедант, то мы можем сделать вывод, что соответствующее условное выражение может быть получено из списка.

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

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

6 rain1 Aug 18 2020 at 20:11

Мы хотим доказать

$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{p\implies r}$$

Введите p в контекст:

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ p \end{matrix}}{r}$$

Собрать вместе $p\implies q$ и $p$ выводить $q$:

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ p \\ q \end{matrix}}{r}$$

Собрать вместе $q\implies r$ и $q$ выводить $r$:

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ p \\ q \\ r \end{matrix}}{r}$$

QED

4 mrtaurho Aug 18 2020 at 20:16

Используйте тавтологию $$(p\implies q)\implies((q\implies r)\implies(p\implies r))$$взамен и примените Modus Ponens два раза в данном помещении. В качестве альтернативы используйте тавтологию$$\varphi\implies(\psi\implies (\varphi\land\psi))$$ заключить $$\frac{\begin{matrix} \varphi \\ \psi\end{matrix}}{(\varphi\land\psi)} $$ а затем используйте тавтологию, которую вы дали, чтобы доказать $$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{ p\implies r} $$

Для полноты: с учетом посылок добавить вышеприведенную тавтологию, заключить

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ (p\implies q)\implies((q\implies r)\implies(p\implies r)) \end{matrix}}{(q\implies r)\implies(p\implies r)}$$

а потом

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ (p\implies q)\implies((q\implies r)\implies(p\implies r))\\ (q\implies r)\implies(p\implies r) \end{matrix}}{p\implies r}$$

что завершает доказательство. Для альтернативы сначала используйте данное правило, чтобы получить

$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{( p\implies q)\land(q\implies r)}$$

а затем, используя другую тавтологию, имеем

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\( p\implies q)\land(q\implies r)\\ (( p\implies q)\land(q\implies r))\implies (p\implies r) \end{matrix}}{p\implies r}$$

2 fleablood Aug 18 2020 at 20:40

Дважды используйте modus ponens и ознакомьтесь с условиями:

$p\implies q$ и $p$ средства $q$ верно. (первое использование). $q\implies r$ и $q$ верно означает $r$правда. (второе использование). Так что$p \implies q$ и $q\implies r$ затем условным введением $p$ быть правдой означает $r$правда. Так$p\implies r$.

Хорошо, думаю, я понял:

Если взять обозначения $\phi\vdash \psi$ означать "если бы мы предполагали $\phi$ мы можем получить $\psi$ тогда:

$p\implies q$ (дано)

$p \implies r$ (qiven)

$p\vdash p$ (при условии, что что-то предполагает что-то. $\mu\vdash \mu$ всегда верно, потому что если мы предположим $\mu$ мы можем получить $\mu$... потому что мы предполагаем, что это правда. Это не значит, что мы утверждаем, что это правда (поскольку ваши утверждения в комментарии о «пребывании в исходных помещениях» подразумевают, что вы верите); это значит, что если бы это было правдой, мы могли бы вывести гипотетическое. Конечно , если это не правда , что то , что мы получаем не будет Релевент.)

$p\vdash p\implies q$ ($p\implies q$ это заданная правда, если мы предполагаем $p$или нет. За каждое верное утверждение$T$ тогда $\mu\vdash T$всегда будет правдой. И я думаю$\mu\vdash F$ всегда будет ложным.)

$p\vdash q$ (модус поненс)

$p\vdash q\to r$ ($q\implies r$ это заданная правда, если мы предполагаем $p$ или нет)

$p\vdash r$ (модус поненс)

$p\implies r$ (Условное введение;)

(это основное правило. На английском языке, если предположить $\mu$ мы можем получить $\psi$ тогда $\mu \implies \psi$ должно быть правдой.)