mscroggs.co.uk
mscroggs.co.uk

subscribe

Blog

Logical contradictions

 2016-10-08 
During my Electromagnetic Field talk this year, I spoke about @mathslogicbot (now reloated to @logicbot@mathstodon.xyz and @logicbot.bsky.social), 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.
Edit: Added Mastodon and Bluesky links
                        
(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 "m" then "e" then "d" then "i" then "a" then "n" in the box below (case sensitive):

Archive

Show me a random blog post
 2025 

Mar 2025

How to write a crossnumber

Jan 2025

Christmas (2024) is over
Friendly squares
 2024 
▼ show ▼
 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

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

Archive

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