--- 1 --- |= F<->G iff |= F->G and |= G->F iff (by deduction theorem) F |= G and G |= F iff Models(F) \subseteq Models(G) and Models(G) \subseteq Models(F) iff Models(F) = Models(G) iff F equiv G --- 2 --- Express all connectives by - and &. E.g.: A | B = -(-A & -B) by De Morgan's laws A -> B = -A | B = -(A & -B) ... Other minimal functionally complete sets: {or, not} {imp, not} nand is functionally complete so is nor --- 3 --- (a) a&b | c&d = (a&b | c) & (a&b | d) = (a|c) & (b|c) & (a|d) & (b|d) (c) d g -sp -st | d g -sp r | d g g -st | d g g r | d -ra -sp -st | d -ra -sp r | d -ra g -st | d -ra g r proof: d & (g|-ra) & (-sp|g) & (-st|r) = (d&g) | (d & -ra) & (-sp|g) & (-st|r) = (d&g) | (d & -ra) & (-sp|g) & (-st|r) = (d&g&(-sp|g) | d&-ra&(-sp|g))& (-st|r) = (d&g&-sp| d&g&g | d&-ra&-sp| d&-ra&g)& (-st|r) = (d&g&-sp& (-st|r) | d&g&g& (-st|r) | d&-ra&-sp& (-st|r) | d&-ra&g& (-st|r)) = starting formula --- 4 --- d <- g <- ra g <- sp r <- st M0 = {} M1 = T(M0) = {d} M2 = T(M1) = {d} = M Then g does not hold. --- 5 --- (. stands for open box) a) 1 . P & -P (assumption) 2 . P (and elimination 1) 3 . -P (and elimination 1) 4 . bottom (contradiction 2+3) 5 -(P & -P) (negation introduction 1+4) b) 1 -P 2 . -Q (assumption) 3 .. P (assumption) 4 .. bottom (contradiction 1+3) 5 . -P (negation introduction 3+4) 6 P->Q (contraposition 2+5)