Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Hoare Logic: Strongest Postcondition and Weakest Precondition

In course

CS-550: Formal verification

We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to use formal verification tools and explain the theory and ...

Description

This lecture introduces Hoare logic, focusing on the concepts of strongest postcondition and weakest precondition. It covers the definitions of Hoare triple, strongest postcondition, and weakest precondition, along with examples and proofs. The instructor explains how to use Hoare logic to simplify proofs about imperative program behavior.

Instructor

Viktor Kuncak

Viktor Kunčak joined EPFL in 2007, after receiving a PhD degree from MIT. Since then has been leading the Laboratory for Automated Reasoning and Analysis and supervised at least 12 completed PhD theses. His works on languages, algorithms and systems for verification and automated reasoning. He served as an initiator and one of the coordinators of a European network (COST action) in the area of automated reasoning, verification, and synthesis. In 2012 he received a 5-year single-investigator European Research Council (ERC) grant of 1.5M EUR. His invited talks include those at Lambda Days, Scala Days, NFM, LOPSTR, SYNT, ICALP, CSL, RV, VMCAI, and SMT. A paper on test generation he co-authored received an ACM SIGSOFT distinguished paper award at ICSE. A PLDI paper he co-authored was published in the Communications of the ACM as a Research Highlight article. His Google Scholar profile reports an over-approximate H-index of 38. He was an associate editor of ACM Transactions on Programming Languages and Systems (TOPLAS) and served as a co-chair of conferences on Computer-Aided Verification (CAV), Formal Methods in Computer Aided Design (FMCAD), Workshop on Synthesis (SYNT), and Verification, Model Checking, and Abstract Interpretation (VMCAI). At EPFL he teaches courses on functional and parallel programming, compilers, and verification. He has co-taught the MOOC "Parallel Programming" that was visited by over 100'000 learners and completed by thousands of students from all over the world.

Official source

Related concepts (32)

Predicate transformer semantics

Predicate transformer semantics were introduced by Edsger Dijkstra in his seminal paper "Guarded commands, nondeterminacy and formal derivation of programs". They define the semantics of an imperative programming paradigm by assigning to each statement in this language a corresponding predicate transformer: a total function between two predicates on the state space of the statement. In this sense, predicate transformer semantics are a kind of denotational semantics.

Adaptive behavior

Adaptive behavior is behavior that enables a person (usually used in the context of children) to cope in their environment with greatest success and least conflict with others. This is a term used in the areas of psychology and special education. Adaptive behavior relates to everyday skills or tasks that the "average" person is able to complete, similar to the term life skills. Nonconstructive or disruptive social or personal behaviors can sometimes be used to achieve a constructive outcome.

Hoare logic

Hoare logic (also known as Floyd–Hoare logic or Hoare rules) is a formal system with a set of logical rules for reasoning rigorously about the correctness of computer programs. It was proposed in 1969 by the British computer scientist and logician Tony Hoare, and subsequently refined by Hoare and other researchers. The original ideas were seeded by the work of Robert W. Floyd, who had published a similar system for flowcharts. The central feature of Hoare logic is the Hoare triple.

Behavior modification

Behavior modification is an early approach that used respondent and operant conditioning to change behavior. Based on methodological behaviorism, overt behavior was modified with consequences, including positive and negative reinforcement contingencies to increase desirable behavior, or administering positive and negative punishment and/or extinction to reduce problematic behavior. It also used Flooding desensitization to combat phobias.

Positive behavior support

Positive behavior support (PBS) uses tools from applied behaviour analysis and values of normalisation and social role valorisation theory to improve quality of life, usually in schools. PBS uses functional analysis to understand what maintains an individual's challenging behavior and how to support the individual to get these needs met in more appropriate way, instead of using 'challenging behaviours'. People's inappropriate behaviors are difficult to change because they are functional; they serve a purpose for them.

Related lectures (40)

Hoare Logic: Postconditions and Preconditions

Covers Hoare logic, postconditions, preconditions, and program behavior proofs.

Converting Imperative Programs to Formulas

Explores converting imperative programs to formulas, including verification conditions, formula construction, and control flow structures.

Hoare Logic: Strongest Postcondition and Weakest Precondition

Introduces Hoare logic for simplifying program behavior proofs through annotations.

Loops: Control Statements and Functions

Covers modeling control statements with functions in Scala, including while loops, repeat loops, and for-loops translation.

Programming Missions: Starting with the Third Line MOOC: The Thymio robot as a tool for discovering digital science