情報科学における論理
小野 寛晰, 日本評論社
>論理学の入門書.ソフトウェア科学の基礎となる内容が盛りだくさんです.

計算論 計算可能性とラムダ計算
高橋 正子, 近代科学社
>計算論,特にラムダ計算について書かれています.後半は少し高度な内容になっています.

コンピュータサイエンス入門―アルゴリズムとプログラミング言語
大堀 淳, ジャック ガリグ, 西村 進, 岩波書店
>第1部は平易ですが,第2部はちょっときついです.でも,読む価値あり.(追記)型理論を学んだのちに第2部を読み返すとすごく理解しやすくなっていました.

コンピュータサイエンス入門―論理とプログラム意味論
田辺 誠, 中島 玲二, 長谷川 真人, 岩波書店
>第2部の不動点意味論が肝です.再帰と不動点の関係が明確に示されます.

プログラム意味論
横内 寛文, 共立出版
>プログラムの表示的意味論の解説書.前半は和書で単純型付きラムダの勉強をしたい人にもぴったり.

Types and Programming Languages
Benjamin C. Pierce, Mit Press
>型とプログラミング言語に関する大抵の話題が網羅されていて,大変便利です.

Basic Category Theory for Computer Scientists (Foundations of Computing)
Benjamin C. Pierce, Mit Press
>カテゴリーの入門書.この本だけでは少し物足りない感じがします.

Basic Proof Theory (Cambridge Tracts in Theoretical Computer Science, 43)
A. S. Troelstra, H. Schwichtenberg, Cambridge Univ Press (Txp)
>証明論についての本.基本定理はもちろん,カテゴリーや様相論理にも言及しています.