Posts

Showing posts from June, 2019

Verifying tautologies with Haskell

join the mathspp mailing list
PtEn< change language A tautology is a formula that is true regardless of the logical value we attribute to the variables it contains. For example, the propositional formula $P \vee \neg P$ is always true, regardless of $P$ being true or false. But not every tautology is as simple as the one I just showed. For example, showing that $$(P \implies Q) \implies [(Q \implies R) \implies (P \implies R)]$$ is a tautology requires a bit more thought. But thinking is too tiring, so let us write a Haskell program that takes a formula and decides if the formula is a tautology or not! (By the way, said program is available in my GitHub...) First we need to be able to represent a proposition and we will create a data type just for that. We will call our type "Prop", from proposition, from propositional logic. where we provided data constructors for all sorts of propositional formulas. The idea is that now the formula $P \vee \neg P$ is represented as Or…

Problem #17 - shuffle me around

join the mathspp mailing list
PtEn< change language This post contains a problem that haunted me for a couple of years. I had it lingering in my brain for a long time and it felt quite challenging... then I presented it to a friend of mine one night, and the morning after I had a text from him saying he had cracked it! So kudos to him! I only got to the answer after he gave me a hint...

Problem statement: you and a friend are outside a room guarded by a sphinx. The sphinx tells you that inside the room there are 100 drawers, numbered from $1$ to $100$, where each drawer contains one of a hundred balls, also numbered from $1$ to $100$. The balls are randomly shuffled inside the drawers but each drawer contains exactly only one unique ball. You, your friend and the sphinx are to play a game. First of all, your friend is going to the room where he will be able check the contents of each drawer for as long as he wants; he will also be given the opportunity to swap the balls of two draw…