Help
Index

Maarten Maartensz:    Philosophical Dictionary | Filosofisch Woordenboek

P - Propositional Logic - Extended: Algebraic semantics

Extended Propositional Logic - Algebraic semantics: Non-standard bivalent extension of standard bivalent propositional logic, to cover also reasoning with uncertainties and propositional attitudes.

This gives a sketch of the foundations of an Algebraic semantics for EPLA. See Extended Propostional Logic.

A. Rules, definitions and axioms

The term "PV" abbreviates "Propositional Variable", and "Prop" abbreviates "Proposition". In what follows, I shall use "p", "q", "r", "s" as PVs, and allow subscripts (letters or numbers) to produce as many PVs as one needs. Note that what follows is an informal formal explanation: It is fairly but not fully precise and specific, but I leave the full details for later: This is just a brief sketch of basic ideas.

The original motive for LPA (that follows below) was: To find a logic for propositional attitudes that is as simple as possible, and that requires neither modal logic nor more than two truth-values. My desire for simplicity was motivated both by logical and mathematical reasons (try to do with as few basic notions as are adequate to solve the problem), and by the empirical observation that not only all non-idiotic humans but also quite a few social mammals, at least, and perhaps also some birds, seem to have something like a theory of mind, that allows them to somehow reckon with the beliefs and desires of others.

B. Logical inference rules

CPL= Classical Propositional Logic

Syntax: Propositions
If X is a PV, X is a Prop.
If X is a Prop, then ¬X is a Prop.
If X is a Prop and Y is a Prop, then (X&Y) is a Prop and (XVY) is a Prop.
Nothing else is a Prop, except by definition.

Note this does not say what are the Props, but only how to produce them from PVs or other Props.

Axioms: pV¬p

Definitions:
p --> q =d ¬p V q
p iff q   =d p-->q & q-->p

Rules: p&q |- p
p&q |- q
p,q |- p&q
p    |- pVq
q    |- pVq
pVq, ¬pVq |- q

The above is a version of Classical Propositional Logic. The axiom is most conveniently read as "any proposition p is true or is not true". It can be proved from the rules, but is added for clarity.

EPL= Extended Propositional Logic EPL = CPL +

Syntax:
If X is a Prop, then +X and -X and ?X are Props.

Axioms: +p V -p V ?p

Definitions

+p       =d  ¬-p & ¬?p = p
-p       =d  ¬+p & ¬?p
?p       =d  ¬+p & ¬-p

piffq    =d   p&q V -p&-q V ?p&?q
p&q     =d   ¬-p & ¬-q
pVq     =d   ¬-p V ¬-q

Extended Propositional Logic adds the distinctions between the weak and strong logical operators (¬ and -, & and &, and V and V, iff and iff respectively), and adds the prefixes +, - and ? (respectively true, false and uncertain, or also verified, falsified and undecided).

One way to motivate the need for EPL is to point to logically contingent propositions about the future, such as "Tomorrow I will still be alive", which by many, such as Aristotle and Ockham, have been believed to be neither true nor false today.

It can be seen from the above and CPL that "¬p" amounts to "-p V ?p", and that accordingly EPL starts with a refinement of negation, and proceeds with refinements of the other logical operators.

EPLA = Extended Propositional Logic  with attitudes = EPL +

Syntax: If X is a Prop, and A is a term for an attitude and a is a term for person, then aAX is a Prop.

Attitudes are terms like "believes", "desires", "chooses" and many more. Terms for persons may include terms for personified entities, such as "the people of France" or "my kitten".

Definitions:
-aAp   =d aA¬p
aKp    =d aBp&p

The first of these makes a sort of reduction of EPLA to EPL possible, as will be shown

Axioms: aAp V aA-p V aA?p V ?aAp
¬aAaAp V aAp
¬aB(p |- q) V (p |- q)

The difference between "aA?p" and "?aAp" will be taken as that between a's believing (etc.) that p is uncertain and a's not being acquainted with p. Thus, if you are not me, presumably you are not acquainted with the proposition "The pope had a child by my grandmother". (This may be made more plausible by reading "?" as "uncertifiable".

Rules:
aA(p&q)    -||- aAp & aAq
aA(pVq)    -||- (aAp & -?aAq) V (aAq & -?aAp)
aA(p&q)    -||- -aA-p & -aA-q
aA(pVq)    -||- (-aA-p & -?aAq) V (-aA-q & -?aAp)
aB(p |- q) -||- aK(p |- q)

Extended Propositional Logic with Attitudes adds attitudes to EPL and some axioms for these.

The last rule is equivalent to the assumption that a is fully correct in his beliefs about logical consequence. This enables substitutions of equivalents, when a is acquainted with the involved propositions, and entails a knows all valid formulas involving only those propositions that a is acquainted with.

One may conditionalize or weaken or relativize this in various ways. Also, the relativization may take the general form K(a) |- ... with K(a) the knowledge a possesses or presumes, or a (certain) subset thereof.

As will be seen in the following section, apart from the axioms and what follows from these, and apart from the uncertifiable propositions for a, which a just doesn't know of, though others may, EPLA is much like a notational variant of EPL.

C. Logical semantical rules

The above can be also given a simple semantical and algebraic formulation. For ease of writing and reading I use "[p]" = "the value of p" (rather than the more prolix "v[p]" or "v(p)"), but of course set-theoretically this is just a function from propositions to the set {0,1}. The values are numbers and can be dealt with as in ordinary algebra, it is assumed.

Extended Valuations = EPLA +

If X is a Prop and y=1 or y=0, [X]=y is a valuation.
If V is a valuation, V is a Prop.

This makes it possible to aggregate the semantics of EPL and its logic.

CPL Valuations

VB:     [p]=1 V [p]=0
V[]:    [[p=1]=1]=[p=1]

V¬:     [¬p]=1-[p]

V&:     [p&q]=[p]*[q]
VV:     [pVq]=[p]+[q]-[p]*[q]

Viff:    [piffq]=[p&q]+[¬p&¬q]
V|-:    [p|-q]=[¬(p&¬q)]

Apart from V[], that allows the collapsing of iterated truth-values to single ones, this is all standard. VB is the rule of bi-valence.

EPL Valuations = CPL Valuations plus

VE0:      [+p]=[p]

VE+:      [+p]=[¬-p]*[¬?p]
VE-:      [-p]=[¬+p]*[¬?p]
VE?:      [?p]=[¬+p]*[¬-p]

VE-+:    [-+p] = [-p]
VE--:     [--p] = [+p]
VE-:      [-?p] = [+p V -p]

VE&:      [+(p & q)] = [+p & +q]
[-(p & q)] = [-p V -q]
[?(p & q)] = [p&?q V q&?p V ?p&?q]

VEV:      [+(p V q)] = [+p V +q]
[-(p V q)] = [-p & -q]
[?(p V q)] = [-p&?q V -q&?p V ?p&?q]

VE&:       [+(p & q)] = [~-p & ~-q]
[-(p & q)] = [-p V -q]

VEV:       [+(p V q)] = [~-p V ~-q]
[-(p V q)] = [-p & -q]

VEIFF:     [piffq]=[p&q]+[-p&-q]+[?p&?q]

Note that the weak operators are all implied by the strong operators of the same kind, but that the converse is not true and that e.g. V|- gets more sophisticated than is possible in CPL, and amounts to [p|-q]=[-pV?p V +q)]

LPA Valuations = EPL Valuations plus

VA-:     [-aAp]=[aA¬p]

VA&:    [aA(p&q)]=[aAp]*[aAq]
VAV:    [aA(pVq)]=[aAp]*[-?aAq]+[aAq]*[-?aAp]-[aAp]*[aAq]

VA&:    [aA(p&q)]=[-aA-p]*[-aA-q]
VAV:    [aA(pVq)]=[-aA-p]*[-?aAq]+[-aA-q]*[-?aAp]-[-aA-p]*[-aA-q]

VASb:   [aB(p |- q) & ¬(p |- q)]=0
VAA:     [aAaAp & ¬aAp]=0

Here are tables that correspond to the above, that may be derived from the stated and  similar theorems:

Tables EPL:

Tables EPL in 1 variable:

 p -p ?p ~p ~-p ~?p --p -?p ?-p 1 p 1 1 1 1 1 2 -p 1 1 1 1 3 ?p 1 1 1 1

Note this contains an innovation as regards truth-tables: To preserve bi-valence, the first column lists all the basic possibilities for all the propositions involved, as also shown in the following tables.

Accordingly, the full truth-tables for n propositions will have 2n lines in CPL, but 3n lines in EPL, and 4n in EPLA, to list all possible basic conjunctions for these n propositions.

Also, in EPL "+p" and "p" are equivalent, and the frontal "+" is usually left out.

Tables EPL in 2 variables:

 (p&q) (p&q) (pVq) (pVq) p ¬-p ¬(¬pV¬q) ¬(-pV-q) ¬(¬p&¬q) ¬(-p&-q) ¬(-pV?p) (pV?p) 1 p q 1 1 1 1 1 1 2 p -q 1 1 1 1 3 p ?q 1 1 1 1 1 4 -p q 1 1 5 -p -q 6 -p ?q 1 7 ?p q 1 1 1 1 8 ?p -q 1 1 9 ?p ?q 1 1 1

These are the basic connectives. Note that all lines in the above and the following truth-tables follow from the semantical rules and that truth-tables are a notational device.

Tables for strong and weak conjunction in EPL:

 (p&q) -(p&q) ?(p&q) (p&q) -(p&q) ?(p&q) ¬(¬pV¬q) (-pV-q) ¬-p&¬-q (-pV-q) 1 p q 1 1 2 p -q 1 1 3 p ?q 1 1 4 -p q 1 1 5 -p -q 1 1 6 -p ?q 1 1 7 ?p q 1 1 8 ?p -q 1 1 9 ?p ?q 1 1

Accordingly, a strong conjunction has all conjuncts are true to be true itself, and a weak conjunction has all conjuncts not false to be true itself.

Tables for strong and weak disjunction in EPL:

 (pVq) -(pVq) ?(pVq) (pVq) -(pVq) ?(pVq) -(-p&-q) (-p&-q) ¬-p&¬-q) (-p&-q) 1 p q 1 1 2 p -q 1 1 3 p ?q 1 1 4 -p q 1 1 5 -p -q 1 1 6 -p ?q 1 1 7 ?p q 1 1 8 ?p -q 1 1 9 ?p ?q 1 1

Accordingly, a strong disjunction has at least one disjunct true to be true itself, and a weak disjunction has at least one disjunct that is not false to be true itself.

Tables for strong and weak equivalence  in EPL:

 (piffq) -(piffq) ?(piffq) (piffq) -(piffq) ?(piffq) (p&q)V(¬p&¬q) (p&q)V(-p&-q)V(?p&?q) 1 p q 1 1 2 p -q 1 1 3 p ?q 1 1 4 -p q 1 1 5 -p -q 1 1 6 -p ?q 1 1 7 ?p q 1 1 8 ?p -q 1 1 9 ?p ?q 1 1

A weak equivalence follows CPL, but confuses non-truth and falsehood in EPL-terms. The strong equivalence has the intuitively nice feature of being true precisely if the propositions involved have the same prefix: both true, both false, or both uncertain.

D. Extending EPL to EPLA

To start with when considering EPLA, it is noteworthy that the given tables for EPLA and for EPL are isomorphic - but it must be kept in mind that in EPLA there are the additional lines when a is not acquainted with some involved proposition.

This also explains the additions in the the EPLA valuation rules for disjunction: To believe a disjunction, whether weak or strong, one must know of all the involved propositions. Thence

VAV:    [aA(pVq)]=[aAp]*[-?aAq]+[aAq]*[-?aA?p]-[aAp]*[aAq]
VAV:    [aA(pVq)]=[-aA-p]*[-?aAq]+[-aA-q]*[-?aA?p]-[-aA-p]*[-aA-q]

But apart from that, the basics for EPL and EPLA are just the same, and it may also be noted about disjunctions and distribution that:

Strong or has the strong distribution property that one of the alternatives is true.
Weak or  has the weak distribution property that one of the alternatives is not false.

Here are tables:

Tables ELPA full:

 aB(p&q) aB(p&q) aB(pVq) aB(pVq) aBp -aB-p -aB(~pV~q) -aB(-pV-q) -aB(~p&~q) -aB(-p&-q) -aB(-pV?p) aB(pV?p) 1 aBp aBq 1 1 1 1 1 1 2 aBp aB-q 1 1 1 1 3 aBp aB?q 1 1 1 1 4 aBp ?aBq 1 1 5 aB-p aBq 1 1 6 aB-p aB-q 7 aB-p aB?q 8 aB-p ?aBq 9 aB?p aBq 1 1 1 1 10 aB?p aB-q 1 11 aB?p aB?q 1 1 1 12 aB?p ?aBq 1 13 ?aBp aBq 14 ?aBp aB-q 15 ?aBp aB?q 16 ?aBp ?aBq

Tables ELPA small: The above may be abbreviated again like this, simply eliminating the cases with frontal ? (that intuitively means for e.g. ?aB(pVq), and any other binary operator, that a does not know of p or of q, which is not at all the same as aB?(pVq), that says a believes that the disjunction p or q is uncertain, for which a does need to know of both, in order to evaluate them.

Note this possible frontal ? must be accounted for in the rules of inference, but since it clutters up tables the above may be simplified to:

 aB(p&q) aB(p&q) aB(pVq) aB(pVq) aBp -aB-p -aB(~pV~q) -aB(-pV-q) -aB(~p&~q) -aB(-p&-q) -aB(-pV?p) aB(pV?p) 1 aBp aBq 1 1 1 1 1 1 2 aBp aB-q 1 1 1 1 3 aBp aB?q 1 1 1 1 4 aB-p aBq 1 5 aB-p aB-q 1 6 aB-p aB?q 7 aB?p aBq 1 1 1 1 8 aB?p aB-q 1 9 aB?p aB?q 1 1 1

Tables for strong and weak conjunction in EPLA:

 aB(p&q) aB-(p&q) aB?(p&q) aB(p&q) aB-(p&q) aB?(p&q) -aB(~pV~q) aB(-pV-q) aB~-p&~-q aB(-pV-q) 1 aBp aBq 1 1 2 aBp aB-q 1 1 3 aBp aB?q 1 1 4 aB-p aBq 1 1 5 aB-p aB-q 1 1 6 aB-p aB?q 1 1 7 aB?p aBq 1 1 8 aB?p aB-q 1 1 9 aB?p aB?q 1 1

Tables for strong and weak disjunction in EPLA:

 aB(pVq) aB-(pVq) aB?(pVq) aB(pVq) aB-(pVq) aB?(pVq) -aB(~p&~q) -aB~(-p&-q) -aB(-p&-q) aB(-p&-q) 1 aBp aBq 1 1 2 aBp aB-q 1 1 3 aBp aB?q 1 1 4 aB-p aBq 1 5 aB-p aB-q 1 1 6 aB-p aB?q 1 1 7 aB?p aBq 1 1 8 aB?p aB-q 1 1 9 aB?p aB?q 1 1

The tables show the interesting property of there being no true weak uncertain binary operators, that also holds for EPL.

It should also be remarked that many of the attitudes people do have are weak rather than strong - which seems to be something most people, whether logicians or not, seem to have overlooked.

Normally when saying e.g. "I believe I will be going on holiday next week to Greece or to France" one means no more than that it is false one does believe one will be going on holiday next week to neither country. ("If I don't go to Greece nor to France next week, I won't be going on holiday at all, but I don't know yet where I will go.")

It should also be mentioned that the following theorems can be proved. First, there is

T11. ¬?aBp |- aB(pV-p)

which says that one believes weakly that p is true or false if one knows of p (but usually one does not believe so strongly, since this involves believing that the one or the other is true, which one often does not believe until one has more evidence). And it may be noted also that aB(pV-p) -||- -aB(p&-p) -||- aB¬(p&-p) -||- aB¬pV-¬p) -||- aB(+pV-pV?p).

And the parallelism between EPL and EPLA is mostly due to

T12. -aAp -||- aA¬p

which is to say that it is false that a has an attitude to p iff it is true that a has that attitude to not p.

Next the VASb leads to (and in fact is equivalent with, given the other rules)

T13. aB(p |- q) |- (p |- q)

which is to say that a is a logical reasoner as regards logical consequence: a is never mistaken in his beliefs about these. This allows substitutions of equivalent propositions, provided a knows of them. (Here the point of (p |- q) is that (|- (¬p V q)) is meant, i.e. a semantically valid disjunction of that form, and not merely (¬p V q) which may be true by accident.)

Something like T13  is necessary for substitutions, though one may restrict this in various ways (e.g. a may be quite logical, but may have forgotten all but the last 7 propositions he thought of).

T14. aAaAp |- aAp

that is if a a believes that a believes p (or desires that a desires, or chooses that a chooses etc.) then indeed a believes (or desires or chooses etc.) p, or in other words, what a is conscious of as regards a's attitudes is true (though a may believe - desire, (try to) cause, know, experience - many things a is not conscious of.

Also, it gives the basics for making one's own attitudes: In the case of belief, by believing one believes p (or believes not p or believes p is uncertain).

This is involved in both consciousness - believing one believes, experiencing one experiences etc. - and in choice, in as much as that by the above to make one believe something all one needs to do is believe one believes it, and the same for other attitudes.

Note this is just a sketch and a prepublication.

It also refines and restates parts of my M.A.-thesis. (The above may need some revising.)

See also: Logic - EPL, Logic of Propositional Attitudes, Extended Propostional Logic

Literature:

Maartensz, Wessel, Zinoviev

Original: Dec 1, 2007                                               Last edited: 12 December 2011.