極小化問題

極小化問題是求出與給定電路等效的一個（或所有）最簡電路的問題。實際上極小化問題就是求與給定真值函式（一種特殊的布爾函式）的一個（或所有）最簡的等值函式。

基本介紹

• 中文名：極小化問題
• 外文名：minimization problem
• 適用範圍：數理科學

定義介紹

極小化問題是求出與給定電路等效的一個（或所有）最簡電路的問題。實際上極小化問題就是求與給定真值函式（一種特殊的布爾函式）的一個（或所有）最簡的等值函式。較複雜的開關函式，常可化成與它相等但形式較簡單的開關函式。

例如， 與相等，但 ψ 比 f 簡單，實現 ψ 的組件比實現 f 的組件要少許多，而它們的邏輯功能卻相同。因此，用電路 ψ 來取代 f 既符合節省原則，而且還可提高效率，所以極小化問題是開關電路中的重要研究課題。求最簡電路的方法有多種，如代數化簡法，奎因一麥克勒斯基法，嘎柴拉法及卡諾圖法等。

真值函式

真值函式亦稱真值函項。一種特殊函式。指以真值集 {T,F} 為定義域和值域的函式。根據真值函式的變元個數，真值函式可為一元真值函式，二元真值函式······ n 元真值函式等。對任意的自然數 n≥1，總有個不同的 n 元真值函式。

開關函式

一個具有兩種狀態的電子元件稱為一個開關。它可由普通的一個開關或聯動開關組成。每一個開關的狀態由一個開關變數來表示，例如用A表示一個開關變數，用0, 1表示一個開關的兩個狀態，則開關變數A的取值是0或1。開關函式就是用來表示電子元件狀態的函式。