CODEWITHSUNDEEP
scalaartificial-intelligence
Moe Walid
Moe Walid

Reputation: 9

Propositional Logic in Scala

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
}

Upvotes: 0

Views: 283

Answers (1)

Utsav
Utsav

Reputation: 566

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.

Upvotes: 1

Related Questions