Translating English Sentences into Propositional Logic Statements¶

In a Logic course, one exercise is to turn an English sentence like this:

Sieglinde will survive, and either her son will gain the Ring and Wotan’s plan will be fulfilled or else Valhalla will be destroyed.

Into a formal Propositional Logic statement:

P ⋀ ((Q ⋀ R) ∨ S)

along with definitions of the propositions:

P: Sieglinde will survive
Q: Sieglinde’s son will gain the Ring
R: Wotan’s plan will be fulfilled
S: Valhalla will be destroyed

For some sentences, it takes detailed knowledge to get a good translation. The following two sentences are ambiguous, with different preferred interpretations, and translating them correctly requires knowledge of eating habits:

I will eat salad or I will eat bread and I will eat butter.     P ∨ (Q ⋀ R)
I will eat salad or I will eat soup  and I will eat ice cream. (P ∨ Q) ⋀ R

But for many sentences, the translation process is automatic, with no special knowledge required. I will develop a program to handle these easy sentences. The program is based on the idea of a series of translation rules of the form:

Rule('{P} ⇒ {Q}', 'if {P} then {Q}', 'if {P}, {Q}')

which means that the logic translation will have the form 'P ⇒ Q', whenever the English sentence has either the form 'if P then Q' or 'if P, Q', where P and Q can match any non-empty subsequence of characters. Whatever matches P and Q will be recursively processed by the rules. The rules are in order—top to bottom, left to right, and the first rule that matches in that order will be accepted, no matter what, so be sure you order your rules carefully. One guideline I have adhered to is to put all the rules that start with a keyword (like 'if' or 'neither') before the rules that start with a variable (like '{P}'); that way you avoid accidentally having a keyword swallowed up inside a '{P}'.

Consider the example sentence "If loving you is wrong, I don't want to be right." This should match the pattern 'if {P}, {Q}' with the variable P equal to "loving you is wrong". But I don't want the variable Q to be "I don't want to be right", rather, I want to have ～Q equal to "I do want to be right". So in addition to having a set of Rules to handle the 'if {P}, {Q}' patterns, I will also have a list of negations to handle "don't" and the like.

Here is the code to process Rule definitions (using regular expressions, which can sometimes be confusing.).

In [1]:

import re

def Rule(output, *patterns):
    "A rule that produces `output` if the entire input matches any one of the `patterns`." 
    return (output, [name_group(pat) + '$' for pat in patterns])

def name_group(pat):
    "Replace '{Q}' with '(?P<Q>.+?)', which means 'match 1 or more characters, and call it Q'"
    return re.sub('{(.)}', r'(?P<\1>.+?)', pat)
            
def word(w):
    "Return a regex that matches w as a complete word (not letters inside a word)."
    return r'\b' + w + r'\b' # '\b' matches at word boundary

Let's see what a rule looks like:

In [2]:

Rule('{P} ⇒ {Q}', 'if {P} then {Q}', 'if {P}, {Q}'),

Out[2]:

(('{P} ⇒ {Q}',
  ['if (?P<P>.+?) then (?P<Q>.+?)$', 'if (?P<P>.+?), (?P<Q>.+?)$']),)

And now the actual rules. If your sentence is not translated correctly, you can attempt to augment these rules to handle your sentence.

In [3]:

rules = [
    Rule('{P} ⇒ {Q}',         'if {P} then {Q}', 'if {P}, {Q}'),
    Rule('{P} ⋁ {Q}',          'either {P} or else {Q}', 'either {P} or {Q}'),
    Rule('{P} ⋀ {Q}',          'both {P} and {Q}'),
    Rule('～{P} ⋀ ～{Q}',       'neither {P} nor {Q}'),
    Rule('～{A}{P} ⋀ ～{A}{Q}', '{A} neither {P} nor {Q}'), # The Kaiser neither ...
    Rule('～{Q} ⇒ {P}',        '{P} unless {Q}'),
    Rule('{P} ⇒ {Q}',          '{Q} provided that {P}', '{Q} whenever {P}', 
                               '{P} implies {Q}', '{P} therefore {Q}', 
                               '{Q}, if {P}', '{Q} if {P}', '{P} only if {Q}'),
    Rule('{P} ⋀ {Q}',          '{P} and {Q}', '{P} but {Q}'),
    Rule('{P} ⋁ {Q}',          '{P} or else {Q}', '{P} or {Q}'),
    ]

negations = [
    (word("not"), ""),
    (word("cannot"), "can"),
    (word("can't"), "can"),
    (word("won't"), "will"),
    (word("ain't"), "is"),
    ("n't", ""), # matches as part of a word: didn't, couldn't, etc.
    ]

Now the mechanism to process these rules. The key function is match_rule, which matches an English sentence against a rule. The function returns two values, a string representing the translation of the English sentence into logic, and defs, a dictionary of {Variable: "value"} pairs. If match_rule finds that the rule matches, it recursively calls match_rules to match each of the subgroups of the regular expression (the P and Q in if {P}, then {Q}). The function match_literal handles negations, and is where the defs dictionary actually gets updated.

In [4]:

def match_rules(sentence, rules, defs):
    """Match sentence against all the rules, accepting the first match; or else make it an atom.
    Return two values: the Logic translation and a dict of {P: 'english'} definitions."""
    sentence = clean(sentence)
    for rule in rules:
        result = match_rule(sentence, rule, defs)
        if result: 
            return result
    return match_literal(sentence, negations, defs)
        
def match_rule(sentence, rule, defs):
    "Match rule, returning the logic translation and the dict of definitions if the match succeeds."
    output, patterns = rule
    for pat in patterns:
        match = re.match(pat, sentence, flags=re.I)
        if match:
            groups = match.groupdict()
            for P in sorted(groups): # Recursively apply rules to each of the matching groups
                groups[P] = match_rules(groups[P], rules, defs)[0]
            return '(' + output.format(**groups) + ')', defs
        
def match_literal(sentence, negations, defs):
    "No rule matched; sentence is an atom. Add new proposition to defs. Handle negation."
    polarity = ''
    for (neg, pos) in negations:
        (sentence, n) = re.subn(neg, pos, sentence, flags=re.I)
        polarity += n * '～'
    sentence = clean(sentence)
    P = proposition_name(sentence, defs)
    defs[P] = sentence
    return polarity + P, defs
    
def proposition_name(sentence, defs, names='PQRSTUVWXYZBCDEFGHJKLMN'):
    "Return the old name for this sentence, if used before, or a new, unused name."
    inverted = {defs[P]: P for P in defs}
    if sentence in inverted:
        return inverted[sentence]                      # Find previously-used name
    else:
        return next(P for P in names if P not in defs) # Use a new unused name
    
def clean(text): 
    "Remove redundant whitespace; handle curly apostrophe and trailing comma/period."
    return ' '.join(text.split()).replace("’", "'").rstrip('.').rstrip(',')

For example:

In [5]:

match_rule("If loving you is wrong, I don't want to be right",
           Rule('{P} ⇒ {Q}', 'if {P}, {Q}'),
           {})

Out[5]:

('(P ⇒ ～Q)', {'P': 'loving you is wrong', 'Q': 'I do want to be right'})

Here are some more test sentences and a top-level function to handle them:

In [6]:

sentences = '''
Polkadots and Moonbeams.
If you liked it then you shoulda put a ring on it.
If you build it, he will come.
It don't mean a thing, if it ain't got that swing.
If loving you is wrong, I don't want to be right.
Should I stay or should I go.
I shouldn't go and I shouldn't not go.
If I fell in love with you,
  would you promise to be true
  and help me understand.
I could while away the hours
  conferrin' with the flowers,
  consulting with the rain
  and my head I'd be a scratchin'
  while my thoughts are busy hatchin'
  if I only had a brain.
There's a federal tax, and a state tax, and a city tax, and a street tax, and a sewer tax.
A ham sandwich is better than nothing 
  and nothing is better than eternal happiness
  therefore a ham sandwich is better than eternal happiness.
If I were a carpenter
  and you were a lady,
  would you marry me anyway?
  and would you have my baby.
Either Danny didn't come to the party or Virgil didn't come to the party.
Either Wotan will triumph and Valhalla will be saved or else he won't and Alberic will have 
  the final word.
Sieglinde will survive, and either her son will gain the Ring and Wotan’s plan 
  will be fulfilled or else Valhalla will be destroyed.
Wotan will intervene and cause Siegmund's death unless either Fricka relents 
  or Brunnhilde has her way.
Figaro and Susanna will wed provided that either Antonio or Figaro pays and Bartolo is satisfied 
  or else Marcellina’s contract is voided and the Countess does not act rashly.
If the Kaiser neither prevents Bismarck from resigning nor supports the Liberals, 
  then the military will be in control and either Moltke's plan will be executed 
  or else the people will revolt and the Reich will not survive'''.split('.')

import textwrap

def logic(sentences, width=80): 
    "Match the rules against each sentence in text, and print each result."
    for s in map(clean, sentences):
        logic, defs = match_rules(s, rules, {})
        print('\n' + textwrap.fill('English: ' + s +'.', width), '\n\nLogic:', logic)
        for P in sorted(defs):
            print('{}: {}'.format(P, defs[P]))

logic(sentences)

English: Polkadots and Moonbeams. 

Logic: (P ⋀ Q)
P: Polkadots
Q: Moonbeams

English: If you liked it then you shoulda put a ring on it. 

Logic: (P ⇒ Q)
P: you liked it
Q: you shoulda put a ring on it

English: If you build it, he will come. 

Logic: (P ⇒ Q)
P: you build it
Q: he will come

English: It don't mean a thing, if it ain't got that swing. 

Logic: (～P ⇒ ～Q)
P: it is got that swing
Q: It do mean a thing

English: If loving you is wrong, I don't want to be right. 

Logic: (P ⇒ ～Q)
P: loving you is wrong
Q: I do want to be right

English: Should I stay or should I go. 

Logic: (P ⋁ Q)
P: Should I stay
Q: should I go

English: I shouldn't go and I shouldn't not go. 

Logic: (～P ⋀ ～～P)
P: I should go

English: If I fell in love with you, would you promise to be true and help me
understand. 

Logic: (P ⇒ (Q ⋀ R))
P: I fell in love with you
Q: would you promise to be true
R: help me understand

English: I could while away the hours conferrin' with the flowers, consulting
with the rain and my head I'd be a scratchin' while my thoughts are busy
hatchin' if I only had a brain. 

Logic: (P ⇒ (Q ⋀ R))
P: I only had a brain
Q: I could while away the hours conferrin' with the flowers, consulting with the rain
R: my head I'd be a scratchin' while my thoughts are busy hatchin'

English: There's a federal tax, and a state tax, and a city tax, and a street
tax, and a sewer tax. 

Logic: (P ⋀ (Q ⋀ (R ⋀ (S ⋀ T))))
P: There's a federal tax
Q: a state tax
R: a city tax
S: a street tax
T: a sewer tax

English: A ham sandwich is better than nothing and nothing is better than
eternal happiness therefore a ham sandwich is better than eternal happiness. 

Logic: ((P ⋀ Q) ⇒ R)
P: A ham sandwich is better than nothing
Q: nothing is better than eternal happiness
R: a ham sandwich is better than eternal happiness

English: If I were a carpenter and you were a lady, would you marry me anyway?
and would you have my baby. 

Logic: ((P ⋀ Q) ⇒ (R ⋀ S))
P: I were a carpenter
Q: you were a lady
R: would you marry me anyway?
S: would you have my baby

English: Either Danny didn't come to the party or Virgil didn't come to the
party. 

Logic: (～P ⋁ ～Q)
P: Danny did come to the party
Q: Virgil did come to the party

English: Either Wotan will triumph and Valhalla will be saved or else he won't
and Alberic will have the final word. 

Logic: ((P ⋀ Q) ⋁ (～R ⋀ S))
P: Wotan will triumph
Q: Valhalla will be saved
R: he will
S: Alberic will have the final word

English: Sieglinde will survive, and either her son will gain the Ring and
Wotan's plan will be fulfilled or else Valhalla will be destroyed. 

Logic: (P ⋀ ((Q ⋀ R) ⋁ S))
P: Sieglinde will survive
Q: her son will gain the Ring
R: Wotan's plan will be fulfilled
S: Valhalla will be destroyed

English: Wotan will intervene and cause Siegmund's death unless either Fricka
relents or Brunnhilde has her way. 

Logic: (～(R ⋁ S) ⇒ (P ⋀ Q))
P: Wotan will intervene
Q: cause Siegmund's death
R: Fricka relents
S: Brunnhilde has her way

English: Figaro and Susanna will wed provided that either Antonio or Figaro pays
and Bartolo is satisfied or else Marcellina's contract is voided and the
Countess does not act rashly. 

Logic: ((((P ⋁ Q) ⋀ R) ⋁ (S ⋀ ～T)) ⇒ (U ⋀ V))
P: Antonio
Q: Figaro pays
R: Bartolo is satisfied
S: Marcellina's contract is voided
T: the Countess does act rashly
U: Figaro
V: Susanna will wed

English: If the Kaiser neither prevents Bismarck from resigning nor supports the
Liberals, then the military will be in control and either Moltke's plan will be
executed or else the people will revolt and the Reich will not survive. 

Logic: ((～PQ ⋀ ～PR) ⇒ (S ⋀ (T ⋁ (U ⋀ ～V))))
P: the Kaiser
Q: prevents Bismarck from resigning
R: supports the Liberals
S: the military will be in control
T: Moltke's plan will be executed
U: the people will revolt
V: the Reich will survive

That looks pretty good! But far from perfect. Here are some errors:

Should I stay etc.:
questions are not propositional statements.
If I were a carpenter:
doesn't handle modal logic.
nothing is better:
doesn't handle quantifiers.
Either Wotan will triumph and Valhalla will be saved or else he won't:
gets 'he will' as one of the propositions, but better would be if that referred back to 'Wotan will triumph'.
Wotan will intervene and cause Siegmund's death:
gets "cause Siegmund's death" as a proposition, but better would be "Wotan will cause Siegmund's death".
Figaro and Susanna will wed:
gets "Figaro" and "Susanna will wed" as two separate propositions; this should really be one proposition.
"either Antonio or Figaro pays":
gets "Antonio" as a proposition, but it should be "Antonio pays".
If the Kaiser neither prevents:
uses the somewhat bogus propositions PQ and PR. This should be done in a cleaner way. The problem is the same as the previous problem with Antonio: I don't have a good way to attach the subject of a verb phrase to the multiple parts of the verb/object, when there are multiple parts.

I'm sure more test sentences would reveal many more types of errors.

There's also a version of this program that is in Python 2 and uses only ASCII characters; if you have a Mac or Linux system you can download this as proplogic.py and run it with the command python proplogic.py. Or you can run it online.