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
How OEISbot works
Raspberry Pi weather station

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 "noitauqe" backwards in the box below (case sensitive):

Archive

Show me a random blog post
 2020 

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

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

Archive

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