Soluções de alguns exercícios

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

$\displaystyle \begin{array}{rcl} &(A\lor B) \land \neg(\neg(A)\land B) & \textit{ motivo}\\ \Leftrightarrow &(A\lor B)\land (\neg\neg(A)\lor\neg(B)) & \text{ De Morgan }\\ \Leftrightarrow &(A\lor B)\land (A\lor\neg(B)) & \text{ dupla nega\c c\~ao }\\ \Leftrightarrow &(A\lor (B \land \neg(B)) & \text{ distributiva }\\ \Leftrightarrow &(A\lor \mathbf{F}) & \text{ inversa }\\ \Leftrightarrow & A & \text{ identidade } \end{array}$

$\Box$

O seguinte é um argumento válido?

${\neg (P)\rightarrow Q}$

${Q\rightarrow S}$

${P\rightarrow R}$

${\therefore \neg R\rightarrow S}$

Sim, vejamos

passo	proposição	justificativa
1.	${\neg P\rightarrow Q}$	premissa
2.	${Q\rightarrow S}$	premissa
3.	${P\rightarrow R}$	premissa
4.	${\neg R\rightarrow \neg P}$	contrapositiva de 3
5.	${\neg R\rightarrow Q}$	Silogismo hipotético de 4 e 1
5.	${\neg R\rightarrow S}$	Silogismo hipotético de 5 e 2

$\Box$

Exercício (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: Consideremos Matata um elemento do domínio.

passo	proposição	justificativa
1.	${\forall x, (L(x) \rightarrow S(x))}$	premissa
2.	${\exists x, (L(x) \land \neg C(x))}$	premissa
3.	${L(Matata) \land \neg C(Matata))}$	instanciação universal de 2
4.	${L(Matata) }$	simplificação de 3
5.	${\neg C(Matata)}$	simplificação de 3
6.	${(L(Matata) \rightarrow S(Matata))}$	instanciação universal de 1
7.	${S(Matata)}$	Modus Ponens de 4 e 6
8.	${S(Matata)\land \neg C(Matata)}$	conjunção de 5 e 7
8.	${\exists x(S(x)\land \neg C(x))}$	generalização existencial

$\Box$

Escreva uma demonstração para: para todo ${x\in {\mathbb N}^*}$ (os naturais menos o zero), para todo ${y\in{\mathbb N}}$ , se ${x}$ divide ${y}$ então ${x^2}$ divide ${y^2}$ .

Demosntração detalhada:

Sejam ${n,m\in{\mathbb N}}$ .

1)	${n\neq 0}$ .	(premissa)
2)	${n\|m }$ .	(premissa)
3)	Se ${n\|m}$ então ${m=nk}$ para algum inteiro ${k}$	(da definição de divide)
4)	${m=nk}$	(2, 3 e MP e instanciação existencial)
5)	Se ${m=nk}$ então ${m^2= n^2 k^2}$	(propriedade aritmética e da igualdade)
6)	${m^2= n^2 k^2}$	(4, 5 e MP)
7)	Se ${m^2= n^2 k^2}$ então existe um inteiro ${c}$ tal que ${m^2= n^2 c}$	(generalização existencial)
8)	existe um inteiro ${c}$ tal que ${m^2= n^2 c}$	(5, 6 e MP)
9)	se existe um inteiro ${c}$ tal que ${m^2= n^2 c}$ então ${n^2 \| m^2}$	(definição de divide)
10)	${n^2 \| m^2}$	(8, 9 e Modus Ponens)

Usando a regra de generalização universal concluímos que para todo ${x\in {\mathbb N}^*}$ (os naturais menos o zero), para todo ${y\in{\mathbb N}}$ , se ${x}$ divide ${y}$ então ${x^2}$ divide ${y^2}$ . $\Box$

Demonstração: Sejam ${n}$ e ${m}$ números naturais, ${n\neq 0}$ . Suponha que ${n|m}$ e que ${n\neq 0}$ .

Se ${n|m}$ e ${n\neq 0}$ então ${nq=m}$ para algum ${q}$ .

Se ${nq=m}$ então ${n^2 q^2 = m^2}$ .

Portanto, ${n^2|m^2.}$

Note que a hipótese $n\neq 0$ é desnecessária. Devemos cuidar para não enunciar sentenças com hipóteses desnecessárias.

Exercício Prove que para qualquer natural ${n>1}$ , existe uma sequência formada por ${n}$ números naturais consecutivos tal que nenhum deles é primo.

Solução: Seja ${n}$ um natural maior que 1 qualquer. A sequência ${(n+1)!+2, (n+1)!+3,\dots,(n+1)!+(n+1)}$ é formada por ${n}$ números naturais consecutivos. Ainda, ${(n+1)!+j}$ é divisível por ${j}$ sempre que ${j\in\{2,3,\dots,n+1\}}$ . $\Box$

O problema com o passo:

Seja ${t\in\mathbb N}$ , suponha que ${\forall a,~\forall b, (\text{max}\{a,b\}=t-1 \rightarrow a=b)}$ e vamos provar que ${\forall a,\forall b,(\text{max}\{a,b\}=t\rightarrow a=b)}$ .

é que $P(0) \not\rightarrow P(1)$ quando $a$ ou $b$ vale $0$ .

Exercício
Para todo inteiro $n \geq 5$ , existem naturais $a$ e $b$ tais que $n= 2a + 5b$ .

Solução:
Vamos provar por contradição. Suponha que a afirmação seja falsa e
seja $A$ o conjunto de todos os naturais maiores ou iguais a 5 que
não podem ser escritos na forma $2a + 5b$ . Como $A\neq \emptyset$
podemos tomar $m$ o menor elemento de $A$ . De $m\in A$ temos $m \geq 5$ , portanto $m-1 \geq 4$ . Da minimalidade de $m$ temos que $m-1 =2a+5b$ .

Se $a \leq 1$ e $b \leq 0$ então $m-1 = 2a+5b \leq 2 + 0 = 2$ ,
portanto, $a > 1$ ou $b > 0$ .

Se $a > 1$ então $m = 2a + 5b +1 = 2(a-2) + 5(b+1)$ .
Se $b > 0$ então $m = 2a + 5b +1 = 2(a+3) + 5(b-1)$ .

Em ambos os casos, temos uma contradição.

Exercício Quantas soluções inteiras tem ${x_1+x_2+x_3=11}$ com ${x_1\in\{1,2,3\}}$ e ${x_2,x_3\in\{4,5\}}$ ?

Solução: O coeficiente de ${x^{11}}$ em ${(x^1+x^2+x^3)(x^4+x^5)(x^4+x^5)}$ . $\Box$

Exercício De quantos modos podemos comprar ${n}$ frutas de modo que ${(1)}$ o número de maçãs é par, ${(2)}$ o número de bananas é múltiplo de 5, ${(3)}$ no máximo 4 laranjas, e ${(4)}$ no máximo uma pêra.

Solução:

$\displaystyle f(x) = \frac 1{1-x^2} \cdot \frac 1{1-x^5} \cdot \frac{1-x^5}{1-x}\cdot (1+x)$

${[x^n]f(x) = n+1}$ . $\Box$

Exercício Escreva uma demonstração para: se ${P\rightarrow (Q\rightarrow R)}$ então ${\neg R\ \rightarrow (P \rightarrow \neg Q)}$ .

Solução:

Assumamos ${P \rightarrow (Q\rightarrow R)}$ e provemos ${\neg R \rightarrow (P \rightarrow \neg Q)}$ .

Para provar ${\neg R \rightarrow (P \rightarrow \neg Q)}$ , assumamos ${\neg R}$ e provemos ${P \rightarrow \neg Q}$ .

Para provar ${P \rightarrow \neg Q }$ , assumamos ${P}$ e provemos ${\neg Q}$ .

1)	${P \rightarrow (Q\rightarrow R)}$	(premissa)
2)	${\neg R}$	(premissa)
3)	${P}$	(premissa)
4)	${Q\rightarrow R}$	(1, 3 e Modus Ponens)
5)	${\neg Q}$	(2, 4 e Modus Tollens)

Portanto ${\neg R \rightarrow (P \rightarrow \neg Q)}$ . $\Box$

Se ${A}$ , ${B}$ e ${C}$ são três subconjuntos de ${X=\{1,2,\dots,n\}}$ . Vamos contar o número de ternas ${(A,B,C)}$ com ${A\cap B \subset C}$ .

Denotemos por $S$ o conjunto das partes de $X$ .
Primeiro, fixamos o conjunto ${C\in S}$ e o conjunto ${A\in S}$ . Digamos que ${C}$ tem cardinalidade ${c}$ e ${A\setminus C}$ tem cardinalidade ${a}$ , com ${0\leq c\leq n}$ e ${0\leq a \leq n-c}$ . O número de possíveis ${B\in S}$ tais que ${A\cap B \subset C}$ é contado da seguinte maneira: para que ${A\cap B}$ seja subconjunto de ${C}$ o conjunto ${B}$ não pode ter elementos de ${A\setminus C}$ , caso contrário teríamos ${x\in A\cap B}$ e ${x\not\in C}$ . Qualquer outro elemento de ${X}$ pode estar em ${B}$ logo temos ${2^{n-a}}$ possibilidades em ${S}$ para o conjunto ${B}$ .

Deixemos ${C}$ fixado e vamos contar quantos ${A\in S}$ são possíveis com ${a}$ elementos em ${A\setminus C }$ . Um conjunto ${A}$ com ${a}$ elementos em ${A\setminus C }$ é formado por elementos de um subconjunto de ${a}$ elementos escolhidos em ${n-c}$ , ou seja ${ \binom{n-c}a}$ possibilidades para ${A\setminus C}$ aos quais unimos um dos ${2^c}$ subconjuntos de ${C}$ para formar ${A}$ , pelo princípio multiplicativo são ${ 2^{n-a}\binom{n-c}a 2^c}$ possibilidades para formar ${A}$ . Assim o número de pares ${(A,B)}$ cuja interseção está contida em ${C}$ (fixo) é

$\displaystyle \sum_{a=0}^{n-c} 2^{n-a}\binom{n-c}a 2^{c} = 2^{c} 2^{c} \sum_{a=0}^{n-c} \binom{n-c}a2^{n-c-a} = 4^c (1+2)^{n-c} = 4^c 3^{n-c} \ \ \ \ \ (1)$

na segunda igualdade usamos o teorema binomial.

Da equação (1) acima, são ${4^c 3^{n-c}}$ pares ${(A,B)}$ cuja interseção está contida em qualquer ${C\in S}$ cuja cardinalidade é ${c}$ . A quantidade de tais ${C}$ é ${\binom nc}$ , portanto, o número de ternas ${(A,B,C)\in S\times S\times S}$ tais que ${A\cap B \subset C}$ é