You could wire the power to the PLC through the normally closed contact of a relay, and wire the relay coil to a PLC output. If the PLC ever turns on that output, it cuts power to itself.
Mind you, if someone asked me to implement this for a PLC, my very first question would be "why?"
If I was presented with a good enough reason to *actually* do this, I'd use a delay-off timer instead of a relay. Because with a straight relay, the split second you open that contact, the power will be removed from the coil of the relay, and thus restored to the PLC. A compact logix PLC, for example, takes around 5-10 seconds from loss of power until all the LED's on the front go off - during this time it's using stored energy to perform necessary shutdown tasks. Repeatedly restoring power to is while it's in this state is probably not a nice way to treat your PLC. If you had a delay off timer that has power applied at all times and is simply triggered by your PLC output, then you can set it up so that as soon as it received the trigger it opens the circuit powering the PLC, which also removes the trigger. But then because the timer still has power applied, just not to the trigger, it can hold the contacts open for another 10-20 seconds to make sure it's fully powered down, before closing them and powering the PLC back up.
Edit: Man, beaten to the punch by no less than five people this morning!