求解某个命题公式的真值表和主析取范式和主合取范式

一、求解公式

　　思路：

　　1、首先我们要处理这个公式怎么能被计算机怎样方便的计算，我们人类所熟悉的是中缀表达式，但是计算机需要的不是我们这种，计算起来十分麻烦，因此我们首先要把这个公式转换成后缀表达式（也就是逆波兰式)不会的同学可以去看看我那篇逆波兰表达式。

　　2、然后我们要考虑公式符号的处理，因为我们计算机是没有->(蕴含符号) 和 <->（等价符号) 和 （取非符号的）所以我们要自定义符号，这里我把蕴含符号变成了‘-’号，等价符号变成了‘+’号，取非符号变成了‘ ! '，这样一来计算再次被化简。

　　3、我们计算逆波兰表达式要用到栈结构，不了解得话可以去看看我的栈结构的文章啊。

　　4、最后是统计主析取范式和主合取范式和真值表

　　5、我们只需要遍历当前元素的个数，然后分别跑n个循环，就可以得到他们的真值表和主析取范式。。。。

二、代码实现

  1 #include 
  2 #include 
  3 #include 
  4 #include 
  5 #include <string>
  6 #include 
  7 #include 
  8 #include 
  9 #include <set>
 10 #include 
 11 #include 
 12 #include 
 13 #define PII pair
 14 #define rep(i,z,n) for(int i = z;i <= n; i++)
 15 #define per(i,n,z) for(int i = n;i >= z; i--)
 16 #define ll long long
 17 #define db double
 18 #define vi vector
 19 #define debug(x) cerr << "!!!" << x << endl;
 20 using namespace std;
 21 inline ll read()
 22 {
 23     ll s,r;
 24     r = 1;
 25     s = 0;
 26     char ch = getchar();
 27     while(ch < '0' || ch > '9'){
 28         if(ch == '-')
 29             r = -1;
 30         ch = getchar();
 31     }
 32     while(ch >= '0' && ch <= '9'){
 33         s = (s << 1) + (s << 3) + (ch ^ 48);
 34         ch = getchar();
 35     }
 36     return s * r;
 37 }
 38 inline void write(ll x)
 39 {
 40     if(x < 0) putchar('-'),x = -x;
 41     if(x > 9) write(x / 10);
 42     putchar(x % 10 + '0');
 43 }
 44 //后缀表达式
 45 string expression;
 46 int cop(char c)
 47 {
 48     if(c == '+')//对应等价
 49         return 1;
 50     else if(c == '-')//对应蕴含
 51         return 2;
 52     else if(c == '|')//对应吸取
 53         return 3;
 54     else if(c == '&')//对应合取
 55         return 4;
 56     else if(c == '!')//对应取非
 57         return 5;  
 58     return 0;
 59 }
 60 int prio(char c)
 61 {
 62     if(c == '(')//对应阔号
 63         return 0;
 64     else if(c == '+')//对应等价
 65         return 1;
 66     else if(c == '-')//对应蕴含
 67         return 2;
 68     else if(c == '|')//对应吸取
 69         return 3;
 70     else if(c == '&')//对应合取
 71         return 4;
 72     else if(c == '!')//对应取非
 73         return 5;
 74     return 0;
 75 }
 76 void aftExpression(string ms)
 77 {
 78     stack <char> ct;//定义一个ct容器存储运算符
 79     for(auto iter = ms.begin();iter != ms.end();iter++){
 80         if(*iter >= 'a' && *iter <= 'z')//如果是数字，直接入栈
 81             expression += *iter;
 82         else{
 83             if(ct.empty() || *iter == '(')//如果是空栈，或者是左括号，直接入栈
 84                 ct.push(*iter);
 85             else if(*iter == ')'){
 86                 while(ct.top() != '('){//把左括号和右括号里面的操作符出栈
 87                     expression += ct.top();
 88                     ct.pop();
 89                 }
 90                 ct.pop();//弹出左括号
 91             }
 92             else{
 93                 while(!ct.empty() && prio(*iter) <= prio(ct.top())){//把优先级低于当前操作符的操作符出栈
 94                     expression += ct.top();
 95                     ct.pop();
 96                 }
 97                 ct.push(*iter);//把当前操作符入栈
 98             }
 99         }
100     }
101     while(!ct.empty()){//如果栈区还有操作符
102         expression += ct.top();
103         ct.pop();
104     }
105     cout << "Aft expression is :";
106     cout << expression << endl;
107  }
108  int sw(char c,int p,int q,int r)
109  {
110      if(c == 'p')
111         return p;
112     else if(c == 'q')
113         return q;
114     else if(c == 'r')
115         return r;
116     return 0;
117  }
118  int compute(int p,int q,int r,string cpu)
119  {
120      stack <int> ans;
121      for(auto it = cpu.begin();it != cpu.end();it++){
122          if(*it >= 'a' && *it <= 'z')
123              ans.push(sw(*it,p,q,r));
124          else if(*it == '!'){
125              int num = ans.top();
126              ans.pop();
127              ans.push(!num);
128          }
129          else{
130              int num1 = ans.top();
131              ans.pop();
132              int num2 = ans.top();
133              ans.pop();
134              switch(cop(*it)){
135                  case 1: ans.push(num1 == num2);break;
136                  case 2: ans.push(num1 || !num2);break;
137                  case 3: ans.push(num1 || num2);break;
138                  case 4: ans.push(num1 && num2);break;
139              }
140          }
141      }
142      return ans.top();
143  }
144  string trans1(int p,int q,int r)
145  {
146      int cnt = p * 4 + q * 2 + r;
147      char c = cnt + '0';
148      string tmp = "m";
149      tmp += c;
150      return tmp;
151  }
152  string trans2(int p,int q,int r)
153  {
154      int cnt = p * 4 + q * 2 + r;
155      char c = cnt + '0';
156      string tmp = "M";
157      tmp += c;
158      return tmp;
159  }
160  void solve()
161  {
162      string s1[10];
163      string s2[10];
164      int cnt1,cnt2;
165      cnt1 = cnt2 = 0;
166      cout << "Table:p|q|r|rt" << endl;
167     for(int p = 0;p <= 1;p++)
168         for(int q = 0;q <= 1;q++)
169             for(int r = 0;r <= 1;r++){
170                 cout << "      " << p << '|' << q << '|' << r << '|' << compute(p,q,r,expression) << endl; 
171                 if(compute(p,q,r,expression))
172                     s1[++cnt1] = trans1(p,q,r);
173                 else
174                     s2[++cnt2] = trans2(p,q,r);
175             }
176     //主析取范式
177     cout << "Principal Disjunctive Normal Form:\n";
178     if(cnt1 == 0){
179         cout << "NULL" << endl;
180     }
181     else{
182         for(int i = 1;i <= cnt1;i++)
183             cout << "      " << s1[i] << endl;
184     }
185 
186     //主合取范式
187     cout << "Principal Conjunctive Normal Form:\n";
188     if(cnt2 == 0){
189         cout << "NULL" << endl;
190     }
191     else{
192         for(int i = 1;i <= cnt2;i++)
193             cout << "      " << s2[i] << endl;        
194     }
195  }
196 int main()
197 {
198     //输入逻辑表达式
199     string s;
200     cin >> s;
201     aftExpression(s);
202     solve();
203     return 0;
204 }
离散数学

相关

关于离散数学到了期末这件事

标签