關于在線性條件下NP≠P的證明

樊雪雙 李云娟

1.西安思源學院基礎部 陜西西安 710038；2.瑪普阿大學研究生院 菲律賓馬尼拉 999005

本文將利用命題公式中所含有的自由變元總次數來刻畫命題公式的最簡形式，且證明命題公式所含有的邏輯門個數是否可轉化為多項式的等價于命題公式中所含有的自由變元總次數是否可轉化為多項式。

1 基本概念及基本定理

首先給出一些必備的概念與定理。

定義1，，…，，…稱為自由變元集序列，其中為自由變元的集合，且對于任意=1，2，……有?+1，記為{}。

定義2 對于任意，若問題真假由中的自由變元的賦值所決定，則稱是上的一個問題。對于任意，其對應的命題公式記為。命題公式序列，，…，，…稱為問題的公式序列，記為{}。

定義3 公式中自由變元的總次數稱為的勢，記為‖‖。

定義4 設公式序列{}，若存在關于的多項式()使得‖‖≤()，則稱公式序列{}是勢多項式的。

定義5 設公式序列{}和{}，對于任意都有?，則稱公式序列{}和{}邏輯等價。

定義6 設公式序列{}，若存在與之邏輯等價且為勢多項式的序列，則稱{}是可勢多項式的。

定義6設公式序列{}，若存在與之邏輯等價且為聯結詞多項式的序列，則稱{}是可聯結詞多項式的。

定義7 給定公式，若公式滿足以下兩條，則稱為的一個極小式。

與邏輯等價。

(2)不存在與邏輯等價的公式，使得‖‖<‖‖。

定義8對于命題公式，把蘊含的原子合取式稱為的一個解。進一步，若不存在的解，使得?，且‖‖<‖‖，則稱為的一個極簡解。

為了對命題公式進行等價轉換，引入強Demorgen轉換。

定義9 對命題公式可多次利用Demorgen律，使得邏輯非下不再含有析取和合取，然后可再利用雙重否定律，使得公式中每個自由變元上最多含有一個邏輯非，稱該轉換過程為強Demorgen轉換。