other exercises: 20241205_DiskMat_Serie11.pdf
11.4 b)
We know that is a complete and sound proof system. Let , be arbitrary. Let be a proof system where
We will now show that is sound and complete.
soundness Let and be arbitrary. For any statement where , at least two of are equal to (def ). Since is sound, this implies that for each where , (def soundness). Thus, at least two of are equal to . This implies (def ). Therefore, is sound.
completeness Let be any statement where . This means that at least two of are equal to (def ). Since is complete, for at least two where , there exists such that (def. completeness). Choose . Thus, (def ), and is complete (def completeness).
11.4 b)
We know that is a complete and sound proof system. Let be arbitrary. Let be a proof system where
Since , also . We will now show that is sound and complete.
soundness For any statement where , (def ). Since is complete, this implies that (def soundness). Thus (def ), proving that is sound (def soundness).
completeness For any statement where , (def ). Since is sound, for any . (def soundness). Thus, (def ), thus proving that is complete (def completeness).