Khalil Sima'an: "Complexity of Disambiguation under DOP1" (2003)

I haven't written here in a while, but I've recently learned a few things I want to write down for later reference. The goal of the current post is to sketch a proof given by Khalil Sima'an for the NP-completeness of the probability-assignment problem under data-oriented parsing.

Background: Data-Oriented Parsing

Data-oriented parsing (DOP) is type of probabilistic language model that can be extracted from a treebank. Unlike probabilistic context-free grammar, the language model does not consist of non-terminal expansion probabilities, but is rather of a distribution over incomplete parse trees. These probabilities are estimated by snipping every subtree of every tree in a data set of manually parsed sentences.

Because the distribution created by the model can assign probability to very large parse trees, this scheme can encode a lot of memory and cross-dependency. Whereas probabilistic context-free grammars are Markovian (the expansion of a non-terminal depends only on the type of that non-terminal), data-oriented parsing models can encode arbitrarily long dependencies within the tree.

 

The tree-joining operation used to derive parse trees in DOP.

DOP models derive parse trees by joining incomplete trees together until all of their leaves are terminals. A single parse tree can therefore have several derivations. DOP models thus have one more source of ambiguity in addition to the structural ambiguity present in context-free grammars. This is the reason why many data-oriented parsing problems are harder than the corresponding parsing problems in formalisms in which parse trees are primitives.

An One-Dimensional Analogy

The difference between a DOP model and a context-free grammar is analogous to difference between a Markov model and a language model that can output words of any length.

We can fit such a distribution to a corpus by setting the probability of a word proportional to its frequency in the corpus, regardless of its length. The corpus ABC then results in a uniform distribution over

{A, B, C, AB, BC, ABC}.

Such a language model can obviously produce lots of long sequences of reasonable-sounding text, at the cost of having enormous memory requirements. The number of substrings is quadratic in the length of the corpus.

Data-oriented parsing similarly encodes long-distance memory within the parse tree by simply memorizing large, ready-made subtrees. An inductive argument shows that the number of subtrees of a tree is exponential in the depth of the tree.

A very large DOP grammar derived from just two sentences.

In both cases, it is possible to introduce rules that bias the distributions to favor shorter or longer segments if that seems desirable, but this makes no difference to the issues of computational complexity.

Background: The 3SAT Problem

Before we go into the mechanics of the complexity proof, a few pieces of specialized logical notation and terminology are necessary.

Sima'an shows that if one can decide whether a given sentence has a high probability under a DOP model, then one can also decide whether a logical formula in three variables is satisfiable (the 3SAT problem). I will start by reformulating the 3SAT problem in a form that lends itself more easily to the complexity proof.

Suppose we are asked if the logical formula

(p v q v ~r) ∧ (p v ~q v r) ∧ ... ∧ (~q v s v u)

consisting of m blocks of three literals, mentioning n ≤ 3m different variables. We are asked whether there is an assignment of truth values to the n logical variables that makes this formula true.

A positive answer to this question should come in the form of a truth assignment like

(T:p v T:q v T:~r) ∧ (T:p v F:~q v F:r) ∧ ... ∧ (F:~q v T:s v F:u)

For this assignment to qualify as a correct and positive answer, it must be

1. true: assign the value T to at least one of the disjuncts in each group
2. consistent: assign the same truth value to any variable x throughout the formula and the opposite to ~x

For example, (F:p) ∧ (F:p) is consistent but false, whereas (T:p) ∧ (T:~p) is a true but inconsistent. It will be convenient below to allow inconsistent truth-value assignments as valid proposals for a solution to the 3SAT problem.

Truth-Value Assignments as Parse Trees

Since truth-value assignments can be represented by formulas like (F:p) ∧ (F:~q v T:r), they can be generated by a context-free grammar.

This grammar can be modified so that eventually outputs the original logical formula with the truth values deleted—in the case of this example, (p) ∧ (~q v r). This can be accomplished by interpreting assignments like T:~q as the name of a non-terminal which always produces the terminal ~q.

This modified grammar will always produce the same surface string, but that string can be the result of different parse trees. Since the parse tree contains non-terminal nodes with Ts and Fs in them, it can be interpreted as a (possibly inconsistent) truth-value assignments. Sima'an's proof uses a representation os this type to reduce the 3SAT to the problem of finding high-probability parse trees.

Most-Likely-DOP-Parse-Tree is NP-Complete

Sima'an shows that the 3SAT problem is not easier than the following problem:

Given a DOP language model P, a sentence s, and a threshold t,
decide whether s has a probability larger than t under the model P.

Suppose we know how to solve this problem, and let a new instance of the 3SAT problem with m conjuncts and n variables be given.

As shown above, candidate solutions to the 3SAT problem can be represented as parses of the logical formula. A parse is a correct solutions when it satisfies both a truth requirement and a consistency requirement. Sima'an's proof constructs a DOP model that generates all the candidates solutions to the given problem, but generates the true and consistent solutions more frequently.

His grammar is constructed such that the formula only has two types of derivations:

1. always-true derivations:
1. generate a shallow tree leaving the disjunctive groups unspecified
   
2. within each disjunctive group, pick one of the three disjuncts and expand it such that it becomes true
   
3. expand the remaining disjuncts of each group randomly
   
2. probably-consistency derivations:
1. pick one of the n variables and generate a deep tree in which that variable is assigned a consistent truth value throughout the parse tree
   
2. expand the remaining disjuncts of each group randomly

Parse trees from the first group always make the formula true and are sometimes consistent. Parse trees from the second group are more likely than chance to be consistent and may occasionally be true. All parse trees result in the same surface string, which is equal to the logical formula.

If a parse tree is both true and consistent, it can derived in at least one way using the first method, and in at least n ways using the second method. The probability of a parse tree that solves the 3SAT problem is therefore higher than the probability of a parse tree that does not. By choosing the probabilities of the various subtrees well, it is possible to pick a threshold such that the existence of a high-probability tree is exactly equivalent to a positive resolution of the 3SAT problem.

The grammar constructed by Sima'an to translate 3SAT to most-likely-parse.

Obviously, I am leaving out some details here, but this is the idea of the proof. I should note that Sima'an's own proof has a what might be considered a minor error, in that he reversed the roles of the truth values and the literals in the parse tree, so that the surface sentence is a string of truth values. This makes no sense because it assumes a solution to the 3SAT problem is given as part of the input, but fortunately, it is an easy error to fix.

Arnauld: Logic (1662), Part IV, chs. 13–16

19th-century portrait of Arnauld, the main author of the Logic.

The last four chapters of the Port-Royal Logic deal with reasoning under uncertainty. They touch briefly on issues of evidential support, balanced odds, and fair games.

In retrospect, these remarks are difficult not to read as a precursors of later probability theory. Many authors have pointed this out, including Ian Hacking and Lorraine Daston.

I'm reading the 1996 translation by Jill Buroker, published by Cambridge UP.

The content of the four chapters on probability, or plausibility, are:

• Chapter 13, "Some Rules for directing reason well in beliefs about events that depend on human faith," argues that the standard of geometric proof and mathematical certainty only applies to matters of "immutable essence," and that judgment about human affairs should be made by meditating on the available evidence and testimonies.
• Chapter 14, "Application of the preceding rule to the beliefs about miracles," claims that this means that there are several instances in which it is reasonable to believe miracles took place, even if this cannot be proven beyond all reasonable doubt.
• Chapter 15, "Another remark on the same subject of beliefs about events," adds that this explains why certain deeds are attested by two notaries, and that the technique of weighing the evidence also has applications to authorship attribution for ancient (religious) manuscripts.
• Chapter 16, "The Judgments we ought to make concerning future events," argues that the doctrine not only applies to reasoning about the past, but also about the prediction of the future; a number of fair and unfair games are described as examples, and a version of Pascal's wager is then put forward.

Quotes follow below.

Don't Hold Your Breath

In chapter 13, we are told that the methodology of geometric proof works for geometry,

But if we try to use the same rules for beliefs about human events, we will always judge them falsely, except by chance, and we will make a thousand fallacious inferences about them. (p. 263)

Instead, we have to look for circumstantial evidence:

In order to decide the truth about an event and to determine whether or not to believe in it, we must not consider it nakedly and in itself, as we would a proposition of geometry. But we must pay attention to all the accompanying circumstances, internal as well as external. I call those circumstances internal that belong to the fact itself, and those external that concern the persons whose testimony leads us to believe in it. Given this attention, if all the circumstances are such that it never or only rarely happens that similar circumstances are consistent with the falsity of the belief, the mind is naturally led to think that it is true. Moreover, it is right to do so, above all in the conduct of life, which does not require greater certainty than moral certainty, and which even ought to be satisfied in many cases with the greatest probability.

But if, on the contrary, these circumstances are such that they are often consistent with the falsity of the belief, reason would require either that we remain in suspense, or that we view as false whatever we are told when its truth does not look likely, even if it does not look completely impossible. (p. 264)

Cloister of the Hôpital Cochin, inhabiting the former site of the Port-Royal abbey.

 

A Perversion of Reason

This idea is echoed in chapter 15:

Since we should be satisfied with moral certainty in matters not susceptible of metaphysical certainty, so too when we cannot have complete moral certainty, the best we can do when we are committed to taking sides is to embrace the most probable, since it would be a perversion of reason to embrace the less probable. (p. 270)

We also hear that negative evidence "weaken or destroy in the mind the grounds for belief" (p. 270).

A couple of things worth noting about these quotes:

• The process described here is a mental therapy, not a decision calculus; you pay close attention, and your "mind is naturally led" to a certain belief.
• The focus is on human affairs, that is, on practical matters.
• As in frequentist statistics, the contrast is not between true and false, but between confirmed and unconfirmed; we thus "remain in suspense" if the evidence is insufficient.

Set the Record Straight

Chapter 16 pours scorn on "many people" for entertaining a certain "illusion":

This is that they consider only the greatness and importance of the benefit they desire or he disadvantage they fear, without considering in any way the likelihood or probability that this benefit or disadvantage will or will not come about. (p. 273)

That is, thinking only of utility while ignoring probability. Moreover,

This is what attracts so many people to lotteries: Is it not highly advantageous, they say, to win twenty thousand crowns for one crown? Each person thinks he will be the happy person who will win the jackpot. No one reflects that if it is, for example, twenty thousand crows, it may be thirty thousand times more probable for each individual to lose rather than to win it.

The flaw in this reasoning is that in order to decide what we ought to do to obtain some good or avoid some harm, it is necessary to consider not only the good or harm itself, but also the probability that it will or will not occur, and to view geometrically the proportion all these things have when taken together. This can be clarified by the following example.

There are game in which, if ten persons each put in a crown, only one wins the whole pot and all the others lose. This each person risks losing only a crown and may win nine. If we consider only the gain and loss in themselves, it would appear that each person has the advantage. But we must consider in addition that if each could win nine crowns and risks losing only one, it is also nine times more probability for each person to lose one crown and not to win nine. Hence each has nine crowns to hope for himself, one crown to lose, nine degrees of probability of losing a crown, and only one of winning the nine crowns. This puts the matter at perfect equality. (pp. 273–74)

This argument is then pushed a little further to deal with some more extreme bets; to the fear of lightning, which is allegedly irrational and has to be "set straight" (p. 275); and finally to a version of Pascal's wager.

Gossuin de Metz: The myrrour (1527)

This is a translation of the 1245 book l'Image du Monde by the French priest Gossuin de Metz. It contains, among other things, short introductions to all the liberal arts, including grammar, logic, and rhetoric.

The quality of the scan of the book at Early English Books Online is quite bad, with splotches and dots all over. Combined with the odd and inconsistent spelling, this makes for a very difficult read.

Since I now plowed my way through the few pages on logic anyway, I thought I should put my own transcript here, and save some poor soul the labor some time in the future. The pages are unnumbered in the book, but the logic section stretches over what I guess would be pages 27–30.

Here is the text:

Logyke is the scyence wherby men do lerne to know the trovthe from the false sverly & trvly by probable argvmentys, and so to knowe the trovthe and the falshed of every proposycyon. A proposycvon is a reason of the indicatyff or shewing mode congrve and perfyte, sygnyfyenge trovthe or false, as god is beyng, a man is a beste, and a horse is rennynge, and svche other.

Also every syngvler proposycyon is an affyrmatyff or a negatyff, The affyrmatyff is he that affyrmeth the pryncypal verbe, As a man is a beste. The negatyfe is he that denyeth the pryncypall verbe, as a man is not a beste, so that the negatyffe come before the pryncypall verbe.

Also of syngle proposycyons, some be universals, some pertycvlers, some indiffinite, and some syngvlers.

An universall proposycyon is he that whan a nowne appellatyff that beryth the name of a thynge is his svbjectyfe determynyd with a sygne universall, as every man is a beste.

A partycvler proposycyon is he that whan a nowne that bereth the name of a thyng is his svbiectyfe determyned with a sygne pertycvler, as some man is a beste.

A proposycyon syngvler is he that whan a nowne that is the proper name of a thynge or a pronowne or adverbe demonstratyfe is svbjectyfe, as John is a man, wylliam is a beste, this men renneth, he ronneth, there is a beste, here is a man.

Also of proposycyons som be modallis & som be essencyallys.

A proposycyon modall is he that hath his svbiectyfe with a sygne modall, as this, possyble it is a man to go.

Sygnes modals be .iiii. that is to say, possyble, impossyble, necessarye, contyngent.

Also of proposycyons impossible and necessary there be thwayne that is so say, impossible by hym selfe, and impossible by accydent, impossible by hym selfe is that ever was fals, is false, and ever shall be fals, as no god is, impossible by accydent is that, that is fals & ever shalbe false, bvt yet ones it myght heve be or was trewe, as I have not be livyng. Necessary by hymselfe in like wise is that, that ever was trewe, is trewe, and ever shall be trew as god is, Necesary by accedent, is that that is trew and ever shalbe trew bvt yet [new page] ones is myght heve be or was fals, as my father hath begotte me, Contyngent is that that may be trewe or fals indyfferently, as I go, I speke, I shall go, I shall speke.

Also a dovble proposycyon is called an ypotytyk which hathe .ii. preposycyons inclvdyd in hym with some conivnctyon, As with &, if, or, & whyle, &, when they be ioyned with this worde &, they be called compylatyves, as thov arte arte a man, & that thov arte a beste, and with this worde, yf, cavsels, as yf I ronne, A man ronnyth and with this worde, or, dyffinytifes, As I go, or thov goest, & with this worde, whyle, temporell, as while I go thov syttest.

Illustration from book, placed between the chapter on rhetoric and the chapter on logic.

An argvment is the reason of a dovbtfvll thynge shewyng that whyche is dovbtfvll to be trewe or false, as John is a man, ergo John is a beste, So ever ye mvste note all that cometh before this worde, ergo is callyd the antecedens & that whiche folowth thys worde ergo is called the conseqvens, And note this ever for a pryncypall rvle to knowe a good argvment, when by no case possyble that can be pvtte the antecedens may be trewe and the conseqvens fals, than it is a good argvment, bvt yf any case in the wordle possyble may be pvt that the antecedens maye be trewe & the conseqvens fals, than it is no good argvment.

Also other rvles there be in Logyke to know a good argvmente whyche for yong lerners is conveinent to be had and to be u[se]d for to qvyckyn theyre wyttes bvt this forsayde rvle for them that have wytte and good capasyte is svffycyent to knowe every argvment whether it be good or badde.

Also Logyke techeth a man to know the dyffynicyon or the discrypcyon of every thyng which is no more in effect bvt rvles wherby to know trvly what the thyng is.

A dyffynycyon is that which sheweth what the thyng is by other thyngs essencyal.

A dyscrynpcyon is that whych sheweth what the thyng is by other thynges accydentall. As the dyffynycyon of a man is thys. A man is a body wyth lyfe sencyble & reasonable or every thynge whiche is a body with lyfe sensyble & reasonable is a man, and every man is a body wyth lyffe sensyble and reasonable.

Sensyble is as moche to say as that thynge that hathe the use or aptnes of the .v. sensys, as of tastynge, smellynge, herynge, seiyng, & tovchyng.

A dyscrypcyon is to know what the thynge is by thynges accyden[new page]tall, as the dyscrypcyon of a boke comonly is that thynge that is made with perchement or paper or with lettres that men may rede yet every thynge which is made with parmemente or paper with leters that men may rede is not a boke, nor every boke is not made with parchement or paper and lettres as a boke made with tables and ymages. Therfore in the dyscrypcyon we saye this worde comonly.

Accydentall thynges be those that my be somtyme take away from the thynge and yet the thynge to remayne as whytnes, blacknes, greatnes, or smalnes.

Essencyall thynges be those which never may be taken away from the thynge and the thynge to remayne, as the body of a man can never be takyn away from the man and the man to remayn.

Then follows the chapter on geometry.

Ainsworth: The Art of Logick (1653)

In this textbook on logic, Henry Ainsworth presents the topic as a kind of mental training, preparing the mind for other serious matters:

No discipline more helpeth the wit, or contemplative sharpness, i.e. the inclination of the temperature to contemplate distinctly and accurately. (p. 7)

This notion of mental training should be taken quite seriously:

The exercise then of Logick consisteth in this, that we frequently think on, & diligently meditate things conformably to the prescriptions and rules of Logick, that is, orderly and distinctly: This indeed is the chief, most principal, and the nearest Efficient Cause of this habit in us of this Art of Logick, and immediately ingenerates and expresseth Logick in us, whereas Wit and Precepts are Causes but remote. (pp. 12–13)

The book consequently closes with two chapters of suggested exercises.

Games and Meditations

These recommended exercises include both "solitary" and "social" exercises or games (p. 205).

For instance, Ainsworth suggests one problem type in which a teacher gives the pupil a theme (e.g., animal), and the pupil then responds by explaining the etymology, genus, parts, antonyms, etc. of the concept (p. 195).

A discussion-game for two is also discussed, after a due amount of prudent warnings (e.g., "Let not the matter propounded to be disputed of, violate Piety or Religion," p. 205).
Specifically for "social disputation," another bundle of ground rules are added:

1. Let there be brought unto disputation a good intention of the mind, which seeks not glory, but truth.
2. Let the mind be pure from all prejudices.
3. Let the disputers agree whither of them shall oppose or answer.
4. Let both parties bind themselves to the Laws and Rules of Logick.
5. Let them agree between themselves of certain foreknown principles.
6. Let brevity and plainness be kept in opposing, and answering all Ambiguities; and Ambages of Oratorious Declamations avoided. (p. 206)

After having drawn up these general rules, Ainsworth goes on to discuss the more specific "duties" of the person playing Opponent, and the person playing Answerer (p. 207–8; there is occasionally also a President, p. 208).

Other suggested exercises include solitary meditation on things learned (p. 212), and methodological analysis of written arguments, putting them into syllogistic form and the like (p. 217ff).

Seneca: Letters to Lucilius (trans. E. Barker, 1932)

The letters from Seneca to Lucilius mostly contain an assorted bunch of moralistic advice on how to live a good, Stoic life. One thing in particular which struck me about them, however, was their very explicit ridiculing of superficial philosophical or logical arguments.

Bust of Seneca (from Wikimedia)

For instance, one central tenet of the Stoic creed is that one should not fear death; but Seneca rejects the notion that this change of attitude can be brought about by a kind of "logical hocus-pocus" (letter 82; p. 12). He thus writes:

Our founder Zeno uses the following syllogism:

'No evil is glorious;
Death is glorious,
Therefore death is not an evil.'

O my comforter! Dispeller of my terrors! After that I shall lay my head on the block with alacrity! Please talk more seriously, and don't make a dying man laugh. Upon my honour I should find it hard to tell you whether the man who imagines he has snuffed out the fear of death by this inference, or one who tries gravely to explode it, as if it really bore on the question, is the crazier. (letter 82, p. 11-12)

The message thus seems to be that it isn't enough to recognize the formal validity of this or that verbal argument — you have to internalize its message and learn to live by it.

"Breakfast, Lads!"

Seneca's own preferred medium for making such points is instead the short, forceful statement of fact that treats death without any special ornament or sentimentality. In another comment to the syllogism above, he thus comments:

A moving address indeed! After that who'd demur to hurl himself on the levelled spear-points and die where he stood? But what gallant words Leonidas spoke: 'Get a good breakfast, lads: there'll be no dinner till the next world.' The food didn't rise in their mouths or stick in their throats or slip from their fingers: they accepted for dinner as cheerfully as for breakfast. Once more, there's the Roman officer speaking to the men sent to pierce a huge hostile force and seize a position: 'We must get there, boys,' said he, 'but we needn't get back again.' You see how unaffected and masterful virtue is: pray is there a single soul the chicaneries of you and your friends could inspire and brace? (letter 82; pp. 17-18)

Apparently, death-talk should not only be staunch and "unaffected," but also positively folksy ("lads"). This is is a matter of style and ethics rather than logic:

What can you say to fire men's heart for a plunge into the thick of peril? With what pleading can you defeat this unanimity of dread, with what resources of genius the conviction of humanity that bars your way? Do I find you juggling with words and spinning miserable little syllogisms? (letter 82; p. 18)

In fact he does, and he has an opinion to offer on the relevance of such arguments:

Your arguments run to point. Yes, and so does an ear of barley. It's the very fineness of some points that makes them useless and ineffective. (letter 82; p. 18)

It's difficult not to read a gendered Victorian connotation into a word like "fineness," but I don't know what the Latin text said, or how it would sound to contemporary ears.

"Storm the Stronghold of the Passions"

Seneca makes a similar point when discussing the dismissive Stoic attitude towards money, and in particular, the false sense of pride and security that people may draw from their wealth. Again, he counters this notion with a syllogism in the classical form:

Good doesn't result from evils. Wealth does results from a sum of many poverties: therefore wealth is not a good. (letter 87, p. 58; italics in original)

But he has little hope that such arguments really convince anybody:

Are we likely to argue the pros and cons in syllogisms of the kind we've just seen? Are we likely by their means to succeed in making the Roman people seek poverty, the groundwork and source of their imperial power, and honour it, shrink in dismay from their own wealth, reflect that they discovered this wealth in the treasuries of the vanquished, that from it bribery, corruption, and political disorders have forced their way into the most irreproachable and austere of cities, that the spoils of other nations are too gloatingly paraded, and that what one people has wrestled from all, all may more easily wrest from one? No, it is our actions [that] must champion that law: we must storm the stronghold of the passions, not draw lines round them. Let us speak, if we can, more forcibly; if not that, more plainly. (letter 87; p. 59)

It thus seems that in Seneca's ethical idiom, there is a strong connection between (1) being a "man of action" rather than idle words; (2) having learned to live in accordance with one's ethical truth; and (3) talking in a certain "no-nonsense" style of frank, manly prose.

In a sort of roundabout way, the effect is thus that he comes to appear in line with the modern "one true sentence" philosophy of writing that we associate with Hemingway — another decidedly macho writer/soldier/moralist.

Johan van Benthem: "Games that make sense" (2008)

This is a chatty note on the various uses of game theory in semantics and pragmatics. It makes two points that I find worth mentioning.

First, van Benthem correctly points out that there are two different notions of "game" in play in semantics, and that these are sometimes confused. One is Hintikka-style verification games, and the other is Parikh-style signaling games. Although the verification games may in some sense be taken as idealized roadmap for a conversation, this fact is not completely obvious and cannot be taken for granted.

Second, he notes that signaling games have thrown a lot of the syntactic and semantic structure from logic overboard in its attempts to model the emergence of meaning. Since logic usually models hard, conventional facts about a language, this means that game-theoretic approaches to pragmatics have a hard time getting off the ground, because they take everything to be up to debate and revision in the online conversation situation. This is a false assumption in many cases.

Van Benthem writes:

Finally, from the viewpoint of natural language, we have not even reached the complete picture of what goes on in ordinary conversation. There may be games that fix meanings for lexical items and for truth or falsity of expressions whose meaning is understood. But having achieved all that, the ‘game of conversation’ only starts, since we must now convey information, try to persuade others, and generally, further our goals – and maybe a bit of the others’ as well. (p. 7)

He gives a tip of the hat to a number of people in dynamic epistemic logic and then continues:

But conversation and communication is also an arena where game theorists have entered independently, witness the earlier references in Van Rooij [42], and the recent signaling games for conversation proposed in Feinberg [22]. Again, there is an interface between logic and game theory to be developed here, and it has not happened yet. (p. 8)

But certainly a number of people are currently trying to smuggle more logical assumptions into the games, with various levels of success. 

Augustine: De Dialectica

Around the year 387, Saint Augustine wrote this little text on logic, spanning only about 20 pages. According to his own account in Retractationes, the book was never finished, and he lost his only copy of the manuscript. However, the text we have genuinely seems to be written by him.

In spite of its opening statement, "Dialectic is the science of disputing well" (p. 5/82), De Dialectica does not contain much that we would now recognize as logic. It's a discussion of a number of topics related to language, most notably ambiguity and etymology.

Truth Values and Dispute

One notable feature of Augustine's discussion of 'dialectics' is that he seems to take dispute to be more fundamental than truth values. A meaningful statement has a truth value in virtue of being up for discussion – not the other way around.

In his words:

For either a statement is made in such a way that it is held to be subject to truth or falsity, such as 'every man is walking' or 'every man is not walking' and others of this kind. Or a statement is made in such a way that, although it fully expresses what one has in mind, it cannot be affirmed or denied, as when we command, wish, curse, or the like. For whoever says 'go into the house' or 'oh that he would go into the house' [utinam pergat ad villam] or 'may the gods destroy that man' cannot be thought to lie or to tell the truth, since he did not affirm or deny anything. Such statements do not, therefore, come into question so as to require anyone to dispute them. (p. 6/85)

He consequently adopts the term "statements that require disputation" as a name for what we would call truth-functional statements (p. 6/85).

Eloquence and Proloquence

He later introduces the distinction "expressing" / "asserting" (eloquendo / proloquendo) to indicate the difference between the statements that "require questioning and disputing" and those that do not (p. 7/87).

This leads him, in the Chapter XII on "the force of words," to make he following wonderful comment on the relation between logic and rhetoric:

For although disputation need not be inelegant [ineptam] and eloquence need not be deceptive [mendacem], still in the former the passion of learning often – indeed, nearly always – scorns the pleasures of hearing, while the in the latter the more ignorant multitude [imperitior multitudo] think that which is said elegant is said truly. Therefore, when it becomes apparent what is proper to each, it is clear that a disputer who has any concern to make his points appealing will sprinkle them with rhetorical color, and an orator who wishes to convince people of the truth will be strengthened by the sinews and bones, as it were, of dialectic, which are indispensable to the strength of the body but are not allowed to become visible to the eye. (p. 13–14/103)

So logic and rhetoric are inner and outer values – but logic is not inner as in the soul, but inner as in internal organs.

An Observation on Implication

Another interesting feature is that he takes implication to be inherently connected to argumentation:

Whoever says 'if he is walking, he is moving' wishes to prove something, so that when I concede that this combined statement is true he only needs to assert that he is walking and the conclusion that he is moving follows and cannot be denied, or he need only assert that he is not moving and the conclusion that he is not walking must be agreed to. (p. 6/85)

It seems fair to say that Augustine thus sees the meaning of the implication as  given by its use in argumentation.

Signification and Writing

In Chapter V, Augustine gives a definition of a sign followed by a slightly strange qualification:

A sign is something which is itself sensed and which indicates to the mind something beyond the sign itself. To speak is to give a sign by means of an articulate utterance. By an articulate utterance I mean one which can be expressed in letters. [Signum is quod et se ipsum sensui et praeter se aliquid animo ostendit. Loqui est articulata voce signum dare. Articulatum autem dico quae comprehendi litteris potest.] (p. 7/87)

The intuition behind this comment seems to be the following: If something is said clearly and intelligibly, it can be broken up into its component parts (letters, or phonemes). However, this does seem on he face of it to make verbal understanding dependent on literary understanding.

But maybe this is only because we read too much into the word "letter":

For we misuse the term 'letter' when we call what we see written down a letter, for it is completely silent and is no part of an utterance but appears as the sign of an articulate utterance. In the same way [we misuse the term 'word'] when we call what we see written down a word, for it appears as the sign of a word, that is, not as a word but as the sign of a significant utterance. Therefore, as I said above, every word is a sound [omne verbum sonat]. (p. 7/89)

The theory thus seems to be this: The written word or letter is a sign because it evokes the spoken word or letter to the mind; and the spoken word or letter is a sign because it evokes its referent.

Ambiguity and Obscurity

In Chapter VIII, Augustine introduces a distinction between ambiguity and obscurity. This is not terribly important, but I find his explanation so nice that I wanted to quote it:

When little appears, obscurity is similar to ambiguity, as when someone who is walking on a road comes upon a junction with two, three, or even more forks of the road, but can see none of them on account of the thickness of a fog. Thus he is kept from proceeding by obscurity. […] When the sky clears enough for good visibility, the direction of all the roads is apparent, but which is to be taken is still in doubt, not because of any obscurity but solely because of ambiguity. (p. 14/105)

He goes on to complicate this distinction by distinguishing further between obscurity based on inaccessibility to the mind and to the senses, as in not recognizing a picture of and apple either because one has never seen an apple before, or because it is too dark (p. 14/105).

Problems with Category Membership

In his discussion of ambiguity, Augustine distinguishes between the vagueness of a word like man and more straightforward cases of homonomy. He calls these two phenomena univocal and equivocal meaning, respectively.

This would not in itself be particularly interesting if he didn't get himself into problems by suggesting that a univocal concept is characterized by having "a single definition" (p. 16/111). This of course raises some problems once we start looking for such a definition:

When we speak of a man we speak equally of a boy and of a young man and of an old man, equally of a fool and of a wise man [and a number of further examples]. Among all those expressions there is not one which does not accept the name 'man' in such a way as to be included by the definition of man. For the definition of 'man' is 'a rational, mortal animal' [animal rationale mortale]. Can anyone say that only a youth is rational, mortal animal and not also a boy or an old man, or that only a wise man is and not only a fool? (p. 16–17/111)

So in order to save his definition, Augustine has to assert that a fool is rational, something he seems to sense the problem with:

One may wonder how a boy who is small and stupid [parvo aut stulto], or at least silly [fatuo], or a man who is sleeping or drunk or in a rage, can be rational animals. This can certainly be defended, but it would take too long to do this because we must hasten on to other subjects. (p. 17/111)

This is approximately the same rhetorical strategy he used when defining a sign back in Ch. V:

Whether all these things that have been defined have been correctly defined and whether the words used in definition so far will have to be followed by other definitions, will be shown in the passage in which the discipline of defining is discussed. [This part was never written.] For the present, pay strict attention to the material at hand. (p. 7/87)

Criticism of the Stoic Theory of Etymology

In addition to being an interesting text in its own right, Augustine's tiny book is also one of our prime sources for the Stoic theory of where meaning comes from.

The upshot of this theory is apparently the following: Every word has a meaning which derived metonymically from another word, and ultimately, these chains of metonymies all point back towards an original sound iconicity. Thus, Augustine reports that in order to avoid infinite regress,

… they assert that you must search until you arrive at some similarity of the sound of the word to the thing, as when we say the 'the clang of bronze' [aeris tinnitum], 'the whinnying of horses' [equorum hinnitum], 'the bleating of sheep' [ovium balatum], 'the blare of trumpets' [tubarum clangorem], 'the rattle of chains' [stridorum catenarum]. For you clearly see that these words sound like the things themselves which are signified by these words. But since there are things which do not make sounds, in these touch is the basis for similarity. If the things touch the sense smoothly or roughly, the smoothness or roughness of letters in like manner touches the hearing and thus has produced the names for them. For example, 'lene' [smoothly] itself has a smooth sound. Likewise, who does not by the name itself judge 'asperitas' [roughness] to be rough? It is gentle to the ears when we say 'voluptas' (pleasure); it is harsh when we say 'crux' (cross). This the words are perceived in the way the things themselves affect is. Just as honey itself affects the taste pleasantly, so its name, 'mel,' affects the hearing smoothly. 'Acre' (bitter) is harsh in both ways. Just as the words 'lana' (wool) and 'verpres' (brambles) are heard, so the things themselves are felt. The Stoics believed that these cases where the impression made one the senses by the sounds are, as it were, the cradle of words. From this point they believed that the license for naming had proceeded to the similarity of things themselves to each other. (p. 10/95)

Augustine's main beef with this theory seems that it is too speculative:

Even though it is is a great help to explicate the origin of a word, it is useless to start on a task whose prosecution could go on indefinitely. For who is able to discover why anything is called what it is called? (p. 9/93)

As an example, he gives a couple of hypotheses about the origin of the word verbum, asking "But what difference does this make to us?" (p. 9/93).

Varieties of Metonymic Shifts

The avenues by which words can jump from meaning to meaning are quite diverse. Twice in the text, Augustine gives a list of relationships that can warrant metonymic slides, once in chapter on "the origin of words" (Ch. VI) and once in the chapter on "equivocation" (Ch. X).

Here's the list from Chapter VI, page 11/97:

Proximity [vicinitas] is a broad notion which can be divided into many aspects:

1. from influence, as in the present instance in which an alliance [foedus] is caused by the filthiness of the pig [foeditate porci];
2. from effects, as puteus [a well] is named, it is believed, from its effect, potatio [drinking];
3. from that which contains, as urbs [city] is named from the orbis [circle] which was by ancient custom plowed around the area […];
4. from that which is contained as it is affirmed that by changing a letter horreum [granary] is named after hordeum [barley];
5. or by transference [abusionem], as when we say horreum, and yet it is wheat that is preserved here;
6. or the whole from the part, as when we call a sword by the name 'mucro' [point], which is the terminating part of the sword;
7. or the part from the whole as when capillus [hair] is named from capitis pilus [hair of the head].

Here's the list from Chapter X, page 19/117–119:

I call it transference [translatione]

1. when by similarity [similitudine] one name is used of many things, as both the man, renowned for his great eloquence, and his statue can be called 'Tillius.'
2. Or when the part is named from the whole, as when his corpus can be said to be Tillius;
3. or the whole from the part, as when we call whole houses 'tecta' [roofs].
4. Or the species from the genus, for 'verba' is used chiefly of all the wors by which we speak, although the words which we decline by mood and tense are named 'verba' in a special sense.
5. Or the genus from the species as 'scholastici' [scholars] were originally and properly those who were still in school, though now all who pursue a literary career [litteris vivunt] use this name.
6. Or the effect from the cause, as 'Cicero' is a book of Cicero's.
7. Or the cause from the effect, as something is a terror [terror] which causes terror.
8. Or what is contained from the container, as those who are in a house are called a household.
9. Or vice versa, as a tree is called a 'chestnut.'
10. Or if any other manner is discovered in which something is named by a transfer, as it were, from the same source.

You see, I believe, what makes for ambiguity in a word.

The itemization is not in the original. It is interesting that many of these examples are slightly strange or would be analyzed differently (but equally speculatively) today; the relationship of a chestnut tree and a chestnut would, e.g., probably be seen as producer–product relation rather than container–contained.

Word, Thing, Concept, and Word-Thing

One last thing that I want to mention is the rather complicated four-part distinction that Augustine introduces in chapter VI between verbum, dicibile, dicto, and res.

The last tree can roughly be glossed as concept, word, and thing:

Now that which the mind not the ears perceives from the word and which is held within the mind itself is called a dicibile. When a word is spoken not for its own sake but for the sake of signifying something else, it is called a dictio. The thing itself which is neither a word nor the conception of a word in the mind [verbi in mente conceptio], whether or not it has a word by which it can be signified, is called nothing but a res in the proper sense of the name. (p. 8/89)

The verbum, however, is a word considered as a thing one can refer to:

Words are signs of things whenever they refer to them, even though those [words] by which we dispute about [things] are [signs] of words. […] When, therefore, a word is uttered for its own sake, that is, so that something is being asked or argued about the word itself, clearly it is the thing which is the subject of disputation and inquiry; but the thing in this case is called a verbum. (p. 8/89)

We thus have here a kind of use/mention distinction, although put in a slightly different vocabulary.

Literature on the meaning of "only if"

I've been looking for some empirical studies of A only if B constructions. In the theoretical literature on natural language semantics, there is a number of models, but I want to know more about how they are actually understood. Fortunately, there seem to be some facts about that out there, too.

What Does It Mean, Allegedly?

The problematic issue with the only if construction is that it is supposed to be logically equivalent to a number of related constructions, even though non-logicians sometimes disagree with this. According to the classical convention, the following sentences thus all mean the same:

• It only thunders if it rains.
• If it thunders, it rains.
• If it doesn't rain, it doesn't thunder.

On the other hand, if we reverse the implication, we change the truth conditions:

• It only rains if it thunders.
• If it rains, it thunders.
• It it doesn't thunder, it doesn't rain.

If this was just a mere convention about logical language, all would be fine. The problem is, however, that these sentence forms are not used in the same situations, and they do not integrate equally well into all reasoning patterns in spite of their (alleged) equivalence.

The Performance Problem

One difference between the If A, then B and A only if B forms is that if form is generally more difficult to use in a modus tollens inference than the only if. At least, this is what Carlos Santamaría and Orlando Espino say (Santamaría and Espino 2002, p. 42). They're referring to three studies, including one by Jonathan Evans and M. A. Beck (Evans and Beck 1981).

The problematic case is thus the following inference:

If it thunders, it rains.
It doesn't rain.
–––––––––––––––––
It doesn't thunder.

This (clasically valid) inference should be performed more readily when served in this alternative, and supposedly equivalent formulation:

It only thunders if it rains.

I doesn't rain.

–––––––––––––––––––––

It doesn't thunder.

Cognitively, or perhaps in terms of actual natrual language semantics, this seems to indicate that A only if B works more like the contrapositive If not B, then not A than like its positive translation, If A, then B. Or at least, it seems to issue a conversational warrant closer to it.

It would be interesting to know if this alternative formulation comes with a corresponding decrease—are we trading of willingness to perform the straightforward modus ponens inference for higher rates of modus tollens? This would imply that the following inference generally is less accepted:

It only thunders if it rains.
It thunders.
–––––––––––––––––––––
It rains.

If the only if formulation really does works like a contrapositive, then this inference should appear to us like a modus tollens inference in terms of plausibility and difficulty. I do not know right now whether such an effect can actually be measured or not.

The Issue of Time

Another interesting proposal that Santamaría and Espino cite, also coming from Evans and Beck, is that there is a systematic interaction between our conception of temporal order and the choice of form.

Thus, even though If A, then B, and A only if B are supposedly logically equivalent, we get different patterns of acceptability or naturalness depending on whether A or B happened first. For A preceding B, we then (perhaps) have:

• If you bought on Tuesday, you're paying on Wednesday.
• (?) You bought on Tuesday only if you paying on Wednesday.

And for B preceding A:

• (?) If you're paying on Wednesday, you bought on Tuesday.
• You're only paying on Wednesday if you bought on Tuesday.

Of course, much clearer intuitions can be produced if we ruffle up the tenses a bit. But this, I think, relatively fair example to start the discussion from.

So, Causality?

Note that the issue of before/after interfaces with the concept of causality, which is notoriously bound up with implication, even if logicians and statisticians hate to admit this fact.

Possibly, the the only way we can really justify an inference from a later effect to a prior cause in the form of If EFFECT, then CAUSE is to objectify the cause and the effect by thinking about the observation of the effect and the deduction of the cause. In this way, we would straighten out the temporal sequence so that EFFECT could in fact precede CAUSE.

If this is true, it has a quite important consequence for the psychology of reasoning: We would then only be able to understand abductive inference by effectivly embedding a cause/effect relationship in a different and larger cause/effect relationship—namely the only in which a real or imagined person reasons from fire (the logical "cause") to smoke (the logical "effect").