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 "s" then "e" then "g" then "m" then "e" then "n" then "t" in the box below (case sensitive):

Archive

Show me a random blog post
 2020 

Jul 2020

Happy τ-√3-2 Approximation Day!

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

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

Archive

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