mscroggs.co.uk
mscroggs.co.uk

subscribe

Blog

Logical contradictions

 2016-10-08 
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
Interesting tautologies
How OEISbot works

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 "u" then "n" then "c" then "o" then "u" then "n" then "t" then "a" then "b" then "l" then "e" in the box below (case sensitive):

Archive

Show me a random blog post
 2020 

May 2020

A surprising fact about quadrilaterals
Interesting tautologies

Mar 2020

Log-scaled axes

Feb 2020

PhD thesis, chapter ∞
PhD thesis, chapter 5
PhD thesis, chapter 4
PhD thesis, chapter 3
Inverting a matrix
PhD thesis, chapter 2

Jan 2020

PhD thesis, chapter 1
Gaussian elimination
Matrix multiplication
Christmas (2019) is over
 2019 
▼ show ▼
 2018 
▼ show ▼
 2017 
▼ show ▼
 2016 
▼ show ▼
 2015 
▼ show ▼
 2014 
▼ show ▼
 2013 
▼ show ▼
 2012 
▼ show ▼

Tags

books tennis statistics platonic solids frobel folding tube maps misleading statistics approximation puzzles braiding reddit matrix of cofactors ucl logic gerry anderson mathsteroids mathsjam european cup computational complexity coins oeis mathslogicbot fractals data python world cup chess bubble bobble graphs golden spiral signorini conditions numerical analysis cross stitch harriss spiral arithmetic triangles quadrilaterals royal institution pythagoras matrix of minors estimation interpolation go sport christmas card wool news martin gardner geometry games national lottery wave scattering christmas hexapawn chalkdust magazine polynomials propositional calculus simultaneous equations matrix multiplication data visualisation matt parker big internet math-off sorting binary reuleaux polygons rugby the aperiodical finite element method final fantasy royal baby dragon curves error bars convergence sobolev spaces squares twitter game show probability people maths london underground golden ratio menace ternary geogebra sound hats logs determinants football draughts manchester inverse matrices preconditioning light machine learning captain scarlet london pizza cutting speed latex asteroids dates rhombicuboctahedron folding paper php game of life map projections javascript accuracy tmip hannah fry matrices palindromes boundary element methods weather station radio 4 trigonometry cambridge stickers countdown pac-man programming phd talking maths in public chebyshev manchester science festival gaussian elimination bodmas flexagons electromagnetic field advent calendar dataset bempp curvature probability nine men's morris plastic ratio raspberry pi craft noughts and crosses graph theory weak imposition video games realhats exponential growth inline code a gamut of games

Archive

Show me a random blog post
▼ show ▼
© Matthew Scroggs 2012–2020