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 "rebmun" backwards 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

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

Archive

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