I have just thought about an interesting problem in classical propositional logic to propose at this site, but lost my notes... I do recall, however, that the problem involved a particular contingent sentence with three atomic variables, $p$, $q$ and $r$. This first sentence contained exactly two occurrences of connectives, both binary. I am positive that at least one of those connectives was an implication having one of the three aforementioned variables as antecedent.

Question 1. Assuming that the previous information is sufficient to semantically characterize the forgotten sentence, can you determine what was its other connective, as well as the possible logical forms that my sentence could have had?

Now, another thing I do recall is that the problem that I had created consisted in checking that the first sentence above is semantically equivalent to a second sentence, written with the same variables and containing the same connectives as the first sentence, but with one extra implication.

Question 2. What could have been this second sentence? Justify.

The following extra considerations should be unnecessary to solve the problem:

Word of warning.
While one must not disconsider any information from the above statement when looking for a solution, one should also not read more than what is written. In particular:
(1) Nowhere in the statement of the problem is to be found a claim about the first (or the second) sentence being "syntactically unique". In fact, there is obviously no way, for instance, of avoiding permutation of the variables in a given solution. But there might clearly be many other structurally different sentences (belonging to the same equivalence class!) that solve Question 1. The task is to identify such sentences (preferably without just guessing).
(2) In the statement of the problem, a sentence is supposed to be "semantically characterized" when it is characterized up to logical equivalence --- so, again, you had better think first about what is happening at the level of the quotient algebra, and consider next the syntactic restrictions imposed by the statement of the problem.

The assumption made in Question 1 is integral part of the statement, and in fact essential to the existence of a well-determined solution!

  • 1
    $\begingroup$ I would have thought "formal logic" or something would be more suitable. I think Maths is used generally more for things like "use these numbers and operators to do this". More what most people would think of as maths than university level people... $\endgroup$ – Chris Nov 8 '14 at 22:31
  • 1
    $\begingroup$ @Chris Thanks for the feedback. I have now also added the tag logic, because of the syntactical aspects of the problem. Boolean Algebras are part of math, anyway. I believe the problem is not easy to solve, but might be worth a try. $\endgroup$ – J Marcos Nov 8 '14 at 22:36
  • $\begingroup$ @J Marcos That's funny.. Really, me solve this? I can probably point out 4 words in that I don't get and multiple sentences I don't understand, I'd never be able to solve this. $\endgroup$ – warspyking Nov 8 '14 at 22:41
  • 1
    $\begingroup$ @warspyking Connectives are syntactical counterpart of operators. This is standard terminology in Logic. In Universal Algebra they are called function symbols. In Linguistics they provide particular examples of conjunctions. The very first line in the statement of the problem already says that it presupposes familiarity with propositional logic! $\endgroup$ – J Marcos Nov 8 '14 at 23:52
  • 1
    $\begingroup$ @JMarcos I think many people on this site have a hard time grasping the concept - maybe you could help us understand the question better by providing an example solution (like an easy first try, which statisfies some of the requirements of the question, but not all of them) - and explain why this exampe solution is wrong? $\endgroup$ – Falco Nov 10 '14 at 15:49

Question 1:

p implies NAND(q,r), which is equivalent to (not p) or (not q) or (not r) which is symmetric in the variables. Once you're told that the second gate is a NAND, you know the sentence must have the form _ implies NAND(_,_). Since any permutation of p,r,q in the blanks is equivalent to the symmetric expression given, all possible choices are semantically equivalent. Intuitively, the sentence says that if a variable is true, the other two can't both also be true, which is equivalent to "It can't be the case that all three variables are true"

  • $\begingroup$ Nope, unfortunately this is not equivalent to the sentence semantically characterized by the statement of the problem. Anyway, you should try explaining why do you think this would be a solution to Question 1. $\endgroup$ – J Marcos Nov 8 '14 at 22:13
  • $\begingroup$ I edited in my reasoning. Maybe I'm just not understanding the problem. $\endgroup$ – xnor Nov 8 '14 at 22:20
  • $\begingroup$ Your intuition about symmetry is good, for it indeed would guarantee equivalence under permutation. However... there is no reason to think that the statement of the problem, up to Question 1, tells you that the second gate is a NAND, and there is no reason to think that the forgotten sentence resists permutation of its variables! $\endgroup$ – J Marcos Nov 8 '14 at 22:31
  • $\begingroup$ I upvoted your answer as a good attempt at a solution together with an explanation, even if it doesn't really solve the problem. $\endgroup$ – J Marcos Nov 8 '14 at 22:32
  • 1
    $\begingroup$ @JMarcos Then I don't know what your question is asking. When you asked for what the second gate was, I had understood that the conditions were specified knowing that gate. Otherwise, there are many different possibilities. By "semantically characterize", do you mean "character the set of assignments that make the formula true"? $\endgroup$ – xnor Nov 8 '14 at 22:34

I have a new answer based on a purely formal logical interpretation of the problem.

Lemma 1: The conditions in paragraph 1 do not specify a syntantically unique sentence.

Proof of lemma: Both the sentences p implies (q or r) and p implies (q and r) satisfying those conditions, as they have three atomic variables p,q,r and two connectives, one an implication implied by a variable. By, they are not logically equivalent as p=True, q=True, r=False satisfies the first but not the second.

Now, afterwards, we're asked to assume that the previous information is sufficient to semantically characterize the forgotten sentence, which is the negation of Lemma 1. For having both Lemma 1 and its negation, we use the principle of explosion to derive all statements.

Therefore, we derive that the forgotten statement was "I am the eggman, I am the walrus." As to the question of "the possible logical forms that my sentence could have had", it is the set of logical forms.

  • $\begingroup$ That was kind of fun. :) Anyway, what you have just confirmed is that these two sentences do not both belong to the class of solutions to the problem, and this is correct. Notice in any case that you have no reason to suppose even that implication is the leftmost connective in your expression! As a last comment, it is interesting to observe that both your sentences here could be used to give a solution to Question 2 (even though, as we agreed, they cannot be both solutions to Question 1). Do you see why? $\endgroup$ – J Marcos Nov 8 '14 at 23:08

I'll have a go with :

$p \rightarrow (q \leftrightarrow r)$

together with

$(p \rightarrow q) \leftrightarrow (p \rightarrow r)$

This reads as "p implies (q if and only if r)", and "(p implies q) if and only if (p implies r).

  • $\begingroup$ @JMarcos I pretty sure this is correct. "if and only if" denotes logical equivalence. $\endgroup$ – user4699 Nov 9 '14 at 1:51
  • $\begingroup$ That was a good try! (even though you have not justified where your sentence came from) However... note that, according to the statement of the problem, one would expect $p\to(q\leftrightarrow r)$ to be logically equivalent, for instance, to a sentence such as $q\leftrightarrow(p\to r)$ --- otherwise you cannot really say that the information I gave you was (necessary and) sufficient to warrant your conclusion about this being the forgotten sentence. $\endgroup$ – J Marcos Nov 9 '14 at 3:14
  • $\begingroup$ @JMarcos Oh, I see. Very clever! It's a nice question. I'll give some more thought if I can find the time over the next day or two. You asked : "... where your sentence came from". I noticed that "implication" did not distribute over "and" and "or", so I scribbled around with the "biconditional" until I came up with my guess. $\endgroup$ – user4699 Nov 9 '14 at 3:23
  • $\begingroup$ There are in principle 16 obvious candidates for the missing binary connective, of course, and one might surely give NAND or the biconditional a try. But a well-justified non-exhaustive-search solution to Question 1 would be more elegant! (and it is available, depending on just a bit of algebraic manipulation) $\endgroup$ – J Marcos Nov 9 '14 at 3:31
  • $\begingroup$ @JMarcos Now I'm not sure if I understand your comment. The sentence $ p \rightarrow (q \leftrightarrow r) $ is NOT logically equivalent to $ q \leftrightarrow (p \rightarrow r) $. For example, they disagree when $ p, q, r $ are all false, or when $ p, q $ are false and $ r $ is true. $\endgroup$ – user4699 Nov 9 '14 at 3:46

EDIT: As J Marcos points out in the comments, this answer cannot possibly be correct, as the 'lost sentence' it gives is tautological, not contingent as specified in the question.

It's been a while since I've done anything with formal logic, so please forgive (and correct) me if I butcher the terminology. I have only attempted to answer question 1.

Based on the information given there are three possible forms (up to relabeling of variables) for the forgotten sentence.

  1. $p \rightarrow (q \text{ B } r)$
  2. $(p \rightarrow q) \text{ B } r$
  3. $p \text{ B }(q\rightarrow r)$

where B is some binary connective. Note that I left out $(p \text{ B } q) \rightarrow r$, as the implication doesn't have an atomic antecedent (unless B is also implication, in which case we're back in case 2).

There is no other information in the question that would allow us to choose any particular one of these forms over the others. Thus, the problem is only well-defined* if there is exactly one choice of B such that the three forms are semantically equivalent. As it happens, there is, and we can derive it as follows.

When $p$ is false, the three forms have the values $True$, $True\text{ B }r$, and $False\text{ B }(q\rightarrow r)$, respectively. These must all be equal regardless of the value of $r$, so $True\text{ B } True = True\text{ B }False = True$.

When $p$ is true and $q$ is false, form 1 reduces to $True \text{ B } True = True$ and form 2 to $False \text{ B } r$. Again these must be equal for either value of $r$, so $False \text{ B } True = False \text{ B } False = True$.

This is enough to completely characterize B: it is the binary connective that always yields $True$ regardless of its operands.

*I'm cheating a bit here, I think -- J Marcos only assumes that the information is enough to define the sentence up to semantic equivalence, which is not quite the same as assuming the question "what was the other connective" has a well-defined answer. To make up the gap I'd need to show that semantic equivalence of $p \rightarrow (q \text{ C } r)$, $(p\rightarrow q)\text{ D } r$, and $p\text{ E }(q\rightarrow r)$ is enough to imply $\text{ C } = \text{ D } = \text{ E } = \text{ B }$, where B is the connective derived above. Proving this is completely mechanical (write down the truth tables for C, D, and E; plug in different values of $p$, $q$, and $r$ to 1, 2, and 3; and follow your nose) but would be tedious to write up, so I leave it as an exercise to the reader.

  • $\begingroup$ Nice try. Some observations: (i) there are many more than three logical forms, but some may be discharged (still leaving more than three logical forms) as soon as you fix the variable in the antecedent of the mentioned implication; (2) you're not really cheating by postulating well-definedness, as that is indeed the effect of the assumption in the statement of the problem; (3) your solution cannot be correct, given the hypothesis that we're talking about a contingent sentence. $\endgroup$ – J Marcos Nov 10 '14 at 23:52
  • $\begingroup$ Could you give an example of a sentence with exactly two occurrences of (binary) connectives, one of which is implication, which doesn't fit into one of my given forms (ignoring a relabeling of variables)? Fair point about it being a contingent sentence, I missed that. $\endgroup$ – Curtis H. Nov 11 '14 at 0:01
  • $\begingroup$ Relabelling of variables can transform a given sentence into a nonequivalent sentence (violating the assumed characterization of the forgotten sentence up to logical equivalence). I suggest you fix your antecedent, instead of fixing the order of the variables in the string. Sentences are not strings, anyway, but are rather structured as trees. $\endgroup$ – J Marcos Nov 11 '14 at 0:07
  • $\begingroup$ Just to be clear, is the answer to my question: "no, there isn't one"? $\endgroup$ – Curtis H. Nov 11 '14 at 0:08
  • $\begingroup$ The problem is precisely that you cannot "ignore a relabeling of variables". That's why you're missing several logical forms. $\endgroup$ – J Marcos Nov 11 '14 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.