1.        The game "Connect 4" can be solved exactly. Yet, people still work on developing
the "optimal" heuristics. Why would anyone do this? 

A cynical response to this question is that they wanted to get published. Developing
an optimal heuristic that performs significantly better than anyone else?s will
probably get you published somewhere. Getting published means you get to keep your
job. A less cynical response is that developing an optimal heuristic might lead to
some new insight (or new insights might lead to a good heuristic) that could advance
the AI field or potentially the game play of connect four?like the advanced
Neurogammon program did for backgammon. I doubt people play connect four as
competitively as backgammon, but it is possible? 

2.        Are there problems that cannot be solved using propositional logic? If yes,
describe one. If no, why not? 

I think that there are problems that cannot be solved using propositional logic.
Because propositional logic can only accept states that are True, False, or Unknown,
a problem or model that cannot be represented by those things will not be solvable.
A book used the example of a work with probability states instead of T or F, and one
could argue that we could have each probability be its own state, but probability is
a real number, so there would be unaccountably infinite number of states which
doesn?t seem like it could be plausibly represented with any circuit or set of
functions. An example of a problem like this would be a text-learning/recognizing
program. There are a ton of different sentences, and by keeping a lot of
probabilities we can use it to recognize English text, but a propositional logic
solution would be too huge and difficult to create to actually ?solve? this problem.