Шпаргалка по "Программированию и компьютерам"

 9) Свойство  единицы: A & 1 º A; A Ú 1 º 1;

 10) Закон  противоречия: A & ØA º 0;

 11) Закон  исключённого третьего: A Ú ØA º 1;

 12) Закон снятия двойного отрицания: ØØA º A.

 Дополнительные  равносильности:

 1) x↔y ≡ (x→y)& (y→x)

 2) x→y ≡ ØxÚy

 3) Ø(x&y) ≡ ØxÚØy

 4) Ø(xÚy) ≡ Øx&Øy

 5) x&y ≡ Ø (ØxÚØy)

 6) xÚy ≡ Ø (Øx&ÚØy)

 7) Øx ≡ x|x

 8) x&y ≡ (x|y)| (x|y)

 9)x|y ≡ Ø(x&y) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

5. Нормальные формы формул. Представление логической функции в виде формулы алгебры логики.

Нормальные  формы формул

• Дизъюнктивная нормальная форма (ДНФ)

Формула называется элементарной конъюнкцией, если она  представляет собой конъюнкцию (возможно, одночленную) переменных или их отрицаний. Пример: (Øx₁ & Øx₂ & x₃). Формула находится в ДНФ, если она представляет собой дизъюнкцию (возможно, одночленную) элементарных конъюнкций. Пример: (Øx₁ & Øx₂) Ú (x₂ & x₃). Для любой формулы алгебры логики может быть построена равносильная ей формула, находящаяся в ДНФ.

• Конъюнктивная нормальная форма (КНФ)

Формула называется элементарной дизъюнкцией, если она  представляет собой дизъюнкцию (возможно, одночленную) переменных или их отрицаний. Пример: (Øx₁ Ú Øx₂ Ú x₃). Формула находится в КНФ, если она представляет собой конъюнкцию (возможно, одночленную) элементарных дизъюнкций. Пример: (Øx₁ Ú Øx₂) & (x₂ Ú x₃). Для любой формулы алгебры логики может быть построена равносильная ей формула, находящаяся в КНФ.

• Совершенная дизъюнктивная нормальная форма (СДНФ)

Формула находится  в СДНФ, если:

1) она находится  в ДНФ;

2) в каждую  элементарную конъюнкцию входят  все переменные или их отрицания,  причём на i-ой позиции находится x_i или Øx_i;

3)  все дизъюнктивные  члены различны.

Пример: (Øx₁ & x₂ & x₃) Ú (x₁ & Øx₂ & x₃).

СДНФ формулы  определяется однозначно с точностью  до порядка дизъюнктивных членов (теорема о единственности СДНФ).

• Совершенная конъюнктивная нормальная форма (СКНФ)

Формула находится  в СКНФ, если:

1) она находится в КНФ;

2) в каждую  элементарную дизъюнкцию входят  все переменные или их отрицания,  причём на i-ой позиции находится x_i или Øx_i;

3)  все конъюнктивные  члены различны.

Пример: (Øx₁ Ú x₂ Ú x₃) & (x₁ Ú Øx₂ Ú x₃).

СКНФ формулы  определяется однозначно с точностью до порядка конъюнктивных членов (теорема о единственности СКНФ).

Представление логической функции  в виде формулы  алгебры логики

• Первая теорема Шеннона о представлении булевой функции.

Пусть рассматривается  k-местная функция f (x₁, …, x_k), не равная тождественно 0. Тогда существует формула алгебры логики F, определяющая функцию f и находящаяся в СДНФ. Формула F определяется однозначно с точностью до порядка дизъюнктивных членов.

Пусть x¹ = x, x⁰ = Øx. Тогда F = Ú (x₁^s1 & … & x_k^sk) для всех (s₁, …, s_k), для которых f (s₁, …, s_k) = 1.

• Вторая теорема Шеннона о представлении булевой функции.

Пусть рассматривается  k-местная функция f (x₁, …, x_k), не равная тождественно 1. Тогда существует формула алгебры логики F, определяющая функцию f и находящаяся в СКНФ. Формула F определяется однозначно с точностью до порядка конъюнктивных членов.

Пусть x¹ = x, x⁰ = Øx. Тогда F = & (x₁^Øs1 Ú … Ú x_k^Øsk) для всех (s₁, …, s_k), для которых f (s₁, …, s_k) = 0.