Логические законы и правила преобразования логических выражений

Если две формулы А и В одновременно, то есть при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными.

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

1. Закон двойного отрицания: ;

2. Переместительный (коммутативный) закон:

• для логического сложения:  ;

• для логического умножения: ;

3. Сочетательный (ассоциативный) закон:

• для логического сложения:  ;

• для логического умножения:   ;

4. Распределительный (дистрибутивный) закон:

• для логического сложения:  ;

• для логического умножения:  ;

5. Законы де Моргана:

• для логического сложения:  ;

• для логического умножения:  ;

6. Закон идемпотентности:

• для логического сложения:  ;

• для логического умножения:  ;

7. Законы исключения констант:

• для логического сложения: ;

• для логического умножения: ;

8. Закон противоречия:;

9. Закон исключения третьего:  ;

10. Закон поглощения:

• для логического сложения: ;

• для логического умножения: ;

11. Правило исключения импликации: ;

12. Правило исключения эквиваленции: .

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

Основываясь на законах, можно выполнять упрощение сложных логических выражений. Такой процесс замены сложной логической функции более простой, но равносильной ей, называется минимизацией функции.

Пример. Упростить логическое выражение .

Решение:

Согласно закону де Моргана:

.

Согласно сочетательному закону:

.

Согласно закону противоречия и закону идемпотентности:

.

Согласно закону исключения 0:

 

Окончательно получаем

/ Задания к лабораторной работе

Пример 1. Установите, какие из следующих предложений являются логическими высказываниями, а какие — нет (объясните почему):

• а) “Солнце есть спутник Земли”;

• б) “2+3=4”;

• в) “сегодня отличная погода”;

• г) “в романе Л.Н. Толстого “Война и мир” 3 432 536 слов”;

• д) “Санкт-Петербург расположен на Неве”;

• е) “музыка Баха слишком сложна”;

• ж) “первая космическая скорость равна 7.8 км/сек”;

• з) “железо — металл”;

• и) “если один угол в треугольнике прямой, то треугольник будет тупоугольным”;

• к) “если сумма квадратов двух сторон треугольника равна квадрату третьей, то он прямоугольный”.

Пример 2. Укажите, какие из высказываний предыдущего упражнения истинны, какие — ложны, а какие относятся к числу тех, истинность которых трудно или невозможно установить.

Пример 3. Приведите примеры истинных и ложных высказываний:

• а) из арифметики;   б) из физики;

• в) из биологии;   г) из информатики;

• д) из геометрии;   е) из жизни.

Пример 4. Сформулируйте отрицания следующих высказываний или высказывательных форм:

• а) “Эльбрус — высочайшая горная вершина Европы”;

• б) “2>=5”;

• в) “10<7”;

• г) “все натуральные числа целые”;

• д) “через любые три точки на плоскости можно провести окружность”;

• е) “теннисист Кафельников не проиграл финальную игру”;

• ж) “мишень поражена первым выстрелом”;

• з) “это утро ясное и теплое”;

• и) “число n делится на 2 или на 3”;

• к) “этот треугольник равнобедренный и прямоугольный”;

• л) "на контрольной работе каждый ученик писал своей ручкой".

Пример 5. Определите, какие из высказываний (высказывательных форм) в следующих парах являются отрицаниями друг друга, а какие нет:

• а) “5<10”, “5>10”;

• б) “10>9”, “10<=9”;

• в) “мишень поражена первым выстрелом”, “мишень поражена вторым выстрелом”;

• г) “машина останавливалась у каждого из двух светофоров”, “машина не останавливалась у каждого из двух светофоров”,

• д) “человечеству известны все планеты Солнечной системы”, “в Солнечной системе есть планеты, неизвестные человечеству”;

• е) “существуют белые слоны”, “все слоны серые”;

• ж) “кит — млекопитающее”, “кит — рыба”;

• з) “неверно, что точка А не лежит на прямой а”, “точка А лежит на прямой а”;

• и) “прямая а параллельна прямой b”, “прямая a перпендикулярна прямой b”;

• к) “этот треугольник равнобедренный и прямоугольный”, “этот треугольник не равнобедренный или он не прямоугольный”.

Пример 6. Формализуйте предостережение, которое одна жительница древних Афин сделала своему сыну, собиравшемуся заняться политической деятельностью: “Если ты будешь говорить правду, то тебя возненавидят люди. Если ты будешь лгать, то тебя возненавидят боги. Но ты должен говорить правду или лгать. Значит, тебя возненавидят люди или возненавидят боги”.

Формализуйте также ответ сына: “Если я буду говорить правду, то боги будут любить меня. Если я буду лгать, то люди будут любить меня. Но я должен говорить правду или лгать. Значит, меня будут любить боги или меня будут любить люди”.

Пример 7. Пусть a = “это утро ясное”, а b = “это утро теплое”. Выразите следующие формулы на обычном языке:

Пример 8. Из двух данных высказываний a и b постройте составное высказывание, которое было бы:

а) истинно тогда и только тогда, когда оба данных выказывания ложны;

б) ложно тогда и только тогда, когда оба данных высказывания истинны.

Пример 9. Из трех данных высказываний a, b, c постройте составное высказывание, которое истинно, когда истинно какое-либо одно из данных высказываний, и только в этом случае.

Пример 10. Найдите значения логических выражений:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) ;

з) ;

Пример 11.  Даны простые высказывания:

А = {Принтер — устройство ввода информации},

В = {Процессор — устройство обработки информации},

С = {Монитор — устройство хранения информации},

D = {Клавиатура — устройство ввода информации}.

Определите истинность составных высказываний:

a) (A&B)&(CvD);     б) (А&В)=>(В&С); в) (AvB) ↔ (C&2>);   г) А↔ В.

Пример 12. Определите с помощью таблиц истинности, какие из следующих формул являются тождественно истинными или тождественно ложными:

а) д)

б) е)

в) ж)

г)

Индивидуальные задания к лабораторной работе "Алгебра логики"

Составить таблицу истинности логического выражения C.

Варианты задания:

 2. Построить логическую схему функции F(A,B).

Варианты задания:

3. Упростить логическое выражение D.

Варианты задания:

4. Определить, являются ли два высказывания эквивалентными.

Варианты задания:

5. Определить истинность или ложность высказываний.

Варианты задания:

№ варианта
1	(X>4) v ¬(X>1) v (X>4) при X=1
2	X>1 & (¬(X<5) v (X<3)) при X=2
3	¬((X>3) v (X<3)) v (X<1) при X=3
4	(X>4) v ¬(X>1) v (X>4) при X=4
5	(¬(X<5) v (X<3)) & (¬(X<2) v (X<1)) при X=1
6	¬(¬(X>2) v (X>3)) при X=2
7	(X>4) v ¬(X>1) v (X>4) при X=3
8	¬((X>2) v (X<2)) v (X>4) при X=4
9	(X>4) v ¬(X>1) v (X>4) при X=1
10	¬((X>3) v (X<3)) v (X<1) при X=2
11	(¬(X<5) v (X<3)) & (¬(X<2) v (X<1) при X=3
12	X>1 & (¬(X<5) v (X<3)) при X=4
13	¬((X>2) v (X<2)) v (X>4) при X=1
14	X>1 & (¬(X<5) v (X<3)) при X=2
15	¬(¬(X>2) v (X>3)) при X=3
16	¬((X>3) v (X<3)) v (X<1) при X=4

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

1. Текст задания (с данными своего варианта).

2. Представление по каждому пункту задания подробного решения.

Вопросы для защиты работы

1. Что такое высказывание (приведите пример)? 

2. Что такое составное высказывание (приведите пример)? 

3. Как называются и как обозначаются (в языке математики) следующие операции: ИЛИ, НЕ, И, ЕСЛИ … ТО, ТОГДА И ТОЛЬКО ТОГДА, ЛИБО …ЛИБО?

4. Укажите приоритеты выполнения логических операций.

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

6. Изобразите функциональные элементы: конъюнктор, дизъюнктор, инвертор.

7. Какие логические выражения называются равносильными?

8. Записать основные законы алгебры логики.