Prove the following by deductive system(Using First-order Logic): If x does not occur in ψ, then ∃x : S • (φ(x) ⇒ ψ) ⊨ (∀x : S • φ(x)) ⇒ ψ.
时间: 2024-05-30 12:13:01 浏览: 25
1. Assume that x does not occur in ψ.
2. Let a be an arbitrary element of S such that φ(a) ⇒ ψ.
3. Assume ∀x : S • φ(x).
4. By Universal Instantiation, φ(a).
5. Using Modus Ponens with (2) and (4), we can conclude that ψ.
6. Therefore, (∀x : S • φ(x)) ⇒ ψ, as desired.
相关问题
Prove the following by deductive system: ⊨ φ ∨ ¬φ (i.e., ∅ ⊨ φ ∨ ¬φ)
Proof:
1. Assume ¬(φ ∨ ¬φ) for the sake of contradiction.
2. By De Morgan's Law, ¬(φ ∨ ¬φ) is equivalent to ¬φ ∧ ¬¬φ.
3. By Double Negation, ¬¬φ is equivalent to φ.
4. Therefore, ¬φ ∧ φ.
5. By the principle of Non-Contradiction, a statement and its negation cannot both be true.
6. Therefore, ¬(φ ∨ ¬φ) leads to a contradiction.
7. By the principle of Explosion, a contradiction implies anything.
8. Therefore, φ ∨ ¬φ must be true, as assuming its negation leads to a contradiction.
9. Therefore, ⊨ φ ∨ ¬φ, as it is true under all interpretations.
Note: This proof uses the principle of Non-Contradiction and the principle of Explosion, which are two fundamental principles of classical logic.
Prove the following by deductive system:1 ⊨ φ ∨ ¬φ (i.e., ∅ ⊨ φ ∨ ¬φ)
To prove 1 ⊨ φ ∨ ¬φ using a deductive system, we need to show that if we assume 1 as true, then we can derive φ ∨ ¬φ as a logical consequence.
We can start with the premise 1, which means that the proposition "true" is true. From this, we can use the rule of addition to derive φ ∨ true, which is logically equivalent to true.
Next, we can use the rule of negation to derive ¬φ ∨ true, which is also logically equivalent to true.
Finally, we can use the rule of disjunction elimination to derive φ ∨ ¬φ from the two previous conclusions. This rule states that if we have a disjunction A ∨ B and we can derive a conclusion C from both A and B separately, then we can conclude C from the disjunction A ∨ B.
In this case, we have the disjunction φ ∨ true and ¬φ ∨ true, and we have derived true from both of them separately. Therefore, we can apply the rule of disjunction elimination to derive φ ∨ ¬φ, which is our desired conclusion.
Therefore, we have shown that if 1 is true, then φ ∨ ¬φ must also be true, which means that 1 ⊨ φ ∨ ¬φ.