mscroggs.co.uk
mscroggs.co.uk

subscribe

Blog

 2015-03-15 
A few months ago, I set @mathslogicbot going on the long task of tweeting all the tautologies (containing 140 characters or less) in propositional calculus with the symbols \(\neg\) (not), \(\rightarrow\) (implies), \(\leftrightarrow\) (if and only if), \(\wedge\) (and) and \(\vee\) (or). My first post on logic bot contains a full explanation of propositional calculus, formulae and tautologies.

An alternative method

Since writing the original post, I have written an alternative script to generate all the tautologies. In this new method, I run through all possible strings of length 1 made with character in the logical language, then strings of length 2, 3 and so on. The script then checks if they are valid formulae and, if so, if they are tautologies.
In the new script, only formulae where the first appearances of variables are in alphabetical order are considered. This means that duplicate tautologies are removed. For example, \((b\rightarrow(b\wedge a))\) will now be counted as it is the same as \((a\rightarrow(a\wedge b))\).
You can view or download this alternative code on github. All the terms of the sequence that I have calculated so far can be viewed here and the tautologies for these terms are here.

Sequence

One advantage of this method is that it generates the tautologies sorted by the number of symbols they contain, meaning we can generate the sequence whose \(n\)th term is the number of tautologies of length \(n\).
The first ten terms of this sequence are
$$0, 0, 0, 0, 2, 2, 12, 6, 57, 88$$
as there are no tautologies of length less than 5; and, for example two tautologies of length 6 (\((\neg a\vee a)\) and \((a\vee \neg a)\)).
This sequence is listed as A256120 on OEIS.

Properties

There are a few properties of this sequence that can easily be shown. Throughout this section I will use \(a_n\) to represent the \(n\)th term of the sequence.
Firstly, \(a_{n+2}\geq a_n\). This can be explained as follows: let \(A\) be a tautology of length \(n\). \(\neg\neg A\) will be of length \(n+2\) and is logically equivalent to \(A\).
Another property is \(a_{n+4}\geq 2a_n\): given a tautology \(A\) of length \(n\), both \((a\vee A)\) and \((A\vee a)\) will be tautologies of length \(n+4\). Similar properties could be shown for \(\rightarrow\), \(\leftrightarrow\) and \(\wedge\).
Given properties like this, one might predict that the sequence will be increasing (\(a_{n+1}\geq a_n\)). However this is not true as \(a_7\) is 12 and \(a_8\) is only 6. It would be interesting to know at how many points in the sequence there is a term that is less than the previous one. Given the properties above it is reasonable to conjecture that this is the only one.
Edit: The sequence has been published on OEIS!

Similar posts

Logical contradictions
Logic bot
Interesting tautologies
How OEISbot works

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

Archive

Show me a random blog post
 2020 

May 2020

A surprising fact about quadrilaterals
Interesting tautologies

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

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

Archive

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