Логические операции Применение двоичной системы счисления дает возможность использовать аппарат математической логики, в частности исчисление высказываний. - презентация

1 Логические операции Применение двоичной системы счисления дает возможность использовать аппарат математической логики, в частности исчисление высказываний. В математической логике под высказыванием понимается любое предложение, относительно которого имеет смысл говорить об его истинности или ложности. Предложения которые могут быть одновременно истинными и ложными или частично истинными, в математической логике не рассматриваются.

2 При оценке высказываний мы будем принимать во внимание лишь их истинность или ложность, никак не учитывая их конкретного содержания Высказывания будем обозначать заглавными буквами латинского алфавита Если A истинно, то будем писать A=1, если ложно A=0

3 Математическая логика изучает вопросы представления и преобразования двоичных функций от двоичных аргументов посредством некоторых логических операций, называемыми логическими связями Из простых выражений посредством логических связей могут быть составлены сложные высказывания, принимающие значения истинно (1) или ложно (0) в зависимости от значения составляющих простых высказываний Так как высказывания можно рассматривать как двоичные переменные, то логические связи между высказываниями можно представить как операции над двоичными переменными величинами Определим основные логические операции

4 1. Отрицание (унарная) _ А - читается не A (обозначается ¬ A) (в С - !A) результат Операция отрицание называется также инверсией, логическим НЕ Отрицание высказывания А является высказывание, которое ложно, когда А истинно, и истинно, когда А ложно

5 2. Логическое умножение А B - читается A и B (обозначается A /\ B) (в С - A & B ) результат 0 /\ 0 = 0 0 /\ 1 = 0 1 /\ 0 = 0 1 /\ 1 = 1 Операция логического умножения называется конъюнкцией, или логическим И, логическим умножением. Конъюнкция двух высказываний представляет собой сложное высказывание, которое истинно тогда и только тогда, когда истинны оба составляющих его высказывания.

6 3. Логическое сложение А B - читается A и B (обозначается A \/ B) (в С - A | B ) результат 0 \/ 0 = 0 0 \/ 1 = 1 1 \/ 0 = 1 1 \/ 1 = 1 Операция логического сложения называется дизъюнкцией, логическим ИЛИ, логическим сложением. Дизъюнкция двух высказываний представляет собой сложное высказывание, которое ложно, тогда и только тогда, когда оба слагаемых ложно

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

8 4. Следование (импликация) А B - обозначается A B результат 0 0 = = = = 1 Импликация как булева функция ложна лишь тогда, когда посылка истинна, а следствие ложно. Операция A B определяет логическую функцию, тождественно совпадающую с функцией ¬ A \/ B. Modus ponens

9 5. Равнозначность (эквивалентность) А B - читается A равнозначно B результат 0 0 = = = = 1 Равнозначность двух высказываний представляет собой сложное высказывание, которое истинно, когда оба его составляющих имеют одинаковой значение истинности и ложна в противоположном случае

10 6. Сложение по модулю 2 А B - (в С - A ^ B ) результат 0 0 = = = = 0 Операция сложения по модулю 2 выражается через операции равнозначности и отрицания по формуле _____ A B = A B

11 Приоритеты логических операций Инверсия (отрицание) Конъюнкция (логическое умножение) Дизъюнкция (логическое сложение) Импликация (следование) Таким образом: ¬ A /\ B \/ C /\ D То же самое ((¬ A) /\ B) \/ (C /\ D)

12 Для логических операций выполняется коммутативность и ассоциативность Проверить следующие формулы (вместо звездочки произвольная операция). Проверка осуществляется подстановкой переменных значений 0 или 1 в различных комбинациях и применением таблиц, определяющих эти операции A * B = B *A Коммутативность (A * B) * C = A *(B*C) Ассоциативность Например: A /\ (B \/ C) = ( A /\ B ) \/ (A /\ C)

13 Табличный способ определения истинности сложного выражения имеет ограниченное применение, так как при увеличении числа логических переменных приходится перебирать слишком много вариантов. В таких случаях используют способ приведения формул к нормальной форме. Формула имеет нормальную форму, если в ней отсутствуют знаки эквивалентности, импликации и двойного отрицания, а все знаки отрицания относятся только к переменным, а не к выражениям.

14 Следующие формулы преобразований дополняют сформулированные выше законы булевой алгебры и позволяют приводить формулы к нормальной форме. ¬ ( ¬ A) = A ¬ (A & B) = ¬ A | ¬ B ¬ (A | B) = ¬ A & ¬ B ¬ (A B) = A & ¬ B A B = ¬ A | B A B = (A & B) | ( ¬ A & ¬ B) =( ¬ A | B) & (A | ¬ B)

15 Знание законов математической логики позволяет решать так называемые логические задачи, возникающие в различных жизненных ситуациях. Воспользуемся исчислением высказываний для решения следующих двух задач. Задача 1. Следователь допрашивал четырех гангстеров по делу о похищении автомобиля. Джек сказал: "Если Том не угонял автомобиля, то его угнал Боб". Боб сказал: "Если Джек не угонял автомобиля, то его угнал Том". Фред сказал: "Если Том не угонял автомобиля, то его угнал Джек". Том сказал: "Если Боб не угонял автомобиля, то его угнал я". Удалось выяснить, что Боб солгал, а Том сказал правду. Правдивы ли показания Джека и Фреда? Кто угнал машину?

A = !( !B) |" title="Решение: Определим следующие простые высказывания: А - "машину угнал Боб"; В - "машину угнал Том"; С - "машину угнал Джек"; D - "машину угнал Фред". Запишем (и сразу упростим) сложные высказывания, выражающие приведенные факты: (1) !B -> A = !( !B) |" class="link_thumb"> 16 Решение: Определим следующие простые высказывания: А - "машину угнал Боб"; В - "машину угнал Том"; С - "машину угнал Джек"; D - "машину угнал Фред". Запишем (и сразу упростим) сложные высказывания, выражающие приведенные факты: (1) !B -> A = !( !B) | A = B | A (истинность неизвестна); (2) !C -> B = !( !C) | B = C | B = F (высказывание ложно); (3) !B -> C = !( !B) | C = B | C = C | B (истинность неизвестна); (4) !A -> B = !( !A) | B = A | B = T (высказывание истинно). Заметим, что после упрощения высказывание (3) совпало с высказыванием (2), которое ложно. Таким образом, высказывание (3), произнесенное Фредом, также ложно. Из ложности высказывания (2) следует ложность каждого дизъюнкта, входящего в него, т. е. C = F и B = F. Подставив найденное значение B в высказывание (4) получаем A || B = A || F = T, что возможно лишь если A = T, т. е. машину угнал Боб. Рассмотрим высказывание Джека (1): B | A = F | T = T - оно истинно. Итак, Джек сказал правду, а Фред соврал. Машину угнал Боб. A = !( !B) |"> A = !( !B) | A = B | A (истинность неизвестна); (2) !C -> B = !( !C) | B = C | B = F (высказывание ложно); (3) !B -> C = !( !B) | C = B | C = C | B (истинность неизвестна); (4) !A -> B = !( !A) | B = A | B = T (высказывание истинно). Заметим, что после упрощения высказывание (3) совпало с высказыванием (2), которое ложно. Таким образом, высказывание (3), произнесенное Фредом, также ложно. Из ложности высказывания (2) следует ложность каждого дизъюнкта, входящего в него, т. е. C = F и B = F. Подставив найденное значение B в высказывание (4) получаем A || B = A || F = T, что возможно лишь если A = T, т. е. машину угнал Боб. Рассмотрим высказывание Джека (1): B | A = F | T = T - оно истинно. Итак, Джек сказал правду, а Фред соврал. Машину угнал Боб."> A = !( !B) |" title="Решение: Определим следующие простые высказывания: А - "машину угнал Боб"; В - "машину угнал Том"; С - "машину угнал Джек"; D - "машину угнал Фред". Запишем (и сразу упростим) сложные высказывания, выражающие приведенные факты: (1) !B -> A = !( !B) |">

17 Пример Кто из людей A, B, C и D играет, а кто не играет в шахматы, если известно следующее: а) если А или В играет, то С не играет; б) если В не играет, то играют С и D; в) С играет. Решение Определим следующие простые высказывания: А - "А играет в шахматы"; В - "В играет в шахматы"; С - "С играет в шахматы"; D - "D играет в шахматы".

18 Запишем сложные высказывания, выражающие известные факты: a) (A & B) -> !C; б) !B -> C & D; в) C Запишем произведение (конъюнкцию) указанных сложных высказываний. Так как все они истинны, то и произведение тоже истинно: ((A | B) -> !C) & ( !B -> C & D) & C = T. Упростив эту формулу, получим !A & !B & C & D = T. Отсюда по свойствам конъюнкции получаем, A = F, B = F, C = T, D = T. Значит, в шахматы играют C и D, а A и B - не играют.

19 Во многих задачах, связанных с обработкой данных, приходится упрощать логические выражения. Приведем пример, демонстрирующий технику упрощения логических формул. Упростим логическую формулу !( (A || B) -> !( B || C)). Решение !( (A | B) -> !( B | C)) = !( !(A | B) | !( B | C)) = !( !(A | B)) & !( !( B | C)) = (A | B) & (B | C) = { дистрибутивность операции ИЛИ } (A | B) & B | ( A | B) & C = A & B | B | A & C | B & C = B & (A | T) | C & (A & B) = B | A & C | B & C = B & (T | C) | A & C = B | A & C.

20 6. Стрелка Пирса Стрелка Пирса (символ Лукашевича) двуместная логическая операция, введена в рассмотрение Ч. Пирсом (Сh. Peirce). Стрелка Пирса, обычно обозначаемая, задаётся следующей таблицей истинности: результат 0 0 = = = = 0 Таким образом, высказывание A B означает «ни A, ни B».

21 Стрелка Пирса обладает тем свойством, что через неё одну выражаются все другие логические операции. Например, высказывание ¬A (отрицание A) эквивалентно высказыванию AA, конъюнкция A /\ B выражается так: (A A) (B B), дизъюнкция A \/ B эквивалентна (A B) (A B).

22 Логические операторы в C

23 2. операции отношения == != = Отношения имеют приоритет ниже арифметических. i < lim-1; Вычисляется как i < (lim-1); Пример: год будет високосным, если он делится на 4, но не делится на 100, однако годы делящиеся на 400 тоже високосные if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) год високосный; else год невисокосный ;

24 Результатом всякой операции отношения является числовое значение типа int, равное единице, если сравнение истинно, и нулю в противном случае Таким образом, операции отношения во внутреннем машинном представлении приводят к арифметическому результату Замечание. Строго говоря, логическое значение "истина" должно отвечать любому числовому значению, отличному от нуля. В дальнейшем мы увидим, что именно такое соглашение принято в языке Си. Это дает возможность объединить понятия арифметического, условного и логического выражений в едином понятии "выражение", что очень важно с точки зрения гибкости и "симметричности" языка Выражения, сконструированные при помощи операций отношения, принято называть условными выражениями

25 3. логические связки ! || && Приоритет ниже, чем у операций отношения Выражения с && и || вычисляются слева направо и вычисления заканчиваются, когда определяется истинность или ложность результата for (i=0; i

26 4. побитовые операции ~ > & | ^ Операции для работы с разрядами. Их нельзя применять к float и double & - поразрядное И. c = m & 0177; - Устанавливает в 0 все разряды, кроме младших семи | - поразрядное ИЛИ x =x | MASK ; - Устанавливает в 1 те разряды x, которым соответствует 1 в MASK ^ - исключающее ИЛИ. Результат содержит 1 в тех разрядах в которых разные значения, 0 в остальных.

27 > - сдвиг влево, сдвиг вправо. x=x2; // сдвигает x вправо на два разряда. На некоторых машинах приводит к размножению знакового разряда ~ - унарная операция дополнение до 1. 1 где 0 и 0 где 1. x =x & ~077; // - Устанавливает в 0 6 разрядов x.