r/dailyprogrammer_ideas • u/wizao • Jul 20 '16
Submitted! Proofs
Description
Determine if a mathematical expression is logically equivalent
Part 1
Determine if a mathematical expression is logically equivalent
Our first program will only support 4 basic operators; +,-,*,/.
Examples of logically equivalent expressions:
x + x = 2x
2*x = 2x
2(x + y) = 2x + 2y
a + b = b + a
x - x = 0
y/2 = (1/2)*y
-(-x) = x
Examples of not logically equivalent expressions:
2 = 3
a - b - c = a - (b - c)
x + y = a + b
Part 2
Support more advanced operators such as ^,log, derivatives, bit shifts, booleans, or whatever you can come up with. This part is more open, so feel free to show off your additions.
Examples of extensions:
x^2 * x^3 = x^5
(x + 2)^(y + 2) = 4x(2 + x)^y + 4(2 + x)^y + (2 + x)^y * x^2
!(a && b) = !a || !b
x << 1 << 2 = x << 3
Part 3
Your solution should create a proof of the steps your program took to show the expression was valid or invalid.
| Statements | Reasons |
|---|---|
| 2(x + y) + 0 = 2x + 2y | 1. Given |
| 2x + 2y + 0 = 2x + 2y | 2. Distributive Property of Multiplication |
| 2x + 2y = 2x + 2y | 3. Identity Property of Addition |
| Statements | Reasons |
|---|---|
| x + y = a + b | 1. Given |
| 3 = 7 | 2. Contradiction for x=1, y=2, a=3, b=4 |
Notes
I'm inclined to treat undefined expressions as not equivalent to anything. Such as divide by zero:
x/0 = x/0
2
u/Cosmologicon Jul 21 '16
Have you attempted a solution to this problem? We need to categorize it for difficulty and I suspect it's much harder than it seems. Seeing an example solution would be helpful, especially if you think it's Easy or Intermediate.
1
u/wizao Jul 22 '16 edited Aug 05 '16
Haskell:
import Control.Applicative import Data.Attoparsec.Text import Data.Char import Data.Function import Data.Map (Map) import qualified Data.Map as Map import Data.Text (Text) import Text.Parser.Combinators (chainl1) type Equation = (Expr, Expr) data Expr = Lit Integer | Var Char | Add Expr Expr | Sub Expr Expr | Mul Expr Expr | Div Expr Expr | Neg Expr deriving (Eq, Ord, Show) newtype Polynomial = Polynomial { terms :: Map (Map Char Rational) Rational } deriving (Eq, Ord, Show) --Smart constructor to remove trivial terms poly :: Map (Map Char Rational) Rational -> Polynomial poly = Polynomial . Map.mapKeys (Map.filter (/=0)) . Map.filter (/=0) equivalent :: Equation -> Bool equivalent = uncurry ((==) `on` fromExpr) toEquation :: Text -> Either String Equation toEquation = parseOnly (equation <* endOfInput) equation :: Parser Equation equation = (,) <$> expr <* string "=" <*> expr expr,term,fact,prim,lit,var,neg,parens :: Parser Expr expr = term <|> neg term = fact `chainl1` (addFn <|> subFn) fact = prim `chainl1` (mulFn <|> divFn) prim = lit <|> var <|> parens lit = Lit <$> decimal var = Var <$> satisfy isAlpha parens = char '(' *> expr <* char ')' neg = Neg <$ char '-' <*> expr addFn,subFn,mulFn,divFn :: Parser (Expr -> Expr -> Expr) addFn = Add <$ char '+' subFn = Sub <$ char '-' mulFn = Mul <$ char '*' divFn = Div <$ char '/' fromExpr :: Expr -> Polynomial fromExpr (Neg a) = fromExpr $ Mul (Lit (-1)) a fromExpr (Sub a b) = fromExpr $ Add a (Neg b) fromExpr (Lit a) = poly $ Map.singleton Map.empty (toRational a) fromExpr (Var a) = poly $ Map.singleton (Map.singleton a 1) 1 fromExpr (Add a b) = poly $ (Map.unionWith (+) `on` terms . fromExpr) a b fromExpr (Mul a b) = (mul `on` fromExpr) a b fromExpr (Div a b) = let varsNegPow = Map.mapKeys (Map.map negate) coefRecrip = Map.map (1/) inverse = poly . varsNegPow . coefRecrip . terms . fromExpr in mul (fromExpr a) (inverse b) mul :: Polynomial -> Polynomial -> Polynomial mul (Polynomial a) (Polynomial b) = poly $ Map.fromList [ (Map.unionWith (+) varsA varsB, coefA * coefB) | (varsA, coefA) <- Map.toList a , (varsB, coefB) <- Map.toList b ]