TPTP Problem File: MSC006-1.p

View Solutions - Solve Problem

%--------------------------------------------------------------------------
% File     : MSC006-1 : TPTP v7.5.0. Released v1.0.0.
% Domain   : Miscellaneous
% Problem  : A "non-obvious" problem
% Version  : Especial.
% English  : Suppose there are two relations, P and Q. P is transitive, and
%            Q is both transitive and symmetric. Suppose further the
%            "squareness" of P and Q: any two things are related either in
%            the P manner or the Q manner. Prove that either P is total or
%            Q is total.

% Refs     : [PR86]  Pelletier & Rudnicki (1986), Non-Obviousness
% Source   : [PR86]
% Names    : nonob.lop [SETHEO]

% Status   : Unsatisfiable
% Rating   : 0.00 v2.0.0
% Syntax   : Number of clauses     :    6 (   1 non-Horn;   2 unit;   5 RR)
%            Number of atoms       :   12 (   0 equality)
%            Maximal clause size   :    3 (   2 average)
%            Number of predicates  :    2 (   0 propositional; 2-2 arity)
%            Number of functors    :    4 (   4 constant; 0-0 arity)
%            Number of variables   :   10 (   0 singleton)
%            Maximal term depth    :    1 (   1 average)
% SPC      : CNF_UNS_EPR_NEQ_NHN

% Comments : Rudnicki says "I think that what you call the non-obvious
%            problem from our write-up with Jeff should be attributed
%            to J. \Lo\'{s} (in LaTeX)." and "J. \Lo\'{s}  is in LaTeX,
%            and it is the name of my Polish prof that told me that.
%            English approximation of his name can be typed as J. Los.".
%--------------------------------------------------------------------------
cnf(p_transitivity,hypothesis,
    ( ~ p(X,Y)
    | ~ p(Y,Z)
    | p(X,Z) )).

cnf(q_transitivity,hypothesis,
    ( ~ q(X,Y)
    | ~ q(Y,Z)
    | q(X,Z) )).

cnf(q_symmetry,hypothesis,
    ( ~ q(X,Y)
    | q(Y,X) )).

cnf(all_related,hypothesis,
    ( p(X,Y)
    | q(X,Y) )).

cnf(p_is_not_total,hypothesis,
    ( ~ p(a,b) )).

cnf(prove_q_is_total,negated_conjecture,
    ( ~ q(c,d) )).

%--------------------------------------------------------------------------