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 "l" then "i" then "n" then "e" then "a" then "r" 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

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

Archive

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