How can you deal with a puzzle where some or all of the statements are falsehoods?
Actually, it's not too bad. A known lie is just as useful as a known truth. You just have to think about what the opposite of the false statement is. For example, if you know that the statement "Either chest A or B contains gold" is false, then you know that "neither chest A nor chest B can contain gold."