离散数学 Lab 1 命题逻辑
Explanation
老师并没有要求采用何种语言进行编写，这里还是优先采用了 C 语言。
在大部分程序设计语言中包含一定的逻辑/位运算符号，如：&(与) |(或) !(非) ^(异或) 等, 对应命题逻辑中的部分联结词，在书写程序的时候可以直接使用.
但为了表示出命题与命题变元之间的真值关系, 在本文中在多数题目中使用了函数去表示联结词，而非直接使用系统提供的运算符。
但这样好像有点多此一举，让代码变得十分冗长, 没有提高可读性甚至还起到了反效果。
但是写都写了, 也便懒得改了.
题目链接在这里~~ 离散数学 Lab1 – SDUTOJ
Basic-Computer-Science
在上学期的 Basic Computer Science 课程中也有 Proposition 部分，对应的实验链接如下：
Basic-Computer-Science：Lab 4 Proposition ( 计算机科学基础 )
用函数代替联结词
在本实验中用到了以下七种联结词：
| 联结词 | 符号 | 函数原型 |
|---|---|---|
| 否定 | $\neg$ | negation(int p) |
| 合取 | $\wedge$ | conjunction(int p,int q) |
| 析取 | $\vee$ | disjunction(int p,int q) |
| 条件 | $\rightarrow$ | implication(int p,int q) |
| 双条件 | $\leftrightarrow$ | biconditional(int p,int q) |
| 与非 | $\uparrow$ | NAND(int p,int q) |
| 或非 | $\downarrow$ | NOR(int p,int q) |
这些函数的实现主要是通过 if 结合定义进行判断，在函数体内并非完全杜绝逻辑运算符，而是通过展开的形式将其真值运算过程展现出来。
例如在 conjunciton 中使用了 if(p == 1 && q == 1)，这里对应了定义中：“当且仅当 p 为真 q 也为真时 p 合取 q （p$\wedge$q）为真”
为了方便起见在后续的问题中将不会重复展示函数具体内容。
int negation(int p)
{
if(p==1)
{
return 0;
}else{
return 1;
}
}
int conjunction(int p,int q)
{
if(p == 1 && q == 1)
{
return 1;
}else{
return 0;
}
}
int disjunction(int p,int q)
{
if(p == 0 && q == 0)
{
return 0;
}else{
return 1;
}
}
int implication(int p,int q)
{
if(p == 1 && q == 0)
{
return 0;
}else return 1;
}
int biconditional(int p,int q)
{
if(p == q)
{
return 1;
}else return 0;
}
int NAND(int p,int q)
{
if(p == 1 && q == 1)
{
return 0;
}else{
return 1;
}
}
int NOR(int p,int q)
{
if(p == 0 && q == 0)
{
return 1;
}else{
return 0;
}
}
Problem A
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int negation(int p);
int conjunction(int p,int q);
int disjunction(int p,int q);
int implication(int p,int q);
int biconditional(int p,int q);
int NAND(int p,int q);
int NOR(int p,int q);
int main()
{
int p,q;
while(~scanf("%d %d",&p,&q)){
for(int i=1;i<=6;i++)
{
switch(i)
{
case 1: printf("%d ",conjunction(p,q)); break;
case 2: printf("%d ",disjunction(p,q));break;
case 3: printf("%d ",implication(p,q));break;
case 4: printf("%d ",biconditional(p,q));break;
case 5: printf("%d ",NAND(p,q));break;
case 6: printf("%d\n",NOR(p,q));break;
}
}
}
return 0;
}
Problem B
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int conjunction(int p,int q);
int disjunction(int p,int q);
int main()
{
int t;
int n1[70];
int n2[70];
while(~scanf("%d",&t))
{
for(int i=0;i<t;i++)
{
scanf("%d",n1+i);
}
for(int i=0;i<t;i++)
{
scanf("%d",n2+i);
}
for(int i=0;i<t;i++)
{
printf("%d ",conjunction(n1[i],n2[i]));
}
printf("\n");
for(int i=0;i<t;i++)
{
printf("%d ",disjunction(n1[i],n2[i]));
}
printf("\n");
}
return 0;
}
Problem C
题干给出了四个命题, 其中三个命题的真值与实际情况相反(即说谎了!), 因此我们需要假设 “某一个命题为真, 其他命题均说谎了”，同时需要枚举最佳赛车是哪一个来获取原命题的真值。
更直观的, 我们假设某辆汽车是最佳的, 然后检验下面的四个复合命题是否为真, 然后给出对应的答案:
$$\begin{align*}
P1 \wedge (\neg P2) \wedge (\neg P3) \wedge (\neg P4) \\
(\neg P1) \wedge P2 \wedge (\neg P3) \wedge (\neg P4) \\
(\neg P1) \wedge (\neg P2) \wedge P3 \wedge (\neg P4) \\
(\neg P1) \wedge (\neg P2) \wedge (\neg P3) \wedge P4 \\
\end{align*}$$
这里没有使用函数，而是直接使用了 == && || 等运算符进行了处理（其实也是懒得改写了）。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
int a,b,c;
while(~scanf("%d %d %d",&a,&b,&c))
{
for(int i=1;i<=4;i++)
{
if(a==i&&b!=i&&c==i&&b==i)
{
printf("%d A\n",i);
break;
}
if(a!=i&&b==i&&c==i&&b==i)
{
printf("%d B\n",i);
break;
}
if(a!=i&&b!=i&&c!=i&&b==i)
{
printf("%d C\n",i);
break;
}
if(a!=i&&b!=i&&c==i&&b!=i)
{
printf("%d D\n",i);
break;
}
}
}
return 0;
}
Problem D
首先是将题目中的自然语言转化为了复合命题，然后使用 P1-P6 六个函数表示六个命题（有些命题比较简单，只包含一个联结词）。
对于每个命题的表示如下：
$$
\begin{align*}
& P1: \neg(a \downarrow b) \\
& P2: ((a \vee e)\wedge f) \vee ((a \vee f)\wedge e) \\
& P3: a \uparrow d \\
& P4: b \leftrightarrow c \\
& P5: \neg(c \leftrightarrow d) \\
& P6: e \rightarrow d \\
\end{align*}
$$
为了直观的看出命题变元，在代码中做了一些处理：
1. 使用了 enum 来替换 a b c d e f, 提高可读性。(总算感觉到他有点用了)
2. 采用了二进制状态压缩来遍历所有状态，简化状态改变的过程。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
enum Flag{A,B,C,D,E,F};
int num[7];
int negation(int p);
int conjunction(int p,int q);
int disjunction(int p,int q);
int implication(int p,int q);
int biconditional(int p,int q);
int NAND(int p,int q);
int NOR(int p,int q);
int P1(int a,int b)
{
return negation(NOR(a,b));
}
int P2(int a,int e,int f)
{
int p1,p2;
int p3,p4;
p1=disjunction(a,e);
p2=conjunction(p1,f);
p3=disjunction(a,f);
p4=conjunction(p3,e);
return disjunction(p2,p4);
}
int P3(int a,int d)
{
return NAND(a,d);
}
int P4(int b,int c)
{
return biconditional(b,c);
}
int P5(int c,int d)
{
return negation(biconditional(c,d));
}
int P6(int d,int e)
{
return implication(e,d);
}
int check(int f[])
{
int p1,p2,p3;
p1=conjunction(P1(f[A],f[B]),P2(f[A],f[E],f[F]));
p2=conjunction(P3(f[A],f[D]),P4(f[B],f[C]));
p3=conjunction(P5(f[C],f[D]),P6(f[D],f[E]));
if(conjunction(conjunction(p1,p2),p3))
{
return 1;
}else{
return 0;
}
}
void out(int f[])
{
for(int i=0;i<6;i++)
{
if(f[i])
{
printf("The suspects numbered %d are criminals.\n",num[i]);
}else{
printf("The suspect numbered %d is not a criminal.\n",num[i]);
}
}
}
int main()
{
while(scanf("%d %d %d %d %d %d",num+A,num+B,num+C,num+D,num+E,num+F)!=EOF)
{
int MAX=(1<<6)-1;//二进制状态压缩
int f[7];
for(int i=0;i<=MAX;i++)
{
for(int j=0;j<6;j++)
{
f[j]=(i>>j)&1;//从压缩的状态还原到f数组
}
if(check(f))//根据f数组中的状态进行 check
{
out(f);
break;
}else continue;
}
}
return 0;
}
More Simple
对于 Problem C、D，这么做好像没什么必要，我们只需要简单推理一下. 这里以 C 题为例：
四名专家对四款赛车进行评论。
专家A说：a号赛车是最好的。
专家B说：b号赛车是最好的。
专家C说：c号不是最佳赛车。
专家D说：专家B说错了。
事实上只有一款赛车最佳，且只有一名专家说对了，其他三人都说错了。请编程输出最佳车的编号，以及哪位专家所对了。
如果 D 说谎，证明 B 说的是对的，则 A C 在说谎，因此有以下结论：
1. a号不是最好的
2. b号是最好的
3. c号是最好的
可以看到 2 3 产生了矛盾。
如果 D 没有说谎， 则证明 B 在说谎，同时 A C 也一定是在说谎，因此有以下结论：
1. a号不是最好的
2. b号不是最好的
3. c号是最好的
此时结论之间没有矛盾，因此答案为 D 没有说谎同时 c 号是最佳赛车，在程序中直接输出结果即可。
代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
int a,b,c;
while(~scanf("%d %d %d",&a,&b,&c))
{
printf("%d D\n",c);
}
return 0;
}