48. Совершенная конъюнктивная нормальная форма

формула  , где всеD_iявляются основными элементарными дизъюнкциями

49. Алгоритм построения скнф

СКНФ функции f содержит ровно столько дизъюнкций, сколько нулей в таблице истинности f. Каждому “нулевому” набору (d ₁,…,d _n) значений переменных, т.е. набору, на котором значение функции равно 0, соответствует дизъюнкция всех переменных, в которых x_i взято с отрицанием, если d _i =1 и без отрицания, если d _i =0.

Пример. Записать СКНФ для функции. 

x1 x2	x1x2	Основная элементарная дизъюнкция
0 0	1
0 1	1
1 0	0	x2
1 1	1

.

50. Ассоциативность логических операций

х₁(х₂ х₃) = (х₁х₂)х₃;

х₁ (х₂ х₃) = (х₁ х₂)  х₃

51. Коммутативность логических операций

х₁ х₂ = х₂ х_1; х₁ х₂ = х₂ х₁

52. Дистрибутивность логических операций

Дистрибутивность конъюнкции относительно дизъюнкции

х₁ (х₂ х₃) = х₁х₂ х₁х₃.

Дистрибутивность дизъюнкции относительно конъюнкции

х₁(х₂ х₃) = (х₁х₂)  (х₁х₃).^

53. Законы идемпотентности (тавтологии)

x & x = x

x  x = x

54. Законы универсального и нулевого множества

55. Правила (законы) де Моргана

56. Закон дополнительности

x x = 0;

57. Элементарная дизъюнкция

Дизъюнкция любого числа переменных из конечного набора n переменных называется элементарной, когда в нее входят либо переменные, либо их отрицания. Например, сумма x₃ v x₂ v x₁ vx₀ является элементарной, а x ₁ x₂+x₀; x ₃ + x ₂ x₁ +x₀ нет.

58. Элементарная конъюнкция

Конъюнкция любого числа переменных из конечного набора n переменных называется элементарной, когда в нее входят либо переменные, либо их отрицания. Например, x₃x₂x₁ x₀ является элементарной,

  _

а (x₃ v x₂)x₀, x₃ x₂ x₁ x₀ не являются элементарными.

59. Ранг элементарной дизъюнкции(конъюнкции)

Рангом дизъюнкции (конъюнкции) называется количество ее операндов.

60. Конституента нуля

Элементарная дизъюнкция всех n переменных называется конституентой нуля.

61. Конституента единицы

Элементарная конъюнкция всех n переменных называется конституентой единицы.

62. Соседние элементарные дизъюнкции (конъюнкции)

Две элементарные дизъюнкции (конъюнкции) одинакового ранга r называются соседними, если они являются функциями одних и тех же переменных и отличаются только знаком инверсии лишь у одной переменной. Например, суммы x₂ v x₁ vx₀ и x₂ v x₁ vx₀ являются соседними, а x₂ v x₁ vx₀ и x₂ vx₁ v x₀ нет.

63. Правило склеивания

Правило склеивания для элементарных конъюнкций следует из распределительного закона, закона дополнительности и закона универсального множества: дизъюнкцию двух соседних конъюнкций можно заменить одной элементарной конъюнкцией, являющейся общей частью исходных конъюнкций.

64. Правило поглощения

Правило поглощения для суммы двух элементарных произведений следует из распределительного закона первого рода и законов универсального множества: дизъюнкцию двух элементарных конъюнкций, из которых одна является составной частью другой, можно заменить конъюнкцией, имеющей меньшее количество операндов.

65. Правило развертывания