From: dseaman@seaman.cc.purdue.edu (Dave Seaman) Subject: Re: Notation of logical expressions Date: 28 Nov 2001 16:03:21 -0500 Newsgroups: sci.math Summary: Prefix Polish Notation for statements in predicate logic In article <9u3d7b$60d$1@zeus.polsl.gliwice.pl>, Piotr wrote: >Hello, > >does anybody know such a notation of logical expressions: > ECpqCNqNp > CCpqCCqrCpr > Cpp > ... >I have been asked a question about this kind of expressions, >but unfortunately I know only the "traditional" notation... Those are examples of "Prefix Polish Notation", which was invented by the Polish mathematician Jan Lukasiewicz. It's called "prefix form" because operators precede their operands. Prefix notation is used in the Lisp programming language and also sometimes in logic. Somewhat better known is "Postfix Polish Notation", or "Reverse Polish Notation", which is used in some handheld calculators, mainly those made by Hewlett-Packard, and also in the FORTH programming language. First you enter the operands, and then you specify the operator. The operators that appear in your examples are C Logical Implication (followed by two operands) N Not (followed by one operand) E Logical Equivalence (followed by two operands) Some other logical operators that you didn't use are: A Alternation (OR) (followed by two operands) K Conjunction (AND) (followed by two operands) Since the number of operands is fixed, there is no need to mark where a subexpression ends (unlike in Lisp, where operators may take a variable number of operands and therefore parentheses are used. Thus, your examples in other notations are: Prefix Form: Cpp With Lisp-style Parentheses: (C p p) Infix Form: p -> p Postfix Form: ppC Prefix Form: ECpqCNqNp With Lisp-style Parentheses: (E (C p q) (C (N q) (N p))) Infix Form: (p -> q) <-> (~q -> ~p) Postfix Form: pqCqNpNCE Prefix Form: CCpqCCqrCpr With Lisp-style Parentheses: (C (C p q) (C (C q r) (C p r))) Infix Form: (p -> q) -> ((q -> r) -> (p -> r)) Postfix Form: pqCqrCprCCC -- Dave Seaman dseaman@purdue.edu Amnesty International calls for new trial for Mumia Abu-Jamal