$->0\mathrm{.}6$ The Resolution Principle

To prove that a clause is valid using the resolution method, we attempt to show that the negation of

the clause is unsatisfiable, meaning it cannot be true under any truth assignment. This is done using

the following algorithm:

Negate the clause and add each literal in the resulting conjunction of literals to the set of clauses

already known to be valid.

Find two clauses for which the resolution rule can be applied. Change the form of the produced

clause to the standard form and add it to the set of valid clauses.

Repeat $2$ until False is produced, or until no new clauses can be produced. If no new clauses can

be produced, report failure; the original clause is not valid. If False is produced, report success;

the original clause is valid.

Consider again our example. Assume we now want to prove that notzvvy is valid. First, we negate

the clause and get z$^(^())$noty$.$ Then each literal is added to the set of valid clauses $($see $4.$ and $5.).$ The

resulting set of clauses is:

notpvvq

notzvvy

p

z

noty

Resolution on $2.$ and $5.$ gives:

notpvvq

notzvvy

p

z

noty

notz

Finally, we apply the resolution rule on $4.$ and $6.$ which produces False. Thus, the original clause

notzvvy is valid.

$0\mathrm{.}7$ The Program

$0\mathrm{.}7\mathrm{.}1$ Files and Task Description

Your program should take exactly one argument from the command line:

A $.$ kb file that contains the initial KB and the clause whose validity we want to test. The input

file contains n lines organized as follows: the first n$-1$ lines describe the initial KB$,$ while line

n contains the $($original$)$ clause to test. Note that the KB is written in CNF$,$ so each clause

represents a disjunction of literals. The literals of each clause are separated by a blank space,

while negated variables are prefixed by $.$

Your program should adhere to the following policy: p

$$zy

Your program's output should be:

$$pq

$$zy

p

z

$$y

q$\{3,1\}$

y$\{4,2\}$

$$z$\{5,2\}$

Contradiction $\{5,7\}$

Valid

My current code:

import sys

def parse$\_$kb$\_$file$($file$\_$path$)$:

$"""$Parse the input $.$kb file to extract the initial KB and clause to test."""

with open$($file$\_$path, $\text{'}$r$\text{'})$ as file:

lines $=$ file.readlines$()$

kb $=[$set$($line$.$strip$().$split$())$ for line in lines$[$:$-1]]$

test$\_$clause $=$ set$($lines$[-1].$strip$().$split$())$

return kb$,$ test$\_$clause

def negate$\_$clause$($clause$)$:

$"""$Negate the clause to be tested and return its literals as a list."""

return $[$f$\text{'}$~$\{$literal$\}\text{'}$ if not literal.startswith$(\text{'}$~$\text{'})$ else literal$[1$:$]$ for literal in clause$]$

def resolve$($clause$1,$ clause$2)$:

$"""$Attempt to resolve two clauses and return the resulting clause or None if not resolvable."""

resolved$\_$clause $=$ set$()$

found$\_$complementary $=$ False

for literal in clause$1$:

complement $=$ f$\text{'}$~$\{$literal$\}\text{'}$ if not literal.startswith$(\text{'}$~$\text{'})$ else literal$[1$:$]$

if complement in clause$2$:

if found$\_$complementary:

return None # More than one complementary pair, not resolvable

found$\_$complementary $=$ True

else:

resolved$\_$clause.add$($literal$)$

for literal in clause$2$:

if f$\text{'}$~$\{$literal$\}\text{'}$ not in clause$1$:

resolved$\_$clause.add$($literal$)$

return resolved$\_$clause if found$\_$complementary else None

def is$\_$redundant$($new$\_$clause, kb$)$:

$"""$Check if the new$\_$clause is logically equivalent to any clause in kb$."""$

new$\_$clause$\_$set $=$ set$($new$\_$clause$)$

return any$($new$\_$clause$\_$set $==$ existing for existing in kb$)$

def resolution$($kb$,$ test$\_$clause$)$:

$"""$Perform the resolution algorithm and print the output."""

clause$\_$counter $=$ len$($kb$)+1$

negated$\_$literals $=$ negate$\_$clause$($test$\_$clause$)$

# Add each literal of the negated clause to the KB

for literal in negated$\_$literals:

kb$.$append$(\{$literal$\})$

print$($f$"\{$clause$\_$counter$\}.\{\{\{$literal$\}\}\}\{\{\}\}")$

clause$\_$counter $+=1$

# Main resolution loop

i $=0$

while i $$ len$($kb$)$:

clause$1=$ kb$[$i$]$

for j in range$($i$)$:

clause$2=$ kb$[$j$]$

resolved$\_$clause $=$ resolve$($clause$1,$ clause$2)$

if resolved$\_$clause is not None:

if not resolved$\_$clause: # If resolved to empty, we found a contradiction

print$($f$"\{$clause$\_$counter$\}.$ Contradiction $\{\{\{$i $+1\},\{$j $+1\}\}\}")$

print$("$Valid$")$

return

if not is$\_$redundant$($resolved$\_$clause, kb$)$ and resolved$\_$clause: # Avoid adding redundant or empty clauses

kb$.$append$($resolved$\_$clause$)$

print$($f$"\{$clause$\_$counter$\}.\{\text{'}\text{'}.$join$($sorted$($resolved$\_$clause$))\}\{\{\{$i $+1\},\{$j $+1\}\}\}")$

clause$\_$counter $+=1$

i $+=1$

print$("$Fail$")$

def main$()$:

if len$($sys$.$argv$)!=2$:

print$("$Usage: python main.py $")$

return

kb$\_$file $=$ sys$.$argv$[1]$

kb$,$ test$\_$clause $=$ parse$\_$kb$\_$file$($kb$\_$file$)$

resolution$($kb$,$ test$\_$clause$)$

if $\_\_$name$\_\_=="\_\_$main$\_\_"$:

main$()$