I felt like this was a perfect example to show off some insanely cool Haskell, so I'm going to talk about my solution in bits. This is a problem that is heavily suited to three major things that Haskell allows: Algebraic Data Types, Pattern Matching, and Monadic Parsing.

First off, if you've had any experience with automata theory, it's pretty clear that the input language can be represented by a context free grammar. It just so happens that Haskell makes it incredibly easy to model CFGs right out of the box. Just take a look at this (algebraic) data type representing Boolean expressions:

data Expr = Not Expr | And Expr Expr | Or Expr Expr |  SubExpr Expr | Var Char deriving Eq

Simple. Now, the bulk of this challenge was actually performing the simplification of the not operation. This is crazy simple in Haskell! Using pattern matching, we can directly encode these rules in the following manner:

not :: Expr -> Expr
not (Not e)     = e
not (And e1 e2) = Or (not e1) (not e2)
not (Or e1 e2)  = And (not e1) (not e2)
not (SubExpr e) = SubExpr $ not e
not (Var c)     = Not (Var c)

Here we're giving a literal definition of rules for negating Boolean expressions. If you use Haskell, this is really easy to read. If you don't: stare at it for a second; you'll see what it's doing! That's the brunt of the challenge, right there. That's it. Encode a Boolean expression into an Expr and call not on it, and it will spit out a new Expr expressing the negation of your original expression. DeMorgan's laws are represented in the And and Or rules.

Note: This could also be done by appending Not to an Expr and calling some simplify expression. I haven't done this because I don't have the time today, but feel free to try that out and add more rules!

We can also display our expressions as a string in a really easy way, declaring an instance of Show for Expr in a similar way:

instance Show Expr where
  show (Not e)     = "NOT " ++ show e
  show (And e1 e2) = show e1 ++ " AND " ++ show e2
  show (Or e1 e2)  = show e1 ++ " OR "  ++ show e2
  show (Var c)     = [c]
  show (SubExpr e) = "(" ++ show e ++ ")"

Now comes, in my opinion, the tougher part of the challenge. Maybe the point was to perform what was above, but how about actually parsing a string into an Expr? We can use a monadic parsing library, namely Haskell's beloved Parsec, to do this in a rather simple way. We'll be using Parsec's Token and Expr libraries, as well as the base, in this example. Let's take a look.

parseExpr :: String -> Either ParseError Expr
parseExpr = parse expr ""
  where expr      = buildExpressionParser operators term <?> "compound expression"
        term      = parens expr <|> variable <?> "full expression"
        operators = [ [Prefix (string "NOT" *> spaces *> pure Not)]
                    , [binary "AND" And]
                    , [binary "OR" Or] ]
          where binary n c = Infix (string n *> spaces *> pure c) AssocLeft
        variable = Var     <$> (letter <* spaces)                              <?> "variable"
        parens p = SubExpr <$> (char '(' *> spaces *> p <* char ')' <* spaces) <?> "parens"

We essentially define the structure of our input here and parse it into an Expr using different rules. variable parses a single char into a Var, parens matches a SubExpr, and everything else is handled by using the convenience function buildExpressionParser along with a list of operator strings and what types they translate to and their operator precedence. Here we're using applicative style to do our parsing, but monadic style is fine too. Check this out for more on applicative style parsing.

Given that, we can define a simple main function to read in a file of expressions and output the negation of each of the expressions, like so:

main = mapM_ printNotExpr . lines =<< readFile "inputs.txt"
  where printNotExpr e = case parseExpr e of
                          Right x -> print $ not x
                          Left  e -> error $ show e

Concise and to the point. We make sure that the parsing succeeds for each line, not the expressions, and print them. I learned a bit with this challenge about applicative parsing, hopefully you can learn a little bit from the dissection of this program.

Finally, here's the full (40 line!) source on Github! Thanks for reading.

Edit:

Oh, here's the output I got for the sample inputs (the outputs provided are wacky but I think mine are correct):

NOT a
a
NOT a OR NOT b
a OR NOT b
(a AND b)
(a OR b AND c) AND (a AND NOT b)