一个逻辑推理类--从规则推测前提的真假

类别:VC语言 点击:0 评论:0 推荐:

                      Power Logic 

C.Second Edition

This is actually third edition of my logic class,in this edition, I made a big change.

1。 Basic idea:

I even change the whole

design of Logic class from "Bool" value to "Logic State"==1:Positive; 0:Possible; -1: Negative. Because in my

mind, as for an unknown logic object, its state is always unknown or "Possible". We can only use known logic

object of which the logic state is either "Positive" or "Negative" to deduct all unknown logic object. Of course

during deduction, if you find out you are attempting to change an known logic object from one state(Positive

or Negative) to its opposite state, we reach an contradiction. I basically define 4 logic operation, but the

4th one "Conditional" is actually able to be expressed by the other three---"AND", "OR", "NOT".

I stubbornly try to avoid to write a "parser" which is possibly beyond my ability, energy. So, I use a

similar method to record each step of logic calculation of a rule(or a logic expression involving several logic

objects connected by logic operators). It is a stack of a record---OpRec which is containing a status flag

indicating whether it is an operand, operator or a result, a pointer in case operand or result, or simply an

operator flag if it is an operator. In order to save space, I use an union to represent "operator" and "operand".

(It doesn't matter, nobody cares about it. I mean space.)

The most important part is that I implement a series of judgement function according to different operators.

For example, for "AND" operator, if either of the two operand is false, and the result is true, you definitely reach

a conclusion that they are contradictive. If the result is true, only one possible solution is that both operands

are true. This is called "deduction". So simple it is.

2。 Program design: In Logic class, there is one static object of Analyse class objects which fulfill analysing

function. In this Analyse object there is a stack to contain array of record---*OpRec--in this record, I record

each logic objects, operators, even including the temperatory logic objects. For example, ~R|W I have to record

"R" as first operand, "! " as operator, "~R" as result; "~R" as first operand for second step, "|" as operator,

"W" as operand, "~R|W" as result. So, you see I actually like using stack to do some similar job of parsing.

3。 Major function:

A. bool Analyse::readStack(int index)

Major function getting info from stack of Analyse class, judging the operator then call appropriate analsing function.

result means if there is new discovery or deductions, like find a new value for any step of logic objects.

B. void Analyse::analysing()

Keep finding the "result" type in OpRec(the stack) and call "readStack", doing the analysing. Have to clear stack for

next expression checking.

C. bool Analyse::analyAnd(Logic* op1, Logic* op2, Logic* result)

bool Analyse::analyNot(Logic* op1, Logic* result)

bool Analyse::analyOr(Logic* op1, Logic* op2, Logic* result)

bool Analyse::analyConditional(Logic* op1, Logic* op2, Logic* result)

These functions actually do the deduction job, given the state of result, there is certain chance you can get the state

of certain operand under certain operator. For example: "OR" operator will only give a "Negative" result when two operand

are both "Negative". That's the idea.

D. void Logic::pushStack(const Logic* self, const Logic* pDummy, LogicOp opCode)

This function will put the pointer of each operand, operator, result which is in array of "temp" into Analyse's

stack.

E. LogicState Logic::And(LogicState self, LogicState dummy)

This is logic "AND"! Have you found out? Say, true=1, false = -1 then result = true "AND" false = (-1*1)

There is only one exception: -1*(-1) = 1, so, I only have to judge when two operands are same. In this case, the result is

same as any of operand.(true&&true=true; false&&false = false) Even Possible is included by the rule as 1*0=0(Possible with

any other state is still possible.)

F. LogicState Logic::And(LogicState self, LogicState dummy)

This is logic "OR". The result is always the bigger one among two operands. Right? (say true||false= true, even Possible

which is 0 also falls within the rule.)

G. LogicState Logic::Not(LogicState self)

This is logic "NOT". Whenever the operand is, just times -1. (!true = false) 

H. void setFacts(); void setFactStr()

These two global function does initialization job to set the Logic objects with initial Logic state and name expression.

I. Logic& (* checkLists[10])() = {check1, check2, check3, check4, check5, check6, check7, check8, check9, check10};

This is a function array which initialize to 10 checking functions each of which is a logic expression with Logic objects

in the logic list of "element[ElementNum]" and connected by logic operators. The return value is actually the final result

Logic objects which is stored in the internal list "temp" along all other transpositional results. And this last result

itself is the so-called "RULE" which should be true. and I set up its state to be Positive before deduction in

void Analyse::analysing()

4。 Further improvement:

A. I always want to write those global function to make them part of class function. But it is not a easy

job.

B.

D. The problem:

    R: "It is raining."

    S: "It is snowing."

    I: "I get ill."

    W: "I get wet."

    D: "I need a doctor."

    H: "It is hot."

    F: "I have a fevor."

    Now I give you some facts which can be regarded as a collection of rules:

    1) ~R|W      (R->W)   If it is raining, then I get wet.

    2)  R|W      (~R->S)  If it is not raining, then it is snowing.

    3)  ~R|~S    (R->~S)   If it is raining, then it is not snowing.

    4)  ~S|~H     (S->~H)  If it is snowing, then it is not hot.

    5)  ~W|H|I    (  W->(H|I)   )  If it is wet, then it is either hot or I get ill.

    6)  ~I|~F|D   (I-> (~F|D) )  If I get ill, then I either don't have a fever or need a doctor.

    7)  F|~D      (  ~F->~D )  If I do not have a fever, then I don't need a doctor. 

    8)  ~S|~H     (  S->~H   ) If it is snowing, then it is not hot.

    9)  ~I|H|D    (  I->(H|D)  ) If I get ill then it is either hot or I need a doctor.

    10) H|~I|~W|F  ( (I&&W)->(H|F)) If I get both wet and ill then it is either hot 

                                or I have a fever.

    Suppose we have following facts:

    1)  R    2)~H

    Can we make conclusion that D?

    or in other words that suppose "it is raining" and "it is not hot", can we conclude that 

    "I need  a doctor"?

    The answer is YES! And the program outcome proves that.

E. The problem of last edition:

    The answer of last edition for same question is different from now! Because in last edition,

the condition of no. 9 is missing Logic "D". I found out this omission when testing.

#include <iostream>

using namespace std;

const int StackLimit = 30;

enum LogicOp {AND, OR, NOT, CONDITIONAL};

enum OpState {Operand, Operator, Result};

enum LogicState {Positive =1, Possible =0, Negative =-1};

bool operator == (LogicState self, LogicState dummy) { return ((self - dummy) == 0); }

//forward declaration class Analyse;

char* OpStr[4] = {" AND ", " OR ", " NOT "," CONDITIONAL "};

class Logic { private: static Analyse* analyse; static bool status; static int logicCount; char* express; int index; LogicState state; void catName(char*, const char*, LogicOp); static Logic* temp[100]; static int tempCount; static Logic* TRUE; static Logic* FALSE; bool definedStatus; LogicState And(LogicState self, LogicState dummy); LogicState Or(LogicState self, LogicState dummy); LogicState Not(LogicState self); void pushStack(const Logic* self, const Logic* pDummy, LogicOp opCode); Logic* getTemp() { return temp[tempCount -1];} protected: void initialize(); bool compare(const Logic& dummy); void uninitialize(); public: Analyse* getAnalyse(); Logic(const char* newExpress, const LogicState value=Possible); ~Logic(); Logic(); void prepare(); bool getStatus() const {return definedStatus;} void setStatus(const bool newStatus) {definedStatus = newStatus;} void setExpress(const char*); char* getExpress() const {return express;} void setIndex(const int newIndex) { index = newIndex;} int getIndex() const {return index;} void setState(LogicState newState) { state = newState;} LogicState getState() const{ return state;} static const int count() {return logicCount;} Logic& operator&&(Logic& dummy); Logic& operator||(Logic& dummy); Logic& operator!(); bool operator==(const Logic& dummy); Logic& operator&&(const bool value); Logic& operator||(const bool value); Logic& operator=(const Logic& dummy); Logic& operator>>(Logic& dummy); void doAnalysing(); };

union UNKNOWN { LogicOp operator = (LogicOp dummy); Logic* operator = (const Logic* dummy); Logic* logic; LogicOp op; };

struct OpRec { OpState opType; union UNKNOWN unknown; };

Logic* UNKNOWN::operator =(const Logic* dummy) { logic = (Logic*)dummy; return logic; }

LogicOp UNKNOWN::operator = (LogicOp dummy) { op = dummy; return op; }

 

class Analyse { private: bool analyAnd(Logic* op1, Logic* op2, Logic* result); bool analyOr(Logic* op1, Logic* op2, Logic* result); bool analyConditional(Logic* op1, Logic* op2, Logic* result); bool analyNot(Logic* op1, Logic* result); static OpRec* opStack[StackLimit]; int top; void clearStack(); LogicOp findOpCode(int index); bool setNewOp(Logic* dummy, LogicState newValue); int findPreResult(int index); OpRec* getTop(){ if (top>0) return opStack[top -1]; else return NULL;} public: Analyse(); ~Analyse(); void push(OpRec* newRec) {if (top<StackLimit) opStack[top++] = newRec;} OpRec* pop() {if (top>0) return opStack[--top];} bool readStack(int index); void analysing(); };

const ElementNum = 7;

enum ELEMENT {R,S,I,W,D,H,F};

char* factStr[7] = {"It is raining", "It is snowing", "I get ill","I get wet", "I need doctor", "It is hot", "I have a fevor"};

Logic element[ElementNum];

Logic& check1();

Logic& check2();

Logic& check3();

Logic& check4();

Logic& check5();

Logic& check6();

Logic& check7();

Logic& check8();

Logic& check9();

Logic& check10();

Logic& (* checkLists[10])() = {check1, check2, check3, check4, check5, check6, check7, check8, check9, check10};

char* logicStr[3] = {"True", "Unknown", "False"};

void displayResult();

void setFactStr();

void setFacts();

int main() { setFactStr(); setFacts(); for (int j=0; j<2; j++) {

for (int i=0; i<10; i++) { cout<<"\nNow check rule of no "<<i<<endl; (checkLists[i]()).doAnalysing(); } } displayResult();

return 0; }

void setFacts() { element[R].setState(Positive); element[H].setState(Negative); }

void setFactStr() { for (int i=0; i< ElementNum; i++) { element[i].setExpress(factStr[i]); } }

void displayResult() { for (int i=0; i< ElementNum; i++) { cout<<"\nThe logic expression '"<<factStr[i]<<" 'is "; switch (element[i].getState()) { case Positive: cout<<logicStr[0]; break; case Possible: cout<<logicStr[1]; break; case Negative: cout<<logicStr[2]; break; } cout<<"\n"; } }

Logic& check10() { return (!element[R])||(element[W]); }

Logic& check2() { return (element[R])||(element[S]); }

Logic& check3() { return (!element[R])||(!element[S]); }

Logic& check4() { return (!element[S])||(!element[H]); }

Logic& check5() { return (!element[W])||(element[H])||(element[I]); }

Logic& check6() { return (!element[I])||(!element[F])||(element[D]); }

Logic& check7() { return (element[F])||(!element[D]); }

Logic& check1() { return (!element[S])||(!element[H]); }

Logic& check9() { return (!element[I])||(element[H])||(element[D]); }

Logic& check8() { return (element[H])||(!element[I])||(!element[W])||(element[F]); }

Analyse* Logic::getAnalyse() { return analyse; }

void Logic::doAnalysing() { getAnalyse()->analysing(); }

int Analyse::findPreResult(int index) { while (index > 0) { index -- ; if (opStack[index]->opType== Result) return index; } return -1; }

void Analyse::analysing() { if (getTop()->opType!= Result) { cout<<"\nOpStack is not ended with Result:"<<endl; return ; } else { int i = top -1; opStack[i]->unknown.logic->setState(Positive); while (i!= -1) { readStack(i); i = findPreResult(i); } } clearStack(); }

LogicOp Analyse::findOpCode(int index) { int i = index; while (opStack[i]->opType != Operator) { i--; } return opStack[i]->unknown.op; }

bool Analyse::readStack(int index) { bool result= false; LogicOp opCode; if (opStack[index]->opType != Result ) { cout<<"Stack error!\n"; return false; } opCode = findOpCode(index); switch (opCode) { case AND: result = analyAnd(opStack[index-3]->unknown.logic, opStack[index - 1]->unknown.logic, opStack[index]->unknown.logic); break; case OR: result = analyOr(opStack[index-3]->unknown.logic, opStack[index - 1]->unknown.logic, opStack[index]->unknown.logic); break; case CONDITIONAL: result = analyConditional(opStack[index-3]->unknown.logic, opStack[index - 1]->unknown.logic, opStack[index]->unknown.logic); break; case NOT: result = analyNot(opStack[index -1]->unknown.logic, opStack[index]->unknown.logic); break; } return result; }

bool Analyse::setNewOp(Logic* dummy, LogicState newValue) { if (dummy->getState()!= newValue) { if (dummy->getState() != Possible) { cout<<"\nYou are changing expression '"<<dummy->getExpress()<<"' value!"; return false; } else { dummy->setState(newValue); return true; } } else return false; }

bool Analyse::analyAnd(Logic* op1, Logic* op2, Logic* result) { bool newOp = false; switch (result->getState()) { case Positive: if (op1->getState()==Negative||op2->getState()==Negative) { cout<<"\nThere is contradictive at:"<<result->getExpress(); return false; }

newOp = setNewOp(op1, Positive) || setNewOp(op2 ,Positive);

break; case Negative: if (op1->getState()==Positive&&op2->getState() == Positive) { cout<<"\nThere is contradictive at:"<<result->getExpress(); return false; } if (op1->getState()==Positive) { newOp = setNewOp(op2, Negative); } else { if (op2->getState() == Positive) { newOp = newOp || setNewOp(op1, Negative); } } break; case Possible: break; } return false; }

bool Analyse::analyOr(Logic* op1, Logic* op2, Logic* result) { bool newOp = false; switch(result->getState()) { case Positive: if (op1->getState()==Negative && op2->getState()==Negative) { cout<<"\nThere is contradictive at:"<<result->getExpress(); return false; } if (op1->getState() == Negative) { newOp = setNewOp(op2, Positive); } else { if (op2->getState() == Negative) { newOp = newOp || setNewOp(op1, Positive); } } break; case Negative: if (op1->getState()==Positive || op2->getState()== Positive) { cout<<"\nThere is contradictive at:"<<result->getExpress(); return false; } break; case Possible: break; } return newOp; }

bool Analyse::analyConditional(Logic* op1, Logic* op2, Logic* result) { bool newOp = false; switch (result->getState()) { case Positive: if (op1->getState()==Positive&& op2->getState()== Negative) { cout<<"\nThere is contradictive at:"<<result->getExpress(); return false; } if (op1->getState()==Positive) { newOp = setNewOp(op2, Positive); } else { if (op2->getState() == Positive) { newOp = setNewOp(op1, Positive); } } break; case Negative: if (op1->getState() == Negative) { cout<<"\nThere is contradictive at:"<<result->getExpress(); return false; }

newOp = setNewOp(op2, Negative); newOp = newOp || setNewOp(op1, Positive); break; case Possible: break; } return newOp; }

bool Analyse::analyNot(Logic* op1, Logic* result) { bool newOp = false;

switch (result->getState()) { case Positive: if (op1->getState() == Positive) { cout<<"\nThere is contradictive at:"<<result->getExpress(); return false; } else { newOp = setNewOp(op1, Negative); } break; case Negative: if (op1->getState() == Negative) { cout<<"\nThere is contradictive at:"<<result->getExpress(); return false; } else { newOp = setNewOp(op1, Positive); } break; case Possible: break; } return newOp; }

Analyse* Logic::analyse = new Analyse;

OpRec* Analyse::opStack[StackLimit];

void Analyse::clearStack() { for (int i =0; i< top; i++) { delete opStack[i]; } top = 0; }

Analyse::Analyse() { top = 0; }

Analyse::~Analyse() { clearStack(); }

LogicState Logic::And(LogicState self, LogicState dummy) { if (self!=dummy) { return (LogicState)(self*dummy); } else { return self; } }

LogicState Logic::Or(LogicState self, LogicState dummy) { return ((self>= dummy)?self: dummy); }

LogicState Logic::Not(LogicState self) { return (LogicState)(-1* self); }

void Logic::prepare() { for (int i=0; i< tempCount; i++) { free(temp[i]); } tempCount =0; }

Logic& Logic::operator >>(Logic& dummy) { char buffer[256]; catName(buffer, dummy.getExpress(), CONDITIONAL);

temp[tempCount] = new Logic(buffer);

temp[tempCount]->setState(Or(Not(state), dummy.getState()));

tempCount++; pushStack(this, &dummy, CONDITIONAL);

return *temp[tempCount-1]; }

void Logic::uninitialize() { status = true;

for (int i=0; i< tempCount;i++) { delete temp[i]; } }

bool Logic::status = false;

Logic* Logic::temp[100] = {NULL}; // = new Logic;

int Logic::tempCount = 0;

Logic* Logic::FALSE = new Logic("FALSE", Negative);

Logic& Logic::operator =(const Logic& dummy) { setExpress(dummy.getExpress()); setState(dummy.getState()); return *this; }

Logic* Logic::TRUE = new Logic("TRUE", Positive);;

Logic& Logic::operator &&(const bool value) { if (value) { return (*this)&&(*TRUE); } else { return (*this)&&(*FALSE); } }

Logic& Logic::operator ||(const bool value) { if (value) { return (*this)||(*TRUE); } else { return (*this)||(*FALSE); } }

bool Logic::operator ==(const Logic& dummy) { return compare(dummy); }

bool Logic::compare(const Logic& dummy) { return (index==dummy.getIndex()); }

void Logic::catName(char* buffer, const char* second, LogicOp opcode) { strcpy(buffer, getExpress()); strcat(buffer, OpStr[opcode]); strcat(buffer, second); }

Logic& Logic::operator !() { char buffer[256]; OpRec* ptr; strcpy(buffer, OpStr[NOT]); strcat(buffer, getExpress());

temp[tempCount] = new Logic(buffer); temp[tempCount]->setState(Not(getState()));

tempCount++;

ptr = new OpRec; ptr->opType = Operator; ptr->unknown = NOT;

analyse->push(ptr);

ptr = new OpRec; ptr->opType = Operand; ptr->unknown = this;

analyse->push(ptr);

ptr = new OpRec; ptr->opType = Result; ptr->unknown = temp[tempCount-1];

analyse->push(ptr);

return *temp[tempCount-1]; }

void Logic::pushStack(const Logic* self, const Logic* pDummy, LogicOp opCode) { OpRec* ptr;

ptr = new OpRec; ptr->opType = Operand; ptr->unknown = self; analyse->push(ptr);

ptr = new OpRec; ptr->opType = Operator; ptr->unknown = opCode; analyse->push(ptr);

ptr = new OpRec; ptr->opType = Operand; ptr->unknown = pDummy; analyse->push(ptr);

ptr = new OpRec; ptr->opType = Result; ptr->unknown = getTemp(); analyse->push(ptr); }

Logic& Logic::operator &&(Logic& dummy) { char buffer[256];

catName(buffer, dummy.getExpress(), AND);

temp[tempCount] = new Logic(buffer); temp[tempCount]->setState(And(getState(),dummy.getState()));

tempCount++; pushStack(this, &dummy, AND);

return *temp[tempCount-1]; }

Logic& Logic::operator ||(Logic& dummy) { char buffer[256]; catName(buffer, dummy.getExpress(), OR);

temp[tempCount] = new Logic(buffer); temp[tempCount]->setState(Or(getState(),dummy.getState()));

tempCount++; pushStack(this, &dummy, OR);

return *temp[tempCount-1]; }

int Logic::logicCount =0;

void Logic::initialize() { express = NULL; state = Possible; definedStatus = false; setIndex(logicCount); logicCount++; status = false; }

Logic::~Logic() {

if (!status) //if you destroy one, then you destroy all!!!!! { uninitialize(); }

if (express!=NULL) { free(express); } }

Logic::Logic(const char* newExpress, const LogicState value) { initialize(); setExpress(newExpress); setState(value); }

Logic::Logic() { initialize(); }

void Logic::setExpress(const char* newExpress) { int i; i = strlen(newExpress) +1;

if (express==NULL) { express = (char*)malloc(i); } else { express = (char*)realloc((void*)express, i); }

strcpy(express, newExpress);

}

                                                                       

http://www3.sympatico.ca/qingzhehuang/PowerLogic.htm

本文地址:http://com.8s8s.com/it/it2000.htm