Symbolizing Quantities in First Order Logic (FOL)? Did I correctly symbolize the quantities listed?

86 Views Asked by At

Domain: D: {d1, d2, …, dk}: di: objects of the domain, Names: N: {c1, c2, …, ck}, ci: constants/names

Quantifying using the existential and universal quantifiers:

  • None (n = 0): ~∃x

  • Some (n ≥ 1): ∃x

  • Every (n = k): ∀x

  • Not every (n < k): ~∀x

  • where: n = # of items to be symbolized

  • where k: = # of items in the domain

Quantifying using ∃ and ∀: Quantities to symbolize in FOL: "at least 1", "at most 1", "exactly 1", "more than 1", "less than 1", "at least 2", "at most 2", "exactly 2", "more than 2", "less than 2".

  • At least one (n ≥ 1): ∃x
  • At most one (n ≤ 1): ∀x∀y(x=y)
  • Exactly one (n = 1): ∃x ^ ∀x∀y(x=y)
  • More than one (n > 1): ∃x ^ ~[∃x ^ ∀x∀y(x=y)]
  • Less than one (n <1): ∀x∀y(x=y) ^ ~[∃x ^ ∀x∀y(x=y)]
  • At least two (n ≥2): ∃x∃y(x=~y) At most two (n≤2): ∀x∀y∀z[(x = y) V {(y=z) V (x=z)}]
  • Exactly two (n = 2): ∃x∃y(x=~y) ^ ∀x∀y∀z[(x = y) V {(y=z) V (x=z)}]
  • More than two (n > 2): ∃x∃y(x=~y) ^ ~[∃x∃y(x=~y) ^ ∀x∀y∀z[(x = y) V {(y=z) V (x=z)}]
  • Less than two (n <2): ∀x∀y∀z[(x = y) V {(y=z) V (x=z)}] ^ ~[∃x∃y(x=~y) ^ ∀x∀y∀z[(x = y) V {(y=z) V (x=z)}]
1

There are 1 best solutions below

0
On BEST ANSWER
  1. $P(x)$ is true for at least one $x$,

$\exists x:P(x)$

  1. $P(x)$ is true for at most one $x$,

$\forall x\forall y(P(x)\land P(y)\implies x=y)$

Another equivalent expression, which is longer but maybe more intuitive,

$\forall x\forall y(x\not=y\implies \neg(P(x)\land P(y)))$

  1. $P(x)$ is true for exactly one $x$,

This is the same as saying, $P(x)$ is true for at least one $x$ AND at most one $x$,

$\exists x:P(x) \land \forall x\forall y(P(x)\land P(y)\implies x=y)$

  1. $P(x)$ is true for more than one $x$, which is the same as saying, $P(x)$ is true for at least two (different) $x$

$\exists x\exists y(x\not=y \land P(x) \land P(y))$

  1. $P(x)$ is true for less than one $x$, which is the same as saying, $P(x)$ is true for at least no $x$

$\neg(\exists x:P(x))$

  1. $P(x)$ is true for less than two (different) $x$, is the same as saying, $P(x)$ is true for at most one $x$

  2. $P(x)$ is true for exactly two (different) $x$, is the same as saying, $P(x)$ is true for at least two $x$ AND for at most two (different) $x$,

$\exists x\exists y(x\not=y \land P(x) \land P(y)) \land \forall x\forall y\forall z(P(x)\land P(y) \land P(z) \implies x=y \lor x=z \lor y=z)$