Lista de Exercícios - Lógica Proposicional e Análise Combinatória

1 10 Via aplicação das regras de equivalências lógicas indiqueas ié sem construir tabelas verdade mostre que a p q p q r p q r b p q p q r p q 2 10 Defina o operador nand de not and por p q p q para proposições p q Represente as operações abaixo utilizando somente este novo operador a p b p q c p q d p q e p q Conclua que é uma base completa de operadores lógicos 3 10 Determine se cada uma das expressões abaixo são satisfatíveis a p q r p q s p q s p r s p q r p r s b p q r p q s q r s p r s p q s p q r p q s p r s 4 10 Temos um conjunto V n de compostos químicos que precisam ser acondicionados em k caixas com n k 1 inteiros No entanto certos pares não ordenados de compostos descritos por E V 2 não podem compartilhar uma mesma caixa sob o risco de reagirem e causarem explosões Para n e k fornecidos formule o problema acima como uma questão de satisfatibilidade de expressões proposicionais descrevendo em detalhes cada cláusula utilizada Sua descrição deve mostrar que cada solução à satisfatibilidade corresponde a uma solução de empacotamento e viceversa 5 5 Sejam B A dois conjuntos fixados com k n elementos respectivamente Determine C A C B 1 Isto é quantos subconjuntos de A possuem interseção unitária com B 6 5 Determine o número de pares ordenados A B em que A B n 7 5 Seja k 2n De quantas formas podemos distribuir k moedas idênticas a n pessoas se cada uma deve receber ao menos 2 moedas 8 5 De quantas formas podemos colocar 8 torres em um tabuleiro de xadrez 8 8 de forma que quaisquer duas delas não se ataquem 9 5 Sejam A B C três conjuntos e suponha que A C Prove que A B C A B C Forneça um exemplo que mostre que a condição A C não pode ser ignorada 10 20 Forneça provas combinatórias sem usar n m nmm para as relações abaixo a Para 0 k n n 2 k 2 kn k n k 2 c Para 0 ℓ k n n kk ℓ n ℓn ℓ k ℓ b n k nk n 1 k 1 d m k0 p kq m k p q m 11 5 Quantas permutações de n existem tais que nenhuma entrada é maior que ambos os seus vizinhos Nota considere que a condição é trivialmente satisfeita para as entradas mais à esquerda e mais à direita 12 5510 Para uma permutação π X X denote por πk a késima composição de π consigo mesma isto é π1 π e πk π πk 1 A ordem da permutação π é o menor k 1 tal que πk id a permutação identidade que mapeia cada elemento de X a si mesmo a Determine a ordem da permutação 2 3 1 5 4 7 8 9 6 Notação a1 a2 an com ai n distintos significa que πi ai para i n b Mostre que cada permutação π de um conjunto finito possui uma ordem finita bem definida c Mostre como computar a ordem a partir dos comprimentos dos ciclos de π 13 10 Seja 𝓕 2n com n 1 tal que A B para quaisquer A B 𝓕 distintos a Mostre que 𝓕 2n 1 b Construa uma coleção de exemplos em que para cada n fixado ocorre a igualdade em a