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.
                        
(Click on one of these icons to react to this blog post)

You might also enjoy...

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> <logo>
To prove you are not a spam bot, please type "cosine" in the box below (case sensitive):

Archive

Show me a random blog post
 2024 

Feb 2024

Zines, pt. 2

Jan 2024

Christmas (2023) is over
 2023 
▼ show ▼
 2022 
▼ show ▼
 2021 
▼ show ▼
 2020 
▼ show ▼
 2019 
▼ show ▼
 2018 
▼ show ▼
 2017 
▼ show ▼
 2016 
▼ show ▼
 2015 
▼ show ▼
 2014 
▼ show ▼
 2013 
▼ show ▼
 2012 
▼ show ▼

Tags

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

Archive

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