Logic for Computer Science

Birla Institute Of Technology And Science–Pilani (BITS–Pilani) via Coursera

Go to class Write review

Details

Go to class

Provider

Coursera
Pricing

Paid Course
Languages

English
Certificate

Paid Certificate Available
Duration & workload

1 day 4 hours 48 minutes
Sessions

On-Demand
Subtitles

English

Found in

Part of

Mathematics for Engineering

Overview

Coursera Flash Sale

40% Off Coursera Plus for 3 Months!

Grab it

Unlock the power of logical thinking and formal reasoning essential for success in computer science, data analysis, and software development with this dynamic course. Ideal for students, software engineers, data scientists, and IT professionals, this comprehensive program delves into logic foundations critical for advanced computing careers. Starting with fundamental proofs and proof systems, you’ll explore soundness, completeness, first-order propositional, and predicate logic. Dive into advanced topics like modeling, program verification, and temporal logic. Master Gentzen’s natural deduction, and understand the semantics and syntax of logical forms. Tackle the undecidability of logic and learn model checking using temporal logics (LTL, CTL, CTL*) to verify system properties, applying Floyd-Hoare logics to ensure program correctness. Our structured approach incorporates practical techniques to enhance memory and overcome procrastination, benefiting both academic learning and professional efficiency. Engaging case studies offer hands-on experience verifying algorithms, such as array searching and sorting, essential for real-world problem solving. Geared towards those aiming for roles in tech innovation, this course equips you with the analytical tools and logical proficiency to excel in computing, programming, and data-driven problem-solving. Elevate your career and expertise in the ever-evolving technology landscape.

Syllabus

Propositional Logic

In this module, you will learn the relevance of formal logics in computer science. You will understand the difference between syntax and semantics. The module will also introduce you to propositional logic and informally to its syntactic constructs.

Natural Deduction in Propositional Logic

In this module, you will learn about the symbolic manipulation technique of natural deduction. The module will also discuss the different rules of natural deduction with examples.

Semantics, Soundness, and Completeness of Natural Deduction

In this module, you will learn about state-of-the-art methods of resolution and Davis-Putnam-Logemann-Loveland (DPLL) methods to argue about the satisfiability of a propositional logic formula. We study the relevant characteristics of a logical theory, i.e., the consistency, soundness, and completeness, and comment on natural deduction as a proof technique on how it scores over these characteristics.

Model Checking Techniques and Temporal Logics

In this module, you will be introduced to model-based formal verification techniques, in particular, the model checking techniques. The module will informally discuss two popular families of temporal logics: linear temporal logic (LTL) and computation tree logic (CTL).

LTL and CTL Temporal Logics, Algorithms for Model Checking

In this module, you will formally learn the LTL and CTL temporal logics. The module will also introduce you to the algorithms used for model checking over these algorithms. The module will further explain fundamental system properties, such as invariance, safety, and liveliness. Furthermore, the module will give provide you insight into how to encode natural language sentences into LTL and CTL formulas.

Predicate Logic

In this module, you will learn the need for predicate logic and how to express statements in predicate logic. You will also learn about the syntax of predicate logic and the fundamentals behind writing proofs in predicate logic. You would also learn the concept of substitution and the difference between the free variables and bound variables. You will also get introduced to basic predicate logic rules that are used for proving sequents.

Natural Deduction in Predicate Logic

In this module, you will learn to apply the proof rules of natural deduction to prove sequents in predicate logic. The proof rules that you would learn include: Universal Quantifier Elimination, Existential Quantifier Introduction, Universal Quantifier Introduction and Existential Quantifier Elimination. You would also learn to identify which specific rules to apply for writing proof of a given sequent.

Semantics, Soundness, Completeness, and Undecidability of Predicate Logic

In this module, you will learn about semantics and model interpretations in predicate logic. You would also learn about the satisfiability and validity of predicate logic formulas, along with the undecidability of validity. You would also learn about the limitations of first-order predicate logic and how second-order predicate logic is useful in such cases.

Program Verification

In this module, you will learn how to formally verify programs written in imperative style. More specifically, you will learn formal methods to verify assignment statements, sequence of statements, conditional statements, and iterative statements. You will also learn the formal method to verify whether a given program terminates or not.

Program Verification Case Studies

In this module, you will learn to prove the total correctness of various commonly used algorithms such as computing the power of two numbers, finding an element from an unsorted array, and selection sort. You would also learn to deduce loop invariants for programs of the above computational problems and prove that these programs terminates.