Many-sorted logic

Many-sorted logic can reflect formally our intention not to handle the universe as a homogeneous collection of objects, but to partition it in a way that is similar to types in typeful programming. Both functional and assertive "parts of speech" in the language of the logic reflect this typeful partitioning of the universe, even on the syntax level: substitution and argument passing can be done only accordingly, respecting the "sorts".

There are various ways to formalize the intention mentioned above; a many-sorted logic is any package of information which fulfils it. In most cases, the following are given:

The domain of discourse of any structure of that signature is then fragmented into disjoint subsets, one for every sort.

Example

When reasoning about biological organisms, it is useful to distinguish two sorts: and . While a function makes sense, a similar function usually does not. Many-sorted logic allows one to have terms like , but to discard terms like as syntactically ill-formed.

Algebraization

The algebraization of many-sorted logic is explained in an article by Caleiro and Gonçalves,[1] which generalizes abstract algebraic logic to the many-sorted case, but can also be used as introductory material.

Order-sorted logic

Example sort hierarchy

While many-sorted logic requires two distinct sorts to have disjoint universe sets, order-sorted logic allows one sort to be declared a subsort of another sort , usually by writing or similar syntax. In the above biology example, it is desirable to declare

,
,
,
,
,
,

and so on; cf. picture.

Wherever a term of some sort is required, a term of any subsort of may be supplied instead (Liskov substitution principle). For example, assuming a function declaration , and a constant declaration , the term is perfectly valid and has the sort . In order to supply the information that the mother of a dog is a dog in turn, another declaration may be issued; this is called function overloading, similar to overloading in programming languages.

Order-sorted logic can be translated into unsorted logic, using a unary predicate for each sort , and an axiom for each subsort declaration . The reverse approach was successful in automated theorem proving: in 1985, Christoph Walther could solve a then benchmark problem by translating it into order-sorted logic, thereby boiling it down an order of magnitude, as many unary predicates turned into sorts.[2]

In order to incorporate order-sorted logic into a clause-based automated theorem prover, a corresponding order-sorted unification algorithm is necessary, which requires for any two declared sorts their intersection to be declared, too: if and are variables of sort and , respectively, the equation has the solution , where .

Smolka generalized order-sorted logic to allow for parametric polymorphism.[3][4] In his framework, subsort declarations are propagated to complex type expressions. As a programming example, a parametric sort may be declared (with being a type parameter as in a C++ template), and from a subsort declaration the relation is automatically inferred, meaning that each list of integers is also a list of floats.

Schmidt-Schauß generalized order-sorted logic to allow for term declarations.[5] As an example, assuming subsort declarations and , a term declaration like allows to declare a property of integer addition that could not be expressed by ordinary overloading.

See also

References

  1. ^ Carlos Caleiro, Ricardo Gonçalves (2006). "On the algebraization of many-sorted logics". Proc. 18th int. conf. on Recent trends in algebraic development techniques (WADT) (PDF). Springer. pp. 21–36. ISBN 978-3-540-71997-7.
  2. ^ Walther, Christoph (1985). "A Mechanical Solution of Schubert's Steamroller by Many-Sorted Resolution" (PDF). Artif. Intell. 26 (2): 217–224. doi:10.1016/0004-3702(85)90029-3.
  3. ^ Smolka, Gert (Nov 1988). "Logic Programming with Polymorphically Order-Sorted Types". Int. Workshop Algebraic and Logic Programming. LNCS. Vol. 343. Springer. pp. 53–70.
  4. ^ Smolka, Gert (May 1989), Logic Programming over Polymorphically Order-Sorted Types (Ph.D. thesis), University of Kaiserslautern-Landau, Germany
  5. ^ Schmidt-Schauß, Manfred (Apr 1988). Computational Aspects of an Order-Sorted Logic with Term Declarations. LNAI. Vol. 395. Springer.

Early papers on many-sorted logic include:

Read other articles:

This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: it contains multiple grammatical and syntactic errors. Relevant discussion may be found on the talk page. Please help improve this article if you can. (February 2017) (Learn how and when to remove this template message) 24°25′01″N 120°40′59″E / 24.416829°N 120.683044°E / 24.416829; 120.683044 Urban townshipYuanli Township苑裡鎮 EnriUrban townshipOld town of Y...

 

De Keyserlei De Keyserlei in 2011 Geografische informatie Locatie       Antwerpen Begin Koningin Astridplein Eind Teniersplaats/Meir Algemene informatie Bestrating asfalt De Keyserlei tussen 1905 en 1914 De Keyserlei (vaak ook gewoon Keyserlei genoemd) is een straat in het centrum van de Belgische stad Antwerpen. Deze (De) Keyserlei verbindt het station Antwerpen Centraal (Pelikaanstraat) met de Teniersplaats en de Leien (Frankrijklei). Aan deze brede winkelstraa...

 

Крін Krien —  громада  — Вид Крін Координати: 53°50′ пн. ш. 13°27′ сх. д. / 53.833° пн. ш. 13.450° сх. д. / 53.833; 13.450 Країна  Німеччина Земля Мекленбург-Передня Померанія Район Передня Померанія-Грайфсвальд Об'єднання громад Анклам-Ланд П...

Luis de Nevers Información personalNacimiento 1272 Fallecimiento 22 de julio de 1322jul. París (Reino de Francia) Sepultura Couvent des Cordeliers FamiliaFamilia Casa de Dampierre Padres Roberto III de Flandes Yolanda de Borgoña Cónyuge Joan, Countess of Rethel (desde 1290) Hijos Juana de FlandesLuis I de Flandes Información profesionalOcupación Aristócrata Escudo [editar datos en Wikidata] Luis I (1272-22 de julio de 1322) fue conde de Nevers suo iure y conde de Rethel ...

 

In July and August 2018, South Africa A cricket team visited India to play two first-class matches against India A. India A won the two-match series 1–0. They were joined by India B and Australia A cricket team for a List-A Quadrangular Series in August. India-B defeated Australia-A in the final to win the series. After Quadrangular series, Australia-A played two first-class matches against India A.The two-match series was drawn 1-1.[1] India 'A' vs South Africa 'A' First-Class Seri...

 

Le département du Loiret en rouge sur la carte La liste des édifices labellisés « Patrimoine du XXe siècle » du Loiret recense les édifices protégés au titre du Patrimoine du XXe siècle dans le département français du Loiret en région Centre-Val de Loire. Liste Monument Commune Adresse Coordonnées Notice Protection Date Illustration Centrale électrique de Fay-aux-Loges Fay-aux-Loges Route de Nestin 47° 56′ 14″ nord, 2° 09′ 02″ e...

Проверить информацию.Необходимо проверить точность фактов и достоверность сведений, изложенных в этой статье.На странице обсуждения идёт дискуссия на тему: проверить количественный состав техники, данные устарели в связи с военными действиями в НК. Сухопутные войска А...

 

American comedy-drama TV series ClawsGenre Dark comedy Crime drama Created byEliot LaurenceStarring Niecy Nash Carrie Preston Judy Reyes Karrueche Tran Jenn Lyon Jack Kesy Kevin Rankin Jason Antoon Harold Perrineau Dean Norris Jimmy Jean-Louis Suleka Mathew Evan Daigle ComposerJeff RonaCountry of originUnited StatesOriginal languageEnglishNo. of seasons4No. of episodes40 (list of episodes)ProductionExecutive producers Eliot Laurence Rashida Jones Will McCormack Janine Sherman Barrois Howard D...

 

Village in East Azerbaijan province, Iran Village in East Azerbaijan, IranAwli Persian: اولیVillageAwliCoordinates: 38°33′43″N 46°29′03″E / 38.56194°N 46.48417°E / 38.56194; 46.48417[1]Country IranProvinceEast AzerbaijanCountyVarzaqanDistrictCentralRural DistrictSinaPopulation (2016)[2] • Total495Time zoneUTC+3:30 (IRST) Awli (Persian: اولی, also known as Āblī, Ālbī, and Avli)[3] is a village in Sina...

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Queen Inseong – news · newspapers · books · scholar · JSTOR (November 2022) Queen dowager of Joseon Queen Inseong 인성왕후Queen dowager of JoseonTenure7 August 1545 – 16 January 1578PredecessorQueen Dowager SeongryeolSuccessor Queen Dowager Uise...

 

Biografi ini tidak memiliki sumber tepercaya sehingga isinya tidak dapat dipastikan. Bantu memperbaiki artikel ini dengan menambahkan sumber tepercaya. Materi kontroversial atau trivial yang sumbernya tidak memadai atau tidak bisa dipercaya harus segera dihapus.Cari sumber: M. Shariefuddin – berita · surat kabar · buku · cendekiawan · JSTOR (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) M. Shariefuddin (31 Juli 1932 –...

 

This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (April 2015) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Sri Garden – news · newspapers · books · scholar · JSTOR (May 2010) (Learn how and when t...

1962 film Copacabana Palace Copacabana Palace is an Italian comedy film from 1962, directed by Steno, written by Luciano Vincenzoni, starring Walter Chiari, Mylène Demongeot and Franco Fabrizi.[1][2] Music Antônio Carlos Jobim wrote Samba do Avião for this film, where it was performed by Jula De Palma and I 4 + 4 di Nora Orlandi. The movie was filmed in Rio de Janeiro and features cameo appearances by Jobim, João Gilberto and Os Cariocas.[3] The first performance o...

 

Characterization of the Internet as splintering and dividing Not to be confused with Scatternet. HTTP 403 Forbidden server response to a geo-blocked website https://sss.gov accessed from a Russian internet provider. The splinternet (also referred to as cyber-balkanization or internet balkanization) is a characterization of the Internet as splintering and dividing due to various factors, such as technology, commerce, politics, nationalism, religion, and divergent national interests. Powerful f...

 

Women's football club in London, England This article is about the women's football club based in England. For the men's team, see Arsenal F.C. For other teams called Arsenal, see Arsenal (disambiguation) § Football. Football clubArsenalFull nameArsenal Women Football ClubNickname(s)The GunnersFounded1987; 36 years ago (1987) as Arsenal LadiesGroundMeadow ParkEmirates Stadium (Select home games)Capacity4,500 (1,700 seated)Meadow Park 60,704 (All seated)Emirates Stadium...

Political movement The National Forum Aidgylara (Abkhaz: Аидгылара, Unity) is a socio-political movement in Abkhazia. It was founded during Perestroika as the ethno-nationalist movement representing the Abkhaz people. Aidgylara's founding congress took place on 13 December 1988 in the building of the Abkhazian State Philharmonic Orchestra, where the writer Alexey Gogua was elected its first Chairman.[1] On 18 March 1989, Aidgylara organised the mass gathering at the historica...

 

14,000 Things to Be Happy About AuthorBarbara Ann KipferCountryUnited StatesLanguageEnglishPublisherWorkman PublishingPublication date1990Pages612ISBN978-0-89480-370-3Dewey Decimal031.02 20LC ClassB187.H3 K55 1990 14,000 Things to Be Happy About is a book by Barbara Ann Kipfer. Illustrated by Pierre Le-Tan. It was published in 1990 by Workman Publishing. The book is a list of about 14,000 random and sometimes abstract items, apparently compiled by the author over the course of 20 years. ...

 

В Википедии есть статьи о других людях с такой фамилией, см. Коваленко; Коваленко, Борис. Борис Евгеньевич Коваленко Дата рождения 15 мая 1917(1917-05-15) Место рождения Москва, Российская империя Дата смерти 17 ноября 2000(2000-11-17) (83 года) Место смерти Екатеринбург, Россия Принад...

Brazilian footballer In this Portuguese name, the first or maternal family name is Santos and the second or paternal family name is de Araújo. Nathan Santos Nathan in 2023Personal informationFull name Nathan Santos de AraújoDate of birth (2001-09-05) 5 September 2001 (age 22)Place of birth Rio de Janeiro, BrazilHeight 1.83 m (6 ft 0 in)[1]Position(s) Right-backTeam informationCurrent team Famalicão(on loan from Santos)Number 22Youth career2017 Portuguesa-RJ2...

 

Shootings which occurred on June 8, 2014 This article is about the Las Vegas shooting of 2014. For other uses, see Las Vegas shooting (disambiguation). 2014 Las Vegas shootingsLocationLas Vegas, Nevada, U.S.DateJune 8, 2014; 9 years ago (2014-06-08) 11:22 a.m. – 12:00 p.m.[1] (PDT)TargetPolice officersAttack typeTriple-murder, Murder–suicide, shootout, domestic terrorism[2][failed verification]Weapons M&P 9mm pistol Ruger LCR .38 revolver...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!