Karnaugh Mapping with Two Outputs?
I beleive that you will need to do two Karnaugh maps; one for each output.  After you have done the two maps, you can see if there are any common terms that can be used in a solution for both outputs.