all

Test Problem: Th2.86PrinMath

The goal to be proved here is Theorem 2.86 from the famous Principia Mathematica of 1910 (Vol 1), written by Whitehead and Russell. The goal is a conditional: $$[(\phi \rightarrow \psi) \rightarrow (\phi \rightarrow \delta)] \rightarrow \phi \rightarrow (\psi \rightarrow \delta).$$ No remaining use of an oracle can be present in a proof that constitutes a solution to this problem, but as always, use of the oracle along the way is not only permitted, but encouraged.

Deadline 28 Feb 2019 11:45:00 EST


Solve

Test Problem: KnightKnave_SmullyanKKProblem1.1

Here’s an early, simple knights-and-knaves problem from Raymond Smullyan, the master of such puzzles; it appears as Problem 1.1 in his educational Logical Labyrinths (2009). The context is that anthropologist Edgar Abercrombie visits the Island of Knights and Knaves, on which knights always tell the truth and knaves always lie. In addition, each inhabitant of the island is either a knight or a knave. The problem runs as follows: Abercrombie comes across three denizens of the island, $a$, $b$, and $c$. Abercrombie asks $a$: “Are you a knight or a knave?” The reply from $a$ is indecipherable. Abercrombie then asks $b$: “What did he say?” The response from $b$ is: “He said that he is a knave.” Right after this utterance, $c$ says: “Don't believe that; it’s a lie!”Your challenge is to decide the category of $b$ and of $c$, and prove that you are right. (You can try to figure out whether $a$ is a knight or a knave, but such effort is not recommended.) Actually, the pre-set HyperSlate file makes things much easier for you, as it presents you with a single goal, which conveys the identity of $b$ and $c$. But, you will have to prove that goal from the information Abercrombie has (which is provided to you in the form of seven givens). Before doing anything, you should make sure you understand, at least to a high degree, what each given is asserting.

You are permitted to use oracles as you engineer your proof, but no use of an oracle can remain in any proof that earns a trophy, and thereby confirms success.

(No deadline for now.)
View

Test Problem: AthenCfromAthenBandBthenC

The theorem to be proved here is a straightforward conditional: viz. $$\vdash (A \rightarrow B) \rightarrow ((B \rightarrow C) \rightarrow (A \rightarrow C)).$$ No remaining use of an oracle can be present in a proof that constitutes a solution to this problem.

Deadline 22 Feb 2019 12:00:00 EST


Solve

Test Problem: EmmaHelpedToo

This problem, known as ‘Bringsjord’ 1 in the initial, motivating part of the of the Spring 2019 edition of the class, has been shown to be unsolvable by the vast majority of college students who haven‘t had sustained, effective training in formal logic.

The problem presents two givens:

  1. The following three propositions are either all true, or all false.
    • If Billy helped, Doreen helped.
    • If Doreen helped, Frank helped.
    • If Frank helped, Emma helped.
  2. Billy helped.

And the question is: Does it follow deductively from these two givens that Emma helped? It seems that the minds of those pondering this question can be partitioned into three categories: The first category is composed of those who answer in the affirmative, because they simply focus on chaining through the conditionals to arrive at the conclusion that Emma helped. The second category is composed of those who realize those in the first category have failed to take account of the all-false possibility, and are quite sure that when the three conditionals are all false, it can’t be deduced that Emma helped. The third category is made up of those who are truly logical; they realize that even in the case when all three conditionals are false, it can be proved that Emma helped. The third group is correct, and hence the answer to the question is: Yes!

While as is standard you can use the PC provability oracle while working toward your solution, no remaining use of the oracle is permitted in the submitted file, if a trophy is to be won.

(No deadline for now.)
View

FregTHEN2

The goal to be proved here is Frege's axiom THEN-2 his axiomatization of the propositional calculus. No remaining use of any oracle can be present in the final solution.

Deadline 14 Mar 2019 12:45:00 EST


View

BiconditionalIntroByChaining

In this problem you are provided with three biconditionals, and must deduce a new one based on the endpoints of what can be regarded as the chain of the trio. One might, upon saving the maneuver in one‘s mind or one‘s library, dub the generalization of what a successful proof shows as biconditional intro by chaining (although you will no doubt be able to devise a less verbose label for the tactic in question). Expressed metalogically, your overall task is to validate: $$\{P \leftrightarrow Q, Q \leftrightarrow R, R \leftrightarrow S\} \vdash P \leftrightarrow S.$$ You are of course free to use the PC oracle during the construction of your proof, but no use of the oracle can remain in your finished, for-credit proof. (No deadline for now.)
View

BogusBiconditional

In this challenge you are given a peculiar biconditional, and asked to prove from it that the moon is made of green cheese (symbolized simply as $G$, as is our custom). It’s possible to obtain $G$ from the biconditional alone, but to make the problem easier, a second given, The Law of the Excluded Middle (LEM), or by its Latin name tertium non datur, is provided. We encourage ambitious students to leave aside this second given and, if they wish to use LEM, to prove it as a theorem (or more precisely, a lemma) in the course of reaching $G$. So, minimally you need to prove this: $\{ P \leftrightarrow \neg P, P \vee \neg P\} \vdash G$; but the more impressive proof would establish this: $\{ P \leftrightarrow \neg P\} \vdash G$.

Deadline 30 Apr 2019 23:59:00 EST


Solve

CheatersNeverPropser

As the saying goes, cheaters (ultimately) never prosper. In the particular case at hand, a formalization of this saying is to be proved from a single given, to wit: $$\forall s \forall t [\mathit{Cheats}(s, \mathit{reddit}, t) \rightarrow \forall t' (t < t' \rightarrow \neg \mathit{Prospers}(s, t'))].$$ The finished proof can have in it remaining use of the PC provability oracle, but no use of any other oracle can be in the finished proof. Notice that in the pre-set file that opens in HyperSlateTM, an English version of the given formula is included.

Deadline 30 Apr 2019 23:59:00 EST


Solve

Contrapositive_NYS_2

Here you are simply asked to prove that the contrapositive of a conditional can be deduced from that conditional. This is expressed in meta-logic by this statement: $\{ \phi \rightarrow \psi \} \vdash \neg \psi \rightarrow \neg \phi$. The problem NYS 2 tested for an understanding of this statement, which when thought of as an inference rule or schema is referred to as contraposition or transposition. No use of an oracle can remain in your solution.

Deadline 30 Apr 2019 23:59:00 EST


Solve

HypSyll

Here you are tasked with proving the very handy hypothetical syllogism, expressed in meta-logic by this statement: $\{ \phi \rightarrow \psi, \psi \rightarrow \delta \} \vdash \phi \rightarrow \delta$.

Deadline 30 Apr 2019 23:59:00 EST


Solve

MiracleOn34thStreet

The theorem to be proved here says that if Kris speaks Dutch, Santa Claus exists. The English sentence “Santa Claus exists” is symbolized here as $\exists x (x = \mathit{santa})$, i.e. as “There exists an x such that it’s Santa.” Cinematic cognoscenti will not only realize that this problem is derived from Miracle on 34th Street; they will also peg the specific scene in the movie that is being alluded to. No remaining use of an oracle is permitted in this problem.

Deadline 30 Apr 2019 23:59:00 EST


Solve

RussellsLetter2Frege

The challenge here is to prove that from Russell's instantiation of Frege's doomed Axiom V a contradiction can be promptly derived. The letter has of course been examined in class, in some detail, by S Bringsjord; it, along with an astoundingly soft-spoken reply from Frege, can be found here. Put meta-logically, your task in the present problem is to build a proof that confirms this: $$\{ \exists x \forall y ((y \in x) \rightarrow (y \not\in y)) \} \vdash \zeta \wedge \neg \zeta.$$ Make sure you understand that the given here is an instantiation of Frege’s Axiom V; i.e. it’s an instantiation of $\exists x \forall y ((y \in x) \rightarrow \phi(y))$. Note: Your finished proof is allowed to make use the PC provability oracle (but only that oracle). (No deadline for now.)
Solve

ThxForThePCOracle

This straightforward problem is quickly solved with a minimum of tedium, courtesy of the PC (entailment) provability oracle, use of which is allowed to remain in your finished proof (but no use of any other oracle can be in the finished proof). (No deadline for now.)
Solve

Explosion

Here your task is to prove the explosion inference schema/rule in HyperSlateTM; the schema says that from a contradiction anything whatsoever follows. Expressed in meta-logic, you are to prove $\{\phi \wedge \neg \phi\} \vdash \psi$. As explained in class, for whatever reason, while the general proof technique of reductio ad absurdum (= proof by contradiction, indirect proof, etc.) is covered in high-school math (at least it is in the textbooks, e.g. solid ones for Geometry and Algebra 2), explosion for some reason is almost invariably left aside, despite the indisputable dual fact that explosion is valid in classical logic and mathematics, and that it can be extremely useful.

Deadline 30 Apr 2019 23:59:00 EST


Solve

OnlyMediumOrLargeLlamas

This is a straightforward problem in which you are to create a HyperSlateTM proof that confirms this: $$\left\{ \begin{aligned}&\neg \exists x (\texttt{Small}(x) \wedge \texttt{Llama}(x)),\\ &\forall x (\texttt{Small}(x) \vee \texttt{Medium}(x) \vee \texttt{Large}(x)) \end{aligned}\right\} \\ \vdash \forall x \Big(\texttt{Llama}(x) \rightarrow \big(\texttt{Medium}(x) \vee \texttt{Large}(x)\big)\Big)$$ Note: Your finished proof is allowed to make use of the PC provabiity oracle, but of no other oracle. (No deadline for now.)
Solve

GreenCheeseMoon1

Is the Moon made of green cheese? Apparently, if one denies what would appear to be a rather crazy claim (viz. that if some proposition $P$ holds, every proposition implies $P$), it does indeed follow that the Moon is made of cheese. Your task here is to build a proof that confirms this (i.e. a proof that confirms $\{ \neg (P \rightarrow (Q \rightarrow P))\} \vdash G$), where we take $G$ to symbolize that the Moon is made of green cheese.

Deadline 30 Apr 2019 23:59:00 EST


Solve

Disj_Elim

This problem requires that one employ the inference schema (or rule) known as disjunction elimination, a.k.a. proof by cases. The inference schema, the hypergraphical specification of which can be found in the chapter Propositional Calculus in LAMA-BDLA, is based on the core idea that if one has a number of cases/disjuncts $\phi_1 \vee \phi_2 \vee \ldots \vee \phi_k$ to consider, and can show that $\psi$ follows from each $\phi_i$ (made as an assumption), then $\psi$ follows from the disjunction itself. (No deadline for now.)
Solve

KingAce2

Your challenge here is to shine the light of logic on one of the most famous cognitive illusions created by the august cognitive scientist (and early AI pioneer!) P. Johnson-Laird, and to thereby dissolve the illusion, which can be presented as follows:
If there is a king in the hand, then there's an ace in the hand; or if there isn't a king in the hand, then there's an ace in the hand; not both of these if-then statements are true. What can you correctly deduce?
Even professors across the globe (as long as they aren't motivated logicians or mathematicians) join 99% of the general public in declaring: 'That there's an ace in the hand!' Unfortunately, as you now know from Bringsjord's relevant lectures (the full lineup of which can be found here), not only is this wrong, but what you can correctly deduce is that there isn't an ace in the hand! Expressed in meta-logic, the HyperSlateTM file in question challenges you to produce a proof that confirms: $$\left\{ \begin{aligned}( K \rightarrow A & \vee \neg K \rightarrow A) \wedge \\ \neg (K \rightarrow A &\wedge \neg K \rightarrow A) \end{aligned}\right\} \\ \vdash \neg A$$ One of the cool things about this problem is that DeMorgan's Law is key, and while that's something many students of high-school math will be acquainted with, few will unfortunately have been asked to prove it. (Having not been asked is unfortunate because unless one can prove such a thing, it's rather doubtful that one understands it.)

Deadline 30 Apr 2019 23:59:00 EST


Solve

ChimericalBarber

The challenge here is to establish the so-called Barber Paradox. You are to show that from the asertion that in a certain town there resides a (male) barber who shaves all and only the men of that town who don't shave themselves, a contradiction can be deduced. (This is of course a picturesque version of Russell's Paradox.) The preset HyperSlateTM file conveniently supplies a first-order symbolization of the paradoxical proposition. You are premitted to leave use of the PC provability oracle in your finished proof (but no other oracles can remain).

Deadline 30 Apr 2019 23:59:00 EST


Solve

switching_conjuncts_fine

Here one needs to provide a proof that confirms $\{\phi \wedge \psi\} \vdash \psi \wedge \phi$. Once the proof is found, this shows that the order of conjuncts is immaterial in logical consequence, for clearly the number of conjuncts could be expanded arbitrarily, so we declare that once this proof works, it's mere tedium to handle $\phi_1 \wedge \phi_2 \wedge \ldots \wedge \phi_k,$ for any $k \in \mathbb{N}$.

Deadline 21 Mar 2019 01:57:00 EDT


Solve

NYS_1

This warmup for the infamous problems that typically follow (in Bringsjord’s demonstration that there’s a dire need to learn formal logic) was covered in the first of the two “motivating” classes, and is taken from New York State's high-school math coverage (under algebra). Viewed from the perspective of meta-logic, your task is to prove $\{\neg A \vee \neg B, B, C \rightarrow A\} \vdash \neg C$. Here, $\neg C$ is the key among a series of options; the distractors are $C, \neg B, H, A$ and NONE OF THE ABOVE.

Deadline 30 Apr 2019 23:59:00 EST


Solve

NYS_3

Viewed from the perspective of meta-logic, your task is to prove $\{\neg \neg C, C \rightarrow A, \neg A \vee B, B \rightarrow D, \neg (D \vee E)\} \vdash H$. Since of course $H$ here is arbitrary, and doesn't appear in the givens, what your proof will demonstrate, if valid, is that from the set of given formulae in the propositional calculus, any $\phi$ can be derived.

Deadline 30 Apr 2019 23:59:00 EST


Solve

tertium_non_datur

The theorem to be proved here is tertium non datur, a.k.a. The Law of the Excluded Middle; you will need to prove this: $\vdash \phi \vee \neg \phi$. For some edifying supplementary reading, provided for the motivated, consult the SEP entry on Contradiction.

Deadline 30 Apr 2019 23:59:00 EST


Solve