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

Содержание

1 Описание
2 Входные данные
3 Исходник на PHP
4 Примеры логических функций
- 4.1 Представимы линейным полиномом
- 4.2 Непредставимы линейным полиномом

Описание

Программа проверяет можно ли заданную булеву функцию представить линейным арифметическим полиномом. Используются материалы из статьи "В. П. Шмерко, Теоремы Малюгина: новое понимание в логическом управлении, проектировании сбис и структурах данных для новых технологий, Автомат. и телемех., 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 переменных соответственно. Далее следуют 2^N строк, в каждой N + K чисел "0" или "1". Первые N чисел - логические значения входов, следующие K чисел логические значения выходов.

Исходник на PHP

```
<?php
```
```
	set_time_limit(3600);
```
```
 
```
```
	function kronecker_product($a1, $a2) {
```
```
		$x1 = count($a1);
```
```
		$y1 = count($a1[0]);
```
```
		$x2 = count($a2);
```
```
		$y2 = count($a2[0]);
```
```
 
```
```
		$ret = array();
```
```
		for ($i1 = 0; $i1 < $x1; $i1++) {
```
```
			for ($i2 = 0; $i2 < $x2; $i2++) {
```
```
				for ($j1 = 0; $j1 < $y1; $j1++) {
```
```
					for ($j2 = 0; $j2 < $y2; $j2++) {
```

						$ret[$i1*$x2+$i2][$j1*$y2+$j2] = $a1[$i1][$j1]*$a2[$i2][$j2];

```
					}
```
```
				}
```
```
			}
```
```
		}
```
```
		return $ret;
```
```
	}
```
```
 
```
```
	function get_conversion_matrix($num) {
```
```
		$arr[0][0] = 1;
```
```
		$arr[0][1] = 0;
```
```
		$arr[1][0] = -1;
```
```
		$arr[1][1] = 1;
```
```
		if ($num == 1) {
```
```
			return $arr;
```
```
		}
```
```
		$narr = $arr;
```
```
		for ($i = 1; $i < $num; $i++) {
```

			$narr = kronecker_product($narr, $arr);

```
		}
```
```
		return $narr;
```
```
	}
```
```
 
```

	function gen_polinom_koeffs($kron, $f) {

```
		$len1 = count($f);
```
```
		$len2 = count($kron);
```
```
		if ($len1 != $len2) {
```

			echo "Something strange ($len1 != $len2)";

```
			exit;
```
```
		}
```
```
 
```
```
		$res = array();
```
```
		for ($i = 0; $i < $len1; $i++) {
```
```
			$res[$i] = 0;
```
```
			for ($j = 0; $j < $len1; $j++) {
```
```
				$res[$i] += $kron[$i][$j]*$f[$j];
```
```
			}
```
```
		}
```
```
		return $res;
```
```
	}
```
```
 
```
```
	function print_2d_matrix($arr) {
```
```
		$x = count($arr);
```
```
		$y = count($arr[0]);
```
```
 
```
```
		for ($i = 0; $i < $x; $i++) {
```
```
			for ($j = 0; $j < $y; $j++) {
```
```
				echo $arr[$i][$j]." ";
```
```
			}
```
```
			echo "\n";
```
```
		}
```
```
		echo "\n";
```
```
	}
```
```
 
```
```
	function print_polinom($res) {
```

		$alpha = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l');

```
		$len = count($res);
```
```
		echo "Polinom: ";
```
```
		for ($i = 0; $i < $len; $i++) {
```
```
			if ($res[$i] != 0) {
```
```
				if ($res[$i] > 0)
```
```
					echo "+";
```
```
				echo $res[$i];
```
```
 
```
```
				$pos = 0;
```
```
				$cur = $i;
```
```
				while ($cur) {
```
```
					if ($cur & 1)
```
```
						echo $alpha[$pos];
```
```
					$pos++;
```
```
					$cur = $cur >> 1;
```
```
				}
```
```
				echo "";
```
```
			}
```
```
		}
```
```
		echo "\n";
```
```
	}
```
```
 
```
```
	function count_ones($val) {
```
```
		$c = 0;
```
```
		while ($val) {
```
```
			if ($val & 1)
```
```
				$c++;
```
```
			$val = $val >> 1;
```
```
		}
```
```
		return $c;
```
```
	}
```
```
 
```

	function check_polinom_linearity($res) {

```
		$len = count($res);
```
```
		for ($i = 1; $i < $len; $i++) {
```
```
			if (count_ones($i) > 1) {
```
```
				if ($res[$i] != 0)
```
```
					return false;
```
```
			}
```
```
		}
```
```
		return true;
```
```
	}
```
```
 
```
```
	function get_bit($j, $num) {
```
```
		return ($j >> $num) & 1;
```
```
	}
```
```
 
```
```
	function if_pow_2($j) {
```
```
		if ($j == 0)
```
```
			return true;
```
```
		for ($i = 0; $i < 32; $i++) {
```
```
			if ($j == (1 << $i))
```
```
				return true;
```
```
		}
```
```
		return false;
```
```
	}
```
```
 
```
```
	function swap(&$arr, $i, $j) {
```
```
		$temp = $arr[$i];
```
```
		$arr[$i] = $arr[$j];
```
```
		$arr[$j] = $temp;
```
```
	}
```
```
 
```
```
	function gen_permute($arr, $i, $n) {
```
```
		global $permutations;
```
```
		if ($i == $n) {
```
```
			$permutations[] = $arr;
```
```
		} else {
```
```
			for ($j = $i; $j < $n; $j++) {
```
```
				swap($arr, $i, $j);
```
```
				gen_permute($arr, $i+1, $n);
```
```
				swap($arr, $i, $j);
```
```
			}
```
```
		}
```
```
	}
```
```
 
```

	function check_linearization_possibility_for_permutation_based_on_kroneker($f, $inum) {

```
		$kron = get_conversion_matrix($inum);
```

		$koefs = gen_polinom_koeffs($kron, $f);

		$result = check_polinom_linearity($koefs);

```
		if ($result == true || 1) {
```
```
			print_polinom($koefs);
```
```
		}
```
```
		return $result;
```
```
	}
```
```
 
```

	function check_linearization_possibility_for_permutation($f, $in, $out, $inum, $onum, $number) {

```
 
```

		for ($j = 0; $j < (1 << $inum); $j++) {

```
			if (if_pow_2($j))
```
```
				continue;
```
```
 
```

			// Считаем значение функции в точке j

```
			$sum = 0;
```
```
			for ($i = 0; $i < $inum; $i++) {
```
```
				$jni = get_bit($j, $inum-1-$i);
```
```
				$f2i = $f[1 << $i];
```
```
				$sum += $jni*$f2i;
```
```
			}
```
```
			$calc = 0;
```
```
			for ($i = 0; $i < $inum; $i++) {
```
```
				$jni = get_bit($j, $i);
```
```
				$calc += $jni;
```
```
			}
```
```
			$sum = $sum + $f[0]*(1 - $calc);
```
```
			if ($sum != $f[$j]) {
```

				echo "$sum != ".$f[$j]." for J = $j\n";

```
				return false;
```
```
			}
```
```
		}
```
```
 
```
```
		return true;
```
```
	}
```
```
 
```

	function check_linearization_possibility($in, $out) {

```
		global $permutations;
```
```
		$inum = count($in[0]);
```
```
		$onum = count($out[0]);
```
```
		$number = count($in);
```
```
 
```
```
		if ($onum > 10) {
```

			echo "It's not possible to check all permuatations for $onum number of outputs!\n";

```
			exit;
```
```
		}
```
```
 
```
```
		$permutations = array();
```
```
		for ($j = 0; $j < $onum; $j++) {
```
```
			$arr[$j] = $j;
```
```
		}
```
```
		gen_permute($arr,0,count($arr));
```
```
 
```
```
		foreach ($permutations as $perm) {
```
```
			echo "Check permuation of outputs:";
```
```
			for ($j = 0; $j < $onum; $j++) {
```
```
				echo " ".$perm[$j];
```
```
			}
```
```
			echo "\n";
```
```
 
```

			// Получаем вектор f для выхода

```
			for ($i = 0; $i < $number; $i++) {
```
```
				$f[$i] = 0;
```
```
				for ($j = 0; $j < $onum; $j++) {
```

					$f[$i] += ($out[$i][$j] << $perm[$j]);

```
				}
```
```
			}
```
```
 
```

			if (check_linearization_possibility_for_permutation_based_on_kroneker($f, $inum)) {

```
				return true;
```
```
			}
```
```
		}
```
```
		return false;
```
```
	}
```
```
 
```
```
	function read_tt($file, &$in, &$out) {
```
```
		$lines = explode("\n", $file);
```
```
		$arr = explode(" ", $lines[0]);
```
```
		$inum = $arr[0];
```
```
		$onum = $arr[1];
```
```
 
```
```
		$ci = 0;
```

		for ($i = 1; $i < count($lines); $i++) {

```
			$l = trim($lines[$i]);
```
```
			if ($l == '')
```
```
				continue;
```

			$l = preg_replace("/[^0-9]/i", " ", $l);

			$l = preg_replace("/[[:blank:]]+/i", " ", $l);

```
			$l = trim($l);
```
```
			$arr = explode(" ", $l);
```

			if (count($arr) != ($inum + $onum)) {

				echo "Some problem at line $i: ".$lines[$i]." (".count($arr)." != ".$inum." + ".$onum.")\n";

```
				print_r($arr);
```
```
				exit;
```
```
			}
```
```
			for ($j = 0; $j < $inum; $j++) {
```
```
				$in[$ci][$j] = $arr[$j];
```
```
			}
```
```
			for ($j = 0; $j < $onum; $j++) {
```
```
				$out[$ci][$j] = $arr[($j+$inum)];
```
```
			}
```
```
			$ci++;
```
```
		}
```
```
		if (count($in) != 1 << $inum) {
```

			echo "Check number of lines in truth table (".count($in)." != ".(1 << $inum).")\n";

```
			exit;
```
```
		}
```
```
	}
```
```
 
```

	function gen_random_truth_table($inum, $onum, &$in, &$out) {

```
		$number = (1 << $inum);
```
```
 
```
```
		for ($i = 0; $i < $number; $i++) {
```
```
			for ($j = 0; $j < $inum; $j++) {
```
```
				$in[$i][$j] = get_bit($i, $j);
```
```
			}
```
```
			for ($j = 0; $j < $onum; $j++) {
```
```
				$out[$i][$j] = mt_rand(0, 1);
```
```
			}
```
```
		}
```
```
		// print_r($in);
```
```
		// print_r($out);
```
```
	}
```
```
 
```

	function print_table_to_file($file, $in, $out) {

```
		$inum = count($in[0]);
```
```
		$onum = count($out[0]);
```
```
		$number = count($in);
```
```
		$o = fopen($file, "w");
```
```
		fprintf($o, "%d %d\n", $inum, $onum);
```
```
		for ($i = 0; $i < $number; $i++) {
```
```
			fprintf($o, "%d", $in[$i][0]);
```
```
			for ($j = 1; $j < $inum; $j++) {
```
```
				fprintf($o, " %d", $in[$i][$j]);
```
```
			}
```
```
			for ($j = 0; $j < $onum; $j++) {
```
```
				fprintf($o, " %d", $out[$i][$j]);
```
```
			}
```
```
			fprintf($o, "\n");
```
```
		}
```
```
		fclose($o);
```
```
	}
```
```
 
```
```
	function simple_test() {
```
```
		$kron = get_conversion_matrix(3);
```
```
		$f = array(0, 2, 6, 4, 7, 5, 1, 2);
```
```
		$ret = gen_polinom_koeffs($kron, $f);
```
```
		print_2d_matrix($kron);
```
```
		print_r($ret);
```
```
		print_polinom($ret);
```
```
		check_polinom_linearity($ret);
```
```
	}
```
```
 
```

	function check_truth_table_linearity($in_file) {

```
		$file = file_get_contents($in_file);
```
```
		read_tt($file, $in, $out);
```

		if (check_linearization_possibility($in, $out)) {

```
			echo "Possible !!!!\n";
```
```
		} else {
```
```
			echo "Not possible\n";
```
```
		}
```
```
	}
```
```
 
```

	function try_to_find_linear_truth_table($out_file, $inum, $onum) {

```
		for ($i = 0; $i < 100000; $i++) {
```
```
			unset($in);
```
```
			unset($out);
```

			gen_random_truth_table($inum, $onum, $in, $out);

```
 
```

			if (check_linearization_possibility($in, $out)) {

				print_table_to_file($out_file, $in, $out);

```
				echo "Possible !!!!\n";
```
```
				break;
```
```
			} else {
```
```
				echo "Not possible\n";
```
```
			}
```
```
		}
```
```
		echo "\n\n";
```
```
	}
```
```
 
```

	check_truth_table_linearity("example.txt");

	// try_to_find_linear_truth_table("tt.txt", 3, 2);

```
 
```
```
?>
```

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

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

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)

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

Содержание

Описание

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

Исходник на PHP

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

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

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

Навигация

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

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты