

![0_image_0.png](0_image_0.png)

Proof: We give the proof for preferred B extensions only. The proof for preferred BH extensions is similar. The proof is by reduction from propositional satisfiability to the complement of the problem. Let I 
m  be a set of propositional clauses and the set of propositional variables occurring in .  Let     be an injective function that maps each clause to a propositional variable   =   ( ) such that   /   . Define the default theory A =
and priorities P on as follows.

![0_image_1.png](0_image_1.png)

