mscroggs.co.uk
mscroggs.co.uk

subscribe

Blog

Archive

Show me a random blog post
 2019 
 2018 
 2017 
 2016 
 2015 
 2014 
 2013 
 2012 

Tags

menace coins wool go sport countdown triangles a gamut of games latex matt parker pizza cutting aperiodical big internet math-off dragon curves folding tube maps fractals interpolation approximation london underground cross stitch harriss spiral accuracy frobel manchester binary hats probability craft manchester science festival news polynomials curvature estimation platonic solids golden ratio map projections chebyshev pythagoras pac-man graph theory draughts european cup javascript folding paper realhats stickers radio 4 sound statistics logic mathslogicbot reddit game show probability data sorting christmas card london weather station palindromes geometry game of life mathsteroids rhombicuboctahedron oeis noughts and crosses flexagons golden spiral propositional calculus people maths final fantasy dates puzzles speed light plastic ratio asteroids trigonometry twitter inline code royal baby electromagnetic field video games raspberry pi rugby hexapawn bubble bobble national lottery php reuleaux polygons error bars gerry anderson tennis martin gardner the aperiodical chalkdust magazine world cup captain scarlet christmas ternary bodmas nine men's morris machine learning chess football books games misleading statistics braiding programming arithmetic python dataset

Archive

Show me a random blog post
▼ show ▼
 2016-10-08 

Logical contradictions

During my Electromagnetic Field talk this year, I spoke about @mathslogicbot, my Twitter bot that is working its way through the tautologies in propositional calculus. My talk included my conjecture that the number of tautologies of length \(n\) is an increasing sequence (except when \(n=8\)). After my talk, Henry Segerman suggested that I also look at the number of contradictions of length \(n\) to look for insights.
A contradiction is the opposite of a tautology: it is a formula that is False for every assignment of truth values to the variables. For example, here are a few contradictions:
$$\neg(a\leftrightarrow a)$$ $$\neg(a\rightarrow a)$$ $$(\neg a\wedge a)$$ $$(\neg a\leftrightarrow a)$$
The first eleven terms of the sequence whose \(n\)th term is the number of contradictions of length \(n\) are:
$$0, 0, 0, 0, 0, 6, 2, 20, 6, 127, 154$$
This sequence is A277275 on OEIS. A list of contractions can be found here.
For the same reasons as the sequence of tautologies, I would expect this sequence to be increasing. Surprisingly, it is not increasing for small values of \(n\), but I again conjecture that it is increasing after a certain point.

Properties of the sequences

There are some properties of the two sequences that we can show. Let \(a(n)\) be the number of tautolgies of length \(n\) and let \(b(n)\) be the number of contradictions of length \(n\).
First, the number of tautologies and contradictions, \(a(n)+b(n)\), (A277276) is an increasing sequence. This is due to the facts that \(a(n+1)\geq b(n)\) and \(b(n+1)\geq a(n)\), as every tautology of length \(n\) becomes a contraction of length \(n+1\) by appending a \(\neg\) to be start and vice versa.
This implies that for each \(n\), at most one of \(a\) and \(b\) can be decreasing at \(n\), as if both were decreasing, then \(a+b\) would be decreasing. Sadly, this doesn't seem to give us a way to prove the conjectures, but it is a small amount of progress towards them.

Similar posts

Logic bot, pt. 2
Logic bot
How OEISbot works
Raspberry Pi weather station

Comments

Comments in green were written by me. Comments in blue were not written by me.
 Add a Comment 


I will only use your email address to reply to your comment (if a reply is needed).

Allowed HTML tags: <br> <a> <small> <b> <i> <s> <sup> <sub> <u> <spoiler> <ul> <ol> <li>
To prove you are not a spam bot, please type "raenil" backwards in the box below (case sensitive):
© Matthew Scroggs 2019