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 "h" then "e" then "x" then "a" then "g" then "o" 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

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

Archive

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