The finite models output by FM-Darwin conform to the TPTP standard.
fof(interpretation_domain, fi_domain, ! [X] : ( X = e1 ) ). fof(interpretation_terms, fi_functors, ( ( ! [X0, X1] : (disbanding_rate(X0, X1) = e1) ) & ( (efficient_producers = e1) ) & ( (esk1_0 = e1) ) & ( (esk2_0 = e1) ) & ( ! [X0] : (esk3_1(X0) = e1) ) & ( (esk4_0 = e1) ) & ( ! [X0] : (esk5_1(X0) = e1) ) & ( (first_movers = e1) ) & ( ! [X0, X1] : (founding_rate(X0, X1) = e1) ) & ( ! [X0, X1] : (growth_rate(X0, X1) = e1) ) ) ). fof(interpretation_atoms, fi_predicates, ( ( ! [X0] : ( environment(X0) <=> ( ( (X0 = e1) ) ) ) ) & ( ! [X0, X1] : ( greater(X0, X1) <=> $false ) ) & ( ! [X0, X1] : ( greater_or_equal(X0, X1) <=> ( ( (X0 = e1) & (X1 = e1) ) ) ) ) & ( ! [X0, X1] : ( in_environment(X0, X1) <=> ( ( (X0 = e1) & (X1 = e1) ) ) ) ) & ( ! [X0] : ( stable(X0) <=> ( ( (X0 = e1) ) ) ) ) & ( ! [X0, X1, X2, X3] : ( subpopulations(X0, X1, X2, X3) <=> ( ( (X0 = e1) & (X1 = e1) & (X2 = e1) & (X3 = e1) ) ) ) ) ) ).
fof(interpretation_domain, fi_domain, ! [X] : ( X = e1 ) ). fof(interpretation_terms, fi_functors, ( ( (a = e1) ) & ( (an_a_nonce = e1) ) & ( (at = e1) ) & ( (b = e1) ) & ( (bt = e1) ) & ( ! [X0, X1] : (encrypt(X0, X1) = e1) ) & ( ! [X0] : (generate_b_nonce(X0) = e1) ) & ( ! [X0] : (generate_expiration_time(X0) = e1) ) & ( ! [X0] : (generate_key(X0) = e1) ) & ( ! [X0, X1] : (key(X0, X1) = e1) ) & ( ! [X0, X1] : (pair(X0, X1) = e1) ) & ( ! [X0, X1, X2, X3] : (quadruple(X0, X1, X2, X3) = e1) ) & ( ! [X0, X1, X2] : (sent(X0, X1, X2) = e1) ) & ( (t = e1) ) & ( ! [X0, X1, X2] : (triple(X0, X1, X2) = e1) ) ) ). fof(interpretation_atoms, fi_predicates, ( ( ! [X0] : a_holds(X0) ) & ( ! [X0] : ( a_stored(X0) <=> ( ( (X0 = e1) ) ) ) ) & ( ! [X0] : b_holds(X0) ) & ( ! [X0] : ( b_stored(X0) <=> ( ( (X0 = e1) ) ) ) ) & ( ! [X0] : ( fresh_to_b(X0) <=> ( ( (X0 = e1) ) ) ) ) & ( ! [X0] : ( message(X0) <=> ( ( (X0 = e1) ) ) ) ) & ( ! [X0] : party_of_protocol(X0) ) & ( ! [X0] : ( t_holds(X0) <=> ( ( (X0 = e1) ) ) ) ) ) ).
fof(interpretation_domain, fi_domain, ! [X] : ( X = e1 | X = e2 ) ). fof(interpretation_domain, fi_domain, ( e1 != e2 ) ). fof(interpretation_terms, fi_functors, ( ( (an_organisation = e1) ) & ( ! [X0, X1, X2] : ( (appear(X0, X1) = X2) <=> ( ( ( (X2 = e1) ) & ~( (X0 = e2) & (X1 = e2) ) & ~( (X0 = e1) & (X1 = e1) ) ) | ( (X0 = e1) & (X1 = e1) & (X2 = e2) ) | ( (X0 = e2) & (X1 = e2) & (X2 = e2) ) ) ) ) & ( ! [X0, X1] : (cardinality_at_time(X0, X1) = e1) ) & ( (e = e1) ) & ( (efficient_producers = e1) ) & ( (first_movers = e2) ) & ( ! [X0, X1, X2] : ( (number_of_organizations(X0, X1) = X2) <=> ( ( ( (X2 = e1) ) & ~( (X0 = e1) & (X1 = e1) ) ) | ( (X0 = e1) & (X1 = e1) & (X2 = e2) ) ) ) ) & ( ! [X0, X1] : (sk1(X0, X1) = e1) ) & ( (sk2 = e2) ) & ( (zero = e1) ) ) ). fof(interpretation_atoms, fi_predicates, ( ( ! [X0] : ( environment(X0) <=> ( ( (X0 = e2) ) ) ) ) & ( ! [X0, X1] : ( greater(X0, X1) <=> ( ( (X0 = e2) & (X1 = e2) ) | ( (X0 = e2) & (X1 = e1) ) ) ) ) & ( ! [X0, X1] : ( greater_or_equal(X0, X1) <=> ( ( (X0 = e2) & (X1 = e1) ) | ( (X1 = X0) ) ) ) ) & ( ! [X0, X1] : ( in_environment(X0, X1) <=> ( ( (X0 = e2) & (X1 = e1) ) ) ) ) & ( ! [X0, X1, X2] : ( subpopulation(X0, X1, X2) <=> $false ) ) ) ).
EP will use the current version of the new TPTP output format. The following rule names are defined for the main proof search:
Additionally, the clausification will use additional rule names:
The first proof uses all proof search inferences except for "ef", "spm", and "csr", although it uses some in fairly trivial ways. The second proof is for SYN075+1, and also contains the clausification steps. The final proof is the proof for SYN075-1, and contains examples for "ef" and "csr".
ALL_RULES
# Problem is unsatisfiable (or provable), constructing proof object # TSTP exit status: Unsatisfiable # Proof object starts here. cnf(1,axiom,(f(X1,X2)=f(X2,X1)),file('ALL_RULES.lop', at_line_19_column_1)). cnf(2,axiom,(f(X1,f(X2,X3))=f(f(X1,X2),X3)),file('ALL_RULES.lop', at_line_20_column_1)). cnf(3,axiom,(g(X1,X2)=g(X2,X1)),file('ALL_RULES.lop', at_line_21_column_1)). cnf(4,axiom,(f(f(X1,X2),f(X3,g(X4,X5)))!=f(f(g(X4,X5),X3),f(X2,X1))|k(X1,X1)!=k( a,b)),file('ALL_RULES.lop', at_line_22_column_1)). cnf(5,axiom,(b=c|X1!=X2|X3!=X4|c!=d),file('ALL_RULES.lop', at_line_24_column_1)). cnf(6,axiom,(a=b|a=c),file('ALL_RULES.lop', at_line_26_column_1)). cnf(7,axiom,(i(X1)=i(X2)),file('ALL_RULES.lop', at_line_28_column_1)). cnf(8,axiom,(c=d|h(i(a))!=h(i(e))),file('ALL_RULES.lop', at_line_29_column_1)). cnf(13,derived,(k(a,b)!=k(X1,X1)),inference(ar,[status(thm)],[4,1,3,2,theory(equality)])). cnf(23,derived,(c=b|epred1_0|X3!=X4|d!=c),inference(split,[split(esplit,[])],[5])). cnf(24,derived,(epred2_0|X1!=X2),inference(split,[split(esplit,[])],[5])). cnf(25,derived,(~epred2_0|~epred1_0),inference(split,[split(esplit,[])],[5])). cnf(26,derived,(epred2_0),inference(er,[status(thm)],[24,theory(equality)])). cnf(27,derived,($false|~epred1_0),inference(rw,[status(thm)],[25,26,theory(equality)])). cnf(28,derived,(~epred1_0),inference(cn,[status(thm)],[27,theory(equality)])). cnf(29,derived,(c=b|epred1_0|d!=c),inference(er,[status(thm)],[23,theory(equality)])). cnf(30,derived,(c=b|d!=c),inference(sr,[status(thm)],[29,28,theory(equality)])). cnf(31,derived,(d=c),inference(sr,[status(thm)],[8,7,theory(equality)])). cnf(32,derived,(c=b|$false),inference(rw,[status(thm)],[30,31,theory(equality)])). cnf(33,derived,(c=b),inference(cn,[status(thm)],[32,theory(equality)])). cnf(34,derived,(b=a),inference(pm,[status(thm)],[6,33,theory(equality)])). cnf(36,derived,(k(b,b)!=k(X1,X1)),inference(rw,[status(thm)],[13,34,theory(equality)])). cnf(75,derived,($false),inference(er,[status(thm)],[36,theory(equality)])). cnf(76,derived,($false),75,['proof']). # Proof object ends here.
# Problem is unsatisfiable (or provable), constructing proof object # TSTP exit status: Theorem # Proof object starts here. fof(1, axiom,?[X1]:?[X2]:![X3]:![X4]:(big_f(X3,X4)<=>(X3=X1&X4=X2)),file('/Users/schulz/EPROVER/TPTP_3.0.1_FLAT/SYN075+1.p', pel52_1)). fof(2, conjecture,?[X2]:![X4]:(?[X1]:![X3]:(big_f(X3,X4)<=>X3=X1)<=>X4=X2),file('/Users/schulz/EPROVER/TPTP_3.0.1_FLAT/SYN075+1.p', pel52)). fof(3, negated_conjecture-derived,~(?[X2]:![X4]:(?[X1]:![X3]:(big_f(X3,X4)<=>X3=X1)<=>X4=X2)),inference(assume_negation,[status(cth)],[2])). fof(4, derived,?[X1]:?[X2]:![X3]:![X4]:((~(big_f(X3,X4))|(X3=X1&X4=X2))&((~(X3=X1)|~(X4=X2))|big_f(X3,X4))),inference(fof_nnf,[status(thm)],[1])). fof(5, derived,?[X1]:?[X2]:(![X3]:![X4]:(~(big_f(X3,X4))|(X3=X1&X4=X2))&![X3]:![X4]:((~(X3=X1)|~(X4=X2))|big_f(X3,X4))),inference(shift_quantors,[status(thm)],[4])). fof(6, derived,?[X5]:?[X6]:(![X7]:![X8]:(~(big_f(X7,X8))|(X7=X5&X8=X6))&![X9]:![X10]:((~(X9=X5)|~(X10=X6))|big_f(X9,X10))),inference(variable_rename,[status(thm)],[5])). fof(7, derived,(![X7]:![X8]:(~(big_f(X7,X8))|(X7=esk1_0&X8=esk2_0))&![X9]:![X10]:((~(X9=esk1_0)|~(X10=esk2_0))|big_f(X9,X10))),inference(skolemize,[status(sab)],[6])). fof(8, derived,![X7]:![X8]:![X9]:![X10]:(((X7=esk1_0|~(big_f(X7,X8)))&(X8=esk2_0|~(big_f(X7,X8))))&((~(X9=esk1_0)|~(X10=esk2_0))|big_f(X9,X10))),inference(distribute,[status(thm)],[7])). cnf(9,derived,(big_f(X1,X2)|X2!=esk2_0|X1!=esk1_0),inference(split_conjunct,[status(thm)],[8])). cnf(10,derived,(X2=esk2_0|~big_f(X1,X2)),inference(split_conjunct,[status(thm)],[8])). cnf(11,derived,(X1=esk1_0|~big_f(X1,X2)),inference(split_conjunct,[status(thm)],[8])). fof(12, negated_conjecture-derived,![X2]:?[X4]:((![X1]:?[X3]:((~(big_f(X3,X4))|~(X3=X1))&(big_f(X3,X4)|X3=X1))|~(X4=X2))&(?[X1]:![X3]:((big_f(X3,X4)&X3=X1)|(~(big_f(X3,X4))&~(X3=X1)))|X4=X2)),inference(fof_nnf,[status(thm)],[3])). fof(13, negated_conjecture-derived,![X5]:?[X6]:((![X7]:?[X8]:((~(big_f(X8,X6))|~(X8=X7))&(big_f(X8,X6)|X8=X7))|~(X6=X5))&(?[X9]:![X10]:((big_f(X10,X6)&X10=X9)|(~(big_f(X10,X6))&~(X10=X9)))|X6=X5)),inference(variable_rename,[status(thm)],[12])). fof(14, negated_conjecture-derived,![X5]:((![X7]:((~(big_f(esk4_2(X5,X7),esk3_1(X5)))|~(esk4_2(X5,X7)=X7))&(big_f(esk4_2(X5,X7),esk3_1(X5))|esk4_2(X5,X7)=X7))|~(esk3_1(X5)=X5))&(![X10]:((big_f(X10,esk3_1(X5))&X10=esk5_1(X5))|(~(big_f(X10,esk3_1(X5)))&~(X10=esk5_1(X5))))|esk3_1(X5)=X5)),inference(skolemize,[status(sab)],[13])). fof(15, negated_conjecture-derived,![X5]:![X7]:![X10]:((((~(big_f(esk4_2(X5,X7),esk3_1(X5)))|~(esk4_2(X5,X7)=X7))|~(esk3_1(X5)=X5))&((big_f(esk4_2(X5,X7),esk3_1(X5))|esk4_2(X5,X7)=X7)|~(esk3_1(X5)=X5)))&((((~(big_f(X10,esk3_1(X5)))|big_f(X10,esk3_1(X5)))|esk3_1(X5)=X5)&((~(X10=esk5_1(X5))|big_f(X10,esk3_1(X5)))|esk3_1(X5)=X5))&(((~(big_f(X10,esk3_1(X5)))|X10=esk5_1(X5))|esk3_1(X5)=X5)&((~(X10=esk5_1(X5))|X10=esk5_1(X5))|esk3_1(X5)=X5)))),inference(distribute,[status(thm)],[14])). cnf(18,negated_conjecture-derived,(esk3_1(X1)=X1|big_f(X2,esk3_1(X1))|X2!=esk5_1(X1)),inference(split_conjunct,[status(thm)],[15])). cnf(20,negated_conjecture-derived,(esk4_2(X1,X2)=X2|big_f(esk4_2(X1,X2),esk3_1(X1))|esk3_1(X1)!=X1),inference(split_conjunct,[status(thm)],[15])). cnf(21,negated_conjecture-derived,(esk3_1(X1)!=X1|esk4_2(X1,X2)!=X2|~big_f(esk4_2(X1,X2),esk3_1(X1))),inference(split_conjunct,[status(thm)],[15])). cnf(24,negated_conjecture-derived,(esk3_1(X1)=X1|big_f(esk5_1(X1),esk3_1(X1))),inference(er,[status(thm)],[18,theory(equality)])). cnf(26,negated_conjecture-derived,(esk1_0=esk4_2(X1,X2)|esk4_2(X1,X2)=X2|esk3_1(X1)!=X1),inference(spm,[status(thm)],[11,20,theory(equality)])). cnf(27,negated_conjecture-derived,(esk2_0=esk3_1(X1)|esk4_2(X1,X2)=X2|esk3_1(X1)!=X1),inference(spm,[status(thm)],[10,20,theory(equality)])). cnf(29,negated_conjecture-derived,(esk4_2(X1,X2)!=X2|esk3_1(X1)!=X1|esk1_0!=esk4_2(X1,X2)|esk2_0!=esk3_1(X1)),inference(spm,[status(thm)],[21,9,theory(equality)])). cnf(31,negated_conjecture-derived,(esk1_0=esk5_1(X1)|esk3_1(X1)=X1),inference(spm,[status(thm)],[11,24,theory(equality)])). cnf(32,negated_conjecture-derived,(esk2_0=esk3_1(X1)|esk3_1(X1)=X1),inference(spm,[status(thm)],[10,24,theory(equality)])). cnf(35,negated_conjecture-derived,(esk3_1(X1)=X1|big_f(esk1_0,esk3_1(X1))),inference(spm,[status(thm)],[24,31,theory(equality)])). cnf(36,negated_conjecture-derived,(esk3_1(X2)=X2|esk2_0!=X2),inference(ef,[status(thm)],[32,theory(equality)])). cnf(46,negated_conjecture-derived,(esk4_2(X1,X2)!=X2|~big_f(esk4_2(X1,X2),X1)|esk2_0!=X1),inference(spm,[status(thm)],[21,36,theory(equality)])). cnf(54,negated_conjecture-derived,(esk2_0=X1|big_f(esk1_0,esk2_0)|esk3_1(X1)=X1),inference(spm,[status(thm)],[35,32,theory(equality)])). cnf(60,negated_conjecture-derived,(esk4_2(X1,X2)!=X2|~big_f(esk4_2(X1,X2),X1)),inference(csr,[status(thm)],[46,10])). cnf(71,negated_conjecture-derived,(esk3_1(X1)=X1|big_f(esk1_0,esk2_0)),inference(csr,[status(thm)],[54,36])). cnf(76,negated_conjecture-derived,(esk3_1(X1)=esk2_0|esk4_2(X1,X2)=X2),inference(csr,[status(thm)],[27,32])). cnf(79,negated_conjecture-derived,(esk3_1(X1)=esk2_0|~big_f(X2,X1)),inference(spm,[status(thm)],[60,76,theory(equality)])). cnf(87,negated_conjecture-derived,(esk3_1(esk2_0)=esk2_0|esk3_1(X1)=X1),inference(spm,[status(thm)],[79,71,theory(equality)])). cnf(101,negated_conjecture-derived,(esk3_1(esk2_0)=esk2_0),inference(ef,[status(thm)],[87,theory(equality)])). cnf(113,negated_conjecture-derived,(esk4_2(esk2_0,X1)=esk1_0|esk4_2(esk2_0,X1)=X1),inference(spm,[status(thm)],[26,101,theory(equality)])). cnf(114,negated_conjecture-derived,(esk4_2(esk2_0,X2)=X2|esk1_0!=X2),inference(ef,[status(thm)],[113,theory(equality)])). cnf(143,negated_conjecture-derived,(X1!=esk1_0|esk3_1(esk2_0)!=esk2_0),inference(spm,[status(thm)],[29,114,theory(equality)])). cnf(150,negated_conjecture-derived,(X1!=esk1_0|$false),inference(rw,[status(thm)],[143,101,theory(equality)])). cnf(151,negated_conjecture-derived,(X1!=esk1_0),inference(cn,[status(thm)],[150,theory(equality)])). cnf(152,negated_conjecture-derived,($false),inference(er,[status(thm)],[151,theory(equality)])). cnf(155,negated_conjecture-derived,($false),152,['proof']). # Proof object ends here.
# Problem is unsatisfiable (or provable), constructing proof object # TSTP exit status: Unsatisfiable # Proof object starts here. cnf(1,axiom,(X1=a|~big_f(X1,X2)),file('/Users/schulz/EPROVER/TPTP_3.0.1_FLAT/SYN075-1.p', clause_1)). cnf(3,axiom,(big_f(X1,X2)|X1!=a|X2!=b),file('/Users/schulz/EPROVER/TPTP_3.0.1_FLAT/SYN075-1.p', clause_3)). cnf(4,negated_conjecture,(f(X2)=X2|~big_f(X1,f(X2))|X1!=g(X2)),file('/Users/schulz/EPROVER/TPTP_3.0.1_FLAT/SYN075-1.p', clause_4)). cnf(6,negated_conjecture,(big_f(X1,f(X2))|f(X2)=X2|X1!=g(X2)),file('/Users/schulz/EPROVER/TPTP_3.0.1_FLAT/SYN075-1.p', clause_6)). cnf(9,negated_conjecture,(big_f(h(X1,X2),f(X1))|h(X1,X2)=X2|f(X1)!=X1),file('/Users/schulz/EPROVER/TPTP_3.0.1_FLAT/SYN075-1.p', clause_9)). cnf(10,negated_conjecture,(f(X1)!=X1|h(X1,X2)!=X2|~big_f(h(X1,X2),f(X1))),file('/Users/schulz/EPROVER/TPTP_3.0.1_FLAT/SYN075-1.p', clause_10)). cnf(14,negated_conjecture-derived,(f(X2)=X2|g(X2)!=X1),inference(csr,[status(thm)],[4,6])). cnf(15,negated_conjecture-derived,(f(X1)=X1),inference(er,[status(thm)],[14,theory(equality)])). cnf(19,negated_conjecture-derived,(h(X1,X2)!=X2|f(X1)!=X1|a!=h(X1,X2)|b!=f(X1)),inference(spm,[status(thm)],[10,3,theory(equality)])). cnf(23,negated_conjecture-derived,(h(X1,X2)!=a|h(X1,X2)!=X2|X1!=b|f(X1)!=X1),inference(rw,[status(thm)],[19,15,theory(equality)])). cnf(24,negated_conjecture-derived,(h(X1,X2)!=a|h(X1,X2)!=X2|X1!=b|$false),inference(rw,[status(thm)],[23,15,theory(equality)])). cnf(25,negated_conjecture-derived,(h(X1,X2)!=a|h(X1,X2)!=X2|X1!=b),inference(cn,[status(thm)],[24,theory(equality)])). cnf(28,negated_conjecture-derived,(h(X1,X2)!=X2|$false|~big_f(h(X1,X2),f(X1))),inference(rw,[status(thm)],[10,15,theory(equality)])). cnf(29,negated_conjecture-derived,(h(X1,X2)!=X2|$false|~big_f(h(X1,X2),X1)),inference(rw,[status(thm)],[28,15,theory(equality)])). cnf(30,negated_conjecture-derived,(h(X1,X2)!=X2|~big_f(h(X1,X2),X1)),inference(cn,[status(thm)],[29,theory(equality)])). cnf(33,negated_conjecture-derived,(h(X1,X2)=X2|big_f(h(X1,X2),X1)|f(X1)!=X1),inference(rw,[status(thm)],[9,15,theory(equality)])). cnf(34,negated_conjecture-derived,(h(X1,X2)=X2|big_f(h(X1,X2),X1)|$false),inference(rw,[status(thm)],[33,15,theory(equality)])). cnf(35,negated_conjecture-derived,(h(X1,X2)=X2|big_f(h(X1,X2),X1)),inference(cn,[status(thm)],[34,theory(equality)])). cnf(38,negated_conjecture-derived,(a=h(X1,X2)|h(X1,X2)=X2),inference(spm,[status(thm)],[1,35,theory(equality)])). cnf(50,negated_conjecture-derived,(h(X1,X2)=a|~big_f(X2,X1)),inference(spm,[status(thm)],[30,38,theory(equality)])). cnf(56,negated_conjecture-derived,(a!=X2|X1!=b|~big_f(X2,X1)),inference(spm,[status(thm)],[25,50,theory(equality)])). cnf(59,negated_conjecture-derived,(a!=X2|X1!=b),inference(csr,[status(thm)],[56,3])). cnf(60,negated_conjecture-derived,(epred1_0|a!=X2),inference(split,[split(esplit,[])],[59])). cnf(61,negated_conjecture-derived,(epred2_0|X1!=b),inference(split,[split(esplit,[])],[59])). cnf(62,negated_conjecture-derived,(~epred2_0|~epred1_0),inference(split,[split(esplit,[])],[59])). cnf(63,negated_conjecture-derived,(epred1_0),inference(er,[status(thm)],[60,theory(equality)])). cnf(65,negated_conjecture-derived,(epred2_0),inference(er,[status(thm)],[61,theory(equality)])). cnf(73,negated_conjecture-derived,($false|~epred1_0),inference(rw,[status(thm)],[62,65,theory(equality)])). cnf(74,negated_conjecture-derived,($false|$false),inference(rw,[status(thm)],[73,63,theory(equality)])). cnf(75,negated_conjecture-derived,($false),inference(cn,[status(thm)],[74,theory(equality)])). cnf(76,negated_conjecture-derived,($false),75,['proof']). # Proof object ends here.
E-KRHyper accepts input in the TPTP-supported Protein-format (*.tme), and therefore clauses are written in the Prolog-like manner of that format.
Normally the proof output of E-KRHyper is in the form of a large and somewhat illegible Prolog-term representing a tree structure, which in turn represents the relevant tableau derivation steps for the closing of each branch, with cross references where subtrees are shared between subderivations. However, for CASC we use a postprocessor script to translate this tree-term into proof steps more in line with the output of the other provers. The sample files are the result of such translations. If you have any specific preferences regarding the output formatting, it should be simple (to a degree) for us to incorporate them by adjusting the postprocessor.
Here is a brief rundown of the current proof output. The examples are taken from the proof for SYN075-1. Each line represents an inference step. General schema of a line:
nodeID>: (Each line starts with a tableau node-identifier and the clause C labeling the node, followed by '<-' and the inference yielding C, with a list of the clauses used as inference input. Node identifiers are unique within a tableau, and once derived a clause will be referred to by its node identifier for brevity.) <- ([inferenceInputList])
Example:
node13: (big_f(A, f(B)); f(B)=B :- g(B)=A) <- input([])In the example we have the node 'node13' with the clause '(big_f(A, f(B)); f(B)=B :- g(B)=A)'. As it is taken directly from the problem, the inference type is stated as 'input' and the list of inference input clauses is empty.
Next example:
node12: (big_f(g(A), f(A)); f(A)=A) <- reflexivity([node13])The clause labeling node13 from the first example has been used as input for the 'reflexivity' inference rule, yielding the new node 'node12' with its clause.
The following inference types exist:
node13: (big_f(A, f(B)); f(B)=B :- g(B)=A) <- input([]) node12: (big_f(g(A), f(A)); f(A)=A) <- reflexivity([node13])
node8: (false :- big_f(h(A, B), f(A)), f(A)=A, h(A, B)=B) <- input([]) node9: (f(b)=b) <- hyperresolution/split([node10, node11]) node7: (false :- f(b)=b, big_f(h(b, A), b), h(b, A)=A) <- superposition-left([node8, node9])
node36: (f(b)=b) <- branch([disj3]) node39: (big_f(h(b, a), f(b))) <- branch([disj53]) node38: (big_f(h(b, a), b)) <- unit-superposition-right([node39, node36])
If C is a Horn clause, then the inferred clause is a positive unit consisting of the positive literal of C, with the hyperresolution-unifier applied. Example:
node10: (b=A :- big_f(B, A)) <- input([]) node11: (big_f(g(b), f(b))) <- branch([disj3]) node9: (f(b)=b) <- hyperresolution/split([node10, node11])If C is not a Horn clause, then it gets a bit tricky, as a case split occurs. No clause is inferred immediately, rather a special disjunction node (with no clause label) is created. Such nodes have identifiers 'disj1', 'disj2', etc., instead of 'node1', 'node2'. In subsequent inference steps the disjunct unit clauses are derived, using the 'branch' inference with the disjunction node as input. The hyperresolution-unifier is applied to each disjunct. In addition a ground substitution is applied to any variables shared between disjuncts, as per the (E-)hyper tableau calculus. Example:
node12: (big_f(g(A), f(A)); f(A)=A) <- reflexivity([node13]) disj3: (---) <- hyperresolution/split([node12]) node11: (big_f(g(b), f(b))) <- branch([disj3]) node36: (f(b)=b) <- branch([disj3])The clause from node12 above has no negative literals, so the input for the hyperresolution/split-inference contains only node12, and the inference creates the disjunction node disj3. From this the tableau branches out with the two disjuncts (node11 and node36), eliminating their shared variable 'A' by substituting 'b'.
The proof for GEO069-3 demonstrates the aforementioned use of negative units for the resolution of positive literals. The negative unit of node12 resolves away one of the positive literals of the clause of node6, so the final splitting actually results in only one branch, with no real split:
node6: (p11(A, B, C); A=D :- p11(D, A, B), p11(D, A, C)) <- input([]) node7: (p11(c14, c15, c16)) <- hyperresolution/split([node8, node9]) node10: (p11(c14, c15, c17)) <- hyperresolution/split([node8, node11]) node12: (~(c15=c14)) <- input([]) disj70: (---) <- hyperresolution/split([node6, node7, node10, node12]) node5: (p11(c15, c17, c16)) <- branch([disj70])
Once the empty clause 'false' has been inferred, that particular tableau branch is closed. All branches have to be closed for a refutation. Example:
node21: (big_f(a, b)) <- reflexivity([node22]) node43: (false :- big_f(a, b)) <- reflexivity([node44]) node42: (false) <- hyperresolution/split([node43, node21])
node8: (false :- big_f(h(A, B), f(A)), f(A)=A, h(A, B)=B) <- input([]) node10: (b=A :- big_f(B, A)) <- input([]) node13: (big_f(A, f(B)); f(B)=B :- g(B)=A) <- input([]) node12: (big_f(g(A), f(A)); f(A)=A) <- reflexivity([node13]) disj3: (---) <- hyperresolution/split([node12]) node11: (big_f(g(b), f(b))) <- branch([disj3]) node9: (f(b)=b) <- hyperresolution/split([node10, node11]) node7: (false :- f(b)=b, big_f(h(b, A), b), h(b, A)=A) <- superposition-left([node8, node9]) node6: (false :- b=b, big_f(h(b, A), b), h(b, A)=A) <- superposition-left([node7, node9]) node5: (false :- big_f(h(b, A), b), h(b, A)=A) <- reflexivity([node6]) node15: (a=A :- big_f(A, B)) <- input([]) node20: (big_f(h(A, B), f(A)); h(A, B)=B :- f(A)=A) <- input([]) node19: (big_f(h(b, A), f(b)); h(b, A)=A :- b=b) <- superposition-left([node20, node9]) node18: (big_f(h(b, A), f(b)); h(b, A)=A) <- reflexivity([node19]) disj62: (---) <- hyperresolution/split([node18]) node17: (big_f(h(b, a), f(b))) <- branch([disj62]) node16: (big_f(h(b, a), b)) <- unit-superposition-right([node17, node9]) node14: (h(b, a)=a) <- hyperresolution/split([node15, node16]) node4: (false :- big_f(a, b), h(b, a)=a) <- superposition-left([node5, node14]) node3: (false :- big_f(a, b), a=a) <- superposition-left([node4, node14]) node2: (false :- big_f(a, b)) <- reflexivity([node3]) node23: (big_f(A, B) :- a=A, b=B) <- input([]) node22: (big_f(A, b) :- a=A) <- reflexivity([node23]) node21: (big_f(a, b)) <- reflexivity([node22]) node1: (false) <- hyperresolution/split([node2, node21]) node28: (h(b, a)=a) <- branch([disj62]) node27: (false :- big_f(a, b), h(b, a)=a) <- superposition-left([node5, node28]) node26: (false :- big_f(a, b), a=a) <- superposition-left([node27, node28]) node25: (false :- big_f(a, b)) <- reflexivity([node26]) node24: (false) <- hyperresolution/split([node25, node21]) node36: (f(b)=b) <- branch([disj3]) node35: (false :- f(b)=b, big_f(h(b, A), b), h(b, A)=A) <- superposition-left([node8, node36]) node34: (false :- b=b, big_f(h(b, A), b), h(b, A)=A) <- superposition-left([node35, node36]) node33: (false :- big_f(h(b, A), b), h(b, A)=A) <- reflexivity([node34]) node41: (big_f(h(b, A), f(b)); h(b, A)=A :- b=b) <- superposition-left([node20, node36]) node40: (big_f(h(b, A), f(b)); h(b, A)=A) <- reflexivity([node41]) disj53: (---) <- hyperresolution/split([node40]) node39: (big_f(h(b, a), f(b))) <- branch([disj53]) node38: (big_f(h(b, a), b)) <- unit-superposition-right([node39, node36]) node37: (h(b, a)=a) <- hyperresolution/split([node15, node38]) node32: (false :- big_f(a, b), h(b, a)=a) <- superposition-left([node33, node37]) node31: (false :- big_f(a, b), a=a) <- superposition-left([node32, node37]) node30: (false :- big_f(a, b)) <- reflexivity([node31]) node29: (false) <- hyperresolution/split([node30, node21]) node46: (h(b, a)=a) <- branch([disj53]) node45: (false :- big_f(a, b), h(b, a)=a) <- superposition-left([node33, node46]) node44: (false :- big_f(a, b), a=a) <- superposition-left([node45, node46]) node43: (false :- big_f(a, b)) <- reflexivity([node44])
Transformation
Geo always starts with a transformation to geometric formulas.
(GNF-transformation)
The intermediate results are shown, but it is not really
documented which steps were made in the transformation.
Proofs
Proofs contain the following rules:
Models
Models are represented by listing the atoms that are true in them.
The elements in the model have form E0, E1, E2, E3, E4, etc.
There are the following types of atoms in models:
-------------------------------------- 0: (nrappl = 1/0, lastappl = 7/0) (deleted,sound) -> # V0 /\ pppp3(V0) -------------------------------------- 1: (nrappl = 1/0, lastappl = 7/0) (deleted,sound) pppp3(V0) -> # V1 /\ pppp2(V0,V1) -------------------------------------- 2: (nrappl = 1/0, lastappl = 6/0) (deleted,sound) pppp2(V0,V1) /\ pppp0(V2,V3,V0,V1) -> big_f(V2,V3) -------------------------------------- 3: (nrappl = 2/0, lastappl = 4/0) (deleted,sound) pppp2(V0,V1) /\ big_f(V2,V3) -> pppp0(V2,V3,V0,V1) -------------------------------------- 4: (nrappl = 1/1, lastappl = 2/6) (deleted,sound) pppp0(V0,V1,V2,V3) /\ V0 != V2 -> FALSE -------------------------------------- 5: (nrappl = 1/1, lastappl = 4/6) (deleted,sound) pppp0(V0,V1,V2,V3) /\ V1 != V3 -> FALSE -------------------------------------- 6: (nrappl = 1/0, lastappl = 7/0) (deleted,sound) # V2 /\ # V3 -> pppp0(V2,V3,V2,V3) -------------------------------------- 7: (nrappl = 1/0, lastappl = 6/0) (deleted,sound) # V0 -> # V1 /\ pppp4(V1,V0) -------------------------------------- 8: (nrappl = 1/0, lastappl = 3/0) (deleted,sound) pppp4(V1,V1) /\ pppp1(V1) -> FALSE -------------------------------------- 9: (nrappl = 1/0, lastappl = 6/0) (deleted,sound) pppp4(V0,V1) /\ V0 != V1 -> pppp1(V0) -------------------------------------- 10: (nrappl = 1/0, lastappl = 6/0) (deleted,sound) pppp1(V0) -> # V1 /\ pppp5(V0,V1) -------------------------------------- 11: (nrappl = 1/0, lastappl = 3/0) (deleted,sound) # V0 /\ # V1 -> pppp1(V0) \/ pppp7(V0,V1) -------------------------------------- 12: (nrappl = 1/0, lastappl = 2/0) (deleted,sound) pppp7(V0,V1) -> # V2 /\ pppp6(V2,V0,V1) -------------------------------------- 13: (nrappl = 2/0, lastappl = 2/0) (deleted,sound) pppp6(V2,V1,V2) /\ big_f(V2,V1) -> FALSE -------------------------------------- 14: (nrappl = 1/0, lastappl = 2/0) (deleted,sound) pppp6(V0,V1,V2) /\ V0 != V2 -> big_f(V0,V1) -------------------------------------- 15: (nrappl = 2/0, lastappl = 5/0) (deleted,sound) pppp5(V0,V1) -> big_f(V1,V0) -------------------------------------- 17: Pick(3),Disj(4) (nrappl = 2/3, lastappl = 5/6) (deleted,sound) pppp2(V0,V1) /\ big_f(V2,V3) /\ V2 != V0 -> FALSE -------------------------------------- 18: Pick(14),Disj(17) (nrappl = 1/0, lastappl = 2/0) (deleted,sound) pppp2(V3,V4) /\ pppp6(V0,V1,V2) /\ V0 != V2 /\ V0 != V3 -> FALSE -------------------------------------- 19: Pick(12),Exist(18),Disj(13),Disj(13) (nrappl = 2/0, lastappl = 4/0) (deleted,sound) pppp2(V1,V2) /\ pppp7(V0,V1) /\ big_f(V1,V0) -> FALSE -------------------------------------- 20: Pick(11),Disj(8),Disj(19) (nrappl = 1/0, lastappl = 4/0) (deleted,sound) pppp4(V0,V0) /\ big_f(V1,V0) /\ pppp2(V1,V2) -> FALSE -------------------------------------- 21: Pick(3),Disj(5),eq(17) (nrappl = 1/2, lastappl = 4/4) (deleted,sound) pppp2(V0,V1) /\ big_f(V0,V3) /\ V3 != V1 -> FALSE -------------------------------------- 23: Pick(20),eq(21) (nrappl = 2/0, lastappl = 6/0) (deleted,sound) pppp4(V2,V2) /\ big_f(V1,V2) /\ pppp2(V1,V2) -> FALSE -------------------------------------- 24: Pick(15),Disj(21) (nrappl = 1/0, lastappl = 6/0) (deleted,sound) pppp5(V0,V1) /\ pppp2(V1,V2) /\ V0 != V2 -> FALSE -------------------------------------- 25: Pick(15),Disj(17) (nrappl = 1/0, lastappl = 6/0) (deleted,sound) pppp5(V0,V1) /\ pppp2(V2,V3) /\ V1 != V2 -> FALSE -------------------------------------- 26: Pick(10),Exist(25),Disj(24) (nrappl = 1/0, lastappl = 6/0) (deleted,sound) pppp1(V0) /\ pppp2(V1,V3) /\ V0 != V3 -> FALSE -------------------------------------- 27: Pick(9),Disj(26) (nrappl = 1/0, lastappl = 6/0) (deleted,sound) pppp2(V2,V3) /\ pppp4(V0,V1) /\ V0 != V1 /\ V0 != V3 -> FALSE -------------------------------------- 28: Pick(7),Exist(27),Disj(23),Disj(23),eq(17),eq(17) (nrappl = 1/0, lastappl = 6/0) (deleted,sound) pppp2(V1,V0) /\ big_f(V1,V0) -> FALSE -------------------------------------- 29: Pick(2),Disj(28),eq(4),eq(5) (nrappl = 1/0, lastappl = 7/0) (deleted,sound) pppp2(V0,V1) /\ pppp0(V0,V1,V0,V1) -> FALSE -------------------------------------- 30: Pick(6),Disj(29) (nrappl = 1/0, lastappl = 7/0) (deleted,sound) pppp2(V0,V1) -> FALSE -------------------------------------- 31: Pick(1),Exist(30) (nrappl = 1/0, lastappl = 7/0) (deleted,sound) pppp3(V0) -> FALSE -------------------------------------- 32: Pick(0),Exist(31) (nrappl = 0/0, lastappl = 0/0) (active,sound) -> FALSE
-------------------------------------- 0: (nrappl = 1/5, lastappl = 2/5) (deleted,sound) P_a(V0) /\ big_f(V1,V2) /\ V1 != V0 -> FALSE -------------------------------------- 1: (nrappl = 1/4, lastappl = 3/3) (deleted,sound) P_a(V0) /\ P_b(V1) /\ big_f(V3,V2) /\ V2 != V1 -> FALSE -------------------------------------- 2: (nrappl = 1/0, lastappl = 5/0) (deleted,sound) P_a(V0) /\ P_b(V1) -> big_f(V0,V1) -------------------------------------- 4: (nrappl = 1/0, lastappl = 3/0) (deleted,sound) P_a(V0) /\ P_b(V1) /\ P_f(V2,V3) /\ P_g(V2,V4) /\ V3 != V2 -> big_f(V4,V3) -------------------------------------- 7: (nrappl = 1/0, lastappl = 2/0) (deleted,sound) P_a(V0) /\ P_b(V1) /\ P_f(V2,V2) /\ P_h(V2,V4,V5) /\ V5 != V4 -> big_f(V5,V2) -------------------------------------- 8: (nrappl = 2/0, lastappl = 2/0) (deleted,sound) P_a(V0) /\ P_b(V1) /\ P_f(V2,V2) /\ P_h(V2,V4,V4) /\ big_f(V4,V2) -> FALSE -------------------------------------- 9: (nrappl = 1/0, lastappl = 6/0) (deleted,sound) -> # V0 /\ P_a(V0) -------------------------------------- 10: (nrappl = 1/0, lastappl = 6/0) (deleted,sound) -> # V0 /\ P_b(V0) -------------------------------------- 11: (nrappl = 1/0, lastappl = 5/0) (deleted,sound) # V0 -> # V1 /\ P_f(V0,V1) -------------------------------------- 12: (nrappl = 1/0, lastappl = 5/0) (deleted,sound) # V0 -> # V1 /\ P_g(V0,V1) -------------------------------------- 13: (nrappl = 1/0, lastappl = 2/0) (deleted,sound) # V0 /\ # V1 -> # V2 /\ P_h(V0,V1,V2) -------------------------------------- 14: Pick(7),Disj(0) (nrappl = 1/0, lastappl = 2/0) (deleted,sound) P_a(V5) /\ P_b(V1) /\ P_f(V2,V2) /\ P_h(V2,V3,V4) /\ V4 != V3 /\ V4 != V5 -> FALSE -------------------------------------- 15: Pick(13),Exist(14),Disj(8),Disj(8),eq(0),eq(0),eq(1),eq(1),eq(1) (nrappl = 2/0, lastappl = 5/0) (deleted,sound) P_b(V6) /\ P_a(V5) /\ big_f(V5,V6) /\ P_f(V6,V6) -> FALSE -------------------------------------- 16: Pick(4),Disj(1) (nrappl = 1/0, lastappl = 5/0) (deleted,sound) P_a(V5) /\ P_b(V6) /\ P_g(V2,V4) /\ P_f(V2,V3) /\ V3 != V2 /\ V3 != V6 -> FALSE -------------------------------------- 18: Pick(12),Exist(16) (nrappl = 1/0, lastappl = 5/0) (deleted,sound) P_a(V1) /\ P_b(V2) /\ P_f(V0,V3) /\ V3 != V0 /\ V3 != V2 -> FALSE -------------------------------------- 19: Pick(11),Exist(18),Disj(15),Disj(15),eq(0),eq(0) (nrappl = 1/0, lastappl = 5/0) (deleted,sound) P_a(V1) /\ P_b(V0) /\ big_f(V1,V0) -> FALSE -------------------------------------- 20: Pick(2),Disj(19) (nrappl = 1/0, lastappl = 6/0) (deleted,sound) P_a(V0) /\ P_b(V1) -> FALSE -------------------------------------- 21: Pick(10),Exist(20) (nrappl = 1/0, lastappl = 6/0) (deleted,sound) P_a(V0) -> FALSE -------------------------------------- 22: Pick(9),Exist(21) (nrappl = 0/0, lastappl = 0/0) (active,sound) -> FALSE
0 : 17() (0/1) [ 0; L0, W1 ] # E0 1 : 17() (0/1) [ 0; L0, W1 ] P_first_movers(E0) 2 : 18() (0/2) [ 0; L0, W1 ] P_efficient_producers(E0) 3 : 0(1,2) (0/2) [ 0; L1, W3 ] pppp1(E0,E0,E0) 4 : 10(1,2) (0/2) [ 0; L1, W3 ] pppp4(E0,E0,E0) 5 : 12(4) (0/1) [ 0; L2, W4 ] stable(E0) 6 : 13(4) (0/1) [ 0; L2, W4 ] environment(E0) 7 : 19(0,0) (0/2) [ 0; L1, W3 ] P_disbanding_rate(E0,E0,E0) 8 : 20(0,0) (0/2) [ 0; L1, W3 ] P_founding_rate(E0,E0,E0) 9 : 21(0,0) (0/2) [ 0; L1, W3 ] P_growth_rate(E0,E0,E0) 10 : 1(3,7,7) (0/2) [ 0; L2, W10 ] pppp0(E0,E0,E0,E0) 11 : 3(10) (0/1) [ 0; L3, W11 ] subpopulations(E0,E0,E0,E0) 12 : 7(1,2,6,5) (0/2) [ 0; L3, W11 ] pppp2(E0,E0,E0,E0) 13 : 9(12) (0/1) [ 0; L4, W12 ] in_environment(E0,E0) 14 : 11(4,13) (0/2) [ 0; L5, W16 ] pppp3(E0,E0,E0,E0,E0) 15 : 15(14,9,9) (0/1) [ 0; L6, W23 ] greater_or_equal(E0,E0)
0 : 17() (0/1) [ 0; L0, W1 ] # E0 1 : 17() (0/1) [ 0; L0, W1 ] P_at(E0) 2 : 18() (0/2) [ 0; L0, W1 ] P_t(E0) 3 : 19() (0/2) [ 0; L0, W1 ] P_a(E0) 4 : 21() (0/2) [ 0; L0, W1 ] P_b(E0) 5 : 23() (0/2) [ 0; L0, W1 ] P_an_a_nonce(E0) 6 : 27() (0/2) [ 0; L0, W1 ] P_bt(E0) 7 : 28(0) (0/2) [ 0; L1, W2 ] P_generate_b_nonce(E0,E0) 8 : 29(0) (0/2) [ 0; L1, W2 ] P_generate_expiration_time(E0,E0) 9 : 30(0) (0/2) [ 0; L1, W2 ] P_generate_key(E0,E0) 10 : 16(0,0) (0/2) [ 0; L1, W3 ] P_key(E0,E0,E0) 11 : 0(1,2,10) (0/1) [ 0; L2, W6 ] a_holds(E0) 12 : 1(1,2,10,3) (0/1) [ 0; L2, W7 ] party_of_protocol(E0) 13 : 22(0,0) (0/2) [ 0; L1, W3 ] P_pair(E0,E0,E0) 14 : 25(0,0) (0/2) [ 0; L1, W3 ] P_encrypt(E0,E0,E0) 15 : 20(0,0,0) (0/2) [ 0; L1, W4 ] P_sent(E0,E0,E0,E0) 16 : 2(1,2,10,3,4,5,13,15) (0/1) [ 0; L2, W16 ] message(E0) 17 : 3(1,2,10,3,4,5,13,15,13) (0/1) [ 0; L2, W19 ] a_stored(E0) 18 : 6(1,2,10,3,4,5,13,15,13,6,10) (0/1) [ 0; L2, W23 ] b_holds(E0) 19 : 8(1,2,10,3,4,5,13,15,13,6,10) (0/1) [ 0; L2, W23 ] fresh_to_b(E0) 20 : 12(1,2,10,3,4,5,13,15,13,6,10,10) (0/1) [ 0; L2, W26 ] t_holds(E0) 21 : 24(0,0,0) (0/2) [ 0; L1, W4 ] P_triple(E0,E0,E0,E0) 22 : 10(1,2,10,3,4,5,13,15,13,6,10,7,8,19,13,15,21,14,21,15,16) (0/1) [ 0; L3, W88 ] b_stored(E0) 23 : 26(0,0,0,0) (0/2) [ 0; L1, W5 ] P_quadruple(E0,E0,E0,E0,E0)
0 : 16() (0/1) [ 0; L0, W1 ] # E0 1 : 16() (0/1) [ 0; L0, W1 ] P_e(E0) 2 : 18() (0/2) [ 0; L0, W1 ] P_an_organisation(E0) 3 : 19() (0/2) [ 0; L0, W1 ] P_zero(E0) 4 : 22() (0/2) [ 0; L0, W1 ] P_efficient_producers(E0) 5 : 23() (1/2) [ 7; L0, W1 ] # E1 6 : 23() (1/2) [ 7; L0, W1 ] P_first_movers(E1) 7 : 9(1,2,3,4,6,0) (0/1) [ 7; L1, W7 ] greater_or_equal(E0,E0) 8 : 9(1,2,3,4,6,5) (0/1) [ 7; L1, W7 ] greater_or_equal(E1,E1) 9 : 24() (1/3) [ 33; L0, W1 ] P_sk2(E1) 10 : 15(0,0) (0/3) [ 33; L1, W3 ] P_number_of_organizations(E0,E0,E0) 11 : 15(0,5) (0/3) [ 33; L1, W3 ] P_number_of_organizations(E0,E1,E0) 12 : 15(5,0) (0/3) [ 33; L1, W3 ] P_number_of_organizations(E1,E0,E0) 13 : 15(5,5) (0/3) [ 33; L1, W3 ] P_number_of_organizations(E1,E1,E0) 14 : 17(0,0) (0/3) [ 33; L1, W3 ] P_appear(E0,E0,E0) 15 : 12(1,2,3,4,6,14,9) (0/1) [ 33; L2, W10 ] environment(E1) 16 : 17(0,5) (1/3) [ 34; L1, W3 ] P_appear(E0,E1,E1) 17 : 13(1,2,3,4,6,14,9,16) (0/1) [ 34; L2, W13 ] in_environment(E1,E1) 18 : 0(1,2,3,16,11,15) (0/1) [ 34; L3, W20 ] greater(E0,E0) 19 : 17(5,0) (0/3) [ 34; L1, W3 ] P_appear(E1,E0,E0) 20 : 17(5,5) (0/3) [ 34; L1, W3 ] P_appear(E1,E1,E0) 21 : 5(1,2,3,4,6,20,16,15) (0/1) [ 34; L3, W22 ] greater_or_equal(E0,E1) 22 : 7(1,2,3,4,6,21,5) (0/1) [ 34; L4, W29 ] greater(E0,E1) 23 : 20(0,0) (0/3) [ 34; L1, W3 ] P_sk1(E0,E0,E0) 24 : 20(0,5) (0/3) [ 34; L1, W3 ] P_sk1(E0,E1,E0) 25 : 1(1,2,3,15,12,24,18) (0/1) [ 34; L4, W40 ] subpopulation(E0,E1,E0) 26 : 20(5,0) (0/3) [ 34; L1, W3 ] P_sk1(E1,E0,E0) 27 : 20(5,5) (0/3) [ 34; L1, W3 ] P_sk1(E1,E1,E0) 28 : 1(1,2,3,15,13,27,18) (0/1) [ 34; L4, W40 ] subpopulation(E0,E1,E1) 29 : 21(0,0) (0/3) [ 34; L1, W3 ] P_cardinality_at_time(E0,E0,E0) 30 : 21(0,5) (0/3) [ 34; L1, W3 ] P_cardinality_at_time(E0,E1,E0) 31 : 21(5,0) (0/3) [ 34; L1, W3 ] P_cardinality_at_time(E1,E0,E0) 32 : 21(5,5) (1/3) [ 35; L1, W3 ] P_cardinality_at_time(E1,E1,E1)
The inference rules of Metis are ...
(* ------------------------------------------------------------------------- *) (* *) (* ----- axiom C *) (* C *) (* ------------------------------------------------------------------------- *) (* ------------------------------------------------------------------------- *) (* *) (* ----------- assume L *) (* L \/ ~L *) (* ------------------------------------------------------------------------- *) (* ------------------------------------------------------------------------- *) (* C *) (* -------- subst s *) (* C[s] *) (* ------------------------------------------------------------------------- *) (* ------------------------------------------------------------------------- *) (* L \/ C ~L \/ D *) (* --------------------- resolve L *) (* C \/ D *) (* *) (* The literal L must occur in the first theorem, and the literal ~L must *) (* occur in the second theorem. *) (* ------------------------------------------------------------------------- *) (* ------------------------------------------------------------------------- *) (* *) (* --------- refl t *) (* t = t *) (* ------------------------------------------------------------------------- *) (* ------------------------------------------------------------------------- *) (* *) (* ------------------------ equality L p t *) (* ~(s = t) \/ ~L \/ L' *) (* *) (* where s is the subterm of L at path p, and L' is L with the subterm at *) (* path p being replaced by t. *) (* ------------------------------------------------------------------------- *)
(0) |- ~($X = a) \/ ~($Y = b) \/ big_f $X $Y [Axiom] (1) |- ~(a = a) \/ ~(b = b) \/ big_f a b [Subst {sub = <[X |-> a, Y |-> b]>, thm = (0)}] (2) |- a = a [Refl a] (3) |- ~(b = b) \/ big_f a b [Resolve {res = a = a, pos = (2), neg = (1)}] (4) |- b = b [Refl b] (5) |- big_f a b [Resolve {res = b = b, pos = (4), neg = (3)}] (6) |- ~(f $X = $X) \/ ~(h $X $Z = $Z) \/ ~big_f (h $X $Z) (f $X) [Axiom] (7) |- ~(h $X $Z = $Z) \/ h $X $Z = $Z [Assume h $X $Z = $Z] (8) |- ~(h $X $Z = $Z) \/ ~big_f $Z (f $X) \/ big_f (h $X $Z) (f $X) [Equality {lit = ~big_f (h $X $Z) (f $X), path = [0], res = $Z}] (9) |- ~(f $X = $X) \/ f $X = $X [Assume f $X = $X] (10) |- ~(f $X = $X) \/ ~big_f $Z $X \/ big_f $Z (f $X) [Equality {lit = ~big_f $Z (f $X), path = [1], res = $X}] (11) |- ~(f $X = $X) \/ ~(h $X $Z = $Z) \/ ~big_f $Z $X \/ big_f (h $X $Z) (f $X) [Resolve {res = big_f $Z (f $X), pos = (10), neg = (8)}] (12) |- ~(f $X = $X) \/ ~(h $X $Z = $Z) \/ ~big_f $Z $X [Resolve {res = big_f (h $X $Z) (f $X), pos = (11), neg = (6)}] (13) |- ~($Y = g $X) \/ ~big_f $Y (f $X) \/ f $X = $X [Axiom] (14) |- ~(g $X = g $X) \/ ~big_f (g $X) (f $X) \/ f $X = $X [Subst {sub = <[Y |-> g $X]>, thm = (13)}] (15) |- g $X = g $X [Refl g $X] (16) |- ~big_f (g $X) (f $X) \/ f $X = $X [Resolve {res = g $X = g $X, pos = (15), neg = (14)}] (17) |- ~big_f (g $_5) (f $_5) \/ f $_5 = $_5 [Subst {sub = <[X |-> $_5]>, thm = (16)}] (18) |- ~($Y = g $X) \/ f $X = $X \/ big_f $Y (f $X) [Axiom] (19) |- ~(g $X = g $X) \/ f $X = $X \/ big_f (g $X) (f $X) [Subst {sub = <[Y |-> g $X]>, thm = (18)}] (20) |- f $X = $X \/ big_f (g $X) (f $X) [Resolve {res = g $X = g $X, pos = (15), neg = (19)}] (21) |- f $_5 = $_5 \/ big_f (g $_5) (f $_5) [Subst {sub = <[X |-> $_5]>, thm = (20)}] (22) |- f $_5 = $_5 [Resolve {res = big_f (g $_5) (f $_5), pos = (21), neg = (17)}] (23) |- f $X = $X [Subst {sub = <[_5 |-> $X]>, thm = (22)}] (24) |- ~($X = $X) \/ ~(f $X = $X) \/ f $X = $X [Equality {lit = f $X = $X, path = [0, 0], res = $X}] (25) |- ~($X = $X) \/ f $X = $X [Resolve {res = f $X = $X, pos = (23), neg = (24)}] (26) |- ~($X = $X) \/ ~(h $X $Z = $Z) \/ ~big_f $Z $X [Resolve {res = f $X = $X, pos = (25), neg = (12)}] (27) |- $X = $X [Refl $X] (28) |- ~(h $X $Z = $Z) \/ ~big_f $Z $X [Resolve {res = $X = $X, pos = (27), neg = (26)}] (29) |- ~(h $X a = a) \/ ~big_f a $X [Subst {sub = <[Z |-> a]>, thm = (28)}] (30) |- ~big_f $X $Y \/ $X = a [Axiom] (31) |- ~big_f (h $_9 $_10) $_9 \/ h $_9 $_10 = a [Subst {sub = <[X |-> h $_9 $_10, Y |-> $_9]>, thm = (30)}] (32) |- ~(f $X = $X) \/ h $X $Z = $Z \/ big_f (h $X $Z) (f $X) [Axiom] (33) |- ~(f $X = $X) \/ ~big_f (h $X $Z) (f $X) \/ big_f (h $X $Z) $X [Equality {lit = big_f (h $X $Z) (f $X), path = [1], res = $X}] (34) |- ~(f $X = $X) \/ h $X $Z = $Z \/ big_f (h $X $Z) $X [Resolve {res = big_f (h $X $Z) (f $X), pos = (32), neg = (33)}] (35) |- ~($X = $X) \/ h $X $Z = $Z \/ big_f (h $X $Z) $X [Resolve {res = f $X = $X, pos = (25), neg = (34)}] (36) |- h $X $Z = $Z \/ big_f (h $X $Z) $X [Resolve {res = $X = $X, pos = (27), neg = (35)}] (37) |- h $_9 $_10 = $_10 \/ big_f (h $_9 $_10) $_9 [Subst {sub = <[X |-> $_9, Z |-> $_10]>, thm = (36)}] (38) |- h $_9 $_10 = $_10 \/ h $_9 $_10 = a [Resolve {res = big_f (h $_9 $_10) $_9, pos = (37), neg = (31)}] (39) |- h $X a = a [Subst {sub = <[_10 |-> a, _9 |-> $X]>, thm = (38)}] (40) |- ~(a = a) \/ ~(h $X a = a) \/ h $X a = a [Equality {lit = h $X a = a, path = [0, 1], res = a}] (41) |- ~(a = a) \/ h $X a = a [Resolve {res = h $X a = a, pos = (39), neg = (40)}] (42) |- ~(a = a) \/ ~big_f a $X [Resolve {res = h $X a = a, pos = (41), neg = (29)}] (43) |- ~big_f a $X [Resolve {res = a = a, pos = (2), neg = (42)}] (44) |- ~big_f a b [Subst {sub = <[X |-> b]>, thm = (43)}] (45) |- F [Resolve {res = big_f a b, pos = (5), neg = (44)}]
|- ~greater (disbanding_rate first_movers skolem_T) (disbanding_rate efficient_producers skolem_T) |- environment skolem_E |- environment skolem_E_1 |- stable skolem_E |- subpopulations first_movers efficient_producers skolem_E_1 skolem_T |- ~greater (growth_rate efficient_producers (skolem_T_1 $To)) (growth_rate first_movers (skolem_T_1 $To)) \/ ~in_environment skolem_E $To |- ~in_environment skolem_E $To \/ greater_or_equal (skolem_T_1 $To) $To |- ~in_environment skolem_E $To \/ subpopulations first_movers efficient_producers skolem_E (skolem_T_1 $To) |- ~environment $E \/ ~stable $E \/ in_environment $E (skolem_To $E) |- ~greater (disbanding_rate first_movers $T) (disbanding_rate efficient_producers $T) \/ ~greater_or_equal (founding_rate efficient_producers $T) (founding_rate first_movers $T) \/ greater (growth_rate efficient_producers $T) (growth_rate first_movers $T) |- ~greater_or_equal $X $Y \/ $X = $Y \/ greater $X $Y |- ~environment $E \/ ~greater_or_equal $T (skolem_To $E) \/ ~stable $E \/ ~subpopulations first_movers efficient_producers $E $T \/ greater_or_equal (founding_rate efficient_producers $T) (founding_rate first_movers $T) |- in_environment skolem_E (skolem_To skolem_E) |- greater_or_equal (skolem_T_1 (skolem_To skolem_E)) (skolem_To skolem_E) |- subpopulations first_movers efficient_producers skolem_E (skolem_T_1 (skolem_To skolem_E)) |- skolem_T_1 (skolem_To skolem_E) = skolem_To skolem_E \/ greater (skolem_T_1 (skolem_To skolem_E)) (skolem_To skolem_E) |- greater_or_equal (founding_rate efficient_producers (skolem_T_1 (skolem_To skolem_E))) (founding_rate first_movers (skolem_T_1 (skolem_To skolem_E))) |- ~greater_or_equal skolem_T (skolem_To skolem_E_1) \/ ~stable skolem_E_1 \/ greater_or_equal (founding_rate efficient_producers skolem_T) (founding_rate first_movers skolem_T) |- founding_rate efficient_producers (skolem_T_1 (skolem_To skolem_E)) = founding_rate first_movers (skolem_T_1 (skolem_To skolem_E)) \/ greater (founding_rate efficient_producers (skolem_T_1 (skolem_To skolem_E))) (founding_rate first_movers (skolem_T_1 (skolem_To skolem_E))) |- ~greater (disbanding_rate first_movers (skolem_T_1 (skolem_To skolem_E))) (disbanding_rate efficient_producers (skolem_T_1 (skolem_To skolem_E))) \/ greater (growth_rate efficient_producers (skolem_T_1 (skolem_To skolem_E))) (growth_rate first_movers (skolem_T_1 (skolem_To skolem_E)))
|- a_holds (key at t) |- a_stored (b, an_a_nonce) |- b_holds (key bt t) |- fresh_to_b an_a_nonce |- message (sent a b (a, an_a_nonce)) |- party_of_protocol a |- party_of_protocol b |- party_of_protocol t |- t_holds (key at a) |- t_holds (key bt b) |- ~a_stored ($Y, $Z) \/ ~message (sent t a (triple (encrypt (quadruple $Y $Z $W $V) at) $X $U)) \/ a_holds (key $W $Y) |- ~a_stored ($Y, $Z) \/ ~message (sent t a (triple (encrypt (quadruple $Y $Z $W $V) at) $X $U)) \/ message (sent a $Y ($X, encrypt $U $W)) |- ~b_stored ($X, $Y) \/ ~message (sent $X b (encrypt (triple $X $V (generate_expiration_time $Y)) bt, encrypt (generate_b_nonce $Y) $V)) \/ b_holds (key $V $X) |- ~fresh_to_b $V \/ ~message (sent $U b ($U, $V)) \/ b_stored ($U, $V) |- ~fresh_to_b $V \/ ~message (sent $U b ($U, $V)) \/ message (sent b t (triple b (generate_b_nonce $V) (encrypt (triple $U $V (generate_expiration_time $V)) bt))) |- ~message (sent $U t (triple $U $V (encrypt (triple $W $X $Y) $Z))) \/ ~t_holds (key $X1 $W) \/ ~t_holds (key $Z $U) \/ message (sent t $W (triple (encrypt (quadruple $U $X (generate_key $X) $Y) $X1) (encrypt (triple $W (generate_key $X) $Y) $Z) $V)) |- b_stored (a, an_a_nonce) |- message (sent b t (triple b (generate_b_nonce an_a_nonce) (encrypt (triple a an_a_nonce (generate_expiration_time an_a_nonce)) bt))) |- ~t_holds (key $_23 a) \/ message (sent t a (triple (encrypt (quadruple b an_a_nonce (generate_key an_a_nonce) (generate_expiration_time an_a_nonce)) $_23) (encrypt (triple a (generate_key an_a_nonce) (generate_expiration_time an_a_nonce)) bt) (generate_b_nonce an_a_nonce))) |- message (sent t a (triple (encrypt (quadruple b an_a_nonce (generate_key an_a_nonce) (generate_expiration_time an_a_nonce)) at) (encrypt (triple a (generate_key an_a_nonce) (generate_expiration_time an_a_nonce)) bt) (generate_b_nonce an_a_nonce))) |- message (sent a b (encrypt (triple a (generate_key an_a_nonce) (generate_expiration_time an_a_nonce)) bt, encrypt (generate_b_nonce an_a_nonce) (generate_key an_a_nonce))) |- a_holds (key (generate_key an_a_nonce) b) |- b_holds (key (generate_key an_a_nonce) a)
|- ~environment $A \/ greater (number_of_organizations e (appear an_organisation $A)) zero |- ~environment $A \/ ~greater (number_of_organizations $A $B) zero \/ subpopulation (sk1 $B $A) $A $B |- ~environment $A \/ ~greater (number_of_organizations $A $B) zero \/ greater (cardinality_at_time (sk1 $B $A) $B) zero |- ~environment $A \/ ~greater (appear efficient_producers $A) $B \/ ~greater (cardinality_at_time efficient_producers $B) zero \/ ~in_environment $A $B |- ~environment $A \/ ~greater (appear first_movers $A) $B \/ ~greater (cardinality_at_time first_movers $B) zero \/ ~in_environment $A $B |- ~environment $A \/ greater_or_equal (appear first_movers $A) (appear an_organisation $A) |- ~greater $A $B \/ ~greater $B $C \/ greater $A $C |- ~greater_or_equal $A $B \/ $A = $B \/ greater $A $B |- ~greater $A $B \/ greater_or_equal $A $B |- greater_or_equal $B $B |- ~environment $A \/ ~greater (cardinality_at_time $B $C) zero \/ ~subpopulation $B $A $C \/ $B = efficient_producers \/ $B = first_movers |- ~environment $A \/ greater (appear efficient_producers e) (appear first_movers $A) |- environment sk2 |- in_environment sk2 (appear an_organisation sk2) |- ~(appear an_organisation sk2 = appear first_movers sk2) |- greater (number_of_organizations e (appear an_organisation sk2)) zero |- greater_or_equal (number_of_organizations e (appear an_organisation sk2)) zero |- greater_or_equal (appear first_movers sk2) (appear an_organisation sk2) |- greater (appear efficient_producers e) (appear first_movers sk2) |- greater_or_equal (appear efficient_producers e) (appear first_movers sk2) |- greater (appear first_movers sk2) (appear an_organisation sk2) |- ~greater (appear first_movers sk2) $_10 \/ greater (appear efficient_producers e) $_10 |- ~greater (appear an_organisation sk2) $_10 \/ greater (appear first_movers sk2) $_10 |- ~greater zero $_10 \/ greater (number_of_organizations e (appear an_organisation sk2)) $_10 |- ~greater $_8 (appear efficient_producers e) \/ greater $_8 (appear first_movers sk2) |- ~greater $_8 (appear first_movers sk2) \/ greater $_8 (appear an_organisation sk2) |- ~greater $_8 (number_of_organizations e (appear an_organisation sk2)) \/ greater $_8 zero |- greater (appear efficient_producers e) (appear an_organisation sk2) |- ~greater $A (appear efficient_producers e) \/ greater $A (appear an_organisation sk2) |- ~greater (appear an_organisation sk2) $C \/ greater (appear efficient_producers e) $C |- greater_or_equal (appear efficient_producers e) (appear an_organisation sk2) |- ~environment e \/ subpopulation (sk1 (appear an_organisation sk2) e) e (appear an_organisation sk2) |- ~environment e \/ greater (cardinality_at_time (sk1 (appear an_organisation sk2) e) (appear an_organisation sk2)) zero
---------------- PROOF ---------------- 1 [] -big_f(A,B)|equal(A,a). 2 [] -big_f(A,B)|equal(B,b). 3 [] -equal(A,a)| -equal(B,b)|big_f(A,B). 4 [] -big_f(A,f(B))| -equal(A,g(B))|equal(f(B),B). 5 [] -equal(A,g(B))|big_f(A,f(B))|equal(f(B),B). 8 [] -equal(f(A),A)|big_f(h(A,B),f(A))|equal(h(A,B),B). 9 [] -equal(f(A),A)| -equal(h(A,B),B)| -big_f(h(A,B),f(A)). 11 [] equal(A,A). 13 [hyper,11,5] big_f(g(A),f(A))|equal(f(A),A). 14 [hyper,11,3,11] big_f(a,b). 21 [hyper,13,3,11] big_f(g(b),f(b))|big_f(a,f(b)). 62 [hyper,21,4,11] big_f(a,f(b))|equal(f(b),b). 79 [hyper,62,3,11,factor_simp] big_f(a,f(b)). 81,80 [hyper,79,2] equal(f(b),b). 126 [hyper,80,8,demod,81] big_f(h(b,A),b)|equal(h(b,A),A). 319 [hyper,126,3,80,demod,81,factor_simp] big_f(h(b,a),b). 331,330 [hyper,319,1] equal(h(b,a),a). 335 [para_from,330.1.1,9.3.1,demod,81,331,81,unit_del,11,11,14] $F. ------------ end of proof -------------
---------------- PROOF ---------------- 1 [] animal(A)| -wolf(A). 2 [] animal(A)| -fox(A). 3 [] animal(A)| -bird(A). 5 [] animal(A)| -snail(A). 6 [] plant(A)| -grain(A). 7 [] eats(A,B)|eats(A,C)| -animal(A)| -plant(B)| -animal(C)| -plant(D)| -much_smaller(C,A)| -eats(C,D). 9 [] much_smaller(A,B)| -snail(A)| -bird(B). 10 [] much_smaller(A,B)| -bird(A)| -fox(B). 11 [] much_smaller(A,B)| -fox(A)| -wolf(B). 13 [] -wolf(A)| -grain(B)| -eats(A,B). 15 [] -bird(A)| -snail(B)| -eats(A,B). 18 [] plant(snail_food_of(A))| -snail(A). 19 [] eats(A,snail_food_of(A))| -snail(A). 20 [] -animal(A)| -animal(B)| -grain(C)| -eats(A,B)| -eats(B,C). 23 [factor,7.4.6] eats(A,B)|eats(A,C)| -animal(A)| -plant(B)| -animal(C)| -much_smaller(C,A)| -eats(C,B). 28 [] wolf(a_wolf). 29 [] fox(a_fox). 30 [] bird(a_bird). 32 [] snail(a_snail). 33 [] grain(a_grain). 34 [hyper,28,1] animal(a_wolf). 35 [hyper,29,11,28] much_smaller(a_fox,a_wolf). 36 [hyper,29,2] animal(a_fox). 37 [hyper,30,10,29] much_smaller(a_bird,a_fox). 38 [hyper,30,3] animal(a_bird). 44 [hyper,32,19] eats(a_snail,snail_food_of(a_snail)). 45 [hyper,32,18] plant(snail_food_of(a_snail)). 46 [hyper,32,9,30] much_smaller(a_snail,a_bird). 47 [hyper,32,5] animal(a_snail). 48 [hyper,33,6] plant(a_grain). 50 [hyper,44,7,38,48,47,45,46] eats(a_bird,a_grain)|eats(a_bird,a_snail). 55 [hyper,50,15,30,32] eats(a_bird,a_grain). 56 [hyper,55,23,36,48,38,37] eats(a_fox,a_grain)|eats(a_fox,a_bird). 62 [hyper,56,20,36,38,33,55] eats(a_fox,a_grain). 63 [hyper,62,23,34,48,36,35] eats(a_wolf,a_grain)|eats(a_wolf,a_fox). 67 [hyper,63,13,28,33] eats(a_wolf,a_fox). 69 [hyper,67,20,34,36,33,62] $F. ------------ end of proof -------------
NOTE: In order to save space in the representation of the model, sometimes, some entries in some of the definition tables are missing. This is not a bug! More detailedly, it might happen that for a model with a domain of size n, for some argument position, only a subset {'1,'2,..,'k} of all domain elements is shown, with k < n. What this means is that the entries for other domain elements 'j (with k < j <= n) occurring at that argument position look the same as entries with 'k at that position. Problem NLP041-1.p is an example where a model is represented in such a way.
an_organisation = '1 appear('1,'1) = '2 appear('1,'2) = '2 appear('2,'1) = '1 appear('2,'2) = '1 cardinality_at_time('1,'1) = '2 cardinality_at_time('1,'2) = '2 cardinality_at_time('2,'1) = '2 cardinality_at_time('2,'2) = '2 e = '1 efficient_producers = '2 environment('1) : FALSE environment('2) : TRUE first_movers = '2 greater('1,'1) : TRUE greater('1,'2) : TRUE greater('2,'1) : FALSE greater('2,'2) : TRUE greater_or_equal('1,'1) : TRUE greater_or_equal('1,'2) : TRUE greater_or_equal('2,'1) : FALSE greater_or_equal('2,'2) : TRUE in_environment('1,'1) : TRUE in_environment('1,'2) : TRUE in_environment('2,'1) : TRUE in_environment('2,'2) : TRUE number_of_organizations('1,'1) = '2 number_of_organizations('1,'2) = '1 number_of_organizations('2,'1) = '2 number_of_organizations('2,'2) = '2 sk1('1,'1) = '2 sk1('1,'2) = '2 sk1('2,'1) = '2 sk1('2,'2) = '2 sk2 = '2 subpopulation('1,'1,'1) : TRUE subpopulation('1,'1,'2) : TRUE subpopulation('1,'2,'1) : TRUE subpopulation('1,'2,'2) : TRUE subpopulation('2,'1,'1) : TRUE subpopulation('2,'1,'2) : TRUE subpopulation('2,'2,'1) : TRUE subpopulation('2,'2,'2) : TRUE zero = '1
abstraction('1,'1) : FALSE abstraction('1,'2) : FALSE abstraction('1,'3) : FALSE abstraction('1,'4) : TRUE act('1,'1) : FALSE act('1,'2) : FALSE act('1,'3) : TRUE act('1,'4) : FALSE actual_world('1) : TRUE agent('1,'1,'1) : TRUE agent('1,'1,'2) : TRUE agent('1,'1,'3) : TRUE agent('1,'1,'4) : TRUE agent('1,'2,'1) : TRUE agent('1,'2,'2) : TRUE agent('1,'2,'3) : TRUE agent('1,'2,'4) : TRUE agent('1,'3,'1) : TRUE agent('1,'3,'2) : FALSE agent('1,'3,'3) : FALSE agent('1,'3,'4) : FALSE agent('1,'4,'1) : TRUE agent('1,'4,'2) : TRUE agent('1,'4,'3) : TRUE agent('1,'4,'4) : FALSE animate('1,'1) : TRUE animate('1,'2) : FALSE animate('1,'3) : FALSE animate('1,'4) : FALSE beverage('1,'1) : FALSE beverage('1,'2) : TRUE beverage('1,'3) : FALSE beverage('1,'4) : FALSE entity('1,'1) : TRUE entity('1,'2) : TRUE entity('1,'3) : FALSE entity('1,'4) : FALSE event('1,'1) : FALSE event('1,'2) : FALSE event('1,'3) : TRUE event('1,'4) : FALSE eventuality('1,'1) : FALSE eventuality('1,'2) : FALSE eventuality('1,'3) : TRUE eventuality('1,'4) : FALSE existent('1,'1) : TRUE existent('1,'2) : TRUE existent('1,'3) : FALSE existent('1,'4) : FALSE female('1,'1) : TRUE female('1,'2) : FALSE female('1,'3) : FALSE female('1,'4) : FALSE food('1,'1) : FALSE food('1,'2) : TRUE food('1,'3) : FALSE food('1,'4) : FALSE forename('1,'1) : FALSE forename('1,'2) : FALSE forename('1,'3) : FALSE forename('1,'4) : TRUE general('1,'1) : FALSE general('1,'2) : FALSE general('1,'3) : FALSE general('1,'4) : TRUE human('1,'1) : TRUE human('1,'2) : FALSE human('1,'3) : FALSE human('1,'4) : FALSE human_person('1,'1) : TRUE human_person('1,'2) : FALSE human_person('1,'3) : FALSE human_person('1,'4) : FALSE impartial('1,'1) : TRUE impartial('1,'2) : TRUE impartial('1,'3) : FALSE impartial('1,'4) : FALSE living('1,'1) : TRUE living('1,'2) : FALSE living('1,'3) : FALSE living('1,'4) : FALSE mia_forename('1,'1) : FALSE mia_forename('1,'2) : FALSE mia_forename('1,'3) : FALSE mia_forename('1,'4) : TRUE nonexistent('1,'1) : FALSE nonexistent('1,'2) : FALSE nonexistent('1,'3) : TRUE nonexistent('1,'4) : TRUE nonhuman('1,'1) : FALSE nonhuman('1,'2) : TRUE nonhuman('1,'3) : TRUE nonhuman('1,'4) : TRUE nonliving('1,'1) : FALSE nonliving('1,'2) : TRUE nonliving('1,'3) : TRUE nonliving('1,'4) : TRUE nonreflexive('1,'1) : FALSE nonreflexive('1,'2) : FALSE nonreflexive('1,'3) : TRUE nonreflexive('1,'4) : TRUE object('1,'1) : FALSE object('1,'2) : TRUE object('1,'3) : FALSE object('1,'4) : FALSE of('1,'1,'1) : FALSE of('1,'1,'2) : TRUE of('1,'1,'3) : TRUE of('1,'1,'4) : TRUE of('1,'2,'1) : FALSE of('1,'2,'2) : TRUE of('1,'2,'3) : TRUE of('1,'2,'4) : TRUE of('1,'3,'1) : FALSE of('1,'3,'2) : TRUE of('1,'3,'3) : TRUE of('1,'3,'4) : TRUE of('1,'4,'1) : TRUE of('1,'4,'2) : TRUE of('1,'4,'3) : TRUE of('1,'4,'4) : TRUE order('1,'1) : FALSE order('1,'2) : FALSE order('1,'3) : TRUE order('1,'4) : FALSE organism('1,'1) : TRUE organism('1,'2) : FALSE organism('1,'3) : FALSE organism('1,'4) : FALSE past('1,'1) : FALSE past('1,'2) : FALSE past('1,'3) : TRUE past('1,'4) : FALSE patient('1,'1,'1) : TRUE patient('1,'1,'2) : TRUE patient('1,'1,'3) : TRUE patient('1,'1,'4) : TRUE patient('1,'2,'1) : TRUE patient('1,'2,'2) : TRUE patient('1,'2,'3) : TRUE patient('1,'2,'4) : TRUE patient('1,'3,'1) : FALSE patient('1,'3,'2) : TRUE patient('1,'3,'3) : TRUE patient('1,'3,'4) : TRUE patient('1,'4,'1) : FALSE patient('1,'4,'2) : FALSE patient('1,'4,'3) : FALSE patient('1,'4,'4) : TRUE relation('1,'1) : FALSE relation('1,'2) : FALSE relation('1,'3) : FALSE relation('1,'4) : TRUE relname('1,'1) : FALSE relname('1,'2) : FALSE relname('1,'3) : FALSE relname('1,'4) : TRUE shake_beverage('1,'1) : FALSE shake_beverage('1,'2) : TRUE shake_beverage('1,'3) : FALSE shake_beverage('1,'4) : FALSE singleton('1,'1) : TRUE singleton('1,'2) : TRUE singleton('1,'3) : TRUE singleton('1,'4) : TRUE skc5 = '1 skc6 = '3 skc7 = '2 skc8 = '4 skc9 = '1 specific('1,'1) : TRUE specific('1,'2) : TRUE specific('1,'3) : TRUE specific('1,'4) : FALSE substance_matter('1,'1) : FALSE substance_matter('1,'2) : TRUE substance_matter('1,'3) : FALSE substance_matter('1,'4) : FALSE thing('1,'1) : TRUE thing('1,'2) : TRUE thing('1,'3) : TRUE thing('1,'4) : TRUE unisex('1,'1) : FALSE unisex('1,'2) : TRUE unisex('1,'3) : TRUE unisex('1,'4) : TRUE woman('1,'1) : TRUE woman('1,'2) : FALSE woman('1,'3) : FALSE woman('1,'4) : FALSE
% domain size is 1 disbanding_rate(!1,!1) = !1 efficient_producers = !1 environment(!1) <=> $true first_movers = !1 founding_rate(!1,!1) = !1 greater(!1,!1) <=> $false greater_or_equal(!1,!1) <=> $true growth_rate(!1,!1) = !1 in_environment(!1,!1) <=> $true stable(!1) <=> $true subpopulations(!1,!1,!1,!1) <=> $true
% domain size is 1 a_holds(X1) a_stored(X1) b_holds(X1) b_stored(X1) fresh_to_b(X1) message(X1) party_of_protocol(X1) t_holds(X1)
% domain size is 2 an_organisation = !1 appear(!1,!1) = !2 appear(!1,!2) = !1 appear(!2,!1) = !1 appear(!2,!2) = !2 cardinality_at_time(!1,!1) = !2 cardinality_at_time(!1,!2) = !1 cardinality_at_time(!2,!1) = !1 cardinality_at_time(!2,!2) = !2 e = !1 efficient_producers = !1 environment(!1) <=> $false environment(!2) <=> $true first_movers = !2 greater(!1,!1) <=> $false greater(!1,!2) <=> $false greater(!2,!1) <=> $true greater(!2,!2) <=> $true greater_or_equal(!1,!1) <=> $true greater_or_equal(!1,!2) <=> $false greater_or_equal(!2,!1) <=> $true greater_or_equal(!2,!2) <=> $true in_environment(!1,!1) <=> $false in_environment(!1,!2) <=> $false in_environment(!2,!1) <=> $true in_environment(!2,!2) <=> $false number_of_organizations(!1,!1) = !2 number_of_organizations(!1,!2) = !1 number_of_organizations(!2,!1) = !1 number_of_organizations(!2,!2) = !2 sk1(!1,!1) = !1 sk1(!1,!2) = !2 sk1(!2,!1) = !2 sk1(!2,!2) = !2 sk2 = !2 subpopulation(!1,!1,!1) <=> $false subpopulation(!1,!1,!2) <=> $false subpopulation(!1,!2,!1) <=> $false subpopulation(!1,!2,!2) <=> $false subpopulation(!2,!1,!1) <=> $false subpopulation(!2,!1,!2) <=> $false subpopulation(!2,!2,!1) <=> $false subpopulation(!2,!2,!2) <=> $true zero = !1
=========== Refutation ========== *********** [1, input] *********** (? X0 X1)(! X2 X3)(big_f(X2,X3) <=> X2=X0 & X3=X1) *********** [1->77, normalize] *********** (? X0 X1)(! X2 X3)(big_f(X2,X3) <=> X2=X0 & X3=X1) ----------------------------- (? X0 X1)(! X2 X3)(big_f(X2,X3) <=> X3=X1 & X2=X0) *********** [77->84, NNF transformation] *********** (? X0 X1)(! X2 X3)(big_f(X2,X3) <=> X3=X1 & X2=X0) ----------------------------- (? X0 X1)(! X2 X3)((~big_f(X2,X3) \/ (X3=X1 & X2=X0)) & ((X3!=X1 \/ X2!=X0) \/ big_f(X2,X3))) *********** [84->85, flattening] *********** (? X0 X1)(! X2 X3)((~big_f(X2,X3) \/ (X3=X1 & X2=X0)) & ((X3!=X1 \/ X2!=X0) \/ big_f(X2,X3))) ----------------------------- (? X0 X1)(! X2 X3)((~big_f(X2,X3) \/ (X3=X1 & X2=X0)) & (X3!=X1 \/ X2!=X0 \/ big_f(X2,X3))) *********** [85->86, skolemization] *********** (? X0 X1)(! X2 X3)((~big_f(X2,X3) \/ (X3=X1 & X2=X0)) & (X3!=X1 \/ X2!=X0 \/ big_f(X2,X3))) ----------------------------- (~big_f(X2,X3) \/ (X3=$s12 & X2=$s11)) & (X3!=$s12 \/ X2!=$s11 \/ big_f(X2,X3)) *********** [86->93, cnf transformation] *********** (~big_f(X2,X3) \/ (X3=$s12 & X2=$s11)) & (X3!=$s12 \/ X2!=$s11 \/ big_f(X2,X3)) ----------------------------- big_f(X2,X3) \/ X2!=$s11 \/ X3!=$s12 *********** [93->116, equality resolution, passive clause reanimation] *********** big_f(X2,X3) \/ X2!=$s11 \/ X3!=$s12 ----------------------------- X1!=$s11 \/ big_f(X1,$s12) *********** [116->122, equality resolution, passive clause reanimation] *********** X1!=$s11 \/ big_f(X1,$s12) ----------------------------- big_f($s11,$s12) *********** [2, input] *********** ~(? X1)(! X3)((? X0)(! X2)(big_f(X2,X3) <=> X2=X0) <=> X3=X1) *********** [2->78, rectify] *********** ~(? X1)(! X3)((? X0)(! X2)(big_f(X2,X3) <=> X2=X0) <=> X3=X1) ----------------------------- ~(? X0)(! X1)((? X2)(! X3)(big_f(X3,X1) <=> X3=X2) <=> X1=X0) *********** [78->79, normalize] *********** ~(? X0)(! X1)((? X2)(! X3)(big_f(X3,X1) <=> X3=X2) <=> X1=X0) ----------------------------- ~(? X0)(! X1)(X1=X0 <=> (? X2)(! X3)(X3=X2 <=> big_f(X3,X1))) *********** [79->80, ENNF transformation] *********** ~(? X0)(! X1)(X1=X0 <=> (? X2)(! X3)(X3=X2 <=> big_f(X3,X1))) ----------------------------- (! X0)(? X1)(X1=X0 <~> (? X2)(! X3)(X3=X2 <=> big_f(X3,X1))) *********** [80->81, NNF transformation] *********** (! X0)(? X1)(X1=X0 <~> (? X2)(! X3)(X3=X2 <=> big_f(X3,X1))) ----------------------------- (! X0)(? X1)((X1=X0 \/ (? X2)(! X3)((X3!=X2 \/ big_f(X3,X1)) & (~big_f(X3,X1) \/ X3=X2))) & (X1!=X0 \/ (! X2)(? X3)((X3=X2 \/ big_f(X3,X1)) & (X3!=X2 \/ ~big_f(X3,X1))))) *********** [81->82, rectify] *********** (! X0)(? X1)((X1=X0 \/ (? X2)(! X3)((X3!=X2 \/ big_f(X3,X1)) & (~big_f(X3,X1) \/ X3=X2))) & (X1!=X0 \/ (! X2)(? X3)((X3=X2 \/ big_f(X3,X1)) & (X3!=X2 \/ ~big_f(X3,X1))))) ----------------------------- (! X0)(? X1)((X1=X0 \/ (? X2)(! X3)((X3!=X2 \/ big_f(X3,X1)) & (~big_f(X3,X1) \/ X3=X2))) & (X1!=X0 \/ (! X4)(? X5)((X5=X4 \/ big_f(X5,X1)) & (X5!=X4 \/ ~big_f(X5,X1))))) *********** [82->83, skolemization] *********** (! X0)(? X1)((X1=X0 \/ (? X2)(! X3)((X3!=X2 \/ big_f(X3,X1)) & (~big_f(X3,X1) \/ X3=X2))) & (X1!=X0 \/ (! X4)(? X5)((X5=X4 \/ big_f(X5,X1)) & (X5!=X4 \/ ~big_f(X5,X1))))) ----------------------------- ($s8(X0)=X0 \/ ((X3!=$s9(X1) \/ big_f(X3,$s8(X0))) & (~big_f(X3,$s8(X0)) \/ X3=$s9(X1)))) & ($s8(X0)!=X0 \/ (($s10(X1,X4)=X4 \/ big_f($s10(X1,X4),$s8(X0))) & ($s10(X1,X4)!=X4 \/ ~big_f($s10(X1,X4),$s8(X0))))) *********** [83->87, cnf transformation] *********** ($s8(X0)=X0 \/ ((X3!=$s9(X1) \/ big_f(X3,$s8(X0))) & (~big_f(X3,$s8(X0)) \/ X3=$s9(X1)))) & ($s8(X0)!=X0 \/ (($s10(X1,X4)=X4 \/ big_f($s10(X1,X4),$s8(X0))) & ($s10(X1,X4)!=X4 \/ ~big_f($s10(X1,X4),$s8(X0))))) ----------------------------- big_f(X3,$s8(X0)) \/ X3!=$s9(X1) \/ $s8(X0)=X0 *********** [87->118, equality resolution, passive clause reanimation] *********** big_f(X3,$s8(X0)) \/ X3!=$s9(X1) \/ $s8(X0)=X0 ----------------------------- big_f($s9(X1),$s8(X2)) \/ $s8(X2)=X2 *********** [86->91, cnf transformation] *********** (~big_f(X2,X3) \/ (X3=$s12 & X2=$s11)) & (X3!=$s12 \/ X2!=$s11 \/ big_f(X2,X3)) ----------------------------- X3=$s12 \/ ~big_f(X2,X3) *********** [118,91->123, resolution, passive clause reanimation] *********** big_f($s9(X1),$s8(X2)) \/ $s8(X2)=X2 X3=$s12 \/ ~big_f(X2,X3) ----------------------------- $s8(X1)=$s12 \/ $s8(X1)=X1 *********** [123->131, equality factoring, passive clause reanimation] *********** $s8(X1)=$s12 \/ $s8(X1)=X1 ----------------------------- $s12!=X1 \/ $s8(X1)=X1 *********** [131->146, equality resolution, passive clause reanimation] *********** $s12!=X1 \/ $s8(X1)=X1 ----------------------------- $s8($s12)=$s12 *********** [83->89, cnf transformation] *********** ($s8(X0)=X0 \/ ((X3!=$s9(X1) \/ big_f(X3,$s8(X0))) & (~big_f(X3,$s8(X0)) \/ X3=$s9(X1)))) & ($s8(X0)!=X0 \/ (($s10(X1,X4)=X4 \/ big_f($s10(X1,X4),$s8(X0))) & ($s10(X1,X4)!=X4 \/ ~big_f($s10(X1,X4),$s8(X0))))) ----------------------------- big_f($s10(X1,X4),$s8(X0)) \/ $s10(X1,X4)=X4 \/ $s8(X0)!=X0 *********** [146,89,146->202, backward superposition, forward demodulation, passive clause reanimation] *********** $s8($s12)=$s12 big_f($s10(X1,X4),$s8(X0)) \/ $s10(X1,X4)=X4 \/ $s8(X0)!=X0 $s8($s12)=$s12 ----------------------------- big_f($s10(X1,X2),$s12) \/ $s10(X1,X2)=X2 *********** [86->92, cnf transformation] *********** (~big_f(X2,X3) \/ (X3=$s12 & X2=$s11)) & (X3!=$s12 \/ X2!=$s11 \/ big_f(X2,X3)) ----------------------------- X2=$s11 \/ ~big_f(X2,X3) *********** [202,92->213, resolution, passive clause reanimation] *********** big_f($s10(X1,X2),$s12) \/ $s10(X1,X2)=X2 X2=$s11 \/ ~big_f(X2,X3) ----------------------------- $s10(X1,X2)=$s11 \/ $s10(X1,X2)=X2 *********** [213->296, equality factoring, passive clause reanimation] *********** $s10(X1,X2)=$s11 \/ $s10(X1,X2)=X2 ----------------------------- $s11!=X1 \/ $s10(X2,X1)=X1 *********** [296->320, equality resolution, passive clause reanimation] *********** $s11!=X1 \/ $s10(X2,X1)=X1 ----------------------------- $s10(X1,$s11)=$s11 *********** [83->90, cnf transformation] *********** ($s8(X0)=X0 \/ ((X3!=$s9(X1) \/ big_f(X3,$s8(X0))) & (~big_f(X3,$s8(X0)) \/ X3=$s9(X1)))) & ($s8(X0)!=X0 \/ (($s10(X1,X4)=X4 \/ big_f($s10(X1,X4),$s8(X0))) & ($s10(X1,X4)!=X4 \/ ~big_f($s10(X1,X4),$s8(X0))))) ----------------------------- ~big_f($s10(X1,X4),$s8(X0)) \/ $s10(X1,X4)!=X4 \/ $s8(X0)!=X0 *********** [146,90,146->192, backward superposition, forward demodulation, passive clause reanimation] *********** $s8($s12)=$s12 ~big_f($s10(X1,X4),$s8(X0)) \/ $s10(X1,X4)!=X4 \/ $s8(X0)!=X0 $s8($s12)=$s12 ----------------------------- $s10(X1,X2)!=X2 \/ ~big_f($s10(X1,X2),$s12) *********** [122,320,192,320->328, backward superposition, forward demodulation, forward subsumption resolution] *********** big_f($s11,$s12) $s10(X1,$s11)=$s11 $s10(X1,X2)!=X2 \/ ~big_f($s10(X1,X2),$s12) $s10(X1,$s11)=$s11 ----------------------------- # ======= End of refutation =======
=========== Refutation ========== *********** [3, input] *********** X0!=a \/ X1!=b \/ big_f(X0,X1) *********** [3->11, normalize] *********** X0!=a \/ X1!=b \/ big_f(X0,X1) ----------------------------- X1!=b \/ X0!=a \/ big_f(X0,X1) *********** [11->28, equality resolution] *********** X1!=b \/ X0!=a \/ big_f(X0,X1) ----------------------------- X1!=a \/ big_f(X1,b) *********** [28->35, equality resolution] *********** X1!=a \/ big_f(X1,b) ----------------------------- big_f(a,b) *********** [1, input] *********** ~big_f(X0,X1) \/ X0=a *********** [4, input] *********** ~big_f(X1,f(X0)) \/ X1!=g(X0) \/ f(X0)=X0 *********** [4->12, normalize] *********** ~big_f(X1,f(X0)) \/ X1!=g(X0) \/ f(X0)=X0 ----------------------------- X1!=g(X0) \/ ~big_f(X1,f(X0)) \/ X0=f(X0) *********** [12->21, literal permutation] *********** X1!=g(X0) \/ ~big_f(X1,f(X0)) \/ X0=f(X0) ----------------------------- X1!=g(X2) \/ ~big_f(X1,f(X2)) \/ f(X2)=X2 *********** [6, input] *********** X1!=g(X0) \/ big_f(X1,f(X0)) \/ f(X0)=X0 *********** [6->14, normalize] *********** X1!=g(X0) \/ big_f(X1,f(X0)) \/ f(X0)=X0 ----------------------------- X1!=g(X0) \/ X0=f(X0) \/ big_f(X1,f(X0)) *********** [21,14->22, forward subsumption resolution] *********** X1!=g(X2) \/ ~big_f(X1,f(X2)) \/ f(X2)=X2 X1!=g(X0) \/ X0=f(X0) \/ big_f(X1,f(X0)) ----------------------------- X1!=g(X2) \/ f(X2)=X2 *********** [22->29, equality resolution] *********** X1!=g(X2) \/ f(X2)=X2 ----------------------------- f(X1)=X1 *********** [9, input] *********** f(X0)!=X0 \/ big_f(h(X0,X2),f(X0)) \/ h(X0,X2)=X2 *********** [9->17, normalize] *********** f(X0)!=X0 \/ big_f(h(X0,X2),f(X0)) \/ h(X0,X2)=X2 ----------------------------- X0!=f(X0) \/ X2=h(X0,X2) \/ big_f(h(X0,X2),f(X0)) *********** [17->25, literal permutation] *********** X0!=f(X0) \/ X2=h(X0,X2) \/ big_f(h(X0,X2),f(X0)) ----------------------------- f(X1)!=X1 \/ big_f(h(X1,X2),f(X1)) \/ h(X1,X2)=X2 *********** [29,25->31, backward demodulation] *********** f(X1)=X1 f(X1)!=X1 \/ big_f(h(X1,X2),f(X1)) \/ h(X1,X2)=X2 ----------------------------- big_f(h(X1,X2),X1) \/ h(X1,X2)=X2 *********** [1,31->33, resolution] *********** ~big_f(X0,X1) \/ X0=a big_f(h(X1,X2),X1) \/ h(X1,X2)=X2 ----------------------------- h(X1,X2)=a \/ h(X1,X2)=X2 *********** [33->36, equality factoring] *********** h(X1,X2)=a \/ h(X1,X2)=X2 ----------------------------- a!=X1 \/ h(X2,X1)=X1 *********** [36->40, equality resolution] *********** a!=X1 \/ h(X2,X1)=X1 ----------------------------- h(X1,a)=a *********** [10, input] *********** f(X0)!=X0 \/ h(X0,X2)!=X2 \/ ~big_f(h(X0,X2),f(X0)) *********** [10->18, normalize] *********** f(X0)!=X0 \/ h(X0,X2)!=X2 \/ ~big_f(h(X0,X2),f(X0)) ----------------------------- X0!=f(X0) \/ X2!=h(X0,X2) \/ ~big_f(h(X0,X2),f(X0)) *********** [18->24, literal permutation] *********** X0!=f(X0) \/ X2!=h(X0,X2) \/ ~big_f(h(X0,X2),f(X0)) ----------------------------- h(X1,X2)!=X2 \/ ~big_f(h(X1,X2),f(X1)) \/ f(X1)!=X1 *********** [29,24->32, backward demodulation] *********** f(X1)=X1 h(X1,X2)!=X2 \/ ~big_f(h(X1,X2),f(X1)) \/ f(X1)!=X1 ----------------------------- h(X1,X2)!=X2 \/ ~big_f(h(X1,X2),X1) *********** [40,32,40->41, backward superposition, forward demodulation] *********** h(X1,a)=a h(X1,X2)!=X2 \/ ~big_f(h(X1,X2),X1) h(X1,a)=a ----------------------------- ~big_f(a,X1) *********** [35,41->42, resolution] *********** big_f(a,b) ~big_f(a,X1) ----------------------------- # ======= End of refutation =======
=========== Refutation ========== *********** [1, input] *********** (? X0 X1)(! X2 X3)(big_f(X2,X3) <=> X2=X0 & X3=X1) *********** [1->77, normalize] *********** (? X0 X1)(! X2 X3)(big_f(X2,X3) <=> X2=X0 & X3=X1) ----------------------------- (? X0 X1)(! X2 X3)(big_f(X2,X3) <=> X3=X1 & X2=X0) *********** [77->84, NNF transformation] *********** (? X0 X1)(! X2 X3)(big_f(X2,X3) <=> X3=X1 & X2=X0) ----------------------------- (? X0 X1)(! X2 X3)((~big_f(X2,X3) \/ (X3=X1 & X2=X0)) & ((X3!=X1 \/ X2!=X0) \/ big_f(X2,X3))) *********** [84->85, flattening] *********** (? X0 X1)(! X2 X3)((~big_f(X2,X3) \/ (X3=X1 & X2=X0)) & ((X3!=X1 \/ X2!=X0) \/ big_f(X2,X3))) ----------------------------- (? X0 X1)(! X2 X3)((~big_f(X2,X3) \/ (X3=X1 & X2=X0)) & (X3!=X1 \/ X2!=X0 \/ big_f(X2,X3))) *********** [85->86, skolemization] *********** (? X0 X1)(! X2 X3)((~big_f(X2,X3) \/ (X3=X1 & X2=X0)) & (X3!=X1 \/ X2!=X0 \/ big_f(X2,X3))) ----------------------------- (~big_f(X2,X3) \/ (X3=$s12 & X2=$s11)) & (X3!=$s12 \/ X2!=$s11 \/ big_f(X2,X3)) *********** [86->93, cnf transformation] *********** (~big_f(X2,X3) \/ (X3=$s12 & X2=$s11)) & (X3!=$s12 \/ X2!=$s11 \/ big_f(X2,X3)) ----------------------------- big_f(X2,X3) \/ X2!=$s11 \/ X3!=$s12 *********** [93->116, equality resolution, passive clause reanimation] *********** big_f(X2,X3) \/ X2!=$s11 \/ X3!=$s12 ----------------------------- X1!=$s11 \/ big_f(X1,$s12) *********** [116->122, equality resolution, passive clause reanimation] *********** X1!=$s11 \/ big_f(X1,$s12) ----------------------------- big_f($s11,$s12) *********** [2, input] *********** ~(? X1)(! X3)((? X0)(! X2)(big_f(X2,X3) <=> X2=X0) <=> X3=X1) *********** [2->78, rectify] *********** ~(? X1)(! X3)((? X0)(! X2)(big_f(X2,X3) <=> X2=X0) <=> X3=X1) ----------------------------- ~(? X0)(! X1)((? X2)(! X3)(big_f(X3,X1) <=> X3=X2) <=> X1=X0) *********** [78->79, normalize] *********** ~(? X0)(! X1)((? X2)(! X3)(big_f(X3,X1) <=> X3=X2) <=> X1=X0) ----------------------------- ~(? X0)(! X1)(X1=X0 <=> (? X2)(! X3)(X3=X2 <=> big_f(X3,X1))) *********** [79->80, ENNF transformation] *********** ~(? X0)(! X1)(X1=X0 <=> (? X2)(! X3)(X3=X2 <=> big_f(X3,X1))) ----------------------------- (! X0)(? X1)(X1=X0 <~> (? X2)(! X3)(X3=X2 <=> big_f(X3,X1))) *********** [80->81, NNF transformation] *********** (! X0)(? X1)(X1=X0 <~> (? X2)(! X3)(X3=X2 <=> big_f(X3,X1))) ----------------------------- (! X0)(? X1)((X1=X0 \/ (? X2)(! X3)((X3!=X2 \/ big_f(X3,X1)) & (~big_f(X3,X1) \/ X3=X2))) & (X1!=X0 \/ (! X2)(? X3)((X3=X2 \/ big_f(X3,X1)) & (X3!=X2 \/ ~big_f(X3,X1))))) *********** [81->82, rectify] *********** (! X0)(? X1)((X1=X0 \/ (? X2)(! X3)((X3!=X2 \/ big_f(X3,X1)) & (~big_f(X3,X1) \/ X3=X2))) & (X1!=X0 \/ (! X2)(? X3)((X3=X2 \/ big_f(X3,X1)) & (X3!=X2 \/ ~big_f(X3,X1))))) ----------------------------- (! X0)(? X1)((X1=X0 \/ (? X2)(! X3)((X3!=X2 \/ big_f(X3,X1)) & (~big_f(X3,X1) \/ X3=X2))) & (X1!=X0 \/ (! X4)(? X5)((X5=X4 \/ big_f(X5,X1)) & (X5!=X4 \/ ~big_f(X5,X1))))) *********** [82->83, skolemization] *********** (! X0)(? X1)((X1=X0 \/ (? X2)(! X3)((X3!=X2 \/ big_f(X3,X1)) & (~big_f(X3,X1) \/ X3=X2))) & (X1!=X0 \/ (! X4)(? X5)((X5=X4 \/ big_f(X5,X1)) & (X5!=X4 \/ ~big_f(X5,X1))))) ----------------------------- ($s8(X0)=X0 \/ ((X3!=$s9(X1) \/ big_f(X3,$s8(X0))) & (~big_f(X3,$s8(X0)) \/ X3=$s9(X1)))) & ($s8(X0)!=X0 \/ (($s10(X1,X4)=X4 \/ big_f($s10(X1,X4),$s8(X0))) & ($s10(X1,X4)!=X4 \/ ~big_f($s10(X1,X4),$s8(X0))))) *********** [83->87, cnf transformation] *********** ($s8(X0)=X0 \/ ((X3!=$s9(X1) \/ big_f(X3,$s8(X0))) & (~big_f(X3,$s8(X0)) \/ X3=$s9(X1)))) & ($s8(X0)!=X0 \/ (($s10(X1,X4)=X4 \/ big_f($s10(X1,X4),$s8(X0))) & ($s10(X1,X4)!=X4 \/ ~big_f($s10(X1,X4),$s8(X0))))) ----------------------------- big_f(X3,$s8(X0)) \/ X3!=$s9(X1) \/ $s8(X0)=X0 *********** [87->118, equality resolution, passive clause reanimation] *********** big_f(X3,$s8(X0)) \/ X3!=$s9(X1) \/ $s8(X0)=X0 ----------------------------- big_f($s9(X1),$s8(X2)) \/ $s8(X2)=X2 *********** [86->91, cnf transformation] *********** (~big_f(X2,X3) \/ (X3=$s12 & X2=$s11)) & (X3!=$s12 \/ X2!=$s11 \/ big_f(X2,X3)) ----------------------------- X3=$s12 \/ ~big_f(X2,X3) *********** [118,91->123, resolution, passive clause reanimation] *********** big_f($s9(X1),$s8(X2)) \/ $s8(X2)=X2 X3=$s12 \/ ~big_f(X2,X3) ----------------------------- $s8(X1)=$s12 \/ $s8(X1)=X1 *********** [123->131, equality factoring, passive clause reanimation] *********** $s8(X1)=$s12 \/ $s8(X1)=X1 ----------------------------- $s12!=X1 \/ $s8(X1)=X1 *********** [131->146, equality resolution, passive clause reanimation] *********** $s12!=X1 \/ $s8(X1)=X1 ----------------------------- $s8($s12)=$s12 *********** [83->89, cnf transformation] *********** ($s8(X0)=X0 \/ ((X3!=$s9(X1) \/ big_f(X3,$s8(X0))) & (~big_f(X3,$s8(X0)) \/ X3=$s9(X1)))) & ($s8(X0)!=X0 \/ (($s10(X1,X4)=X4 \/ big_f($s10(X1,X4),$s8(X0))) & ($s10(X1,X4)!=X4 \/ ~big_f($s10(X1,X4),$s8(X0))))) ----------------------------- big_f($s10(X1,X4),$s8(X0)) \/ $s10(X1,X4)=X4 \/ $s8(X0)!=X0 *********** [146,89,146->202, backward superposition, forward demodulation, passive clause reanimation] *********** $s8($s12)=$s12 big_f($s10(X1,X4),$s8(X0)) \/ $s10(X1,X4)=X4 \/ $s8(X0)!=X0 $s8($s12)=$s12 ----------------------------- big_f($s10(X1,X2),$s12) \/ $s10(X1,X2)=X2 *********** [86->92, cnf transformation] *********** (~big_f(X2,X3) \/ (X3=$s12 & X2=$s11)) & (X3!=$s12 \/ X2!=$s11 \/ big_f(X2,X3)) ----------------------------- X2=$s11 \/ ~big_f(X2,X3) *********** [202,92->213, resolution, passive clause reanimation] *********** big_f($s10(X1,X2),$s12) \/ $s10(X1,X2)=X2 X2=$s11 \/ ~big_f(X2,X3) ----------------------------- $s10(X1,X2)=$s11 \/ $s10(X1,X2)=X2 *********** [213->296, equality factoring, passive clause reanimation] *********** $s10(X1,X2)=$s11 \/ $s10(X1,X2)=X2 ----------------------------- $s11!=X1 \/ $s10(X2,X1)=X1 *********** [296->320, equality resolution, passive clause reanimation] *********** $s11!=X1 \/ $s10(X2,X1)=X1 ----------------------------- $s10(X1,$s11)=$s11 *********** [83->90, cnf transformation] *********** ($s8(X0)=X0 \/ ((X3!=$s9(X1) \/ big_f(X3,$s8(X0))) & (~big_f(X3,$s8(X0)) \/ X3=$s9(X1)))) & ($s8(X0)!=X0 \/ (($s10(X1,X4)=X4 \/ big_f($s10(X1,X4),$s8(X0))) & ($s10(X1,X4)!=X4 \/ ~big_f($s10(X1,X4),$s8(X0))))) ----------------------------- ~big_f($s10(X1,X4),$s8(X0)) \/ $s10(X1,X4)!=X4 \/ $s8(X0)!=X0 *********** [146,90,146->192, backward superposition, forward demodulation, passive clause reanimation] *********** $s8($s12)=$s12 ~big_f($s10(X1,X4),$s8(X0)) \/ $s10(X1,X4)!=X4 \/ $s8(X0)!=X0 $s8($s12)=$s12 ----------------------------- $s10(X1,X2)!=X2 \/ ~big_f($s10(X1,X2),$s12) *********** [122,320,192,320->328, backward superposition, forward demodulation, forward subsumption resolution] *********** big_f($s11,$s12) $s10(X1,$s11)=$s11 $s10(X1,X2)!=X2 \/ ~big_f($s10(X1,X2),$s12) $s10(X1,$s11)=$s11 ----------------------------- # ======= End of refutation =======
=========== Refutation ========== *********** [3, input] *********** X0!=a \/ X1!=b \/ big_f(X0,X1) *********** [3->11, normalize] *********** X0!=a \/ X1!=b \/ big_f(X0,X1) ----------------------------- X1!=b \/ X0!=a \/ big_f(X0,X1) *********** [11->28, equality resolution] *********** X1!=b \/ X0!=a \/ big_f(X0,X1) ----------------------------- X1!=a \/ big_f(X1,b) *********** [28->35, equality resolution] *********** X1!=a \/ big_f(X1,b) ----------------------------- big_f(a,b) *********** [1, input] *********** ~big_f(X0,X1) \/ X0=a *********** [4, input] *********** ~big_f(X1,f(X0)) \/ X1!=g(X0) \/ f(X0)=X0 *********** [4->12, normalize] *********** ~big_f(X1,f(X0)) \/ X1!=g(X0) \/ f(X0)=X0 ----------------------------- X1!=g(X0) \/ ~big_f(X1,f(X0)) \/ X0=f(X0) *********** [12->21, literal permutation] *********** X1!=g(X0) \/ ~big_f(X1,f(X0)) \/ X0=f(X0) ----------------------------- X1!=g(X2) \/ ~big_f(X1,f(X2)) \/ f(X2)=X2 *********** [6, input] *********** X1!=g(X0) \/ big_f(X1,f(X0)) \/ f(X0)=X0 *********** [6->14, normalize] *********** X1!=g(X0) \/ big_f(X1,f(X0)) \/ f(X0)=X0 ----------------------------- X1!=g(X0) \/ X0=f(X0) \/ big_f(X1,f(X0)) *********** [21,14->22, forward subsumption resolution] *********** X1!=g(X2) \/ ~big_f(X1,f(X2)) \/ f(X2)=X2 X1!=g(X0) \/ X0=f(X0) \/ big_f(X1,f(X0)) ----------------------------- X1!=g(X2) \/ f(X2)=X2 *********** [22->29, equality resolution] *********** X1!=g(X2) \/ f(X2)=X2 ----------------------------- f(X1)=X1 *********** [9, input] *********** f(X0)!=X0 \/ big_f(h(X0,X2),f(X0)) \/ h(X0,X2)=X2 *********** [9->17, normalize] *********** f(X0)!=X0 \/ big_f(h(X0,X2),f(X0)) \/ h(X0,X2)=X2 ----------------------------- X0!=f(X0) \/ X2=h(X0,X2) \/ big_f(h(X0,X2),f(X0)) *********** [17->25, literal permutation] *********** X0!=f(X0) \/ X2=h(X0,X2) \/ big_f(h(X0,X2),f(X0)) ----------------------------- f(X1)!=X1 \/ big_f(h(X1,X2),f(X1)) \/ h(X1,X2)=X2 *********** [29,25->31, backward demodulation] *********** f(X1)=X1 f(X1)!=X1 \/ big_f(h(X1,X2),f(X1)) \/ h(X1,X2)=X2 ----------------------------- big_f(h(X1,X2),X1) \/ h(X1,X2)=X2 *********** [1,31->33, resolution] *********** ~big_f(X0,X1) \/ X0=a big_f(h(X1,X2),X1) \/ h(X1,X2)=X2 ----------------------------- h(X1,X2)=a \/ h(X1,X2)=X2 *********** [33->36, equality factoring] *********** h(X1,X2)=a \/ h(X1,X2)=X2 ----------------------------- a!=X1 \/ h(X2,X1)=X1 *********** [36->40, equality resolution] *********** a!=X1 \/ h(X2,X1)=X1 ----------------------------- h(X1,a)=a *********** [10, input] *********** f(X0)!=X0 \/ h(X0,X2)!=X2 \/ ~big_f(h(X0,X2),f(X0)) *********** [10->18, normalize] *********** f(X0)!=X0 \/ h(X0,X2)!=X2 \/ ~big_f(h(X0,X2),f(X0)) ----------------------------- X0!=f(X0) \/ X2!=h(X0,X2) \/ ~big_f(h(X0,X2),f(X0)) *********** [18->24, literal permutation] *********** X0!=f(X0) \/ X2!=h(X0,X2) \/ ~big_f(h(X0,X2),f(X0)) ----------------------------- h(X1,X2)!=X2 \/ ~big_f(h(X1,X2),f(X1)) \/ f(X1)!=X1 *********** [29,24->32, backward demodulation] *********** f(X1)=X1 h(X1,X2)!=X2 \/ ~big_f(h(X1,X2),f(X1)) \/ f(X1)!=X1 ----------------------------- h(X1,X2)!=X2 \/ ~big_f(h(X1,X2),X1) *********** [40,32,40->41, backward superposition, forward demodulation] *********** h(X1,a)=a h(X1,X2)!=X2 \/ ~big_f(h(X1,X2),X1) h(X1,a)=a ----------------------------- ~big_f(a,X1) *********** [35,41->42, resolution] *********** big_f(a,b) ~big_f(a,X1) ----------------------------- # ======= End of refutation =======