b'\n_START_ARTICLE_\nL\xc3\xb3gica combinat\xc3\xb3ria\n_START_PARAGRAPH_\nL\xc3\xb3gica combinat\xc3\xb3ria \xc3\xa9 uma nota\xc3\xa7\xc3\xa3o introduzida por Moses Sch\xc3\xb6nfinkel e Haskell Curry para eliminar a necessidade de vari\xc3\xa1veis em l\xc3\xb3gica matem\xc3\xa1tica. Vem sendo mais usada recentemente na ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o como um modelo de computa\xc3\xa7\xc3\xa3o e como base para o desenvolvimento de linguagens de programa\xc3\xa7\xc3\xa3o funcionais. Ela \xc3\xa9 baseada em combinadores, fun\xc3\xa7\xc3\xb5es de ordem superior somente usam aplica\xc3\xa7\xc3\xb5es de fun\xc3\xa7\xc3\xb5es e outros combinadores para definir um resultado a partir de seus par\xc3\xa2metros.\n_START_SECTION_\nMatem\xc3\xa1tica\n_START_PARAGRAPH_\nA l\xc3\xb3gica combinat\xc3\xb3ria visava originalmente servir como uma "pr\xc3\xa9-l\xc3\xb3gica" que clarificasse o papel das vari\xc3\xa1veis quantificadas na l\xc3\xb3gica, eliminando-as do processo. Inventor original da l\xc3\xb3gica combinat\xc3\xb3ria, Moses Sch\xc3\xb6nfinkel n\xc3\xa3o publicou nada mais sobre o assunto ap\xc3\xb3s seu artigo original de 1924, e parou de publicar ap\xc3\xb3s a consolida\xc3\xa7\xc3\xa3o do poder de Stalin em 1929. Haskell Curry redescobriu os combinadores enquanto trabalhava como instrutor na Universidade de Princeton no final de 1927. No final da d\xc3\xa9cada de 1930, Alonzo Church e seus estudantes da Princeton inventaram um formalismo rival para a abstra\xc3\xa7\xc3\xa3o funcional, o c\xc3\xa1lculo lambda, que se tornou mais popular que a l\xc3\xb3gica combinat\xc3\xb3ria. At\xc3\xa9 que a ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o tomasse interesse no assunto entre as d\xc3\xa9cadas de 1960 e 1970, quase todo o trabalho no assunto foi publicado por Curry e seus estudantes, ou por Robert Feys na B\xc3\xa9lgica. Curry e Feys (1958) e Curry et al. (1972) tra\xc3\xa7aram os prim\xc3\xb3rdios dessa nota\xc3\xa7\xc3\xa3o.\n_START_SECTION_\nCi\xc3\xaancia da computa\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nNa ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o, a l\xc3\xb3gica combinat\xc3\xb3ria \xc3\xa9 usada como um modelo simplificado de computa\xc3\xa7\xc3\xa3o, usado na teoria da computabilidade e na teoria da demonstra\xc3\xa7\xc3\xa3o. Apesar de sua simplicidade, ela captura diversos elementos essenciais da computa\xc3\xa7\xc3\xa3o._NEWLINE_A l\xc3\xb3gica combinat\xc3\xb3ria pode ser vista como uma varia\xc3\xa7\xc3\xa3o do c\xc3\xa1lculo lambda, em que as express\xc3\xb5es lambda (representando a abstra\xc3\xa7\xc3\xa3o funcional) s\xc3\xa3o substitu\xc3\xaddas por um conjunto limitado de combinadores, fun\xc3\xa7\xc3\xb5es primitivas sem a presen\xc3\xa7a de vari\xc3\xa1veis livres. \xc3\x89 trivial transformar express\xc3\xb5es lambda em express\xc3\xb5es de combinadores, e a redu\xc3\xa7\xc3\xa3o de combinadores \xc3\xa9 muito mais simples que a de lambda. Portanto, a l\xc3\xb3gica combinat\xc3\xb3ria tem sido usada para modelar algumas linguagens de programa\xc3\xa7\xc3\xa3o funcionais n\xc3\xa3o r\xc3\xadgidas e hardware. A vis\xc3\xa3o mais pura dessa nota\xc3\xa7\xc3\xa3o \xc3\xa9 a linguagem de programa\xc3\xa7\xc3\xa3o Unlambda, cujas \xc3\xbanicas primitivas s\xc3\xa3o os combinadores S e K. Apesar da car\xc3\xaancia de praticidade, a linguagem promove certo interesse te\xc3\xb3rico.\n_START_SECTION_\nC\xc3\xa1lculo combinat\xc3\xb3rio\n_START_PARAGRAPH_\nComo a abstra\xc3\xa7\xc3\xa3o \xc3\xa9 a \xc3\xbanica forma de montagem de fun\xc3\xa7\xc3\xb5es em lambda c\xc3\xa1lculo, deve-se criar um substituto no c\xc3\xa1lculo combinat\xc3\xb3rio. Ao inv\xc3\xa9s de abstra\xc3\xa7\xc3\xa3o, o c\xc3\xa1lculo combinat\xc3\xb3rio prove um conjunto limitado de fun\xc3\xa7\xc3\xb5es a partir das quais outras podem ser constru\xc3\xaddas.\n_START_SECTION_\nRedu\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nCada combinador primitivo possui uma regra de redu\xc3\xa7\xc3\xa3o da forma:_NEWLINE_em que  \xc3\xa9 um termo mencionando somente vari\xc3\xa1veis do conjunto . \xc3\x89 assim que os combinadores primitivos atuam como fun\xc3\xa7\xc3\xb5es.\n_START_SECTION_\nExemplos de combinadores\n_START_PARAGRAPH_\nO exemplo mais simples de combinador \xc3\xa9 , o combinador identidade, definido por  para todos os termos ._NEWLINE_Outro combinador simples \xc3\xa9 , que monta fun\xc3\xa7\xc3\xb5es constantes.  \xc3\xa9 uma fun\xc3\xa7\xc3\xa3o que, para qualquer par\xc3\xa2metro, retorna , de forma que  para todos os termos  e . Ou, a seguinte conven\xc3\xa7\xc3\xa3o para m\xc3\xbaltipla aplica\xc3\xa7\xc3\xa3o: ._NEWLINE_Mais um combinador \xc3\xa9 , uma forma generalizada de aplica\xc3\xa7\xc3\xa3o, de forma que .  aplica  a  ap\xc3\xb3s substituir  em ambos._NEWLINE_Uma caracter\xc3\xadstica interessante \xc3\xa9 que, dados  e ,  pode ser constru\xc3\xaddo da seguinte forma:_NEWLINE_para qualquer termo . Notar que apesar de  para qualquer , . Diz-se que os termos s\xc3\xa3o estencionalimente iguais. Esse conceito captura a no\xc3\xa7\xc3\xa3o matem\xc3\xa1tica de igualidade de fun\xc3\xa7\xc3\xb5es, em que duas fun\xc3\xa7\xc3\xb5es s\xc3\xa3o iguais se elas produzem a mesma sa\xc3\xadda para a mesma entrada. Em contraste, os termos em si, juntos com a redu\xc3\xa7\xc3\xa3o dos combinadoers primitivos, capturam a no\xc3\xa7\xc3\xa3o de igualidade intencional, isto \xc3\xa9, duas fun\xc3\xa7\xc3\xb5es s\xc3\xa3o iguais se e somente se elas possuem implementa\xc3\xa7\xc3\xb5es id\xc3\xaanticas at\xc3\xa9 a expans\xc3\xa3o dos combinadores primitivos, quando estes s\xc3\xa3o aplicados aos par\xc3\xa2metros. H\xc3\xa1 v\xc3\xa1rias formas de implementa\xc3\xa7\xc3\xa3o da fun\xc3\xa7\xc3\xa3o identidade, e entre elas est\xc3\xa3o ,  e . Um combinador mais interessante \xc3\xa9 o combinador de ponto fixo, ou , que pode ser usado para implementar recursividade.\n_START_SECTION_\nExemplo de convers\xc3\xa3o\n_START_PARAGRAPH_\nPor exemplo, pode-se converter o termo lambda  em um combinador:_NEWLINE_Se aplicarmos esse combinador a quaisquer termos  e , reduz-se da seguinte forma:'