I see from your pics above, that your using 'PC Linux OS' live to boot the PC.
Are you getting reboots using the live CD? (I may have missed this part in your postings
)
There will be logs generated with PC Linux....but as it's a live CD they will not be kept if the PC has rebooted.
Have you replaced the "TIM" on the cpu? (Thermal paste) this can dry out leading to poor contact, which in turn causes the cpu to overheat.
Like Chrysalis it's looking like a cpu problem, if it were Ram the PC would simply lock up.
Power supplies tend to suffer from lack of 5v rail, which in turn randomly turns the PC on and not at other times.
As you've already swapped this out, that's another idea in the bin.
Have you put a new graphics card in? or are you using the onboard graphics?