Uma inferência lógica: $\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $ sem usar tabelas de verdade
Prove a validade da seguinte inferência (NÃO use tabelas de verdade):
$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $$ Eu desenhei uma tabela de verdade que mostra que a proposição: $((p\implies q) \land (q\implies r)) \implies (p\implies r)$é uma tautologia, mas não teve sucesso em manipular as premissas usando regras de inferência lógica para mostrar o resultado.
Por favor, dê alguns conselhos.
Respostas
Usando uma notação ligeiramente diferente - Cálculo Sequencial - podemos construir a seguinte árvore de prova de dedução natural:
$$\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}$$
Assim, concluímos que a inferência é válida: $$\left\lvert\!\begin{split} &p\to q\\&q\to r\\\hline &p\to r\end{split}\right.$$
As regras usadas - onde $\Gamma, \Delta$são listas de declarações e$\varphi, \psi$ são declarações simples - são:
$\textsf{ID}$: Identidade (ou suposição) $\qquad\begin{split}~\\\hline\Gamma,\varphi&\vdash\varphi\end{split}$
Trivialmente: você pode derivar uma afirmação se for assumida junto com uma lista adicional (possivelmente vazia) de suposições.
${\to}\mathsf E$: Eliminação condicional: $\qquad\begin{split}\Gamma&\vdash\varphi\\\Delta&\vdash \varphi\to \psi\\\hline\Gamma\cup\Delta&\vdash \psi\end{split}$
Se uma condicional pode ser derivada de uma lista de declarações, e seu antecedente pode ser derivado de outra lista, então podemos inferir que o consequente pode ser derivado da união das listas.
${\to}\mathsf I$: Introdução condicional: $\qquad\begin{split}\Gamma,\varphi&\vdash \psi\\\hline\Gamma&\vdash\varphi\to\psi\end{split}$
Se um consequente pode ser derivado de uma lista de declarações incluindo um antecedente, então podemos inferir que a respectiva condicional pode ser derivada da lista.
Essa inferência é um exemplo de descartar uma suposição. No final de uma prova, todas as suposições, exceto para as instalações, precisam ter sido devidamente descartadas.
Aqui, assumimos três afirmações, as duas premissas com a adição do antecedente de nossa conclusão. Nós descartamos essa terceira suposição depois de fazer com sucesso nossa derivação do conseqüente.
Queremos provar
$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{p\implies r}$$
Introduza p no contexto:
$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ p \end{matrix}}{r}$$
Coloque junto $p\implies q$ e $p$ deduzir $q$:
$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ p \\ q \end{matrix}}{r}$$
Coloque junto $q\implies r$ e $q$ deduzir $r$:
$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ p \\ q \\ r \end{matrix}}{r}$$
QED
Use a tautologia $$(p\implies q)\implies((q\implies r)\implies(p\implies r))$$em vez disso, aplique o Modus Ponens duas vezes com as premissas fornecidas. Como alternativa, use a tautologia$$\varphi\implies(\psi\implies (\varphi\land\psi))$$ concluir $$\frac{\begin{matrix} \varphi \\ \psi\end{matrix}}{(\varphi\land\psi)} $$ e então usar a tautologia que você deu para provar $$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{ p\implies r} $$
Por uma questão de completude: dadas as premissas, adicione a tautologia acima concluir
$$\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)}$$
e depois
$$\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}$$
que completa a prova. Para a alternativa, primeiro use a regra fornecida para obter
$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{( p\implies q)\land(q\implies r)}$$
e então, usando a outra tautologia, temos
$$\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}$$
Use o modus ponens duas vezes e a introdução da condição:
$p\implies q$ e $p$ significa $q$ é verdadeiro. (primeiro uso). $q\implies r$ e $q$ é verdadeiro significa $r$é verdade. (segundo uso). Tão dado$p \implies q$ e $q\implies r$ então por introdução condicional $p$ ser verdadeiro significa $r$é verdade. então$p\implies r$.
Ok, acho que entendi:
Se tomarmos a notação $\phi\vdash \psi$ para significar "deveríamos assumir $\phi$ nós podemos derivar $\psi$ então:
$p\implies q$ (dado)
$p \implies r$ (qiven)
$p\vdash p$ (assumir que algo é assumir algo. $\mu\vdash \mu$ é sempre verdade porque se assumirmos $\mu$ nós podemos derivar $\mu$... porque assumimos que é verdade. Isso não quer dizer que estamos afirmando que é verdade (como suas afirmações no comentário sobre "permanecer nas premissas iniciais" sugerem que você acredita); isto é, sob uma hipótese, se fosse verdade, poderíamos derivar. Claro, se não for verdade, o que derivamos não será relevante.)
$p\vdash p\implies q$ ($p\implies q$ é uma verdade dada se assumirmos $p$ou não. Para cada afirmação verdadeira$T$ então $\mu\vdash T$sempre será verdade. E eu acho$\mu\vdash F$ sempre será falso.)
$p\vdash q$ (modus ponens)
$p\vdash q\to r$ ($q\implies r$ é uma verdade dada se assumirmos $p$ ou não)
$p\vdash r$ (modus ponens)
$p\implies r$ (Introdução condicional;)
(esta é uma regra básica. Em inglês, se assumindo $\mu$ nós podemos derivar $\psi$ então $\mu \implies \psi$ deve ser verdade.)
Aqui está uma prova usando regras de dedução natural:
$\vdash((p\implies q)\land(q\implies r))\implies (p\implies r)$
- $((p\implies q)\land(q\implies r))$ - suposição
- $\mid\underline{\quad p}$ - suposição
- $\mid\quad p\implies q$ - Eliminação de regra de $\land$ dentro $1.$
- $\mid\quad q$ - Eliminação de regra de $\implies$ dentro $2.,\,3.$
- $\mid\quad q\implies r$ - Eliminação de regra de $\land$ dentro $1.$
- $\mid\quad r$ - regra de eliminação de $\implies$ dentro $4.,\,5.$
- $p\implies r$ - Introdução de regra de $\implies$ dentro $2.,\,6.$ (suposição próxima 2.)
- $((p\implies q)\land(q\implies r))\implies (p\implies r)$ - Introdução de regra de $\implies$ dentro $1.,\,7.$ (suposição próxima $1.$)