<!doctype
html public "-//w3c//dtd html 4.0 transitional//en">
Mathematics 470 Spring 2005
7 problems worth 15 points each.
1. Find
CNF and DNF for each of the following formulas
a. (
A <-> B ) <-> C
CNF: (ØA v ØB
v C) ^ ( Av ØB v ØC) ^ (ØA
v B v ØC) ^ (A v B V C)
DNF:
(A ^ B ^ C) v (A ^ ØB
^ ØC) v (ØA ^ B ^ ØC)
v (ØA ^ ØB ^ C)
b. (A
^ C ) <-> (B ^ C)
CNF: (ØA v B v ØC)
^ (A v ØB v ØC)
DNF:
(A ^ B) v (A ^ ØB ^ ØC) v (ØA
^ B ^ ØC) v (ØA ^ ØB)
2a. Show that ¯ or NOR defined by
|
a |
b |
a ¯ b |
|
T |
T |
F |
|
T |
F |
F |
|
F |
T |
F |
|
F |
F |
T |
is adequate. ØA ó (A¯ A)
A v B ó Ø( A ¯
B) ó ( ( A ¯ B) ¯ ( A ¯ B) )
Since {Ø,v} is adequate, this shows that {¯} is adequate.
b. Show that if F is a binary connective and F is adequate, then F(P, P) ~ ¬P.
We have seen that F (T, T) must = F since otherwise, any repeated applications
of F, would continue to return
T. Similarly F (F, F) must = T.
This makes F(P,
P) ~ ¬P.
c. Use this to conclude that | and ¯ are the only adequate binary connectives.
Of the 16 possible binary connectives, there are only 4 satisfying
the above condition. They are ¯, |, ØP and ØQ.
The last two ignore one of their arguments and thus could not be used to
express ^ or v or any connective using both arguments.
3. Find Cn(S) and M (S) for
each of the following:
a. S = { A -> B, ØB}
Cn = S
U {ØA} U Taut. M = {V | V(A) = V(B) = F}
b. S = {A
-> B, A, ØB}
Cn = {all propositions}. M = F
4. (( A v B) ^ C) <->( (A v C) ^ (B v C) )
F(( A v B) ^ C) <->( (A v C) ^ (B v
C) )
/
\
T(( A v B) ^ C)) F((
A v B) ^ C)
F(A v C) ^ (B v C) T(A
v C) ^ (B v C)
T (AvB)
T(Av
C)
TC
T(B v C)
/
\
/ \
F(A v
C) F(B v C)
F(A v B) FC
FC FC
FA
/ \
X
X
FB
TA TB
TC
The given proposition is not
valid. It is false when V(A) =
V(B) = T and V(C) = F
and also when V(A) = V(B) = F
and V(C) = T.
5. ( (A-> B) -> (A -> C) ) -> ( A -> ( B -> C) )
F( (A-> B) -> (A -> C) ) -> ( A ->
( B -> C) )
T ( (A-> B) -> (A -> C) )
F ( A -> ( B -> C) )
TA
F (B-> C)
TB
FC
/ \
F(A -> B)
T(B->C)
TA
/ \
FB FB TC
X X X
All paths are contradictory,
so the given proposition is valid.
6. ( A -> ( B -> C) ) -> ( ( A -> B) -> C )
F ( A -> ( B -> C) ) -> ( ( A -> B) -> C )
T ( A -> ( B -> C) )
F ( ( A -> B) -> C )
T (A->B)
F C
/
\
FA
T(B->C)
/ \
/ \
FA TB FB TC
/ \ X
FA TB
X
The given proposition is not
valid. It is false when V(A) = F
and V(C) = F.
7. ( ( A ->
B) -> C ) -> ( A -> ( B -> C) )
F( ( A -> B)
-> C ) -> ( A -> ( B -> C) )
T(
( A -> B) -> C )
F ( A -> ( B -> C) )
TA
F(B->C)
TB
FC
/ \
F(A ->B)
TC
TA
X
FB
X
All paths are contradictory,
so the given proposition is valid.