Wyrażenia lambda Niech będzie nieskończonym, przeliczalnym zbiorem zmiennych. Wyrażenie lambda definiuje się następująco: Jeżeli to jest wyrażeniem lambda, Jeżeli jest wyrażeniem lambda i to napis jest wyrażeniem lambda, Jeżeli oraz są wyrażeniami lambda, to napis jest wyrażeniem lambda, Wszystkie wyrażenia lambda można utworzyć korzystając z powyższych reguł.
Zbiór wszystkich wyrażeń lambda oznacza się
Wyrażenia lambda rozpatruje się najczęściej jako klasy abstrakcji relacji alfa-konwersji.
Zmienne wolne Zbiór zmiennych wolnych definiuje się następująco:
Logika Użycie wartości liczbowych do oznaczania wartości logicznych może prowadzić do nieścisłości przy operowaniu relacjami na liczbach, dlatego też należy wyraźnie oddzielić logikę od obiektów, na których ona operuje. Z tego powodu oczywistym staje się fakt, że wartości logiczne prawdy i fałszu muszą być elementami skonstruowanymi z wyrażeń tego rachunku.
Wartościami logicznymi nazwiemy funkcje dwuargumentowe, z których jedna zawsze będzie zwracać pierwszy argument, a druga – drugi: (prawda) to (fałsz) to
Teraz chcąc ukonstytuować operacje logiczne stosuje się nasze ustalone wartości tak, by wyniki tych operacji były zgodne z naszymi oczekiwaniami, mamy: (negacja) to (koniunkcja) to (alternatywa) to