If you read Dijkstra's letter it wasn't about formal proofs. It was about go to statements being very hard to reason about, especially when trying to understand the flow of a program and how you got to a particular point in its execution. The word "proof" doesn't even show up in the letter. It's only a page or so, well worth a read instead of guessing at what he may have been writing about.

http://www.u.arizona.edu/~rubinson/copyright_violations/Go_T...