Lista 02 - FTC

Prévia do material em texto

Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
Fundamentos de Teoria da Computação
Prof. Rodrigo Yoshikawa Oeiras
Lista de Exercícios 02: Lógica de Proposições
1. Para os itens abaixo, identifique a regra de inferência que representa os argumentos.
a) Se a firma falir, todos os seus ativos têm que ser confiscados. A firma faliu. Segue 
que todos os seus bens têm que ser confiscados.
b) O cachorro tem um pelo sedoso e adora latir. Portanto, o cachorro adora latir.
c) (Olhar a tabela da questão 5) Se Paulo é um bom nadador, então ele é um bom 
corredor. Se Paulo é um bom corredor, então ele é um bom ciclista. Portanto, se 
Paulo é um bom nadador, então ele é um bom ciclista.
2. Identifique cada passo na demonstração (hipóteses, uso de tabelas de equivalência e 
de inferência, etc).
a) A (B→C)→(B→(A C))˄ ˄
1. A
2. (B → C)
3. B
4. C
5. A C˄
b) [A → (B C)] B' C' → A'˅ ˄ ˄
1. A → (B C)˅
2. B'
3. C'
4. B' C'˄
5. (B C)'˅
6. A'
c) A' B [B → (A C)] → C˄ ˄ ˅
1. A'
2. B
3. B → (A C)˅
4. A C˅
5. (A')' C˅
6. A' → C
7. C
3. A seguir, use a lógica proposicional para provar se o argumento é válido.
a) A' (B → A) → B'˄
b) (A → B) [A → (B → C)] → (A → C)˄
c) [(C → D) → C] → [(C → D) → D]
d) A' (A B) → B˄ ˅
e) [A → (B → C)] (A D') B → (D → C)˄ ˅ ˄
f) (A' → B') B (A → C) → C˄ ˄
g) (A → B) [B → (C → D)] [A → (B → C)] → (A → D)˄ ˄
h) [A → (B → C)] → [B → (A → C)]
i) (A B) → (A → B')'˄
Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
4. Use as tabelas de lógica proposicional das aulas para provar os argumentos válidos 
abaixo.
a) A' A → B˄
b) (A' → B') (A → C) → (B → C)˄
c) (A' → B) (B → C) → (C → D) → (A' → D)˄
5. Prove as regras de inferência da tabela abaixo:
Tabelas Básicas
Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
Respostas
1. a) (B → A) ^ B → A [mp] b) A ^ B → B [simp] c) ( A → B ) ^ ( B → C ) → ( A → C) [sh]
2. a) 1-“Hip”, 2-“hip¨, 3-“hip”(método dedutivo), 4-“2,3,mp”, 5-“1,4,con”. b) 
1-“hip”, 2-“hip”, 3-“hip”, 4-“2,3,conj”, 5-“4, DeMorgan”, 6-“1,5,mt”. c) 
1-“hip”, 2-“hip”, 3-“hip”, 4-“2,3,mp”, 5-“4,dn”, 6-“5,cond”, 7-“1,6,mp”.
3. a) 1:A' “hip”, 2:(B → A) “hip”, 3:B' “1,2,mt”. 
b) 1:A → B “hip”, 2:A → (B → C) “hip”, 3:A “hip”, 4:B “1,3,mp”, 5:B → C “2,3,mp”, 6:C 
“ 4,5,mp”. 
c) 1:(C → D) → C “hip”, 2:C → D “hip”, 3:C “1,2,mp”, 4:D “2,3,mp”. 
d) 1:A' “hip”, 2:A B “hip”, 3:(A')' B “2,dn”, 4:A' → B “3,cond”, 5:B “1,4,mp”. ˅ ˅
e) 1:A → (B → C) “hip”, 2:A D' “hip”, 3:B “hip”, 4:D “hip”, 5:D' A “2,com”, 6:D → A ˅ ˅
“5,cond”, 7:A “4,6,mp”, 8: B → C “1,7,mp”, 9: C “3,8,mp”. 
f) 1:A' → B' “hip”, 2:B “hip”, 3:A → C “hip”, 4:(B')' “2,dn”, 5:(A')' “1,4,mt”, 6: A “5,dn”, 7:C 
“3,6,mp”.
g) 1:A → B “hip”, 2:B → (C → D) “hip”, 3:A → (B → C) “hip”, 4:A “hip”, 5:B “1,4,mp”, 6: 
B → C “3,4,mp”, 7:C “5,6,mp”, 8: C → D “2,5,mp”, 9:D “7,8,mp”
h) 1:A → (B → C) “hip”, 2:B “hip(dedução)”, 3:A “hip(dedução)”, 4. B → C “1,3,mp”, 
5:C “2,4,mp”.
i) 1: A B “hip”, 2:(A')' (B')' “1,dn”, 3:(A' B')' “2,DeMorgan”, 4:(A → B')' “3,conj”.˄ ˄ ˄
4. a) 1: A' “hip”, 2: A “hip”, 3:B “1,2,inc”. 
b) 1: A' → B' “hip”, 2: A → C “hip”, 3:B “hip,dedução”, 4: B → A “1,cont”, 5:C “4,2,sh”
c) 1: A' → B “hip”, 2: B → C “hip”, 3: C → D “hip”, 4:A' → C “1,2,sh”, 5:A' → D “4,3,sh”