Terim (mantık) - Term (logic)

Olarak matematiksel mantık , bir terim bir süre matematiksel bir nesne anlamına gelmektedir , formül matematiksel gerçeği belirtmektedir. Özellikle, terimler bir formülün bileşenleri olarak görünür. Bu, bir isim öbeğinin bir nesneye atıfta bulunduğu ve tüm bir cümlenin bir gerçeğe atıfta bulunduğu doğal dile benzer .

Bir birinci dereceden terim yinelemeli inşa sabit semboller, gelen değişken ve fonksiyon sembolleri . Uygun sayıda terime bir yüklem sembolü uygulanarak oluşturulan bir ifadeye atomik formül denir ve yorum verildiğinde iki değerli mantıkta doğru veya yanlış olarak değerlendirilir . Örneğin, 1 sabiti, $x$ değişkeni ve ikili işlev sembollerinden ve ; $x'in$ her gerçek sayılı değeri için doğru olarak değerlendirilen atom formülünün bir parçasıdır . ${\ Displaystyle (x+1)*(x+1)}$ ${\görüntüleme stili +}$ ${\görüntüleme stili *}$ $(x+1)*(x+1)\geq 0$

İçinde yanında mantık , terimler önemli roller oynamaktadır evrensel cebir ve yeniden yazma sistemleri .

Resmi tanımlama

( n ⋅( n +1)/2 ve n ⋅(( n +1)/2) terimlerinin ağaç yapısı

Verilen bir dizi V değişken sembol, bir dizi bir C sabiti sembollerin ve ayarlar F _{, n} ve n, her bir doğal sayı için, -ary fonksiyon sembolleri olarak da adlandırılan operatör sembolleri n ≥ 1, grubu (ayrıştırılmamış birinci dereceden) terimleri , T ise aşağıdaki özelliklere sahip en küçük küme olarak özyinelemeli olarak tanımlanmıştır :

her değişken sembol bir terimdir: V ⊆ T ,
her sabit sembol bir terimdir: C ⊆ T ,
Her gelen n terimleri t ₁ , ..., t _n ve her n -ary fonksiyon sembolü f ∈ F _n , daha büyük bir terim f ( t ₁ , ..., t _{, n} ) inşa edilebilir.

Sezgisel, sözde gramer gösterimi kullanılarak, bu bazen şöyle yazılır: t ::= x | c | f ( t ₁ , ..., t _{, n} ). Genellikle, yalnızca ilk birkaç işlev simgesi kümesi F _n'de bulunur. İyi bilinen örnekler tek terimli fonksiyon semboller sin , cos ∈ F ₁ ve ikili fonksiyon sembolleri +, -, ⋅, / ∈ F ₂ iken, üçlü işlemleri daha az bilinmektedir, yüksek Arity dursun fonksiyonları. Birçok yazar sabit sembolleri 0-ary fonksiyon sembolleri F _{0 olarak kabul eder} , bu nedenle onlar için özel bir sözdizimsel sınıfa ihtiyaç duymazlar.

Bir terim , söylem alanından matematiksel bir nesneyi belirtir . Sabit bir c , bu etki, değişken adlandırılmış nesneyi belirtmektedir X bu etki nesneler üzerinde aralıkları ve bir n- -ary fonksiyonu f haritalar N - küpe nesnelerin nesnelerin. Örneğin, eğer, n, ∈ V değişken sembol, 1 ∈ Cı sabit bir sembolüdür ve ekleme ∈ F ₂ , daha sonra, bir ikili işlev sembolü , n ∈ T , 1 ∈ T , (bu nedenle) eklenti ( n , 1) ∈ T sırasıyla birinci, ikinci ve üçüncü dönem oluşturma kuralına göre. İkinci terim genellikle , kolaylık olması için ek notasyonu ve daha yaygın operatör sembolü + kullanılarak n +1 olarak yazılır .

Dönem yapısı ve temsil

Başlangıçta, mantıkçılar bir terimi , belirli yapı kurallarına bağlı kalan bir karakter dizisi olarak tanımladılar . Ancak ağaç kavramı bilgisayar bilimlerinde popüler hale geldiğinden, bir terimi ağaç olarak düşünmek daha uygun hale geldi. Örneğin, " $(n \cdot(n +1)/2$ ", " $((n \cdot(n +1)))/2$ " ve " " gibi birkaç farklı karakter dizisi aynı terimi belirtir ve aynı ağaç, yani. Yukarıdaki resimde sol ağaç. Bir terimin ağaç yapısını kağıt üzerindeki grafik temsilinden ayırarak, parantezleri (yapı değil, yalnızca temsildir) ve görünmez çarpma operatörlerini (temsilde değil, yalnızca yapıda mevcuttur) hesaba katmak da kolaydır. ${\frac {n(n+1)}{2}}$

yapısal eşitlik

Aynı ağaca karşılık geliyorlarsa , iki terimin yapısal , kelimenin tam anlamıyla veya sözdizimsel olarak eşit olduğu söylenir . Örneğin, sol ve yukarıdaki resimde sağ ağaç yapısal olan un onlar "olarak kabul edilmekle beraber, eşit terimler semantik eşit hep aynı değere değerlendirirken" rasyonel aritmetik . Sembollerin anlamı hakkında herhangi bir bilgi olmadan yapısal eşitlik kontrol edilebilirken, anlamsal eşitlik kontrol edilemez. Eğer / fonksiyonu örneğin rasyonel olarak değil de tamsayılı bölme olarak yorumlanırsa , o zaman n =2'de sol ve sağ terim sırasıyla 3 ve 2 olarak değerlendirilir. Yapısal eşit terimlerin değişken adlarında uyuşması gerekir.

Bunun aksine, bir terim t denen adlandırma ya da bir varyantının bir terimin, U sürekli, yani eğer önceki tüm değişkenler adlandırma sonucu ikinci eğer U = tσ bazı adlandırma ikame σ. Bu durumda, u da t'nin yeniden adlandırılmasıdır , çünkü yeniden adlandırma ikamesi σ, ters σ ^-1 ve t = uσ ^{-1'e sahiptir} . Her iki terimin de eşit modulo yeniden adlandırma olduğu söylenir . Birçok bağlamda, bir terimdeki belirli değişken adları önemli değildir, örneğin toplama için değişmelilik aksiyomu x + y = y + x veya a + b = b + a olarak ifade edilebilir ; bu gibi durumlarda formülün tamamı yeniden adlandırılabilirken, keyfi bir alt terim genellikle olmayabilir, örneğin x + y = b + a , değişme aksiyomunun geçerli bir versiyonu değildir.

Zemin ve lineer terimler

Bir dönem değişkenler grubu t ile gösterilir değişkenler ( t ). Herhangi bir değişken içermeyen terime temel terim denir ; Bir değişkenin birden çok örneğini içermeyen bir terime doğrusal terim denir . Örneğin, 2+2 bir temel terimdir ve dolayısıyla aynı zamanda lineer bir terimdir, x ⋅( n +1) lineer bir terimdir, n ⋅( n +1) lineer olmayan bir terimdir. Bu özellikler, örneğin terimin yeniden yazılmasında önemlidir .

Fonksiyon sembolleri için bir imza verildiğinde , tüm terimlerin kümesi serbest terim cebiri oluşturur . Tüm temel terimlerin kümesi, ilk terim cebiri oluşturur .

Gibi kontrol sayısını kısaltarak f _{, 0} ve sayısı ı olarak -ary fonksiyon sembolleri f _i , sayı θ _saat için bir yüksekliğe kadar belirgin zemin terimleri saat , aşağıdaki yineleme formül ile hesaplanır:

θ ₀ = f ₀ , yükseklik 0 olan bir zemin terimi yalnızca bir sabit olabileceğinden,
$\theta _{h+1}=\sum _{i=0}^{\infty}f_{i}\cdot \theta _{h}^{i}$ , çünkü h +1'e kadar olan bir yükseklik zemin terimi, bir i -ary kök fonksiyon sembolü kullanılarak h'ye kadar olan herhangi bir i temel yükseklik terimi oluşturularak elde edilebilir . Yalnızca sonlu sayıda sabit ve fonksiyon sembolü varsa, genellikle böyle olan toplamın sonlu bir değeri vardır.

Terimlerden formüller oluşturma

Verilen bir dizi R _{, n} ve n, her bir doğal sayı -ary ilişki semboller n ≥ 1, bir (ayrıştırılmamış birinci dereceden) Atomik formülün bir uygulanarak elde edilir , n için -ary ilişki sembolü N açısından. Fonksiyon sembollerine gelince, bir ilişki sembol seti R _n genellikle sadece küçük n için boş değildir . Matematiksel mantıkta, mantıksal bağlaçlar ve niceleyiciler kullanılarak atomik formüllerden daha karmaşık formüller oluşturulur . Örneğin , ∀ x : x ∈ ⇒ ( x +1)⋅( x +1) ≥ 0 gerçek sayılar kümesini göstermeye izin vermek , karmaşık sayılar cebirinde doğru olarak değerlendirilen bir matematiksel formüldür . Bir atom formülü, tamamen temel terimlerden oluşturulmuşsa, temel olarak adlandırılır; belirli bir fonksiyon ve yüklem sembolleri setinden oluşturulabilen tüm temel atom formülleri , bu sembol setleri için Herbrand tabanını oluşturur. $\mathbb {R}$ $\mathbb {R}$

Şartlı işlemler

Mavi redex ile siyah örnek terimin ağaç yapısı

{\frac {a*((a+1)*(a+2))}{1*(2*3)}}

{\görüntüleme stili x*(y*z)}

Bir terim bir ağaç hiyerarşisi yapısına sahip olduğundan, düğümlerinin her birine bir konum veya yol , yani düğümün hiyerarşideki yerini gösteren bir doğal sayılar dizisi atanabilir. Genellikle ε ile gösterilen boş dize, kök düğüme atanır. Siyah terim içindeki pozisyon dizeleri resimde kırmızı ile gösterilmiştir.
Her pozisyonda p bir dönem t , benzersiz subterm yaygın ile gösterilir başlar, $t | s$ . Örneğin, resimdeki siyah terimin 122 konumunda, a +2 alt teriminin kökü vardır. İlişkisi "bir subterm olan" a, kısmi sıralama açısından setinde; öyle dönüşlü her terim trivially kendi başına bir subterm olduğundan.
Bir t teriminde, p konumundaki alt terimin yeni bir u terimiyle değiştirilmesiyle elde edilen terim , genel olarak $t$ $[$ $u$ $]$ $p ile gösterilir$ . $t$ $[$ $u$ $]$ $p$ terimi , aynı zamanda, u teriminin, $t$ $[.]$ terimine benzer bir nesneyle genelleştirilmiş bir şekilde birleştirilmesinin sonucu olarak da görülebilir ; ikincisine bağlam veya boşluklu bir terim ("." ile gösterilir; konumu p'dir ), u'nun gömülü olduğu söylenir . Örneğin , resimdeki siyah terim t ise, o zaman $t$ $[$ $b$ $+1]$ $12$ terimi ile sonuçlanır . İkinci terim ayrıca, $b$ $+1$ teriminin bağlama dahil edilmesinden kaynaklanır . Gayri resmi anlamda, somutlaştırma ve gömme işlemleri birbiriyle ters orantılıdır: ilki terimin altına işlev sembolleri eklerken, ikincisi bunları en üste ekler. Encompassment sipariş bir terim ve her iki tarafta da ekler arasında herhangi bir sonuç ile ilgilidir. ${\frac {a*(b+1)}{1*(2*3)}}$ ${\frac {a*(\;.\;)}}$
Bir terimin her düğümüne, derinliği ( bazı yazarlar tarafından yükseklik olarak adlandırılır ) atanabilir, yani kökten uzaklığı (kenar sayısı). Bu ayarda, bir düğümün derinliği her zaman konum dizisinin uzunluğuna eşittir. Resimde siyah terimdeki derinlik seviyeleri yeşil ile belirtilmiştir.
Boyutu , bir terimin ortak olarak parantez olmayan semboller sayımı, dönem yazılı temsil uzunluğuna, eşit olarak, düğümlerinin sayısını ifade eder, ya da. Resimdeki siyah ve mavi terim sırasıyla 15 ve 5 boyutundadır.
Bir terim u maçları bir terim t bir ikame örneği ise, u yapısal bir subterm eşittir t eğer resmen ya $u σ = t | p$ bir pozisyon için p de t ve bazı ikame σ. Bu durumda, u , t ve σ sırasıyla model terimi , özne terimi ve eşleşen ikame olarak adlandırılır. Resimde, mavi kalıp terimi , 1. konumdaki siyah özne terimiyle eşleşir ve eşleşen ikame ${$ $x$ $\mapsto$ $a$ $,$ $y$ $\mapsto$ $a$ $+1, z \mapsto$ $a$ $+2 }$ mavi değişkenler tarafından hemen siyah ikamelerine bırakılır. Sezgisel olarak, örüntü, değişkenleri dışında öznede yer almalıdır; desende bir değişken birden çok kez meydana gelirse, öznenin ilgili konumlarında eşit alt terimler gerekir. ${\görüntüleme stili x*(y*z)}$
birleştirici terimler
terim yeniden yazma

Ilgili kavramlar

Sıralanmış terimler

Söylem alanı temelde farklı türden öğeler içerdiğinde, tüm terimler kümesini buna göre bölmek yararlıdır. Bu amaçla, her değişkene ve her sabit sembole bir sıralama (bazen type olarak da adlandırılır ) atanır ve her işlev sembolüne bir etki alanı sıralama ve aralık sıralama bildirimi atanır. Bir sıralı süreli f ( t ₁ , ..., t _{, n} ) sıralı alt terimler den oluşabilir t ₁ , ..., t _{, n} sadece $i$ inci subterm bir nevi ilan maçları $i$ inci alanı çeşit f . Böyle bir terim aynı zamanda iyi sıralanmış olarak da adlandırılır ; diğer herhangi bir terime ( yalnızca sıralanmamış kurallara uymak ) kötü sıralanmış denir .

Örneğin, bir vektör uzayı , ilişkili bir skaler sayı alanıyla birlikte gelir . Let B ve N , sırasıyla vektörler ve sayılar tür ifade izin V _W ve V _{, N} , sırasıyla vektör ve sayı değişkenleri grubu olabilir ve Cı- _B ve C _{, N} , sırasıyla vektör ve sayı sabitleri grubu. Daha sonra örn. ve $0 \in$ $C$ $N$ ve vektör toplama, skaler çarpma ve iç çarpım sırasıyla , ve olarak bildirilir . Değişken sembolleri ve $a$ $,$ $b$ $\in$ $V$ $N$ varsayıldığında , terim iyi sıralanmıştır, oysa değildir (çünkü +, 2. argüman olarak N sıralamalı bir terimi kabul etmez ). İyi sıralanmış bir terim yapmak için ek bir beyan gereklidir. Birkaç bildirimi olan fonksiyon sembollerine aşırı yüklenmiş denir . ${\vec {0}}\C_{W}$ $+:W\times W\to W,*:W\times N\toW$ $\langle .,.\rangle :W\times W\to N$ ${\vec {v}},{\vec {w}}\in V_{W}$ $\langle ({\vec {v}}+{\vec {0}})*a,{\vec {w}}*b\rangle$ ${\vec {v}}+a$ $a*{\vec {v}}$ ${\görüntüleme stili *:N\kez W\to W}$

Burada açıklanan çok sıralı çerçevenin uzantıları da dahil olmak üzere daha fazla bilgi için çok sıralı mantığa bakın .

Lambda terimleri

Bağlı değişkenli terimler
Notasyon örneği	bağlı değişkenler	Serbest değişkenler	lambda terimi olarak yazıldı
$lim n \to\infty x / n$	n	x	sınırı (λ n . div ( x , n ))
$\sum _{i=1}^{n}i^{2}$	ben	n	toplam (1, n ,λ i . güç ( ben ,2))
$\int _{a}^{b}\sin(k\cdot t)dt$	T	bir , b , k	integral ( a , b ,λ t . sin ( k ⋅ t ))

Motivasyon

Tabloda gösterildiği gibi matematiksel gösterimler, yukarıda tanımlandığı gibi birinci dereceden bir terim şemasına uymaz , çünkü bunların tümü , gösterimin kapsamı dışında görünmeyebilecek kendi yerel veya bağlı bir değişkeni tanıtırlar , örn. anlamlı değildir. . Buna karşılık, free olarak adlandırılan diğer değişkenler, sıradan birinci dereceden terim değişkenleri gibi davranır, örneğin anlamlıdır. $t\cdot \int _{a}^{b}\sin(k\cdot t)\;dt$ $k\cdot \int _{a}^{b}\sin(k\cdot t)\;dt$

Tüm bu operatörler, argümanlarından biri olarak bir değer terimi yerine bir fonksiyon alıyor olarak görülebilir. Örneğin, lim operatörü bir diziye, yani pozitif tam sayıdan örneğin gerçek sayılara bir eşlemeye uygulanır. Başka bir örnek olarak, tablodaki ikinci örneği uygulayan bir C işlevi, Σ, bir işlev işaretçi argümanına sahip olacaktır (aşağıdaki kutuya bakın).

Lambda terimleri , lim , Σ, ∫ vb.için bağımsız değişkenler olarak sağlanacak anonim işlevleri belirtmek için kullanılabilir.

Örneğin, aşağıdaki C programından kare işlevi, adsız olarak bir lambda terimi λ i olarak yazılabilir . ben ² . Genel toplam operatörü Σ daha sonra bir alt sınır değeri, bir üst sınır değeri ve toplanacak bir fonksiyon alan üçlü bir fonksiyon sembolü olarak düşünülebilir. İkinci argümanı nedeniyle, Σ operatörü, ikinci dereceden bir fonksiyon sembolü olarak adlandırılır . Başka bir örnek olarak, lambda terimi λ n . x / n eşleştiren bir fonksiyon anlamına gelir, 1, 2, 3, ... için x / 1, x / 2, X / 3, ..., sırasıyla olduğuna göre, gösterir sekansı ( x / 1, x / 2, x /3, ...). Lim operatörü bu tür bir sekans alır ve (tanımlanmışsa) sınırına döndürür.

Tablonun en sağdaki sütunu, her bir matematiksel gösterim örneğinin bir lambda terimiyle nasıl temsil edilebileceğini gösterir ve ayrıca ortak infix operatörlerini önek formuna dönüştürür .

int sum(int lwb, int upb, int fct(int)) {    // implements general sum operator
    int res = 0;
    for (int i=lwb; i<=upb; ++i)
        res += fct(i);
    return res;
}

int square(int i) { return i*i; }            // implements anonymous function (lambda i. i*i); however, C requires a name for it

#include <stdio.h>
int main(void) {
    int n;
    scanf(" %d",&n);
    printf("%d\n", sum(1, n, square));        // applies sum operator to sum up squares
    return 0;
}

Tanım

Ayrıca bakınız

Notlar

Referanslar

Franz Baader ; Tobias Nipkov (1999). Terim Yeniden Yazma ve Hepsi . Cambridge Üniversitesi Yayınları. s. 1-2 ve 34-35. ISBN'si 978-0-521-77920-3.

Languages

In other projects