[MCTB019-17] §1 — Demonstrações: Linguagem

Publicado em por

A linguagem que usamos nas demostrações é uma linguagem natural, como o português e o inglês. O estudo formal das deduções matematicamente corretas é feito na Lógica Matemática. Os lógicos contemporâneos

  1. constroem linguagens simbólicas, rigorosas e livres de ambiguidades e de contexto, adequadas para lidar com a relação de consequência. As linguagens possuem duas dimensões relevantes:
    • a sintática: os símbolos da linguagem e as regras de combinação às quais estão sujeitos para a construção dos termos e fórmulas;
    • a semântica define precisamente o significado das fórmulas.
  2. especificam os axiomas dentre as fórmulas bem formadas;
  3. especificam as regras de inferência que independem da semântica.

E assim temos uma LÓGICA.

Por que precisamos criar uma linguagem para formalizar as formas de raciocínio?
Para evitar os paradoxos e imprecisões da linguagem natural. Importante quando estudamos assuntos mais restritos, com menos complexidade, porém com maior exigência de rigor. A seguir daremos um esboço da lógica de primeira ordem, a qual tem poder expressivo suficiente para formalizar grande parte da matemática.

Nós não utilizamos a linguagem simbólica no dia-a-dia em Matemática, isso seria muito penoso, mas existe uma certa “convenção linguística quase universal” na escrita em linguagem natural nas sentenças matemáticas que nos faz aceitar as formas como rigorosas e não ambíguas.

A seguir daremos um esboço bastante informal da lógica de primeira ordem, a qual tem poder expressivo suficiente para formalizar praticamente toda a Matemática. O que veremos a seguir são alguns conceitos da Lógica de Predicados de primeira ordem apresentados de maneira ingênua para que entendamos o significado de certas expressões chaves que aparecem nas demonstrações escritas em português.

Definição 1 Uma sentença é uma é uma frase declarativa que assume um de dois valores: VERDADEIRO (V) ou FALSO (F). O valor é chamado de valor-verdade ou valor-lógico da sentença.

Não é necessário sabermos se a sentença é verdadeira ou falsa.

Exemplos:

  1. O time joga bem.
  2. O time ganhou o campeonato.
  3. O técnico é o culpado.
  4. Os torcedores estão felizes.
  5. O Sr. Temer está feliz.
  6. A Sra. Temer não está feliz.
  7. O suborno será pago.
  8. As mercadorias são entregues.
  9. {1+1=2}.
  10. {3>5}.

Do ponto de vista da linguagem natural é bastante restritivo. Mas, estamos mais interessado nos enunciados matemáticos

  1. Uma sequência limitada é convergente
  2. {27} é um quadrado perfeito
  3. O conjunto vazio é único

onde sentenças interrogativas ou imperativas não são importantes. Não são sentenças:

  1. {x^2} é positivo.
  2. {x} é a soma de quatro quadrados perfeitos.
  3. essa frase é falsa.
  4. vá estudar discreta.
  5. hoje tem festa?

1.1. Operadores lógicos:{\neg,\land,\lor,\rightarrow,\leftrightarrow}

Toda linguagem permite construir sentenças mais complexas a partir de outras.

  1. Os torcedores estão felizes e o técnico foi
    demitido.
  2. Samuel virá para a festa e Maximiliano não
    virá, ou Samuel não virá para a festa e Maximiliano vai
    se divertir.
  3. Se o time joga bem, então o time ganha
    o campeonato.
  4. Se o time não joga bem, então o técnico é o culpado.
  5. Se o time ganha o campeonato então os torcedores estão felizes.
  6. O suborno será pago se, e somente se, as mercadorias são entregues.
  7. {27} não é um quadrado perfeito.
  8. O conjunto vazio não é único.
  9. Os torcedores não estão felizes.

Uma sentença que não pode ser decomposta em sentenças ligadas pelos conectivos lógicos “e”, “ou”, “se … então”, “se, e só se” é uma sentença atômica.

O valor lógico de uma sentença depende do valor lógico das sentenças atômicas que a compõem, e da maneira como elas são combinadas pelos conectivos, de acordo com as regras abaixo. Sejam {A} e {B} sentenças

Definição 2 A negação de {A} é a sentença {\neg (A)} cujo valor-verdade é

{A} {\neg (A)}
{V} {F}
{F} {V}

Definição 3 A disjunção de {A} e {B} é a sentença {A \lor B} cujo valor-verdade é

{A} {B} {A \lor B}
{V} {V} {V}
{V} {F} {V}
{F} {V} {V}
{F} {F} {F}

A conjunção é a sentença {A\land B} cujo valor-verdade é

{A} {B} {A\land B}
{V} {V} {V}
{V} {F} {F}
{F} {V} {F}
{F} {F} {F}

Definição 4 A implicação é a sentença {A\rightarrow B} cujo valor-verdade é

{A} {B} {A \rightarrow B}
{V} {V} {V}
{V} {F} {F}
{F} {V} {V}
{F} {F} {V}

Exemplo:

Se a lua é verde então o sol é quadrado,

é uma implicação verdadeira.

A implicação

  • não pressupõe relação causa/efeito: se chove então o rio transborda.
  • Não deve ser entendido como equivalência: Se não comer a refeição então não ganha a sobremesa.

A recíproca de {A\rightarrow B} é {B\rightarrow A}. Observe que que há casos em que {A\rightarrow B} tem valor lógico diferente de {B\rightarrow A}.

A contrapositiva de {A\rightarrow B} é {\neg (B)\rightarrow \neg(A)}. Pode-se verificar que contrapositiva tem sempre o mesmo valor lógico que a sentença que a originou.

A implicação é um dos mais importantes conectivos da matemática, muitos teoremas são escritos na forma de implicações: se {A} (hipótese, premissa ou antecedente) é verdadeira, então {B} (tese, conclusão ou consequente) é verdadeira. Em português, a implicação pode ser expressa de muitas formas:

  • se {A} então {B}.
  • quando {A}, temos {B}.
  • sempre que {A}, temos {B}.
  • {B} sempre que {A}.
  • {B} se {A}.
  • {A} é suficiente para {B}.
  • {A} é uma mais forte que {B}.
  • se não {B}, então não {A}.
  • se {B} não vale, então {A} não vale.
  • não {A} se não {B}.
  • {A} é falsa sempre que {B} é falsa.
  • {B} é mais fraco que {A}.
  • {B} é necessário para {A}.

Definição 5 A bicondicional é a sentença {A\leftrightarrow B} cujo valor-verdade é

{A} {B} {A \leftrightarrow B}
{V} {V} {V}
{V} {F} {F}
{F} {V} {F}
{F} {F} {V}

O conectivo lógico “se e somente se” também pode ser expresso de várias maneiras

  • {A} é condição necessária e suficiente para {B}.
  • {A} e {B} são equivalentes.
  • se {A} então {B}, e se {B} então {A}.

As vezes usamos a abreviação ”{A} sse {B}”.

1.2. Tautologia e Contradição

Definição 6 Uma tautologia é uma sentença composta que é sempre verdadeira. Uma contradição é uma sentença composta que é sempre falsa.

Por exemplo {A\lor \neg(A)} e {(A\rightarrow B) \leftrightarrow (\neg(A)\lor B)} são tautologias e {A\land \neg(A)} é uma contradição.

Uma tautologia qualquer é denotada por {\mathbf{V}} e uma contradição qualquer por {\mathbf{F}}.

1.3. Equivalência lógica

Definição 7 Duas sentenças {A} e {B} são logicamente equivalentes se assumem o mesmo valor-verdade. A notação é {A\Leftrightarrow B}.

{A\Leftrightarrow B} é o mesmo que dizer que {A\leftrightarrow B} é tautologia.

Por exemplo {(A\rightarrow B) \Leftrightarrow (\neg(A)\lor B)} e {(A\leftrightarrow B) \Leftrightarrow (A\rightarrow B)\land(B\rightarrow A)}.

Teorema 1 Sejam {A,B,C} sentenças.

  1. Leis de identidade

    \displaystyle A\land \mathbf{V} \Leftrightarrow A \ \ \ \ \ (1)

    \displaystyle A\lor \mathbf{F} \Leftrightarrow A \ \ \ \ \ (2)

  2. Leis de dominação

    \displaystyle A\lor \mathbf{V} \Leftrightarrow \mathbf{V} \ \ \ \ \ (3)

    \displaystyle A\land \mathbf{F} \Leftrightarrow \mathbf{F} \ \ \ \ \ (4)

  3. Leis de idempotência

    \displaystyle A\land A \Leftrightarrow A \ \ \ \ \ (5)

    \displaystyle A\lor A \Leftrightarrow A \ \ \ \ \ (6)

  4. Lei da dupla negação {\neg(\neg(A)) \Leftrightarrow A}.
  5. Leis distributivas

    \displaystyle A \land (B \lor C) \Leftrightarrow (A \land B) \lor (A \land C) \ \ \ \ \ (7)

    \displaystyle A \lor (B \land C) \Leftrightarrow (A \lor B) \land (A \lor C) \ \ \ \ \ (8)

  6. Leis comutativas

    \displaystyle A \lor B \Leftrightarrow B \lor A \ \ \ \ \ (9)

    \displaystyle A \land B \Leftrightarrow B \land A \ \ \ \ \ (10)

  7. Leis de associativas

    \displaystyle A \lor (B \lor C) \Leftrightarrow (A \lor B) \lor C \ \ \ \ \ (11)

    \displaystyle A \land (B \land C) \Leftrightarrow (A \land B) \land C \ \ \ \ \ (12)

  8. Leis de De Morgan

    \displaystyle \neg(A \lor B)\Leftrightarrow \neg(A) \land \neg(B) \ \ \ \ \ (13)

    \displaystyle \neg(A \land B)\Leftrightarrow \neg(A) \lor \neg(B) \ \ \ \ \ (14)

  9. Contrapositiva {A\rightarrow B \Leftrightarrow \neg(B)\rightarrow \neg(A)}.
  10. Redução ao absurdo {A\rightarrow B \Leftrightarrow (A\land \neg(B))\rightarrow\mathbf{F}}.
  11. Leis de absorção

    \displaystyle A\lor (A\land B) \Leftrightarrow A \ \ \ \ \ (15)

    \displaystyle A\land (A\lor B) \Leftrightarrow A \ \ \ \ \ (16)

  12. Leis de inversa

    \displaystyle A\lor \neg(A) \Leftrightarrow \mathbf{V} \ \ \ \ \ (17)

    \displaystyle A\land \neg(A) \Leftrightarrow \mathbf{F} \ \ \ \ \ (18)

Prova: Exercício. \Box

Exercício 1 Verifique usando as leis acima que {(A\lor B) \land \neg(\neg(A)\land B)} é logicamente equivalente a {A}. (Solução)

Exercício 2 Verifique que {\neg(A\rightarrow B) \Leftrightarrow A\land \neg(B)}.

1.4. Implicação lógica

Sejam {A} e {B} sentenças.

Definição 8 Dizemos que {A} implica logicamente {B} se {A\rightarrow B} é uma tautologia e escrevemos {A\Rightarrow B} Nesse caso, dizemos também que {B} é uma consequência lógica de {A}.

Mais geralmente, sejam {P_1,P_2,\dots,P_n} e {Q} sentenças. Dizemos que essas sentenças {P_1,P_2,\dots,P_n} implicam logicamente {Q} se {P_1\land P_2 \land \cdots \land P_n \rightarrow Q} é uma tautologia e escrevemos {P_1\land P_2 \land \cdots \land P_n \Rightarrow Q}

Por exemplo, se {A\rightarrow B} é verdadeira, sua conclusão {B} pode ser verdadeira ou falsa; mas se tanto a implicação quanto a hipótese {A} são verdadeiras, então a conclusão {B} deve ser verdadeira, isto é

\displaystyle A \land (A\rightarrow B) \Rightarrow B.

Notemos que se {A\Leftrightarrow B} então {A\leftrightarrow B} é tautologia, portanto, {A\rightarrow B} é tautologia e {B\rightarrow A} é tautologia, ou seja {A\Rightarrow B} e {B\Rightarrow A}. Reciprocamente, se {A\Rightarrow B} e {B\Rightarrow A} então {A\rightarrow B} é tautologia e {B\rightarrow A} é tautologia, ou seja, {A\leftrightarrow B} é tautologia, logo {A\Leftrightarrow B}.

Exercício 3 Considere as sentenças

{A} é “Mané estuda”

{B} é “Mané joga futebol”

{C} é “Mané passa em discreta”

Então {A\rightarrow C}, {\neg(B)\rightarrow A}, {\neg(C)} implicam logicamente {B}.

Teorema 2 Sejam {A,B,C} sentenças arbitrárias.

  1. Lei da adição: {A \Rightarrow A\lor B}.
  2. Lei da simplificação: {A\land B \Rightarrow A}.
  3. Lei do modus ponens: {A \land (A\rightarrow B) \Rightarrow B}.
  4. Lei do modus tollens: {(A\rightarrow B) \land \neg(B) \Rightarrow \neg(A)}.
  5. Silogismo hipotético: {(A\rightarrow B) \land (B\rightarrow C) \Rightarrow A\rightarrow C}.
  6. Silogismo disjuntivo: {(A\lor B) \land \neg(A) \Rightarrow B}.
  7. Demonstração por absurdo: {A \rightarrow \mathbf{F} \Rightarrow \neg(A)}.

Prova: Exercício. \Box

No exercício 3

\displaystyle \begin{array}{rll} 1. & A \rightarrow C & \text{ premissa} \\ 2. & \neg C & \text{ premissa } \\ 3. & \neg (B)\rightarrow A & \text{ premissa } \\ 4. & \neg C \rightarrow \neg A & \text{ contrapositiva de 1} \\ 5. & \neg A & \text{ Modus ponens de 2 e 4} \\ 6. & \neg (A)\rightarrow \neg(\neg B) & \text{ contrapositiva de 3}\\ 7. & \neg(\neg B) & \text{ modus ponens de 5 e 6}\\ 8. & B & \text{ dupla nega\c c\~ao}\\ \end{array}

A partir da linha 4, cada linha é consequência lógica das linhas anteriores, portanto, {B} é consequência lógica das premissas.

1.5. Predicados

Definição 9 Uma sentença aberta é uma sentença parametrizada por uma ou mais variáveis. Uma sentença aberta não tem valor lógico.

Por exemplo, são predicados

  • {P(x)}: {x \leq x^{2}}.
  • {Q(x,y)}: {x \leq y^{2}}.

O nome “predicado” vem da analogia com a gramática usual, onde {x} “faz o papel de sujeito” da afirmação. O símbolo {x} recebe o nome de variável livre do predicado {P}.

Pra nós, ituitivamente, cada variável está associada a um domínio não-vazio de onde empresta valores e sempre que substituirmos as variáveis de uma sentença aberta por valores do seu domínio, obtemos uma sentença fechada, que não depende de nenhuma variável e que portanto pode ser tratada como uma sentença atômica do cálculo proposicional.

Por exemplo, {R(x,y): x > y } é uma sentença verdadeira se os valores de {x} e {y} forem {7} e {4} (i.e., {R(4,7)} é verdadeiro), mas é falsa se os valores forem {1} e {2} (i.e., {R(1,2)} é falso).

Usaremos letras minúsculas {x, y, z,\dots} para denotar variáveis, letras maiúsculas {P, Q, R, \dots} para os predicados as quais são seguidas por uma lista de variáveis entre parênteses para denotar que a sentença aberta depende dessas variáveis. Como em Funções, dado um predicado {P(x_1 , x_2 ,\dots, x_n )}, usamos a notação {P(v_1 , v_2 , \dots, v_n )} para indicar a substituição da variável {x_i} valor {v_i}, para {i=1,2,\dots,n}. Supõe-se que todas as ocorrências da mesma variável na sentença são substituídas pelo mesmo valor.

Podemos combinar predicados, da mesma maneira que nós fizemos com as sentenças, usando os operadores lógicos {\neg,\land,\lor,\rightarrow,\leftrightarrow} para formar predicados mais complexos.

A substituição de variáveis por valores do domínio não é a única maneira de transformar uma sentença aberta em uma sentença atômica. Outra maneira é a chamada quantificação. A quantificação permite expressar conceitos como “Todos os elementos de D” ou “alguns elementos de D”. O primeiro é chamado quantificação universal e segundo de quantificação existencial.

1.6. Quantificadores

Definição 10 A quantificação universal de {P(x)} é a sentença

\displaystyle \mathrm{para~todo~} x,~P(x) \quad \text{tamb\'em denotada por} \quad \forall x,~P(x)

que é verdadeira se {P(x)} é verdadeiro para toda instanciação de {x} com valores de um domínio {D\neq\emptyset}. Caso {P(x)} seja falsa para um ou mais valores atribuídos a {x} então a sentença { \mathrm{para~todo~} x,~P(x)} é falsa.

Por exemplo,

\displaystyle \mathrm{para~todo~} x\in {\mathbb Z},~x < x+1

é verdadeira enquanto que

\displaystyle \mathrm{para~todo~} x\in {\mathbb N},~x \text{ \'e primo}

é falsa pois {4\in {\mathbb N}} e {4} não é primo. Dizemos que {4} é um contraexemplo para {\forall x\in {\mathbb N},~x \text{ \'e primo}}.

As vezes quantificadores estão implícitos, por exemplo, no domínio do reais a afirmação

se um número é inteiro, então é racional

é uma sentença implicitamente quantificada

\displaystyle \forall x\in {\mathbb R},~(x\in {\mathbb Z}\rightarrow x\in {\mathbb Q})

assim como {\sin^2(x) + \cos^2(x)=1} expressa

\displaystyle \forall x\in {\mathbb R}, \sin^2(x) + \cos^2(x)=1.

Se o domínio {D} de x é um conjunto finito, digamos {D=\{v_1 , v_2 , \dots , v_ n\}}, então {\forall x,~P(x)} equivale logicamente a { P(v_1 ) \land P(v_2 ) \land \cdots \land P(v_n )}, i.e.,

\displaystyle (\forall x\in \{v_1 , v_2 , \dots , v_ n\},~P(x)) \Leftrightarrow (P(v_1 ) \land P(v_2 ) \land \cdots \land P(v_n )).

Definição 11 A quantificação existencial da sentença aberta {P(x)} é a sentença

\displaystyle \mathrm{existe~} x,~P(x) \quad \text{tamb\'em denotada por} \quad \exists x,~P(x)

que é verdadeira se {P(x)} é verdadeiro para pelo menos uma instanciação de {x} com valores de um domínio {D\neq\emptyset}. Caso {P(x)} seja falsa para todos os valores de um domínio {D} atribuídos a {x} então a sentença { \mathrm{existe~} x,~P(x)} é falsa.

Por exemplo,

\displaystyle \mathrm{existe~} x\in {\mathbb Z},~x = x+1

é falsa enquanto que

\displaystyle \mathrm{existe~} x\in {\mathbb N},~x \text{ \'e primo}

é verdadeira.

Se o domínio {D} de x é um conjunto finito, digamos {D=\{v_1 , v_2 , \dots , v_ n\}}, então {\exists x\in D,~P(x)} equivale logicamente a { P(v_1 ) \lor P(v_2 ) \lor \cdots \lor P(v_n )}, i.e.,

\displaystyle (\exists x\in \{v_1 , v_2 , \dots , v_ n\},~P(x)) \Leftrightarrow (P(v_1 ) \lor P(v_2 ) \lor \cdots \lor P(v_n )).

sentença verdadeira falsa
{\forall~x,~P(x)} {P(a)} é verdadeiro para todo {a} no domínio existe pelo menos um {a} no domínio para o qual {P(a)} é falso
{\exists~ x,~P(x)} existe pelo menos um {a} no domínio para o qual {P(a)} é verdadeiro {P(a)} é falso para todo {a} no domínio

Defina os predicados {P(x) : x\geq 0}, {Q(x):x^2 \geq 0} e {R(x) : x^2>3}.

  1. {\mathrm{para~todo~} x\in{\mathbb R},} se {x\geq 0} então {x^2\geq 0}, ou

    \displaystyle \forall x\in{\mathbb R} (P(x)\rightarrow Q(x))

    é verdadeiro.

  2. {\mathrm{existe~} x\in{\mathbb R},} se {x\geq 0} então {x^2\geq 0}, ou

    \displaystyle \exists x\in{\mathbb R} (P(x)\rightarrow Q(x))

    é verdadeiro.

Agora

\displaystyle \forall x\in{\mathbb R} (P(x)\rightarrow R(x))

é falso e para mostrar isso basta exibirmos um contraexemplo, um valor {a} do domínio ({a\in{\mathbb R}}) para o qual {P(a)\rightarrow R(a)} é falso, como o {0}.

Definição 12 As sentenças abertas {P(x)} e {Q(x)} são logicamente equivalentes se {P(a)\leftrightarrow Q(a)} é tautologia para todo {a\in D}, e escrevemos {\forall x (P(x)\Leftrightarrow Q(x))}.

Se {P(a)\rightarrow Q(a)} é tautologia para todo {a\in D} então {P(x)} implica logicamente {Q(x)} e escrevemos {\forall x (P(x)\Rightarrow Q(x))}.

1.7. Distribuição de quantificadores

Sejam {P(x)} e {Q(x)} sentenças abertas

  1. {\forall x (P(x) \land Q(x)) \Leftrightarrow (\forall x , P(x)) \land (\forall x, Q(x)).}
  2. {\forall x (P(x) \lor Q(x)) \Leftarrow (\forall x , P(x)) \lor (\forall x, Q(x)).}
  3. {\exists x, (P(x) \lor Q(x)) \Leftrightarrow (\exists x , P(x)) \lor (\exists x, Q(x)).}
  4. {\exists x, (P(x) \land Q(x)) \Rightarrow (\exists x , P(x)) \land (\exists x, Q(x)).}

1.8. Negação de quantificadores

{ \neg \Big( \forall x,~P(x)\Big) \Leftrightarrow \exists x, \neg(P(x)) }.

{ \neg\Big( \exists x,~P(x)\Big) \Leftrightarrow \forall x, \neg(P(x))}.

1.9. Múltiplos quantificadores

Se uma sentença aberta menciona mais de uma variável, é preciso um quantificador para cada variável distinta para transformá-la numa sentença fechada.

Por exemplo, no domínio dos inteiros há oito maneiras de transformar a sentença aberta {x + y = y+x} em uma sentença fechada:

{\forall x\in {\mathbb Z},~\forall y \in {\mathbb Z} (x + y = y+x)}

{\forall x\in {\mathbb Z},~\exists y \in {\mathbb Z} (x + y = y+x)}

{\exists x\in {\mathbb Z},~\forall y \in {\mathbb Z} (x + y = y+x)}

{\exists x\in {\mathbb Z},~\exists y \in {\mathbb Z} (x + y = y+x)}

{\forall y\in {\mathbb Z},~\forall x \in {\mathbb Z} (x + y = y+x)}

{\exists y\in {\mathbb Z},~\forall x \in {\mathbb Z} (x + y = y+x)}

{\forall y\in {\mathbb Z},~\exists x \in {\mathbb Z} (x + y = y+x)}

{\exists y\in {\mathbb Z},~\exists x \in {\mathbb Z} (x + y = y+x)}

Em sentenças com mais de uma variável a ordem em que os quantificadores aparece é importante. Por exemplo, se {x} e {y} são inteiros

\displaystyle \mathrm{para~todo~} x\in {\mathbb Z},~\mathrm{existe~} y\in {\mathbb Z},~(x+y=0) \ \ \ \ \ (19)

não é logicamente equivalente a

\displaystyle \mathrm{existe~} y\in {\mathbb Z},~\mathrm{para~todo~}~x\in {\mathbb Z},~(x+y=0) \ \ \ \ \ (20)

pois (19) é verdadeiro enquanto que (20) é falso. Entretanto, em alguns casos vale a equivalência. Por exemplo, se {x} e {y} são números naturais

\displaystyle \mathrm{para~todo~} x\in {\mathbb N},~\mathrm{existe~} y\in {\mathbb N} \text{ tal que } x~\mathrm{divide}~y \ \ \ \ \ (21)

é verdadeira, assim como

\displaystyle \mathrm{existe~} y\in {\mathbb N},~\mathrm{para~todo~} x\in {\mathbb N}\text{ tal que } x~\mathrm{divide}~y \ \ \ \ \ (22)

pois todo {x\in{\mathbb N}} divide o {0}.

Sempre podemos trocar a ordem de dois quantificadores do mesmo tipo

\displaystyle \begin{array}{rcl} \forall x,~\forall y, ~ P(x, y) &\Leftrightarrow& \forall y,~\forall x ,~ P(x, y) \\ \exists x ,~\exists y , ~ P(x, y) &\Leftrightarrow& \exists y,~\exists x ,~ P(x, y) \end{array}

Ao escrever (e ler) demonstrações de teoremas nós devemos estar sempre
atentos à estrutura lógica e ao significados das sentenças. Às vezes é
necessário (ou ao menos útil) escrevê-las em expressões que envolvem
símbolos lógicos. Isso pode ser feito mentalmente ou em papel de
rascunho, ou ocasionalmente, mesmo explicitamente dentro do corpo de
uma prova.

Entretanto, deve-se ter em mente que simbolizar uma sentença não a
torna mais formal ou mais correta, apena ajuda na compreensão da sua
estrutura lógica.


1.10. Regras de Inferência e Argumentos válidos

As provas em matemática são argumentos válidos que estabelecem a verdade de sentenças.

Um argumento é uma seqüência {P_1, P_2, \dots , P_n} de sentenças, ditas premissas , que terminam com uma conclusão {Q} (o que indicamos pelo símbolo \therefore, que lê-se
portanto)

{P_1}
{P_2}
{\vdots}
{P_n}
{\therefore Q}

O argumento é válido se, e só se, {(P_1\land P_2\land\cdots\land P_n) \Rightarrow Q.}

Regras de inferência são esquemas de argumentos válidos
simples que usamos para para construir argumentos válidos mais
complexos. Por exemplo,

Se você tem uma senha, então você pode fazer logon no facebook
Você tem uma senha
Portanto, você pode fazer logon no facebook

é um argumento válido porque se encaixa no modelo

{P\rightarrow Q}
{P}
{\therefore Q}

que é um argumento válido pelo teorema 2, essa regra de inferência é chamada Modus Ponens.

Notemos que cada caso do teorema 2 nos dá uma regra de inferência:

  1. Regra da Adição. Se {P} é uma premissa, podemos derivar {P\lor Q}
    {P}
    {\therefore P\lor Q}

    Por exemplo, “Ele estuda muito”, portanto “Ou ele estuda muito ou é um estudante muito ruim”.

  2. Regra da Simplificação. Se {P\land Q} é uma premissa, podemos derivar {P}
    {P\land Q}
    {\therefore P}

    Por exemplo, “Ele estuda muito” e “Ele é o melhor aluno da classe”, portanto “Ele é o melhor aluno da classe”.

  3. Modus Ponens.
    {P\rightarrow Q}
    {P}
    {\therefore Q}
  4. Modus Tollens. Se {P\rightarrow Q} e {\neg Q} são duas premissas, podemos usar o Modus Tollens para derivar {\neg P}
    {P\rightarrow Q}
    {\neg Q}
    {\therefore \neg P}

    Por exemplo

    Se você tem uma senha, então você pode fazer logon no facebook
    Você não pode fazer logon no facebook
    Portanto, você não tem uma senha
  5. Regra do silogismo hipotético. Se {P\rightarrow Q} e {Q\rightarrow R} são duas premissas, podemos usar o silogismo hipotético para derivar {P\rightarrow R}
    {P\rightarrow Q}
    {Q\rightarrow R}
    {\therefore P\rightarrow R}

    Por exemplo, “Se chover, eu não vou para a escola” e “Se eu não for para a escola, não terei que fazer a lição de casa”, portanto, “Se chover, eu não precisarei fazer lição de casa”.

  6. Regra do silogismo disjuntivo. Se {\neg P} e {P\lor Q} são duas premissas, podemos usar o silogismo disjuntivo para derivar {Q}
    {P\lor Q}
    {\neg P}
    {\therefore Q}

    Por exemplo, “O sorvete não é de baunilha” e “O sorvete é ou sabor baunilha ou sabor chocolate”, portanto, “O sorvete é de chocolate”.

  7. Regra da contradição. Se {\neg P \rightarrow \mathbf{F}} então deduzimos {P}
    {\neg P\rightarrow \mathbf{F}}
    {\therefore P}

O seguinte é um argumento válido?

{\neg (P)\rightarrow Q}
{Q\rightarrow S}
{P\rightarrow R}
{\therefore \neg R\rightarrow S}

Resposta

Atenção

se {\sqrt{2} > 3/2} então {2 > 9/4}
{\sqrt{2} > 3/2}
{\therefore 2 > 9/4}

é um argumento válido!!!!!! Mas não é um argumento correto pois a premissas não são verdadeiras.

Regras de inferência para quantificadores

  1. Instanciação universal. Se {\mathrm{para~todo~} x,~P(x)} então {P(c)} sempre que {c} é um elemento do domínio
    {\forall x,P(x)}
    {\therefore P(c)}

  2. Generalização universal. Se {P(c)} para um elemento {c} arbitrário do domingo então {\mathrm{para~todo~} x,~P(x)}
    {P(c)} para {c} arbitrário
    {\therefore \forall x,P(x)}

  3. Instanciação existencial. Se {\mathrm{existe~} x,~P(x)} então {P(c)} para algum elemento {c} do domínio
    {\exists x,P(x)}
    {\therefore P(c)}

  4. Generalização existencial. Se {P(c)} para algum {c} específico, então {\mathrm{existe~} x,~P(x)}
    {P(c)} para algum {c} específico
    {\therefore \exists x,~P(x)}

    .

Atenção, consideremos a sentença aberta {n^2=n} o argumento

{0^2=0}
{\therefore \forall n\in{\mathbb N},~n^2 = n}

usando a generalização universal para {c=0}!!! não é válido porque 0 não é elemento genérico do domínio.

Por exemplo, o seguinte argumento é válido

{\forall x(P(x)\rightarrow Q(x))}
{\forall x(Q(x)\rightarrow R(x))}
{\therefore \forall x(P(x)\rightarrow R(x))}

Vejamos

passo sentença justificativa
1. {\forall x(P(x)\rightarrow Q(x))} premissa
2. {\forall x(Q(x)\rightarrow R(x))} premissa
3. {P(c)\rightarrow Q(c)} instanciação universal de 1
4. {Q(c) \rightarrow R(c)} instanciação universal de 2
5. {P(c) \rightarrow R(c)} Silogismo hipotético de 3 e 4
6. {\forall x(P(x)\rightarrow R(x))} generalização universal.


A regra da conjunção:

{P}
{Q}
{\therefore P\land Q}

pode ser usada para mostrar que {\exists x, (P(x) \land Q(x)) \Rightarrow (\exists x , P(x)) \land (\exists x, Q(x)).} Vejamos

passo sentença justificativa
1. {\exists x, (P(x) \land Q(x))} premissa
2. {P(c)\land Q(c)} instanciação existencial de 1
3. {P(c)} simplificação de 2
4. {Q(c)} simplificação de 2
5. {\exists x, P(x)} generalização existencial de 3
6. {\exists x, Q(x)} generalização existencial de 4
7. {(\exists x, P(x)) \land (\exists x, Q(x))} conjunção.

No próximo exercício suponha que há um domínio associado sem se preocupar com o que de fato é tal conjunto (pode ser o conjunto de todos os animais conhecidos, por exemplo)

Exercício 4 (Lewis Carrol) Verfique se o seguinte argumento é válido:

Todos os leões são selvagens.
Alguns leões não bebem café
Portanto, alguma criatura selvagem não bebe café.

(Solução )

Exercício 5 (Modus Ponens Universal) Verfique se o seguinte argumento que combina instanciação universal com Modus Ponens é válido:

{\forall x(P(x)\rightarrow Q(x))}
{P(a)}
{\therefore Q(a)}

Exercício 6 Verifique a validade das seguintes regras de inferência:

  1. Resolução
    {P\lor Q}
    {\neg (P) \lor R}
    {\therefore Q\lor R}

  2. Prova por casos
    {P\rightarrow Q}
    {R\rightarrow Q}
    {P \lor R}
    {\therefore Q}

  3. Regra da conjunção
    {P}
    {Q}
    {\therefore P\land Q}

Exercícios

2 respostas em “[MCTB019-17] §1 — Demonstrações: Linguagem”

  1. Definição 11 A quantificação existencial da sentença aberta {P(x)} é a sentença

    \displaystyle \mathrm{existe~} x,~P(x) \quad \text{tamb\’em denotada por} \quad \exists x,~P(x)

    que é verdadeira se {P(x)} é verdadeiro para pelo menos uma instanciação de {x} com valores de um domínio {D\neq\emptyset}. Caso {P(x)} seja falsa para todos os valores de um domínio {D} atribuídos a {x} então a sentença { \mathrm{para~todo~} x,~P(x)} é falsa.

    para algum x, P(x) é falsa

    há um pequeno erro

    Comentar ↓

Deixe um comentário