Лекции - Машины Тьюринга. Основы теории вычислимости. Булевы функции и пропозициональные формулы
Подождите немного. Документ загружается.
1
0
1
0
•
NP
•
•
•
NP
•
NP
•
•
•
NP
•
NP
•
•
•
NP
•
NP
•
•
•
NP
•
A → B ¬A ∨ B
•
•
A ∧ (C ∨ D) = A ∧ C ∨ A ∧ D
•
((A ∨ C ) → B) ∧ (A ∨ C )
(¬(A ∨ C ) ∨ B) ∧ (A ∨ C )
((¬A ∧ ¬C ) ∨ B) ∧ (A ∨ C )
(¬A ∧ ¬C ∧ A) ∨ (¬A ∧ ¬C ∧ C ) ∨ (B ∧ A) ∨ (B ∧ C )
(B ∧ A) ∨ (B ∧ C )
•
A → B ¬A ∨ B
•
•
A ∧ (C ∨ D) = A ∧ C ∨ A ∧ D
•
((A ∨ C ) → B) ∧ (A ∨ C )
(¬(A ∨ C ) ∨ B) ∧ (A ∨ C )
((¬A ∧ ¬C ) ∨ B) ∧ (A ∨ C )
(¬A ∧ ¬C ∧ A) ∨ (¬A ∧ ¬C ∧ C ) ∨ (B ∧ A) ∨ (B ∧ C )
(B ∧ A) ∨ (B ∧ C )
•
A → B ¬A ∨ B
•
•
A ∧ (C ∨ D) = A ∧ C ∨ A ∧ D
•
((A ∨ C ) → B) ∧ (A ∨ C )
(¬(A ∨ C ) ∨ B) ∧ (A ∨ C )
((¬A ∧ ¬C ) ∨ B) ∧ (A ∨ C )
(¬A ∧ ¬C ∧ A) ∨ (¬A ∧ ¬C ∧ C ) ∨ (B ∧ A) ∨ (B ∧ C )
(B ∧ A) ∨ (B ∧ C )
•
A → B ¬A ∨ B
•
•
A ∧ (C ∨ D) = A ∧ C ∨ A ∧ D
•
((A ∨ C ) → B) ∧ (A ∨ C )
(¬(A ∨ C ) ∨ B) ∧ (A ∨ C )
((¬A ∧ ¬C ) ∨ B) ∧ (A ∨ C )
(¬A ∧ ¬C ∧ A) ∨ (¬A ∧ ¬C ∧ C ) ∨ (B ∧ A) ∨ (B ∧ C )
(B ∧ A) ∨ (B ∧ C )
•
A → B ¬A ∨ B
•
•
A ∧ (C ∨ D) = A ∧ C ∨ A ∧ D
•
((A ∨ C ) → B) ∧ (A ∨ C )
(¬(A ∨ C ) ∨ B) ∧ (A ∨ C )
((¬A ∧ ¬C ) ∨ B) ∧ (A ∨ C )
(¬A ∧ ¬C ∧ A) ∨ (¬A ∧ ¬C ∧ C ) ∨ (B ∧ A) ∨ (B ∧ C )
(B ∧ A) ∨ (B ∧ C )