İyi biçimlendirilmiş formül - Well-formed formula

İçinde matematiksel mantık, önerme mantığı ve yüklem mantığı, bir iyi biçimlendirilmiş formül, kısaltılmış WFF veya wff, genellikle basitçe formül, sonlu sıra nın-nin semboller verilenden alfabe bu bir parçası resmi dil.^[1] Resmi bir dil, dildeki formül seti ile tanımlanabilir.

Bir formül bir sözdizimsel anlamsal verilebilen nesne anlam bir yorum yoluyla. Formüllerin iki temel kullanımı önermeler mantığı ve yüklem mantığındadır.

Giriş

Formüllerin önemli bir kullanımı önerme mantığı ve yüklem mantığı gibi birinci dereceden mantık. Bu bağlamlarda bir formül, bir semboller dizisidir φ, bunun için "φ doğru mu?" Diye sormak mantıklıdır. serbest değişkenler in φ somutlaştırılmıştır. Biçimsel mantıkta, kanıtlar belirli özelliklere sahip formül dizileri ile temsil edilebilir ve dizideki son formül kanıtlanmıştır.

"Formül" terimi yazılı işaretler için kullanılabilse de (örneğin, bir kağıt parçası veya kara tahta üzerinde), daha kesin olarak, işaretlerin bir jeton formül örneği. Böylece aynı formül birden fazla yazılabilir ve bir formül ilke olarak o kadar uzun olabilir ki fiziksel evren içinde yazılamaz.

Formüllerin kendileri sözdizimsel nesnelerdir. Yorumlarla anlamlandırılırlar. Örneğin, bir önermesel formülde, her önermesel değişken somut bir önerme olarak yorumlanabilir, böylece genel formül bu önermeler arasındaki bir ilişkiyi ifade eder. Bununla birlikte, bir formülün yalnızca bir formül olarak değerlendirilmesi için yorumlanmasına gerek yoktur.

Önerme hesabı

Formülleri önermeler hesabı, olarak da adlandırılır önerme formülleri,^[2] gibi ifadeler ${ displaystyle (A arazi (B lor C))}$. Tanımları, keyfi bir set seçimi ile başlar. V nın-nin önerme değişkenleri. Alfabe aşağıdaki harflerden oluşur V sembolleriyle birlikte önerme bağlaçları ve parantezler "(" ve ")", bunların hepsinin içinde olmadığı varsayılır V. Formüller, bu alfabe üzerinde belirli ifadeler (yani sembol dizileri) olacaktır.

Formüller endüktif olarak aşağıdaki gibi tanımlanmıştır:

• Her önerme değişkeni kendi başına bir formüldür.
• Eğer a bir formülse, o zaman ¬φ bir formüldür.
• Φ ve ψ formülse ve • herhangi bir ikili bağlayıcıysa, (φ • ψ) bir formüldür. Burada • olağan operatörler ∨, ∧, → veya ↔ olabilir (ancak bunlarla sınırlı değildir).

Bu tanım aynı zamanda resmi bir gramer olarak da yazılabilir. Backus-Naur formu değişken kümesinin sonlu olması koşuluyla:

<alfa seti> ::= p | q | r | s | t | u | ... (keyfi sonlu önermesel değişkenler kümesi)<form> ::= <alfa seti> | ¬<form> | (<form>∧<form>) | (<form>∨<form>) | (<form>→<form>) | (<form>↔<form>)

Bu dilbilgisini kullanarak, sembollerin sırası

(((p → q) ∧ (r → s)) ∨ (¬q ∧ ¬s))

bir formüldür, çünkü dilbilgisi açısından doğrudur. Sembol dizisi

((p → q)→(qq))p))

bir formül değildir, çünkü dilbilgisine uymamaktadır.

Örneğin parantezlerin çoğalması nedeniyle karmaşık bir formülün okunması zor olabilir. Bu son fenomeni hafifletmek için, öncelik kuralları (benzer şekilde standart matematiksel işlem sırası ) operatörler arasında varsayılır ve bazı operatörleri diğerlerinden daha bağlayıcı hale getirir. Örneğin, önceliği varsayarak (en çok bağlayıcıdan en az bağlayıcıya) 1. ¬ 2. → 3. ∧ 4. ∨. Sonra formül

(((p → q) ∧ (r → s)) ∨ (¬q ∧ ¬s))

olarak kısaltılabilir

p → q ∧ r → s ∨ ¬q ∧ ¬s

Ancak bu, yalnızca bir formülün yazılı temsilini basitleştirmek için kullanılan bir sözleşmedir. Örneğin, önceliğin aşağıdaki sırayla sol-sağ ilişkisel olduğu varsayılsaydı: 1. ¬ 2. ∧ 3. ∨ 4. →, o zaman yukarıdaki aynı formül (parantez olmadan) şu şekilde yeniden yazılırdı:

(p → (q ∧ r)) → (s ∨ ((¬q) ∧ (¬s)))

Yüklem mantığı

Bir formülün tanımı birinci dereceden mantık ${ displaystyle { mathcal {QS}}}$ göreceli imza eldeki teorinin. Bu imza, eldeki teorinin sabit sembollerini, yüklem sembollerini ve fonksiyon sembollerini, topraklar fonksiyon ve yüklem sembolleri.

Bir formülün tanımı birkaç bölümden oluşur. İlk olarak, dizi şartlar özyinelemeli olarak tanımlanır. Gayri resmi terimler, nesnelerin nesnelerini temsil eden ifadelerdir. söylem alanı.

1. Herhangi bir değişken bir terimdir.
2. İmzadaki herhangi bir sabit sembol bir terimdir
3. formun bir ifadesi f(t₁,...,t_n), nerede f bir n-ary işlev sembolü ve t₁,...,t_n terimlerdir, yine bir terimdir.

Bir sonraki adım, atomik formüller.

1. Eğer t₁ ve t₂ o zaman şartlar t₁=t₂ atomik bir formül
2. Eğer R bir n-ary yüklem sembolü ve t₁,...,t_n şartlar, öyleyse R(t₁,...,t_n) atomik bir formüldür

Son olarak, formül kümesi, aşağıdakilerin geçerli olacağı şekilde atomik formül kümesini içeren en küçük küme olarak tanımlanır:

1. ${ displaystyle neg phi}$ ne zaman bir formül ${ displaystyle phi}$ bir formül
2. ${ displaystyle ( phi land psi)}$ ve ${ displaystyle ( phi lor psi)}$ formüller ne zaman ${ displaystyle phi}$ ve ${ displaystyle psi}$ formüllerdir;
3. ${ displaystyle var x , phi}$ ne zaman bir formül ${ displaystyle x}$ bir değişkendir ve ${ displaystyle phi}$ bir formüldür;
4. ${ displaystyle forall x , phi}$ ne zaman bir formül ${ displaystyle x}$ bir değişkendir ve ${ displaystyle phi}$ bir formüldür (alternatif olarak, ${ displaystyle forall x , phi}$ kısaltma olarak tanımlanabilir ${ displaystyle neg var x , neg phi}$).

Bir formülde herhangi bir oluşum yoksa ${ displaystyle var x}$ veya ${ displaystyle forall x}$, herhangi bir değişken için ${ displaystyle x}$, sonra denir niceleyici içermeyen. Bir varoluşsal formül bir dizi ile başlayan bir formüldür varoluşsal niceleme ardından nicelik belirteci içermeyen bir formül.

Atomik ve açık formüller

Bir atomik formül hayır içeren bir formül mantıksal bağlantılar ne de niceleyiciler veya eşdeğer olarak katı alt formülleri olmayan bir formül. Atomik formüllerin kesin biçimi, söz konusu resmi sisteme bağlıdır; için önerme mantığı örneğin, atomik formüller önerme değişkenleri. İçin yüklem mantığı atomlar, argümanları ile birlikte yüklem sembolleridir, her argüman bir dönem.

Bazı terminolojiye göre, bir açık formül yalnızca mantıksal bağlayıcılar kullanılarak atomik formüllerin nicelik belirteçleri hariç tutularak birleştirilmesiyle oluşturulur.^[3] Bu, kapalı olmayan bir formülle karıştırılmamalıdır.

Kapalı formüller

Bir kapalı formül, Ayrıca zemin formül veya cümle, hiçbir şeyin olmadığı bir formül ücretsiz oluşumlar herhangi bir değişken. Eğer Bir değişkenlerin bulunduğu birinci dereceden bir dilin formülüdür v₁, ..., v_n ücretsiz oluşum var, o zaman Bir öncesinde ${ displaystyle forall}$v₁ ... ${ displaystyle forall}$v_n kapanışı Bir.

Formüller için geçerli özellikler

• Bir formül Bir bir dilde ${ displaystyle { mathcal {Q}}}$ dır-dir geçerli herkes için doğruysa yorumlama nın-nin ${ displaystyle { mathcal {Q}}}$.
• Bir formül Bir bir dilde ${ displaystyle { mathcal {Q}}}$ dır-dir tatmin edici bazıları için doğruysa yorumlama nın-nin ${ displaystyle { mathcal {Q}}}$.
• Bir formül Bir dilinin aritmetik dır-dir karar verilebilir eğer bir karar verilebilir set yani eğer varsa etkili yöntem verilen bir ikame serbest değişkenlerin Bir, sonuçta ortaya çıkan Bir kanıtlanabilir ya da olumsuzluğu.

Terminolojinin kullanımı

Matematiksel mantık üzerine daha önceki çalışmalarda (örneğin, Kilise^[4]), herhangi bir sembol dizisine atıfta bulunan formüller ve bu dizeler arasında iyi biçimlendirilmiş formüller, (doğru) formüllerin oluşum kurallarını izleyen dizelerdi.

Birkaç yazar basitçe formül diyor.^[5][6][7][8] Modern kullanımlar (özellikle bilgisayar bilimi bağlamında matematiksel yazılımlar gibi model dama, otomatik teorem kanıtlayıcılar, etkileşimli teorem kanıtlayıcılar ) formül kavramını sadece cebirsel kavramı muhafaza etme ve sorusunu bırakma eğilimindedir. iyi biçimlilik, yani formüllerin somut dizgi gösterimi (bunu veya bu simgeyi bağlayıcılar ve niceleyiciler için kullanarak, bunu veya bunu kullanarak parantezleme kuralı, kullanma Lehçe veya infix notasyon, vb.) sadece notasyonel bir problem olarak.

İfade ederken iyi biçimlendirilmiş formül hala kullanımda,^[9][10][11] bu yazarlar mutlaka^{[Gelincik kelimeler ]} eski anlamının tersine kullanın formülartık matematiksel mantıkta yaygın olmayan.^{[kaynak belirtilmeli ]}

"İyi biçimlendirilmiş formüller" (WFF) ifadesi de popüler kültüre sızdı. WFF akademik oyun adına kullanılan ezoterik kelime oyunlarının bir parçasıdır "WFF 'N PROOF: The Game of Modern Logic, "Layman Allen,^[12] o oradayken gelişti Yale Hukuk Fakültesi (o daha sonra bir profesördü Michigan üniversitesi ). Oyun grubu, çocuklara sembolik mantık ilkelerini öğretmek için tasarlanmıştır. Lehçe notasyonu ).^[13] Onun adı bir yankıdır whiffenpoof, bir saçma kelime olarak kullanılan tezahürat -de Yale Üniversitesi popüler yaptı Whiffenpoof Şarkısı ve Whiffenpoofs.^[14]

Ayrıca bakınız

• Zemin ifadesi

Notlar

Referanslar

• Allen, Layman E. (1965), "WFF 'N PROOF Games tarafından Matematiksel Mantığın Autotelic Öğrenimine Doğru", Matematiksel Öğrenme: Sosyal Bilimler Araştırma Konseyi Fikri Süreçler Araştırma Komitesi tarafından Desteklenen Bir Konferans Raporu, Çocuk Gelişimi Araştırma Derneği Monografileri, 30 (1): 29–41
• Boolos, George; Burgess, John; Jeffrey, Richard (2002), Hesaplanabilirlik ve Mantık (4. baskı), Cambridge University Press, ISBN  978-0-521-00758-0
• Ehrenberg, Rachel (Bahar 2002). "Olumlu Mantıklı". Michigan Bugün. Michigan üniversitesi. Arşivlenen orijinal 2009-02-08 tarihinde. Alındı 2007-08-19.
• Enderton Herbert (2001), Mantığa matematiksel bir giriş (2. baskı), Boston, MA: Akademik Basın, ISBN  978-0-12-238452-3
• Gamut, L.T.F. (1990), Mantık, Dil ve Anlam, Cilt 1: Mantığa Giriş, Chicago Press Üniversitesi, ISBN  0-226-28085-3
• Hodges, Wilfrid (2001), "Classical Logic I: First-Order Logic", Goble'da, Lou (ed.), Blackwell Felsefi Mantık Rehberi, Blackwell, ISBN  978-0-631-20692-7
• Hofstadter, Douglas (1980), Gödel, Escher, Bach: Ebedi Altın Örgü, Penguin Books, ISBN  978-0-14-005579-5
• Kleene, Stephen Cole (2002) [1967], Matematiksel mantık, New York: Dover Yayınları, ISBN  978-0-486-42533-7, BAY  1950307
• Rautenberg, Wolfgang (2010), Matematiksel Mantığa Kısa Bir Giriş (3. baskı), New York: Springer Science + Business Media, doi:10.1007/978-1-4419-1221-3, ISBN  978-1-4419-1220-6

Dış bağlantılar

• Birinci Derece Dayanak Mantık için İyi Biçimlendirilmiş Formül - kısa içerir Java sınav.
• ProvenMath'te İyi Biçimlendirilmiş Formül