Основные законы, определяющие свойства логических операций

 

1) Идемпотентность дизъюнкции и конъюнкции:

,                                   .

 

2) Коммутативность дизъюнкции и конъюнкции:

,                                 .

 

3) Ассоциативность дизъюнкции и конъюнкции:

,                        .

 

4) Дистрибутивность операций дизъюнкции и конъюнкции относительно друг друга:

,                .

 

5) Двойное отрицание:

.

 

6) Закон де Моргана:

,                 .

 

7) Склеивание:

,             .

 

8) Поглощение:

,              .

 

9) Действия с логическими константами 0 и 1:

,         ,          ,       ,      .

 

 

10) Закон исключенного третьего:

.

 

11) Тождество:

.

 

12) Отрицание противоречия:

.

13) Контрапозиция:

.

 

Сформулированные законы легко проверить с помощью таблиц истинности.

При исследовании различных высказываний на эквивалентность(равносильность) логическую связку «можно заменить обычным знаком равенства =.

 

Пример 1. Доказать равносильность, используя основные законы логических операций:

 = .

Решение.

1. Используя законы де Моргана  и , получим:

= = .

2. Используя закон двойного отрицания , получаем:

= .

3. Применяя дистрибутивный закон , получаем

= = )) .

4. Ассоциативность дизъюнкции:  позволяет упростить последнее выражение:

)) = .

5. Учитывая законы, включающие тождественно ложные высказывания, окончательно получаем:

= .

 

 

Работу составила преподаватель                  Т.С. Пронина

                           Практическое занятие №5

1 Наименование: Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний. Двойственность.

2 Цель: Научиться представлять булевы функции в дизъюнктивной и конъюнктивной нормальных формах, находить функции двойственные заданным, а также самодвойственные.

Формирование ОК 2,3,8; овладение знаниями и умениями, необходимыми для освоения ПК 2.4. (спец. 09.02.03.), ПК 1.4, 2.4. (спец. 09.02.04.).

3 Подготовка к занятию: Повторить тему: Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний. Двойственность.

4 Литература:

4.1 Конспект лекций по учебной дисциплине «Элементы математической логики», 2016

4.2 Приложение к ПЗ №5.

5 Перечень используемых материалов:

5.1 Бланк для отчета.

5.2 Канцелярские принадлежности.

6 Задание на занятие:

Основная часть

6.1 Постройте КНФ и ДНФ функций и докажите их тождественность с помощью построения таблиц истинности.

а) f (x, y, z) =

б) f (x₁, x₂, x₃, x₄) =

6.2 Приведите к ДНФ и КНФ функцию f= (x Å y) z

6.3 Найдите двойственные функции для булевых функций двух переменных. Перечислите самодвойственные функции.

 

f₁ (x, y) = 0

f₂ (x, y) =

f₃ (x, y) =

f₄ (x, y) = x

f₅ (x, y) =

f₆ (x, y) = y

f₇ (x, y) =

f₈ (x, y) =

 

f₉ (x, y) =

f₁₀ (x, y) =

f₁₁(x, y) =

f₁₂ (x, y) =

f₁₃ (x, y) =

f₁₄ (x, y) =

f₁₅ (x, y) =

f₁₆ (x, y)

6.4 Перейдите от ДНФ к КНФ, используя законы двойственности, если

f (x, y, z) =

 

Вариативная часть

6.5 Приведите к ДНФ и КНФ функции:

а)  

б)

в)

7 Порядок выполнения работы:

Выполните практическую работу в соответствии с заданием (основная часть п.п. 6.1 – 6.4) и сдайте зачет. В случае получения зачета, выполните вариативную часть (п. 6.5).

8 Содержание отчета:

Решения задач в соответствии с заданием.

 

9 Контрольные вопросы:

1 Что называется булевой функцией?

2 Какая функция называется двойственной, самодвойственной?

3 Приведите определение ДНФ и КНФ.

4 Какова процедура приведения функции к ДНФ

Приложение к практическому занятию по ЭМЛ № 5