poj 3295 Tautology【离散数学之重言式】

柔情只为你懂 2022-08-05 11:15 183阅读 0赞

Tautology

<table> 
 <tbody> 
 <tr> 
 <td>Time Limit: 1000MS</td> 
 <td>&nbsp;</td> 
 <td>Memory Limit: 65536K</td> 
 </tr> 
 <tr> 
 <td>Total Submissions: 10723</td> 
 <td>&nbsp;</td> 
 <td>Accepted: 4074</td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td> Definitions of K, A, N, C, and E </td> 
 </tr> 
 </tbody> 
</table>

题目大意：输入一个逻辑表达式【长度小于100】，逻辑表达式由K,A,N,C,E,p,q,r,s,t，其中

K表示合取，【Kwx即为w合取x，wx均为1时，值才为1】

A表示析取，【Awx即为w析取x，wx均为0时，值才为0】

N表示取反，【Nw即为 非w，若w=0，则Nw=1，若w=1，则Nw=0】

C表示条件，【Cwx即为非w析取x，结合A与N】

E相等，       【Ewx，w与x相等时，值为1，若不同，值为0】

【均为离散数学中的知识点】p,q,r,s,t均只有两个值，1或0；题目要求判断所输入的逻辑表达式是否为重言式【永真式】【即最后的结果全为1】

思路：

p，q，r，s，t共有32种，故定义变量 i，for i=0 to i <32;

遇到p，则 p = i & 1;

遇到q，则 q = (i >> 1) &1;

遇到r，则 r= (i >> 2) & 1;

遇到s，则s = (i >> 3) & 1;

遇到t，则 t = (i >> 4) & 1;

比如说判断函数为is\_Tautology(char ,int );

遇到K  则 is\_Tautology(char ,int ) & is\_Tautology();

A  N  C  E【类推 K 】

已Accept代码【c++提交】

#include <iostream>
 using namespace std;
 int n;
 char str[101];
 bool step ( char str[101], int k ){
 	n++;
 	switch ( str[n] )
 	{
 		case 'p': return k & 1;
 		case 'q': return ( k >> 1 ) & 1;
 		case 'r': return ( k >> 2 ) & 1;
 		case 's': return ( k >> 3 ) & 1;
 		case 't': return ( k >> 4 ) & 1;
 		case 'N': return !step ( str, k );
 		case 'K': return step ( str, k ) & step ( str, k ); 
 		case 'A': return step ( str, k ) | step ( str, k );
 		case 'C': return !step (str, k ) | step ( str, k );
 		case 'E': return step ( str, k ) == step ( str, k );
 	}
 }
 bool judge ( char str[101] ){
 	for ( int i = 0; i < 32; i++ ){
 		n = -1;
 		if ( !step ( str, i ) )
 			return false;
 	}
 	return true;
 }
 int main(){
 	while ( cin >> str && str[0] != '0' ){
 		if ( judge ( str ) )
 			cout << "tautology" << endl;
 		else
 			cout << "not" << endl;
 	}
 	return 0;
 }