Изменения

Перейти к: навигация, поиск

XOR-SAT

9850 байт добавлено, 13:39, 5 января 2017
→‎Решение XOR-SAT задачи методом Гаусса
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|+
!colspan="52"|Система уравнений
|-align="center"
!("<tex>1</tex>" означает «<tex> \mathtt {true}</tex>», "<tex>0</tex>" означает «<tex> \mathtt {false}</tex>»)
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|+
!colspan="52"|Нормированная система уравнений
|-align="center"
! Используя свойства Булевых колец (<tex>\neg x=1 \oplus x</tex>, <tex>x \oplus x=01</tex>)
|
|-align="center"
|}
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|+
!colspan="6"|Матрица соответствующих коэффициентов
|-align="center"
!class="dark"| <tex>a</tex>
!class="dark"| <tex>b</tex>
!class="dark"| <tex>c</tex>
!class="dark"| <tex>d</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"|
|Строка
|-align="center"
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>
| <tex>A</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>0</tex>
| <tex>B</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>0</tex>
| <tex>C</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>
| <tex>D</tex>
|}
 
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|+
!colspan="6"|Преобразования, чтобы сформировать
верхнюю треугольную матрицу
|-align="center"
!class="dark"| <tex>a</tex>
!class="dark"| <tex>b</tex>
!class="dark"| <tex>c</tex>
!class="dark"| <tex>d</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"|
|Операция
|-align="center"
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>
| <tex>A</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>0</tex>
| <tex>C</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>
| <tex>D</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>0</tex>
| <tex>B</tex>
|}
 
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|+
|-align="center"
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>
| <tex>A</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>0</tex>
| <tex>C</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>
| <tex>D</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>0</tex>
| <tex>B</tex>
|}
 
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|+
|-align="center"
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>
| <tex>A</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>
| <tex>E=C \oplus A</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>0</tex>
| <tex>F=D \oplus A</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>0</tex>
| <tex>B</tex>
|}
 
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|+
|-align="center"
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>
| <tex>A</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>
| <tex>E</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>
| <tex>G=F \oplus E</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>
| <tex>H=B \oplus E</tex>
|}
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|+
!colspan="6"|Преобразования, чтобы сформировать
диагональную матрицу
|-align="center"
!class="dark"| <tex>a</tex>
!class="dark"| <tex>b</tex>
!class="dark"| <tex>c</tex>
!class="dark"| <tex>d</tex>
!class="green"|
|Операция
|-align="center"
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>0</tex>
| <tex>I=A \oplus H</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>
| <tex>E</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>0</tex>
| <tex>J=G \oplus H</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="dark" style="font-weight:normal"| <tex>1</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>
| <tex>H</tex>
|}
</center>
Павел Хужин
62
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/58768»

Навигация