Kuantifikasi semesta

Kuantifikasi logis dengan pernyataan berlaku untuk semua objekTemplat:SHORTDESC:Kuantifikasi logis dengan pernyataan berlaku untuk semua objek

Kuantifikasi semesta
Jenis	Kuantor
Cabang	Logika matematika
Pernyataan	∀ x P ( x ) {\displaystyle \forall xP(x)} $\forall xP(x)$ adalah benar ketika P ( x ) {\displaystyle P(x)} $P(x)$ adalah benar untuk semua nilai dari x {\displaystyle x} $x$ .
Pernyataan dalam bentuk simbol	∀ x P ( x ) {\displaystyle \forall xP(x)} $\forall xP(x)$

Dalam logika matematika, kuantifikasi semesta atau kuantifikasi universal adalah jenis kuantifikasi yang dapat diartikan sebagai "untuk semua" atau "untuk setiap". Kuantifikasi semesta menyatakan bahwa suatu predikat terpenuhi oleh setiap anggota universal of discourse. Dengan kata lain, kuantifikasi semesta adalah suatu predikat dari sifat atau relasi untuk setiap anggota domain. Hal ini menyatakan bahwa predikat dalam cakupan kuantifikasi semesta adalah benar untuk nilai variabel predikat.

Kuantifikasi semesta umumnya dilambangkan dengan huruf A terbalik (∀). Hal ini dapat dikaitkan dengan kuantor semesta, yang mana ketika simbol operator logika ini digunakan bersama dengan variabel predikat. Kuantor semesta dapat ditulis sebagai ∀ x {\displaystyle \forall x} $\forall x$ . Kuantifikasi semesta berbeda dengan kuantifikasi eksistensial, jenis kuantifikasi yang hanya mengatakan bahwa sifat atau relasi berlaku untuk setidaknya satu anggota domain.

Kuantor universal diberi kode sebagai U+2200∀for all dalam Unicode, dan diberi kode\forall dalam markah LaTeX.

Notasi

Dalam logika simbolik, kuantor semesta diberi simbol ∀ {\displaystyle \forall } $\forall$ , sebuah huruf "A" terbalik, dengan Unicode U+2200. Simbol ini digunakan untuk mengartikan kuantifikasi semesta. Cara menggunakan simbol tersebut berawal dari Gerhard Gentzen pada tahun 1935, yang sejalan dengan notasi Giuseppe Peano ∃ {\displaystyle \exists } $\exists$ (sebuah huruf E terbalik) sebagai simbol kuantifikasi eksistensial.^[1]

Sebagai contoh, jika P ( n ) {\displaystyle P(n)} $P(n)$ menyatakan predikat " 2 ⋅ n > 2 + n {\displaystyle 2\cdot n>2+n} $2\cdot n>2+n$ " dan N {\displaystyle \mathbb {N} } $\mathbb {N}$ menyatakan himpunan bilangan asli, maka ∀ n ∈ N P ( n ) {\displaystyle \forall n\!\in \!\mathbb {N} \;P(n)} $\forall n\!\in \!\mathbb {N} \;P(n)$ adalah pernyataan (yang salah). Pernyataan ini dapat dibaca sebagai, "untuk semua bilangan asli n {\displaystyle n} $n$ , berlaku 2 ⋅ n > 2 + n {\displaystyle 2\cdot n>2+n} $2\cdot n>2+n$ ". Contoh yang serupa dengannya adalah: jika Q ( n ) {\displaystyle Q(n)} $Q(n)$ menyatakan predikat " n {\displaystyle n} $n$ adalah komposit", maka ∀ n ∈ N ( Q ( n ) → P ( n ) ) {\displaystyle \forall n\!\in \!\mathbb {N} \;{\bigl (}Q(n)\rightarrow P(n){\bigr )}} $\forall n\!\in \!\mathbb {N} \;{\bigl (}Q(n)\rightarrow P(n){\bigr )}$ adalah pernyataan (yang benar). Pernyataan ini dibaca, "untuk semua bilangan asli n {\displaystyle n} $n$ , jika n {\displaystyle n} $n$ komposit, maka 2 ⋅ n > 2 + n {\displaystyle 2\cdot n>2+n} $2\cdot n>2+n$ ".

Sifat

Negasi

Negasi dari fungsi berkuantor semesta diperoleh dengan mengubah kuantor semesta menjadi kuantor eksistensial, dan kemudian memberi tanda negasi ¬ {\displaystyle \lnot } $\lnot$ pada rumus. Dengan kata lain, ¬ ∀ x P ( x ) {\displaystyle \lnot \forall x\;P(x)} $\lnot \forall x\;P(x)$ ekuivalen dengan ∃ x ¬ P ( x ) {\displaystyle \exists x\;\lnot P(x)} $\exists x\;\lnot P(x)$ .

Operator logika lainnya

Kuantor universal (dan eksistensial) untuk operator logika ∧, ∨, →, dan ↚ adalah sebagai berikut:

P ( x ) ∧ ( ∃ y ∈ Y Q ( y ) ) ≡ ∃ y ∈ Y ( P ( x ) ∧ Q ( y ) ) P ( x ) ∨ ( ∃ y ∈ Y Q ( y ) ) ≡ ∃ y ∈ Y ( P ( x ) ∨ Q ( y ) ) , asalkan Y ≠ ∅ P ( x ) → ( ∃ y ∈ Y Q ( y ) ) ≡ ∃ y ∈ Y ( P ( x ) → Q ( y ) ) , asalkan Y ≠ ∅ P ( x ) ↚ ( ∃ y ∈ Y Q ( y ) ) ≡ ∃ y ∈ Y ( P ( x ) ↚ Q ( y ) ) P ( x ) ∧ ( ∀ y ∈ Y Q ( y ) ) ≡ ∀ y ∈ Y ( P ( x ) ∧ Q ( y ) ) , asalkan Y ≠ ∅ P ( x ) ∨ ( ∀ y ∈ Y Q ( y ) ) ≡ ∀ y ∈ Y ( P ( x ) ∨ Q ( y ) ) P ( x ) → ( ∀ y ∈ Y Q ( y ) ) ≡ ∀ y ∈ Y ( P ( x ) → Q ( y ) ) P ( x ) ↚ ( ∀ y ∈ Y Q ( y ) ) ≡ ∀ y ∈ Y ( P ( x ) ↚ Q ( y ) ) , asalkan Y ≠ ∅ {\displaystyle {\begin{aligned}P(x)\land (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\land Q(y))\\P(x)\lor (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\lor Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \\P(x)\to (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\to Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \\P(x)\nleftarrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\nleftarrow Q(y))\\P(x)\land (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\land Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \\P(x)\lor (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\lor Q(y))\\P(x)\to (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\to Q(y))\\P(x)\nleftarrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\nleftarrow Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \end{aligned}}} ${\begin{aligned}P(x)\land (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\land Q(y))\\P(x)\lor (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\lor Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \\P(x)\to (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\to Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \\P(x)\nleftarrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\nleftarrow Q(y))\\P(x)\land (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\land Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \\P(x)\lor (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\lor Q(y))\\P(x)\to (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\to Q(y))\\P(x)\nleftarrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\nleftarrow Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \end{aligned}}$

Sebaliknya, untuk penghubung logis ↑, ↓, ↛, dan ←, maka kuantifikasi tersebut dapat dinyatakan sebagai berikut:

P ( x ) ↑ ( ∃ y ∈ Y Q ( y ) ) ≡ ∀ y ∈ Y ( P ( x ) ↑ Q ( y ) ) P ( x ) ↓ ( ∃ y ∈ Y Q ( y ) ) ≡ ∀ y ∈ Y ( P ( x ) ↓ Q ( y ) ) , asalkan Y ≠ ∅ P ( x ) ↛ ( ∃ y ∈ Y Q ( y ) ) ≡ ∀ y ∈ Y ( P ( x ) ↛ Q ( y ) ) , asalkan Y ≠ ∅ P ( x ) ← ( ∃ y ∈ Y Q ( y ) ) ≡ ∀ y ∈ Y ( P ( x ) ← Q ( y ) ) P ( x ) ↑ ( ∀ y ∈ Y Q ( y ) ) ≡ ∃ y ∈ Y ( P ( x ) ↑ Q ( y ) ) , asalkan Y ≠ ∅ P ( x ) ↓ ( ∀ y ∈ Y Q ( y ) ) ≡ ∃ y ∈ Y ( P ( x ) ↓ Q ( y ) ) P ( x ) ↛ ( ∀ y ∈ Y Q ( y ) ) ≡ ∃ y ∈ Y ( P ( x ) ↛ Q ( y ) ) P ( x ) ← ( ∀ y ∈ Y Q ( y ) ) ≡ ∃ y ∈ Y ( P ( x ) ← Q ( y ) ) , asalkan Y ≠ ∅ {\displaystyle {\begin{aligned}P(x)\uparrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\uparrow Q(y))\\P(x)\downarrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\downarrow Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \\P(x)\nrightarrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\nrightarrow Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \\P(x)\gets (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\gets Q(y))\\P(x)\uparrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\uparrow Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \\P(x)\downarrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\downarrow Q(y))\\P(x)\nrightarrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\nrightarrow Q(y))\\P(x)\gets (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\gets Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \\\end{aligned}}} ${\begin{aligned}P(x)\uparrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\uparrow Q(y))\\P(x)\downarrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\downarrow Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \\P(x)\nrightarrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\nrightarrow Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \\P(x)\gets (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\gets Q(y))\\P(x)\uparrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\uparrow Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \\P(x)\downarrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\downarrow Q(y))\\P(x)\nrightarrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\nrightarrow Q(y))\\P(x)\gets (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\gets Q(y)),&{\text{asalkan }}\mathbf {Y} \neq \emptyset \\\end{aligned}}$

Aturan inferensi

Aturan inferensi adalah aturan yang membenarkan langkah-langkah logika, dimulai dari hipotesis sampai ke kesimpulan. Beberapa aturan-aturan tersebut memakai kuantor universal.

Instansiasi semesta menyimpulkan bahwa, jika diketahui bahwa fungsi proposisional adalah benar secara universal, maka hal tersebut benar untuk sebarang anggota universal of discourse. Sifat-sifat ini dapat dinyatakan dengan lambang ∀ x ∈ X P ( x ) → P ( c ) , {\displaystyle \forall {x}{\in }\mathbf {X} \,P(x)\to P(c),} $\forall {x}{\in }\mathbf {X} \,P(x)\to P(c),$ dengan c {\displaystyle c} $c$ menyatakan sebarang anggota universe of discourse.

Universal generalization menyimpulkan bahwa fungsi proposisional adalah benar secara universal, jika benar untuk sebarang anggota universal of discourse. Untuk sebarang c {\displaystyle c} $c$ , dapat dinyatakan dengan lambang P ( c ) → ∀ x ∈ X P ( x ) . {\displaystyle P(c)\to \ \forall {x}{\in }\mathbf {X} \,P(x).} $P(c)\to \ \forall {x}{\in }\mathbf {X} \,P(x).$ Anggota c {\displaystyle c} $c$ harus sepenuhnya adalah sebarang. Jika tidak, maka logika tersebut berkata lain: jika c {\displaystyle c} $c$ tidak sebarang, melainkan anggota khusus dari universal of discourse, maka P ( c ) {\displaystyle P(c)} $P(c)$ hanya menyiratkan kuantifikasi eksistensial dari fungsi proposisional.

Himpunan kosong

Berdasarkan konvensi, rumus ∀ x ∈ ∅ P ( x ) {\displaystyle \forall {x}{\in }\emptyset \,P(x)} $\forall {x}{\in }\emptyset \,P(x)$ selalu benar untuk P ( x ) {\displaystyle P(x)} $P(x)$ manapun.

Universal closure

Universal closure dari rumus φ {\displaystyle \varphi } $\varphi$ menyatakan rumus tanpa variabel bebas yang diperoleh dengan menambahkan kuantor universal untuk setiap variabel bebas di φ {\displaystyle \varphi } $\varphi$ . Sebagai contoh, universal closure dari P ( y ) ∧ ∃ x Q ( x , z ) {\displaystyle P(y)\land \exists xQ(x,z)} $P(y)\land \exists xQ(x,z)$ ditulis ∀ y ∀ z ( P ( y ) ∧ ∃ x Q ( x , z ) ) . {\displaystyle \forall y\forall z(P(y)\land \exists xQ(x,z)).} $\forall y\forall z(P(y)\land \exists xQ(x,z)).$