Лекции - Машины Тьюринга. Основы теории вычислимости. Булевы функции и пропозициональные формулы
Подождите немного. Документ загружается.
x
i
¬x
i
(x
1
∨ ¬x
2
∨ x
3
)
(x
1
∨ ¬x
2
∨ x
3
) ∧ (¬x
1
∨ ¬x
3
) ∧ ¬x
1
(x
1
∧ ¬x
2
∧ x
3
)
(x
1
∧ ¬x
2
∧ x
3
) ∨ (¬x
1
∧ ¬x
3
) ∨ ¬x
1
x
i
¬x
i
(x
1
∨ ¬x
2
∨ x
3
)
(x
1
∨ ¬x
2
∨ x
3
) ∧ (¬x
1
∨ ¬x
3
) ∧ ¬x
1
(x
1
∧ ¬x
2
∧ x
3
)
(x
1
∧ ¬x
2
∧ x
3
) ∨ (¬x
1
∧ ¬x
3
) ∨ ¬x
1
x
i
¬x
i
(x
1
∨ ¬x
2
∨ x
3
)
(x
1
∨ ¬x
2
∨ x
3
) ∧ (¬x
1
∨ ¬x
3
) ∧ ¬x
1
(x
1
∧ ¬x
2
∧ x
3
)
(x
1
∧ ¬x
2
∧ x
3
) ∨ (¬x
1
∧ ¬x
3
) ∨ ¬x
1
x
i
¬x
i
(x
1
∨ ¬x
2
∨ x
3
)
(x
1
∨ ¬x
2
∨ x
3
) ∧ (¬x
1
∨ ¬x
3
) ∧ ¬x
1
(x
1
∧ ¬x
2
∧ x
3
)
(x
1
∧ ¬x
2
∧ x
3
) ∨ (¬x
1
∧ ¬x
3
) ∨ ¬x
1
f (x
1
, x
2
, x
3
)
x
1
x
2
x
3
f (x
1
, x
2
, x
3
)
(¬x
1
∧ ¬x
2
∧ ¬x
3
)∨
(¬x
1
∧ ¬x
2
∧ x
3
)∨
(x
1
∧ ¬x
2
∧ ¬x
3
)
(x
1
∨ ¬x
2
∨ x
3
)∧
(x
1
∨ ¬x
2
∨ ¬x
3
)∧
(¬x
1
∨ x
2
∨ ¬x
3
)∧
(¬x
1
∨ ¬x
2
∨ x
3
)∧
(¬x
1
∨ ¬x
2
∨ ¬x
3
)
f (x
1
, x
2
, x
3
)
x
1
x
2
x
3
f (x
1
, x
2
, x
3
)
(¬x
1
∧ ¬x
2
∧ ¬x
3
)∨
(¬x
1
∧ ¬x
2
∧ x
3
)∨
(x
1
∧ ¬x
2
∧ ¬x
3
)
(x
1
∨ ¬x
2
∨ x
3
)∧
(x
1
∨ ¬x
2
∨ ¬x
3
)∧
(¬x
1
∨ x
2
∨ ¬x
3
)∧
(¬x
1
∨ ¬x
2
∨ x
3
)∧
(¬x
1
∨ ¬x
2
∨ ¬x
3
)
•
¬(A ∨ B) (¬A ∧ ¬B)
•
¬(A ∧ B) (¬A ∨ ¬B)
¬((l
1,1
∧ l
1,2
∧ · · · ∧ l
1,n
1
) ∨ (l
2,1
∧ l
2,2
∧ · · · ∧ l
2,n
2
) ∨ . . .
∨(l
k,1
∧ l
k,2
∧ · · · ∧ l
k,n
k
))
(¬l
1,1
∨ ¬l
1,2
∨ · · · ∨ ¬l
1,n
1
) ∧ (¬l
2,1
∨ ¬l
2,2
∧ · · · ∨ ¬l
2,n
2
) ∧ . . .
∧(¬l
k,1
∨ ¬l
k,2
∨ · · · ∨ ¬l
k,n
k
)
•
¬(A ∨ B) (¬A ∧ ¬B)
•
¬(A ∧ B) (¬A ∨ ¬B)
¬((l
1,1
∧ l
1,2
∧ · · · ∧ l
1,n
1
) ∨ (l
2,1
∧ l
2,2
∧ · · · ∧ l
2,n
2
) ∨ . . .
∨(l
k,1
∧ l
k,2
∧ · · · ∧ l
k,n
k
))
(¬l
1,1
∨ ¬l
1,2
∨ · · · ∨ ¬l
1,n
1
) ∧ (¬l
2,1
∨ ¬l
2,2
∧ · · · ∨ ¬l
2,n
2
) ∧ . . .
∧(¬l
k,1
∨ ¬l
k,2
∨ · · · ∨ ¬l
k,n
k
)
1
0
1
0
1
0
1
0