• 离散数学命题公式的一个演示程序
• 离散学这一部分的时候就感觉手工求太麻烦了，所以就考虑写个程序直接枚举每一种情况，然后把真值表输出出来开始的时候，考虑把命题转成后缀表达式，然后进一步计算表达式的值。但是中间遇到了一些问题，不是很好...
为了输入和处理的时候方便，做了以下规定:
否定：!
合取：&
析取：|
蕴含：>
等价: -
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ElemPyte char
#define maxn 100
#pragma warning(disable : 4996)
using namespace std;

class Stack
{
public:
Stack();
int M;
ElemPyte* top;
ElemPyte* best;
void push(ElemPyte e)
{
if (top - best >= M)
{
best = (ElemPyte*)realloc(best, sizeof(ElemPyte) * (M + maxn));
if(!best)
{
exit(0);
}
M += maxn;
}
*top = e;
top++;
}
ElemPyte pop()
{
if (top == best) return 0;
return *(--top);
}
bool empty()
{
return best == top;
}
};
Stack::Stack()
{
M = maxn;
best = (ElemPyte*)malloc(sizeof(ElemPyte) * maxn);
if (!best)
{
exit(0);
}
top = best;
}
Stack s1;
char a[10000];
char rpn[10000];
int rpn_t;
map<char, int>book;
map<char, int>book2;
int t =0;
int e[26];
char slove(char s[], int n)
{
int i = 0;
while ( i < n)
{
if (s[i]=='!')
{
if (s[i + 1] == '!')
{
for (int j = i; j < n - 2; j++)
{
s[j] = s[j + 2];
}
n -= 2;
continue;
}
else
{
s[i + 1] ^= 1;
for (int j = i; j < n-1; j++)
{
s[j] = s[j + 1];
}
n--;
i++;
}
}
else
{
i++;
}
}
int sum;
do
{
sum = 0;
for (i = 0; i < n-1; i++)
{
if (s[i] == '&')
{
sum++;
s[i - 1] = ((s[i - 1] - '0') && (s[i + 1] - '0')) + '0';
for (int j = i; j < n - 2; j++)
{
s[j] = s[j + 2];
}
n -= 2;
}
}
} while (sum);
do
{
sum = 0;
for (i = 0; i < n - 1; i++)
{
if (s[i] == '|')
{
sum++;
s[i - 1] = ((s[i - 1] - '0') || (s[i + 1] - '0')) + '0';
for (int j = i; j < n - 2; j++)
{
s[j] = s[j + 2];
}
n -= 2;
}
}
} while (sum);
do
{
sum = 0;
for (i = 0; i < n - 1; i++)
{
if (s[i] == '>')
{
sum++;
if (s[i - 1] == '0')
{
s[i - 1] = '1';
}
else
{
if (s[i + 1] == '1')
{
s[i - 1] = '1';
}
else
{
s[i - 1] = '0';
}
}
for (int j = i; j < n - 2; j++)
{
s[j] = s[j + 2];
}
n -= 2;
}
}
} while (sum);
do
{
sum = 0;
for (i = 0; i < n - 1; i++)
{
if (s[i] == '-')
{
sum++;
if (s[i - 1] == s[i + 1])
{
s[i - 1] = '1';
}
else
{
s[i - 1] = '0';
}
for (int j = i; j < n - 2; j++)
{
s[j] = s[j + 2];
}
n -= 2;
}
}
} while (sum);
s[n] = '\0';
return s[0];
}
int main()
{
printf("请输入命题公式\n");
printf("否定:!\n合取:&\n析取:|\n蕴含:>\n等价:-\n");
scanf("%s", a);
int n = strlen(a);
for (int i = 0; i < n; i++) if (a[i] != '!' && a[i] != '&' && a[i] != '|' && a[i] != '>' && a[i] != '-' && a[i] != '(' && a[i] != ')' && !book2[a[i]]) book2[a[i]]=1,e[t++]=a[i]-'a';
sort(e, e + t);
for (int i = 0; i < t; i++) book[e[i] + 'a'] = t - i;
for (int pos = 0; pos < 1 << t; pos++)
{
char copy[1000];
for (int i = 0; i < n; i++)
{
copy[i] = a[i];
if (a[i] != '!' && a[i] != '&' && a[i] != '|' && a[i] != '>' && a[i] != '-' && a[i] != '(' && a[i] != ')')
{
copy[i] = '0' + (1 & pos >> book[a[i]]-1);
}
}
char str[1000];
int sum = 0,str_n=0;
do
{
sum = 0;
int i = n - 1;
int r = n;
while ( i >= 0 )
{
str_n = 0;
if (copy[i] == '(')
{
sum++;
int j;
for (j = i + 1; j < n; j++)
{
if (copy[j] != ')')
{
str[str_n++] = copy[j];
}
else
{
break;
}
}
str[str_n] = '\0';
copy[i] = slove(str, str_n);
int e = r;
r = i+1;
for (int k = j + 1; k < e; k++) copy[r++] = copy[k];
copy[r++] = '\0';
break;
}
i = min(r-1, i - 1);
}
} while (sum);
char ans = slove(copy, n);
printf("%c\n",ans);
}
return 0;
}

展开全文
• 离散数学命题公式求值及真值表题目要求算法思想代码总结 题目要求 给定任意一个命题公式的真值表，并根据真值表求主范式。 算法思想 将逻辑表达式转换为后缀表达式，然后套用逆波兰表达式的求值方法 利用位运算，找...


离散数学命题公式求值及真值表
题目要求算法思想代码总结

题目要求
给定任意一个命题公式的真值表，并根据真值表求主范式。
算法思想
将逻辑表达式转换为后缀表达式，然后套用逆波兰表达式的求值方法利用位运算，找出一个十进制整数对应二进制的每一位，给命题变项赋值记录下成真赋值以及成假赋值，最后输出
代码
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <cmath>
#include <iomanip>

using namespace std;
/**
* 用new_value替换src字符串中的old_value
* @param src
* @param old_value
* @param new_value
*/
void replace(string &src, const string &old_value, const string &new_value);
/**
* 获取一个整数二进制的某一位
* @param num
* @param bit 位数
* @return
*/
int valueAtBit(int num, int bit);

/**
* 计算给定真值及联结词的真值
* @param p 命题变项p的赋值
* @param q 命题变项q的赋值
* @param model 联结词
* @return 运算的真值
*/
int value(char p, char q, char op);

/**
* 根据给定的表达式求取命题变项的个数
* @param p_var 用于存放命题变项
* @param ex 表达式
*/
void get_p_var(vector<char> &p_var, const string &ex);

/**
* Infix expression is regarded as suffix expression
* @param midExpression the mid expression
* @return the suffix expression
*/
string midToSuf(const string &midExpression);

/**
* Calculate the suffix expression with stack and record the value
* @param suf suf expression
* @param p_var
* @param result real value set
* @param assigment
*/
void calculate(const string &suf, vector<char> &p_var, vector<char> &result, vector<char> &t_assigment, vector<char> &f_assigment);
/**
* 由后缀表达式计算
* @param str
* @return value
*/
int getValue(const string &str);

void setOut(vector<char> var, vector<char> result, vector<char> t_assigment, vector<char> f_assignment);
/**
* 整数转二进制串
* @param i
* @param size
* @return
*/
string intToStr(int i, int size);

int main() {
// 读入需要求的表达式
string ex;
string suf_ex; // Suffix expression corresponding to infix expression
// 记录命题变项
vector<char> p_var;
vector<char> result; // alphaStack propositional variables stack
vector<char> t_assignment; // True assignment
vector<char> f_assignment;
string t_str, f_str;
cout << "please input expression:(!：否定（括号外的否定需化入括号内）  &:合取  |：析取  >：蕴涵  =：等价)";
cin >> ex;
// Analytic expression, determine the number of propositional variables
get_p_var(p_var, ex);
// Infix expression is regarded as suffix expression
suf_ex = midToSuf(ex);
// Calculate the suffix expression and record the value
calculate(suf_ex, p_var, result, t_assignment, f_assignment);
setOut(p_var, result, t_assignment, f_assignment);
return 0;
}

void setOut(vector<char> var, vector<char> result, vector<char> t_assigment, vector<char> f_assignment) {
cout << "真值表如下：" << endl;
int size = var.size();
int k = pow(2, size);
for (int i = 0; i < size; ++i) {
cout << setiosflags(ios::left) << setfill(' ') << setw(2) << var[i];
}
cout << endl;
string value;
string t;
for (int j = 0; j < k; ++j) {
value = intToStr(j, size);
for (int i = 0; i < size; ++i) {
cout << setiosflags(ios::left) << setfill(' ') << setw(2) << value[i];
}
t = to_string(result[j]);
cout << "    " << t << endl;
}
cout << "主析取范式:" << endl;
int length = t_assigment.size();
for (int l = 0; l < length; ++l) {
t = to_string(t_assigment[l]);
t.insert(0, 1, 'm');
if (l + 1 != length) {
t.append(1, '|');
}
cout << t;
}
cout << endl;
cout << "主合取范式:" << endl;
t.clear();
length = f_assignment.size();
for (int l = 0; l < length; ++l) {
t = to_string(f_assignment[l]);
t.insert(0, 1, 'M');
if (l + 1 != length) {
t.append(1, '&');
}
cout << t;
}
}

int value(char p, char q, char op) {
int val = 0;
if (!isdigit(p) || !isdigit(q)) {
throw "输入不合法";
}
bool p_v = p != '0';
bool q_v = q != '0';
switch (op) {
case '=':
val = p_v == q_v;
break;
case '>':
val = p_v ? q_v ? 1 : 0 : 1;
break;
case '|':
val = q_v || p_v;
break;
case '&':
val = p_v && q_v;
break;
default:
break;
}
return val;
}

void get_p_var(vector<char> &p_var, const string &ex) {
bool exists = false;
int length = ex.length();
for (int i = 0; i < length; ++i) {
exists = false;
// if ex[i] is not a alpha, then continue.
if (!isalpha(ex[i])) {
continue;
}
for (char j : p_var) {
// 如果当前命题变项已经存放，则直接跳过当前字符
if (ex[i] == j) {
exists = true;
break;
}
}
if (!exists) {
p_var.push_back(ex[i]);
}
}
}

bool isOperator(char ch) {
return ch == '|' || ch == '&' || ch == '>' || ch == '=' || ch == '(' || ch == ')';
// 否则返回false
}

int getPriority(char ch) {
int level = 0; // 优先级
switch (ch) {
case '(':
level = 1;
break;
case '=':
level = 2;
break;
case '>':
level = 3;
break;
case '|':
level = 4;
break;
case '&':
level = 5;
break;
case ')':
level = 6;
break;
default:
break;
}
return level;
}

string midToSuf(const string &midExpression) {
string str;
int length = midExpression.length();
stack<char> op;
char top = ' ';
for (int i = 0; i < length; ++i) {
char ca = midExpression[i];
if (isalpha(ca) || isdigit(ca) || ca == '!') { // 如果是数字
if (ca == '!') {
str.append(1, ca);
str.append(1, midExpression[++i]);
continue;
} else {
str.append(1, ca);
}
} else if (isOperator(ca)) {// 操作符
if (!op.empty()) {
top = op.top();
}
if (op.empty() || ca == '(' || getPriority(top) < getPriority(ca)) {
op.push(ca);
if (ca == ')') {
while (true) {
top = op.top();
op.pop();
if (top == '(') {
break;
} else {
if (top == ')') {
continue;
}
str.append(1, top);
}
}
}
} else {
top = op.top();
op.pop();
op.push(ca);
str.append(1, top);
}

} else {
throw "expression is error";
}
}
// 第二个while结束
while (!op.empty()) {
top = op.top();
op.pop();
str.append(1, top);
}
return str;
}

void calculate(const string &suf, vector<char> &p_var, vector<char> &result, vector<char> &t_assigment, vector<char> &f_assigment) {
int size = p_var.size();
int k = pow(2, size);
string oldStr;
string newStr;
string temp;
string t_value;
for (int i = 0; i < k; ++i) {
temp = suf;
// 赋值
t_value = intToStr(i, size);
for (int j = 0; j < size; ++j) {
newStr.append(1, t_value[size - 1 - j]);
oldStr.append(1, p_var[size - 1 - j]);
replace(temp, oldStr, newStr);
newStr.clear();
oldStr.clear();
}
int length = temp.length();
for (int l = 0; l < length; ++l) {
if (temp[l] == '!') {
char t = temp[++l];
int v = t - '0';
v = !v;
temp.replace( l , 1, to_string(v));
}
}
replace(temp,"!","");
int v = getValue(temp);
if (v != 0) {
t_assigment.push_back(i);
} else {
f_assigment.push_back(i);
}
result.push_back(v);
}
}

string intToStr(int i, int size) {
string str;
for (int j = 0; j < size; ++j) {
int r = valueAtBit(i, j + 1);
str.append(1, r + '0');
}
reverse(str.begin(), str.end());
return str;
}

int getValue(const string &str) {
stack<char> num;
int size = str.size();
for (int i = 0; i < size; ++i) {
char t = str[i];
if (isdigit(t)) {
num.push(t);
} else {
char c1 = num.top();
num.pop();
char c2 = num.top();
num.pop();
int v = value(c2, c1, t);
num.push(v + '0');
}
}
return num.top() - '0';
}

int valueAtBit(int num, int bit) {
return (num >> (bit - 1)) & 1;
}

void replace(string &src, const string &old_value, const string &new_value) {
// 每次重新定位起始位置，防止上轮替换后的字符串形成新的old_value
for (string::size_type pos(0); pos != string::npos; pos += new_value.length()) {
if ((pos = src.find(old_value, pos)) != string::npos) {
src.replace(pos, old_value.length(), new_value);
} else break;
}
}


总结
我这代码写的太low了 有时间再对这个代码进行优化
展开全文
• 给学离散数学的同学编程用 详细注释在里边
• 用VC6.0编写的一个演示命题公式判断和运算的程序，程序通过对话框和用户实现交互，可以求解命题公式的真值表、主合取范式、主析取范式等等。
• 命题公式


§2.2命题公式
$\color{blue}{\S 2.2 命题公式}$

2.2.1公式
$\color{blue}{2.2.1 公式}$

我们用大写的英文字母P，Q，R，⋯,等代表一个抽象的命题，或称为命题符号.
$我们用大写的英文字母P，Q，R，\cdots,等代表一个抽象的命题，或称为命题符号.$

定义2.2.1.命题符号称为原子。
$定义2.2.1. 命题符号称为原子。$

例如，Q，S，⋯等都是原子。
$例如，Q，S，\cdots等都是原子。$

定义2.2.2.命题逻辑中的公式，是如下定义的一个符号串:(1)原子是公式；(2)0,1是公式；(3)若G，H是公式，则(¬G),(G∨H),(G∧H),(G→H),(G↔H)是公式；
$定义2.2.2.命题逻辑中的公式，是如下定义的一个符号串:\\ (1) 原子是公式；\\ (2) 0,1是公式；\\ (3) 若G，H是公式，则(\lnot G), (G \lor H), (G \land H), (G \to H), (G \leftrightarrow H)是公式；$

所有公式都是有限次使用(1),(2),(3)得到的符号串。
$所有公式都是有限次使用(1),(2),(3)得到的符号串。$

为了省括号，有如下规定：1.公式(¬G)的括号可以省略，写成¬G。2.整个公式最外层的括号可以省略。3.五种逻辑联结词的优先级按如下次序递增:↔,→,∧,∨,¬
$为了省括号，有如下规定：\\ 1.公式(\lnot G)的括号可以省略，写成 \lnot G。\\ 2.整个公式最外层的括号可以省略。\\ 3.五种逻辑联结词的优先级按如下次序递增:\\ \leftrightarrow, \to, \land, \lor, \lnot$

例如，我们写符号串:P∧Q∨R→Q∧¬S∨R就意味着是如下公式：((P∧(Q∨R))→(Q∧((¬S)∨R)))
$例如，我们写符号串: \\ P \land Q \lor R \to Q \land \lnot S \lor R \\ 就意味着是如下公式：\\ ((P \land (Q \lor R)) \to (Q \land ((\lnot S) \lor R)))$

2.2.2解释
$\color{blue}{2.2.2 解释}$
由定义知，公式是由命题符号，逻辑联结词，括号组成的符号串，而命题符号是抽象的，所以，如果不对命题符号给以解释(即指定命题符号为真或假)，则公式没有真值可言。反之，若对所有命题符号都给以解释，则公式就变成一个有真值的命题。

定义2.2.3.设G是命题公式，A 1 ,⋯,A n 是出现在G中的所有原子。指定A 1 ,⋯,A n 的一组真值，则这些真值称为G的一个解释。
$定义2.2.3.设G是命题公式，A_1, \cdots, A_n是出现在G中的所有原子。\\ 指定A_1, \cdots, A_n的一组真值，则这些真值称为G的一个解释。$

设G是公式，I是G的一个解释，G在I下有真值，通常记为T I (G)。
$设G是公式，I是G的一个解释，G在I下有真值，通常记为T_I(G)。$

例如，G=P∧Q,设解释I，I ′ 如下：
$例如，G = P \land Q, 设解释I，I^{\prime}如下：$

I:P1 Q1  I ′ :P1 Q0
$I:\left. \begin{array}{l c c }P & Q \\ \hline 1 & 1 \end{array} \right. \qquad I^{\prime}:\left. \begin{array}{l c c }P & Q \\ \hline 1 & 0 \end{array} \right.$

则T I (G)=1,T I ′  (G)=0
$则T_I(G) = 1, T_{I^{\prime}}(G) = 0$

定义2.2.4.公式G在其所有可能的解释下所取真值的表，称为G的真值表。
$定义2.2.4.公式G在其所有可能的解释下所取真值的表，称为G的真值表。$

有n个不同原子的公式，共有2 n 个解释。
$有n个不同原子的公式，共有2^n个解释。$

例如，G=(P∧Q)→R,其真值表如下：
$例如，G = (P \land Q) \to R, 其真值表如下：$

G=(P∧Q)→R
$\qquad \qquad G = (P \land Q) \to R$
PQRG00010011010101111001101111001111

若公式G中出现的所有原子为A 1 ,⋯,A n ,有时我们用{m 1 ,⋯,m n }表示G的一个解释I，其中
$若公式G中出现的所有原子为A_1, \cdots, A_n,\\ 有时我们用\lbrace m_1, \cdots, m_n \rbrace表示G的一个解释I，其中$

m i ={A i 当A i 在I下为1时，¬A i 当A i 在I下为0时， i=1,⋯,n
$m_i = \left \lbrace \begin{array}{l} A_i \quad 当A_i在I下为1时，\\ \lnot A_i \quad 当A_i在I下为0时，\end{array} \right. i=1, \cdots, n$

例如，上例公式G的真值表中第二个解释就可以记为{¬P,¬Q,R}。
$例如，上例公式G的真值表中第二个解释就可以记为\lbrace \lnot P, \lnot Q, R \rbrace。$

定义2.2.5.公式G称为恒真的(或有效的)，如果G在它的所有解释下都是真的；公式G称为恒假的(或不可满足的)，如果G在它的所有解释下都是假的；公式G称为可满足的，如果它不是恒假的。
$定义2.2.5.公式G称为恒真的(或有效的)，如果G在它的所有解释下都是真的；\\ 公式G称为恒假的(或不可满足的)，如果G在它的所有解释下都是假的；\\ 公式G称为可满足的，如果它不是恒假的。$

例如，P∨¬P是恒真公式，而P∧¬P是恒假公式，G=(P∧Q)→R则是可满足的公式。
$例如，P \lor \lnot P是恒真公式，而P \land \lnot P是恒假公式，\\ G=(P \land Q) \to R则是可满足的公式。$

G是恒真的当且仅当¬G是恒假的。
$G是恒真的当且仅当\lnot G是恒假的。$

G是可满足的当且仅当至少有一个解释I，使G在I下为真。
$G是可满足的当且仅当至少有一个解释I，使G在I下为真。$

若G是恒真的，则G是可满足的；反之不对。
$若G是恒真的，则G是可满足的；反之不对。$

如果公式G在解释I下是真的，则称I满足G；
$如果公式G在解释I下是真的，则称I满足G；$

如果G在解释I下是假的，则称I弄假G。
$如果G在解释I下是假的，则称I弄假G。$

判定问题：能否给出一个可行方法，对任意公式，判定其是否恒真公式。
$\color{blue}{判定问题}：能否给出一个可行方法，对任意公式，判定其是否恒真公式。$

因为一个命题公式的解释数目是有穷的，所以命题逻辑的判定问题是可解的(可判定的，可计算的)，亦即，命题公式的恒真，恒假性是可判定的。
$因为一个命题公式的解释数目是有穷的，所以命题逻辑的判定问题是可解\\ 的(可判定的，可计算的)，亦即，命题公式的恒真，恒假性是可判定的。$
展开全文
• 本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动，欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外，在本系列学习文章中，为了透彻理解数学知识，...

本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动，欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外，在本系列学习文章中，为了透彻理解数学知识，本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录，在后续学习中还会逐渐补充：
（国外经典教材）离散数学及其应用 第七版 Discrete Mathematics and Its Applications 7th ，作者是 Kenneth H.Rosen ，袁崇义译，机械工业出版社离散数学 第二版，武波等编著，西安电子科技大学出版社，2006年离散数学 第三版，方世昌等编著，西安电子科技大学出版社，2013年（经典参考书及其题解）离散数学/离散数学——理论•分析•题解，左孝凌、李为鉴、刘永才编著，上海科学技术文献出版社离散数学习题集：数理逻辑与集合论分册，耿素云；图论分册，耿素云；抽象代数分册， 张立昂。北京大学出版社

文章目录
2. 命题公式2.1 命题公式及其符号化（难点）2.2 命题公式的赋值 assign

2. 命题公式
2.1 命题公式及其符号化（难点）
命题常元 Propositional constant ，表示一个确定命题（真值不是

T

T

就是

F

F

）的标识符，一般为

T

T

或

F

F

。命题变元 Propositional variable ，表示一个不确定或可泛指任意命题的、以“真，假”为其变域的标识符，即真值未确定（但真值唯一）的命题的标识符，表示为

A

,

B

,

C

A,\ B,\ C

。在此基础上，原子公式指的是单个命题变元或命题常元。
命题公式的递归定义如下：
（1）基础：单个原子公式是命题公式。（2）归纳：如果

A

A

和

B

B

是命题公式，则

(

¬

A

)

,

(

A

∧

B

)

,

(

A

∨

B

)

,

(

A

→

B

)

,

(

A

⇔

B

)

(¬ A),\ (A∧B),\ (A∨B),\ (A→B),\ (A \Leftrightarrow B)

是命题公式。（3）极小性：只有有限步应用条款（1）和（2）生成的长度有限的符号串才是命题公式。
这种定义叫归纳定义或递归定义。由这种定义产生的公式叫命题公式或合式公式 Well formed formula 。若

B

B

是命题公式

A

A

的一个连续段，并且

B

B

也是命题公式，则称

B

B

是

A

A

的一个子公式。
例1：(a) 说明

(

P

→

(

P

∨

Q

)

)

(P→(P∨Q))

是命题公式。 解：
(i) P是命题公式，根据条款（1）(ii) Q是命题公式，根据条款（2）(iii)

(

P

∨

Q

)

(P∨Q)

是命题公式，根据(i)(ii)和条款（2）(iv)

(

P

→

(

P

∨

Q

)

)

(P→(P∨Q))

是命题公式，根据(i)(iii)和条款（2）
(b)

∧

Q

∧Q

、

(

P

→

Q

(P→ Q

、

P

→

∧

Q

P→∧Q

、

(

(

P

Q

)

∧

R

)

((PQ)∧R)

都不是命题公式, 因为它们不能由形成规则得出。
注意，并非由命题常元/变元、联结词和一些括号组成的字符串都能成为命题公式！
例2. 符号化下列命题： ① 若天不下雨也不下雪，则我去学校。 解：

P

P

：天下雨；

Q

Q

：天下雪；

R

R

：我去学校。于是命题公式是，

(

¬

P

∧

¬

Q

)

→

R

(\lnot P \wedge \lnot Q) \to R

。

翻译时约定：运算符结合力的强弱顺序为 ：

¬

¬

、

∧

∧

、

∨

∨

、

→

→

、

⇔

\Leftrightarrow

，凡符合此顺序的，括号均可省去。相同的运算符，按从左至右次序计算时，括号可省去。最外层的圆括号可以省去。

② 林芬和林芳是姐妹。 解：

P

P

：林芬和林芳是姐妹。这是一个原子命题。
③ 除非你掌握情况，否则你不能作出科学判断。 解：

P

P

：你掌握情况；

Q

Q

：作出科学判断。于是命题公式为，

¬

P

→

¬

Q

\lnot P \to \lnot Q

或其逆否命题

Q

→

P

Q \to P

。
④ 说离散数学枯燥无味或毫无价值，那是不对的。 解：

P

P

：离散数学是枯燥无味的；

Q

Q

：离散数学是毫无价值的。于是命题公式为，

¬

(

P

∨

Q

)

¬(P\vee Q)

。
2.2 命题公式的赋值 assign
命题公式的真值往往取决于所含命题变元的真值。设

p

1

,

p

2

,

…

,

p

n

p_1, p_2, \dots, p_n

是命题公式

A

A

中出现的所有命题变元，如果给

p

1

,

p

2

,

…

,

p

n

p_1, p_2, \dots, p_n

指定一组真值，则称为对命题公式

A

A

赋值/指派/解释。
显而易见，对于含有

n

n

个命题变元的命题公式

A

(

P

1

,

P

2

,

…

,

P

n

)

A(P_1, P_2, \dots, P_n)

，由于每个命题变元可以有

T

,

F

T, F

两个不同赋值，因此共有

2

n

2^n

种不同的赋值。
为观察命题公式在不同赋值下的真值情况，将命题公式

A

(

P

1

,

P

2

,

…

,

P

n

)

A(P_1, P_2, \dots, P_n)

的所有可能赋值和对应真值形成的各种情况列举出来，就是命题公式的真值表。不过真值表有以下约定：
将公式中出现的

n

n

个命题变元，按照字典升序或降序排列；对于

2

n

2^n

个不同赋值，按照对应的

n

n

位二进制数从小到大或从大到小的顺序排列；若公式较复杂，可从里到外先列出各个子公式的真值，最后列出所求公式的真值。

从真值表的各种情况发现，可以将命题公式分为三类：重言式、矛盾式、偶然式：
给定一个命题公式，如果在任何赋值下，它的真值都为

T

T

，则称该命题公式为重言式 tautology 或永真式；如

¬

P

∨

P

\lnot P\vee P

给定一个命题公式，如果在任何赋值下，它的真值都为

F

F

，则称该命题公式为矛盾式 contradiction 或永假式；如

¬

P

∧

P

\lnot P\wedge P

给定一个命题公式，如果它既不是永真式，也不是永假式，则称该命题公式为偶然式 contingency ；如

P

∨

Q

P\vee Q

对一个命题公式

A

A

，如果至少存在一种赋值，使得

A

A

的真值为

T

T

，则称

A

A

为可满足的 satisfiable 。对一个命题公式

A

A

，如果至少存在一种赋值，使得

A

A

的真值为

F

F

，则称

A

A

为非永真。
从而有以下推论：
重言式和偶然式都是可满足式；如果一个命题不是可满足式，则它是矛盾式。如果命题公式

A

A

为重言式，则

¬

A

\lnot A

为矛盾式。反之亦然。如果命题公式

A

,

B

A, B

均为重言式，则

(

A

∧

B

)

(A\wedge B)

、

(

A

∨

B

)

(A\vee B)

、

(

A

→

B

)

(A\to B)

、

(

A

↔

B

)

(A \leftrightarrow B)

都是重言式。
关于可满足式，还有一个有趣的问题：SAT，即判断一个命题公式是否为一个可满足式。关于SAT问题的介绍和2-SAT问题的解法，见[这篇文章]。
展开全文
• 文章目录命题公式命题常量和命题变元命题合式公式的递归式定义（well-Formed formula）联结词的优先级命题公式的种类重言式 / 永真式 （常见举例）矛盾式 / 不可满足式 / 永假式 （常见举例）可满足式真值表判断合式...
• 离散数学第一章导学离散数学都包括哪些方面内容命题及命题公式命题与命题连接词重点命题的基本概念命题符号化命题的联结词命题公式的等值演算重点联结词完备集重点 导学 离散数学都包括哪些方面内容 一，数理逻辑 １...
• c++程序判断离散数学命题公式，MFC开发
• 命题公式的等价关系和蕴涵关系
• c++程序判断离散数学命题公式
• ## 离散数学证明公式整理

千次阅读 多人点赞 2020-06-27 11:09:54
先把公式 按照自己的方式 背下来 然后多练几题 什么是 前束范式》？？？
• 1.命题： 定义：能够判断真假的陈述句叫做命题（不以句号结尾的句子，以及悖论，2*x>...3.命题公式的层次计算： 先从最简单的开始比如p∧q，∧两边都是单个命题变项，层次为0，所以总层次=0+1=1。 再比如...
• 输入命题公式的合式公式，求出公式的真值表，并输出该公式的主合取范式和主析取范式。 Input 命题公式的合式公式 Output 公式的主析取范式和主合取范式，输出形式为：“ mi ∨ mj ; Mi ∧ Mj” ，极小项和 ∨ 符号...
• //此代码只支持三个变相的命题公式 #include<iostream> #include<cctype> #include<set> #include<string> #include<stack> using namespace std; int Com(char a) { switch (a) { ...
• 等值关系式 重言蕴含式 真值表
• 2离散数学-命题公式,真值表[借鉴].pdf
• 一、知识框架图  二、数理逻辑  1.命题符号化  命题：能判断真假的陈述句  命题包含两个要素：陈述句，能判断真假  命题题符号化的步骤：   1 )对于不太好理解的联结词或表达... 设A是一命题公式, P1,P2….
• 命题的概念、联结词、 命题公式、命题的符号化与翻译、构造真值表证明命题公式的等价、 不构造真值表证明蕴涵式与等价式及命题公式的化简、命题公式的主析取范式、主合取范式 的求法、推理证明的直接证法和间接证...
• 命题概念 命题：有唯一真值的陈述句（悖论除外） 真值：真/假（T/F、0/1） 真（假）命题：真值为真（假）的命题 原子命题：不能再分割的...命题公式 命题变元：取值 1（真）或 0（假）的变元 合式公式：将命题变元用联
• 命题公式 命题常量表示一个具体的命题，真值唯一确定，可以看作命题。 命题变量可以表示任何一个命题，真值不确定，不能看作命题。 包含命题变量的复合命题就是一个关于命题变量的函数，叫做命题公式或真值函数。 ...
• 所有符合定义的合式公式构成合式公式空间，它可被视为命题逻辑的符号化语言。语言的结构包括符号表、语法规则（即合适公式定义）和语义（也即真值）。 • 定义：符号化语言 Lp 的符号表包括 − 小写英文字母：p, q
• 用C语言实现离散数学中的任意合式公式的真值表
• 命题：用一个陈述句表示的一个或多个为真为假，但不能同时为真又为假的判断句（或判断结果唯一的陈述句，或客观上存在唯一真值的陈述句） 命题的真值：只能是命题为“真”或“假” 例：（Y、F表示是否是命题） 1....
• 这是离散数学中很简单的一个实验，只需要对输入的公式判断是否合法就可以了，首先给出一个比较复杂的代码。 #include"stdio.h" #include"string.h" void rule1(char a[],int i) { if((a[i]>='a')&&(a[i]...
• 离散数学】编程练习：求命题公式的主范式 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #define N 50 char input[N]; bool table[N]; int cvt[N]; ...
• 命题符号化及联结词 0x00 前置知识 命题：能判断真假的陈述句，是具有唯一真值的陈述句 ???? 命题符号化：使用小写的英文字母 p,q,r,...,qi,pi,ri,...{p},{q},{r},{...},{q_i},{p_i},{r_i},{...}p,q,r,...,qi​,pi​...

...