Books on Polish Logic

Books on Polish Logic
Philonous
Forum Veteran
Avatar

Usergroup: Members
Joined: Apr 20, 2011

Total Topics: 13
Total Posts: 677
#1 - Quote - Permalink
Posted Apr 29, 2013 - 11:25 PM:
Subject: Books on Polish Logic
I am reading through some papers in journals on logic, and one of them uses a notation developed by Jan Lukasiewicz. One of the papers is by A.N. Prior and he uses Polish Notation in logic.

For example:
~x = Nx
x & q = Kxq
x v q = Axq
x--->y = Cxy
Lx = Necessarily x
Mx = Possibly x



I'm wondering if anyone knows of a logic text book that uses Polish notation to help me get to understand them a little better, just to see how it all works out with the mechanics.
andrewk
Inexhaustibly Curious
Avatar

Usergroup: Moderators
Joined: Oct 13, 2011
Location: Sydney, Australia

Total Topics: 41
Total Posts: 4664

Last Blog: On being, and eating, the juices of other animals

#2 - Quote - Permalink
1 of 1 people found this post helpful
Posted Apr 30, 2013 - 2:06 AM:

The wikipedia article on it gives a pretty good explanation.

http://en.wikipedia.org/wiki/Polish_notation

It's just a different notation by the way. The logic is exactly the same.

I think what's in that article is all there is to it. It's a prefix notation rather than the usual infix notation, meaning that the application of binary operators is written as:

<Operator> <1st Operand> <2nd Operand>

rather than the infix

<1st Operand><Operator> <2nd Operand>

If you've ever used a Hewlett Packard calculator, you'll be familiar with Reverse Polish Notation, which is postfix:

<1st Operand> <2nd Operand><Operator>

It looks like it also uses different symbols for the operators: N for not, K for And, A for Or etc. The main ones are listed in the wiki article.

One advantage of Polish notation is that you don't need any brackets or rules of precedence of operators. The disadvantage is that it's harder to read.
Willemien
Blond Dutch Mensa meisje

Usergroup: Sponsors
Joined: Apr 05, 2011
Location: London (UK)

Total Topics: 77
Total Posts: 1284
#3 - Quote - Permalink
1 of 1 people found this post helpful
Posted Apr 30, 2013 - 4:20 AM:

Welcome to the world of Polish notation smiling face

Andrewk is right in that it is just a different notation, but there are other advantages as well, but I do disagree that it is harder to read, you just need to get used to it.
(and of course I can name some psychological reasons for it)


I guess the book you are refering to is "Formal Logic" by A.N Prior,
another book in Polish Notation is "Modal Logic" by Zeman freely downloadable at: http://www.clas.ufl.edu/users/jzeman/modallogic/

Zeman also names other advantages of Polish notation ( Ɓukasiewicz parenthesis-free notation) :

" The researcher himself gains an obvious advantage in his choice of this notation, for almost all of the characters he will use in setting down his results are to be found on a standard typewriter keyboard. But the notation gives him another more important advantage. It lends itself exceptionally well to the use of the rules of inference commonly used with propositional calculi : substitution for variables and detachment. "

(Zeman refers to condenced detachment a strong way to generate theorems, see http://en.wikipedia.org/wiki/Condensed_detachment sadly it only works with polish notation)

Other advantages of Polish notation are:
- formula's in Polish notation are shorter,(around half the size, and how more complicated the formula , the bigger the difference)
- the main connective is always easy to find (it is just the first character)

Problems are off course
- it is sadly not used so much anymore. (although I am writing a computer program that works with it, Polish notation is just so much easier for computers)
- formulas look rather alien at first, but that is because it is another language.


Some hints on how to learn to use it.

- Don't translate polish formula's to infix formula's, just because you can, it is better to treat polish formula's as a seperate logic language, follow its flow and treat it atfirst as a seperate logic.
A problem here is also that formula's grow in this translation.

CCpCqrCCpqCpr (13 characters) translates to
(P -> (Q -> R)) -> ((P -> Q) -> (P ->R)) (23 characters, counting -> as one character)

ENApqKNpNq( 10 characters) translates to
~(P v Q) <-> (~P & ~Q) (14 characters)

CCCCCpqCrostCCtpCrp (single axiom C-o logic, Prior page 303) 19 characters
(((((P -> Q) -> (R -> _|_) -> S) -> T) -> ((T -> P) -> (R -> P)))) 35 characters


- learn to recognize well formed formulas and subformula's (there is a simple way see attached txt file)

GOOD LUCK
andrewk
Inexhaustibly Curious
Avatar

Usergroup: Moderators
Joined: Oct 13, 2011
Location: Sydney, Australia

Total Topics: 41
Total Posts: 4664

Last Blog: On being, and eating, the juices of other animals

#4 - Quote - Permalink
Posted Apr 30, 2013 - 5:12 AM:

Willemien, I find those Polish formulas quite easy to understand reading from right to left, but very difficult to understand reading from left to right. Do you think that's a feature of the language, or just a bias induced in me by the languages I'm used to? Or is it perhaps just a feature of the particular formulae you wrote? Can you write a formula that's easier to read from left to right?

Thinking about it, I think what I'm doing when reading from right to left is that, whenever the next symbol I read is not an operand, I push the stack up one level, like in an HP calculator or a computer push-pop stack. Reading from left to right I can't do that, because the operands come first, but maybe there's an analogous stack operation that can be used (stacking operators rather than operands?).

Willemien
Blond Dutch Mensa meisje

Usergroup: Sponsors
Joined: Apr 05, 2011
Location: London (UK)

Total Topics: 77
Total Posts: 1284
#5 - Quote - Permalink
2 of 2 people found this post helpful
Posted Apr 30, 2013 - 8:40 AM:

Hi Andrew I think you try to hard to translate from Polish to Infix,

And that is easier from right to left (because at the right is an complete formula)


But left to right is the right version to process them and all you need is some simple counting.


I also noticed my leson was not attached, i just include it below

But first write down the way you answer the question "What is the concequent of CCpCqrCCpqCpr?"

(the same question is at the end of this lesson )


Do try it out and see how much now easier reading from left to right has become,


Good luck

Polish notation lesson 1.5

so in the previous lesson we started with polish notation now we continue.

with some intermezzo (but still important)


- Main Connective

every formula has a main connective in A -> B it is ->
in ~(A->B) it is ~
in (A -> B ) <-> (~A v B) it is <->
in ~(A <-> B ) <-> (~A <-> B) it is <->
in ~((A <-> B ) <-> (~A <-> B)) it is ~

I guess you needed to have a good look at the last two before you could decide it was correct

In ~(complicated formula with ([{v & -> })]~ and <-> )
you will get confused what is the main connective.

in Polish notation no problem the main connective is just the first one.

ECpqANpq ((A -> B ) <-> (~A v B) it is E (<->)
ENEpqENpq ~(A <-> B ) <-> (~A <-> B) it is E (<->)
NEEpqENpq ~((A <-> B ) <-> (~A <-> B)) it is N (~)



- well formed formula.

In polish notation you off course also have well formed formula's and bad formed formula's

1) Cpq is well formed
2) CCp is incomplete and therefore not well formed
3) CCpNpNp is well formed
4) CCpNpNpq is not well formed
5) CCpppCCpq is not well formed


Have a go at them and then read further

so how do we check that easely and quickly?
(and you will see later this also has other uses)

Use the following table
- variable . . . . . . . . deduct 1
- zero place connective. . deduct 1
- one place connective . . no change
- two place connective . . add 1

What are the zero place connectives?
_|_ in Polish Notation called o (yep lowercase O)
T in Polish Notation called 1 (yep number 1)

One place connectives
~ N not
[] L nescesary
<> M posibility

Two place connectives
K &, A v, C ->, E <->.


Start with 1 and at the end we should have a zero

so for NCpq we get
. . . .1210
for NCCpppCCpq we get
. . 1232101210

There is a zero in it and therefore not well formed
(for the same reasoning NCCppp the formula till the 0 is well formed)

for NKpNp we get
. . 12110
and so is wellformed


Off course you have noticed both formula's did start with an N, I just did so to show the 1 to start with

for CCpqCCqrCpr we get
. . 23212321210
and so is wellformed



- Subformula's
what is the use of knowing what well formud formula's are?
There is more to it than knowing that a formula is wellformed (although that is very important in its own right)
one point where this is useful for is for finding subformula's


what are the subformula's of NKKNpNNqr?
we do this the same way starting at every position in the formula
. .. . . . .. . . . . NKKNpNNqr
starting at 1 gives . 123321110
starting at 2 gives . .23321110
starting at 3 gives . . 221110.(we stop at the first 0)
starting at 4 gives . . .10.... (we stop at the first 0)
starting at 5 gives . . . 0....
starting at 6 gives . . . .110.
starting at 7 gives . . . . 10.
starting at 8 gives . . . . .0.
starting at 9 gives . . . . . 0

So the sub formula's are NKKNpNNqr, KKNpNNqr, KNpNNq, Np, p, NNq, Nq, q and r

what are the subformula's of CCpCqrCCpqCpr?
we do this the same way starting at every position in the formula
. . . . . . . . . . . CCpCqrCCpqCpr
starting at 1 gives . 2323212321210
starting at 2 gives . .21210....... (stop at the first 0)
starting at 3 gives . . 0..........
starting at 4 gives . . .210.......
starting at 5 gives . . . 0........
starting at 6 gives . . . .0.......
starting at 7 gives . . . . 2321210
starting at 8 gives . . . . .210...
ect. (I am allowed to be lazy)

now you
what are the subformula's of NCNCpqCNqNp and of CCpqCCrpCrq ?


Antecedent and concequent

in A-> B, A is the antecedent and B the concequent
so in Cpq, p is the antecedent and q the concequent

Now back to CCpCqrCCpqCpr what is the antecedent and what the concequent?

the antecedent starts directly after the C, using what we just learned over subformula's
CCpCqrCCpqCpr
.21210....... CpCqr is the antecedent, and the rest is the concequent
. . ..2321210 CCpqCpr is the concequent (notice that it is also wellformed)

Futher deepening it out: (just for fun)
CCpCqrCCpqCpr
.21210....... CpCqr is the antecedent
. . . 2321210 CCpqCpr is the concequent
. 0.......... p is the antecedent of the antecedent
. .210....... Cqr is the concequent of the antecedent
. . . .210... Cpq is the antecedent of the concequent
. . . . . 210 Cpr is the concequent of the concequent

now you
what is the concequent of CpCCpqq?
and the antecedent of CKpCprr?




- uniform substitution
last point before we start with Condenced Detachment

what does CCpqCCrpCrq become if we replace p with Cst and q with CCusCut?
just add some spaces to the original formula
and put the repacement below it

CCp..q......CCrp..Crq replace p and q by
..p..q.........p....q
..CstCCusCut...Cst..CCusCut
CCCstCCusCutCCrCstCrCCusCut

that is all
so now you

1) what does CCpqCCrpCrq become if you replace p with s and q with CCstt
2) what does CpCCpqq become if you replace p with s and q with t (is simple)

3) modus ponens from 1 and 2

CONGRATULAUIONS
You just did condenced detachment with
major CCpqCCrpCrq and minor CpCCpqq

andrewk
Inexhaustibly Curious
Avatar

Usergroup: Moderators
Joined: Oct 13, 2011
Location: Sydney, Australia

Total Topics: 41
Total Posts: 4664

Last Blog: On being, and eating, the juices of other animals

#6 - Quote - Permalink
1 of 1 people found this post helpful
Posted Apr 30, 2013 - 4:52 PM:

Thanks Willemien. Your examples show nicely how one can keep track of things working from left to right. Your 'deduct 1' corresponds to what I think of as 'pushing up the stack' in my computer paradigm, and 'add 1' corresponds to 'pop off the stack'. When we go from left to right we push one and two-place connectives up into the stack as well as variables and zero-connectives.

This is nice and methodical. On reflection though, I still find it easier to work from right to left, because then we only need to push variables and zero-connectives into the stack. One and two-place connectives are used as soon as they are encountered. This means the stack usually doesn't get as high when working from right to left.

For example, taking your example of CCpCqrCCpqCpr:

Working right to left (the yellow highlighted C is a character that I erroneously omitted in the first version of this post. This version is fixed).

operation --------------------------- Stack ------ Stack Height
read 'r' and push into stack ----- r --------------------- 1
read 'p' and push into stack ---- p,r ------------------- 2
read and apply C ------------------- Cpr ------------------ 1
read q and push into stack ----- q,Cpr --------------- 2
read p and push into stack ----- p,q,Cpr -------------3
read and apply C ------------------- Cpq, Cpr ---------- 2
read and apply C ------------------- CCpqCpr -----------1
read r and push into stack ------ r,CCpqCpr --------- 2
read q and push into stack ----- q,r,CCpqCpr ------- 3
read and apply C ------------------- Cqr,CCpqCpr ----- 2
read p and push into stack ----- p,Cqr,CCpqCpr --- 3
read and apply C ------------------- CpCqr,CCpqCpr -- 2
read and apply C ------------------- CCpCqrCCpqCpr - 1

We can read off the subformulas from this by just taking the bottom (leftmost) element of the stack at each step. There are 13 steps, one for each symbol in the formula, which gives us 13 subformulas.

Now working from left to right. Going this way we push any variables or zero-connectives onto the stack and we execute the lowest (leftmost) one-connective or two-connective on the stack as soon as it has the required operand(s) below it.

operation ----------------------------- stack -----------------------stack height
read C and push into stack ------ C -----------------------------1
read C and push into stack ------ C,C ------------------------- 2
read p and push into stack ------- p,C,C ---------------------- 3
read C and push into stack ------ C,p,C,C ------------------- 4
read q and push into stack ------- q,C,p,C,C ---------------- 5
read r -------------------------------------- r,q,C,p,C,C -------------- 6
execute lowest connective (C) --- Cqr,p,C,C ---------------- 4
execute lowest connective (C) --- CpCqr,C ------------------ 2
read C and push into stack ------- C,CpCqr,C --------------- 3
read C and push into stack ------- C,C,CpCqr,C ------------ 4
read p and push into stack -------- p,C,C,CpCqr,C --------- 5
read q and push into stack -------- q,p,C,C,CpCqr,C ------ 6
execute lowest connective (C) --- Cpq,C,CpCqr,C --------- 4
read C and push into stack -------- C,Cpq,C,CpCqr,C ----- 5
read p and push into stack --------- p,C,Cpq,C,CpCqr,C -- 6

This has 19 steps, but it would reduce to 16 if we combine the execution of a connective with the preceding step where that preceding step is a 'read-and-push'. But that is still more steps than working from right to left.

The stack gets bigger working in this direction, because we have to push connectives into it as well as variables. Working from right to left a connective is used and disposed of as soon as it is read.

I think that may be why reverse polish (postfix) is so commonly used. Reverse polish is just normal polish, written in reverse order. With reverse polish we work from left to right, as we are accustomed to, but obtain the efficiency benefits of the first of the above examples.

It would be interesting to see if there is any formula that generates a higher stack and/or a lower number of steps in evaluation, working from right to left than left to right. I can't think of one.



Edited by andrewk on May 1, 2013 - 5:06 PM. Reason: Fixed error & restored inadvertent deletion
Philonous
Forum Veteran
Avatar

Usergroup: Members
Joined: Apr 20, 2011

Total Topics: 13
Total Posts: 677
#7 - Quote - Permalink
Posted Apr 30, 2013 - 9:50 PM:

Willemien wrote:
I guess the book you are refering to is "Formal Logic" by A.N Prior,
another book in Polish Notation is "Modal Logic" by Zeman freely downloadable at: http://www.clas.ufl.edu/users/jzeman/modallogic/


Thank you. The paper I was reading was A.N. Prior, and he did use the Polish Notation so it makes sense to check out his book on it. And I do also recall coming across the very book you linked, I just forgot who the author was. Thanks for that link and I shall use it.

I recently came across this notion of polish notation, which is simpler to present on a computer screen, at least for the person typing it out.

I was also interested in the works of Lukasiewicz. What he did was create a three value logic system and from this we can come up with multi valued logics, and one of the ways that they do this is done by some Matrix system. Does anyone know of a book that presents this Matrix system to come up with two valued, three valued, or more valued logical systems?
Willemien
Blond Dutch Mensa meisje

Usergroup: Sponsors
Joined: Apr 05, 2011
Location: London (UK)

Total Topics: 77
Total Posts: 1284
#8 - Quote - Permalink
Posted May 1, 2013 - 6:17 AM:

to Philonous

what you are talking about is called many valued logic, http://en.wikipedia.org/wiki/Many-valued_logic
http://plato.stanford.edu/entries/logic-manyvalued/


I am not well versed in them, it is al semantic model theory to me so maybe I should read more about it.


I did some study in lattice theory (a related field i guess, but am not sure in how far they coincide or not)


Maybe you can advice me on a good book about it.
(ps i just bought a second hand copy of "Aristotle's Syllogistic: From the Standpoint of Modern Formal Logic" Jan Lukasiewicz; Hardcover; £15.00 , my first book by him) smiling face

also Aristo in forums.philosophyforums.com...out-mathematics-60793.html
is busy with multivalued logic

let me know what you come up with smiling face



to Andrew

you are doing something completely different than me,
I am splitting a formula up in subformula's (looking at the structure of the formula)
you are evaluating formula's (simplifying them to a single (truth) value)

The difference goes a bit back to my question "What is the concequent of CCpCqrCCpqCpr?"

With your method you cannot even answer the question (which answer should be a formula) all your method does is evaluating the complete formula (the method doesn't even know when it has evaluated the consequent)

Calculators are doing that as well they just generate a value (number), nothing else.
for calculaters that is right , for logic it isn't.

That doesn't mean that your method is wrong, both approuches have their values (i need to write an routine that does exactly what you are doing soonish so thanks for your help smiling face ) but it is a different part of logic.
ciceronianus
Gentleman Loser
Avatar

Usergroup: Sponsors
Joined: Sep 20, 2008
Location: An old chaos of the Sun

Total Topics: 96
Total Posts: 5905

Last Blog: Make the World Go Away

#9 - Quote - Permalink
1 of 2 people found this post helpful
Posted May 1, 2013 - 9:12 AM:

For a moment, I thought this thread might be a "Polish joke." I'm just saying.
andrewk
Inexhaustibly Curious
Avatar

Usergroup: Moderators
Joined: Oct 13, 2011
Location: Sydney, Australia

Total Topics: 41
Total Posts: 4664

Last Blog: On being, and eating, the juices of other animals

#10 - Quote - Permalink
Posted May 1, 2013 - 3:03 PM:

Well I've made a complete mess of this Willemien!

In trying to reply to your post #8 I inadvertently edited my above post #6, so my reply has now over-written that one, to which you were replying.

I shall try to restore it, but it'll be a bit tricky because the table formatting doesn't copy properly.

I apologise for the inconvenience. Normal service will be resumed shortly.

ETA: Fixed now. Crikey these WSN tables are unreliable b**rs to try and edit, quote or copy. Most of the time they just don't work at all, despite my trying using several different browsers and operating systems! I gave up in the end and just used hyphens to space out the columns.

Edited by andrewk on May 1, 2013 - 5:10 PM
locked
Download thread as
  • 0/5
  • 1
  • 2
  • 3
  • 4
  • 5


Recent Internal Replies
On May 4, 2013 - 3:53 AM, Willemien replied internally to andrewk's We can answer the ....

This thread is closed, so you cannot post a reply.