uni/inf1080/hw3.md

Innlevering 3

4.8

D) ((P \to Q) \land \lnot Q) \to \lnot P

P	Q	(P \to Q)	\lnot Q	\lnot P	((P \to Q) \land \lnot Q) \to \lnot P
1	1	1	0	0	(1 \land 0) \to 0: 0 \to 0: 1
1	0	0	1	0	(0 \land 1) \to 0: 0 \to 0: 1
0	1	1	0	1	(1 \land 0) \to 1: 0 \to 1: 1
0	0	1	1	1	(1 \land 1) \to 1: 1 \to 1: 1

(((P \to Q) \land \lnot Q) \to \lnot P) er en tautologi; for alle kombinasjoner av variablene blir formelen 1.

E) \lnot (P \lor Q) \land (\lnot Q \lor R) \land (\lnot R \lor P)

P	Q	R	\lnot (P \lor Q)	(\lnot Q \lor R)	(\lnot R \lor P)	\lnot (P \lor Q) \land (\lnot Q \lor R) \land (\lnot R \lor P)
1	1	1	0	-	-	0
1	1	0	0	-	-	0
1	0	1	0	-	-	0
1	0	0	0	-	-	0
0	1	1	0	-	-	0
0	1	0	0	-	-	0
0	0	1	1	1	0	0
0	0	0	1	1	1	1

(\lnot (P \lor Q) \land (\lnot Q \lor R) \land (\lnot R \lor P)) er hverken en tautologi eller en kontradiksjon, siden det finnes både variabelkombinasjoner hvor den er sann og kombinasjoner hvor den er usann.

\pagebreak

F) (\lnot (P \lor Q)) \land P

P	Q	R	\lnot (P \lor Q)	(\lnot (P \lor Q)) \land P
1	1	1	0	0 \land 1: 0
1	1	0	0	0 \land 1: 0
1	0	1	0	0 \land 1: 0
1	0	0	0	0 \land 1: 0
0	1	1	0	0 \land 0: 0
0	1	0	0	0 \land 0: 0
0	0	1	1	1 \land 0: 0
0	0	0	1	1 \land 0: 0

((\lnot (P \lor Q)) \land P) er en kontradiksjon, siden det ikke finnes noen kombinasjon av variablene som gjør den sann.

5.5

• Påstand: Hvis (P \to Q) og (Q \to R) er sanne, så er (P \to R) sann

A) Direkte bevis:

Vi vet at det eneste tilfellet hvor (P \to R) er usann er hvis P er sann og R er usann. Derfor må vi bevise at hvis P er sann, er R sann.

Når (P \to Q) er sann, og P er sann, må Q være sann. Når (Q \to R) er sann, og Q er sann, må R være sann. Da vet vi at når P er sann, og (P \to Q) er sann, og (Q \to R) er sann, må R være sann. Siden det eneste tilfellet hvor (P \to R) er usann er at P er sann og R er usann, vet vi at (P \to R) er sann hvis (P \to Q) og (Q \to R) er sanne.

C) Motsigelsesbevis:

Anta at P er sann og R er usann, den eneste kombinasjonen som gjør (P \to R) usann. Da vet vi at Q er usann (den eneste måten (Q \to R) er kan være sann hvis R er usann), som betyr at P er usann (den eneste måten (P \to Q) kan være sann hvis Q er usann). Dette motsier antagelsen om at P er sann.

Contradiction!