회사에서 A직원이 병역기피 의심되는데 해고 처리하면 부당해고 예고수당을 지급해야 되나요?

회사에서 6개월 근속한 A직원이 입사 당시 허리 디스크로 인한 면제라고 말씀을 하고 입사를 하셨는데

병역증명서 발급 요청을 드렸을 때, 허리디스크가 아닌, 십자인대 파열이다. 등 예전과 다른 답변을 하셨습니다.

그로 인해서 정신질환으로 인한 병역 기피로 의심되는 상황이에요. 이로 인해서 해고 처리 시, 부당 해고에 해당 하는건가요?

아니면 해고 예고의 의무를 지켜야 되나요?