Pytania otagowane jako logic

Kombinator Y ma typ . Według korespondencji Curry-Howarda, ponieważ typ ( a → a ) → a jest zamieszkały, musi odpowiadać prawdziwemu twierdzeniu. Jednak a → a jest zawsze prawdziwe, więc wydaje się, że typ kombinatora Y odpowiada twierdzeniu a , co nie zawsze jest prawdziwe. Jak to może być?( …

16 logic  recursion  type-theory  combinatory-logic  curry-howard 

Jestem samoukiem, asystentem ds. Dowodów i postanowiłem zacząć od kilku podstawowych dowodów i podążać swoją drogą. Ponieważ dowody są oparte na innych dowodach, a zatem tworzą hierarchię, czy istnieje repozytorium hierarchii dowodów? Wiem, że mogę wybrać konkretnego asystenta proofów i przeanalizować jego bibliotekę, aby wyodrębnić jego hierarchię, jednak jeśli chcę …

15 reference-request  logic  proof-assistants 

Pracuję nad kompilatorem dla języka konkatenatywnego i chciałbym dodać obsługę wnioskowania typu. Rozumiem Hindleya-Milnera, ale nauczyłem się teorii typów, więc nie jestem pewien, jak ją dostosować. Czy następujący system jest dźwiękowy i można go w sposób zdecydowanie wywnioskować? Termin jest literałem, kompozycją terminów, cytatem terminu lub prymitywem. e::=x∣∣ee∣∣[e]∣∣…e::=x|ee|[e]|… e ::= …

15 programming-languages  logic  compilers  type-theory  type-checking 

Próbuję owinąć głowę wokół dowodu kompletności NP, który wydaje się obracać wokół SAT / 3CNF-SAT. Może jest późna godzina, ale obawiam się, że nie mogę wymyślić formuły 3CNF, której nie można spełnić (prawdopodobnie brakuje mi czegoś oczywistego). Czy możesz podać mi przykład takiej formuły?

15 logic  satisfiability  3-sat 

Kolejność aplikacji: Zawsze w pełni oceniaj argumenty funkcji przed oceną samej funkcji, na przykład - (λx.x2(λx.(x+1) 2)))→(λx.x2(2+1))→ (λx.x2(3))→ 32 → 9(λx.x2(λx.(x+1) 2)))→(λx.x2(2+1))→ (λx.x2(3))→ 32 → 9(\lambda x. x^2(\lambda x.(x+1) \ \ 2))) \rightarrow (\lambda x. x^2(2+1))\rightarrow \ (\lambda x. x^2(3)) \rightarrow \ 3^2 \ \rightarrow \ 9 Normalna kolejność: wyrażenie …

14 logic  lambda-calculus  normal-forms 

Załóżmy, że mamy prosty język, który składa się z terminów: truetrue\mathtt{true} falsefalse\mathtt{false} jeśli są warunkami, to podobnie jest zi ft1,t2,t3t1,t2,t3t_1,t_2,t_3ift1thent2elset3ift1thent2elset3\mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 Załóżmy teraz następujące logiczne reguły oceny: iftruethent2elset3→t2[E-IfTrue]iffalsethent2elset3→t3[E-IfFalse]t1→t′1ift1thent2elset3→ift′1thent2elset3[E-If]iftruethent2elset3→t2[E-IfTrue]iffalsethent2elset3→t3[E-IfFalse]t1→t1′ift1thent2elset3→ift1′thent2elset3[E-If] \begin{gather*} \dfrac{} {\mathtt{if}\: \mathtt{true} \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 \to t_2} \text{[E-IfTrue]} \quad \dfrac{} {\mathtt{if}\: \mathtt{false} \:\mathtt{then}\: t_2 \:\mathtt{else}\: …

14 logic  semantics  proof-techniques  term-rewriting 

Oto kontekst ( Struktura i interpretacja programów komputerowych , sekcja 1.1.8, pod nagłówkiem „Nazwy lokalne”): Formalny parametr procedury ma bardzo szczególną rolę w definicji procedury, ponieważ nie ma znaczenia, jaką nazwę ma parametr formalny. Taka nazwa nazywa się zmienną powiązaną i mówimy, że definicja procedury wiąże jej parametry formalne. Znaczenie …

14 logic 

Rozumiem znaczenie, jakie informatycy lub inżynierowie związani z opracowywaniem oprogramowania powinni rozumieć jako podstawy badania logiki podstawowej. Ale czy są jakieś zadania / zadania, które wyraźnie wymagają wiedzy na ich temat, inne niż zadania wymagające jakiejkolwiek reprezentacji wiedzy przy użyciu Knowledge Base? Chcę usłyszeć rodzaje zadań, a nie koncepcyjne odpowiedzi. …

14 logic 

Jestem programistą z automatami, ale nie logiką. Przeczytałem w artykułach, że te dwa są ze sobą ściśle powiązane. Deterministyczne automaty skończone (DFA), automaty drzewa i automaty z widocznym przesunięciem w dół są powiązane z logiką Monadic drugiego rzędu (MSO). Chociaż rozumiem automaty i ludzie (w dokumentach) próbowali mi wyjaśnić związek …

14 automata  finite-automata  logic  coq  automated-theorem-proving 

Wygląda na to, że znalazłem ogólny sposób na konwersję dowolnej procedury rekurencyjnej na rekurencyjną: Zdefiniuj podprocedurę pomocnika z dodatkowym parametrem „wynik”. Zastosuj to, co zostanie zastosowane do wartości zwracanej przez procedurę do tego parametru. Zadzwoń do tej procedury pomocnika, aby rozpocząć. Wartość początkowa parametru „wynik” jest wartością punktu wyjścia procesu …

13 algorithms  logic  recursion  lisp 

Myślałem o dowodach i natknąłem się na ciekawą obserwację. Tak więc dowody są równoważne programom za pomocą izomorfizmu Curry'ego-Howarda, a dowody kołowe odpowiadają nieskończonej rekurencji. Wiemy jednak z problemu zatrzymania, że ​​ogólne testowanie, czy dowolny program powróci na zawsze, jest nierozstrzygalne. Czy Curry-Howard oznacza, że ​​nie ma „kontrolera dowodu”, który …

13 logic  curry-howard 

Myślałem, że dobrze rozumiem pisanie zależne (DT), ale odpowiedź na to pytanie: /cstheory/30651/why-was-there-a-need-for-martin-l%C3% Teoria typu B6f do tworzenia-intuicyjnego typu kazała mi myśleć inaczej. Po przeczytaniu DT i próbie zrozumienia, czym one są, zastanawiam się, co zyskujemy dzięki temu pojęciu DT? Wydają się być bardziej elastyczne i wydajne niż zwykły rachunek …

13 logic  type-theory  intuition 

Obecnie muszę się nauczyć Coq i nie wiem, jak sobie radzić z or: Jako przykład, choć jest to tak proste, nie widzę, jak udowodnić: Theorem T0: x \/ ~x. Byłbym bardzo wdzięczny, gdyby ktoś mógł mi pomóc. Dla porównania używam tego ściągawki . Mam też przykład dowodu, który mam na …

12 logic  coq 

W praktycznych podstaw dla języków programowania , Robert Harper mówi Jeśli twierdzenie, które jest prawdziwe, oznacza posiadanie dowodu, co to znaczy, że twierdzenie jest fałszywe? Oznacza to, że mamy obalenie go, pokazując, że nie można tego udowodnić. Oznacza to, że twierdzenie jest fałszywe, jeśli możemy wykazać, że założenie, że jest …

12 logic 

Czytałem pytanie Spójność i kompletność oznaczają solidność? a pierwsze oświadczenie zawiera: Rozumiem, że solidność oznacza konsekwencję. Byłem dość zdziwiony, ponieważ uważałem, że dźwięk jest słabszym stwierdzeniem niż spójność (tj. Myślałem, że spójne systemy muszą być zdrowe, ale wydaje mi się, że to nieprawda). Używałem nieformalnej definicji, której Scott Aaronson używał …

12 terminology  logic  first-order-logic  propositional-logic  incompleteness