Eu tenho uma visão bem particular, e gosto de conversar com as pessoas sobre isso. Abordo melhor minha visão aqui.
Tem uma palestra interessante no Youtube que defende que lógica de programação não existe. Mesmo discordando do ponto geral e achar que há utilidade prática em dizer que há uma lógica de programação, é interessante notar que de fato, não há uma definição formal do termo. Se quisermos defini-la como tal, devemos resolver certos tópicos: o que seria lógica de programação? No que ela se diferencia da lógica matemática, lógica aristotélica e outras lógicas formais? Frequentemente se diz que a lógica de programação é independente de linguagem, mas como argumentei no texto que linkei acima, o ser humano precisa de linguagem para pensamentos complexos. Você pode tentar evitar usar linguagens formais de programação e usar linguagens mais complexas como a linguagem natural para este objetivo, mas isso não te faz independente de linguagem, te faz dependente de linguagem natural, o que na prática é pior, pois não programamos em linguagem natural. Por isso vejo que um estudo da tal lógica de programação deve vir acompanhado do estudo de uma, e se possível, várias linguagens de programação. Entender como cada uma delas apresentam recursos para expressar conceitos abstratos. Saber diferencia-las mas também compara-las para entender o que elas tem em comum, pode ser a chave para separar o conceito da linguagem.
No geral, como você mesmo disse, há diferenças entre a programação funcional, como em Haskell, e programação imperativa no geral, isso é uma distinção bem perspicaz. Compara-las talvez seja a chave para chegarmos ao tal fundamento que definiria lógica de programação como lógica formal. Acontece, que há argumentavelmente mais diferenças do que semelhanças, ao menos de forma superficial. No geral, a subtância comum dos dois casos, parece nos levar ao conceito matemático de função (mesmo a programação imperativa), a computação trabalha com o que é chamado de funções computáveis. Portanto, a lógica de programação seria o estudo do raciocínio correto que compreende, modela e resolve funções computáveis? Se for o caso, o que distingue a lógica de programação de lógica matemática? No fim, a primeira parece ser um subconjunto da segunda. Não me parece coincidência que grande parte dos nomes da computação e programação eram matemáticos, como John von Neumann, Alan Turing, Alonso Church, Donald Knuth, John Backus e a que é considerada por muitos como a primeira programadora da história (há quem discorde), Ada Lovelace. Inclusive, se for analisar o tal primeiro programa feito por Lovelace, ela não usa nada que se assemelhe a uma linguagem de programação moderna, mas sim, um diagrama com linguagem algébrica.
Um aviso é que não tenho estudo formal na área de matemática, filosofia ou lógica. Apenas expresso pensamentos que tenho usando o conhecimento limitado que tenho sobre estes. Eu gosto de compartilhar minha visão com os outros para que elas compartilhem as suas e eu possa enriquecer meu próprio pensamento. No geral, se o dono do post ou outros quiserem comentar sobre ficaria muito feliz :)