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).