Kuantifikasi eksistensial

Dalam logika predikat, kuantifikasi eksistensial adalah jenis kuantifer, konstanta logika yang ditafsirkan sebagai "ada", "setidaknya ada satu", atau "untuk beberapa". Dilambangkan dengan operator logika simbol ∃, jika digunakan bersama dengan variabel predikat, disebut kunatifer eksistensial (" $\exists x$ " or " $\exists(x)$ ").^[1] Kuantifikasi eksistensial berbeda dari kuantifikasi universal ("untuk semua"), yang menegaskan bahwa sifat atau relasi untuk semua anggota domain.^[2]^[3] Beberapa sumber menggunakan istilah eksistensialisasi untuk merujuk pada kuantifikasi eksistensial.^[4]

Dasar

Pertimbangkan rumus yang menyatakan bahwa beberapa bilangan asli dikalikan dengan 25.

0·0 = 25, atau 1·1 = 25, atau 2·2 = 25, atau 3·3 = 25, dan seterusnya.

Ini tampaknya menjadi disjungsi logis karena penggunaan berulang "atau". Namun, "dan seterusnya" membuat hal ini tidak untuk diintegrasikan dan diinterpretasikan sebagai suatu disjungsi dalam logika formal. Sebaliknya, pernyataan tersebut dapat diutarakan secara lebih formal menjadi

Untuk beberapa 1 asli n, n·n = 25.

Pernyataan tunggal menggunakan kuantifikasi eksistensial.

Pernyataan ini lebih tepat dari yang asli, karena frasa "dan seterusnya" tidak selalu mencakup semua bilangan asli dan mengecualikan yang lainnya. Dan karena domain tidak dinyatakan secara eksplisit, frasa tersebut tidak dapat diartikan secara formal. Namun, dalam pernyataan terkuantifikasi, bilangan asli disebutkan secara eksplisit.

Contoh khusus, karena 5 adalah bilangan asli, dan ketika kita mengganti 5 untuk n, memproduksi "5·5 = 25", yang mana yang benar. Tidak menggunakan "n·n = 25" hanya berlaku untuk satu bilangan asli 5; bahkan keberadaan satu solusi sudah cukup untuk membuktikan kuantifikasi eksistensial ini benar. Sebaliknya, "Untuk beberapa bilangan genap n, n·n = 25" salah, karena bahkan tidak ada solusi.

Domain wacana, yang menentukan nilai variabel n yang diperbolehkan untuk diambil, oleh karena itu penting untuk kebenaran atau kepalsuan pernyataan. Konjungsi logis digunakan untuk membatasi domain diskursus untuk memenuhi predikat tertentu. Sebagai contoh:

Untuk beberapa bilangan ganjil positif n, n·n = 25

adalah ekuivalen logika dengan

Untuk beberapa bilangan asli n, n adalah ganjil dan n·n = 25.

Di sini, "dan" adalah konjungsi logika.

Dalam logika simbolik, "∃" (huruf "E" terbalik atau terbalik, dalam font sans-serif) digunakan untuk menunjukkan kuantifikasi eksistensial.^[1]^[5] Jadi, jika P(a, b, c) is predikat "a·b = c", dan $\mathbb {N}$ adalah himpunan dari bilangan asli, maka

\exists {n}{\in }\mathbb {N} \,P(n,n,25)

adalah pernyataan (benar)

Untuk beberapa bilangan asli n, n·n = 25.

Demikian pula, jika Q(n) adalah predikat "n genap", maka

\exists {n}{\in }\mathbb {N} \,{\big (}Q(n)\;\!\;\!{\wedge }\;\!\;\!P(n,n,25){\big )}

adalah pernyataan (salah)

Untuk beberapa bilangan asli n, n genap dan n·n = 25.

Dalam matematika, bukti dari pernyataan "beberapa" dapat dicapai baik dengan bukti konstruktif, yang menunjukkan objek yang memenuhi pernyataan "beberapa", atau dengan bukti nonkonstruktif, yang menunjukkan bahwa pasti ada benda seperti itu tetapi tanpa memamerkannya.^[6]

Sifat

Negasi

Fungsi proposisional terkuantifikasi adalah pernyataan; dengan demikian, seperti pernyataan, fungsi terkuantifikasi dapat dinegasikan. Simbol $\lnot \$ digunakan untuk menunjukkan negasi.

Misalnya, jika P(x) adalah predikat "x lebih besar dari 0 dan kurang dari 1", maka, untuk domain diskursus X dari semua bilangan asli, Kuantifikasi eksistensial "Ada bilangan asli x yang lebih besar dari 0 dan kurang dari 1" dapat dinyatakan secara simbolis sebagai:

\exists {x}{\in }\mathbf {X} \,P(x)

Hal tersebut bisa dibuktikan salah. Sejujurnya, harus dikatakan, "Tidak ada kasus bahwa ada bilangan asli x yang lebih besar dari 0 dan kurang dari 1", atau, secara simbolis:

\lnot \ \exists {x}{\in }\mathbf {X} \,P(x)

.

Jika tidak ada elemen dari domain wacana yang pernyataannya benar, maka itu pasti salah untuk semua elemen. Artinya, negasi dari

\exists {x}{\in }\mathbf {X} \,P(x)

secara logis setara dengan "Untuk bilangan asli x, x tidak lebih besar dari 0 dan kurang dari 1", atau:

\forall {x}{\in }\mathbf {X} \,\lnot P(x)

Secara umum, maka negasi dari kuantifikasi eksistensial fungsi proposisional adalah kuantifikasi universal dari negasi fungsi proposisional; secara simbolis,

\lnot \ \exists {x}{\in }\mathbf {X} \,P(x)\equiv \ \forall {x}{\in }\mathbf {X} \,\lnot P(x)

(Maka, ini adalah generalisasi dari Hukum De Morgan untuk predikat logika.)

Kesalahan umum menyatakan "semua orang belum menikah" (yaitu, "tidak ada orang yang menikah"), ketika "tidak semua orang menikah" (yaitu, "ada orang yang belum menikah") dimaksudkan:

\lnot \ \exists {x}{\in }\mathbf {X} \,P(x)\equiv \ \forall {x}{\in }\mathbf {X} \,\lnot P(x)\not \equiv \ \lnot \ \forall {x}{\in }\mathbf {X} \,P(x)\equiv \ \exists {x}{\in }\mathbf {X} \,\lnot P(x)

Negasi pula dapat diekspresikan melalui pernyataan "untuk tidak", bukan "untuk beberapa":

\nexists {x}{\in }\mathbf {X} \,P(x)\equiv \lnot \ \exists {x}{\in }\mathbf {X} \,P(x)

Tidak seperti kuantifer universal, kuantifer eksistensial mendistribusikan melalui disjungsi logis:

$\exists {x}{\in }\mathbf {X} \,P(x)\lor Q(x)\to \ (\exists {x}{\in }\mathbf {X} \,P(x)\lor \exists {x}{\in }\mathbf {X} \,Q(x))$

Kaidah Inferensi

Templat:Kaidah transformasi Kaidah inferensi adalah aturan yang membenarkan langkah logis dari hipotesis hingga kesimpulan. Beberapa kaidah inferensi yang memanfaatkan kuantifer eksistensial.

Pengenalan eksistensial (P∃) menyimpulkan bahwa, jika fungsi proposisional diketahui benar untuk elemen tertentu dari domain wacana, maka benar bahwa terdapat elemen fungsi proposisi yang benar. Secara simbolis,

P(a)\to \ \exists {x}{\in }\mathbf {X} \,P(x)

Eliminasi eksistensial, saat dilakukan dalam pengurangan gaya Fitch, melanjutkan dengan memasukkan sub-turunan baru mengganti variabel yang dikuantifikasi secara eksistensial untuk subjek dalam sub-turunan aktif. Jika kesimpulan dapat dicapai dalam sub-turunan dimana subjek substitusi tidak muncul, maka keluar dari sub-turunan dengan kesimpulan. Alasan di balik eliminasi eksistensial (E∃) adalah sebagai berikut: Jika diberikan bahwa elemen fungsi proposisi yang benar, dan jika kesimpulan dapat dicapai dengan elemen trivial, kesimpulan prinsip, selama tidak memuat nama. Secara simbolis, untuk sembarang c dan untuk proposisi Q di mana c tidak muncul:

\exists {x}{\in }\mathbf {X} \,P(x)\to \ ((P(c)\to \ Q)\to \ Q)

$P(c)\to \ Q$ harus benar untuk semua nilai c pada domain yang sama X; jika, logika tersebut tidak mengikuti: Jika c tidak sembarang, dan sebagai gantinya merupakan elemen spesifik dari domain wacana, maka P(c) tidak dibenarkan lebih banyak informasi tentang objek tersebut.

Himpunan kosong

Rumus $\exists {x}{\in }\emptyset \,P(x)$ adalah salah, maka dari P(x). Hal ini karena $\emptyset$ menunjukkan himpunan kosong, dan tidak ada x dari deskripsi, x dengan predikat yang diberikan P(x) adalah himpunan kosong. Lihat pula prinsip vacuous untuk informasi lebih lanjut.

Sebagai adjoin

Dalam teori kategori dan teori topoi elementer, pembilang eksistensial dapat dipahami sebagai adjoin kiri dari funktor antara himpunan daya, fungsi citra invers dari sebuah fungsi antara himpunan; demikian pula, kuantifikasi universal adalah adjoin kanan.^[7]

Pengkodean

Dalam Unicode dan HTML, simbol dari kode U+2203 ∃ ada (HTML: ∃ ∃ sebagai simbol matematika) dan U+2204 ∄ ada tidak ada (HTML: ∄).

Dalam TeX, simbol diproduksi dengan "\exists".

Lihat pula

Klausa eksistensial
Teorema keberadaan
Logika orde pertama
Kuantifer Lindström
Daftar simbol logika - untuk simbol unicode ∃
Kuantifer varian
Kuantifer
Kuantifikasi unik
Kuantifikasi universal

Catatan

^ ^a ^b "Comprehensive List of Logic Symbols". Math Vault (dalam bahasa Inggris). 2020-04-06. Diakses tanggal 2020-09-04.
^ "Predicates and Quantifiers". www.csm.ornl.gov. Diakses tanggal 2020-09-04.
^ "1.2 Quantifiers". www.whitman.edu. Diakses tanggal 2020-09-04.
^ Allen, Colin; Hand, Michael (2001). Logic Primer (dalam bahasa Inggris). MIT Press. ISBN 0262303965.
^ Simbol ini juga dikenal sebagai operator eksistensial. Terkadang diwakili dengan V.
^ "The Definitive Glossary of Higher Mathematical Jargon: Constructive Proof". Math Vault (dalam bahasa Inggris). 2019-08-01. Diakses tanggal 2020-09-04.
^ Saunders Mac Lane, Ieke Moerdijk, (1992) Sheaves in Geometry and Logic Springer-Verlag. ISBN 0-387-97710-4 Lihat halaman 58

Referensi

Hinman, P. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1-56881-262-0.

[:0-1] "Comprehensive List of Logic Symbols". Math Vault (dalam bahasa Inggris). 2020-04-06. Diakses tanggal 2020-09-04.

[2] "Predicates and Quantifiers". www.csm.ornl.gov. Diakses tanggal 2020-09-04.

[3] "1.2 Quantifiers". www.whitman.edu. Diakses tanggal 2020-09-04.

[4] Allen, Colin; Hand, Michael (2001). Logic Primer (dalam bahasa Inggris). MIT Press. ISBN 0262303965.

[5] Simbol ini juga dikenal sebagai operator eksistensial. Terkadang diwakili dengan V.

[6] "The Definitive Glossary of Higher Mathematical Jargon: Constructive Proof". Math Vault (dalam bahasa Inggris). 2019-08-01. Diakses tanggal 2020-09-04.

[7] Saunders Mac Lane, Ieke Moerdijk, (1992) Sheaves in Geometry and Logic Springer-Verlag. ISBN 0-387-97710-4 Lihat halaman 58

[1]

[2]

[3]

[4]

[5]

[6]

[7]