Skip to content

matixezor/propositional-calculus-satisfiability-checker

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

6 Commits
 
 
 
 
 
 

Repository files navigation

Propositional calculus satisfiability checker

A script that checks if a given formula is satisfiable

Table of Content

  1. About
  2. Legend
  3. Example
  4. How to use
  5. Tests

About

This script was created in order to solve the satisfiability problem. It outputs the formula in disjunctive normal form and informs you whether it's satisfiable. The formula is not satisfiable if all of its elementary components contain a pair of opposite literals.
To achieve it, the script applies suitable laws and definitions:

  • Def. of implication
  • Def. of equivalence
  • DeMorgan's laws
  • Double negation law
  • Distributive law

Legend

Signs below represent logical conjunctions:

  • |- disjunction (or)
  • & - conjunction (and)
  • <> - If and only if
  • >> - implication
  • ~ - negation

Example

Here I'm gonna show how the script applies the laws and definitions on a simple example.
Formula: (p<>q)>>p&q

  1. Def. of equivalence
    (p>>q)&(q>>p)>>p&q
  2. Def. of implication
    (~p|q)&(q>>p)>>p&q
  3. Def. of implication
    (~p|q)&(~q|p)>>p&q
  4. Def. of implication
    ~[(~p|q)&(~q|p)]|(p&q)
  5. DeMorgan's laws
    ~(~p|q)|~(~q|p)|(p&q)
  6. DeMorgan's laws
    (p&~q)|~(~q|p)|(p&q)
  7. DeMorgan's laws
    (p&~q)|(q&~p)|(p&q)

Formula is now in disjunctive normal form and the script proceeds to check if it's satisfiable.
The verdict is that it is indeed satisfiable.

How to use

It's very simple to use it as it doesn't require any 3rd party libraries. Script was written in Python 3.8.1. There's no formula validation so make sure you input a correct formula.

Tests

There are tests, written using unittest, which are to ensure that no code improvements would generate wrong answers. There's 9 formulas which brings us to 54 unit tests.

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages