Основы логики

Логика Логика – это наука о формах и законах человеческой мысли, о законах доказательных рассуждений, изучающая методы доказательств и опровержений.

Высказывание может быть истинно или ложно. Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Алгебра логики Пример: 6- четное число следует считать высказыванием, т.к. оно истинное Пример: Рим – столица Франции Тоже высказывание, только ложное.

Алгебра логики Не всякое предложение является логическим высказыванием. Пример: «ученик 9 класса» и «информатика – интересный предмет» - не являются высказыванием. Почему? Пример: «в городе А более миллиона жителей» - является высказыванием?

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

1. Информатика изучается в курсе средней школы. 2.«Е»- шестая буква алфавита. 3. Квадрат является ромбом. 4. Квадрат гипотенузы равен сумме квадратов катетов. 5. Сумма углов треугольника равна >30 7. Графическое изображение векторной графики формируется из точек(пикселей) битные звуковые карты точнее кодируют и воспроизводят звук, чем 8-битные.

В алгебре высказываний высказывания обозначаются именами логических переменных, которые могут принимать лишь два значения «истинно» и «ложно». Истинно =1 Ложно=0

Для образования новых высказываний используются базовые логические операции: инверсия логическое отрицание операция не конъюнкция дизъюнкция логическое умножение операция и логическое сложение операция или операция или

Основные логические операции ИНВЕРСИЯ не Логическое отрицание - операция не Соответствует союзу НЕ; Обозначение А; В языках программирования not; Название: Отрицание. A

Логическое умножение КОНЪЮНКЦИЯ Соответствует союзу И; Обозначение &; В языках программирования and; Название: Логическое умножение. A B A·B

Логическое сложение ДИЗЪЮНКЦИЯ Соответствует союзу ИЛИ; Обозначение V; В языках программирования or; Название: Логическое сложение. A B A+B

13 ABА B Импликация («если …, то …») Логическое следование A B A B

Логическое равенство Эквиваленция («тогда и только тогда, …») A B

Логические операции Инверсия КонъюнкцияДизъюнкция ИмпликацияЭквиваленция Л о г и ч е с к о е отрицание умножениесложениеследование равенство В р у с с к о м я з ы к е частица «не»союз «и» союз «или»оборот речи «если…,то…» оборот речи «…т.т.т,...» О б о з н а ч е н и е Не А; А; А ; NOT A А и В; А В; А & В; А В; А and В А или В; А В; А В; А + В; А or В А В; А В А В; А В З н а ч е н и е в ы р а ж е н и я Истина, когда высказывание ложно, и наоборот Ложь, когда хотя бы одно высказывание ложно Истина, когда хотя бы одно высказывание истинно Ложно, когда из истинного следует ложное Истина, когда оба высказывания имеют одно значение

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

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

Порядок выполнения логических операций Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания (не), затем конъюнкция (и), после конъюнкции дизъюнкция (или) и в последнюю очередь импликация.

Определите значение истинности следующих высказываний: Бульдог – собака и 8 – четное число. Бульдог – собака или 8 – нечетное число. Если Волга впадает в Черное море, то белые медведи живут в Африке. Если платина – драгоценный металл, то все птицы летают.

Даны два высказывания А - «Студент сдал экзамены» В - «Студент едет на каникулы домой Сформулируйте следующие высказывания: А В; В А

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

Таблицы истинности 1. Количество строк = 2 ª, где а – количество переменных; 2. Количество столбцов = количество переменных + количество логических операций

построим таблицу истинности для логической функции: Количество входных переменных в заданном выражении равно трем (A,B,C). Значит, количество входных наборов, а значит и строк Q=2 3 =8. Количество столбцов равно 6 (3 переменные + 3 операции). Столбцы таблицы истинности соответствуют значениям исходных выражений A,B,C, промежуточных результатов и (B V C), а также искомого окончательного значения сложного арифметического выражения

ABCB V C

ABC

ABC

27 Составление таблиц истинности ABA·BA·BX Логические выражения могут быть: тождественно истинными (всегда 1, тавтология) тождественно ложными (всегда 0, противоречие) вычислимыми (зависят от исходных данных)

28 Составление таблиц истинности ABCABACBCX

Тождественная истина При всех наборах значений переменных x и y формула принимает значение 1, то есть является тождественно истинной.

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

Тождественная ложь При всех наборах значений переменных x и y формула принимает значение 0, то есть является тождественно ложной.

Определить истинность формулы

Для какого слова истинно высказывание (Вторая буква слова согласная + Последняя буква слова гласная) -> Первая буква слова гласная 1) Горе 2) Привет 3) Кресло 4) Закон

Для какого из указанных значений числа Х истинно высказывание (x>4) \/ ((x>1) (x>4))? 1)1 2) 23) 34) 4

Для какого числа Х истинно высказывание ((x>2) \/ (x 4)? 1) 12) 23) 34) 4

Для какого Х истинно высказывание ¬ ((x>3) (x>4))? 1) 12) 23) 34) 4

Закон Для ИЛИДля И Операция с константами Операция переменной с ее инверсией Двойного отрицания ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

Закон Для ИЛИДля И Переместительный Сочетательный Распределительный ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

42 Законы алгебры логики названиедля Идля ИЛИ двойного отрицания исключения третьего операции с константами повторения поглощения переместительный сочетательный распределительный законы де Моргана

43 Упрощение логических выражений Шаг 1. Заменить операции на их выражения через И, ИЛИ и НЕ: Шаг 2. Раскрыть инверсию сложных выражений по формулам де Моргана: Шаг 3. Используя законы логики, упрощать выражение, стараясь применять закон исключения третьего.

44 Упрощение логических выражений раскрыли формула де Моргана распределительный исключения третьего повторения поглощения

Упростить логические выражения: а) ¬(A \/ ¬B) б) ¬(¬А \/ B) \/ C в) A ^ ¬(¬B \/ C)

47 Логические уравнения A=0, B=1, C – любое 2 решения: (0, 1, 0), (0, 1, 1) A=0, B=1, C – любое 2 решения: (0, 1, 0), (0, 1, 1) или A=1, B=0, C=1 Всего 3 решения! ! K=1, L=1, M и N – любые 4 решения K=1, L=1, M и N – любые 4 решения M=1, L=1, N=1, K – любое 2 решения M=1, L=1, N=1, K – любое 2 решения K=1, L=1, M=0, N – любое 2 решения K=1, L=1, M=0, N – любое 2 решения Всего 5 решений! !

Высказывания А, В, С истинны для точек, принадлежащих кругу, треугольнику или прямоугольнику соответственно. Для всех точек выделенной на рисунке области истинно высказывание 1) (А или В) и В 2) (С и не А) и не В 3) (В или С) и не С 4) (В и С) и не А 5) (А и С) и не В

Высказывания А, В, С истинны для точек, принадлежащих кругу, треугольнику или прямоугольнику соответственно. Для всех точек выделенной на рисунке области истинно высказывание 1) (С и не А) и не В 2) (А и С) и не В 3) (В или С) и не С 4) (В и С) и не А 5) (А или В) и (А и В)

Высказывания А, В, С истинны для точек, принадлежащих кругу, треугольнику или прямоугольнику соответственно. Для всех точек выделенной на рисунке области истинно высказывание 1)(В и С) и не А 2)(В или С) и не С 3) (А и С) и не В 4) (С и не А) и не В 5) (А или В) и В

Высказывания А, В, С истинны для точек, принадлежащих кругу, треугольнику или прямоугольнику соответственно. Для всех точек выделенной на рисунке области истинно высказывание 1)В и не(А и не С) 2)А и не(В и С) 3) (А и В) или (А и С) 4) С и не(не В и А) 5) А и не (С или В)

53 Логические элементы компьютера & 11 & НЕ ИИЛИ ИЛИ-НЕ И-НЕ значок инверсии

54 Составление схем последняя операция - ИЛИ & 1 & & И И

55 Логические задачи

56 Метод рассуждений Задача 1. Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты договора, представленные каждой из стран. Отвечая затем на вопрос журналистов: «Чей именно проект был принят?», министры дали такие ответы: Россия «Проект не наш (1), проект не США (2)»; США «Проект не России (1), проект Китая (2)»; Китай «Проект не наш (1), проект России (2)». Один из них оба раза говорил правду; второй – оба раза говорил неправду, третий один раз сказал правду, а другой раз неправду. Кто что сказал? (1)(2) Россия США Китай проект России (?) – + – – + + (1)(2) Россия США Китай проект США (?) + – (1)(2) Россия США Китай проект Китая (?) + –

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

58 Использование алгебры логики Задача 3. Следующие два высказывания истинны: 1. Неверно, что если корабль A вышел в море, то корабль C – нет. 2. В море вышел корабль B или корабль C, но не оба вместе. Определить, какие корабли вышли в море. … если корабль A вышел в море, то корабль C – нет. 1. Неверно, что если корабль A вышел в море, то корабль C – нет. 2. В море вышел корабль B или корабль C, но не оба вместе. Решение:

59 Использование алгебры логики Задача 4. Когда сломался компьютер, его хозяин сказал «Память не могла выйти из строя». Его сын предположил, что сгорел процессор, а винчестер исправен. Мастер по ремонту сказал, что с процессором все в порядке, а память неисправна. В результате оказалось, что двое из них сказали все верно, а третий – все неверно. Что же сломалось? Решение: A – неисправен процессор, B – память, C – винчестер хозяин: сын: мастер: Если ошибся хозяин: Если ошибся сын: Если ошибся мастер: В общем случае: Несколько решений! !

60 Использование алгебры логики Задача 5. На вопрос «Кто из твоих учеников изучал логику?» учитель ответил: «Если логику изучал Андрей, то изучал и Борис. Однако неверно, что если изучал Семен, то изучал и Борис». Кто же изучал логику? Решение: A – логику изучал Андрей, B – Борис, C – Семен «Если логику изучал Андрей, то изучал и Борис». 1 способ: «Неверно, что если изучал Семен, то изучал и Борис».

61 Использование алгебры логики Задача 5. На вопрос «Кто из твоих учеников изучал логику?» учитель ответил: «Если логику изучал Андрей, то изучал и Борис. Однако неверно, что если изучал Семен, то изучал и Борис». Кто же изучал логику? Решение: A – логику изучал Андрей, B – Борис, C – Семен «Если логику изучал Андрей, то изучал и Борис». 2 способ: «Неверно, что если изучал Семен, то изучал и Борис». СBС B ABA B

62 Использование алгебры логики Задача 6. Суд присяжных пришел к таким выводам: если Аськин не виновен или Баськин виновен, то виновен Сенькин если Аськин не виновен, то Сенькин не виновен Виновен ли Аськин? Решение: A – виновен Аськин, B – Баськин, C – Сенькин «Если Аськин не виновен или Баськин виновен, то виновен Сенькин». «Если Аськин не виновен, то Сенькин не виновен». Аськин виновен

63 Использование алгебры логики Задача 6 б. Суд присяжных пришел к таким выводам: если Аськин не виновен или Баськин виновен, то виновен Сенькин если Аськин не виновен, то Сенькин не виновен Виновен ли Баськин? Решение: A – виновен Аськин, B – Баськин, C – Сенькин Не получили противоречия: возможно, что и виновен

64 Использование алгебры логики Задача 6 в. Суд присяжных пришел к таким выводам: если Аськин не виновен или Баськин виновен, то виновен Сенькин если Аськин не виновен, то Сенькин не виновен Виновен ли Сенькин? Решение: A – виновен Аськин, B – Баськин, C – Сенькин Не получили противоречия: возможно, что и виновен