ubuntuでaptのupdate/upgradeができなくなりました

使用しているSSDの容量が少なくなってきていたので、不要なパッケージなどを削除していたのですが
どうもその際に消したらいけないものを削除したようで、
再起動後にaptでupdate/upgradeなどができなくなりました。
その際に出力されるのが以下のエラーです。

ヒット:11 https://download.sublimetext.com apt/stable/ InRelease
ヒット:12 http://security.ubuntu.com/ubuntu bionic-security InRelease
Could not find platform independent libraries <prefix>
Consider setting $PYTHONHOME to <prefix>[:<exec_prefix>]
Python path configuration:
  PYTHONHOME = (not set)
  PYTHONPATH = (not set)
  program name = '/usr/bin/python3'
  isolated = 0
  environment = 1
  user site = 1
  import site = 1
  sys._base_executable = '/usr/bin/python3'
  sys.base_prefix = '/usr'
  sys.base_exec_prefix = '/usr'
  sys.executable = '/usr/bin/python3'
  sys.prefix = '/usr'
  sys.exec_prefix = '/usr'
  sys.path = [
    '/usr/lib/python38.zip',
    '/usr/lib/python3.8',
    '/usr/lib/python3.8/lib-dynload',
  ]
Fatal Python error: init_fs_encoding: failed to get the Python codec of the filesystem encoding
Python runtime state: core initialized
ModuleNotFoundError: No module named 'encodings'

Current thread 0x00007ffaac521740 (most recent call first):
<no Python frame>
パッケージリストを読み込んでいます...
E: Problem executing scripts APT::Update::Post-Invoke-Success 'if /usr/bin/test -w /var/lib/command-not-found/ -a -e /usr/lib/cnf-update-db; then /usr/lib/cnf-update-db > /dev/null; fi'
E: Sub-process returned an error code

どうも見た感じpythonが関係しているように思えるのですが、どう関係しているのかがわからずつまづいています。
もともとpythonはsystem標準の/usr/bin/python2が使用されていたのですが、表示上はpython3を見に行ってしまっています。
環境変数なども特に変えていないので、なぜ異なるpythonを見に行ってるのかもわからず。。。

現在使用しているのはUbuntu20.04.2 LTSです

もしわかるかたいましたら、ご教授お願いします。