For convenience to the user, the first check should be done using JavaScript on the browser. Give all of the relevant checkboxes an onchange= event handler that calls a JavaScript function. This function should check the relevant checkboxes (parts of it would probably need to be written by PHP if the list of cars is dynamically generated) and e.g. disable the submit button if the necessary criteria aren't met.
Alternatively, replace the onchange= handlers with a single onsubmit= handler in the <form> itself to do the validation when the user attempts submission.
Either way, for safety's sake and the sake of non-JavaScript-enabled browsers, you'll still want to check server-side as well, checking the submitted form for consistency and responding accordingly.
The values of the submitted $cars[] array are the names of the cars, and they'll be in relative order [thinks: is this guaranteed? Not sure ... unthinks]. That is to say, if the user has checked
[X] car 1
[ ] car 2
[X] car 3
Then $cars[0]='car 1'; $cars[1]='car 3';. That's what you will have to examine to see if the submitted details are consistent.
I'm afraid after that it's all a bunch of if () statements. Things like
if(in_array('car 1',$cars) && in_array('car 3',$cars) && !in_array('car 2',$cars)){
...
}
[thinks: that will work even if the relative order is not preserved ... unthinks]
If the consistency criteria are dynamic as well as the list of cars themselves then things get a lot hairier and I'll need quite a few more [thinks] :-)