Logic is now widely recognized to be one of the foundational disciplines of computing, and its applications reach almost every aspect of the subject, from software engineering and hardware to programming languages and artificial intelligence research. The Handbook of Logic in Computer Science is a six volume, internationally authored work which offers a comprehensive treatment of the application of the concepts of logic to theoretical computer science. Each volume is comprised of an average of five 100-page monographs and presents an in-depth overview of a major subject area. The first two volumes, available now, cover the background to the subject in terms of mathematical and computational structures. Future volumes will cover semantic structures, semantic modelling, theoretical methods in specification and verification, and logical methods in computer science. The result of five years of cooperative effort by some of the field's most eminent scholars, this series will undoubtedly be the standard reference work in logic and theoretical computer science for years to come.

Das Unendliche hat wie keine andere Frage von jeher so tief das Gemut der Menschen bewegt," das Unendliche hat wie kaum eine andere Idee auf den Verstand so an- regend und fruchtbar gewirkt," das Unendliche ist aber auch wie kein anderer Begriff so der Aufklarung bedurftig. HILBERT [226, p. 163] Etwas mehr als 100 Jahre sind vergangen, seit in den Mathemati- schen Annalen der sechste und letzte Teil von CANTORS fundamenta- ler Arbeit UEber unendliche lineare Punktmannichfaltigkeiten erschie- nen ist. Damit war die Mengenlehre geboren und mit ihr eine prinzipiell neue Auffassung des Unendlichen in der Mathematik, verkoerpert in CANTORS Theorie der transfiniten Zahlen. Diese Theo- rie hat HILBERT als "die bewundernswerteste Blute mathematischen Geistes und uberhaupt eine der hoechsten Leistungen rein verstandes- massiger menschlicher Tatigkeit" bezeichnet. Anfangs unbeachtet oder abgelehnt, zu Ende des vorigen Jahrhunderts zunehmend anerkannt und verwendet, durch die Ent- deckung der Antinomien erneut erschuttert, ist die Mengenlehre in ihrer heutigen axiomatisierten Gestalt eines der Fundamente der Mathematik. Die Tatsache, dass alle mathematischen Begriffe auf mengentheoretische Begriffe zuruckgefuhrt werden koennen, hat ei- nige Autoren sogar zu der Behauptung veranlasst, die gesamte Ma- thematik sei letztendlich mit der Mengenlehre identisch. Wenn uns allerdings eine solche Ansicht als eine ungerechtfertigte UEberbeto- nung des Formalen gegenuber dem Inhaltlichen erscheint, so ist doch unbestritten, dass die mengentheoretische Durchdringung der Mathematik neben der Entstehung des strukturellen Denkens und der Verwendung der axiomatischen Methode ein Wesenszug der mo- dernen Mathematik ist. Das hat in zahlreichen Landern bis in den Schulunterricht hinein gewirkt.

H. Soubies-Camy: L alg bre logique appliqu e aux techniques binaires, I parte: lezioni.- H. Soubies-Camy: L alg bre logique appliqu e aux techniques binaires, II parte: disegni.- J. Piesch: Switching Algebra.- J.P. Roth: Una teoria per la progettazione logica dei Meccanismi Automatici.

Now the most used texbook for introductory cryptography courses in both mathematics and computer science, the Third Edition builds upon previous editions by offering several new sections, topics, and exercises. The authors present the core principles of modern cryptography, with emphasis on formal definitions, rigorous proofs of security.

Table of Contents

I Introduction and Classical Cryptography

1. Introduction

Cryptography and Modern Cryptography

The Setting of Private-Key Encryption

Historical Ciphers and Their Cryptanalysis

Principles of Modern Cryptography

Principle 1 - Formal Definitions

Principle 2 - Precise Assumptions

Principle 3 - Proofs of Security

Provable Security and Real-World Security

References and Additional Reading

Exercises

2. Perfectly Secret Encryption

Definitions

The One-Time Pad

Limitations of Perfect Secrecy

*Shannon's Theorem

References and Additional Reading

Exercises

II Private-Key (Symmetric) Cryptography

3. Private-Key Encryption

Computational Security

The Concrete Approach

The Asymptotic Approach

Defining Computationally Secure Encryption

The Basic Definition of Security (EAV-Security)

*Semantic Security

Constructing an EAV-Secure Encryption Scheme

Pseudorandom Generators

Proofs by Reduction

EAV-Security from a Pseudorandom Generator

Stronger Security Notions

Security for Multiple Encryptions

Chosen-Plaintext Attacks and CPA-Security

CPA-Security for Multiple Encryptions

Constructing a CPA-Secure Encryption Scheme

Pseudorandom Functions and Permutations

CPA-Security from a Pseudorandom Function

Modes of Operation and Encryption in Practice

Stream Ciphers

Stream-Cipher Modes of Operation

Block Ciphers and Block-Cipher Modes of Operation

*Nonce-Based Encryption

References and Additional Reading

Exercises

4. Message Authentication Codes

Message Integrity

Secrecy vs Integrity

Encryption vs Message Authentication

Message Authentication Codes (MACs) - Definitions

Constructing Secure Message Authentication Codes

A Fixed-Length MAC

Domain Extension for MACs

CBC-MAC

The Basic Construction

*Proof of Security

GMAC and Poly

MACs from Difference-Universal Functions

Instantiations

*Information-Theoretic MACs

One-Time MACs from Strongly Universal Functions

One-Time MACs from Difference-Universal Functions

Limitations on Information-Theoretic MACs

References and Additional Reading

Exercises

5. CCA-Security and Authenticated Encryption

Chosen-Ciphertext Attacks and CCA-Security

Padding-Oracle Attacks

Defining CCA-Security

Authenticated Encryption

Defining Authenticated Encryption

CCA Security vs Authenticated Encryption

Authenticated Encryption Schemes

Generic Constructions

Standardized Schemes

Secure Communication Sessions

References and Additional Reading

Exercises

6. Hash Functions and Applications

Definitions

Collision Resistance

Weaker Notions of Security

Domain Extension: The Merkle-Damgard Transform

Message Authentication Using Hash Functions

Hash-and-MAC

HMAC

Generic Attacks on Hash Functions

Birthday Attacks for Finding Collisions

Small-Space Birthday Attacks

*Time/Space Tradeo s for Inverting Hash Functions

The Random-Oracle Model

The Random-Oracle Model in Detail

Is the Random-Oracle Methodology Sound?

Additional Applications of Hash Functions

Fingerprinting and Deduplication

Merkle Trees

Password Hashing

Key Derivation

Commitment Schemes

References and Additional Reading

Exercises

7. Practical Constructions of Symmetric-Key Primitives

Stream Ciphers

Linear-Feedback Shift Registers

Adding Nonlinearity

Trivium

RC4

ChaCha20

Block Ciphers

Substitution-Permutation Networks

Feistel Networks

DES - The Data Encryption Standard

3 DES: Increasing the Key Length of a Block Cipher

AES -The Advanced Encryption Standard

*Differential and Linear Cryptanalysis

Compression Functions and Hash Functions

Compression Functions from Block Ciphers

MD5, SHA-1, and SHA-2

The Sponge Construction and SHA-3 (Keccak)

References and Additional Reading

Exercises

8. *Theoretical Constructions of Symmetric-Key Primitives

One-Way Functions

Definitions

Candidate One-Way Functions

Hard-Core Predicates

From One-Way Functions to Pseudorandomness

Hard-Core Predicates from One-Way Functions

A Simple Case

A More Involved Case

The Full Proof

Constructing Pseudorandom Generators

Pseudorandom Generators with Minimal Expansion

Increasing the Expansion Factor

Constructing Pseudorandom Functions

Constructing (Strong) Pseudorandom Permutations

Assumptions for Private-Key Cryptography

Computational Indistinguishability

References and Additional Reading

Exercises

III Public-Key (Asymmetric) Cryptography

9. Number Theory and Cryptographic Hardness Assumptions

Preliminaries and Basic Group Theory

Primes and Divisibility

Modular Arithmetic

Groups

The Group ZN

*Isomorphisms and the Chinese Remainder Theorem

Primes, Factoring, and RSA

Generating Random Primes

*Primality Testing

The Factoring Assumption

The RSA Assumption

*Relating the Factoring and RSA Assumptions

Cryptographic Assumptions in Cyclic Groups

Cyclic Groups and Generators

The Discrete-Logarithm/Diffie-Hellman Assumptions

Working in (Subgroups of) Zp

Elliptic Curves

*Cryptographic Applications

One-Way Functions and Permutations

Collision-Resistant Hash Functions

References and Additional Reading

Exercises

10. *Algorithms for Factoring and Computing Discrete Logarithms

Algorithms for Factoring

Pollard's p - Algorithm

Pollard's Rho Algorithm

The Quadratic Sieve Algorithm

Generic Algorithms for Computing Discrete Logarithms

The Pohlig-Hellman Algorithm

The Baby-Step/Giant-Step Algorithm

Discrete Logarithms from Collisions

Index Calculus: Computing Discrete Logarithms in Zp

Recommended Key Lengths

References and Additional Reading

Exercises

11. Key Management and the Public-Key Revolution

Key Distribution and Key Management

A Partial Solution: Key-Distribution Centers

Key Exchange and the Diffie-Hellman Protocol

The Public-Key Revolution

References and Additional Reading

Exercises

12. Public-Key Encryption

Public-Key Encryption - An Overview

Definitions

Security against Chosen-Plaintext Attacks

Multiple Encryptions

Security against Chosen-Ciphertext Attacks

Hybrid Encryption and the KEM/DEM Paradigm

CPA-Security

CCA-Security

CDH/DDH-Based Encryption

El Gamal Encryption

DDH-Based Key Encapsulation

*A CDH-Based KEM in the Random-Oracle Model

*Chosen-Ciphertext Security and DHIES/ECIES

RSA-Based Encryption

Plain RSA Encryption

Padded RSA and PKCS # v

*CPA-Secure Encryption without Random Oracles

OAEP and PKCS # v

*A CCA-Secure KEM in the Random-Oracle Model

RSA Implementation Issues and Pitfalls

References and Additional Reading

Exercises

13. Digital Signature Schemes

Digital Signatures - An Overview

Definitions

The Hash-and-Sign Paradigm

RSA-Based Signatures

Plain RSA Signatures

RSA-FDH and PKCS #1 Standards

Signatures from the Discrete-Logarithm Problem

Identification Schemes and Signatures

The Schnorr Identification/Signature Schemes

DSA and ECDSA

Certificates and Public-Key Infrastructures

Putting It All Together { TLS

*Signcryption

References and Additional Reading

Exercises

14. *Post-Quantum Cryptography

Post-Quantum Symmetric-Key Cryptography

Grover's Algorithm and Symmetric-Key Lengths

Collision-Finding Algorithms and Hash Functions

Shor's Algorithm and its Impact on Cryptography

Post-Quantum Public-Key Encryption

Post-Quantum Signatures

Lamport's Signature Scheme

Chain-Based Signatures

Tree-Based Signatures

References and Additional Reading

Exercises

15. *Advanced Topics in Public-Key Encryption

Public-Key Encryption from Trapdoor Permutations

Trapdoor Permutations

Public-Key Encryption from Trapdoor Permutations

The Paillier Encryption Scheme

The Structure of Z_N

The Paillier Encryption Scheme

Homomorphic Encryption

Secret Sharing and Threshold Encryption

Secret Sharing

Verifiable Secret Sharing

Threshold Encryption and Electronic Voting

The Goldwasser-Micali Encryption Scheme

Quadratic Residues Modulo a Prime

Quadratic Residues Modulo a Composite

The Quadratic Residuosity Assumption

The Goldwasser-Micali Encryption Scheme

The Rabin Encryption Scheme

Computing Modular Square Roots

A Trapdoor Permutation Based on Factoring

The Rabin Encryption Scheme

References and Additional Reading

Exercises

Index of Common Notation

Appendix A Mathematical Background

A Identities and Inequalities

A Asymptotic Notation

A Basic Probability

A The \Birthday" Problem

A *Finite Fields

Appendix B Basic Algorithmic Number Theory

B Integer Arithmetic

B Basic Operations

B The Euclidean and Extended Euclidean Algorithms

B Modular Arithmetic

B Basic Operations

B Computing Modular Inverses

B Modular Exponentiation

B *Montgomery Multiplication

B Choosing a Uniform Group Element

B *Finding a Generator of a Cyclic Group

B Group-Theoretic Background

B Efficient Algorithms

References and Additional Reading

Exercises



　

/

Der Autor vermittelt logisches Grundwissen, fundamentale Beweisprinzipien und Methoden der Mathematik. Dabei geht er u. a. folgenden Fragen nach: Was unterscheidet endliche von unendlichen Mengen? Wie lassen sich die ganzen, rationalen und reellen Zahlen aus den nat rlichen Zahlen konstruieren? Welche grundlegenden topologischen Eigenschaften besitzt die Menge der reellen Zahlen? Lassen sich die nat rlichen oder reellen Zahlen vollst ndig axiomatisch beschreiben? Pflichtlekt re f r alle Studierenden der Mathematik, Physik und Informatik.

Petri-Netze sind das meist beachtete und am besten untersuchte Modell fur nebenlaufige, parallele Rechnungen. In diesem Lehrbuch werden zum ersten Mal zahlreich Resultate der Originalliteratur uber Unmoglichkeiten, Moglichkeiten und die Komplexitat der Ausdrucksmittel von Petri-Netzen didaktisch aufgearbeitet und im Detail einer breiteren Leserschaft vorgestellt. Alle fur die Beweise notwendigen Techniken und mathematischen Begriffe werden erlautert. Damit wendet sich das Buch sowohl an Studierende als auch an Lehrende und Forscher. Der Inhalt konzentriert sich neben einer Darstellung der Grundbegriffe und deren Zusammenhange insbesondere auf einen Algorithmus fur die Erreichbarkeitsfrage, die Ausdrucksfahigkeit verschiedener Berechnungsbegriffe, ausgewahlte Fragen zur Entscheidbarkeit und Komplexitat, sowie Petri-Netz Semantiken mittels Sprachen und partiell geordneten Mengen und deren algebraische Charakterisierung."

A mathematical introduction to the theory and applications of logic and set theory with an emphasis on writing proofs Highlighting the applications and notations of basic mathematical concepts within the framework of logic and set theory, A First Course in Mathematical Logic and Set Theory introduces how logic is used to prepare and structure proofs and solve more complex problems. The book begins with propositional logic, including two-column proofs and truth table applications, followed by first-order logic, which provides the structure for writing mathematical proofs. Set theory is then introduced and serves as the basis for defining relations, functions, numbers, mathematical induction, ordinals, and cardinals. The book concludes with a primer on basic model theory with applications to abstract algebra. A First Course in Mathematical Logic and Set Theory also includes: * Section exercises designed to show the interactions between topics and reinforce the presented ideas and concepts * Numerous examples that illustrate theorems and employ basic concepts such as Euclid s lemma, the Fibonacci sequence, and unique factorization * Coverage of important theorems including the well-ordering theorem, completeness theorem, compactness theorem, as well as the theorems of Lowenheim Skolem, Burali-Forti, Hartogs, Cantor Schroder Bernstein, and Konig An excellent textbook for students studying the foundations of mathematics and mathematical proofs, A First Course in Mathematical Logic and Set Theory is also appropriate for readers preparing for careers in mathematics education or computer science. In addition, the book is ideal for introductory courses on mathematical logic and/or set theory and appropriate for upper-undergraduate transition courses with rigorous mathematical reasoning involving algebra, number theory, or analysis.

Mathematics and logic have been central topics of concern since the dawn of philosophy. Since logic is the study of correct reasoning, it is a fundamental branch of epistemology and a priority in any philosophical system. Philosophers have focused on mathematics as a case study for general philosophical issues and for its role in overall knowledge- gathering. Today, philosophy of mathematics and logic remain central disciplines in contemporary philosophy, as evidenced by the regular appearance of articles on these topics in the best mainstream philosophical journals; in fact, the last decade has seen an explosion of scholarly work in these areas.
This volume covers these disciplines in a comprehensive and accessible manner, giving the reader an overview of the major problems, positions, and battle lines. The 26 contributed chapters are by established experts in the field, and their articles contain both exposition and criticism as well as substantial development of their own positions. The essays, which are substantially self-contained, serve both to introduce the reader to the subject and to engage in it at its frontiers. Certain major positions are represented by two chapters--one supportive and one critical.
The Oxford Handbook of Philosophy of Math and Logic is a ground-breaking reference like no other in its field. It is a central resource to those wishing to learn about the philosophy of mathematics and the philosophy of logic, or some aspect thereof, and to those who actively engage in the discipline, from advanced undergraduates to professional philosophers, mathematicians, and historians.

This book develops arithmetic without the induction principle, working in theories that are interpretable in Raphael Robinson's theory Q. Certain inductive formulas, the bounded ones, are interpretable in Q. A mathematically strong, but logically very weak, predicative arithmetic is constructed.

Originally published in 1986.

The Princeton Legacy Library uses the latest print-on-demand technology to again make available previously out-of-print books from the distinguished backlist of Princeton University Press. These paperback editions preserve the original texts of these important books while presenting them in durable paperback editions. The goal of the Princeton Legacy Library is to vastly increase access to the rich scholarly heritage found in the thousands of books published by Princeton University Press since its founding in 1905.

An Introduction to Proof Theory provides an accessible introduction to the theory of proofs, with details of proofs worked out and examples and exercises to aid the reader's understanding. It also serves as a companion to reading the original pathbreaking articles by Gerhard Gentzen. The first half covers topics in structural proof theory, including the Goedel-Gentzen translation of classical into intuitionistic logic (and arithmetic), natural deduction and the normalization theorems (for both NJ and NK), the sequent calculus, including cut-elimination and mid-sequent theorems, and various applications of these results. The second half examines ordinal proof theory, specifically Gentzen's consistency proof for first-order Peano Arithmetic. The theory of ordinal notations and other elements of ordinal theory are developed from scratch, and no knowledge of set theory is presumed. The proof methods needed to establish proof-theoretic results, especially proof by induction, are introduced in stages throughout the text. Mancosu, Galvan, and Zach's introduction will provide a solid foundation for those looking to understand this central area of mathematical logic and the philosophy of mathematics.

Diese kompakte Einfuhrung in die Theoretische Informatik stellt die wichtigsten Modelle fur zentrale Probleme der Informatik vor. Dabei werden u.a. folgende Fragestellungen behandelt:

Welche Probleme sind algorithmisch losbar? (Theorie der Berechenbarkeit und Entscheidbarkeit)

Wie schwierig ist es algorithmische Probleme zu losen? (Theorie der Berechnungskomplexitat, NP-Theorie)

Wie sind informationsverarbeitende Systeme prinzipiell aufgebaut? (Theorie der endlichen Automaten)

Welche Strukturen besitzen Programmiersprachen? (Theorie der formalen Sprachen)

In der Erarbeitung dieser Themen wird der Abstraktionsprozess von den realen Gegenstanden der Informatik zu den in der Theoretischen Infromatik etabliertern Modellen, wie z.B. Random-Access-Maschinen, Turingmaschinen und endliche Automaten, nachvollzogen und umgekehrt verdeutlicht, was diese Modelle aufgrund der uber sie gewonnenen Erkenntnisse fur die Praxis leisten konnen."

Dieses Buch basiert auf Vorlesungen, die der Autor in Kaiserslautern gehalten hat. Ihr wesentliches Anliegen war, die Turing-berechenbaren Wortfunktionen auf eine von jeglichem Maschinenmodell unabhangige Weise zu charakterisieren, namlich als die partiell Wort-rekursiven Wortfunktionen. Wortfunktionen lassen sich mittels arithmetischer Funktionen darstellen und zwar so, dass die partiell rekursiven arithmetischen Funktionen den partiell Wort-rekursiven Wortfunktionen entsprechen, was fur sich gesehen schon nicht auf der Hand liegt. Auf diese Weise erhalt man den Begriff der Turing-Berechenbarkeit auch fur arithmetische Funktionen. Der Satz also, dass die Turing-berechenbaren Wortfunktionen gerade die partiell rekursiven Wortfunktionen sind, ist uberhaupt nicht selbstverstandlich, so dass auf dem Wege zu diesem Satz eine ganze Reihe hoch interessanter weiterer Satze zu beweisen sind. Dies alles ist hier aufgeschrieben.

In funf sorgfaltig aufeinander abgestimmten Teilen behandelt das Buch die wesentlichen mathematischen Elemente der formalen Spezifikation von Systemen und der Aussagen- und Pradikatenlogik, die fur das Verstandnis des formalisierten Problemlosens entscheidend und damit fur Informatiker unerlasslich sind. Eine Einfuhrung in die intuitive Mengentheorie vermittelt zunachst notwendige mathematische Grundlagen. Motiviert durch das Konzept von Datenstrukturen und abstrakten Datentypen werden dann algebraische Strukturen in der Informatik behandelt. Danach werden Aussagen- und Pradikatenlogik aus der Sicht der Mathematik und Informatik dargestellt. Schliesslich fuhrt die Kategorientheorie fur Informatiker in die Welt der abstrakten Behandlung mathematischer Strukturen ein.
Die Neuauflage wurde erweitert um Darstellungen zur Modellalgebra und zur Implementierung. Ubungsaufgaben wurden erganzt."

Cinderella ist eine einzigartige, technisch ausgereifte interaktive Geometrie-Lernsoftware, die sich ausgezeichnet fA1/4r Studenten zum Erlernen der Euklidischen, projektiven, sphArischen und hyperbolischen Geometrie eignet. Aufgrund seines leistungsfAhigen mathematischen Kerns kann Cinderella jedoch ebenfalls als Werkzeug fA1/4r Wissenschaftler in der Forschung auf dem Gebiet der Geometrie und KomplexitAtstheorie Anwendung finden. Die Software enthAlt einen eingebauten automatischen Beweiser fA1/4r geometrische SAtze. Durch eine einfache Exportfunktion kann Cinderella als Werkzeug zum Gestalten von WWW-Seiten oder als Hilfe bei der Ausarbeitung interaktiver Geometrie-BA1/4cher genutzt werden.

Die zentrale Aufgabe einer zukunftsorientierten Computerlinguistik ist die Entwicklung kognitiver Maschinen, mit denen Menschen in ihrer jeweiligen Sprache frei reden kAnnen. Langfristig umfaAt diese Zielsetzung eine funktional ausgerichtete Theoriebildung, eine objektive Verifikationsmethode und eine FA1/4lle praktischer Anwendungen.
FA1/4r die natA1/4rlichsprachliche Kommunikation wird nicht nur Sprachverarbeitung, sondern auch nichtsprachliche Wahrnehmung und Handlung benAtigt. Deshalb ist der Inhalt dieses Lehrbuchs als Sprachtheorie fA1/4r die Konstruktion sprechender Roboter organisiert. Sein zentrales Thema ist die Kommunikationsmechanik natA1/4rlicher Sprachen - beim Sprecher und beim HArer. Der Inhalt ist in folgende vier Teile mit je sechs Kapiteln gegliedert: Sprachtheorie; Formale Grammatik; Morphologie und Syntax; Semantik und Pragmatik. Insgesamt 772 Aoebungsaufgaben dienen der VerstAndniskontrolle und -vertiefung.

In mathematics we are interested in why a particular formula is true. Intuition and statistical evidence are insufficient, so we need to construct a formal logical proof. The purpose of this book is to describe why such proofs are important, what they are made of, how to recognize valid ones, how to distinguish different kinds, and how to construct them. This book is written for 1st year students with no previous experience of formulating proofs. Dave Johnson has drawn from his considerable experience to provide a text that concentrates on the most important elements of the subject using clear, simple explanations that require no background knowledge of logic. It gives many useful examples and problems, many with fully-worked solutions at the end of the book. In addition to a comprehensive index, there is also a useful `Dramatis Personae` an index to the many symbols introduced in the text, most of which will be new to students and which will be used throughout their degree programme.