Math 470 Spring ’05

HW #2 Solutions

Section 1.2

15. The induction on propositions will be replaced by ordinary induction on the stage or level n at which a proposition is built.

Base case: n = 0.

Induction step: Assume the claim is true for all propositions built by level n. Then prove it is true for propositions built by level n+1.

Any proposition built at level n+1 is either not P, where P is built at level n, or P * Q where P and Q are built by level n and * is ^, v, -> or <->.

Section 1.3

1. a) If V(A) = T, then V(A v not A) =T. If V(A) = F, then V(not A) = T, so V( A v not A) = T.

b) If V(A) = T, then V (((A->B) -> A) -> A) = T. If V(A) = F, then V(A->B) = T, so V((A->B)->A) = F. Then V(((A->B) -> A) -> A) = T.

2. a) A disjunction is false if and only if all the disjuncts are false.

b) A conjunction is false if and only at least one of the conjuncts is false.

4. a) The CNF has a single conjunct: (not A v not B v not C v D)

b) The CNF also has a single conjunct: (not A v not B v C v D)

5. i) Suppose P is in CN(S1). Then V(P) = T for any V making every proposition in S1 is true. If every proposition in S2 is true then every one in S1 is true because S1 C S2. So P is in CN(S2).

ii) If P is in S and V(S) = T for all S in S, then V(P) = T.

iii) If P is a tautology, then V(P) = T for any V, including any V that make all of S true.

iv) Cn(S) C Cn(Cn(S)) by ii). Now suppose P is in Cn(Cn(S)). Then V(P) = T for any V, making all of CN(S) true. Then V(P) = T for any V making all of S true. So P is in CN(S).

v) Suppose that S1 C S2 and V is in M(S2). This means that V(P) = T for all P in S2. Since S1 C S2, V(P) = T for all P in S1. So V is in M(S1).

vi) V(P) = T for all V in M(S) ó V(P) = T whenever V(S) = T for all S in S ó then P is in CN(S).

vii) If s is in CN( {s1, …, sn}) then V(s1) = … = V(sn) = T => V(s) = T. Then the truth table for (s1 -> … (sn -> s) is all T, so the formula is a tautology.

If the formula is a tautology, and V(s1) = … = V(sn) = T, then V(s) = T. So s is in CN( {s1, …, sn}).

Section 1.4

1. a) F((A v A) <-> A)

/ \

F(A v A) T(A v A)

| |

TA FA

| |

FA / \

| TA TA

FA

All paths are contradictory.

b) F((A ^ A) <-> A)

/ \

F(A ^ A) T(A ^ A)

| |

TA FA

/ \ |

FA FA TA

|

TA

All paths are contradictory.

c) F((A ^ B) <-> (B ^A))

/ \

F(A ^ B) T( A^B)

| |

T(B ^ A) F(B ^A)

/ \ |

FA FB TA

| | |

TB TB TB

| | / \

TA TA FB FA

All paths are contradictory.

d) F((A v B) <-> (B vA))

/ \

F(A v B) T( AvB)

| |

T(B v A) F(B vA)

| / \

FA TA TB

| | |

FB FB FB

/ \ | |

TB TA FA FA

All paths are contradictory.

3. a) F(A ->A)

|

TA

|

FA

b) Done in class.

c) F( (A -> B) -> ((B -> C) -> (A ->C)))

|

T( A -> B)

|

F((B -> C) -> (A ->C))

|

T(B -> C)

|

F( A-> C)

|

TA

|

FC

/ \

FA TB

/ \

FB TC

All paths are contradictory.

d) Done in class.

5. a) F(not(A v B) <-> (not A ^ not B))

/ \

T(not(A v B)) F(not(A v B))

| |

F(not A ^ not B) T(not A ^ not B)

| |

F( A v B)

| T( (A v B))

FB |

| T not A

FA |

/ \ T not B

F(not A) F(not B) |

| | F A

TA TB |

FB

/ \

TA TB

All paths are contradictory.

b) similar to a.

8. F (not (A ^ not A)

|

T ( A ^ not A)

|

TA

|

T not A

|

FA

10. a)( ( A -> B) -> ( A - > C) ) ^ ((A-> C) -> (A -> B))

(( not ( A -> B)) v ( A -> C) ) ^ (( not ( A -> C)) v ( A -> B) )

( ( A ^ not B) v ( not A v C)) ^ ( ( A ^ not C) v ( not A v B))

DNF : (not A) v (B ^ C) v (not B ^ not C)

CNF: ( not A v C v not B) ^ (not A v B v not C)

b) not ( A < -> B) v ( C v D)

DNF: ( A ^ not B) v (not A ^ B) v (C) v (D)

CNF: (A v C V D V B) ^ ( not B v C v D v not A)