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

Aug 18 2020

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

7 GrahamKemp Aug 19 2020 at 01:51

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.

6 rain1 Aug 18 2020 at 20:11

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

4 mrtaurho Aug 18 2020 at 20:16

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

2 fleablood Aug 18 2020 at 20:40

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.)

2 Maurocurto Aug 18 2020 at 21:19

Aqui está uma prova usando regras de dedução natural:

$\vdash((p\implies q)\land(q\implies r))\implies (p\implies r)$

  1. $((p\implies q)\land(q\implies r))$ - suposição
  2. $\mid\underline{\quad p}$ - suposição
  3. $\mid\quad p\implies q$ - Eliminação de regra de $\land$ dentro $1.$
  4. $\mid\quad q$ - Eliminação de regra de $\implies$ dentro $2.,\,3.$
  5. $\mid\quad q\implies r$ - Eliminação de regra de $\land$ dentro $1.$
  6. $\mid\quad r$ - regra de eliminação de $\implies$ dentro $4.,\,5.$
  7. $p\implies r$ - Introdução de regra de $\implies$ dentro $2.,\,6.$ (suposição próxima 2.)
  8. $((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.$)