对位运算与逻辑电路统一性的浅显理解

时间:2024-01-27 13:50:07

前言

在学OI的过程中,我一开始完全不懂位运算,后来经过一些题目的记忆,也是能够记下来算术运算符它们的效果和作用,但是总是忘记每个运算符具体的效果,比如或运算与运算之类。

今天无意间翻开物理书,看到逻辑电路那一节,里面的与,或不就是算术位运算的效果吗?我突然感到自己是个弱智,先前都是在死记硬背(数学课讲逻辑的时候也有与和或,当时没有联想到按位运算,只是想到了对于条件且(&&)和条件(||)的类比)

(我死记硬背的方法——在便笺里放着小口诀)

于是我打算改变我憨批一般的死记硬背,从更基本的逻辑电路出发来记忆和理解各个位运算的效果。

将数学语言上的逻辑,计算机上的逻辑(程序语言),电路上的逻辑(其实也是计算机底层的逻辑吧)统一起来,让自己更清晰。

而众所周知,计算机位运算中有 “与” “或”“非”“异或”四种算术位运算,下面将分别分析和统一它们。

##事先备注,下文的表述中在数学上只是逻辑语言,用于一种描述或进行推论;而表现在计算机中,这些逻辑运用都是二进制下按位运算,也就是对二进制数的每一位都进行这样的逻辑运算;物理上就是逻辑门的关系,(当然还存在“与非”“或非”等等,本文只讲述与c++位运算有关内容,这些并无直接对应,但可以通过组合实现)。它们只是在逻辑上统一,具有相同的逻辑关系,并非含义等同。


 

基本介绍

  • :  

    符号:

        数学: ∧             (这个不是^(次方或者异或符号),是逻辑与)

        计算机(c++)(其实是按位与)    : and    &   (整条语句为“&&”)

    具体描述 :

                  都为真才为真 ,或者说 输入都为1(true) 才输出 1(true) ,再或者说 条件都为1(true) 结论才为1(true)。

        对于c++来说,使用第二条来记录比较具象(就是我便笺上写的)。

                  物理上的逻辑(开关串联):

       

                  我们规定开关关闭(断路)则表示条件(逻辑再者说输入)为0(假),开关开启(通路)则表示条件(逻辑再者说输入)为1(真),

                        两者都为1的时候,两者都为0(0&0),灯泡的状态为不亮,即表现为0(假);同时,开关一开一关(0&1),

        显然灯泡也不会亮,即表现为0(假);只有二者均为1(1&1)的时候,灯泡才会亮,即表现为1(真);

    运算表达式:

      数学(其实数学这里“与”其实是“逻辑且(逻辑与)”吧,对应在程序里是&&而不是按位与的&,但它们在逻辑上是并通的): 

              如果条件p为假,条件q为假,那么   p∧q=假;

        如果条件 p为真,q为假或者p为假,q为真 ,那么p∧q=假;

        如果p,q都为真,那么p∧q=真

        抽象点(有定义,乘法为与,"+"表逻辑或,条件加“ ' ”为非): 

        F=AB (AB都为1,F才为1)

      计算机(二进制按位运算):

               0&0=0;1&0=0;0&1=0;1&1=1;

      物理:这咋表达?这个只能用图

      逻辑上的统一就是:都为真才得到真这不还是那句话?——但是我们多了个物理含义!是不是更好记了?
              

  • 或:    

    符号:

      数学:  ∨ 

      计算机(c++): or  |  (对于整条语句来说是“||”)

    具体描述:

        只要有一个为真就是真,都为假时才是假;或者说输入有一个为1(true)就是1(true),都为0(false)才是假;

        再或者说,条件有一个为1(true)结论就为1(true),条件均为0(false)结论才为0(false)。  

        对于c++来说,仍然是第二条。

        物理上的逻辑(开关并联):

      

        同样的,开关通路(开)则表示1,断路(关)则表示0。如图

        两者都为1(开)的时候(1|1),则为1,任意一者为1(1|0)的时候也为1,即这两种情况灯是亮的;

        而只有两者都为0(0|0)的时候才为0,即灯是不亮的;

    运算表达式:         

      数学(同逻辑与,数学的含义实际类似于“||”):

        如果条件p,q至少有一个为真,则p∨q=真。

        如果条件都为假,则p∨q=假。

        抽象点(有定义,乘法为与,"+"表逻辑或,条件加“ ' ”为非): 

        F=A+B     (AB只要有一个为1,F就不为0)

      计算机(二进制按位运算):

        1|1=1;0|1=1;1|0=1;0|0=0; 

      物理:并联开关一个为开则干路上的灯为亮,都关了才不亮。     

      逻辑上的统一就是:都为假才是假

  • 非:    

    符号:    

      数学:    ¬

      计算机(c++): ~ (对于整条语句来说是“!”,不过在c++的条件语句里,二者都可以作用于一个判断语句的真假,但对数字按位取反要用~) 

     具体描述:  

        是真则为假,是假则为真。输入为输出相反。条件与结论相反。

        c++同样为第二条。

        物理上的逻辑(开关串联,与灯泡并联):

         

        同上,很显然的就是,开关打开(通路)时灯泡不亮(被短路了)  (!1),即为0,开关关闭(断路)时灯泡亮(!0),即为1。

   运算表达式:

     数学:   若p为真,则¬p为假

         若p为假,则¬p为真

         抽象点(有定义,乘法为与,"+"表逻辑或,条件加“ ' ”为非): 

         F=A'

     计算机(二进制按位运算): 这个比较特殊,因为如果要按位非的话,也就是按位取反

        由于计算机内一个数字变量类型的最高为(比如int的第32位)符号位,按位取反则对从32到1所有取反

        所以说~1=-2,~0=-1。但是

        !0=1    !1=0      

        实际上除了!0之外的所有数进行!操作,都是0

        "!"只是逆转真假罢了,一个数只有是0的时候才是假,所以只有0的时候进行"!"才是真,于是造成了这样的结果。

     物理:开开关灯就灭,关开关等就亮
     统一的逻辑就是:是真则为假,是假则为真

  • 异或:

     符号:   

      数学:    ⊕

      计算机(c++): xor   ^ 

    具体描述:   

        相同则为假,相异则为真。输入都为0或1则为假,输入为一0一1则为真。条件都真或者都假结论就假,条件一真一假才为真。

        c++同样为第二条。

        物理上的逻辑(不好用语言描述图了,口胡一下:非电路和另一开关构造与电路,再交换开关复制成或电路):

        图一(严格按照数学表达式):

      ,    

        令上下的并联开关为k1,可以理解为同一个开关,二者操作同时,表达同时同等,k2理解为另一个开关,二者同时同等。

        当k1打开,k2关闭的时候(1^0),上路的灯可以亮,当k2打开,k1关闭的时候(0^1),下路的灯可以亮。

          当k1,k2都关闭(0^0)或者都打开(1^1)的时候,两个路的灯都不可以亮。

        总的表示就是开关状态相同则不亮,开关状态不同则亮。

        图2(与非电路串或电路,并借此分析异或的条件与结论的关系):

         

        如图。还是两个k1同步,两个k2同步。(下面的叙述较长,于是我以插入代码的形式压缩了起来)

       

左边这团电路是"与非电路",与非电路即先与再非的电路,当""表达为假的时候总表达为真,反之为假。
右边的或电路和灯是串的,所以逻辑就是单纯的或。

如果只有左电路,开关都打开灯一定不亮,灯不亮时开关一定都打开(开关是通路,灯被短路),二者互为充要条件。
放在整个电路中,虽然灯不亮时开关不一定都打开,但开关都打开时灯一定不亮(被短路),

所以开关都打开是灯不亮的充分不必要条件,灯不亮是开关都打开的必要不充分条件。

如果只有右电路,开关都关闭灯一定不亮,灯不亮时开关一定都关闭(灯被断路),二者互为充要条件。
放在整个电路中,虽然灯不亮时开关不一定都关闭,但开关都关闭时灯一定不亮,

所以开关都关闭时灯不亮的充分不必要条件,灯不亮是开关都关闭的必要不充分条件。

以上分析可知,开关都开或者都闭的时候(0^0或者1^1),灯一定不亮(0)。灯不亮的时候一定是开关都开或都关的时候。
也就是说,开关状态一致和灯的不亮,互为充要条件,既然它们互为充要,如果画成韦恩图,二者等价。

到这里可以用数学的逻辑推出来开关不一致对应的是灯亮:

    很明显开关状态不一致是和开关状态一致是相反的说法,没有交集,所以说它对开关的不亮是既不充分也不必要条件。
    因为开关如果分成一致(0)或不一致(1)只有0/1两个状态,灯泡的亮与不亮也只有两个状态,所以说灯亮的时候一定和开关状态不一致时等价的。
    也就是说开关状态不一致的时候,灯一定是亮的。
  具体来说,开关状态不一致的时候,"与非电路"为真(1),而或电路也为真(1),二者又是与的关系,都为真(1) 则表达为真(1),所以说灯泡就是亮的,为真(1)。    
View Code

        其实个人觉得两个图都比较好记,图一的优点在于完全对应数学表达,图二的优点在于不在乎k1,k2的交换,只要左右电路分别有对k1,k2就行。

    运算表达式:  

      数学:条件p和条件q一真一假,则 p ⊕ q=真 

            条件p和条件q都为真或者都为假,则p ⊕ q =假

         抽象点(有定义,乘法为与,"+"表逻辑或,条件加“ ' ”为非): 

         F=AB'+A'B(完全对应图1,图二相当于 F=(AB)'(A+B),两式结果相同)

      计算机(c++):   

 

           0^0=0;1^1=0;0^1=1;1^0=1;

         统一的逻辑就是:同则为0,异则为1


后记

   写下来花了两三个小时,尽管已经查阅资料尽量保证语言的严谨性,但总怕难免有我误解的地方。

   不过大的错误应该没有,或许会有小地方术语说错的,不过不影响物理图数学公式和c++逻辑上的统一性。

   写完之后感觉自己受益良多,强化加深了自己在逻辑运算和位运算方面的理解,甚至包括一些c++语法上的理解。

   同时我再也不会忘了这些算术运算符在c++的效果了。

   到此结束!

   希望看到的人也能有收获,同时欢迎各位提出建议,批评指正。