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 "x" then "-" then "a" then "x" then "i" then "s" 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

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

Archive

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