Программа для проверки представимости булевой функции линейным арифметическим полиномом (PHP)

Материал из Модулярная арифметики
Перейти к: навигация, поиск

Содержание

Описание

Программа проверяет можно ли заданную булеву функцию представить линейным арифметическим полиномом. Используются материалы из статьи "В. П. Шмерко, Теоремы Малюгина: новое понимание в логическом управлении, проектировании сбис и структурах данных для новых технологий, Автомат. и телемех., 2004, выпуск 6, 61–83" Статья

Входные данные

На вход программы подается таблица истинности в виде:

4 3
0 0 0 0 0 0 0
0 0 0 1 0 0 1
0 0 1 0 0 1 0
0 0 1 1 0 1 1
0 1 0 0 0 0 1
0 1 0 1 0 1 0
0 1 1 0 0 1 1
0 1 1 1 1 0 0
1 0 0 0 0 1 0
1 0 0 1 0 1 1
1 0 1 0 1 0 0
1 0 1 1 1 0 1
1 1 0 0 0 1 1
1 1 0 1 1 0 0
1 1 1 0 1 0 1
1 1 1 1 1 1 0

Здесь первые два числа количество входных N и выходных K переменных соответственно. Далее следуют 2N строк, в каждой N + K чисел "0" или "1". Первые N чисел - логические значения входов, следующие K чисел логические значения выходов.

Исходник на PHP

  1. <?php
  2. 	set_time_limit(3600);
  3.  
  4. 	function kronecker_product($a1, $a2) {
  5. 		$x1 = count($a1);
  6. 		$y1 = count($a1[0]);
  7. 		$x2 = count($a2);
  8. 		$y2 = count($a2[0]);
  9.  
  10. 		$ret = array();
  11. 		for ($i1 = 0; $i1 < $x1; $i1++) {
  12. 			for ($i2 = 0; $i2 < $x2; $i2++) {
  13. 				for ($j1 = 0; $j1 < $y1; $j1++) {
  14. 					for ($j2 = 0; $j2 < $y2; $j2++) {
  15. 						$ret[$i1*$x2+$i2][$j1*$y2+$j2] = $a1[$i1][$j1]*$a2[$i2][$j2];
  16. 					}
  17. 				}
  18. 			}
  19. 		}
  20. 		return $ret;
  21. 	}
  22.  
  23. 	function get_conversion_matrix($num) {
  24. 		$arr[0][0] = 1;
  25. 		$arr[0][1] = 0;
  26. 		$arr[1][0] = -1;
  27. 		$arr[1][1] = 1;
  28. 		if ($num == 1) {
  29. 			return $arr;
  30. 		}
  31. 		$narr = $arr;
  32. 		for ($i = 1; $i < $num; $i++) {
  33. 			$narr = kronecker_product($narr, $arr);
  34. 		}
  35. 		return $narr;
  36. 	}
  37.  
  38. 	function gen_polinom_koeffs($kron, $f) {
  39. 		$len1 = count($f);
  40. 		$len2 = count($kron);
  41. 		if ($len1 != $len2) {
  42. 			echo "Something strange ($len1 != $len2)";
  43. 			exit;
  44. 		}
  45.  
  46. 		$res = array();
  47. 		for ($i = 0; $i < $len1; $i++) {
  48. 			$res[$i] = 0;
  49. 			for ($j = 0; $j < $len1; $j++) {
  50. 				$res[$i] += $kron[$i][$j]*$f[$j];
  51. 			}
  52. 		}
  53. 		return $res;
  54. 	}
  55.  
  56. 	function print_2d_matrix($arr) {
  57. 		$x = count($arr);
  58. 		$y = count($arr[0]);
  59.  
  60. 		for ($i = 0; $i < $x; $i++) {
  61. 			for ($j = 0; $j < $y; $j++) {
  62. 				echo $arr[$i][$j]." ";
  63. 			}
  64. 			echo "\n";
  65. 		}
  66. 		echo "\n";
  67. 	}
  68.  
  69. 	function print_polinom($res) {
  70. 		$alpha = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l');
  71. 		$len = count($res);
  72. 		echo "Polinom: ";
  73. 		for ($i = 0; $i < $len; $i++) {
  74. 			if ($res[$i] != 0) {
  75. 				if ($res[$i] > 0)
  76. 					echo "+";
  77. 				echo $res[$i];
  78.  
  79. 				$pos = 0;
  80. 				$cur = $i;
  81. 				while ($cur) {
  82. 					if ($cur & 1)
  83. 						echo $alpha[$pos];
  84. 					$pos++;
  85. 					$cur = $cur >> 1;
  86. 				}
  87. 				echo "";
  88. 			}
  89. 		}
  90. 		echo "\n";
  91. 	}
  92.  
  93. 	function count_ones($val) {
  94. 		$c = 0;
  95. 		while ($val) {
  96. 			if ($val & 1)
  97. 				$c++;
  98. 			$val = $val >> 1;
  99. 		}
  100. 		return $c;
  101. 	}
  102.  
  103. 	function check_polinom_linearity($res) {
  104. 		$len = count($res);
  105. 		for ($i = 1; $i < $len; $i++) {
  106. 			if (count_ones($i) > 1) {
  107. 				if ($res[$i] != 0)
  108. 					return false;
  109. 			}
  110. 		}
  111. 		return true;
  112. 	}
  113.  
  114. 	function get_bit($j, $num) {
  115. 		return ($j >> $num) & 1;
  116. 	}
  117.  
  118. 	function if_pow_2($j) {
  119. 		if ($j == 0)
  120. 			return true;
  121. 		for ($i = 0; $i < 32; $i++) {
  122. 			if ($j == (1 << $i))
  123. 				return true;
  124. 		}
  125. 		return false;
  126. 	}
  127.  
  128. 	function swap(&$arr, $i, $j) {
  129. 		$temp = $arr[$i];
  130. 		$arr[$i] = $arr[$j];
  131. 		$arr[$j] = $temp;
  132. 	}
  133.  
  134. 	function gen_permute($arr, $i, $n) {
  135. 		global $permutations;
  136. 		if ($i == $n) {
  137. 			$permutations[] = $arr;
  138. 		} else {
  139. 			for ($j = $i; $j < $n; $j++) {
  140. 				swap($arr, $i, $j);
  141. 				gen_permute($arr, $i+1, $n);
  142. 				swap($arr, $i, $j);
  143. 			}
  144. 		}
  145. 	}
  146.  
  147. 	function check_linearization_possibility_for_permutation_based_on_kroneker($f, $inum) {
  148. 		$kron = get_conversion_matrix($inum);
  149. 		$koefs = gen_polinom_koeffs($kron, $f);
  150. 		$result = check_polinom_linearity($koefs);
  151. 		if ($result == true || 1) {
  152. 			print_polinom($koefs);
  153. 		}
  154. 		return $result;
  155. 	}
  156.  
  157. 	function check_linearization_possibility_for_permutation($f, $in, $out, $inum, $onum, $number) {
  158.  
  159. 		for ($j = 0; $j < (1 << $inum); $j++) {
  160. 			if (if_pow_2($j))
  161. 				continue;
  162.  
  163. 			// Считаем значение функции в точке j
  164. 			$sum = 0;
  165. 			for ($i = 0; $i < $inum; $i++) {
  166. 				$jni = get_bit($j, $inum-1-$i);
  167. 				$f2i = $f[1 << $i];
  168. 				$sum += $jni*$f2i;
  169. 			}
  170. 			$calc = 0;
  171. 			for ($i = 0; $i < $inum; $i++) {
  172. 				$jni = get_bit($j, $i);
  173. 				$calc += $jni;
  174. 			}
  175. 			$sum = $sum + $f[0]*(1 - $calc);
  176. 			if ($sum != $f[$j]) {
  177. 				echo "$sum != ".$f[$j]." for J = $j\n";
  178. 				return false;
  179. 			}
  180. 		}
  181.  
  182. 		return true;
  183. 	}
  184.  
  185. 	function check_linearization_possibility($in, $out) {
  186. 		global $permutations;
  187. 		$inum = count($in[0]);
  188. 		$onum = count($out[0]);
  189. 		$number = count($in);
  190.  
  191. 		if ($onum > 10) {
  192. 			echo "It's not possible to check all permuatations for $onum number of outputs!\n";
  193. 			exit;
  194. 		}
  195.  
  196. 		$permutations = array();
  197. 		for ($j = 0; $j < $onum; $j++) {
  198. 			$arr[$j] = $j;
  199. 		}
  200. 		gen_permute($arr,0,count($arr));
  201.  
  202. 		foreach ($permutations as $perm) {
  203. 			echo "Check permuation of outputs:";
  204. 			for ($j = 0; $j < $onum; $j++) {
  205. 				echo " ".$perm[$j];
  206. 			}
  207. 			echo "\n";
  208.  
  209. 			// Получаем вектор f для выхода
  210. 			for ($i = 0; $i < $number; $i++) {
  211. 				$f[$i] = 0;
  212. 				for ($j = 0; $j < $onum; $j++) {
  213. 					$f[$i] += ($out[$i][$j] << $perm[$j]);
  214. 				}
  215. 			}
  216.  
  217. 			if (check_linearization_possibility_for_permutation_based_on_kroneker($f, $inum)) {
  218. 				return true;
  219. 			}
  220. 		}
  221. 		return false;
  222. 	}
  223.  
  224. 	function read_tt($file, &$in, &$out) {
  225. 		$lines = explode("\n", $file);
  226. 		$arr = explode(" ", $lines[0]);
  227. 		$inum = $arr[0];
  228. 		$onum = $arr[1];
  229.  
  230. 		$ci = 0;
  231. 		for ($i = 1; $i < count($lines); $i++) {
  232. 			$l = trim($lines[$i]);
  233. 			if ($l == '')
  234. 				continue;
  235. 			$l = preg_replace("/[^0-9]/i", " ", $l);
  236. 			$l = preg_replace("/[[:blank:]]+/i", " ", $l);
  237. 			$l = trim($l);
  238. 			$arr = explode(" ", $l);
  239. 			if (count($arr) != ($inum + $onum)) {
  240. 				echo "Some problem at line $i: ".$lines[$i]." (".count($arr)." != ".$inum." + ".$onum.")\n";
  241. 				print_r($arr);
  242. 				exit;
  243. 			}
  244. 			for ($j = 0; $j < $inum; $j++) {
  245. 				$in[$ci][$j] = $arr[$j];
  246. 			}
  247. 			for ($j = 0; $j < $onum; $j++) {
  248. 				$out[$ci][$j] = $arr[($j+$inum)];
  249. 			}
  250. 			$ci++;
  251. 		}
  252. 		if (count($in) != 1 << $inum) {
  253. 			echo "Check number of lines in truth table (".count($in)." != ".(1 << $inum).")\n";
  254. 			exit;
  255. 		}
  256. 	}
  257.  
  258. 	function gen_random_truth_table($inum, $onum, &$in, &$out) {
  259. 		$number = (1 << $inum);
  260.  
  261. 		for ($i = 0; $i < $number; $i++) {
  262. 			for ($j = 0; $j < $inum; $j++) {
  263. 				$in[$i][$j] = get_bit($i, $j);
  264. 			}
  265. 			for ($j = 0; $j < $onum; $j++) {
  266. 				$out[$i][$j] = mt_rand(0, 1);
  267. 			}
  268. 		}
  269. 		// print_r($in);
  270. 		// print_r($out);
  271. 	}
  272.  
  273. 	function print_table_to_file($file, $in, $out) {
  274. 		$inum = count($in[0]);
  275. 		$onum = count($out[0]);
  276. 		$number = count($in);
  277. 		$o = fopen($file, "w");
  278. 		fprintf($o, "%d %d\n", $inum, $onum);
  279. 		for ($i = 0; $i < $number; $i++) {
  280. 			fprintf($o, "%d", $in[$i][0]);
  281. 			for ($j = 1; $j < $inum; $j++) {
  282. 				fprintf($o, " %d", $in[$i][$j]);
  283. 			}
  284. 			for ($j = 0; $j < $onum; $j++) {
  285. 				fprintf($o, " %d", $out[$i][$j]);
  286. 			}
  287. 			fprintf($o, "\n");
  288. 		}
  289. 		fclose($o);
  290. 	}
  291.  
  292. 	function simple_test() {
  293. 		$kron = get_conversion_matrix(3);
  294. 		$f = array(0, 2, 6, 4, 7, 5, 1, 2);
  295. 		$ret = gen_polinom_koeffs($kron, $f);
  296. 		print_2d_matrix($kron);
  297. 		print_r($ret);
  298. 		print_polinom($ret);
  299. 		check_polinom_linearity($ret);
  300. 	}
  301.  
  302. 	function check_truth_table_linearity($in_file) {
  303. 		$file = file_get_contents($in_file);
  304. 		read_tt($file, $in, $out);
  305. 		if (check_linearization_possibility($in, $out)) {
  306. 			echo "Possible !!!!\n";
  307. 		} else {
  308. 			echo "Not possible\n";
  309. 		}
  310. 	}
  311.  
  312. 	function try_to_find_linear_truth_table($out_file, $inum, $onum) {
  313. 		for ($i = 0; $i < 100000; $i++) {
  314. 			unset($in);
  315. 			unset($out);
  316. 			gen_random_truth_table($inum, $onum, $in, $out);
  317.  
  318. 			if (check_linearization_possibility($in, $out)) {
  319. 				print_table_to_file($out_file, $in, $out);
  320. 				echo "Possible !!!!\n";
  321. 				break;
  322. 			} else {
  323. 				echo "Not possible\n";
  324. 			}
  325. 		}
  326. 		echo "\n\n";
  327. 	}
  328.  
  329. 	check_truth_table_linearity("example.txt");
  330. 	// try_to_find_linear_truth_table("tt.txt", 3, 2);
  331.  
  332. ?>

Примеры логических функций

Представимы линейным полиномом

3 4
0 0 0  0 1 1 1
0 0 1  0 0 1 1
0 1 0  1 0 0 0
0 1 1  0 1 0 0
1 0 0  1 1 1 0
1 0 1  1 0 1 0
1 1 0  1 1 1 1
1 1 1  1 0 1 1

Непредставимы линейным полиномом

ISCAS85 C17:

5 2
(0, 0, 0, 0, 0) | (0, 0)
(0, 0, 0, 0, 1) | (0, 1)
(0, 0, 0, 1, 0) | (0, 0)
(0, 0, 0, 1, 1) | (0, 1)
(0, 0, 1, 0, 0) | (0, 0)
(0, 0, 1, 0, 1) | (0, 1)
(0, 0, 1, 1, 0) | (0, 0)
(0, 0, 1, 1, 1) | (0, 0)
(0, 1, 0, 0, 0) | (1, 1)
(0, 1, 0, 0, 1) | (1, 1)
(0, 1, 0, 1, 0) | (1, 1)
(0, 1, 0, 1, 1) | (1, 1)
(0, 1, 1, 0, 0) | (1, 1)
(0, 1, 1, 0, 1) | (1, 1)
(0, 1, 1, 1, 0) | (0, 0)
(0, 1, 1, 1, 1) | (0, 0)
(1, 0, 0, 0, 0) | (0, 0)
(1, 0, 0, 0, 1) | (0, 1)
(1, 0, 0, 1, 0) | (0, 0)
(1, 0, 0, 1, 1) | (0, 1)
(1, 0, 1, 0, 0) | (1, 0)
(1, 0, 1, 0, 1) | (1, 1)
(1, 0, 1, 1, 0) | (1, 0)
(1, 0, 1, 1, 1) | (1, 0)
(1, 1, 0, 0, 0) | (1, 1)
(1, 1, 0, 0, 1) | (1, 1)
(1, 1, 0, 1, 0) | (1, 1)
(1, 1, 0, 1, 1) | (1, 1)
(1, 1, 1, 0, 0) | (1, 1)
(1, 1, 1, 0, 1) | (1, 1)
(1, 1, 1, 1, 0) | (1, 0)
(1, 1, 1, 1, 1) | (1, 0)

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация