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.

Similar posts

Logic bot, pt. 2
Logic bot
How OEISbot works
Raspberry Pi weather station

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 "c" then "o" then "s" then "i" then "n" then "e" in the box below (case sensitive):

Archive

Show me a random blog post
 2019 

Jul 2019

Big Internet Math-Off stickers 2019

Jun 2019

Proving a conjecture

Apr 2019

Harriss and other spirals

Mar 2019

realhats

Jan 2019

Christmas (2018) is over
 2018 
▼ show ▼
 2017 
▼ show ▼
 2016 
▼ show ▼
 2015 
▼ show ▼
 2014 
▼ show ▼
 2013 
▼ show ▼
 2012 
▼ show ▼

Tags

light trigonometry electromagnetic field puzzles matt parker european cup ternary programming stickers propositional calculus binary final fantasy speed craft captain scarlet sorting fractals news the aperiodical football frobel coins a gamut of games error bars palindromes harriss spiral bodmas reddit golden ratio martin gardner twitter golden spiral accuracy realhats national lottery dates javascript latex flexagons mathsteroids chess christmas card books manchester science festival menace hats gerry anderson tennis radio 4 estimation london dataset oeis folding paper world cup folding tube maps bubble bobble big internet math-off draughts plastic ratio noughts and crosses nine men's morris statistics braiding chebyshev map projections probability approximation php manchester raspberry pi pac-man mathsjam misleading statistics pizza cutting go asteroids wool mathslogicbot data arithmetic rhombicuboctahedron curvature pythagoras dragon curves royal baby geometry hexapawn games polynomials rugby logic graph theory machine learning interpolation python game show probability video games weather station triangles inline code reuleaux polygons christmas sport platonic solids london underground cross stitch people maths game of life chalkdust magazine sound countdown

Archive

Show me a random blog post
▼ show ▼
© Matthew Scroggs 2019