實現給定布林表示式的基本邏輯閘最小數量

---

邏輯閘是數位電路的基本組成單元。它們接收一個或兩個二進位制輸入，並返回一個二進位制輸出。由於使用了二進位制術語，輸出和輸入可以是0或1，也可以說是“假”和“真”或“低”和“高”。

有三種基本邏輯閘：

與門

與門有兩個或多個輸入和一個輸出。如果所有輸入都為高電平，則產生高電平輸出。一個雙輸入與門的真值表如下：

輸入1	輸入2	輸出
1	1	1
1	0	0
0	1	0
0	0	0

或門

或門有兩個或多個輸入和一個輸出。如果任何一個輸入為高電平，則產生高電平輸出。一個雙輸入或門的真值表如下：

輸入1	輸入2	輸出
1	1	1
1	0	1
0	1	1
0	0	0

非門

非門有一個輸入和一個輸出。如果輸入為低電平，則產生高電平輸出；如果輸入為高電平，則產生低電平輸出。非門的真值表如下：

輸入	輸出
1	0
0	1

這三種基本邏輯閘可以組合起來建立更復雜的電路，例如與非門、或非門和異或門。

布林表示式：它是一個包含一個或多個變數、邏輯運算子和常量的數學表示式。變數的值可以是0或1，用a、b、c等表示。布林表示式中使用的邏輯運算子通常是與、或和非。這些運算子以某種方式組合變數和常量，從而定義變數或常量之間的關係。

例如，布林表示式 A AND B 只有在變數 A 和 B 都為真時才為真。表示式 A OR B 如果變數 A 或變數 B 或兩者都為真，則為真。表示式 NOT A 只有在變數 A 為假時才為真。

布林表示式通常用於程式設計、電路設計和數位電子學中，以表示邏輯運算、條件和所用變數之間的邏輯關係。

問題陳述

給定一個定義布林表示式的字串 str。找到實現給定表示式所使用的基本邏輯閘的最小數量。

輸入：

str = “!A.B+C”

輸出：

3

解釋

該表示式使用1個非門（用'!'表示）、1個與門（用'.'表示）和1個或門（用'+'表示）。因此，總共有3個基本邏輯閘。

示例2

輸入：

str = “!(a+b)+c.d”

輸出：

4

解釋

該表示式使用1個非門（用'!'表示）、2個與門（用'.'表示）和1個或門（用'+'表示）。因此，總共有4個基本邏輯閘。

解決方案方法

為了實現布林表示式的邏輯閘總數，我們計算字串中出現的門總數，並根據其符號表示識別它們。

• 與門表示為'.'

• 或門表示為'+'

• 非門表示為'!'

虛擬碼

procedure numberOfGates (s)
n = length(s)
   count = 0
   for i = 1 to n
      if s[i] equals '.' or s[i] equals '+' or s[i] equals '!'
         count = count + 1
      end if
   end for
   output count
end procedure

示例：C++ 實現

在下面的程式中，我們遍歷布林表示式並根據其出現次數計算門數。

#include <bits/stdc++.h>
using namespace std;
// Function to find the number of basic logic gates used in a boolean expression
void numberOfGates(string s){

   // Calculating the size of the string
   int n = s.size();
   
   // Initialising count variable
   int count = 0;
   
   // Traversing the string to find the gate's symbols
   for (int i = 0; i < n; i++) {
   
      // Incrementing counter on the occurrence of AND, OR or NOT gate
      if (s[i] == '.' || s[i] == '+' || s[i] == '!') {
         count++;
      }
   }
   cout << count;
}
int main(){
   string str = "!a+b";
   cout << "Boolean Exoression: " << str << endl;
   cout << "Minimum number of basic logic gate required: " ;
   numberOfGates(str);
}

輸出

Boolean Exoression: !a+b
Minimum number of basic logic gate required: 2

結論

總之，為了找到實現給定布林表示式所需的基本邏輯閘的最小數量，我們可以有效地使用 numberOfGates() 函式。此函式將定義布林表示式的字串作為輸入，並輸出實現表示式所需的最小門數。最小化邏輯閘對於降低電路的成本和複雜性非常重要。

總的來說，該程式碼是一種簡單有效的方法，可以計算實現布林表示式所需的基本邏輯閘的數量，並且可以輕鬆地將其應用於更復雜的數位電路。