IUMA Máster MTT, Métodos, 2015-2016 Examen 22 febrero 2016 Nombre:
1. Lógica deductiva formal de proposiciones. Comentarlas siguientes reglas de deducción natural ND 1, 2 y 3 con sus casos a, b, c, d: Given a set of premises D, and the goal you are trying to prove, G , there are some simple rules that will be helpful in finding ND proofs for problems. These rules are not complete, but will get you through many problem sets. Here it goes. Given D, prove G:
1. Apply premises (atomic propositions and formulas) piD, to prove G.
2. If you need to use a -premise, then apply -e and prove G for each disjunct (case).
3. Otherwise, work backwards from the type of goal you are proving:
(a) If the goal G is a conditional formula (A B), then assume A and prove B; use -i rule.
(b) If the goal G is a negative formula (A), then assume A and prove contradiction PC; use -irule.
(c) If the goal G is a conjunction (A B), then prove A and prove B; use -i rule.
(d) If the goal G is a disjunction (A B), then prove one of A or B; use -i rule.
2. Comentar: A formula A is said to be consistent if⊬¬A. Also: a formula is consistent if and only if it is satisfiable.
3. Comentar: A1, . . . ,An ⊨ B means that formula B is valid: it is true in all situations in which A1, . . . ,Anare true. It implies the use of semantics. However a theorem is a formula that can be established(‘proved’) by a given proof system. We write A is a theorem as ⊢A, A is a theorem.A proof system is sound (sólido) if every theorem is valid,and complete if every valid formula is a theorem. Natural deduction in formal logic is both sound and complete. When some premises are hypotheses or postulates (rather than axioms) then what is proved, deduced, is called a thesis. We then say ⊢ A, A is a thesis. Or if A is not a thesis ⊬A.
4. Lógica deductiva formal de predicados de primer orden. Siguiendo los ejemplos vistos en clase, decir en español:
a) ∀x∃y bought(x, y)
b) ∃y∀x bought(x, y)