Python Forum
propositional logic formula converter
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
propositional logic formula converter
#1
'''
Here is some short code which is rather self-contained and is somewhat difficult to write making it perfect for sharing. So here are the rules, hopefully you're familiar with the propositional logic formulas which look like this:


p → (q & r)

Things become much more difficult if the sentences which p, q and r stand for have words in them like 'something'. So, for example, 'if something is a man, then it is mortal'.  It is obvious that I can replace 'something' with 'Socrates' and get the conditional: 'if Socrates is a man, then he is mortal'.  What if you have something more complicated?  Suppose we want to define the word 'during'.  A reasonable definition might be:

event b [occurs] during period c iff period c has moment d and b [occurs] at d

We could then abbreviate the sentences as:

p = event b [occurs] during period c
q = period c has moment d
r = b [occurs] at d

which would give us:

p ≡ (q & r)

The problem with the above definition is the location of the word 'iff'. Suppose I believe falsely that:

event b [occurs] during [the entirety of] period c and period c has moment d and event b was not in progress at moment d.

It turns out that if we have to be able to switch the sentences around, like so:

If event b [occurs] during [all of] period c and period c has moment d then b [occurs] at d

But we can also do:

If period c has moment d and event b [occurs] at d then event b [occurs] during period c.

Now for pedagogical reasons I had to simplify things but for quite complicated reasons, we cannot do:

If period c has moment d then event b [occurs] at d and event b [occurs] during period c.

This is mostly because in the real definitions you don't put the words 'period' and 'event' in the sentence but just 'has' which would give us:

If c has d then b [occurs] at d and b [occurs] during c.

which of course is not true because c could be just a geometric shape and not a period. So  in any case we have to be able to handle sentences which move around between the ≡ → signs.  So here are the rules I've adopted, the following:

A sentence which is left of the ⊳ can only be right of the → sign if it is the only sentence to the right of the → sign.  Other than that every combination is possible

p ⊳ q ⊗ r

can be transformed into:

p → (q & r)
(p & r) → q
(p & q) → r
(q & r) → p

but not

(r → (p & q)
(q → (p & r)

because if p is to the right of → then it can be the only
sentence which appears to the right of →


We can also have any number of ⊗ signs, so we can also have

p ⊳ q ⊗ r ⊗ s

p ⊳ q ⊗ r ⊗ s ⊗ t

For the purposes of the following algorithm I simply number the sentences starting at 1.1 and number them 1.2, 1.3 and so on.  We then need to split the sentences into two categories and antecedent and a consequent.  So if we number the sentences as follows:

p = 1.1
q = 1.2
r = 1.3
s = 1.4

and if we have 4 sentences then this will return a list which looks like this:

[
                [['1.1', '1.2'], ['1.3', '1.4']],
                [['1.1', '1.3'], ['1.2', '1.4']],
                [['1.1', '1.4'], ['1.2', '1.3']],
                [['1.1', '1.2', '1.3'], ['1.4']],
                [['1.1', '1.2', '1.4'], ['1.3']],
                [['1.1', '1.3', '1.4'], ['1.2']],
                [['1.1'], ['1.3','1.2', '1.4']],
                [['1.4', '1.3','1.2'], ['1.1']],
        ]

'''



import ujson # i use ujson instead of deepcopy so if you don't have ujson you can just use deepcopy
from itertools import chain, combinations

jsonc = lambda x: ujson.loads(ujson.dumps(x))

def powerset(list1):
    '''not written by me'''
    b = chain.from_iterable(combinations(list1, r) for r in range(len(list1) + 1))
    return [set(x) for x in b]

def build_lst_nums():
    dict1 = {}
    for x in range(4, 7):
        dict1[x] = build_lst_nums2(x)

    return dict1



def build_lst_nums2(num):
    lst = ["1." + str(x) for x in range(1, num + 1)]
    main_lst = jsonc(lst)
    main_lst.remove('1.1')
    lst_nums = [
        [['1.1'], lst[1:]],
    [lst[1:], ['1.1']]
     ]

    for x in range(1, num - 1):
        con_sents = jsonc(main_lst)
        ant_sents = jsonc(main_lst)
        ant_size = x
        con_size = (num - 1) - x
        power_ants = powerset(ant_sents)
        power_cons = powerset(con_sents)
        power_ants = [x for x in list(power_ants) if len(x) == ant_size]
        power_cons = [x for x in list(power_cons) if len(x) == con_size]
        for power_ant in power_ants:
            for power_con in power_cons:
                if len(power_con & power_ant) == 0:
                    ant = list(power_ant)
                    ant.append('1.1')
                    lst_nums.append([ant, list(power_con)])

    return lst_nums

def quadruple():
    '''
    this is a sample answer for how the list should look if we have 4 sentences
    '''

    return [
            [['1.1', '1.2'], ['1.3', '1.4']],
            [['1.1', '1.3'], ['1.2', '1.4']],
            [['1.1', '1.4'], ['1.2', '1.3']],
            [['1.1', '1.2', '1.3'], ['1.4']],
            [['1.1', '1.2', '1.4'], ['1.3']],
            [['1.1', '1.3', '1.4'], ['1.2']],
            [['1.1'], ['1.3','1.2', '1.4']],
            [['1.4', '1.3','1.2'], ['1.1']],
    ]

build_lst_nums()
Reply
#2
The problem I have is that I can't imagine a use case where I'd call build_lst_nums(). An explanation is probably needed about what you want to do with this.
Reply
#3
I see what you're saying. When you're trying to determine if a sentence is logically possible you have to have a database of the definition of each word. The definitions cannot be written in natural language but must be written in a language which is easy for a computer to process. So suppose the sentence you want to analyze for consistency is: 'x is a hill and y is a mountain and x is larger than y,' which is logically impossible. Your definition for 'x is larger than y' would be written in a fashion similar to:

p ⊳ q ⊗ r

But ⊳ and ⊗ cannot be used to calculate contradiction so you have to convert that definition into:

p → (q & r)

or something similar to that. I realize that that probably doesn't illuminate things but calculating contradiction on natural language sentences takes a lot of background knowledge.
Reply
#4
bobsmith76 Wrote:calculating contradiction on natural language sentences takes a lot of background knowledge
Do you have a few internet links about this topic?
Reply
#5
No. I'm the only one that does it last time I checked. Why are you interested in doing it?
Reply
#6
bobsmith76 Wrote:Why are you interested in doing it?
I'm only trying to understand the code...
Reply
#7
That code is just a small snippet of a 12,000 line code. I've always been reluctant to post code because how can you make someone understand an excerpt from a huge code base? I thought that code was reasonably well self-contained such that others might get off on it. It's mostly just a combinatorics problem.

Think of it this way. Suppose you have any number of blocks greater than 2. You number the blocks from 1 to n. You then have to fit the blocks into 2 categories and each block cannot appear twice in the same category. Further, the first block must always be in the first category or if it is in the second category then it must be the only block that is in that category. For each n, how many different ways are there to arrange the blocks? That's basically the problem that the code answers.
Reply
#8
Your algorithm is ineffictient because at line 128, 129 you generate too many subsets and then you eliminate subsets having a non empty intersection. I think you can simplify this a lot
from itertools import chain, combinations, filterfalse

def almost_powerset(iterable):
    "almost_powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)))

def con_ant(n):
    ind = list(range(1, n+1))
    for s in almost_powerset(ind):
        b = set(s)
        t = [x for x in filterfalse(b.__contains__, ind)]
        yield s, t
        
def build_lst_nums(num):
    lst = ["1." + str(x) for x in range(1, num + 1)]
    u = lst[:1]
    for s, t in con_ant(num-1):
        a = u + [lst[x] for x in s]
        b = [lst[x] for x in t]
        yield a, b
    yield lst[1:], u

        
if __name__ == '__main__':
    for s, t in build_lst_nums(4):
        print(s, t)
Output:
['1.1'] ['1.2', '1.3', '1.4'] ['1.1', '1.2'] ['1.3', '1.4'] ['1.1', '1.3'] ['1.2', '1.4'] ['1.1', '1.4'] ['1.2', '1.3'] ['1.1', '1.2', '1.3'] ['1.4'] ['1.1', '1.2', '1.4'] ['1.3'] ['1.1', '1.3', '1.4'] ['1.2'] ['1.2', '1.3', '1.4'] ['1.1']
Reply
#9
Thanks, I really appreciate you taking the time to give me some useful feedback.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Decimal to binary weighted number converter hobbyprogrammer 1 2,335 Nov-28-2018, 12:38 AM
Last Post: Larz60+

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020