62
правки
Изменения
→Решение XOR-SAT задачи методом Гаусса
!class="dark"| <tex>c</tex>
!class="dark"| <tex>d</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"|
|Операция
|-align="center"
!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>
|}
{| 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>0</tex>
!class="dark" style="font-weight:normal"| <tex>0</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>0</tex>
| <tex>K=I \oplus J</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>0</tex>
!class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>
| <tex>L=E \oplus J</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</tex>
|-align="center"
!class="dark" style="font-weight:normal"| <tex>0</tex>
|}
</center>
Следствие:<tex>R</tex>(<tex>a</tex>,<tex>c</tex>,<tex>d</tex>)<tex>\land</tex> <tex>R</tex>(<tex>b</tex>,<tex>\neg c</tex>,<tex>d</tex>)<tex>\land</tex><tex>R</tex>(<tex>a</tex>,<tex>b</tex>,<tex>\neg d</tex>)<tex>\land</tex><tex>R</tex>(<tex>a</tex>,<tex>\neg b</tex>,<tex>\neg c</tex>)<font color='red'>∧ R(¬a,b,c)</font>
==Вычислительная сложность==
