mscroggs.co.uk
mscroggs.co.uk

subscribe

Blog

Logic bot, pt. 2

 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 "x" then "-" then "a" then "x" then "i" then "s" in the box below (case sensitive):

Archive

Show me a random blog post
 2020 

Jul 2020

Happy π+√3-4 Approximation Day!

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

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

Archive

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