All of the following are valid formulas in classical first-order logic assuming that, in particular, x does not occur free in R.
| A | B | |
|---|---|---|
| ∀x(P(x) ∧ Q(x)) | ≡ | (∀xP(x) ∧ ∀xQ(x)) |
| ∃x(P(x) ∧ Q(x)) | → | (∃xP(x) ∧ ∃xQ(x)) |
| ∀x(P(x) ∨ Q(x)) | ← | (∀xP(x) ∨ ∀xQ(x)) |
| ∃x(P(x) ∨ Q(x)) | ≡ | (∃xP(x) ∨ ∃xQ(x)) |
| ∀x(P(x) → Q(x)) | ← | (∃xP(x) → ∀xQ(x)) |
| ∃x(P(x) → Q(x)) | ≡ | (∀xP(x) → ∃xQ(x)) |
| ∀x¬P(x) | ≡ | ¬∃xP(x) |
| ∃x¬P(x) | ≡ | ¬∀xP(x) |
| ∀x∃yT(x,y) | ← | ∃y∀xT(x,y) |
| ∀x∀yT(x,y) | ≡ | ∀y∀xT(x,y) |
| ∃x∃yT(x,y) | ≡ | ∃y∃xT(x,y) |
| ∀x(P(x) ∨ R) | ≡ | (∀xP(x) ∨ R) |
| ∃x(P(x) ∧ R) | ≡ | (∃xP(x) ∧ R) |
| ∀x(P(x) → R) | ≡ | (∃xP(x) → R) |
| ∃x(P(x) → R) | → | (∀xP(x) → R) |
| ∀x(R → Q(x)) | ≡ | (R → ∀xQ(x)) |
| ∃x(R → Q(x)) | → | (R → ∃xQ(x)) |
| ∀xR | ← | R |
| ∃xR | → | R |
The following formulas are not valid.
| A | B | counterexample | |
|---|---|---|---|
| ∃x(P(x) ∧ Q(x)) | ← | (∃xP(x) ∧ ∃xQ(x)) | D = {a, b}, M = {P(a), Q(b)} |
| ∀x(P(x) ∨ Q(x)) | → | (∀xP(x) ∨ ∀xQ(x)) | D = {a, b}, M = {P(a), Q(b)} |
| ∀x(P(x) → Q(x)) | → | (∃xP(x) → ∀xQ(x)) | D = {a, b}, M = {P(a), Q(a)} |
| ∀x∃yT(x,y) | → | ∃y∀xT(x,y) | D = {a, b}, M = {T(a,b), T(b,a)} |
| ∃x(P(x) → R) | ← | (∀xP(x) → R) | D = Ø, M = {R} |
| ∃x(R → Q(x)) | ← | (R → ∃xQ(x)) | D = Ø, M = Ø |
| ∀xR | → | R | D = Ø, M = Ø |
| ∃xR | ← | R | D = Ø, M = {R} |
Note: if empty domains are not allowed, then the last four implications are in fact valid.
