Логика и логические операции

Термин «логика» происходит от древнегреческого logos – «слово, мысль, понятие, рассуждение, закон». Логика является одной из дисциплин, образующих математический фундамент информатики. В вычислительной технике и автоматике используются логические схемы – устройства, которые преобразуют двоичные сигналы. Анализ и проектирование логических схем опираются на законы алгебры логики. Любой язык программирования содержит логические переменные и средства для описания и вычисления логических выражений. Логические методы применяются и при работе с базами данных.

Логика – это наука о правильном мышлении, наука о законах и формах мышления. Она изучает абстрактное мышление как средство познания объективного мира.

Этапы развития логики Первые учения о формах и способах рассуждений возникли в странах Дальнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные древнегреческими мыслителями. Основы формальной логики заложил Аристотель (384–322 гг. до н.э.), который впервые отделил логические формы речи от ее содержания.

В XVII веке немецкий ученый и философ Готфрид Вильгельм Лейбниц (1646 – 1716) попытался построить первые логические исчисления, усовершенствовал и уточнил логические символы. На фундаменте, заложенном Лейбницем, другой великий математик, англичанин Джордж Буль ( ) воздвиг здание новой области науки – математической логики. Начальный раздел математической логики называют алгеброй логики или Булевой алгеброй.

Алгебра логики С точки зрения устройства ЭВМ нас интересует алгебра логики, в которой не рассматривается конкретное содержание основного понятия логики – высказывания, а важно только истинно оно или ложно. Основным объектом в логике является высказывание. Высказывание – это повествовательное предложение, о котором можно сказать истинно оно или ложно. Высказывание называется простым, если никакая его часть сама не является высказыванием. Высказывание называется составным, если оно состоит из простых высказываний, соединенных логическими связками: И, ИЛИ, частицей НЕ

Логические основы компьютеров К. Поляков, Обозначение высказываний A – Сейчас идет дождь. B – Форточка открыта. простые высказывания (элементарные) Составные высказывания строятся из простых с помощью логических связок (операций) «и», «или», «не», «если … то», «тогда и только тогда» и др. Любое высказывание может быть ложно (0) или истинно (1). ! A и B A или не B если A, то B A тогда и только тогда, когда B Сейчас идет дождь и открыта форточка. Сейчас идет дождь или форточка закрыта. Если сейчас идет дождь, то форточка открыта. Дождь идет тогда и только тогда, когда открыта форточка.

Примеры: 1.Москва – столица России 2.Студент математического факультета педагогического университета 3.Треугольник АВС подобен треугольнику АВС 4.Луна есть спутник Марса 5.Кислород – газ 6.Каша – вкусное блюдо 7.Математика – интересный предмет 8.Железо тяжелее свинца 9.Треугольник называется равносторонним, если все его стороны равны 10.Сегодня плохая погода 11.Река Ангара впадает в озеро Байкал Какие из этих предложений являются высказываниями? Ответ: 1, 4, 5, 8, 9, 11

Логические основы компьютеров К. Поляков, Высказывание или нет? Сейчас идет дождь. Жирафы летят на север. История – интересный предмет. У квадрата – 10 сторон и все разные. Красиво! В городе N живут 2 миллиона человек. Который час?

Основные понятия логики: Утверждение – высказывание, которое требуется доказать или опровергнуть. Например: «Сумма внутренних углов треугольника равна » Рассуждение – цепочка высказываний или утверждений, определенным образом связанных друг с другом. Например: «Если хотите начать работать на компьютере, то необходимо сначала включить электропитание» Умозаключение – логическая операция, в результате которой из одного или нескольких данных высказываний получается (выводится) новое высказывание. Например: «Все металлы электропроводны». «Ртуть является металлом». Путем умозаключения можно сделать вывод, что «Ртуть электропроводна». Логическое выражение – запись или устное утверждение, в которое, наряду с постоянными, обязательно входят переменные величины (объекты). Например: (А ۸ (В ۷ С))

Простые высказывания обозначают заглавными латинскими буквами A, B, C…X, Y, Z и называют логическими переменными Значения высказываний ИСТИНА или ЛОЖЬ обозначают соответственно цифрами 1 и 0 и называют логическими величинами Составные высказывания называются логическими выражениями и включают в себя логические переменные, операции логики и скобки для изменения порядка действий операций

Примеры: Рассмотрим следующие высказывания: 1.A = (7 > 3) 2.B = (7 = 3) 3.C = (7 3) 4.D = (B ۸ C) = ((7 = 3) ۸ (7 3)) На языке алгебры логики эти высказывания можно записать так: A = ИСТИНА = 1 B = ЛОЖЬ = 0 C = ИСТИНА = 1 D = ЛОЖЬ = 0

Пример: Пусть дано два утверждения: 1. Фрукты могут расти на деревьях. 2. Яблоко это фрукт. Так как оба эти утверждения истинны, то можно сказать, что утверждение «Яблоки могут расти на деревьях» также истинно. Это третье утверждение никак не содержится в двух первых, оно из них следует. Или, иначе говоря, третье утверждение является логическим выводом из первых двух. Пример решения задачи: Необходимо выяснить: в какой из двух комнат находится принцесса, а в какой тигр. На дверях каждой из комнат есть таблички с некоторыми утверждениями, кроме того, дополнительно известно, что на одной табличке написана правда, а на другой нет, но на какой правда, а на какой ложь не известно. И ещё известно, что в каждой комнате кто-то есть. Таблички содержат следующие надписи: 1. В этой комнате находится принцесса, а в другой комнате сидит тигр. 2. В одной из этих комнат находится принцесса; кроме того, в одной из этих комнат сидит тигр. Решение задачи: Утверждения на табличках не могут быть одновременно истинными или ложными. Следовательно, возможны только две ситуации. Первая: первое истинно, а второе ложно и вторая: первое ложно, а второе истинно. Рассмотрим их. Ситуация 1. Из истинности первого утверждения следует, что принцесса находится в первой комнате, а тигр во второй. В это же время из ложности второго утверждения следует, что нет комнаты, в которой находится принцесса и нет комнаты в которой сидит тигр. Следовательно, истинность первого утверждения и ложность второго невозможны одновременно. Ситуация 2. Из истинности второго утверждения следует только то, что и тигр и принцесса имеются в наличии. Из ложности же первого следует, что принцесса находится во второй комнате, а тигр в первой. Анализируя вторую ситуацию, мы не получили противоречия, следовательно ситуация 2 и есть решение задачи. Решение данной задачи есть пример более сложного рассуждения. Однако нетрудно заметить общий принцип. В этом рассуждении, так же как и в первом примере есть элементарные утверждения из истинности, которых следует истинность или ложность других утверждений. А цель логического вывода как раз и заключается в установлении истинности или ложности различных утверждений.

Логические основы компьютеров К. Поляков, Табличный метод 14 Задача 2. Дочерей Василия Лоханкина зовут Даша, Анфиса и Лариса. У них разные профессии и они живут в разных городах: одна в Ростове, вторая – в Париже и третья – в Москве. Известно, что Даша живет не в Париже, а Лариса – не в Ростове, парижанка – не актриса, в Ростове живет певица, Лариса – не балерина. ПарижРостовМоскваПевицаБалеринаАктриса Даша Анфиса Лариса В каждой строке и в каждом столбце может быть только одна единица! ! Много вариантов. Есть точные данные. Много вариантов. Есть точные данные.

Основные логические операции Логическая операция КОНЪЮНКЦИЯ (логическое умножение) Ставит в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказываний истинны. Легко проверить, что этот результат можно получить «обычным» умножением A на B, поэтому операцию «И» называют логическим умножением. Существует и другое название этой операции – конъюнкция (от латинского conjunctio – союз, связь). Соответствует союзу И Обозначается & или ۸, *, And Диаграммы Эйлера- ВеннаАВ А А ۸ В ×

Примеры: Определить значения истинности следующих высказываний: 1.Ленинград расположен на Неве и = – простое число и 9 – простое число 3.2 * 2 = 4 и 2 * 2 5 и 2 * Москва – столица России и Екатеринбург – столица Сибири 5.Книга – источник информации и 5 не больше 8 6.Девочки обычно любят играть в куклы и Не любая машина - автомобиль 7.Все гуси – птицы и Все игрушки - машины Ответ: истинными высказываниями являются: 1, 3, 5, 6

Из двух простых высказываний постройте сложное и проверьте на истинность, используя логическую связку И Пример: А=«Марс - планета» В=«Число 12 - чётное» АВА&ВА&В Проверьте таблицу истинности на примере АВА&ВА&В

Соответствует союзу ИЛИ Обозначается ۷,+, Or или Логическая операция ДИЗЪЮНКЦИЯ (логическое сложение) Каждым двум простым высказываниям ставит в соответствие составное высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны, а истинным, когда хотя бы одно из двух исходных высказываний истинно. Операцию «ИЛИ» называют логическим сложением, потому что она похоже на обычное математическое сложение. Единственное отличие – в последней строке таблицы истинности: в математике 1+1 равно 2, а в алгебре логики – 1. Другое название операции «ИЛИ» – дизъюнкция (от латинского disjunctio – разделение).АВ А А ۷ В

Примеры: Определить значения истинности следующих высказываний: 1.7 – простое число или 9 – простое число 2.Число 2 четное или Это простое число 3.2 * 2 = 4 или Белые медведи живут в Африке 4.Каша – вкусное блюдо или Математика – интересный предмет 5.Луна – спутник Марса или Луна – спутник Земли 6.Сегодня плохая погода или Кислород – вода 7.Microsoft Word – текстовый редактор или Paint – графический редактор Ответ: истинными высказываниями являются: 1, 2, 3, 5, 7

Из двух простых высказываний постройте сложное и проверьте на истинность, используя логическую связку ИЛИ Пример: А=«Земля вращается вокруг Солнца» В=«Число 13 - чётное» АВА&ВА&В Проверьте таблицу истинности на примере АВА&ВА&В

Логическая операция ИНВЕРСИЯ (отрицание) Соответствует частице НЕ Обозначается А, ¬, NotАĀ01 10 Каждому простому высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицает.

Пример Рассмотрим высказывание: Неверно, что 4 делится на 3. Обозначим А = Число 4 делится на 3 Тогда логическая форма отрицания этого высказывания имеет вид: ~A

Задание: Сформулируйте отрицания следующих высказываний и укажите значения истинности полученных отрицаний: 1.Волга впадает в Каспийское море. 2.Число 28 не делится на число > Ответ: истинными высказываниями являются: 2

Логические основы компьютеров К. Поляков, Логическая операция разделительная дизъюнкция «исключающее ИЛИ» Высказывание «A B» истинно тогда, когда истинно А или B, но не оба одновременно (то есть A B). AB А B «Либо пан, либо пропал». A B = ¬A B + A ¬B Сложение по модулю два. Это название связано с тем, что ее результат равен остатку от деления «обычной» суммы A + B на 2:A B = (A + B) mod 2. Здесь mod обозначает операцию взятия остатка от деления.

Логическая операция ИМПЛИКАЦИЯ (логическое следование) Соответствует обороту ЕСЛИ…, ТО… Обозначается =>, Ставит в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно. Импликацию можно выразить через дизъюнкцию и отрицание: A B = ¬А B (1)АВ А А => В

Логические основы компьютеров К. Поляков, Импликация («если …, то …») «Если Вася идет гулять, то Маша сидит дома». A – «Вася идет гулять». B – «Маша сидит дома». Маша может пойти гулять (B=0), а может и не пойти (B=1)! ABА B А если Вася не идет гулять? ? ABА B

Примеры: Определить значения истинности следующих высказываний: 1.Если 12 делится на 6, то 12 делится на 3. 2.Если 11 делится на 6, то 11 делится на 3. 3.Если 15 делится на 6, то 15 делится на 3. 4.Если 15 делится на 3, то 15 делится на 6. 5.Если Саратов расположен на Неве, то белые медведи обитают в Африке. Ответ: истинными высказываниями являются: 1, 2, 3, 5

Из двух простых высказываний постройте сложное и проверьте на истинность, используя логическую связку ЕСЛИ…ТО Пример: А=«выглянет Солнце» В=«станет тепло» АВA В

Логическая операция ЭКВИВАЛЕНЦИЯ (эквивалентность) (равнозначность) Ставит в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны. Эквивалентность можно выразить через отрицание, дизъюнкцию и конъюнкцию: A B = (¬А B) (¬B А) (2) Возможно, вы заметили, что эквивалентность – это обратная операция для «исключающего ИЛИ» (проверьте по таблицам истинности), то есть A B = A B. Соответствует оборотам: ТОГДА И ТОЛЬКО ТОГДА; В ТОМ И ТОЛЬКО В ТОМ СЛУЧАЕ Обозначается; ~,, АВ А А В

Из двух простых высказываний постройте сложное и проверьте на истинность, используя логическую связку ТОГДА И ТОЛЬКО ТОГДА…КОГДА Пример: А=«треугольник прямоугольный» В=«квадрат большей стороны равен сумме квадратов других сторон» АВA В

Примеры: Определить значения истинности следующих высказываний: 1.12 делится на 6 тогда и только тогда, когда 12 делится на делится на 6 тогда и только тогда, когда 11 делится на делится на 6 тогда и только тогда, когда 15 делится на делится на 5 тогда и только тогда, когда 15 делится на 4. Ответ: истинными высказываниями являются: 1, 2

Логические основы компьютеров К. Поляков, Штрих Шеффера, «И-НЕ» ABА | B Базовые операции через «И-НЕ»: ABА | B

Логические основы компьютеров К. Поляков, Стрелка Пирса, «ИЛИ-НЕ» ABА B Базовые операции через «ИЛИ-НЕ»: Самостоятельно… !

Логические основы компьютеров К. Поляков, Формализация Прибор имеет три датчика и может работать, если два из них исправны. Записать в виде формулы ситуацию «авария». A – «Датчик 1 неисправен». B – «Датчик 2 неисправен». C – «Датчик 3 неисправен». Аварийный сигнал: X – «Неисправны два датчика». X – «Неисправны датчики 1 и 2» или «Неисправны датчики 1 и 3» или «Неисправны датчики 2 и 3» 3». логическая формула Формализация – это переход к записи на формальном языке! !

Объединенная таблица истинности АВ ¯А¯А¯А¯А А А => В А А В А А ۸ В А А ۷ В А А В

Демонстрационный вариант ЕГЭ 2013 г. ИНФОРМАТИКА и ИКТ, 11 класс. ( / 36) В экзаменационных заданиях используются следующие соглашения. 1. Обозначения для логических связок (операций): a) отрицание (инверсия, логическое НЕ) обозначается ¬ (например, ¬А); b) конъюнкция (логическое умножение, логическое И) обозначается /\ (например, А /\ В) либо & (например, А & В); c) дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/(например, А \/ В); d) следование (импликация) обозначается (например, А В); e) тождество обозначается (например, A B). Выражение A B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны); f) символ 1 используется для обозначения истины (истинного высказывания); символ 0 – для обозначения лжи (ложного высказывания). 2. Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А В и (¬А) \/ В равносильны, а А \/ В и А /\ В неравносильны (значения выражений разные, например, при А = 1, В = 0). 3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), тождество. Таким образом, ¬А /\ В \/ С /\ D означает то же, что и ((¬А) /\ В) \/ (С /\ D). Возможна запись А /\ В /\ С вместо (А /\ В) /\ С. То же относится и к дизъюнкции: возможна запись А \/ В \/ С вместо (А \/ В) \/ С. 4. Обозначения Мбайт и Кбайт используются в традиционном для информатики смысле – как обозначения единиц измерения, чьё соотношение с единицей «байт» выражается степенью двойки.

Aчемпионы | (бег & плавание) Бчемпионы & плавание Вчемпионы | бег | плавание Гчемпионы & Европа & бег & плавание Пусть K = «чемпионы»; L = «бег»; M = «плавание»; N = «Европа», тогда запрос А = K L M; Б = K M; В = K L M; Г = K N L M. X Y X Y Рис. 2. Х Y Рис. 1. X Y Задание 11. (Задание В8 демоверсии 2006 г.) В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции ИЛИ в запросе используется символ |, а для логической операции И - &. Решение. Решение задачи сводится с тому, чтобы расположить множества, состоящие из результатов поиска А-Г в порядке возрастания количества элементов. Воспользуемся тем, что логическое умножение для двух множеств равносильно их пересечению, а логическое сложение – их объединению. При этом при пересечении несовпадающих множеств в результате всегда получается множество, меньшее, чем исходные множества, а при объединении – большие, чем исходные (см. Рис. 1 – Рис. 2). Введем обозначения для множеств и запросов. Пусть K = «чемпионы»; тогда запрос А = K L M; L = «бег»; Б = K M; M = «плавание»; В = K L M; N = «Европа», Г = K N L Из обозначений запросов видно, что самым маленьким по количеству элементов будет множество Г (состоит из пересечений четырех множеств K, L, M, N). Самым большим множеством является множество В, т.к. оно состоит из объединений трех множеств K, L и M. Значит, ответ на Задание 11 будет выглядеть так: Г**В. Осталось определить, какие множества (из А и Б) будут стоять на 2 и 3 местах. Заметим, что множество Б состоит из пересечений двух множеств K и M, поэтому оно является множеством, меньшим К). Множество А состоит из объединения множества К с пересечением множеств L и M, поэтому А - множество, большее К. Значит, при расположении их в порядке возрастания, получим, что на втором месте в ответе будет стоять Б, а на третьем – А. Ответ: ГБАВ.