Propositional Logic in Scala

Question

The type Prop models propositional sentences (or, more concisely, propositions). Propositional symbols (variables) are encoded as terms of the form P(n) where n is an integer identifier. The type Interpr implements propositional interpretations as a Scala list of propositional symbol ids (with no repetitions). A propositional symbol P(n) is meant to be true in an interpretation i if and only if n occurs in i.

Write a Scala method meaning(i:Interpr, p:Prop):Boolean that takes an interpretation i and a proposition p, and returns the Scala Boolean value true if the interpretation satisfies the proposition according to the semantics of propositional logic, and returns the value false otherwise.

I am confused as to how I can implement this using pattern matching and recursion. Any guidance would be appreciated!

// Example case
meaning(List(1,2), And(P(1), P(2))) is true

// Example case
meaning(List(1), And(P(1), P(2))) is false




type PVar = Int

type Interpr = List[PVar]

sealed abstract class Prop
case object True extends Prop
case object False extends Prop
case class P(id: PVar) extends Prop                  // propositional         variable
case class Not(sub: Prop) extends Prop
case class Or(sub1: Prop, sub2: Prop) extends Prop   // inclusive or
case class Xor(sub1: Prop, sub2: Prop) extends Prop  // exclusive or
case class And(sub1: Prop, sub2: Prop) extends Prop
case class Impl(sub1: Prop, sub2: Prop) extends Prop // simple implication =>
case class Iff(sub1: Prop, sub2: Prop) extends Prop  // double implication <=>


sealed abstract class Answer
case object Yes extends Answer
case object No extends Answer

def meaning(i: Interpr, p: Prop): Boolean = p match {
    // solution here
}

"// solution here" Stack Overflow, the new do-your-homework service — pedrofurla
Come on, show us what you've tried or what you're thinking about a solution. It's an assignment, you're supposed to learn from it. What's the point in just submitting someone else's solution? — The Archetypal Paul

Utsav Utsav · Accepted Answer · 2017-03-08T04:37:08

I am confused as to what exactly you require. Should the method meaning be able to evaluate compound propositions as well ? How exactly is List(1,2) getting evaluated to true ?

However regarding your question on evaluation using recursion I would suggest that you have a look at Philip Wadler's paper Monads for functional programming

http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf

This is one of the best examples on writing expression evaluator in functional languages.

Propositional Logic in Scala

1 Answers