后使用快捷导航没有帐号？
查看: 1037|回复: 4
求助！！p→(r→q)为何不是合式公式
一般战友, 积分 384, 距离下一级还需 116 积分
在线时间85 小时
主题帖子积分
一般战友, 积分 384, 距离下一级还需 116 积分
一般战友, 积分 384, 距离下一级还需 116 积分
p→(r→q)为何不是合式公式
新手上路, 积分 19, 距离下一级还需 81 积分
在线时间2 小时
主题帖子积分
新手上路, 积分 19, 距离下一级还需 81 积分
新手上路, 积分 19, 距离下一级还需 81 积分
因为没有加括号....
一般战友, 积分 384, 距离下一级还需 116 积分
在线时间85 小时
主题帖子积分
一般战友, 积分 384, 距离下一级还需 116 积分
一般战友, 积分 384, 距离下一级还需 116 积分
那p^（q^┐r）就可以了？
一般战友, 积分 153, 距离下一级还需 347 积分
在线时间108 小时
主题帖子积分
一般战友, 积分 153, 距离下一级还需 347 积分
一般战友, 积分 153, 距离下一级还需 347 积分
后面又有地方把他当合式公式用了 不知道什么情况 耿素云的书。。。
新手上路, 积分 19, 距离下一级还需 81 积分
在线时间2 小时
主题帖子积分
新手上路, 积分 19, 距离下一级还需 81 积分
新手上路, 积分 19, 距离下一级还需 81 积分
bngdyz 发表于
那p^（q^┐r）就可以了？
没加外面的大括号，怎么看的书呀
您还剩5次免费下载资料的机会哦~
扫描二维码下载资料
使用手机端考研帮，进入扫一扫在“我”中打开扫一扫，扫描二维码下载资料
Powered by Discuz!深入理解计算机系统：信息的处理和表示（二）整数四则运算 - 苯苯吹雪 - 博客园
开篇说明一下，本文不是介绍四则运算的具体执行过程，想了解具体过程的孩子们自己去看看计算机组成。
好了，话不多说。
1.& 加减法
加法和减法没有区别，以下内容专注于加法。
1.1 &无符号数加法
无符号数加法会出现溢出问题，当发生溢出的时候直接扔掉溢出进位。比如1111 + 0001 = 10000 直接扔掉进位1，结果为0000。考虑到溢出之后，我们可以总结出这样的计算式：
那么我们怎么来判断溢出呢？
对于s= x+ 当s &x 或者 s & y的时候就是溢出了。原因在于溢出的时候s=x+y-2w。而x,y都是小于2w的所以s&x ，s&y。
于是，我们可以写出函数来提前判断两个无符号数想加是否会溢出：
/* Determine whether arguments can be added without overflow */
int uadd_ok(unsigned x, unsigned y){
temp= x+y;
return temp&=x;
下面给出一张图，全面展示四位无符号二进制树之间的想加情况：
好了，之前提到加法和减法没什么区别，那么我们怎么计算无符号数减法呢？要知道无符号数可是没有&相反数&这个东西的。
为了解决这个问题，我们引入一个 加法逆元(additive inverse) 的概念。假设x的加法逆元是y，当且仅当(x+y)%2w=0，其中x,y为w位的二进制数。
加法逆元的计算公式：
以后计算减法的时候，就将被减数转换为其加法逆元，这样再相加就好了。
1.2 &有符号数加法
有符号加法和无符号加法产生的二进制是一样的，它也会产生溢出，由于符号的原因它有两种溢出 正溢出和负溢出。正溢出是指两个两个正数想家结果为负数，比如0111 + 。负溢出就是两个负数相加为正数1001 + 。计算公式如下：
给出四位二进制有符号数相加的全部情况图：
那么怎么判断是否溢出呢？
原理就是 负负得正，正正得负 就是溢出啦。
/* Determine whether arguments can be added without overflow */
int tadd_ok(int x, int y) {
int sum = x+y;
int neg_over = x & 0 && y & 0 && sum &= 0;
int pos_over = x &= 0 && y &= 0 && sum & 0;
return !neg_over && !pos_
当然了，如果有人神经叨叨的给你看他的实现方法：
/* Determine whether arguments can be added without overflow */
/* WARNING: This code is buggy. */
int tadd_ok(int x, int y) {
int sum = x+y;
return (sum-x == y) && (sum-y == x);
这段代码毫无疑问是错误的，为什么呢？因为我们知道加法是符合交换律的，那么(x+y)-x = (x-x)+y，也就是说上述判断条件始终成立。不信你可以验证。
说完加法，我们来看看怎么将减法转换为加法。当然是取相反数了，关键是，怎么取相反数？这是一个很有学问的地方，技巧妙的一谈糊涂。
x相反数是y，当且仅当x+y=0。那么我们显然得到y=-x这个公式了，但是要是有人问你最小负数的相反数是多少，你怎么办？举个例子，对于8位二进制而言，最小负数-128，-(-128)=128&127(8位二进制最大正数)。
哈哈，怎么办，怎么办。
结论是最小负数的相反数就是它自己！！你可以算一算 +
= 符合定义！
于是就有我们的求负数的公式了：
哈哈，看完这个我们再来看看怎么验证两个数相减会不会溢出，先看看下述代码：
/* Determine whether arguments can be subtracted without overflow */
/* WARNING: This code is buggy. */
int tsub_ok(int x, int y) {
return tadd_ok(x, -y);
这个对不对呢？
应该是不对的，因为Tmin的相反数还是他自己，当x为正数，y为Tmin的时候，这个函数是会报错的，但是实际上是不会溢出的。
下面接着来说怎么实际操作来取相反数：一种方法是 各位取反后加一
第二种方法：我们仔细看看这个我们能看出一个规律，就是说我们沿着二进制从右往左走，知道遇到第一个1，然后将第一个1之后的每个位取反就好了。
关于具体怎么做乘法自己去查阅计算机组成原理课本。我们先来看具体的二进制乘法的例子：
我们发现一个现象，就是说有符号二进制乘法和无符号二进制乘法，他们获得的最终结果的二进制表示是一样的！！、
好吧，处于严谨考虑，我们来证明一下下：
那么我们怎么来判断乘法会不会发生溢出呢？我们注意到，上面那个图中的乘法都是溢出的。
先给出代码，大家可以看看这个代码对不对？
/* Determine whether arguments can be multiplied without overflow */
int tmult_ok(int x, int y) {
int p = x*y;
/* Either x is zero, or dividing p by x gives y */
return !x || p/x ==
好吧，我承认我顽皮了，因为大部分同学（包括曾经的我）根本看不懂这个是什么东东！脑子里就俩个字：尼玛！
我们从理论上证明一下下：
首先我们知道对于w位的x和y，x*y是可以用2w位二进制来表示的，我们将这2w位二进制拆为两部分，高w位（用v来表示）和低w位（用u来表示），于是我们得到x*y=v*2w + u. u代表了代码中p的二进制表示，根据无符号数转换为有符号数的公式我们得到：u = p + p w&1 2w，于是我们可以将x * y = p + t * 2w. 根据溢出的定义，该乘法发生溢出当且仅当 t != 0。
其次，当x!=0的时候我们可以将p表示为p = x * q + r， |r| & |x|。于是我们有x * y = x * q + r + t * 2w。我们需要推导出t == 0的等价条件。当t = 0的时候，我们有x * y = x * q + r，而|r| & |x|，所以必有q=y；反过来,q=y的时候我们也可以推出t=0。也即是说t=0这个条件等价于q=y这个条件（前提是x不为0）。
于是我们就得到了我们代码里面的判断条件： !x || p/x == y
那么如果我们不允许使用除法，但是允许你使用long long这个数据类型，你怎么来做乘法的溢出检查呢？
哈哈，其实这个就简单了。
/* Determine whether arguments can be multiplied without overflow */
int tmult_ok(int x, int y) {
/* Compute product without overflow */
long long pll = (long long) x*y;
/* See if casting to int preserves value */
return pll == (int)
哈哈，说完这些之后我们来看看怎么将乘法转换为 移位和加法操作， 因为这两种操作时非常快速的。
我们来看，怎么将通过移位的方法一个数扩大两倍？很显然是左移一位。扩大四倍呢？左移两位。
其实我们就类比十进制乘法& 列竖的计算式子就可以了。
这里面有个可以被优化的技巧，我们来看。加入被乘数是[(0 . . . 0)(1 . . . 1)(0 . . . 0) ].那么我们还要一个个的移位相加么？其中连续的1，起于从右到左的第m位，终于第n位。
我们可以这样，(x&&n+1) - (x&&m)。
好了，乘法也就这么多了，下面是除法。
除法这一块我们只涉及除以一个2k次方。对于正数以及无符号数而言，这意味着右移k位，高位补0。下图中斜体的0都是后来补的0。
而对于负数而言，我们需要采用逻辑右移，也就是说高位补1。例子见下图：
但是我们在图中发现一个问题，就是结果可能跟真实的值相差一，比如-12340/8应该为-48而不是-49，-7/2=-3而不是-4。怎么处理这个问题呢？
我们可以对负数做一点预处理，使得x=x+y-1。其中y就是我们的除数。
我们先来看看这么做对不对，(-7+2-1)/2 = (-6/2) =-3 没有问题啊。
证明如下：假设x = qy + r，其中0 &r &y。那么，(x + y & 1)/y = q + (r + y & 1)/y。当r=0的时候x/y=q，否则x/y=q+1。符合要求！！
代码实现是这样的：(x&0 ? x+(1&&k)-1 : x) && k。
哈哈，妙吧！
那么如果仅仅允许使用移位和&操作以及加法，怎么代码实现除法呢？（注意除数为2k)
int div16(int x) {
/* Compute bias to be either 0 (x &= 0) or 15 (x & 0) */
int bias = (x && 31) & 0xF;
return (x + bias) && 4;
看看这个代码写的！！亮瞎了吧。
当x为正数的时候,bias=0, 这没错。
当x为负数的时候，bias为15=16-1。又没问题！
好了，除法也就这些了！
4& 总结练习
Assume we are running code on a 32-bit machine using two&s-complement arithmetic for signed values. Right shifts are performed arithmetically for signed values
and logically for unsigned values. The variables are declared and initialized as
int x = foo(); /* Arbitrary value */
int y = bar(); /* Arbitrary value */
unsigned ux =
unsigned uy =
For each of the following C expressions, either (1) argue that it is true (evaluates
to 1) for all values of x and y, or (2) give values of x and y for which it is false
(evaluates to 0):
A. (x & 0) || (x-1 & 0)
B. (x & 7) != 7 || (x&&29 & 0)
C. (x * x) &= 0
D. x & 0 || -x &= 0
E. x & 0 || -x &= 0
F. x+y == uy+ux
G. x*~y + uy*ux == &x
解答如下：
A. (x & 0) || (x-1 & 0)
False. Let x be &2,147,483,648 (TMin32). We will then have x-1 equal to
B. (x & 7) != 7 || (x&&29 & 0)
True. If (x & 7) != 7 evaluates to 0, then we must have bit x2 equal to 1.
When shifted left by 29, this will become the sign bit.
C. (x * x) &= 0
False. When x is 65,535 (0xFFFF), x*x is &131,071 (0xFFFE0001).
D. x & 0 || -x &= 0
True. If x is nonnegative, then -x is nonpositive.
E. x & 0 || -x &= 0
False. Let x be &2,147,483,648 (TMin32). Then both x and -x are negative.
F. x+y == uy+ux
True. Two&s-complement and unsigned addition have the same bit-level behavior,
and they are commutative.
G. x*~y + uy*ux == -x
True. ~y equals -y-1. uy*ux equals x*y. Thus, the left hand side is equivalent
to x*-y-x+x*y.
随笔 - 114计算机操作员复习题库(1)
计算机操作员复习题库(1)
当前文档过大，建议您在wifi环境下观看蕴涵_百度百科
清除历史记录关闭
声明：百科词条人人可编辑，词条创建和修改均免费，绝不存在官方及代理商付费代编，请勿上当受骗。
[yùn hán]
蕴涵，汉语。① 里边含有，包含。②判断中前后两个命题间存在的某一种条件关系叫蕴涵，表现形式是“如果...则...”。例如“如果温度增高则寒暑表的水银柱上升”。基本含义近同于蕴含、包含、包涵，关系。
1.[accumulate] 。也称为“蕴含”。 2.逻辑名词。判断前后两个命题互为条件关系的叫&蕴涵&。表现形式是&如果……则……&（符号：“→“）。
基本解释：
1. 包含。也作“蕴含”。
词语分开解释：
蕴 : 蕴（蕴） yùn 积聚，蓄藏，包含：蕴蓄。蕴藏。蕴结（郁结）。蕴蕴（多指暑气郁积）。蕴含。蕴涵（a
涵 : 涵 hán 包容，包含：。涵容。涵养（a．蓄积并保持，如“涵涵水源”；b．指修养
《纪念逝世一百周年的演说》：“但是，其中蕴涵有哲理的忧伤。”
蕴涵假言命题
在假言判断中：如果P，那么Q，可以表示为P→Q
P称为前件（条件），Q称为后件（后果），“→”这个符号，逻辑叫做“蕴涵”
蕴涵式中，只有当前件真后件假时整个假言判断为假，其余均为真。
真假值如下表：
编程语言中，蕴涵逻辑运算符通常是Imp
清除历史记录关闭P∧(P→Q)=&Q？？【离散数学吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：6,927贴子：
P∧(P→Q)=&Q？？收藏
P∧(P→Q)=&Q
出处&左孝凌&《离散数学》&（上海科技文献出版社）&21页
个人推演如下：
P∧(P→Q)&=&P∧(┐P∨Q)&=&(P∧┐P)∨(P∧Q)&=&F∨(P∧Q)&=&(P&P∧(P→Q)=&Q
出处&左孝凌&《离散数学》&（上海科技文献出版社）&21页
个人推演如下：
P∧(P→Q)&=&P∧(┐P∨Q)&=&(P∧┐P)∨(P∧Q)&=&F∨(P∧Q)&=&P∧Q=&
到此&根据公式&应该为
P∧Q=&P&或Q
也就是说&
P∧(P→Q)=&Q&且P∧(P→Q)=&P
而不仅仅=&Q&&
问此推演是否正确？&
快试试吧，可以对自己使用挽尊卡咯~◆◆
我个的理解是：这段推理不是按照逻辑等价的规则来做的，而是按照推理规则来完成的。其逻辑形式是：如果p，那么q，&p；所以q。用数理逻辑的符号形式表示为：&((p→q)∧p)→q。例如：如果犯故意杀人罪，那么应受刑罚处罚；李四犯故意杀人罪，所以，李四应受刑罚处罚。也就是说，在P值为真的前提下，由P→Q，可以得出P∧(P→Q)=&Q
快试试吧，可以对自己使用挽尊卡咯~◆◆
补充一点，P∧(P→Q)=&Q&运用的推理规则是“假言推理”，《离散数学及其应用》（机械工业出版社，第5版），第47页说得很清楚：假言推理是说，若蕴含式及其前提都已知为真，则这个蕴含式的结论为真。也就是说，这个推理规则先已假定P&和P→Q为真，即P可以用T来代替，即你推出的最后结果P∧Q，实际上是T∧Q，最后的结论当然是Q
快试试吧，可以对自己使用挽尊卡咯~◆◆
P∧(P→Q)&=&Q
P&Q&(P→Q)&P∧(P→Q)
T&T&&&T&&&&&&&T
T&F&&&T&&&&&&&T
F&T&&&F&&&&&&&F
F&F&&&T&&&&&&&F
由此可得出P∧(P→Q)&=&Q;
只要判断（P∧(P→Q)）→Q是不是永真式就好了嘛。
（P∧(P→Q)）→Q&=&(p∧(┐P∨Q））→Q
&=&┐((P∧┐P)∨(P∧Q))∨Q
&=&┐(F∨(P∧Q))∨Q
&=&┐(P∧Q)∨Q
&=&┐P∨┐Q∨Q
&=&┐P∨T
&=&T
所以原式是永真式
拜托,搂主,这就是个永真式，原名叫modus&ponens,是最最最基本的rule&of&inference...
这两个符号什么意思∨ ∧
登录百度帐号