Kuantifer (logika)

Dalam bahasa alami, kuantifer mengubah kalimat tentang sesuatu yang memiliki beberapa properti menjadi kalimat tentang jumlah (kuantitas) benda sifat. Contoh bilangan dalam bahasa Inggris adalah "all", "some", "many", "few", "most", dan "no"; Contoh kalimat terkuantifikasi adalah "semua orang fana", "beberapa orang fana", dan "tidak ada orang yang fana", adalah benar, dan salah.

Dalam logika matematika, khususnya dalam logika orde pertama, kuantifer mencapai tugas serupa, beroperasi pada rumus matematika dari kalimat bahasa Inggris.

Lebih tepatnya, pembilang menentukan jumlah spesimen dalam domain wacana yang menggunakan rumus terbuka. Dua bilangan formal yang umum adalah "kuantifikasi universal" (pembilang universal, secara tradisional dilambangkan dengan "∀" ), dan " eksistensial kuantifikasi" (pembilang eksistensial, "∃"). Misalnya, dalam aritmetika, bilangan memungkinkan bahwa bilangan asli berlangsung, dengan menulis bahwa "untuk bilangan asli n, bilangan asli m yang terbesar dari n "; ditulis sebagai formal sebagai "∀ n ∈ℕ. ∃ m ∈ℕ. m > n ". Contoh di atas dapat diformalkan sebagai "∀ p ∈ P. M ( p )", "∃ p ∈ P. M ( p )", dan " ¬ ∃ p ∈ P. M ( p )", ketika P menunjukkan himpunan, dan m ( p ) menunjukkan "p adalah fana".

Rumus dimulai dengan kuantifer disebut rumus kuantifikasi. Kuantifer formal membutuhkan variabel, yang dikatakan terkait, dan subrumus menentukan sifat variabel.

Pengukur formal digeneralisasikan dengan karya Mostowski dan Lindström.

Relasi dengan konjungsi dan disjungsi logis

Untuk domain hingga wacana D = {a ₁, ... a _n }, pembilang universal ekuivalen dengan konjungsi logis dari proposisi dengan istilah tunggal a _i (dengan bentuk Pa _i untuk predikat monadik).

Pengukur eksistensial ekuivalen dengan disjungsi logis dari proposisi digunakan struktur yang sama seperti sebelumnya. Untuk wacana yang tak hingga, persamaannya serupa.

Domain wacana tak hingga

Perhatikan pernyataan berikut:

1 · 2 = 1 + 1, dan 2 · 2 = 2 + 2, dan 3 · 2 = 3 + 3, ..., dan 100 · 2 = 100 + 100, dan ..., dll.

Konjungsi proposisi yang tak hingga dari sudut bahasa formal secara langsung menjadi masalah, karena aturan sintaks dengan menghasilkan kata terbatas.

Contoh di atas, karena prosedur untuk konjungsi. Namun, jika pernyataan dibuat tentang bilangan irasional, tidak ada cara untuk menghitung semua konjungsi, karena irasional tidak disebutkan. Rumus ekuivalen ringkas masalah menggunakan penghitungan universal:

Untuk bilangan asli n, n · 2 = n + n .

Analisis serupa berlaku untuk disjungsi,

1 sama dengan 5 + 5, atau 2 sama dengan 5 + 5, atau 3 sama dengan 5 + 5, ..., atau 100 sama dengan 5 + 5, atau ..., dll.

dirumuskan ulang menggunakan kuantifikasi eksistensial:

Untuk beberapa bilangan asli n, n sama dengan 5 + 5.

Pendekatan aljabar untuk kuantifikasi

Dimungkinkan untuk merancang aljabar abstrak yang modelnya mencakup bahasa formal dengan kuantifikasi, tetapi kemajuannya lambat dan minat pada aljabar terbatas. Tiga pendekatan dirancang saat ini:

• Aljabar relasi, ditemukan oleh Augustus De Morgan, dan diterbitkan oleh Charles Sanders Peirce, Ernst Schröder, Alfred Tarski, dan siswa Tarski. Aljabar relasi tidak dapat merepresentasikan rumus dengan bilangan yang bersarang lebih dari tiga kedalaman. Anehnya, model aljabar relasi mencakup teori himpunan aksiomatik ZFC dan aritmetika Peano ;
• Tabung aljabar, dibuat ditemukan Alfred Tarski, Leon Henkin, dan lainnya;
• Aljabar poliadic dari Paul Halmos.

Notasi

Dua bilangan yang umum adalah bilangan universal dan bilangan eksistensial. Simbol tradisional untuk pembilang universal adalah " ∀ ", huruf yang diputar " A ", yang berarti "semua". Simbol yang sesuai untuk pembilang eksistensial adalah " ∃ ", huruf " E " yang diputar, yang berarti "ada".

Contoh translasi pernyataan terkuantifikasi dalam bahasa alami seperti bahasa Indonesia adalah sebagai berikut. Dengan pernyataan, "Setiap teman Udin suka menari atau suka pergi ke pantai (atau keduanya)", aspek kunci dapat diidentifikasi dan ditulis ulang menggunakan simbol termasuk bilangan. Jadi, misalkan X adalah himpunan dari semua teman Udin, U( x ) predikat "x suka menari", dan Q( x ) predikat "x suka pergi ke pantai". Maka kalimat diatas dapat ditulis dalam notasi formal sebagai $\forall {x}{\in }X,U(x)\lor Q(x)$, yang dibaca, "untuk x yang merupakan anggota X, U berlaku untuk x atau Q berlaku untuk x ".

Beberapa ekspresi terkuantifikasi lainnya dibangun sebagai berikut,

$\exists {x}\,U$   $\forall {x}\,U$

untuk rumus U kedua ungkapan ini (menggunakan definisi di atas) dibaca sebagai "ada teman Udin yang suka menari" dan "semua teman Udin suka menari". Notasi varian termasuk, untuk himpunan X dan himpunan anggota x :

$\bigvee _{x}U$  $(\exists {x})U$  $(\exists x\ .\ U)$  $\exists x\ \cdot \ U$  $(\exists x:U)$  $\exists {x}(U)$   $\exists _{x}\,U$  $\exists {x}{,}\,U$  $\exists {x}{\in }X\,U$  $\exists \,x{:}X\,U$

Semua variasi berlaku untuk penghitungan universal. Variasi lain untuk pembilang universal adalah

$\bigwedge _{x}U$  $\bigvee xU$   $(x)\,U$

Beberapa versi notasi secara eksplisit menyebutkan kisaran kuantifikasi. Kisaran penghitungan harus selalu ditentukan; untuk teori matematika tertentu dapat dilakukan dengan beberapa cara:

• Asumsikan domain diskursus tetap untuk setiap kuantifikasi, seperti yang dilakukan dalam teori himpunan Zermelo–Fraenkel ,
• Perbaiki beberapa domain wacana terlebih dahulu dan mengharuskan setiap variabel memiliki domain yang dideklarasikan, yang merupakan jenis variabel itu. Ini sejalan dengan situasi dalam bahasa pemrograman komputer yang diketik secara statis, di mana variabel telah menyatakan tipe.
• Sebutkan secara eksplisit kisaran kuantifikasi, mungkin menggunakan simbol untuk himpunan semua objek dalam domain itu (atau tipe objek dalam domain itu).

Menggunakan variabel apa pun sebagai variabel terkuantifikasi sebagai pengganti variabel lain, di bawah batasan tertentu di mana pengambilan variabel. Meskipun notasi menggunakan variabel yang diketik, variabel jenis itu dapat digunakan.

Secara informal atau dalam bahasa alami, "∀ x " atau "∃ x "setelah atau di tengah P ( x ). Secara formal, frase yang memperkenalkan variabel dummy ditempatkan di depan.

Rumus matematika menggabungkan ekspresi simbolis untuk bilangan dengan bilangan bahasa alami seperti,

Untuk setiap bilangan asli x ,. . .

Ada x . . .

Untuk setidaknya satu x,. . . .

Kata kunci untuk penghitungan keunikan meliputi:

Untuk tepat satu bilangan asli x ,. . .

Ada satu dan hanya satu x seperti itu. . . .

Selanjutnya, x dapat diganti dengan kata ganti. Sebagai contoh,

Untuk setiap bilangan asli, hasil perkaliannya dengan 2 sama dengan penjumlahannya dengan dirinya sendiri.

Beberapa bilangan asli adalah bilangan prima.

Urutan kuantifer (bersarang)

Urutan bilangan untuk makna, seperti yang diilustrasikan oleh dua proposisi berikut:

Untuk setiap bilangan asli n, terdapat bilangan asli s sehingga s = n ².

Hal ini jelas benar, setiap bilangan asli memiliki persegi. Arti pernyataan di mana urutan bilangan dibalik berbeda:

Terdapat bilangan asli s sehingga untuk setiap bilangan asli n, s = n ².

Hal ini jelas salah; ia menegaskan bahwa ada satu bilangan asli s yang merupakan kuadrat dari setiap bilangan asli. Ini karena sintaksis mengarahkan bahwa variabel apa pun tidak dapat menjadi fungsi dari variabel yang diperkenalkan selanjutnya.

Sebuah contoh non-trivial dari analisis matematis adalah konsep keseragaman dan kontinuitas pointwise, yang definisinya hanya berbeda dengan pertukaran dalam posisi dua bilangan. Fungsi f dari R ke R.

• Kontinu Pointwise jika ${\textstyle \forall \varepsilon >0\;\forall x\in \mathbb {R} \;\exists \delta >0\;\forall h\in \mathbb {R} \;(|h|<\delta \,\Rightarrow \,|f(x)-f(x+h)|<\varepsilon )}$
• Kontinu unuform jika ${\textstyle \forall \varepsilon >0\;\exists \delta >0\;\forall x\in \mathbb {R} \;\forall h\in \mathbb {R} \;(|h|<\delta \,\Rightarrow \,|f(x)-f(x+h)|<\varepsilon )}$

Dalam kasus sebelumnya, nilai tertentu yang dipilih untuk δ dapat berupa fungsi dari ε dan x, variabel yang mendahuluinya. Dalam kasus terakhir, δ dapat menjadi fungsi hanya dari ε (yaitu, dipilih terlepas dari x). Sebagai contoh, f(x) = x², tetapi tidak keseragaman kontinuitas. Sebaliknya, menukar dua bilangan universal awal dalam definisi kontinuitas pointwise tidak mengubah artinya.

Kedalaman maksimum penyarangan bilangan dalam sebuah rumus disebut "pangkat kuantifer".

Ekspresi ekuivalen

Jika D adalah domain dari x dan P(x) adalah predikat yang bergantung pada variabel objek x, maka proposisi universal dapat dinyatakan sebagai

$\forall x\!\in \!D\;P(x).$

Notasi ini dikenal sebagai dibatasi atau direlatifkan atau kuantifikasi terbatas. Sama halnya menulis,

$\forall x\;(x\!\in \!D\to P(x)).$

Proposisi eksistensial dapat diekspresikan dengan kuantifikasi terbatas sebagai

$\exists x\!\in \!D\;P(x),$

atau ekuivalen

$\exists x\;(x\!\in \!\!D\land P(x)).$

Dengan negasi, hanya satu dari bilangan universal atau eksistensial yang diperlukan untuk melakukan kedua tugas tersebut:

$\neg (\forall x\!\in \!D\;P(x))\equiv \exists x\!\in \!D\;\neg P(x),$

yang menunjukkan bahwa untuk menyangkal proposisi "untuk semua x", seseorang tidak perlu lebih dari menemukan x yang predikatnya salah. Demikian pula,

$\neg (\exists x\!\in \!D\;P(x))\equiv \forall x\!\in \!D\;\neg P(x),$

untuk menyangkal sebuah proposisi "ada x", kita perlu menunjukkan bahwa predikatnya salah untuk semua x.

Semantik formal

Semantik matematika adalah aplikasi matematika untuk mempelajari makna ekspresi dalam bahasa formal. memiliki tiga elemen: spesifikasi matematis dari kelas objek melalui sintaks, spesifikasi matematis dari berbagai domain semantik dan hubungan antara keduanya, yang biasanya dinyatakan sebagai fungsi dari objek sintaksis ke objek semantik. Artikel ini hanya membahas masalah bagaimana elemen pembilang diinterpretasikan. Sintaks rumus dapat digunakan oleh pohon sintaks. Kuantifer memiliki ruang lingkup, dan variabel x adalah bebas jika tidak berada dalam lingkup perhitungan untuk variabel. Maka

$\forall x(\exists yB(x,y))\vee C(y,x)$

kemunculan x dan y dalam C(y, x) bebas, sedangkan kemunculan x dan y dalam B(y, x) bond (yaitu tidak bebas).

Pohon sintaks dari rumus $\forall x(\exists yB(x,y))\vee C(y,x)$, menggambarkan ruang lingkup dan tangkapan variabel. Kemunculan variabel terikat dan bebas masing-masing diberi warna merah dan hijau.

Interpretasi untuk kalkulus predikat orde pertama mengasumsikan sebagai domain individu X. Rumus A dari variabel bebas x₁, ..., x_n diinterpretasikan sebagai fungsi Boolean F(v₁, ..., v_n) dari argumen n, di mana setiap argumen berkisar pada domain X. Nilai Boolean berarti bahwa fungsi tersebut mengasumsikan salah satu nilai T (ditafsirkan sebagai kebenaran) atau F (ditafsirkan sebagai kepalsuan). Penafsiran rumus

$\forall x_{n}A(x_{1},\ldots ,x_{n})$

adalah fungsi G dari n-1 argumen G(v₁, ..., v_n-1) = T jika dan hanya jika F(v₁, ..., v_n-1, w) = T untuk w in X. Jika F(v₁, ..., v_n-1, w) = F untuk setidaknya satu nilai w, maka G(v₁, ..., v_n-1) = F. Demikian pula interpretasi rumusnya

$\exists x_{n}A(x_{1},\ldots ,x_{n})$

adalah fungsi H dari n-1 argumen sedemikian rupa H(v₁, ..., v_n-1) = T jika dan hanya jika F(v₁, ..., v_n-1, w) = T untuk setidaknya satu w dan jika tidak H(v₁, ..., v_n-1) = F.

Semantik untuk kuantifikasi keunikan membutuhkan kalkulus predikat orde pertama dengan persamaan. Artinya predikat dua tempat yang dibedakan "="; semantik juga dimodifikasi sedemikian rupa sehingga "=" selalu diartikan sebagai relasi persamaan dua tempat pada X. Interpretasinya adalah

$\exists !x_{n}A(x_{1},\ldots ,x_{n})$

kemudian adalah fungsi dari n-1 argumen, yang merupakan logika dari interpretasi

$\exists x_{n}A(x_{1},\ldots ,x_{n})$

$\forall y,z\left\{A(x_{1},\ldots ,x_{n-1},y)\wedge A(x_{1},\ldots ,x_{n-1},z)\implies y=z\right\}.$

Jenis kuantifikasi mendefinisikan operator penutupan yang sesuai pada himpunan rumus, dengan menambahkan, untuk setiap variabel bebas x, pembilang untuk x. Misalnya, penutupan eksistensial dari rumus terbuka n>2 ∧ xⁿ+yⁿ=zⁿ adalah rumus tertutup ∃n ∃x ∃y ∃z (n>2 ∧ xⁿ+yⁿ=zⁿ); rumus terakhir, ketika ditafsirkan di atas bilangan asli, diketahui salah oleh teorema terakhir Fermat. Sebagai contoh lain, aksioma persamaan, x+y=y+x, biasanya dimaksudkan untuk menunjukkan penutupan universal ∀x ∀y (x+y=y+x) untuk mengekspresikan komutatif.

Paucal, multal dan kuantifer derajat lainnya

Lihat pula: Teorema Fubini dan Ukuran (matematika)

Dari bilangan yang dibahas sebelumnya berlaku untuk bilangan seperti

Ada banyak bilangan bulat n < 100, sehingga n habis dibagi 2 atau 3 atau 5.

Salah satu mekanisme interpretasi yang mungkin dapat diperoleh sebagai berikut: Misalkan sebagai tambahan untuk domain semantik X, ukuran probabilitas P yang ditentukan pada X dan bilangan Cutoff 0 < a ≤ b ≤ 1. If A adalah rumus dengan variabel bebas x₁,...,x_n yang interpretasi fungsi F variabel v₁,...,v_n kemudian interpretasi

$\exists ^{\mathrm {many} }x_{n}A(x_{1},\ldots ,x_{n-1},x_{n})$

adalah fungsi dari v₁,...,v_n-1 yaitu T jika dan hanya jika

$\operatorname {P} \{w:F(v_{1},\ldots ,v_{n-1},w)=\mathbf {T} \}\geq b$

dan F sebaliknya. Begitu pula dengan interpretasi

$\exists ^{\mathrm {few} }x_{n}A(x_{1},\ldots ,x_{n-1},x_{n})$

adalah fungsi dari v₁,...,v_n-1 yaitu F jika dan hanya jika

$0<\operatorname {P} \{w:F(v_{1},\ldots ,v_{n-1},w)=\mathbf {T} \}\leq a$

dan T sebaliknya.

Kuantifer lainnya

Beberapa kuantifer lain telah diusulkan dari waktu ke waktu. Secara khusus, pengukur solusi,^:28 mencatat § (tanda bagian) dan membaca "itu". Sebagai contoh,

$\left[\S n\in \mathbb {N} \quad n^{2}\leq 4\right]=\{0,1,2\}$

dibaca "itu n dalam N seperti itu n² ≤ 4 berada dalam {0,1,2}." Konstruksi yang sama dapat diekspresikan dalam notasi himpunan-builder sebagai

$\{n\in \mathbb {N} :n^{2}\leq 4\}=\{0,1,2\}.$

Berlawanan dengan bilangan lain, § menghasilkan satu himpunan dari rumus.

Beberapa bilangan lain yang terkadang digunakan dalam matematika meliputi:

• Ada banyak elemen yang tak terbatas sehingga...
• Untuk semua kecuali banyak elemen yang terbatas... (kadang-kadang dinyatakan sebagai "untuk semua elemen...").
• Ada banyak elemen yang tak terhitung banyaknya sehingga ...
• Untuk semua kecuali banyak elemen...
• Untuk semua elemen dalam satu himpunan ukuran positif...
• Untuk semua elemen kecuali yang ada dalam satu himpunan ukuran nol...

Lihat pula

• General mutlak
• Hampir semua (matematika)
• Kantifer bercabang
• Kuantifer bersyarat
• Hitung kuantifikasi
• Iventuali (matematika)
• Kuantifer generalisasi - properti tingkat tinggi yang digunakan sebagai semantik standar dari frase kata benda
• Kuantifer Lindström - pembilang poladik umum
• Kuantifer eliminasi
• Kuantifer shift

Bibliografi

• Barwise, Jon; and Etchemendy, John, 2000. Language Proof and Logic. CSLI (University of Chicago Press) and New York: Seven Bridges Press. A gentle introduction to first-order logic by two first-rate logicians.
• Frege, Gottlob, 1879. Begriffsschrift. Translated in Jean van Heijenoort, 1967. From Frege to Gödel: A Source Book on Mathematical Logic, 1879-1931. Harvard University Press. The first appearance of quantification.
• Hilbert, David; and Ackermann, Wilhelm, 1950 (1928). Principles of Mathematical Logic. Chelsea. Translation of Grundzüge der theoretischen Logik. Springer-Verlag. The 1928 first edition is the first time quantification was consciously employed in the now-standard manner, namely as binding variables ranging over some fixed domain of discourse. This is the defining aspect of first-order logic.
• Peirce, C. S., 1885, "On the Algebra of Logic: A Contribution to the Philosophy of Notation, American Journal of Mathematics, Vol. 7, pp. 180–202. Reprinted in Kloesel, N. et al., eds., 1993. Writings of C. S. Peirce, Vol. 5. Indiana University Press. The first appearance of quantification in anything like its present form.
• Reichenbach, Hans, 1975 (1947). Elements of Symbolic Logic, Dover Publications. The quantifiers are discussed in chapters §18 "Binding of variables" through §30 "Derivations from Synthetic Premises".
• Westerståhl, Dag, 2001, "Quantifiers," in Goble, Lou, ed., The Blackwell Guide to Philosophical Logic. Blackwell.
• Wiese, Heike, 2003. Numbers, language, and the human mind. Cambridge University Press. ISBN 0-521-83182-2.

Pranala luar

• Hazewinkel, Michiel, ed. (2001) [1994], "Quantifier", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4 
• ""For all" and "there exists" topical phrases, sentences and expressions". Diarsipkan dari versi asli tanggal March 1, 2000.  . From College of Natural Sciences, University of Hawaii at Manoa.
• Stanford Encyclopedia of Philosophy:
  • Shapiro, Stewart (2000). "Classical Logic" (Covers syntax, model theory, and metatheory for first order logic in the natural deduction style.)
  • Westerståhl, Dag (2005). "Generalized quantifiers"
• Peters, Stanley; Westerståhl, Dag (2002). "Quantifiers" Diarsipkan 2012-07-16 di Wayback Machine.